Network loss tomography using striped unicast probes

ABSTRACT

In this paper, we explore the use of end-to-end unicast traffic as measurement probes to infer link-level loss rates. We leverage off of earlier work that produced efficient estimates for link-level loss rates based on end-to-end multicast traffic measurements. We design experiments based on the notion of transmitting stripes of packets (with no delay between transmission of successive packets within a stripe) to two or more receivers. The purpose of these stripes is to ensure that the correlation in receiver observations matches as closely as possible what would have been observed if a multicast probe followed the same path to the receivers. Measurements provide good evidence that a packet pair to distinct receivers introduces considerable correlation which can be further increased by simply considering longer stripes. Using an M/M/1/K model for a link, we theoretically confirm this benefit for stripes. We also use simulation to explore how well these stripes translate into accurate link-level loss estimates. We observe good accuracy with packet pairs, with a typical error of about 1%, which significantly decreases as stripe length is increased.

REFERENCES

• 1: [1] A. Adams, T. Bu, R. Cáceres, N. G. Duffield, T. Friedman, J. Horowitz, F. Lo Presti, S. B. Moon, V. Paxson, and D. Towsley, "The use of end-to-end multicast measurements for characterizing internal network behavior," IEEE Commun. Mag., vol. 38, no. 5, pp. 152-159, May 2000.
• 2: [2] BRITE: Boston University Representative Internet Topology GEnerator. [Online]. Available: http://www.cs.bu.edu/brite/
• 3: [3] R. Cáceres, N. G. Duffield, J. Horowitz, and D. Towsley, "Multicast-based inference of network internal loss characteristics," IEEE Trans. Inf. Theory, vol. 45, no. 7, pp. 2462-2480, Nov. 1999.
• 4: [4] R. Caceres, N. G. Duffield, S. B. Moon, and D. Towsley, "Inferring link-level performance from end-to-end multicast measurements," presented at the Global Internet Symp., Rio de Janiero, Brazil, 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: [6] M. Coates and R. Nowak, "Network loss inference using unicast end-to-end measurement," in Proc. ITC Conf. IP Traffic, Modeling and Management, Monterey, CA, Sep. 2000, pp. 28-1-28-9.
• 7: [7] M. J. Coates and R. Nowak, "Network tomography for internal delay estimation," in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, May 2001, pp. 3409-3412.
• 8: 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
• 9: [9] N. G. Duffield, J. Horowitz, D. Towsley, W. Wei, and T. Friedman, "Multicast-based loss inference with missing data," IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 700-713, May 2002.
• 10: [10] N. G. Duffield, J. Horowitz, F. Lo Presti, and D. Towsley, "Multicast topology inference from measured end-to-end loss," IEEE Trans. Inf. Theory, vol. 48, no. 1, pp. 26-45, Jan. 2002.
• 11: [11] N. G. Duffield and F. Lo Presti, "Multicast inference of packet delay variance at interior network links," in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000, pp. 1351-1360.
• 12: [12] S. Floyd and V. Jacobson, "On traffic phase effects in packet-switched gateways," Internetworking: Research and Experience, vol. 3, pp. 115-156, 1992.
• 13: [13] S. Floyd, "Simulator tests," July 1995, revised May 1997 [Online]. Available: http://www.icir.org/floyd/papers/simtests.ps.Z
• 14: 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]
• 15: [15] GT-ITM Georgia Tech Internetwork Topology Models. [Online]. Available: http://www.cc.gatech.edu/fac/Ellen.Zegura/graphs.html
• 16: 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
• 17: [17] G. He and J. C. Hou, "On exploiting long range dependence of network traffic in measuring cross traffic on an end-to-end basis," in Proc. IEEE INFOCOM, Apr. 2003, pp. 1858-1868.
• 18: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 19: [19] V. Jacobson, Pathchar--A Tool to Infer Characteristics of Internet Paths. [Online]. Available: ftp://ftp.ee.lbl.gov/pathchar
• 20: 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
• 21: 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
• 22: [22] B. N. Levine, S. Paul, and J. J. Garcia-Luna-Aceves, "Organizing multicast receivers deterministically according to packet-loss correlation," Univ. California, Santa Cruz, Preprint.
• 23: Francesco Lo Presti , N. G. Duffield , Joe Horowitz , Don Towsley, Multicast-based inference of network-internal delay distributions, IEEE/ACM Transactions on Networking (TON), v.10 n.6, p.761-775, December 2002 [doi>10.1109/TNET.2002.805026]
• 24: [24] mtrace--Print multicast path from a source to a receiver. [Online]. Available: ftp://ftp.parc.xerox.com/pub/net-research/ipmulti
• 25: [25] ns--network simulator. [Online]. Available: http://www-mash.cs. berkeley.edu/ns/ns.html
• 26: 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
• 27: [27] V. Paxson, J. Mahdavi, A. Adams, and M. Mathis, "An architecture for large-scale Internet measurement," IEEE Commun. Mag., vol. 36, no. 8, pp. 48-54, Aug. 1998.
• 28: [28] M. J. Schervish, Theory of Statistics. New York: Springer, 1995.
• 29: [29] V. Ribeiro, M. Coates, R. Riedi, S. Sarvotham, B. Hendricks, and R. Baraniuk, "Multifractal cross-traffic estimation," presented at the ITC Specialist Seminar on IP Traffic Measurement, Modeling, and Management, Monterey, CA, Sep. 2000.
• 30: Dan Rubenstein , Jim Kurose , Don Towsley, Detecting shared congestion of flows via end-to-end measurement, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.145-155, June 18-21, 2000, Santa Clara, California, United States
• 31: [31] Y. Tsang, M. J. Coates, and R. Nowak, "Passive network tomography using EM algorithms," in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, Salt Lake City, UT, May 2001, pp. 1469-1472.
• 32: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques; Modeling techniques; Performance attributes

General Terms:
Design, Measurement, Performance

Keywords:
correlation, end-to-end measurement, estimation, network tomography, packet loss rates