Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-14T19:19:15.090Z Has data issue: false hasContentIssue false
  • English
  • Français

A Stochastic Ordering Property for Leaky Bucket Regulated Flows in Packet Networks

Part of:Operations research and management scienceSpecial processes

Published online by Cambridge University Press:  14 July 2016

Fabrice M. Guillemin,
Ravi R. Mazumdar,
Catherine P. Rosenberg and
Yu Ying
Fabrice M. Guillemin*
Affiliation:
France Telecom
Ravi R. Mazumdar*
Affiliation:
University of Waterloo
Catherine P. Rosenberg*
Affiliation:
University of Waterloo
Yu Ying*
Affiliation:
Purdue University
*
∗ Postal address: France Telecom, 2 Avenue Pierre Marzin, 22300 Lannion, France. Email address: fabrice.guillemin@orange-ftgroup.com
∗∗ Postal address: Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON N2L 3G1, Canada.
∗∗ Postal address: Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON N2L 3G1, Canada.
∗∗∗∗∗ Postal address: School of ECE, Purdue University, West Lafayette, IN 47907, USA. Email address: yingy@purdue.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show in this paper that if a stationary traffic source is regulated by a leaky bucket with leak rate ρ and bucket size σ, then the amount of information generated in successive time intervals is dominated, in the increasing convex ordering sense, by that of a Poisson arrival process with rate ρ/σ, with each arrival bringing an amount of information equal to σ. By exploiting this property, we then show that the mean value in the stationary regime of the content of a buffer drained at constant rate and fed with the superposition of regulated flows is less than the mean value of the same buffer fed with an adequate Poisson process, whose characteristics depend upon the regulated input flows.

Keywords

Stochastic orderingfluid queueregulated flows

MSC classification

Primary:60K35: Interacting random processes; statistical mechanics type models; percolation theory
Secondary:90B15: Network models, stochastic90B18: Communication networks90B20: Traffic problems

Information

Type
Research Article
Information
Journal of Applied Probability , Volume 44 , Issue 2 , June 2007, pp. 332 - 348
Copyright
Copyright © Applied Probability Trust 2007 

References

Baccelli, F. and Brémaud, P. (1994). Elements of Queueing Theory (Appl. Math. 26). Springer, New York.Google Scholar
Billingsley, P. (1968). Convergence of Probability Measures. John Wiley, New York.Google Scholar
Chang, C.-S. (2000). Performance Guarantees in Communication Networks. Springer, London.CrossRefGoogle Scholar
Chang, C.-S., Song, W. and Chiu, Y.-M. (2001). On the performance of multiplexing independent regulated inputs. In Proc. 2001 ACM Sigmetrics, ACM Press, New York, pp. 184–193.Google Scholar
Cruz, R. L. (1991). A calculus for network delay. I. Network elements in isolation. IEEE Trans. Inf. Theory 37, 114–131.CrossRefGoogle Scholar
Cruz, R. L. (1991). A calculus for network delay. II. Network analysis. IEEE Trans. Inf. Theory 37, 132–141.Google Scholar
Fidler, M. (2004). Elements of probabilistic network calculus applying moment generating functions. Tech. Rep. 12, Institut Mittag Leffler.Google Scholar
Firoiu, V., Le Boudec, J.-Y., Towsley, D. and Zhang, Z. L. (2002). Theories and models for internet quality of service. Proc. IEEE, pp. 1565–1591.CrossRefGoogle Scholar
Guillemin, F., Likhanov, N., Mazumdar, R. and Rosenberg, C. (2003). Buffer overflow bounds for multiplexed regulated traffic streams. In Proc. 18th Intenat. Teletraffic Congress 2003, eds Charzinsky, J. et al. Elsevier, pp. 491–500.Google Scholar
Guillemin, F. M., Likhanov, N., Mazumdar, R. R. and Rosenberg, C. P. (2002). Extremal traffic and bounds for the mean delay of multiplexed regulated traffic streams. In Proc. IEEE INFOCOM 2002, IEEE, pp. 985–993.Google Scholar
Kesidis, G. and Konstantopoulos, T. (2000). Extremal traffic and worst-case performance for queues with shaped arrivals. In Analysis of Communication Networks: Call Centres, Traffic and Performance, American Mathematical Society, Providence, RI, pp. 159–178.Google Scholar
Le Boudec, J.-Y. and Thiran, P. (2001). Network Calculus. Springer, Berlin.CrossRefGoogle Scholar
Massoulié, L. (1998). Large deviation ordering of point processes in some queueing networks. Queueing Systems 4, 317–335.Google Scholar
Massoulié, L. and Busson, A. (2000). Stochastic majorization of aggregates of leaky bucket-constrained traffic streams. Preprint, Microsoft Research, Cambridge.Google Scholar
Turner, J. (1986). New directions in communications (or which way in the information age?). IEEE Commun. Mag. 24, 8–15.CrossRefGoogle Scholar
Ying, Y., Guillemin, F., Mazumdar, R. and Rosenberg, C. (2005). Buffer overflow asymptotics for multiplexed regulated traffic. To appear in Performance Evaluation.Google Scholar