Optimal trunk reservation for an overloaded link

We consider a single overloaded link with a large number of circuits which is offered two kinds of calls. The traffic intensity of the primary calls is assumed to be strictly less than 1, and R of the circuits are reserved for these. Rewards are generated when calls are accepted, and it is assumed that the reward for primary calls is greater than that for secondary calls. We determine the trunk reservation parameter R which asymptotically maximizes the long run average reward.     

Change in Network Revenue Due to Changes in Capacities of Links

A multirate, loss network is investigated. The intensities of the traffic carried on each link, and the link capacities, are assumed to be commensurately large. An asymptotic approximation to the change in network revenue, due to small changes in the capacities of the links, is derived. A significant advantage of this approximation is that it is not necessary to specify which links are overloaded, critically loaded, or underloaded. Moreover, it is shown how to asymptotically calculate the change in revenue in terms of quantities which are already known for the unchanged network. This result has been used to calculate linearized capacity costs in the joint resource allocation and routing design of virtual private networks.     

A critically loaded multirate link with trunk reservation

We consider a loss system model of interest in telecommunications. There is a single service facility with N servers and no waiting room. There are K types of customers, with type ί customers requiring A _ί servers simultaneously. Arrival processes are Poisson and service times are exponential. An arriving type ί customer is accepted only if there are Rί(⩾A_ί ) idle servers. We examine the asymptotic behavior of the above system in the regime known as critical loading where both N and the offered load are large and almost equal. We also assume that R ₁,..., R _K-1 remain bounded, while R _K ^N ←∞ and R _K ^N /√N ← 0 as N ← ∞. Our main result is that the K dimensional “queue length” process converges, under the appropriate normalization, to a particular K dimensional diffusion. We show that a related system with preemption has the same limit process. For the associated optimization problem where accepted customers pay, we show that our trunk reservation policy is asymptotically optimal when the parameters satisfy a certain relation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Light traffic for workload in queues

General exact light traffic limit theorems are given for the distribution of steadystate workloadV, in open queueing networks having as input a general stationary ergodic marked point process {(t _n ,K _n )n0 (where t_n denotes the arrival time and K_n the routing and service times of the nth customer). No independence assumptions of any kind are required of the input. As the light traffic regime, it is only required that the Palm distribution for the exogenous interarrival time converges weakly to infinity (while the service mechanism is not allowed to change much). As is already known in the context of a single-server queue, work is much easier to deal with mathematically in light traffic than is customer delayD, and consequently, our results are far more general than existing results forD. We obtain analogous results for multi-channel and infinite-channel queues. In the context of open queueing networks, we handle both the total workload in the network as well as the workload at isolated nodes.Research supported in part by the Japan Society for the Promotion of Science during the author's fellowship in Tokyo, and by NSF Grant DDM 895 7825.     

Asymptotic Analysis of a Loss Model with Trunk Reservation II: Trunks Reserved for Slow Traffic

We consider a model for a single link in a circuit switched network. The link has C circuits, and the input consists of offered calls of two types, that we call primary and secondary traffic. Of the C links R are reserved for primary traffic. We assume that both traffic types arrive as Poisson arrival streams. Assuming that C is large and   R = O (1)  , the arrival rate of secondary traffic is   O ( C )  while that of primary traffic is smaller, of the order     . The holding times of the secondary calls are assumed exponentially distributed with unit mean. Those of the primary calls are exponentially distributed with a large mean, that is     . The loads for both traffic types are thus comparable  ( O ( C ))  and we assume that the system is "critically loaded," i.e., the system's capacity is approximately equal to the total load. We analyze asymptotically the steady state probability that   n ₂  (resp.   n ₁  ) circuits are occupied by primary (resp. secondary) calls. In particular, we obtain two-term asymptotic approximations to the blocking probabilities for both traffic types. This work complements part I, where we assumed that the secondary traffic had an arrival rate that was     and a service rate that was     . Thus in part I the R trunks were reserved for the "fast traffic," whose arrival and service rates were   O ( C )  and   O (1)  .     

Susceptible-infected-recovered models with natural birth and death on complex networks

This paper proposes two modified susceptible-infected-recovered (SIRS) models on homogenous and heterogeneous networks, respectively. In the study of the homogenous network model, Lyapunov functions are used to study the globally asymptotically stable of the equilibria of the model. It is proved that if the basic reproduction number of the model is less than one, then the disease-free equilibrium is globally asymptotically stable, otherwise, the endemic equilibrium is globally asymptotically stable. In the study of the heterogeneous network model, the existences of the disease-free equilibrium and epidemic equilibrium of the model are discussed. A threshold value is given. It is proved that if the threshold value of the model is less than one, then the disease-free equilibrium is globally asymptotically stable. The simulation examples on the two SIRS models are given. Copyright © 2013 John Wiley & Sons, Ltd.     

Overflow and losses in a network queue with a self-similar input

This paper considers a discrete time queuing system that models a communication network multiplexer which is fed by a self-similar packet traffic. The model has a finite buffer of size h, a number of servers with unit service time, and an input traffic which is an aggregation of independent source-active periods having Pareto-distributed lengths and arriving as Poisson batches. The new asymptotic upper and lower bounds to the buffer-overflow and packet-loss probabilities P are obtained. The bounds give an exact asymptotic of log P/log h when h → to ∞. These bounds decay algebraically slow with buffer-size growth and exponentially fast with excess of channel capacity over traffic rate. Such behavior of the probabilities shows that one can better combat traffic losses in communication networks by increasing channel capacity rather than buffer size. A comparison of the obtained bounds and the known upper and lower bounds is done. This revised version was published online in June 2006 with corrections to the Cover Date.     

Designing Least-Cost Survivable Wireless Backhaul Networks

This paper presents a new heuristic algorithm for designing least-cost telecommunications networks to carry cell site traffic to wireless switches while meeting survivability, capacity, and technical compatibility constraints. This requires solving the following combinatorial optimization problems simultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; (2) Optimally assign traffic from other nodes to these hubs, so that the traffic entering the network at these nodes is routed to the assigned hubs while respecting capacity constraints on the links and routing-diversity constraints on the hubs to assure survivability; and (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these optimization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuristic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such backhaul networks for carrying personal communications services (PCS) traffic. It solves problems that are challenging for conventional branch-and-bound solvers in minutes instead of hours and finds lower-cost solutions. Applied to real-world network design problems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.     

Dynamic Safety-Stocks for Asymptotic Optimality in Stochastic Networks

This paper concerns control of stochastic networks using state-dependent safety-stocks. Three examples are considered: a pair of tandem queues; a simple routing model; and the Dai-Wang re-entrant line. In each case, a single policy is proposed that is independent of network load ρ?. The following conclusions are obtained for the controlled network in each case, where the finite constant K ₀ is independent of load: The policy is fluid-scale asymptotically optimal, and satisfies the bound 2 $$ eta_ast \le \eta \le \eta_\ast + K_0 \log(\eta_\ast),\quad 0 \le \rho_\bullet \le 1, $$ where η_* is the optimal steady-state cost. These results are based on the construction of an approximate solution to the average-cost dynamic programming equations using a perturbation of the value function for an associated fluid model. Moreover, a new technique is introduced to obtain fluid-scale asymptotic optimality for general networks modeled in discrete time. The proposed policy is myopic with respect to a perturbation of the value function for the fluid model.     

Stability of Earliest-Due-Date,First-Served Queueing Networks

We study multiclass queueing networks with the earliest-due-date, first-served (EDDFS) discipline. For these networks, the service priority of a customer is determined, upon its arrival in the network, by an assigned random due date. First-in-system, first-out queueing networks, where a customer's priority is given by its arrival time in the network, are a special case. Using fluid models, we show that EDDFS queueing networks, without preemption, are stable whenever the traffic intensity satisfies _j <1 for each station j.     

A Reduced-Load Equivalence for Generalised Processor Sharing Networks with Long-Tailed Input Flows

We consider networks where traffic is served according to the Generalised Processor Sharing (GPS) principle. GPS-based scheduling algorithms are considered important for providing differentiated quality of service in integrated-services networks. We are interested in the workload of a particular flow i at the bottleneck node on its path. Flow i is assumed to have long-tailed traffic characteristics. We distinguish between two traffic scenarios, (i) flow i generates instantaneous traffic bursts and (ii) flow i generates traffic according to an on/off process. In addition, we consider two configurations of feed-forward networks. First we focus on the situation where other flows join the path of flow i. Then we extend the model by adding flows which can branch off at any node, with cross traffic as a special case. We prove that under certain conditions the tail behaviour of the workload distribution of flow i is equivalent to that in a two-node tandem network where flow i is served in isolation at constant rates. These rates only depend on the traffic characteristics of the other flows through their average rates. This means that the results do not rely on any specific assumptions regarding the traffic processes of the other flows. In particular, flow i is not affected by excessive activity of flows with heavier-tailed traffic characteristics. This confirms that GPS has the potential to protect individual flows against extreme behaviour of other flows, while obtaining substantial multiplexing gains.     

Clifford algebra method for network expression,computation, and algorithm construction

Clifford algebra is introduced as a theoretical foundation for network topology expression and algorithm construction. Network nodes are coded with basis vectors in a vector space , and the edges and k‐walk routes can be expressed by 2‐blades and k‐blades, respectively, in the Clifford algebra Cl(n,0). The topologies among nodes, edges, and routes of networks can be directly calculated, and the network routes can be extended and traversed with oriented join products. The network algorithm construction processes based on Clifford algebra are instantiated by the single source shortest path algorithm. The experimental results on different scale random networks suggest that Clifford algebra is suited for network expression and relation computation. The Clifford algebra‐based shortest path algorithm is vivid and clear in geometric meaning and has great advantage on temporal and spatial complexity. Copyright © 2013 John Wiley & Sons, Ltd.     

Locating Active Sensors on Traffic Networks

Sensors are used to monitor traffic in networks. For example, in transportation networks, they may be used to measure traffic volumes on given arcs and paths of the network. This paper refers to an active sensor when it reads identifications of vehicles, including their routes in the network, that the vehicles actively provide when they use the network. On the other hand, the conventional inductance loop detectors are passive sensors that mostly count vehicles at points in a network to obtain traffic volumes (e.g., vehicles per hour) on a lane or road of the network.This paper introduces a new set of network location problems that determine where to locate active sensors in order to monitor or manage particular classes of identified traffic streams. In particular, it focuses on the development of two generic locational decision models for active sensors, which seek to answer these questions: (1) “How many and where should such sensors be located to obtain sufficient information on flow volumes on specified paths?”, and (2) “Given that the traffic management planners have already located count detectors on some network arcs, how many and where should active sensors be located to get the maximum information on flow volumes on specified paths?”The problem is formulated and analyzed for three different scenarios depending on whether there are already count detectors on arcs and if so, whether all the arcs or a fraction of them have them. Location of an active sensor results in a set of linear equations in path flow variables, whose solution provide the path flows. The general problem, which is related to the set-covering problem, is shown to be NP-Hard, but special cases are devised, where an arc may carry only two routes, that are shown to be polynomially solvable. New graph theoretic models and theorems are obtained for the latter cases, including the introduction of the generalized edge-covering by nodes problem on the path intersection graph for these special cases. An exact algorithm for the special cases and an approximate one for the general case are presented.     

Routing and capacity assignment in backbone communication networks under time varying traffic conditions

This paper studies the problem of assigning capacities to links in a backbone communication network and determining the routes used by messages for all communicating node pairs in the network under time varying traffic conditions. The best routes are to be chosen from among all possible routes in the network. Tradeoffs between link costs and response time to users are achieved by specifying an upper limit on the average link queueing delay in the network. The goal is to minimize total link fixed and variable costs. The topology of the network and the end-to-end traffic requirements during the different busy-hours are assumed to be known. The problem is formulated as a mathematical programming model. An efficient solution procedure based on a Lagrangian relaxation of the problem is developed. The results of extensive computational experiments across a variety of networks are reported. These results indicate that the solution procedure is effective for a wide range of traffic loads and cost structures.     

Some applications of the asymptotic distribution of likelihood functions to the asymptotic efficiency of estimates

Summary In the present paper, a Markov process is considered whose distribution depends on a k-dimensional parameter . Under suitable regularity conditions on the process, which include the differentiability in quadratic mean of a certain random function, attention is first focused to the class of estimates of which, properly normalized, are asymptotically normal. Within this class the subclass of estimates of which are asymptotically efficient is characterized. As a criterion of asymptotic efficiency we use the covariance of the asymptotic distribution of the estimates.Secondly, a class of estimates of is considered defined by the requirement that the estimates, properly normalized, have an asymptotic distribution which need not be normal. Again within this class the subclass of asymptotically efficient estimates of is characterized. The adopted criterion of asymptotic efficiency here is the asymptotic concentration of the estimates about certain hyperplanes.Finally, the above results are specialized to the independent identically distributed case.This paper was part of an invited address presented at the annual meeting of the Institute of Mathematical Statistics in Madison, Wisconsin, August 27–30, 1968.I would like to thank my colleague R. A. Johnson for constructive discussions in connection with this paper.     

Bottleneck analysis in multiclass closed queueing networks and its application

Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date.     

Continuous-Review Tracking Policies for Dynamic Control of Stochastic Networks

This paper is concerned with dynamic control of stochastic processing networks. Specifically, it follows the so called heavy traffic approach, where a Brownian approximating model is formulated, an associated Brownian optimal control problem is solved, the solution of which is then used to define an implementable policy for the original system. A major challenge is the step of policy translation from the Brownian to the discrete network. This paper addresses this problem by defining a general and easily implementable family of continuous-review tracking policies. Each such policy has the following structure: at each point in time t, the controller observes the current vector of queue lengths q and chooses (i) a target position z(q) of where the system should be at some point in the near future, say at time t+l, and (ii) an allocation vector v(q) that describes how to split the server's processing capacity amongst job classes in order to steer the state from q to z(q). Implementation of such policies involves the enforcement of small safety stocks. In the context of the heavy traffic approach, the solution of the approximating Brownian control problem is used in selecting the target state z(q). The proposed tracking policy is shown to be asymptotically optimal in the heavy traffic limiting regime, where the Brownian model approximation becomes valid, for multiclass queueing networks that admit orthant Brownian optimal controls; this is a form of pathwise, or greedy, optimality. Several extensions are discussed.     

Design of trees in the hose model: The balanced case

In the hose model we are given upper bounds on the amount of traffic entering/leaving a node. We show that when , designing a minimum cost tree network is easy and the cost of an optimal tree reservation is within a factor of three of the cost of any reservation.     

Bias optimality of admission control in a non-stationary repairable queue

We study a non-stationary repairable queue with a single server and multiple customers’ types. The difference between types of customers is defined by the offered rewards. We show that the bias optimal policy has the trunk reservation (threshold) form. Furthermore, under some given conditions, we also prove that the control level of the bias optimal policy is monotone about time.     

The blocking probability of spider-web networks

We determine the limiting behavior of the blocking probability for spider-web networks, a class of crossbar switching networks proposed by Ikeno. We use a probabilistic model proposed by the author, in which the busy links always form disjoint routes through the network. We show that if the occupancy probability is below the threshold 2 - √2 = 0.5857…, then the blocking probability tends to zero, whereas above this threshold it tends to one. This provides a theoretical explanation for results observed empirically in simulations by Bassalygo, Neiman, and Vvedenskaya.