Measuring capacity bandwidth of targeted path segments

ABSTRACT

Accurate measurement of network bandwidth is important for network management applications as well as flexible Internet applications and protocols which actively manage and dynamically adapt to changing utilization of network resources. Extensive work has focused on two approaches to measuring bandwidth: measuring it hop-by-hop, and measuring it end-to-end along a path. Unfortunately, best-practice techniques for the former are inefficient and techniques for the latter are only able to observe bottlenecks visible at end-to-end scope. In this paper, we develop end-to-end probing methods which can measure bottleneck capacity bandwidth along arbitrary, targeted subpaths of a path in the network, including subpaths shared by a set of flows. We evaluate our technique through ns simulations, then provide a comparative Internet performance evaluation against hop-by-hop and end-to-end techniques. We also describe a number of applications which we foresee as standing to benefit from solutions to this problem, ranging from network troubleshooting and capacity provisioning to optimizing the layout of application-level overlay networks, to optimized replica placement.

REFERENCES

• 1: B. Ahlgren, M. Bjorkman, and B. Melander, "Network probing using packet trains," Swedish Inst., Technical Report, Mar. 1999.
• 2: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 3: Estimating Available Capacity of a Network Connection, Proceedings of the 8th IEEE International Conference on Networks, p.131, September 05-08, 2000
• 4: Jean-Chrysotome Bolot, End-to-end packet delay and loss behavior in the internet, Conference proceedings on Communications architectures, protocols and applications, p.289-298, September 13-17, 1993, San Francisco, California, United States
• 5: John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: J. Byers, M. Luby, and M. Mitzenmacher, "Accessing multiple mirror sites in parallel: Using Tornado codes to speed up downloads," in Proc. IEEE INFOCOM'99, Mar. 1999, pp. 275-83.
• 7: Robert L. Carter , Mark E. Crovella, Measuring bottleneck link speed in packet-switched networks, Performance Evaluation, 27-28, p.297-318, Oct. 1996 [doi>10.1016/0166-5316(96)00036-3]
• 8: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 9: Mark E. Crovella , Robert Frangioso , Mor Harchol-Balter, Connection scheduling in web servers, Proceedings of the 2nd conference on USENIX Symposium on Internet Technologies and Systems, p.22-22, October 11-14, 1999, Boulder, Colorado
• 10: C. Dovrolis, P. Ramanathan, and D. Moore, "What do packet dispersion techniques measure?," in INFOCOM'01, Anchorage, AK, Apr. 2001.
• 11: Allen B. Downey, Using pathchar to estimate Internet link characteristics, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.241-250, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 12: N. Duffield, F. L. Presti, V. Paxson, and D. Towsley, "Inferring link loss using striped unicast probes," in IEEE INFOCOM 2001, Apr. 2001.
• 13: NLANR Network Traffic Traces. NLANR: National Lab. for Applied Network Research, 2003 [Online]. Available: http://www.caida.org/publications/papers/2003/nlanr/nlanr\-overview.pdf
• 14: M. Goyal, R. Guerin, and R. Rajan, "Predicting TCP throughput from non-invasive network sampling," in IEEE INFOCOM'02, Jun. 2002.
• 15: Evaluation of a Novel Two-Step Server Selection Metric, Proceedings of the Ninth International Conference on Network Protocols, p.290, November 11-14, 2001
• 16: Khaled A. Harfoush , Azer Bestavros, A framework and toolkit for the effective measurement and representation of internet internal characteristics, Boston University, Boston, MA, 2003
• 17: K. Harfoush , A. Bestavros , J. Byers, Robust identification of shared losses using end-to-end unicast probes, Proceedings of the 2000 International Conference on Network Protocols, p.22, November 14-17, 2000
• 18: N. Hu, L. Li, and P. Steenkiste, "Evaluation and characterization of available bandwidth probing techniques," IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 879-974, Aug. 2004.
• 19: Ningning Hu , Li (Erran) Li , Zhuoqing Morley Mao , Peter Steenkiste , Jia Wang, Locating internet bottlenecks: algorithms, measurements, and implications, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 20: V. Jacobson, Pathchar: A tool to infer characteristics of Internet paths. [Online]. Available: ftp://ftp.ee.lbl.gov/pathchar
• 21: V. Jacobson, Traceroute. 1989 [Online]. Available: ftp://ftp.ee.lbl.gov/ traceroute.tar.Z
• 22: Manish Jain , Constantinos Dovrolis, End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughput, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 23: M. Jain and C. Dovrolis, "Pathload: A measurement tool for end-to-end available bandwidth," in Passive and Active Measurement (PAM) Workshop 2002, Fort Collins, CO, Mar. 2002.
• 24: John Jannotti , David K. Gifford , Kirk L. Johnson , M. Frans Kaashoek , James W. O'Toole, Jr., Overcast: reliable multicasting with on overlay network, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.14-14, October 22-25, 2000, San Diego, California
• 25: J. Kangasharju, J. Roberts, and K. W. Ross, "Object replication strategies in content distribution networks," in Proc. WCW'01: Web Caching and Content Distribution Workshop, Boston, MA, Jun. 2001.
• 26: Rohit Kapoor , Ling-Jyh Chen , Li Lao , Mario Gerla , M. Y. Sanadidi, CapProbe: a simple and accurate capacity estimation technique, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 27: Srinivasan Keshav, A control-theoretic approach to flow control, Proceedings of the conference on Communications architecture & protocols, p.3-15, September 03-06, 1991, Zurich, Switzerland
• 28: Srinivasan Keshav, Congestion control in computer networks, University of California at Berkeley, Berkeley, CA, 1992
• 29: Kevin Lai , Mary Baker, Measuring link bandwidths using a deterministic model of packet delay, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.283-294, August 28-September 01, 2000, Stockholm, Sweden
• 30: Kevin Lai , Mary Baker, Nettimer: a tool for measuring bottleneck link, bandwidth, Proceedings of the 3rd conference on USENIX Symposium on Internet Technologies and Systems, p.11-11, March 26-28, 2001, San Francisco, California
• 31: B. Mah, pchar. 2000 [Online]. Available: http://www.ca.sandia.gov/ bmah/Software/pchar
• 32: The Abilene Network Logical Map. Jan. 30, 2002 [Online]. Available: http://www.abilene.iu.edu/images/logical.pdf
• 33: B. Melander, M. Bjorkman, and P. Gunningberg, "A new end-to-end probing and analysis method for estimating bandwidth bottlenecks," in IEEE GLOBECOM 2000, San Francisco, CA, Nov. 2000.
• 34: ns: Network Simulator [Online]. Available: http://www-mash.cs. berkeley.edu/ns/ns.html
• 35: Attila Pásztor , Darryl Veitch, Active probing using packet quartets, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637247]
• 36: A. Pasztor and D. Veitch, "The packet size dependence of packet pair like methods," in Tenth International Workshop on Quality of Service (IWQoS), 2002.
• 37: Vern Paxson, End-to-end routing behavior in the Internet, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.25-38, August 28-30, 1996, Palo Alto, California, United States
• 38: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 39: Vern Edward Paxson, Measurements and analysis of end-to-end Internet dynamics, University of California at Berkeley, Berkeley, CA, 1998
• 40: P. Radoslavov, R. Govindan, and D. Estrin, "Topology-informed internet replica placement," in WCW'01: Web Caching and Content Distribution Workshop, Boston, MA, Jun. 2001.
• 41: V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell, "PathChirp: Efficient available bandwidth estimation for network paths," in Passive and Active Measurement (PAM) Workshop 2003, La Jolla, CA, Apr. 2003.
• 42: P. Rodriguez, A. Kirpal, and E. Biersack, "Parallel-access for mirror sites in the internet," in IEEE INFOCOM'00, Mar. 2000.
• 43: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 44: Jacob Strauss , Dina Katabi , Frans Kaashoek, A measurement study of available bandwidth estimation tools, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948211]
• 45: Z. ZiXuan, B. Lee, C. Fu, and J. Song, "Packet triplet: A novel approach to estimate path capacity," IEEE Commun. Lett., vol. 9, no. 12, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
bottleneck bandwidth, content distribution, end-to-end measurement, overlay networks, packet-pair