skip to main content
10.1145/1028788.1028820acmconferencesArticle/Chapter ViewAbstractPublication PagesimcConference Proceedingsconference-collections
Article

MultiQ: automated detection of multiple bottleneck capacities along a path

Published: 25 October 2004 Publication History

Abstract

multiQ is a passive capacity measurement tool suitable for large-scale studies of Internet path characteristics. It is the first passive tool that discovers the capacity of <i>multiple</i> congested links along a path from a single flow trace, and the first tool that effectively extracts capacity information from ack-only traces. It uses <i>equally-spaced mode gaps</i> in TCP flows' packet interarrival time distributions to detect multiple bottleneck capacities in their relative order.
We validate multiQ in depth using the RON overlay network, which provides more than 400 heterogeneous, well-understood Internet paths. We compare multiQ with two other capacity measurement tools (Nettimer and Pathrate) in the first large-scale wide-area evaluation of capacity measurement techniques, and find that multiQ is highly accurate; for instance, though multiQ is passive, it achieves the same accuracy as Pathrate, which is active.

References

[1]
Abilene. http://monon.uits.iupui.edu/.
[2]
A. Akella, S. Seshan, and A. Shaikh. An Empirical Evaluation of Wide-Area Internet Bottlenecks. In Proc. IMC, October 2003.
[3]
K. Claffy, G. Miller, and K. Thompson. The Nature of the Beast: Recent Traffic Measurements from an Internet Backbone, 1998. http://www.caida.org/outreach/resources/learn/packetsizes/.
[4]
C. Dovrolis, P. Ramanathan, and D. Moore. Packet Dispersion Techniques and Capacity Estimation. IEEE/ACM Trans. on Neworking. Under submission.
[5]
N. Hu and P. Steenkiste. Evaluation and Characterization of Available Bandwidth Techniques. IEEE JSAC Special Issue in Internet and WWW Measurement, Mapping, and Modeling, 2003.
[6]
M. Jain and C. Dovrolis. Pathload: A Measurement Tool for End-to-End Available Bandwidth. In Proc. Passive and Active Measurement Workshop, March 2002.
[7]
H. Jiang and C. Dovrolis. Source-Level IP Packet Bursts: Causes and Effects. In Proc. IMC, October 2003.
[8]
S. Katti, D. Katabi, C. Blake, E. Kohler, and J. Strauss. M&M: A passive toolkit for measuring, tracking and correlating path characteristics. Technical Report 945, MIT CSAIL, 2004.
[9]
S. Keshav. A Control-Theoretic Approach to Flow Control. In Proc. ACM SIGCOMM, September 1991.
[10]
K. Lai and M. Baker. Nettimer: A Tool for Measuring Bottleneck Link Bandwidth. In Proc. USENIX, 2001.
[11]
Kevin Lai and Mary Baker. Measuring Bandwidth. In Proc. IEEE INFOCOM, 1999.
[12]
R. Mahajan, N. Spring, D. Wetherall, and T. Anderson. User Level Internet Path Diagnosis. In Proc. ACM SOSP, October 2003.
[13]
B. Melander, M. Bjorkman, and P. Gunningberg. A New End-to-End Probing and Analysis Method for Estimating Bandwidth Bottlenecks. In Proc. Global Internet Symposium, 2000.
[14]
A. Pasztor and D. Veitch. The Packet Size Dependence of Packet Pair Methods. In Proc. 10th IWQoS, 2003.
[15]
pathchar. ftp://ee.lbl.gov/pathchar.tar.Z.
[16]
V. Paxson. End-to-End Internet Packet Dynamics. IEEE/ACM Trans. on Networking, June 1999.
[17]
V. E. Paxson. Measurements and Analysis of End-to-End Internet Dynamics. PhD thesis, Berkeley, 1997.
[18]
Resilient Overlay Networks. http://nms.lcs.mit.edu/ron/.
[19]
V. J. Ribeiro, M. Coates, R. H. Riedi, S. Sarvotham, and R. G. Baraniuk. Multifractal Cross Traffic Estimation. In Proc. ITC Specialist Seminar on IP Traffic Measurement, September 2000.
[20]
V. J. Ribeiro, R. H. Riedi, R. G Baraniuk, J. Navratil, and L. Cottrell. pathChirp: Efficient Available Bandwidth Estimation for Network Paths. In Proc. Passive and Active Measurement Workshop, 2003.
[21]
D. Scott. Multivariate Density Estimation. John Wiley, 1992.
[22]
C. Shannon, D. Moore, and K. Claffy. Beyond Folklore: Observations on Fragmented Traffic. In IEEE/ACM Trans. on Networking, 2002.
[23]
H. Uijiterwall and M. Santcroos. Bandwidth Estimations for Test Traffic Measurement Project, December 2003.

Cited By

View all
  • (2016)Implementation Design of Available Bandwidth Measurement SchemeAdjunct Proceedings of the 13th International Conference on Mobile and Ubiquitous Systems: Computing Networking and Services10.1145/3004010.3004047(257-262)Online publication date: 28-Nov-2016
  • (2015)On the performance of packet-pair based path capacity estimation in wireless Ad Hoc networks2015 International Conference on Military Communications and Information Systems (ICMCIS)10.1109/ICMCIS.2015.7158705(1-9)Online publication date: May-2015
  • (2015)BLORConcurrency and Computation: Practice & Experience10.1002/cpe.335627:14(3614-3632)Online publication date: 25-Sep-2015
  • Show More Cited By

Index Terms

  1. MultiQ: automated detection of multiple bottleneck capacities along a path

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      IMC '04: Proceedings of the 4th ACM SIGCOMM conference on Internet measurement
      October 2004
      386 pages
      ISBN:1581138210
      DOI:10.1145/1028788
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 25 October 2004

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. capacity
      2. measurement
      3. modeling

      Qualifiers

      • Article

      Conference

      IMC04
      Sponsor:
      IMC04: Internet Measurement Conference
      October 25 - 27, 2004
      Taormina, Sicily, Italy

      Acceptance Rates

      Overall Acceptance Rate 277 of 1,083 submissions, 26%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)14
      • Downloads (Last 6 weeks)1
      Reflects downloads up to 14 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2016)Implementation Design of Available Bandwidth Measurement SchemeAdjunct Proceedings of the 13th International Conference on Mobile and Ubiquitous Systems: Computing Networking and Services10.1145/3004010.3004047(257-262)Online publication date: 28-Nov-2016
      • (2015)On the performance of packet-pair based path capacity estimation in wireless Ad Hoc networks2015 International Conference on Military Communications and Information Systems (ICMCIS)10.1109/ICMCIS.2015.7158705(1-9)Online publication date: May-2015
      • (2015)BLORConcurrency and Computation: Practice & Experience10.1002/cpe.335627:14(3614-3632)Online publication date: 25-Sep-2015
      • (2014)Path capacity estimation by passive measurement for the constant monitoring of every network pathThe 16th Asia-Pacific Network Operations and Management Symposium10.1109/APNOMS.2014.6996516(1-6)Online publication date: Sep-2014
      • (2014)Towards a Peer-to-Peer Bandwidth MarketplaceProceedings of the 15th International Conference on Distributed Computing and Networking - Volume 831410.1007/978-3-642-45249-9_20(302-316)Online publication date: 4-Jan-2014
      • (2014)Lightweight enhanced monitoring for high speed networksTransactions on Emerging Telecommunications Technologies10.1002/ett.263725:11(1095-1113)Online publication date: 1-Nov-2014
      • (2013)Support Vector Regression Technique for Multimedia Quality Control in Multicast NetworksProceedings of the 2013 IEEE 10th International Conference on Ubiquitous Intelligence & Computing and 2013 IEEE 10th International Conference on Autonomic & Trusted Computing10.1109/UIC-ATC.2013.90(601-606)Online publication date: 18-Dec-2013
      • (2013)On the Security of End-to-End Measurements Based on Packet-Pair DispersionsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2012.22265798:1(149-162)Online publication date: 1-Jan-2013
      • (2013)Inferring the periodicity in large-scale Internet measurements2013 Proceedings IEEE INFOCOM10.1109/INFCOM.2013.6566964(1672-1680)Online publication date: Apr-2013
      • (2013)A TCP delay-based mechanism for detecting congestion in the Internet2013 Third International Conference on Communications and Information Technology (ICCIT)10.1109/ICCITechnology.2013.6579538(141-145)Online publication date: Jun-2013
      • Show More Cited By

      View Options

      Login options

      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