Abstract
Recent experimental studies have revealed that network traffic exhibits burstiness, that is fluctuations, over multiple scales of time. In many circumstances, heavy-tailed probability distributions have been found appropriate for capturing this salient feature. Heavy-tailed distributions have the property of decaying more slowly than any distribution belonging to the exponential family.
Traditional network engineering is essentially based on the exponential distribution and its variants. Recent work indicate that models based on this approach may be less useful than expected in predicting the behavior of modern networks. Our goal in this research is to present new perspectives on teletraffic engineering and on the concept of Quality of Service in high speed networks. Towards this aim, we develop novel and easily tractable methodologies for the teletraffic engineering of high speed networks with multiple time-scale traffic. Our analytical procedures are useful for the design and performance evaluation of both single queues and queueing networks.
First, we focus on the single-node engineering. We propose a new methodology for the modeling and analysis of heavy-tailed distributions, such as the Pareto distribution, in a queueing system. Our main thesis is that classical teletraffic methods can be employed for analyzing such distributions. Our approach is based on a fitting algorithm which approximates a heavy-tailed distribution by a hyperexponential distribution. This algorithm possesses several key properties. First, the approximation can be achieved within any desired degree of accuracy. Second, the fitted hyperexponential distribution depends only on a few parameters. Third, only a small number of exponentials are required in order to obtain an accurate approximation over many time scales. Once equipped with a fitted hyperexponential distribution, we have an integrated framework for analyzing queueing systems with heavy-tailed distributions. We consider the GI/G/1 queue with Pareto distributed service time and show how our approach allows to derive both quantitative numerical results and asymptotic closed-form results. This derivation provides new insight into the impact of system characteristics on performance measures, such as the relation between the inter-arrival time distribution and the waiting time distribution. Moreover, it enables to state the domain of validity of asymptotic results.
Next, we introduce a comprehensive framework for evaluating the impact of multiple time-scale traffic on important QoS performance measures in a communication network. Our approach is based on a new network calculus, termed Stochastically Bounded Burstiness (SBB) calculus, which provides statistical upper bounds on various performance metrics such as delay, at each node of a feedforward network. This calculus is based on an appropriate characterization of the processes feeding the network. This characterization is achieved by stochastically bounding the ``burstiness'', which in our context means an ensemble of linear envelop processes, by general decreasing functions. The SBB methodology is useful for a large class of exogenous arrival processes, including important processes exhibiting ``subexponentially bounded burstiness'' such as fractional Brownian motion. Moreover, it allows to judiciously capture the salient features of real-time traffic, such as the ``cell'' and ``burst'' characteristics of multiplexed voice traffic. This accurate characterization is achieved by setting the bounding function as a sum of exponentials. We compare our methodology with previous approaches and show that it can substantially improve the utilization of networks implementing services based on statistical guarantees.
We expect that the results of this research will be especially useful to major areas of high speed networking such as buffer design, traffic management, resource reservation and call admission procedures.