 Award ID(s):
 1850439
 NSFPAR ID:
 10405999
 Date Published:
 Journal Name:
 Mathematics of Operations Research
 Volume:
 47
 Issue:
 4
 ISSN:
 0364765X
 Page Range / eLocation ID:
 2691 to 2720
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

null (Ed.)This work concerns the asymptotic behavior of solutions to a (strictly) subcritical fluid model for a data communication network, where file sizes are generally distributed and the network operates under a fair bandwidthsharing policy. Here we consider fair bandwidthsharing policies that are a slight generalization of the [Formula: see text]fair policies introduced by Mo and Walrand [Mo J, Walrand J (2000) Fair endtoend windowbased congestion control. IEEE/ACM Trans. Networks 8(5):556–567.]. Since the year 2000, it has been a standing problem to prove stability of the data communications network model of Massoulié and Roberts [Massoulié L, Roberts J (2000) Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems 15(1):185–201.], with general file sizes and operating under fair bandwidth sharing policies, when the offered load is less than capacity (subcritical conditions). A crucial step in an approach to this problem is to prove stability of subcritical fluid model solutions. In 2012, Paganini et al. [Paganini F, Tang A, Ferragut A, Andrew LLH (2012) Network stability under alpha fair bandwidth allocation with general file size distribution. IEEE Trans. Automatic Control 57(3):579–591.] introduced a Lyapunov function for this purpose and gave an argument, assuming that fluid model solutions are sufficiently smooth in time and space that they are strong solutions of a partial differential equation and assuming that no fluid level on any route touches zero before all route levels reach zero. The aim of the current paper is to prove stability of the subcritical fluid model without these strong assumptions. Starting with a slight generalization of the Lyapunov function proposed by Paganini et al., assuming that each component of the initial state of a measurevalued fluid model solution, as well as the file size distributions, have no atoms and have finite first moments, we prove absolute continuity in time of the composition of the Lyapunov function with any subcritical fluid model solution and describe the associated density. We use this to prove that the Lyapunov function composed with such a subcritical fluid model solution converges to zero as time goes to infinity. This implies that each component of the measurevalued fluid model solution converges vaguely on [Formula: see text] to the zero measure as time goes to infinity. Under the further assumption that the file size distributions have finite pth moments for some p > 1 and that each component of the initial state of the fluid model solution has finite pth moment, it is proved that the fluid model solution reaches the measure with all components equal to the zero measure in finite time and that the time to reach this zero state has a uniform bound for all fluid model solutions having a uniform bound on the initial total mass and the pth moment of each component of the initial state. In contrast to the analysis of Paganini et al., we do not need their strong smoothness assumptions on fluid model solutions and we rigorously treat the realistic, but singular situation, where the fluid level on some routes becomes zero, whereas other route levels remain positive.more » « less

The bursty nature of network traffic makes it difficult to characterize accurately, and may give rise to heavytailed queue distributions within the network. Building on prior work in stochastic network calculus, we propose traffic burstiness bounds based on the class of phasetype distributions and develop an approach to estimate the parameter of such bounds using the expectationmaximization (EM) algorithm. By limiting the tail of the burstiness bound, our approach achieves a better fit of the phasetype distribution to the empirical data from heavytailed traffic. The proposed taillimited phasetype burstiness bounds fall within the framework for stochastic network calculus based on generalized stochastically bounded burstiness. We demonstrate the effectiveness of the proposed methodology with a numerical example involving a heavytailed M/G/1 queue.more » « less

Network traffic is difficult to characterize due to its random, bursty nature. Even if a traffic source could be fit to a stochastic model with reasonable accuracy, analysis of endtoend network performance metrics for such traffic models is generally intractable. In prior work, an approach to characterize traffic burstiness using a bound based on the class of phasetype distributions was proposed. Such phasetype bounds could be applied in conjunction with stochastic network calculus to derive probabilistic endtoend delay bounds for a traffic stream. In this paper, we focus on the problem of estimating a tight phasetype burstiness bound for a given traffic trace. We investigate a method based on least squares and another based on the expectationmaximization algorithm. Our numerical results compare the two approaches in the scenario of a heavytailed M/G/1 queue. We find that while both methods are viable approaches for deriving phasetype bounds on traffic burstiness, the least squares approach performs better, particularly when a tail limit is imposed.more » « less

Evaluation of endtoend network performance using realistic traffic models is a challenging problem in networking. The classical theory of queueing networks is feasible only under rather restrictive assumptions on the input traffic models and network elements. An alternative approach, first proposed in the late 1980s, is to impose deterministic bounds on the input traffic that can be used as a basis for a network calculus to compute endtoend network delay bounds. Such deterministic bounds are inherently loose as they must accommodate worst case scenarios. Since the early 1990s, efforts have shifted to development of a stochastic network calculus to provide probabilistic endtoend performance bounds. In this paper, we capitalize on the approach of stochastically bounded burstiness (SBB) which was developed for a general class of bounding functions, and was demonstrated for a bound that is based on a mixture distribution. We specialize the SBB bounds to bounds based on the class of phasetype distributions, which includes mixture distributions as a particular case. We develop the phasetype bounds and demonstrate their performance.more » « less

Abstract We develop a robust queueing network analyzer algorithm to approximate the steady‐state performance of a single‐class open queueing network of single‐server queues with Markovian routing. The algorithm allows nonrenewal external arrival processes, general service‐time distributions and customer feedback. The algorithm is based on a decomposition approximation, where each flow is partially characterized by its rate and a continuous function that measures the stochastic variability over time. This function is a scaled version of the variance‐time curve, called the index of dispersion for counts (IDC). The required IDC functions for the external arrival processes can be calculated from the model primitives or estimated from data. Approximations for the IDC functions of the internal flows are calculated by solving a set of linear equations. The theoretical basis is provided by heavy‐traffic limits for the flows established in our previous papers. A robust queueing technique is used to generate approximations of the mean steady‐state performance at each queue from the IDC of the total arrival flow and the service specification at that queue. The algorithm's effectiveness is supported by extensive simulation studies.