Performance evaluation of long range dependent queues

Abstract

With the increasing demand of Internet services, significant efforts have been made to evaluate grade of service for network design and dimensioning. Since the Long Range Dependent (LRD) characteristics of Internet traffic has been discovered, queueing performance analysis and capacity assignment for queues fed by LRD inputs, so-called LRD queues, has attracted significant attention. Compared to the traditional Poisson models inherited from the telephony world, the performance analysis of LRD queues is much more involved and faces many challenges. Despite the considerable efforts made in the past twenty years, exact results are only available for the case with the Hurst parameter equal to 0.5. In addition, simulating systems with LRD traffic inputs usually requires unrealistically long simulation times. Therefore, it is important to obtain simple and accurate analytical results, as well as time-efficient simulation methods, for LRD queues. In this thesis, we evaluate the performance of the queues fed by LRD processes. In particular, we focus on two LRD input processes: the Poisson Lomax Burst Process (PLBP) and the fractional Brownian motion (fBm). PLBP is a variant of the popular M/G/∞ traffic process, the Poisson Pareto Burst Process (PPBP), which consists of bursts with Pareto distributed length that arrive according to a Poisson process. Since PPBP exhibits the LRD phenomenon and also captures the behaviour of Internet traffic, there have been significant research efforts to analyze the performance of queues fed by PPBP input. Here, we replace the Pareto burst distribution of PPBP with a Lomax distribution so that small traffic flows can be taken into account. The resulting input process is named PLBP. We illustrate its advantage in modelling Internet traffic flow sizes, particularly, in its ability to capture a large number of small flows. We provide two approximations to the overflow probability of a single queue fed by PLBP based on analytical and fast simulation methods, and illustrate their accuracy by discrete-event simulations. Fractional Brownian motion (fBm) is another important model because it captures the LRD characteristics of Internet traffic, accurately represents traffic generated as an aggregate of many sources, a prevalent characteristic of many Internet traffic streams, and is amenable to analysis. We introduce a new, simple, closed-form approximation for the stationary workload distribution (virtual waiting time) of a single server queue fed by an fBm input, the so-called fBm queue. Next, an efficient approach for producing a sequence of simulations with finer and finer details of the fBm process is introduced and applied to demonstrate good agreement between the new formula and the simulation results. This method is necessary in order to ensure that the discrete-time simulation accurately models the continuous-time fBm queueing process. Based on the closed-form formula, we provide the approximations for the mean, variance, third central moment and skewness of the occupancy of an fBm queue. Then we study the limitations of the fBm process as a traffic model with the help of a benchmark model - a truncated version of the fBm. We determine by numerical experiments the region where the fBm can serve as an accurate traffic model. These experiments show that when the level of multiplexing is sufficient, fBm is an accurate model for the traffic on links in the core of an internet. Using our result obtained for the workload distribution, we derive a closed-form expression for service rate provisioning when the desired blocking probability as a measure of quality of service is given. We then apply this result to a range of examples. Finally, we validate our fBm-based overflow probability and link dimensioning formulae through benchmark results based on a queue fed by real traffic traces as a benchmark, and demonstrate an advantage for the range of overflow probability over another traffic model, named Markov modulated Poisson process. Finally, we compare the fBm model with the PPBP and the PLBP models and show the convergence between fBm and the PPBP/PLBP models for high aggregation of traffic.

Date of Award	2 Oct 2015
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Moshe ZUKERMAN (Supervisor)