article

Multiscale queueing analysis

Authors:

Vinay J. Ribeiro,

Rudolf H. Riedi,

Richard G. BaraniukAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 14, Issue 5

Pages 1005 - 1018

https://doi.org/10.1109/TNET.2006.882987

Published: 01 October 2006 Publication History

Abstract

This paper introduces a new multiscale framework for estimating the tail probability of a queue fed by an arbitrary traffic process. Using traffic statistics at a small number of time scales, our analysis extends the theoretical concept of the critical time scale and provides practical approximations for the tail queue probability. These approximations are non-asymptotic; that is, they apply to any finite queue threshold. While our approach applies to any traffic process, it is particularly apt for long-range-dependent (LRD) traffic. For LRD fractional Brownian motion, we prove that a sparse exponential spacing of time scales yields optimal performance. Simulations with LRD traffic models and real Internet traces demonstrate the accuracy of the approach. Finally, simulations reveal that the marginals of traffic at multiple time scales have a strong influence on queueing that is not captured well by its global second-order correlation in non-Gaussian scenarios.

References

[1]

{1} V. Ribeiro, R. Riedi, M. S. Crouse, and R. G. Baraniuk, "Multiscale queueing analysis of long-range-dependent network traffic," in Proc. IEEE INFOCOM, Mar. 2000, pp. 1026-1035.

[2]

{2} K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, F. Tobagi, and C. Diot, "Analysis of measured single-hop delay from an operational backbone network," in Proc. IEEE INFOCOM, Jun. 2002, pp. 535-544.

[3]

{3} L. Breslau, S. Jamin, and S. Shenker, "Comments on the performance of measurement-based admission control," in Proc. IEEE INFOCOM, Mar. 2000, pp. 1233-1242.

[4]

{4} C. Fraleigh, F. Tobagi, and C. Diot, "Provisioning IP backbone networks to support latency sensitive traffic," in Proc. IEEE INFOCOM, Apr. 2003, pp. 375-385.

[5]

{5} W. Leland, M. Taqqu, W. Willinger, and D. Wilson, "On the self-similar nature of ethernet traffic (extended version)," IEEE/ACM Trans. Networking, vol. 2, no. 1, pp. 1-15, Feb. 1994.

[6]

{6} I. Norros, "A storage model with self-similar input," Queueing Syst., vol. 16, pp. 387-396, 1994.

[7]

{7} N. Duffield and N. O'Connell, "Large deviations and overflow probabilities for the general single-server queue, with applications," Math. Proc. Cambr. Phil. Soc, vol. 118, pp. 363-374, 1995.

[8]

{8} J. Hüsler and V. Piterbarg, "Extremes of a certain class of Gaussian processes," Stochastic Process. Applicat., vol. 83, pp. 257-271, 1999.

[9]

{9} A. L. Neidhardt and J. L. Wang, "The concept of relevant time scales and its application to queueing analysis of self-similar traffic," in Proc. ACM SIGMETRICS, Mar. 1998, pp. 222-232.

[10]

{10} M. Grossglauser and J.-C. Bolot, "On the relevance of long-range dependence in network traffic," Comput. Commun. Rev., vol. 26, no. 4, pp. 15-24, Oct. 1996.

[11]

{11} J. Choe and N. B. Shroff, "Queueing analysis of high-speed multiplexers including long-range dependent arrival processes," in Proc. IEEE INFOCOM, Mar. 1999, pp. 617-624.

[12]

{12} A. Erramilli, O. Narayan, A. Neidhardt, and I. Sanjee, "Performance impacts of multi-scaling in wide area TCP/IP traffic," in Proc. IEEE INFOCOM, Mar. 2000, pp. 352-359.

[13]

{13} K. Debicki and T. Rolski, "A note on transient Gaussian fluid models," Queueing Syst., vol. 41, pp. 321-342, 2002.

[14]

{14} B. Hajek and L. He, "On variations of queue response for inputs with the same mean and autocorrelation function," IEEE/ACM Trans. Networking , vol. 6, no. 5, pp. 588-598, Oct. 1998.

[15]

{15} S. Ma and C. Ji, "Modeling video traffic in the wavelet domain," in Proc. IEEE INFOCOM, Mar. 1998, pp. 201-208.

[16]

{16} S. Ma, "Network Traffic Modeling and Analyisis," Ph.D. dissertation, Rensselaer Polytechnic Inst., Troy, NY, 1998.

[17]

{17} R. Riedi, M. S. Crouse, V. Ribeiro, and R. G. Baraniuk, "A multifractal wavelet model with application to network traffic," IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 992-1018, Apr. 1999.

[18]

{18} D. Fan, "The distribution of the product of independent beta variables," Commun. Statist.-Theory Meth., vol. 20, no. 12, pp. 4043-4052, 1991.

[19]

{19} O. Narayan, "Exact asymptotic queue length distribution for fractional brownian traffic," Adv. Perform. Anal., vol. 1, no. 1, pp. 39-63, 1998.

[20]

{20} L. Massoulié and A. Simonian, "Large buffer asymptitocs for the queue with fBm input," J. Appl. Probabil., vol. 36, no. 3, pp. 894-906, 1999.

[21]

{21} K. Park and W. Willinger, Eds., Self-Similar Network Traffic and Performance Evaluation. New York: Wiley Interscience, 2001.

[22]

{22} Auckland-II Trace Archive. NLANR, Trace 20000125-143640, corresponding to 3:11:28 hours of mostly TCP traffic. {Online}. Available: http://moat.nlanr.net/Traces/Kiwitraces/

[23]

{23} M. Crouse and R. G. Baraniuk, "Fast, exact synthesis of Gaussian and non-Gaussian long-range dependent processes," IEEE Trans. Inf. Theory, submitted for publication.

[24]

{24} A. Erramilli, O. Narayan, and W. Willinger, "Experimental queueing analysis with long-range dependent traffic," IEEE/ACM Trans. Networking , vol. 4, no. 2, pp. 209-223, Apr. 1996.

[25]

{25} D. P. Heyman and T. V. Lakshman, "What are the implications of long-range dependence for VBR-video traffic engineering?," IEEE/ACM Trans. Networking, vol. 4, no. 3, pp. 301-317, Jun. 1996.

[26]

{26} M. Parulekar and A. M. Makowski, "Tail probabilities for a multiplexer with self-similar traffic," in Proc. IEEE INFOCOM, Mar. 1996, pp. 1452-1459.

[27]

{27} B. K. Ryu and A. Elwalid, "The importance of long-range dependence of VBR video traffic in ATM traffic engineering: Myths and realities," in Proc. ACM SIGCOMM, 1996, pp. 3-14.

[28]

{28} O. Rose, Statistical properties of MPEG video traffic and their impact on traffic modeling in ATM systems, Univ. Wuerzburg, Inst. Computer Science Research Report Series, Tech. Rep. 101, 1995.

[29]

{29} Y. Joo, V. Ribeiro, A. Feldmann, A. C. Gilbert, and W. Willinger, "TCP/IP traffic dynamics and network performance: A lesson in workload modeling, flow control, and trace-driven simulations," Comput. Commun. Rev., vol. 31, no. 2, pp. 25-37, Apr. 2001.

[30]

{30} R. J. Adler, An Introduction to Continuity, Extrema, and Related Topics for General Gaussian Processes. Institute of Mathematical Statistics, 1990, IMS Lecture Notes--Monograph Series.

[31]

{31} P. Billingsley, Probability and Measure. New York: Wiley Interscience, 1995.

[32]

{32} V. I. Piterbarg, "Asymptotic methods in the theory of Gaussian processes and fields," in Translations of Mathematical Monographs. Providence, RI: American Mathematical Society, 1996, vol. 148.

Cited By

Chen YXiang ZDong YLu D(2011)Multi-Fractal Characteristics of Mobile Node's Traffic in Wireless Mesh Network with AODV and DSDV Routing ProtocolsWireless Personal Communications: An International Journal10.1007/s11277-009-9904-z58:4(741-757)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s11277-009-9904-z
Rizk AFidler M(2010)Sample path bounds for long memory FBM trafficProceedings of the 29th conference on Information communications10.5555/1833515.1833528(61-65)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833528
Feng BHuang CDevetsikiotis M(2009)FISTEACM Transactions on Modeling and Computer Simulation10.1145/1596519.159652119:4(1-39)Online publication date: 4-Nov-2009
https://dl.acm.org/doi/10.1145/1596519.1596521

Index Terms

Multiscale queueing analysis

Recommendations

Modeling network traffic by a cluster Poisson input process with heavy and light-tailed file sizes

We consider a cluster Poisson model with heavy-tailed interarrival times and cluster sizes as a generalization of an infinite source Poisson model where the file sizes have a regularly varying tail distribution function or a finite second moment. One ...
Queue-Length, Waiting-Time and Service Batch Size Analysis for the Discrete-Time GI/D-MSP $^{(a,b)} / 1 / \infty$ Queueing System
Abstract
This paper analyzes an infinite-buffer single-server bulk-service queueing system in which customers arrive according to a discrete-time renewal process. The customers are served under the discrete-time Markovian service process according to the ...
Analysis of a last come first served queueing system with customer abandonment

Motivated by manufacturing and service applications, we consider a single class multi-server queueing system working under the LCFS discipline of service. After entering the queue, a customer will wait a random length of time for service to begin. If ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 14, Issue 5

October 2006

226 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 October 2006

Published in TON Volume 14, Issue 5

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
286
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen YXiang ZDong YLu D(2011)Multi-Fractal Characteristics of Mobile Node's Traffic in Wireless Mesh Network with AODV and DSDV Routing ProtocolsWireless Personal Communications: An International Journal10.1007/s11277-009-9904-z58:4(741-757)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s11277-009-9904-z
Rizk AFidler M(2010)Sample path bounds for long memory FBM trafficProceedings of the 29th conference on Information communications10.5555/1833515.1833528(61-65)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833528
Feng BHuang CDevetsikiotis M(2009)FISTEACM Transactions on Modeling and Computer Simulation10.1145/1596519.159652119:4(1-39)Online publication date: 4-Nov-2009
https://dl.acm.org/doi/10.1145/1596519.1596521

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents