Sticky States in Banyan Network Queues and Their Application to Analysis

A finite-buffered banyan network analysis technique designed to model networks at high traffic loads is presented. The technique specially models two states of the network queues: queue empty and queue congested (roughly, zero or one slots free). A congested queue tends to stay congested because packets bound for the queue accumulate in the previous stage. The expected duration of this state is computed using a probabilistic model of a switching module feeding the congested queue. A technique for finding a lower arrival rate to an empty queue is also described. The queues themselves are modeled using independent Markov chains with an additional congested state added. The new analysis technique is novel in its modeling the higher arrival rate to a congested queue and a lower arrival rate to an empty queue. Comparison of queue state distributions obtained with the analysis and simulation shows that an important feature of congestion is modeled.     

Access control to two multiserver loss queues in series

We consider admission policies to two multiserver loss queues in series with two types of traffic. Both are generated according to independent Poisson processes with constant arrival rates. The first type requires service at the first queue and with a positive probability enters the second queue; the second type requires service at only the second queue. The service time distribution is exponential at either station. We show that under appropriate conditions the optimal admission policy that maximizes the expected total discounted reward over an infinite horizon is given by a switching curve. We characterize the form and shape of this curve and its variation with system parameters     

Fuzzy-Based Dynamic Distributed Queue Scheduling for Packet Switched Networks

Addressing the problem of queue scheduling for the packet-switched system is a vital aspect of congestion control. In this paper, the fuzzy logic based decision method is adopted for queue scheduling in order to enforce some level of control for traffic of different quality of service requirements using predetermined values. The fuzzy scheduler proposed in this paper takes into account the dynamic nature of the Internet traffic with respect to its time-varying packet arrival process that affects the network states and performance. Three queues are defined, viz low, medium and high priority queues. The choice of prioritizing packets influences how queues are served. The fuzzy scheduler not only utilizes queue priority in the queue scheduling scheme, but also considers packet drop susceptibility and queue limit. Through simulation it is shown that the fuzzy scheduler is more appropriate for the dynamic nature of Internet traffic in a packet-switched system as compared with some existing queue scheduling methods. Results show that the scheduling strategy of the proposed fuzzy scheduler reduces packet drop, provides good link utilization and minimizes queue delay as compared with the priority queuing (PQ), first-in-first-out (FIFO), and weighted fair queuing (WFQ).     

Decomposition of general tandem queueing networks with MMPP input

For tandem queueing networks with generally distributed service times, decomposition often is the only feasible solution method besides simulation. The network is partitioned into individual nodes which are analyzed in isolation. In most existing decomposition algorithms for continuous-time networks, the output of a queue is usually approximated as a renewal process, which becomes the arrival process to the next queue. In this paper, the internal traffic processes are described as semi-Markov processes (SMPs) and Markov modulated Poisson processes (MMPPs). Thus, correlations in the traffic streams, which are known to have a considerable impact on performance, are taken into account to some extent. A two-state MMPP, which arises frequently in communications modeling, serves as input to the first queue of the tandem network. Furthermore, the single nodes may have infinite or finite buffers. Customers who arrive at a full buffer will get lost.

In principle, the analysis of an individual queue as an MMPP/G/1(/K) system delivers a wide range of performance measures. For different examples of tandem networks, stationary mean queue lengths at arbitrary time are compared to simulation data. The relative errors of the results, which are computed promptly by the decomposition component of the tool TimeNET, remain within a reasonable range.     

Performance of a beacon enabled IEEE 802.15.4 cluster with downlink and uplink traffic

The performance of an IEEE 802.15.4 compliant network operating in the beacon enabled mode with both downlink and uplink traffic is analyzed through discrete time Markov chains and the theory of M/G/1 queues. The model considers acknowledged transmissions and includes the impact of different network and traffic parameters such as the packet arrival rate, packet size, inactive period between the beacons, and the number of stations. We investigate the nonsaturation region and outline the conditions under which the network abruptly goes to saturation. The analysis of stability of the network queues shows that the stability of the downlink queue at the coordinator is the most critical for network operation. Due to the abruptness with which the switch from nonsaturation to saturation occurs, the network operating point has to be carefully chosen according to the volume of downlink traffic. Furthermore, our model shows that certain features prescribed by the standard actually limit the performance of 802.15.4 networks.     

Queueing systems with random service rate

We consider a queue with the arrival process, the service time process and the service rate process as regenerative processes. We provide conditions for its stability, rates of convergence, finiteness of moments and functional limit theorems. This queue can model a queue serving ABR and UBR traffic in an ATM switch; a multiple access channel with TDMA or CDMA protocol and fading; a queue holding best effort or controlled and guaranteed traffic in a router in the integrated service architecture (ISA) of IP-based Internet and a scheduler in the router of a differentiated service architecture. In the process we also provide results for a queue with a leaky bucket controlled bandwidth scheduler. This result is of independent interest. We extend these results to feed-forward networks of queues. We also obtain the results when the arrival rate to the queue can be feedback controlled based on the congestion information in the queue (as in ABR service in the ATM networks or in the real time applications controlled by RTCP protocol in the Internet).     

Proof of stability conditions for token passing rings by Lyapunovfunctions

A token passing ring can be described as a system of M queues with one server that rotates around the queues sequentially. Georgiadis-Szpankowski (1992) considered rings where the token (server) performs x ∇ l_j services on queue j, where x is the size of queue j upon arrival of the token, and l_j is a fixed limit of service for queue j. The token then spends some random time switching to the next queue. For j=1, ..., M, arrivals to queue j are Poisson with rate λ_j, and service times have mean s _j and are independent of the arrival and switchover processes. The purpose of this paper is to give an alternate and simpler proof of the stability conditions given by Georgiadis-Szpankowski using Lyapunov functions. An additional assumption is made about the second moments of the service and switchover times being finite     

Modeling and performance analysis for IPv6 traffic with multiple QoS classes

This paper focuses on the modeling and performance analysis for IPv6 traffic with multi-class QoS in virtual private networks (VPN). The multi-class QoS is implemented on differentiated service basis using priority scheme of 4 bits defined in the packet header of IPv6. A VPN-enabled IP router is modeled as a tandem queuing system in which each output link consists of two parallel priority output queues. The high-priority queue is used to carry the delay sensitive traffic while the low-priority queue is used to carry the delay insensitive traffic. On the other hand, multiple thresholds are implemented in each queue, respectively, for packet loss priority control. The performance analysis is done using fluid flow techniques. The numerical results obtained from the analysis show that the differentiated service based on the priority schemes defined in IPv6 is able to effectively satisfy the multi-class QoS requirement for supporting multimedia services in VPN. The performance trade-off between the delay sensitive traffic and delay insensitive traffic in terms of traffic throughput, packet loss probability and end-to-end delay in VPN networks is presented.     

基于车辆载带中继的路边单元突发业务分组调度最优策略

高速公路车联网场景中, 路边单元(Roadside units, RSUs)可作为多种周边监测数据的汇入网关, 其业务具有突发特性, 且可通过移动车辆以“存储?载带?转发”方式传输到与骨干网络互联的RSU. 针对RSU间业务传输问题, 源RSU可根据实时业务到达率按需匹配资源, 以应对业务突发性对分组端到端时延的影响. 本文首先针对RSU突发业务传输过程建立突发业务到达模型、车辆到达模型和离散车速状态模型; 进而利用受限马尔科夫决策过程对系统状态转移过程进行分析, 并建立非线性平均端到端时延最小化问题; 最后通过分析最优解的形式得出最优分组调度策略具有门限结构. 仿真结果验证了RSU间业务传输过程中排队时延和传播时延之间存在折中, 且该分组调度策略能降低业务传输过程的平均端到端时延.     

Mean-delay approximation for cyclic-service queueing systems

This paper investigates mean delays in a single-server queueing model with cyclic service. An approximate analysis is performed for an arbitrary number of queues, constant switch-over time, exhaustive service discipline, Poisson arrival processes, and general service-time distributions. Neither inter-arrival nor service-time distributions have to be identical for the different queues. A major value of our approximation lies in the simplicity of its numerical evaluation for an arbitrary number of queues and any traffic pattern. Extensive comparisons with simulation results show the high accuracy of the approximation over a wide range of parameters.     

Performance analysis of networks of queues under active queue management scheme

Analysis of networks of queues under repetitive service blocking mechanism has been presented in this paper. Nodes are connected according to an arbitrary configuration and each node in the networks employs an active queue management (AQM) based queueing policy to guarantee certain quality of service for multiple class external traffic. This buffer management scheme has been implemented using queue thresholds. The use of queue thresholds is a well known technique for network traffic congestion control. The analysis is based on a queue-by-queue decomposition technique where each queue is modelled as a GE/GE/1/N queue with single server, R (R ⩾ 2) distinct traffic classes and {N = N₁, N₂, … , N_R} buffer threshold values per class under first-come-first-serve (FCFS) service rule. The external traffic is modelled using the generalised exponential (GE) distribution which can capture the bursty property of network traffic. The analytical solution is obtained using the maximum entropy (ME) principle. The forms of the state and blocking probabilities are analytically established at equilibrium via appropriate mean value constraints. The initial numerical results demonstrate the credibility of the proposed analytical solution.     

Stability of Parallel Queueing Systems with Coupled Service Rates

This paper considers a parallel system of queues fed by independent arrival streams, where the service rate of each queue depends on the number of customers in all of the queues. Necessary and sufficient conditions for the stability of the system are derived, based on stochastic monotonicity and marginal drift properties of multiclass birth and death processes. These conditions yield a sharp characterization of stability for systems where the service rate of each queue is decreasing in the number of customers in other queues, and has uniform limits as the queue lengths tend to infinity. The results are illustrated with applications where the stability region may be nonconvex.     

Seeing through black boxes: Tracking transactions through queues under monitoring resource constraints

The problem of optimal allocation of monitoring resources for tracking transactions progressing through a distributed system, modeled as a queueing network, is considered. Two forms of monitoring information are considered, viz., locally unique transaction identifiers, and arrival and departure timestamps of transactions at each processing queue. The timestamps are assumed to be available at all the queues but in the absence of identifiers, only enable imprecise tracking since parallel processing can result in out-of-order departures. On the other hand, identifiers enable precise tracking but are not available without proper instrumentation. Given an instrumentation budget, only a subset of queues can be selected for the production of identifiers, while the remaining queues have to resort to imprecise tracking using timestamps. The goal is then to optimally allocate the instrumentation budget to maximize the overall tracking accuracy. The challenge is that the optimal allocation strategy depends on accuracies of timestamp-based tracking at different queues, which has complex dependencies on the arrival and service processes, and the queueing discipline. We propose two simple heuristics for allocation by predicting the order of timestamp-based tracking accuracies of different queues. We derive sufficient conditions for these heuristics to achieve optimality through the notion of the stochastic comparison of queues. Simulations show that our heuristics are close to optimality, even when the parameters deviate from these conditions.     

Product-forms in batch networks: Approximation and asymptotics

It is shown that a Markovian queue, with bulk arrivals and departures having any probability mass functions for their batch sizes, has geometrically distributed queue length at equilibrium (when this exists) provided there is an additional special bulk arrival stream, with particular rate and batch size distribution, when the server is idle. It is shown that the time-averaged input rate of the special arrivals tends to zero as the queue becomes saturated, and a heavy-traffic limit for the queue without special arrivals is derived by martingale methods. This is shown to give the same asymptotic queue length probabilities as the geometric model. The product form is then extended to tandem networks of batch queues using the reversed compound agent theorem (RCAT). In order to obtain the product form in this case, it is required that, in addition to special arrival streams, so-called ‘partial batches’ are discarded immediately from the network when there are not enough customers in the queue to fill an entire departing batch. Somewhat surprisingly it turns out that, in heavy traffic, the product-form network does not always agree with the regulated Brownian motion (RBM) diffusion limit for the standard network without special arrivals and where partial batches are not discarded, but forwarded to the next node. Indeed, we show that the two models agree in heavy traffic if and only if the skew-symmetry condition for the RBM to have a product form is satisfied. When the condition does hold, our theoretical and numerical results thus validate the use of the product-form batch networks as moderate-traffic approximations to the analogous standard queueing network model without special arrivals and where partial batches may be forwarded to the next node instead of being lost. In the case that the condition does not hold, we obtain a new product-form stationary distribution for the associated non-RBM diffusion limit.     

Adaptive back-pressure congestion control based on localinformation

The problem of distributed congestion control as it arises in communication networks as well as in manufacturing systems is studied in this paper. In particular, a multistage queueing system that models virtual circuit and datagram communication networks and a class of manufacturing systems are considered. The topology may be arbitrary, there are multiple traffic classes, and the routing can be class dependent, with routes that may form direct or indirect loops. The model incorporates the functions of transmission scheduling, flow control, and routing, through which congestion control is performed in the network. A policy is given that performs these functions jointly. According to the policy, heavily loaded queues are given higher priority in service. A congested node may reduce the how from upstream nodes through a flow control mechanism. Whenever routing is required, it is performed in such a manner that the lightly loaded queues receive most of the traffic. For arrival processes with bounded burstiness, the policy guarantees bounded backlogs in the network, as long as the load of each server is less than one. The actions of each server are based on the state of its own queues and of the queues one hop away. Therefore, they are implementable in a distributed fashion. An adaptive version of the policy is also provided which makes it independent of the arrival rates     

Robust design of server capability in M/M/1 queues with both partly random arrival and service rates

In this paper we consider a robust design of controllable factors related to the server capability in M/M/1 queues where both arrival and service rates are assumed to be partly random. The performance of an individual queue is measured in terms of the random traffic intensity parameter defined as the ratio of the arrival rate to the service rate where both rates are functions of associated characteristics of an individual queue and a random error. We utilize the empirical Bayes estimator of the traffic intensity parameter and employ a Monte-Carlo simulation to find the optimal levels of server characteristics with respect to mean squared error. An example is given to illustrate how the proposed procedures can be applied to the robust design of a transmission line.Scope and purposeRobust design is an important issue and has been extensively applied to both product and manufacturing process design so that the resulting quality can consistently satisfy customers under the variation of some uncontrollable factors. We apply this concept to design server capability in a queueing system for given arrival rates. In order to reflect random phenomena, we use Bayesian approach to estimate parameters in the given queueing model. We expect that the resulting robust design procedure can be effectively utilized for budgeting server levels of various queueing systems.     

控制排队长度的高密度路网信号优化模型

为了提高高密度路网地区的交通管理水平,针对高密度路网特点,提出了一种分布式信号控制模型,用于控制交叉口的排队管理.该模型建立了多目标函数,包括了平均出行延误最小和平均排队占比最小;模型约束包括了排队长度估计、信号控制参数约束.此外,为了避免排队回流现象的产生,还建立了具有高优先级的排队回流约束.仿真结果表明,该模型提高了高密度路网地区的交通通行效率,并有效避免交叉口排队回流现象.     

Fluid analysis of arrival routing

In Hajek's arrival routing problem (1984), customers are routed to one of n queues to minimize average holding cost. Interarrival and service times are exponentially distributed. We solve the associated fluid model. The optimal fluid policy tells us the asymptotic slopes of the switching surfaces in the original problem when the queues are large. If these slopes are nonzero, then numerical tests indicate that the fluid policy performs well in the original stochastic network. The fluid policy also indicates the approximate path that will be taken to recover from large queues: Routing only switches to queues with larger holding cost and once a large queue empties it will remain approximately empty     

A Markovian queue with varying number of servers and applications to the performance comparison of HSDPA user equipment

Inspired by the need for performability models for HSDPA user equipment, a Markovian queue with varying number of servers is conceived. The arrival and the service processes, the number of allocated or active servers of the queue are inherently, and independently (or jointly) Markov modulated. Batch arrivals, batch services, autocorrelation of inter-arrival times, and autocorrelation of batch sizes can be accommodated in the queue, by a suitable use of Markov modulation and generalized exponential distribution. The queue has a provision for negative customers too. Transformations of the balance equations into a computable form are proposed in order to obtain the steady state probabilities with the Spectral Expansion method. This queue is used to model the High Speed Downlink Packet Access (HSDPA) wireless networks. The model is an integrated one with respect to HSDPA, capable of accommodating many of the intricate aspects of HSDPA such as, channel allocation policy, loss of packets due to channel fading, bursty and correlated traffic. Good agreement is observed between the numerical results of the proposed analytical model and those of an independent simulator of real HSDPA and radio channel behaviors. The comparison of the terminal categories specified by the 3rd Generation Partnership Project (3GPP) is also presented.     

A Symmetrical Exponential Open Queue Network with Blocking and Feedback

The exponential open queue network model studied here consists of n symmetrical queues in parallel served by independent first-level servers in tandem with a second-level server. Blocking of the flow of units through a first-level server occurs each time the server completes a service. The server remains blocked until its blocking unit completes its service at the second-level server. An approximate expression of the probability distribution of the number of blocked first-level servers conditioned upon a service completion of a first-level server is obtained. This expression compares well with simulation data. Based on this distribution, an approximate expression of the queue-length probability distribution is derived assuming a processor-sharing type of service. The exact condition for stability of the queue network is also derived. Some potential applications are discussed, and a quantitative evaluation of the model is given through a case study.