Queueing Systems with Stochastic Time out

In this paper, formulas are derived for queueing systems where the delayed customers are controlled by a stochastic time out, i.e., the delays are limited by a timeTthat is drawn from a general probability distribution. Formulas are also worked out for the case of a limitation of the time spent in the total system (queue + servers). In order to simplify numerical calculations, an approximate method is worked out and numerical examples are shown.     

Queueing behavior of statistical multiplexers with correlatedinputs

The author considers an asynchronous time-division-multiplexing system with a finite number of identical users generating data only during their so-called active periods, which alternate with so-called passive periods. Assuming geometric distributions for the active and passive periods of the users, the author derives a functional equation which describes the full steady-state buffer behavior of the multiplexer. The buffer occupancy at various moments can be derived from this equation and explicit functions of the parameters of the system. The results indicate a strong dependency of the mean buffer occupancy on the actual lengths of the active and passive periods of the users, even for a given mean user activity     

Queueing analysis of a single-wavelength Fiber-Delay-Line buffer

We present in rather mathematical detail the queueing analysis of a single-wavelength Fiber-Delay-Line buffer. Such optical buffer system cannot realize all possible delay values, but only a limited set, typically multiple integers of some basic unit called the granularity. This leads to an under-utilization of the available channel capacity, and a bad design choice for the granularity can seriously impair performance. The analysis makes extensive use of generating functions and focusses on the scheduling horizon as seen by arriving bursts and the waiting time these incur in an infinite system. From the expressions obtained, several measures of interest are derived, notably heuristics for the burst loss probability and the mean waiting time in finite systems, which can be used to evaluate performance for any given value of the input load. The model we propose allows for rather general burst-size distributions, but for special instances thereof, the formulae can be made more explicit. A number of numerical examples highlight some of the peculiar aspects of Fiber-Delay-Line buffers.     

Queueing models for systems with synchronization constraints

The authors consider queueing that occur naturally in the study of a class of resource-sharing problems under synchronization constraints such as resequencing and fork-join primitives. These queueing models are amenable to a representation in terms of a state recursion. The proposed methods of analysis are complementary and draw on classical ideas of queuing theory as well as on mathematical tools from the theory of stochastic ordering and ergodic theory. The state recursion is at the center of all aspects of the analysis, be it for developing the exact solutions, obtaining bounds on system performance or establishing the stability conditions. The ideas are illustrated on simple models of resequencing and fork-join synchronization, which emphasis put on deriving computable bounds on the performance measures     

Integrated Digital Switching System with Queueing Storage Facility

This paper outlines the features of a new integrated switching system for voice and data. It is composed of integrated subscriber terminals, integrated subscriber lines, an integrated digital switching system, and integrated storage facilities. This paper shows that the introduction of the integrated storage facility can create various new service utilities and improve the traffic capacity of the system.     

Input Versus Output Queueing on a Space-Division Packet Switch

Two simple models of queueing on anN times Nspace-division packet switch are examined. The switch operates synchronously with fixed-length packets; during each time slot, packets may arrive on any inputs addressed to any outputs. Because packet arrivals to the switch are unscheduled, more than one packet may arrive for the same output during the same time slot, making queueing unavoidable. Mean queue lengths are always greater for queueing on inputs than for queueing on outputs, and the output queues saturate only as the utilization approaches unity. Input queues, on the other hand, saturate at a utilization that depends onN, but is approximately(2 -sqrt{2}) = 0.586whenNis large. If output trunk utilization is the primary consideration, it is possible to slightly increase utilization of the output trunks-upto(1 - e^{-1}) = 0.632asN rightarrow infty-by dropping interfering packets at the end of each time slot, rather than storing them in the input queues. This improvement is possible, however, only when the utilization of the input trunks exceeds a second critical threshold-approximatelyln (1 +sqrt{2}) = 0.881for largeN.     

Queueing analysis of a threshold based priority scheme for ATMnetworks

A threshold-based priority scheme in which a tuning parameter is used to provide adequate quality of service to real-time traffic while providing the best possible service to the non-real-time traffic is proposed. The priority scheme is a generalization of the static priority scheme and the one-limited scheme and is more flexible than both. For this scheme, the authors carry out a queueing analysis and obtain the joint distribution of the queue-lengths. They show by numerical examples how the parameter of this scheme can be tuned dynamically, so that the tuning function can be integrated with the call admission policy     

ARQ with Sequential Decoding of Packetized Data: Queueing Analysis

The operation of a sequential decoder in a packet-switching environment is considered. Packets arrive randomly at the decoder, and a packet is stored in a buffer if the decoder is busy upon its arrival. The decoder devotes no more than a time-out period of predetermined length to the decoding of any single packet. If packet decoding is completed within that period, the packet leaves the system. Otherwise, it is retransmitted and its decoding starts anew. While a packet is retransmitted, the decoder decodes another packet that resides in its buffer. An upper bound on the maximum rate of packets that can be supported by the channel-decoder combination is derived, and the optimum time-out that maximizes that rate is determined. A discrete-time model of the decoder's queue is presented, and the average queue length and throughput are evaluated.     

On Calculations Transient Statistics of a Discrete Queueing System with Independent General Arrivals and Geometric Departures

An approximation algorithm is developed for calculating transient mean and variance of the queue size of a discrete queueing system with independent general arrivals and geometric output processes. The algorithm makes no assumption on the form of the distribution function of the arrival process and only the first three moments of the arrival process are required. Three numerical examples are presented.     

Queueing model of a bi-level Markov service-system and its solutionusing recursion

The authors present a closed queueing model of a bi-level stochastic service system using a Markov process. The existence of two modes of operation in some real situations such as reliability, inventory, and production problems is outlined. A recursive solution technique is developed for computing steady-state probabilities and the relevant performance measures for such a system. A bi-level system is completely analyzed. The effect of the two modes of operation on the system performance measures is also discussed. The recursive solution technique is consistently superior to other common solution techniques with respect to computation time and memory requirement. A procedure is outlined for extension to a multi-level service system     

Queueing analysis of delay constrained voice traffic in a packetswitching system

Unlike data traffic, the voice packet stream from a node has very high correlation between consecutive packets. In addition, in order for the speech to be properly reconstructed, a delay constraint must be satisfied. A queueing model that accurately predicts packet loss probabilities for such a system is presented. Analytical results are obtained from an embedded bivariate Markov chain and are validated by a simulation program. Based on this model, the impact of the delay constraint, talkspurt detection thresholds, and packet size on packet loss are studied. Two schemes, named `instant' and `random', for discarding late packets are considered. Simulation results show that better performance can be obtained by using the latter scheme     

Performance Analysis of Reassembly and Multiplexing Queueing with Long-Range-Dependent Input Traffic

This paper studies the impact of long-range-dependent (LRD) traffic on the performance of reassembly and multiplexing queueing. A queueing model characterizing the general reassembly and multiplexing operations performed in packet networks is developed and analyzed. The buffer overflow probabilities for both reassembly and multiplexing queues are derived by extending renewal analysis and Bene fluid queue analysis, respectively. Tight upper and lower bounds of the frame loss probabilities are also analyzed and obtained. Our analysis is not based on existing asymptotic methods, and it provides new insights regarding the practical impact of LRD traffic. For the reassembly queue, the results show that LRD traffic and conventional Markov traffic yield similar queueing behavior. For the multiplexing queue, the results show that the LRD traffic has a significant impact on the buffer requirement when the target loss probability is small, including for practical ranges of buffer size or maximum delay.     

Analysis on Partial Overflow Queueing Systems with Two Kinds of Calls

In this paper, the traffic model of one kind of the partial overflow system is presented and theoretically analyzed, which has remained unsolved up to today. In the partial overflow systems, the considered overflow traffic stream is a part of the traffic stream overflowing from a common trunks group with multiinput calls. The systems with two kinds of calls are treated. Both of the two input traffic streams are assumed to follow the Poisson process and the holding times of the calls are assumed to be identical and follow an exponential distribution. Under these assumptions, analytical formulas are derived to calculate the individual traffic characteristics for both the loss-loss partial overflow system and the wait-loss partial overflow system. With these results, the accuracy of the well-used equivalent random theory in approximating the traffic model offered with partial overflow stream is investigated. The two-input model is a general one and can be used for analyzing the model with more than two inputs. It is expected that the formulas derived in this paper can be Used to improve the accuracy of ERT method as well as used directly.     

A Recursive Approximation Technique for a Combined Source Queueing Model

The model studied in this paper captures the combined effects of finite and infinite source traffic-often used to model interactive and batch traffic, respectively-when they contend for a single server resource. The finite source traffic is modeled by heterogeneous finite sources, the infinite source traffic by a stationary Poisson process, and the single server is assumed to have exponentially distributed service times with distinct service rates for the different customer types. All customers share a common queue and are serviced in FIFO order. A special case of this model where theNfinite sources are identical combines two fundamental and widely used models (the repairman andM/M/1models) in a natural manner. Regardless of the homogeneous or heterogeneous nature of the finite sources, the combined source model is not product form due to the realistic assumption that service rates are distinct for different customer types (batch and interactive traffic typically have different CPU processing requirements). In this paper, we show how to recursively calculate all mean quantities of interest in an approximate but quite accurate manner for the general heterogeneous model. The accuracy of the recursive technique is established in part by contrasting the approximate solution to simulation results for a wide parameter range, and in part by studying the asymptotic behavior of the approximation.     

Queueing processes in GPS and PGPS with LRD traffic inputs

Long range dependent (LRD) traffic whose single server queue process is Weibull Bounded (WB) is first analyzed. Two upper bounds on the individual session's queue length of LRD traffic under the generalized processor sharing (GPS) scheduling discipline are then contributed. It is shown that the index parameter in the upper bound of one LRD flow, (in addition to the decay rate and the asymptotic constant), may be affected by other LRD flows. A new concept, called LRD isolation, is subsequently contributed and accompanying it, a new technique is contributed to check whether a flow, with a given GPS weight assignment, can be guaranteed to be LRD isolated. This technique is also amenable for use in an online call admission control (CAC) scenario. When existing flows have already been assigned contract weights that cannot be changed, our technique can be used to determine minimum contract weights to be assigned to a new flow in order to guarantee the flow to be LRD isolated. The results are also extended to a PGPS (packet-based GPS) scheduler and relevant numerical results are provided to show the usefulness of our bounds and LRD isolation technique.     

Queueing analysis of buffered switching networks

A method for analyzing the queueing behavior of switching networks constructed from switches that employ shared buffering or parallel bypass input buffering is presented. The queueing models introduced by Y.C. Jenq (1983) and generalized by T. Szymanski and S. Shaikh (1989) are extended to handle these classes of networks. The analysis explicitly models the state of an entire switch and infers information about the distribution of packets associated with particular inputs or outputs when needed. It is shown that the method can be extended to switching systems with input buffering, including systems supporting bypass queueing. Numerical comparisons of the different buffering techniques are included     

Predicting Properties of Congestion Events for a Queueing System With fBm Traffic

In packet networks, congestion events tend to persist, producing large delays and long bursts of consecutive packet loss resulting in perceived performance degradations. The length and rate of these events have a significant effect on network quality of service (QoS). The packet delay resulting from these congestion events also influences QoS. In this paper a technique for predicting these properties of congestion events in the presence of fractional Brownian motion (fBm) traffic is developed.     

一种分级WFQ的宽带无线接入系统QoS架构

文章介绍了加权公平排队(WFQ)分组调度算法和IEEE 802 16的QoS架构.在此基础上,文章结合分级WFQ分组调度算法和IEEE 802 16协议中所提供的控制机制提出了一种适合于BWA系统的QoS架构.该架构充分利用IEEE 802.16提供的控制机制,结合分级WFQ公平队列调度算法,在主动授予业务(UGS)、实时轮询业务(rtS)、非实时轮询业务(nrtPS)和尽力传输业务(BE)之间公平分配带宽,并保证各种业务的QoS特性,完成了在IEEE 802 16协议中留给用户自己定义的调度策略.