Asymptotically optimal importance sampling for Jackson networks with a tree topology

This note describes an importance sampling (IS) algorithm to estimate buffer overflows of stable Jackson networks with a tree topology. Three new measures of service capacity and traffic in Jackson networks are introduced and the algorithm is defined in their terms. These measures are effective service rate, effective utilization and effective service-to-arrival ratio of a node. They depend on the nonempty/empty states of the queues of the network. For a node with a nonempty queue, the effective service rate equals the node’s nominal service rate. For a node i with an empty queue, it is either a weighted sum of the effective service rates of the nodes receiving traffic directly from node i, or the nominal service rate, whichever smaller. The effective utilization is the ratio of arrival rate to the effective service rate and the effective service-to-arrival ratio is its reciprocal. The rare overflow event of interest is the following: given that initially the network is empty, the system experiences a buffer overflow before returning to the empty state. Two types of buffer structures are considered: (1) a single system-wide buffer shared by all nodes, and (2) each node has its own fixed size buffer. The constructed IS algorithm is asymptotically optimal, i.e., the variance of the associated estimator decays exponentially in the buffer size at the maximum possible rate. This is proved using methods from (Dupuis et al. in Ann. Appl. Probab. 17(4):1306–1346, 2007), which are based on a limit Hamilton–Jacobi–Bellman equation and its boundary conditions and their smooth subsolutions. Numerical examples involving networks with as many as eight nodes are provided.     

Analysis of a tandem network model of a single-router Network-on-Chip

We study a single-router Network-on-Chip modelled as a tandem queueing network. The first node is a geo ^K /D/1 queue (K fixed) representing a network interface, and the second node is a ./G/1 queue representing the packet switch. If K>1 we have train arrivals at the second node. If K=1 the arrival process of the second node reduces to a Bernoulli process. In the latter case, routers have been studied extensively as part of ATM and LAN networks under the assumption that the number of input ports N tends to infinity. In Networks-on-Chips N is usually 4 or 5 and results for ATM and LAN routers lead to inaccurate results. We introduce a new approximation scheme that yields accurate results for small switches. In addition to this we analyse the tandem network, both for K=1 and K>1, and we approximate the mean sojourn time in the switch and the mean end-to-end delay. If N=4 our approximation has a relative error of only 4.5% if K=6 and 1% if K=1.     

Monitoring the packet gap of real-time packet traffic

Real-time packet traffic is characterized by a strict deadline on the end-to-end time delay and an upper bound on the information loss. Due to the high correlation among consecutive packets, the individual packet loss does not well characterize the performance of real-time packet sessions. An additional measure of packet loss is necessary to adequately assess the quality of each real-time connection. The additional measure considered here is the average number of consecutively lost packets, also called the average packet gap. We derive a closed form for the average packet gap for the multiclassG/G/m/B queueing system in equilibrium and show that it only depends on the loss behavior of two consecutive packets. This result considerably simplifies the monitoring process of real-time packet traffic sessions. If the packet loss process is markovian, the consecutive packet loss has a geometric distribution.     

A queueing network with a single cyclically roving server

A queueingnetwork that is served by asingle server in a cyclic order is analyzed in this paper. Customers arrive at the queues from outside the network according to independent Poisson processes. Upon completion of his service, a customer mayleave the network, berouted to another queue in the network orrejoin the same queue for another portion of service. The single server moves through the different queues of the network in a cyclic manner. Whenever the server arrives at a queue (polls the queue), he serves the waiting customers in that queue according to some service discipline. Both the gated and the exhaustive disciplines are considered. When moving from one queue to the next queue, the server incurs a switch-over period. This queueing network model has many applications in communication, computer, robotics and manufacturing systems. Examples include token rings, single-processor multi-task systems and others. For this model, we derive the generating function and the expected number of customers present in the network queues at arbitrary epochs, and compute the expected values of the delays observed by the customers. In addition, we derive the expected delay of customers that follow a specific route in the network, and we introduce pseudo-conservation laws for this network of queues.Summary of notation B_i, B _i ^* (s) service time of a customer at queue i and its LST - b_i, b_i ⁽²⁾ mean and second moment of B_i - R_i, R _i ^* (s) duration of switch-over period from queue i and its LST - r_i, r_i mean and second moment of R_i - r, r⁽²⁾ mean and second moment of _i ^N =₁R_i - _i external arrival rate of type-i customers - _i total arrival rate into queue i - _i utilization of queue i; _i=_i - system utilization _i ^N =_1i - c=E[C] the expected cycle length - X _i ^j number of customers in queue j when queue i is polled - X_i=X _i ⁱ number of customers residing in queue i when it is polled - f_i(j) - X _i ^* number of customers residing in queue i at an arbitrary moment - Y_i the duration of a service period of queue i - W_i,T_i the waiting time and sojourn time of an arbitary customer at queue i - F^*(z₁, z₂,..., z_N) GF of number of customers present at the queues at arbitrary moments - F_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at polling instants of queue i - ¯F_i(z₁, z₂,...,z_N) GF of number of customers present at the queues at switching instants of queue i - V_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at service initiation instants at queue i - ¯V_i(z₁,z₂,...,z_N) GF of number of customers present at the queues at service completion instants at queue i The work of this author was supported by the Bernstein Fund for the Promotion of Research and by the Fund for the Promotion of Research at the Technion.Part of this work was done while H. Levy was with AT&T Bell Laboratories.     

Delay and partial system contents for a discrete-time G-D-c queue

We consider a discrete-time multiserver queueing system with infinite buffer size, constant service times of multiple slots and a first-come-first-served queueing discipline. A relationship between the probability distributions of the partial system contents and the packet delay is established. The relationship is general in the sense that it doesn’t require knowledge of the exact nature of the arrival process. By means of the relationship, results for the distribution of the partial system contents for a wide variety of discrete-time queueing models can be transformed into corresponding results for the delay distribution. As a result, a separate full analysis of the packet delay becomes unnecessary.      

Dynamic power control in a fading downlink channel subject to an energy constraint

A central controller chooses a state-dependent transmission rate for each user in a fading, downlink channel by varying transmission power over time. For each user, the state of the channel evolves over time according to an exogenous continuous-time Markov chain (CTMC), which affects the quality of transmission. The traffic for each user, arriving at the central controller, is modeled as a finite-buffer Markovian queue with adjustable service rates. That is, for each user data packets arrive to the central controller according to a Poisson process and packet size is exponentially distributed; an arriving packet is dropped if the associated buffer is full, which results in degradation of quality of service. The controller forwards (downlink) the arriving packets to the corresponding user according to an optimally chosen transmission rate from a fixed set A _i of available values for each user i, depending on the backlog in the system and the channel state of all users. The objective is to maximize quality of service subject to an upper bound on the long-run average power consumption. We show that the optimal transmission rate for each user is solely a function of his own packet queue length and channel state; the dependence among users is captured through a penalty rate. Further, we explicitly characterize the optimal transmission rate for each user. This project is partially supported by Motorola grant # 0970-350-AF24. The authors thank Phil Fleming,Randy Berry and Achal Bassamboo for helpful comments.     

Instability of FIFO in session-oriented networks

We show that the First-In-First-Out (FIFO) scheduling discipline can be unstable in the (σ,ρ)-regulated session model for packet-switched networks. In this model packets are injected into the network in fixed sessions. The total size of the session-i packets injected during the time interval [x,y) is at most σ_i+ρ_i(y−x) for some burst parameter σ_i and rate ρ_i. The sum of the rates of sessions passing through a server is at most the server speed.Previous work on FIFO stability either allowed for dynamically changing session paths or else assumed that session-i packets are injected at a constant rate. Our result shows that FIFO can be unstable for static paths as long as the injections into a session can be temporarily suspended.     

On queueing delays of dispersed messages

We study the message queueing delays in a node of a communication system, where a message consists of a block of consecutive packets. The message delay is defined as the time elapsing between the arrival epoch of the first packet of the message to the system until after the transmission of the last packet of that message is completed. We distinguish between two types of message generation processes. The message can be generated as abatch or it can bedispersed over time. In this paper we focus on the dispersed generation model. The main difficulty in the analysis is due to the correlation between the system states observed by different packets of the same message. This paper introduces a new technique to analyze the message delay in such systems for different arrival models and different number of sessions. For anM/M/1 system with variable size messages and for the bursty traffic model, we obtain an explicit expression for the Laplace-Stieltjes transform (LST) of the message delay. Derivations are also provided for anM/G/1 system, for multiple session systems and for fixed message sizes. We show that the correlation has a strong effect on the performance of the system, and that the commonly usedindependence assumption, i.e., the assumption that the delays of packets are independent from packet to packet, can lead to wrong conclusions.     

Scheduling policies using marked/phantom slot algorithms

We address the problem of schedulingM customer classes in a single-server system, with customers arriving in one ofN arrival streams, as it arises in scheduling transmissions in packet radio networks. In general,NM and a customer from some stream may join one of several classes. We consider a slotted time model where at each scheduling epoch the server (channel) is assigned to a particular class (transmission set) and can serve multiple customers (packets) simultaneously, one from every arrival stream (network node) that can belong to this class. The assignment is based on arandom polling policy: the current time slot is allocated to theith class with probability _i. Our objective is to determine the optimal probabilities by adjusting them on line so as to optimize some overall performance measure. We present an approach based on perturbation analysis techniques, where all customer arrival processes can be arbitrary, and no information about them is required. The basis of this approach is the development of two sensitivity estimators leading to amarked slot and aphantom slot algorithm. The algorithms determine the effect of removing/ adding service slots to an existing schedule on the mean customer waiting times by directly observing the system. The optimal slot assignment probabilities are then used to design adeterministic scheduling policy based on the Golden Ratio policy. Finally, several numerical results based on a simple optimization algorithm are included.This work was supported by the Naval Research Laboratory under contracts N000014-91-J-2025 and N000014-92-J-2017, by the National Science Foundation under grant EID-9212122, and by the Rome Laboratory under contract F30602-94-C-0109.     

Multiset Permutations and Loopless Generation of Ordered Trees with Specified Degree Sequence

An ordered tree with specified degree sequence and n internal nodes has a_i nodes of degree i, where a₀ = 1 + ∑_i = 1(i − 1)a_i and n = ∑_i = 0a_i. This paper presents the first loopless algorithm for generating all ordered trees with specified degree sequence. It uses a new version of the algorithm for generating multiset permutations. When a_k = N, a₀ = (k − 1)N + 1, and all other a_i's are 0, all N node k-ary trees are generated.     

Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models

The optimal scheduling problem in two queueing models arising in multihop radio networks with scheduled link activation is investigated. A tandem radio network is considered. Each node receives exogenous arriving packets which are stored in its unlimited capacity buffer. Links adjacent to the same node cannot transmit simultaneously because of radio interference constraints. The problem of link activation scheduling for minimum delay is studied for two different traffic types. In the first type all packets have a common destination that is one end-node of the tandem. In this case the system is modeled by a tandem queueing network with dependent servers. The server scheduling policy that minimizes the delay is obtained. In the second type of traffic, the destination of each packet is an immediate neighbor of the node at which the packet enters the network. In this case the system corresponds to a set of parallel queues with dependent servers. It is shown that the optimal policy activates the servers so that the maximum number of packets are served at each slot.     

Analysis of a two-stage network server

This paper presents modeling and analysis of a finite-queuing system of a server with two stages of service. In real life, such systems may represent typical network servers or client machines where network packets arrive and get queued to be served sequentially in two stages in a mutually exclusion fashion. That is, packets will be served by a first stage followed by a second stage, with only one stage being active at a time. In this paper, we present two equivalent analytical models to study and analyze the behavior of such systems. We derive equations for key features and performance measures of engineering and design significance. These features and measures include throughput, packet loss, packet delay, and server CPU utilization.     

Exact emulation of a priority queue with a switch and delay lines

All-optical packet switched networking is hampered by the problem of realizing viable queues for optical packets. Packets can be buffered in delay lines, but delay lines do not functionally emulate queues from an input-output point of view. In this paper we consider the problem of exact emulation of a priority queue of size K using a switching system comprised of a switch of size (M + 1) × (M + 1), which has one distinguished input for external arrivals, one distinguished output for external departures, and fixed-length delay lines of lengths L₁, L₂, ..., L_M connecting the other inputs and outputs in pairs. We measure the complexity of such an emulation by M + 1. We prove that and present a construction which works with ; further, in our construction . We also sketch an idea for an all-optical packet switched communication network architecture based on approximate emulation of priority queues of finite size using switches and delay lines, with erasure control coding at the packet level. AMS 2000 subject classifications: Primary: 60K25; Secondary: 90B22 · 90B36 · 68R99 The work of A. D. Sarwate is supported by an NDSEG Graduate Research Fellowship which is sponsored by the U.S. Department of Defense. The work of V. Anantharam is supported by ONR grant No. N00014-1-0637, DARPA grant No. N66001-00-C-8062, and by NSF grant No. ECS 0123512.     

Queueing models for the analysis of communication systems

Queueing models can be used to model and analyze the performance of various subsystems in telecommunication networks; for instance, to estimate the packet loss and packet delay in network routers. Since time is usually synchronized, discrete-time models come natural. We start this paper with a review of suitable discrete-time queueing models for communication systems. We pay special attention to two important characteristics of communication systems. First, traffic usually arrives in bursts, making the classic modeling of the arrival streams by Poisson processes inadequate and requiring the use of more advanced correlated arrival models. Second, different applications have different quality-of-service requirements (packet loss, packet delay, jitter, etc.). Consequently, the common first-come-first-served (FCFS) scheduling is not satisfactory and more elaborate scheduling disciplines are required. Both properties make common memoryless queueing models (M/M/1-type models) inadequate. After the review, we therefore concentrate on a discrete-time queueing analysis with two traffic classes, heterogeneous train arrivals and a priority scheduling discipline, as an example analysis where both time correlation and heterogeneity in the arrival process as well as non-FCFS scheduling are taken into account. Focus is on delay performance measures, such as the mean delay experienced by both types of packets and probability tails of these delays.     

Structural properties and stochastic bounds for a buffer problem in packetized voice transmission

We consider a communication channel which carries packetized voice. A fixed number (K) of calls are being transmitted. Each of these calls generates one packet at everyC timeslots and the channel can transmit at most one packet every timeslot. We consider the nontrivial caseK ≤C. We study the effectsK, C and the arrival process have on the number of packets in the buffer. When the call origination epochs in the firstC timeslots of theK calls are uniformly distributed (i.e. when the arrivals during the firstC timeslots have a multinomial distribution) it is shown that the stationary number of calls waiting in the buffer is stochastically increasing and convex in the number of calls. For a fixed average number of calls per slot, it is shown that increasing the number of slots per frame increases the stationary number of packets in the buffer in the sense of increasing convex ordering. Using this, it is shown that the stationary number of packets in the buffer is bounded from above by the number of packets in a stationary discreteM/D/1 queue with arrival rateK/C and unit service time. This bound is in the sense of the increasing convex order.     

Multi-objective OLSR for proactive routing in MANET with delay,energy, and link lifetime predictions

In this paper, we develop a multi-objective approach for proactive routing in a Mobile Ad Hoc Network (MANET). We consider three routing objectives: minimizing average end-to-end delay, maximizing network energy lifetime, and maximizing packet delivery ratio. Accordingly, we develop three routing metrics: mean queuing delay on each node, energy cost on each node, and link stability on each link. For the proposed multi-objective approach, we develop efficient prediction methods: (a) predicting queuing delay and energy consumption using double exponential smoothing, and (b) predicting residual link lifetime using a heuristic of the distributions of the link lifetimes in MANET. Extensive simulation (by using ns2) is performed for the comparison of this multi-objective OLSR with existing OLSRs. The results show that the multi-objective OLSR is effective in finding optimal routing by tradeoffs among proposed objectives.     

Analysis of queueing policies in QoS switches

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the “best effort” approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst-case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.     

Cyclic Bernoulli polling

We introduce, analyse and optimize the class of Bernoulli random polling systems. The server movescyclically among N channels (queues), butChange-over times between stations are composed ofwalking times required to move from one channel to another andswitch-in times that are incurredonly when the server actually enters a station to render service. The server uses aBernoulli random mechanism to decide whether to serve a queue or not: upon arrival to channeli, it switches in with probabilityp _i , or moves on to the next queue (w.p. 1 —p _i ) without serving any customer (e.g. packet or job). The Cyclic Bernoulli Polling (CBP) scheme is independent of the service regime in any particular station, and may be applied to any service discipline. In this paper we analyse three different service disciplines under the CBP scheme: Gated, Partially Exhaustive and Fully Exhaustive. For each regime we derive expressions for (i) the generating functions and moments of the number of customers (jobs) at the various queues at polling instants, (ii) the expected number of jobs that an arbitrary departing job leaves behind it, and (iii) the LST and expectation of the waiting time of a cutomer at any given queue. The fact that these measures of performance can be explicitly obtained under the CBP is an advantage over all parameterized cyclic polling schemes (such as the k-limited discipline) that have been studied in the literature, and for which explicit measures of performance are hard to obtain. The choice of thep _i 's in the CBP allows for fine tuning and optimization of performance measures, as well as prioritization between stations (this being achieved at a low computational cost). For this purpose, we develop a Pseudo-conservation law for amixed system comprised of channels from all three service disciplines, and define a Mathematical Program to find the optimal values of the probabilities {p _i } _i ^N =1 so as to minimize the expected amount of unfinished work in the system. Any CBP scheme for which the optimalp _i 's are not all equal to one, yields asmaller amount of the expected unfinished work in the system than that in the standard cyclic polling procedure with equivalent parameters. We conclude by showing that even in the case of a single queue, it is not always true thatp ₁=1 is the best strategy, and derive conditions under which it is optimal to havep ₁ < 1.Supported by a Grant from the France-Israel Scientific Cooperation (in Computer Science and Engineering) between the French Ministry of Research and Technology and the Israeli Ministry of Science and Technology, Grant Number 3321190.     

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.     

Towards better multi-class parametric-decomposition approximations for open queueing networks

Methods are developed for approximately characterizing the departure process of each customer class from a multi-class single-server queue with unlimited waiting space and the first-in-first-out service discipline. The model is (GT _i /GI _i )/1 with a non-Poisson renewal arrival process and a non-exponential service-time distribution for each class. The methods provide a basis for improving parametric-decomposition approximations for analyzing non-Markov open queueing networks with multiple classes. For example, parametric-decomposition approximations are used in the Queueing Network Analyzer (QNA). The specific approximations here extend ones developed by Bitran and Tirupati [5]. For example, the effect of class-dependent service times is considered here. With all procedures proposed here, the approximate variability parameter of the departure process of each class is a linear function of the variability parameters of the arrival processes of all the classes served at that queue, thus ensuring that the final arrival variability parameters in a general open network can be calculated by solving a system of linear equations.