User-level internet path diagnosis

ABSTRACT

Diagnosing faults in the Internet is arduous and time-consuming, in part because the network is composed of diverse components spread across many administrative domains. We consider an extreme form of this problem: can end users, with no special privileges, identify and pinpoint faults inside the network that degrade the performance of their applications? To answer this question, we present both an architecture for user-level Internet path diagnosis and a practical tool to diagnose paths in the current Internet. Our architecture requires only a small amount of network support, yet it is nearly as complete as analyzing a packet trace collected at all routers along the path. Our tool, tulip, diagnoses reordering, loss and significant queuing events by leveraging well deployed but little exploited router features that approximate our architecture. Tulip can locate points of reordering and loss to within three hops and queuing to within four hops on most paths that we measured. This granularity is comparable to that of a hypothetical network tomography tool that uses 65 diverse hosts to localize faults on a given path. We conclude by proposing several simple changes to the Internet to further improve its diagnostic capabilities.

REFERENCES

• 1: Marcos K. Aguilera , Jeffrey C. Mogul , Janet L. Wiener , Patrick Reynolds , Athicha Muthitacharoen, Performance debugging for distributed systems of black boxes, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 2: K. Anagnostakis, M. Greenwald, and R. Ryger. cing: Measuring network-internal delays using only existing infrastructure. In IEEE INFOCOM, Apr. 2003.
• 3: 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
• 4: Paul Barford , Mark Crovella, Critical path analysis of TCP transactions, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.238-248, June 2001 [doi>10.1109/90.929848]
• 5: P. Barham, R. Isaacs, R. Mortier, and D. Narayanan. Magpie: Online modelling and performance-aware systems. In HotOS-IX, May 2003.
• 6: John Bellardo , Stefan Savage, Measuring packet reordering, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637216]
• 7: A. Broido. Ping Record Route stats. http://www.caida.org/~broido/png/pingR.html.
• 8: Mike Y. Chen , Emre Kiciman , Eugene Fratkin , Armando Fox , Eric Brewer, Pinpoint: Problem Determination in Large, Dynamic Internet Services, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.595-604, June 23-26, 2002
• 9: Cisco IOS NetFlow. http://www.cisco.com/warp/public/732/Tech/nmp/netflow/index.shtml.
• 10: Jeffrey Dean , James E. Hicks , Carl A. Waldspurger , William E. Weihl , George Chrysos, ProfileMe: hardware support for instruction-level profiling on out-of-order processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.292-302, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 11: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 12: N. G. Duffield , Matthias Grossglauser, Trajectory sampling for direct traffic observation, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.280-292, June 2001 [doi>10.1109/90.929851]
• 13: N. Duffield, F. Presti, V. Paxson, and D. Towsley. Inferring link loss using striped unicast probes. In IEEE INFOCOM, Apr. 2001.
• 14: Cristian Estan , George Varghese, New directions in traffic measurement and accounting, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 15: S. Floyd. Questions about the Internet. http://www.icir.org/floyd/questions.html, May 2002.
• 16: R. Govindan and V. Paxson. Estimating router ICMP generation delays. In Passive & Active Measurement (PAM), Mar. 2002.
• 17: Bradley Huffak r , Daniel Plummer , David Moore , and k. Claffy, Topology Discovery by Active Probing, Proceedings of the 2002 Symposium on Applications and the Internet (SAINT) Workshops, p.90, January 28-February 01, 2002
• 18: V. Jacobson. Pathchar. ftp://ftp.ee.lbl.gov/pathchar.
• 19: 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
• 20: C. A. Kent , J. C. Mogul, Fragmentation considered harmful, Proceedings of the ACM workshop on Frontiers in computer communications technology, p.390-401, August 11-13, 1987, Stowe, Vermont, United States
• 21: K. Lai and M. Baker. Nettimer: A tool for measuring bottleneck link bandwidth. In USITS, Mar. 2001.
• 22: K. Lakshminarayanan, I. Stoica, and S. Shenker. Building a flexible and efficient routing infrastructure: Need and challenges. Technical Report CSD-03-1254, University of California, Berkeley, 2003.
• 23: Matthew J. Luckie , Anthony J. McGregor , Hans-Werner Braun, Towards improving packet probing techniques, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505221]
• 24: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 25: G. Martinez. Problems with AT&T. NANOG archives: http://www.merit.edu/mail.archives/nanog/msg08420.html, Mar. 2003.
• 26: J. McClave and F. Dietrich. Statistics. Macmillan Publishing Company, 6th edition, 1994.
• 27: P. McKenney. Stochastic fairness queuing. In IEEE INFOCOM, June 1990.
• 28: S. Moon, P. Skelly, and D. Towsley. Estimation and removal of clock skew from network delay measurements. In IEEE INFOCOM, Mar. 1999.
• 29: S. Ostermann. tcptrace. http://jarok.cs.ohiou.edu/software/tcptrace/index.html.
• 30: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 31: J. Padhye and S. Floyd. Identifying the TCP behavior of Web servers. In ACM SIGCOMM, Aug. 2001.
• 32: V. Padmanabhan, L. Qiu, and H. Wang. Server-based inference of Internet performance. In IEEE INFOCOM, Apr. 2003.
• 33: K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, F. Tobagi, and C. Diot. Analysis of measured single-hop delay from an operational backbone network. In IEEE INFOCOM, June 2002.
• 34: 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]
• 35: Attila Pásztor , Darryl Veitch, PC based precision timing without GPS, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 36: 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
• 37: Vern Paxson, On calibrating measurements of packet transit times, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.11-21, June 22-26, 1998, Madison, Wisconsin, United States
• 38: R. Perlman. Network Layer Protocols with Byzantine Robustness. PhD thesis, MIT, 1988.
• 39: L. Peterson, T. Anderson, D. Culler, and T. Roscoe. A blueprint for introducing disruptive technology into the Internet. In HotNets-I, Oct. 2002.
• 40: J. Postel. Internet control message protocol. IETF RFC 792, Sept. 1981.
• 41: J. Postel. Internet protocol specification. IETF RFC 791, Sept. 1981.
• 42: RouteScience. http://www.routescience.com/.
• 43: R. Ryger. fixclock: removing clock artifacts from communication timestamps. Technical Report DCS/TR-1243, Yale University, March 2003.
• 44: S. Savage. Sting: A TCP-based network measurement tool. In USITS, Oct. 1999.
• 45: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 46: Stefan Savage , David Wetherall , Anna Karlin , Tom Anderson, Practical network support for IP traceback, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.295-306, August 28-September 01, 2000, Stockholm, Sweden
• 47: Alex C. Snoeren, Hash-based IP traceback, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.3-14, August 2001, San Diego, California, United States
• 48: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 49: N. Spring, D. Wetherall, and T. Anderson. Scriptroute: A public Internet measurement facility. In USITS, Mar. 2003.
• 50: W. Stevens. TCP slow start, congestion avoidance, fast retransmit, and fast recovery algorithms. IETF RFC 2001, Jan. 1997.
• 51: Y. Tsang, M. Coates, and R. Nowak. Passive network tomography using EM algorithms. In IEEE Int'l Conference on Acoustics, Speech, and Signal Processing, May 2001.
• 52: Tulip. http://www.cs.washington.edu/research/networking/tulip/.
• 53: A. Whitaker and D. Wetherall. Forwarding without loops in Icarus. In IEEE OPENARCH, June 2002.
• 54: L. Zhang, Z. Liu, and C. Xia. Clock synchronization algorithms for network measurements. In IEEE INFOCOM, June 2002.
• 55: Yin Zhang , Lee Breslau , Vern Paxson , Scott Shenker, On the characteristics and origins of internet flow rates, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 56: 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.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Measurement, Performance

Keywords:
measurement tools, path diagnosis