Finite Buffer Behavior with Poisson Arrivals and Random Server Interruptions

A queueing model with finite buffer size, Poisson arrival process, synchronous transmission and server interruptions is studied through a Bernoulli sequence of independent random variables. An integrated digital voice-data system with Synchronous Time-Division Multiplexing (STDM) for voice sources and Poisson arrival process for data messages is considered as an application for this model. The relationships among overflow probabilities, buffer size and expected queueing delay due to buffering for various traffic intensities are obtained. The results of this study are portrayed on graphs and may be used as guide lines for the buffer design in digital voice-data systems. Although this study arose in the design of a buffer for digital voice-data systems, the queueing model developed is quite general and may be useful for other industrial applications.     

Buffer Behavior for Mixed Input Traffic and Single Constant Output Rate

A queueing model with limited waiting room (buffer), mixed input traffic (Poisson and compound Poisson arrivals), and constant service rate is studied. Using average burst length, traffic intensity, and input-traffic mixture rate as parameters, we obtain relationships among buffer size, overflow probabilities, and expected message-queueing delay due to buffering. These relationships are portrayed on graphs that can be used as a guide in buffer design. Although this study arose in the design of statistical multiplexors, the queueing model developed is quite general and may be useful for other industrial applications.     

Buffer losses vs. deadline violations for ABR traffic in an ATM switch: A computational approach

The B‐ISDN will carry a variety of traffic types: the Variable Bit Rate traffic (VBR), of which compressed video is an example, Continuous Bit Rate traffic (CBR), of which telemetry is an example, Data traffic, and Available Bit Rate traffic (ABR) that represents aggregate data traffic with very limited guarantees on quality. Of these, VBR and CBR have timing constraints and need synchronous bandwidth; data traffic is relatively delay insensitive. In this paper, we consider the VBR, Data and ABR traffic types and obtain the cumulative distribution function (cdf) of the queueing delay experienced by a burst of ABR traffic in the output buffer of an ATM switch. The cdf is used to trade off buffer loss probabilities against deadline violation probabilities through adjusting the buffer size and (delay) deadline values. Large buffers result in low losses but queueing delays can become excessive and cause a high level of deadline violations. Both losses and violations are detrimental and an operating point must be chosen to achieve a balance. In this paper we study the nature of the trade off. We develop a stochastic Petri net model assuming periodic burst arrivals for VBR and Poisson arrival processes for the Data and ABR traffic types at the burst level, and solve the model analytically (numerically) using a decomposition approach. This decomposition, along with the inherent decomposability of the tagged customer approach for obtaining the cdf opens up a possibility of carrying out fast computations using a parallel machine for selecting the operating point each time that a call is admitted. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Data Burst Assembly Algorithm in Optical Burst Switching Networks

Presently, optical burst switching (OBS) technology is under study as a promising solution for the backbone of the optical Internet in the near future because OBS eliminates the optical buffer problem at the switching node with the help of no optical/electro/optical conversion and guarantees class of service without any buffering. To implement the OBS network, there are a lot of challenging issues to be solved. The edge router, burst offset time management, and burst assembly mechanism are critical issues. In addition, the core router needs data burst and control header packet scheduling, a protection and restoration mechanism, and a contention resolution scheme. In this paper, we focus on the burst assembly mechanism. We present a novel data burst generation algorithm that uses hysteresis characteristics in the queueing model for the ingress edge node in optical burst switching networks. Simulation with Poisson and self‐similar traffic models shows that this algorithm adaptively changes the data burst size according to the offered load and offers high average data burst utilization with a lower timer operation. It also reduces the possibility of a continuous blocking problem in the bandwidth reservation request, limits the maximum queueing delay, and minimizes the required burst size by lifting up data burst utilization for bursty input IP traffic.     

Performance analysis of cellular mobile communication systems fordata transmission

Buffers are used to overcome the data losses due to the interruption of data transmission when a mobile station is handed over in a cellular network. Data traffic from a wireline network to its mobile data terminal, such as access to large commercial databases or data transmission from a main computer to its remote mobile terminal, is studied. Compound Poisson (CP) is used to approximate the arrival process of the data traffic, and a modulated D (MD) distribution is used to approximate the service and handover process. The performance of the queueing model CP/MD/1/N is analyzed. Probability generating functions and characteristic functions are used to evaluate the mean queue length and the mean burst delay for an infinite buffer system and the overflow probabilities versus the buffer size for a finite buffer system. A method is presented to find the probability transition matrix entries by recursively taking derivatives of the probability generating function of the number of the characters arriving during the service-time. The queue length distributions for a finite buffer, both at departure instants and at arbitrary time instants are derived. Comparison with simulation indicates that the model is accurate. The numerical results of the model confirm the effectiveness of the scheme     

Modeling multiple IP traffic streams with rate limits

We start with the premise, and provide evidence that it is valid, that a Markov-modulated Poisson process (MMPP) is a good model for Internet traffic at the packet/byte level. We present an algorithm to estimate the parameters and size of a discrete MMPP (D-MMPP) from a data trace. This algorithm requires only two passes through the data. In tandem-network queueing models, the input to a downstream queue is the output from an upstream queue, so the arrival rate is limited by the rate of the upstream queue. We show how to modify the MMPP describing the arrivals to the upstream queue to approximate this effect. To extend this idea to networks that are not tandem, we show how to approximate the superposition of MMPPs without encountering the state-space explosion that occurs in exact computations. Numerical examples that demonstrate the accuracy of these methods are given. We also present a method to convert our estimated D-MMPP to a continuous-time MMPP, which is used as the arrival process in a matrix-analytic queueing model.     

On the characteristics of queueing and scheduling at encoding nodes for network coding

Synchronization can greatly influence the performance of network coding. In this paper, we shall investigate the synchronization issue based on the use of queueing theory. We shall first propose a queueing model, referred to as the classic model, to investigate the characteristics of the encoding process. It will be proved that given the packet arrival processes are stationary, i.e. the distribution of the arrival processes does not depend on time, and obey independently and identically Poisson distribution and that the encoding time is exponentially distributed, the output flow will be an asymptotically Poisson flow with the same parameter. Through simulation we shall show that the network is sensitive to the arrival rate of input flows and becomes unstable with the input queue size increasing to infinity. This indicates that the classic coding scheme would impose strict requirements on synchronization over the whole network. In order to address this, we shall propose a combined opportunistic scheduling and encoding (COSE) strategy, in which the classic coding scheme and the traditional forwarding algorithm are well integrated. Theoretical analysis and simulation will demonstrate that the COSE strategy is able to control the input queue sizes and keep the network operating in a stable state while maintaining a relatively high throughput, low blocking probability and small waiting delay under various levels of traffic load. Copyright © 2009 John Wiley & Sons, Ltd.     

Edge node buffer usage in optical burst switching networks

Optical Burst Switching (OBS) combines the benefits of Optical Packet Switching and Optical Circuit Switching technologies to provide an efficient, yet cost effective, method for data transmission in an all-optical, bufferless, core network. While most studies on OBS has concentrated on the core OBS network, we contribute new studies for the buffer requirement of an OBS edge node. The buffer usage for OBS systems only arises in the edge nodes since they contain an array of assemblers which combines electronic data with a common destination into an OBS burst stream for transmission in an all-optical bufferless core network. Specifically, we present two analytical results for buffer usage in an OBS edge node: one for Poisson traffic and the other for self-similar traffic input. The results show that the aggregated traffic from many assemblers inherits the characteristics of the source input traffic. This means that the output traffic approaches Poisson if the input traffic is Poisson, and the output traffic remains self-similar if the input is self-similar. These results lead to the following important design issues when dimensioning buffer requirements in an OBS edge node: if the traffic input is Poisson, the M/G/m model is the model to use for obtaining the upper bound on buffer usage in an OBS edge node; and for the case of self-similar traffic, Brichet’s method can be used to provide the upper and lower bound.     

Buffer sizing in an ATM switch for both ATM and STM traffics

Specific queueing models are derived in order to size the buffers of ATM switching elements in the cases of ATM or STM multiplexed traffic. Buffering is performed either at the outputs or in a central memory for ATM multiplexed traffic; for STM multiplexed traffic, buffers can also be provided at the inputs. The buffer size is chosen in order to ensure a loss probability in the switch smaller than 10^?10. It is shown that the buffer size per output in the case of central queueing is smaller than the buffer size in case of output queueing for both ATM and STM multiplexed traffics. Moreover, for STM multiplexed traffic, buffer sizes are identical for input and output queueing. Lastly, it is pointed out that buffers used for STM multiplexed traffic should be 4 to 20 times larger than the corresponding buffers for ATM multiplexed traffic.     

Performance of Voice/Data Integration on a TDM System

Data queueing is of primary concern in a voice/data integrated TDM system. The data queueing model is represented in the discrete-time domain with multiple servers and voice is given a higher priority than data. The data arrival process is assumed to be Poisson and the voice arrival process is characterized by a Markov chain. The correlation coefficient of the number of on voice calls between consecutive frames is used to measure the correlation behavior of the voice process. While the generating function approach may be used to analyze the queueing process, it involves the evaluation of a large number of boundary terms. On the assumption that the voice traffic consists ofNi.i.d. two-state Markov chains, we derive a simple expression for the mean queue size as a function of two variables in the form of the traffic departure processes. The results clearly reveal a significant influence of the correlation coefficient on the data queueing process. Then, an approximate analysis based on the departure processes is introduced. The numerical and simulation results indicate that this approximate approach yields reasonably accurate results.     

Buffer sizing for synchronous self-routeing broadband packet switches with bursty traffic

Previous studies on the performance of synchronous self-routeing packet switches have assumed that the input traffic is random, i.e. there is no correlation between adjacent packet arrivals. This assumption is generally not valid in the data communication environment (e.g. host-to-host communication) where a file transfer usually generates a string of correlated packets. The consequence is that the random traffic assumption greatly underestimates the buffer requirement of the switch. In this paper, we model each input traffic stream as a binary source as a first step to understand the performance of a packet switch in a bursty traffic environment. We found that, given a fixed traffic load (or switch utilization), the required buffer size increases linearly as the burstiness index (the average burst length) of the traffic increases. In addition, the required buffer size is more sensitive to the burstiness of the traffic, when the average traffic load is higher and when the packet loss requirement is more stringent. Initial applications of broadband packet switches are likely to be the interconnections of LANs and hosts. The results of the study indicate that the high burstiness in certain broadband traffic significantly reduces the allowable switch utilization, given a fixed amount of buffers. To increase the switch utilization, an appropriate congestion control mechanism needs to be implemented.     

A discrete-time queueing network model of a hub-based OBS architecture

We propose and analyze a novel discrete-time queueing network model of a zero loss hub-based Optical Burst Switched (OBS) architecture, consisting of multiple input edge nodes and one destination edge node. The arrival process of bursts is slotted with bulk arrivals as generated by a Time and Burst-Length based burst aggregation algorithm. The queueing network is analyzed by decomposition. We obtain the average end-to-end delay of a burst in the queueing network as well as queueing delays at individual nodes. Our model provides a tight upper bound as shown by comparing the analytical data to simulation results.     

A histogram-based model for video traffic behavior in an ATMmultiplexer

The authors introduce a model based on arrival rate histograms for characterizing the behavior of an ATM buffer when it is carrying variable bit rate video traffic. Traffic smoothing on a frame-by-frame basis allows a quasistatic approximation that accurately predicts results such as buffer occupancy distributions and cell loss rates to be made. Convolving individual source histograms allow prediction of the queueing performance of a multiplexed stream. The approximation is investigated in more detail by modeling video as a Markov modulated Poisson process. It is shown that the multiplexer system is nearly completely decomposable (NCD). NCD systems have a well-known approximate solution, which is identical to the histogram approximation. Error bounds for the NCD approximation are also known and are reasonably tight. Results indicate that while the presence of strong correlations is an important characteristic of video traffic, the actual form of that correlation is not     

NN based ATM cell scheduling with queue length-based priorityscheme

The asynchronous transfer mode (ATM) is the choice of transport mode for broadband integrated service digital networks (B-ISDNs). We propose a window-based contention resolution algorithm to achieve higher throughput for nonblocking switches in ATM environments. In a nonblocking switch with input queues, significant loss of throughput can occur due to head-of-line (HOL) blocking when first-in first-out (FIFO) queueing is employed. To resolve this problem, we employ bypass queueing and present a cell scheduling algorithm which maximizes the switch throughput. We also employ a queue length based priority scheme to reduce the cell delay variations and cell loss probabilities. With the employed priority scheme, the variance of cell delay is also significantly reduced under nonuniform traffic, resulting in lower cell loss rates (CLRs) at a given buffer size. As the cell scheduling controller, we propose a neural network (NN) model which uses a high degree of parallelism. Due to higher switch throughput achieved with our cell scheduling, the cell loss probabilities and the buffer sizes necessary to guarantee a given CLR become smaller than those of other approaches based on sequential input window scheduling or output queueing     

A new approximation for analyzing the multiplexing of bursty sources in ATM networks

This paper is concerned with the analysis of an asynchronous transfer mode (ATM) multiplexer serving bursty applications such as voice, image, and high-speed data. The model used is a GI _i /D/1 discrete-time single-server queueing system: the arrival process is a superposition of several random processes, and the departure process is a deterministic with a FCFS discipline. The difficulty in solving such a queueing system depends on the model chosen for the individual traffic sources. For the case in which the cell arrival stream from the individual sources is modeled as a Bernouli process, an exact solution is possible. The problem with such a model is that it does not incorporate the effect of burst length, which has been shown through simulation experiments to have a significant effect on the performance. A more realistic model that takes into consideration the impact of the burst length is considered in this study. In particular, an alternating-state Markov process is chosen to model the individual arrival stream.The solution of a GI _i /D/1 queueing system with the arrival process being a superposition of several renewal processes is in general intractable. This paper obtained a new approximation we refer to as the three-parameters approximation (TPA). This approximation was based on the asymptotic properties of the aggregate traffic and the congestion estimates from the simulation experiments. The TPA solution was found to be dependent on three parameters: number of sources, overall traffic intensity at the queue, and multiplexing factor. The TPA is an improvement of a previous approximation developed in analyzing packet voice system.In addition, the study determined an optimal operating point for the ATM multiplexer and the ATM switch that takes into account the tradeoff between delay and throughput. In particular, an optimal operating point is specified by the traffic loading that maximizes the queueing power. This optimal operating point is used to contrast the performance of ATM with synchronous transfer mode (STM).     

A neural-based technique for estimating self-similar trafficaverage queueing delay

Estimating buffer latency is one of the most important challenges in the analysis and design of traffic control algorithms. In this paper a novel approach for estimating average queueing delay in multiple source queueing systems is introduced. The approach relies on the modeling power of neural networks in predicting self-similar traffic patterns in order to determine the arrival rate and the packet latency of low loss, moderately loaded queueing systems accommodating such traffic patterns     

Modeling and Simulation of Mixed Queueing and Loss Systems

In this paper, we investigate a multi-rate network in which wide-band calls are allowed to wait if insufficient resources are available at the time of the call arrival. On the link level, an analytical model is presented and simulations have been carried out on the network level. The results indicate that allowing a few wide-band calls to queue can give a significant improvement in performance in terms of network revenue , as well as a means to level out the blocking probabilities of the different traffic classes. This improvement becomes significant when the service discipline of the waiting calls (of different bandwidth requirements) is adaptive in the sense that longer queues get served first. This observation motivates the investigation of the impact of various buffer space assignment and queueing disciplines on network revenue and call blocking probabilities. The study of such mixed delay and queueing networks is motivated by its possible applications to traffic problems in future Broadband Integrated Services Digital Networks as well as in multi-rate cellular radio networks.     

Analysis of packet-switched data in a new basic rate user-networkinterface of ISDN

We present here an exact method for analyzing the queueing behavior of packet-switched data in a new basic rate user-network interface of ISDN. The new interface of ISDN in this paper adopts statistical multiplexing for providing integrated voice and data services. In order to properly represent the arrival of multirate data service, this interface assumes that the data packet input process is in batch Poisson. Furthermore, it is modeled by multiple synchronous servers with priority queues and finite waiting room with complete rejection strategy. The analytical method, with an application of the residue theorem in complex variable, can accurately obtain the data performance measures     

Individual Traffic Characteristics Queueing Systems with Multiple Poisson and Overflow Inputs

A theoretical method for analyzing overflow problems in queueing systems is presented. An interrupted Poisson process (IPP) approximation of overflow traffic is employed. An overflow stream is replaced by an IPP using the three-moment matching method. For a three-input model, to which one Poisson and two IPP streams are offered simultaneously, explicit and iterative formulas are derived to calculate the mean waiting time, overflow probability, and moments of overflow traffic intensity from the system for each of the three input streams. This three-input model is a general one, and can be used for analyzing complex problems such as multistage overflow models and individual traffic characteristics for a model with more than three inputs. By setting the capacity of the waiting room of the three-input model to 0, this method can cover loss systems. For both queueing and loss systems, several numerical examples of typical traffic models are shown. Comparisons are made between theoretical values and experimental values by computer simulations, and it is demonstrated that the accuracy of the method is excellent.     

Performance of cell loss priority management schemes in a single server queue

The throughput optimality of priority management strategies in a single buffer has been studied for a general aggregate arrival law. The tight upper bounds found are useful to understand optimality in the utilization of specific priority schemes such as push-out buffer (POB) and partial buffer sharing (PBS). This paper further focuses on the maximum allowable load ρ_max versus the priority mix α for a PBS and a random push-out buffer (RPOB) of size K for a wide variety of arrival processes. The role of priorities in a special type of bursty arrivals, the compound Poisson process with constant burst length and random priority assignment within the burst is found to be less pronounced than that of ‘pure’ Poisson arrivals. On the other hand, the results for ON–OFF cell arrivals modelled by a MMPP(2), MMPP(3), and higher order Markov modulated processes (MMP) closely follow the behaviour of the maximum allowable load in the RPOB with Poisson arrivals, however, scaled to lower loads. The results indicate that the priority mix distribution within the aggregate arrival flow influences the shape of ρ_max(α)-curve more than the aggregate arrival distribution itself. © 1997 John Wiley & Sons, Ltd.