skip to main content
article

A queueing-theoretic foundation of available bandwidth estimation: single-hop analysis

Published: 01 August 2007 Publication History

Abstract

Most existing available-bandwidth measurement techniques are justified using a constant-rate fluid cross-traffic model. To achieve a better understanding of the performance of current bandwidth measurement techniques in general traffic conditions, this paper presents a queueing-theoretic foundation of single-hop packet-train bandwidth estimation under bursty arrivals of discrete cross-traffic packets. We analyze the statistical mean of the packet-train output dispersion and its mathematical relationship to the input dispersion, which we call the probing-response curve. This analysis allows us to prove that the single-hop response curve in bursty cross-traffic deviates from that obtained under fluid cross traffic of the same average intensity and to demonstrate that this may lead to significant measurement bias in certain estimation techniques based on fluid models. We conclude the paper by showing, both analytically and experimentally, that the response-curve deviation vanishes as the packet-train length or probing packet size increases, where the vanishing rate is decided by the burstiness of cross-traffic.

References

[1]
{1} M. Abramowitz and I. A. Stegun, Eds., Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, ser. Applied Mathematics Series, 55. Washington, DC: Nat. Bureau of Standards, 1972.
[2]
{2} F. Baccelli, S. Macliiraju, D. Veitch, and J. Bolot, "The role of PASTA in network measurement," in Proc. ACM SIGCOMM, Aug. 2006, pp. 231-242.
[3]
{3} J. Bolot, "Characterizing end-to-end packet delay and loss in the internet," in Proc. ACM SIGCOMM, Aug. 1993, pp. 289-298.
[4]
{4} C. Dovrolis, P. Ramanathan, and D. Moore, "What do packet dispersion techniques measure?," in Proc. IEEE INFOCOM, Apr. 2001, pp. 905-914.
[5]
{5} G. He and J. Hou, "On exploiting long range dependence of network traffic in measuring cross traffic on an end-to-end basis," in Proc. IEEE INFOCOM, Mar. 2003, pp. 1858-1868.
[6]
{6} N. Hu and P. Steenkiste, "Evaluation and characterization of available bandwidth probing techniques," IEEE J. Sel. Areas Commun., vol. 21, no. 6, pp. 879-894, Aug. 2003.
[7]
{7} V. Jacobson, "Congestion avoidance and control," Proc. ACM SIGCOMM , pp. 314-329, Aug. 1988.
[8]
{8} M. Jain and C. Dovrolis, "End-to-end available bandwidth: Measurement methodology, dynamics, and relation with TCP throughput," Proc. ACM SIGCOMM, pp. 295-308, Aug. 2002.
[9]
{9} M. Jain and C. Dovrolis, "Ten fallacies and pitfalls in end-to-end available bandwidth estimation," in Proc. ACM IMC, Oct. 2004, pp. 272-277.
[10]
{10} S. Keshav, "A control-theoretic approach to flow control," Proc. ACM SIGCOMM, pp. 3-15, Sep. 1991.
[11]
{11} K. Lai and M. Baker, "Measuring bandwidth," in Proc. IEEE INFOCOM , Mar. 1999, pp. 235-245.
[12]
{12} X. Liu, K. Ravindran, B. Liu, and D. Loguinov, "Single-hop probing asymptotics in available bandwidth estimation: Sample-path analysis," Proc. ACM IMC, pp. 300-313, Oct. 2004.
[13]
{13} X. Liu, K. Ravindran, B. Liu, and D. Loguinov, "Single-hop probing asymptotics in available bandwidth estimation: Sample-path analysis," City University of New York, New York, Tech. Rep. TR-2004012, Aug. 2004. {Online}. Available: http://www.cs.gc.cuny.edu/tr/files/ TR-2004012.pdf
[14]
{14} X. Liu, K. Ravindran, and D. Loguinov, "Multi-hop probing asymptotics in available bandwidth estimation: Stochastic analysis," Proc. ACM IMC, pp. 173-186, Oct. 2005.
[15]
{15} X. Liu, K. Ravindran, and D. Loguinov, "What signals do packet-pair dispersions carry?," in Proc. IEEE INFOCOM, Mar. 2005, pp. 281-292.
[16]
{16} B. Melamed and D. Yao, "The ASTA property," in Advances in Queueing: Theory, Methods and Open Problems, J. H. Dshalalow, Ed. Boca Raton, FL: CRC Press, 1995, pp. 195-224.
[17]
{17} B. Melander, M. Bjorkman, and P. Gunningberg, "A new end-to-end probing and analysis method for estimating bandwidth bottlenecks," in Proc. IEEE GLOBECOM Global Internet Symp., Nov. 2000, pp. 415-420.
[18]
{18} B. Melander, M. Bjorkman, and P. Gunningberg, "Regression-based available bandwidth measurements," Proc. SPECTS, Jul. 2002.
[19]
{19} E. Muhammad and S. Stidham, Sample-Path Analysis of Queueing Systems . Norwell, MA: Kluwer Academic, 1999.
[20]
{20} A. Pasztor and D. Veitch, "The packet size dependence of packet pair like methods," in Proc. IEEE/IFIP Int. Workshop on Quality of Service (IWQoS), May 2002, pp. 204-213.
[21]
{21} V. Paxson, "End-to-end Internet packet dynamics," IEEE/ACM Trans. Netw., vol. 7, no. 3, pp. 277-292, Jun. 1999.
[22]
{22} V. Ribeiro, M. Coates, R. Riedi, S. Sarvotham, B. Hendricks, and R. Baraniuk, "Multifractal cross traffic estimation," in Proc. ITC Specialist Seminar on IP Traffic Measurement, Monterey, CA, Sep. 2000, pp. 15-1-15-10.
[23]
{23} V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell, "Pathchirp; Efficient available bandwidth estimation for network paths," presented at the Passive Active Measurement Workshop, San Diego, CA, Apr. 2003.
[24]
{24} J. Strauss, D. Katabi, and F. Kaashoek, "A measurement study of available bandwidth estimation tools," in Proc. ACM IMC, Oct. 2003, pp. 39-44.
[25]
{25} R. Wolff, "Poisson arrivals see time averages," Oper. Res., vol. 30, no. 2, pp. 223-231, 1982.
[26]
{26} R. Wolff, Stochastic Modeling and the Theory of Queues. Englewood Cliffs, NJ: Prentice-Hall, 1989.

Cited By

View all
  • (2019)Packet Clustering Introduced by RoutersACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33450324:3(1-28)Online publication date: 30-Aug-2019
  • (2014)Stochastic bandwidth estimation in networks with random serviceIEEE/ACM Transactions on Networking10.1109/TNET.2013.226191422:2(484-497)Online publication date: 1-Apr-2014
  • (2012)Analytical model of a weighted round robin service systemJournal of Electrical and Computer Engineering10.1155/2012/3749612012(17-17)Online publication date: 1-Jan-2012
  • Show More Cited By

Index Terms

  1. A queueing-theoretic foundation of available bandwidth estimation: single-hop analysis

            Recommendations

            Comments

            Information & Contributors

            Information

            Published In

            cover image IEEE/ACM Transactions on Networking
            IEEE/ACM Transactions on Networking  Volume 15, Issue 4
            August 2007
            243 pages

            Publisher

            IEEE Press

            Publication History

            Published: 01 August 2007
            Published in TON Volume 15, Issue 4

            Author Tags

            1. active measurement
            2. bandwidth estimation
            3. packet-pair sampling

            Qualifiers

            • Article

            Contributors

            Other Metrics

            Bibliometrics & Citations

            Bibliometrics

            Article Metrics

            • Downloads (Last 12 months)0
            • Downloads (Last 6 weeks)0
            Reflects downloads up to 16 Feb 2025

            Other Metrics

            Citations

            Cited By

            View all
            • (2019)Packet Clustering Introduced by RoutersACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33450324:3(1-28)Online publication date: 30-Aug-2019
            • (2014)Stochastic bandwidth estimation in networks with random serviceIEEE/ACM Transactions on Networking10.1109/TNET.2013.226191422:2(484-497)Online publication date: 1-Apr-2014
            • (2012)Analytical model of a weighted round robin service systemJournal of Electrical and Computer Engineering10.1155/2012/3749612012(17-17)Online publication date: 1-Jan-2012
            • (2012)MR-BARTJournal of Network and Computer Applications10.1016/j.jnca.2011.11.00635:2(731-742)Online publication date: 1-Mar-2012
            • (2011)Analysis of traffic correlation attacks on router queuesComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.10.01655:3(734-747)Online publication date: 1-Feb-2011
            • (2011)Estimating network link characteristics using packet-pair dispersionComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.05.00855:5(1052-1068)Online publication date: 1-Apr-2011
            • (2010)A system-theoretic approach to bandwidth estimationIEEE/ACM Transactions on Networking10.1109/TNET.2009.203511518:4(1040-1053)Online publication date: 1-Aug-2010
            • (2009)A two-way available bandwidth estimation scheme for multimedia streaming networks adopting scalable video codingProceedings of the 32nd international conference on Sarnoff symposium10.5555/1719650.1719671(109-114)Online publication date: 30-Mar-2009
            • (2009)Impact of transient CSMA/CA access delays on active bandwidth measurementsProceedings of the 9th ACM SIGCOMM conference on Internet measurement10.1145/1644893.1644941(397-409)Online publication date: 4-Nov-2009
            • (2009)Online Estimation of Available Bandwidth and Fair Share Using Kalman FilteringProceedings of the 8th International IFIP-TC 6 Networking Conference10.1007/978-3-642-01399-7_43(548-561)Online publication date: 11-May-2009
            • Show More Cited By

            View Options

            Login options

            Full Access

            View options

            PDF

            View or Download as a PDF file.

            PDF

            eReader

            View online with eReader.

            eReader

            Figures

            Tables

            Media

            Share

            Share

            Share this Publication link

            Share on social media