Buffer Engineering for M|G|infinity Input Processes

Abstract

We suggest the $M|G|infty$ input process as a viable model forrepresenting the heavy correlations observed in network traffic.Originally introduced by Cox, this model represents the busy-serverprocess of an $M|G|infty$ queue with Poisson inputs and generalservice times distributed according to $G$, and provides a large andversatile class of traffic models. We examine various properties ofthe $M|G|infty$ process, focusing particularly on its richcorrelation structure. The process is shown to effectively portrayshort or long-range dependence simply by controlling the tail of thedistribution $G$.In an effort to understand the dynamics of a system supporting$M|G|infty$ traffic, we study the large buffer asymptotics of amultiplexer driven by an $M|G|infty$ input process. Using the largedeviations framework developed by Duffield and O'Connell, weinvestigate the tail probabilities for the steady-state buffercontent. The key step in this approach is the identification of theappropriate large deviations scaling. This scaling is shown to beclosely related to the forward recurrence time of the service timedistribution, and a closed form expression is derived for thecorresponding limiting log-moment generating functionassociated with the input process. Three different regimes areidentified.The results are then applied to obtain the large bufferasymptotics under a variety of service time distributions. In eachcase, the derived asymptotics are compared with simulation results. While the general functional form of buffer asymptotics may be derivedvia large deviations techniques, direct arguments often provide a moreprecise description when the input traffic is heavily correlated.Even so, several significant inferences may be drawn from thefunctional dependencies of the tail buffer probabilities. Theasymptotics already indicate a sub-exponential behavior in the caseof heavily-correlated traffic, in sharp contrast to the geometricdecay usually observed for Markovian input streams. This difference,along with a shift in the explicit dependence of the asymptotics onthe input and output rates $r_{in}$ and $c$, from $ ho=r_{in}/c$ when$G$ is exponential, to $Delta = c - r_{in}$ when $G$ issub--exponential, clearly delineates the heavy and light tailed cases.Finally, comparison with similar asymptotics for a different class ofinput processes indicates that buffer sizing cannot be adequatelydetermined by appealing solely to the short versus long-rangedependence characterization of the input model used.