Towards unbiased end-to-end network diagnosis

ABSTRACT

Internet fault diagnosis is extremely important for end users, overlay network service providers (like Akamai [1]) and even Internet service providers (ISPs). However, because link-level properties cannot be uniquely determined from end-to-end measurements, the accuracy of existing statistical diagnosis approaches is subject to uncertainty from statistical assumptions about the network. In this paper, we propose a novel Least-biased End-to-end Network Diagnosis (in short, LEND) system for inferring link-level properties like loss rate. We define a minimal identifiable link sequence (MILS) as a link sequence of minimal length whose properties can be uniquely identified from end-to-end measurements. We also design efficient algorithms to find all the MILSes and infer their loss rates for diagnosis. Our LEND system works for any network topology and for both directed and undirected properties, and incrementally adapts to network topology and property changes. It gives highly accurate estimates of the loss rates of MILSes, as indicated by both extensive simulations and Internet experiments. Furthermore, we demonstrate that such diagnosis can be achieved with fine granularity and in near real-time even for reasonably large overlay networks. Finally, LEND can supplement existing statistical inference approaches and provide smooth tradeoff between diagnosis accuracy and granularity.

REFERENCES

• 1: Akamai Inc.," Technology overview," http://www.akamai.com/en/html/technology/overview.html
• 2: Ratul Mahajan , Neil Spring , David Wetherall , Thomas Anderson, User-level internet path diagnosis, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 3: K. Anagnostakis, M. Greenwald, and R. Ryger, "cing: Measuring network-internal delays using only existing infrastructure," in IEEE INFOCOM 2003.
• 4: M. Coates, A. Hero, R. Nowak, and B. Yu, "Internet Tomography," IEEE Signal Processing Magazine vol. 19, no. 3, pp. 47--65, 2002.
• 5: A. Adams et al., "The use of end-to-end multicast measurements for characterizing internal network behavior," in IEEE Communications May, 2000.
• 6: Tian Bu , Nick Duffield , Francesco Lo Presti , Don Towsley, Network tomography on general topologies, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 7: V. Padmanabhan, L. Qiu, and H. Wang, "Server-based inference of Internet link lossiness," in IEEE INFOCOM 2003.
• 8: Dan Rubenstein , Jim Kurose , Don Towsley, Detecting shared congestion of flows via end-to-end measurement, IEEE/ACM Transactions on Networking (TON), v.10 n.3, p.381-395, June 2002 [doi>10.1109/TNET.2002.1012369]
• 9: Nick Duffield, Simple network performance tomography, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948232]
• 10: Yan Chen , David Bindel , Hanhee Song , Randy H. Katz, An algebraic approach to practical and scalable overlay network monitoring, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 11: R. Govindan and H. Tangmunarunkit, "Heuristics for Internet map discovery," in IEEE INFOCOM 2000.
• 12: R. Caceres, N. Duffield, J. Horowitz, D. Towsley, and T. Bu, "Multicast-based inference of network-internal characteristics: Accuracy of packet loss estimation," in IEEE INFOCOM 1999.
• 13: N. G. Duffield, F. L. Presti, V. Paxson, and D. Towsley, "Inferring link loss using striped unicast probes," in IEEE INFOCOM 2001.
• 14: O. Gurewitz and M. Sidi, "Estimating one-way delays from cyclic-path delay measurements," in IEEE Infocom 2001.
• 15: R. Caceres, N. Duffield, J. Horowitz, and D. Towsley, "Multicast-based inference of network-internal loss characteristics," IEEE Transactions in Information Theory vol. 45, 1999.
• 16: N. Duffield, J. Horowitz, D. Towsley, W. Wei, and T. Friedman, "Multicast-based loss inference with missing data," IEEE Journal of Selected Areas of Communications vol. 20, no. 4, 2002.
• 17: Chiping Tang , Philip K. McKinley, On the Cost-Quality Tradeoff in Topology-Aware Overlay Path Probing, Proceedings of the 11th IEEE International Conference on Network Protocols, p.268, November 04-07, 2003
• 18: Richard A. Brualdi , Shmuel Friedland , Alex Pothen, The Sparse Basis Problem and Multilinear Algebra, SIAM Journal on Matrix Analysis and Applications, v.16 n.1, p.1-20, Jan. 1995 [doi>10.1137/S0895479892230067]
• 19: 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]
• 20: Y. Shavitt, X. Sun, A. Wool, and B. Yener, "Computing the unmeasured:An algebraic approach to Internet mapping," in IEEE INFOCOM 2001.
• 21: G. W. Stewart, Matrix Algorithms: Basic Decompositions Society for Industrial and Applied Mathematics, 1998.
• 22: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 23: R. Govindan and V. Paxson, "Estimating router icmp generation delays," in Passive & Active Measurement (PAM) 2002.
• 24: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 25: Neil Spring , Ratul Mahajan , Thomas Anderson, The causes of path inflation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863970]
• 26: PlanetLab, "http://www.planet-lab.org/,".
• 27: Z. M. Mao and et.al., "Scalable and accurate identification of as-level forwarding paths," in IEEE Infocom 2004.
• 28: University of Oregon Route Views Archive Project, "http://www.routeviews.org/".

INDEX TERMS

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

General Terms:
Experimentation, Measurement

Keywords:
internet diagnosis, linear algebra, network measurement