Using loss pairs to discover network properties

ABSTRACT

Accurate estimation of network characteristics based on endpoint measurements is a challenging and important problem. In this paper we propose and evaluate a new tool for the discovery of network charactertics called loss pairs. A loss pair is a pair of packets travelling the same path and close together in time, such that exactly one of the two packets is dropped in the network. Loss pairs provide insight into network conditions close to the time when loss is occuring. Using loss pairs, we show that it is possible to characterize the packet dropping behavior of drop-tail and AQM routers internal to the network, from measurements made at end systems. Furthermore, we show that loss pairs can be used to estimate bottleneck buffer sizes of droptail routers. An attractive feature of loss pairs is that they lend themselves naturally to use in a passive-measurement setting. Using such an approach, we show that loss pairs provide estimates that are generally accurate and robust over a wide range of network conditions.

REFERENCES

• 1: Mark Allman , Vern Paxson, On estimating end-to-end network path properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.263-274, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 2: Hari Balakrishnan , Hariharan S. Rahul , Srinivasan Seshan, An integrated congestion management architecture for Internet hosts, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.175-187, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 3: Jean-Chrysostome Bolot. Characterizing end-to-end packet delay and loss in the Internet. Journal of High Speed Networks, 2(3):305-323, 1993.
• 4: R. Caceres, N.G. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network-internal loss characteristics. IEEE Transactions on Information Theory, November 1999.
• 5: 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]
• 6: D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V. Jacobson, G. Minshall, C. Partridge, L. Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski, and L. Zhang. Recommendations on queue management and congestion avoidance in the intemet. RFC 2309, April 1998.
• 7: 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
• 8: Wu-Chang Feng , Dilip Kandlur , Debanjan Saha , Kang G. Shin, BLUE: an alternative approach to active queue management, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.41-50, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378350]
• 9: W. Feng, D. Kandlur, D. Saha, and K. Shin. Stochastic fair blue: A queue management algorithm for enforcing fairness. In Proc. of ZNFOCOM 2001, April 2001.
• 10: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 11: 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
• 12: Khaled Harfoush , Azer Bestavros , John Byers, Measuring Bottleneck Bandwidth of Targeted Path Segments, Boston University, Boston, MA, 2001
• 13: Information Sciences Institute. The ns-2 simulator. Available at http: //www . isi. edu/nsnam/ns/.
• 14: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 15: Van Jacobson. pathchar. ftp://ftp.ee.lbl.gov/pathchar/, 1997.
• 16: 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
• 17: K. Lai and M. Baker. Measuring bandwidth. In Proceedings of IEEE ZNFOCOM '99, March 1999.
• 18: 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
• 19: Bruce Mah. pchar. http://www.employees.org/lbmah/Software/pchar, 1999.
• 20: M. Mathis. Treno bulk transfer capacity. Internet- Draft:Work in progress; draft-ietf-ippm-treno-btc-03.txt, Feb 1999.
• 21: Kihong Park , Gitae Kim , Mark Crovella, On the relationship between file sizes, transport protocols, and self-similar network traffic, Proceedings of the 1996 International Conference on Network Protocols (ICNP '96), p.171, October 29-November 01, 1996
• 22: Vern Edward Paxson, Measurements and analysis of end-to-end Internet dynamics, University of California at Berkeley, Berkeley, CA, 1998
• 23: Stefan Savage. Sting: a tcp-based network measurement tool. In Proceedings of the USENIX Symposium on Internet Technologies and Systems, 1999.
• 24: Srini Seshan, Mark Stemm, and Randy Katz. SPAND: shared passive network performance discovery. In Proceedings of the USENZXSymposium on Internet Technologies and Systems, 1997.
• 25: Walter Willinger , Murad S. Taqqu , Robert Sherman , Daniel V. Wilson, Self-similarity through high-variability: statistical analysis of ethernet LAN traffic at the source level, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.100-113, August 28-September 01, 1995, Cambridge, Massachusetts, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Measurement, Performance