Characterization of failures in an operational IP backbone network

ABSTRACT

As the Internet evolves into a ubiquitous communication infrastructure and supports increasingly important services, its dependability in the presence of various failures becomes critical. In this paper, we analyze IS-IS routing updates fromthe Sprint IP backbone network to characterize failures that affect IP connectivity. Failures are first classified based on patterns observed at the IP-layer; in some cases, it is possible to further infer their probable causes, such as maintenance activities, router-related and optical layer problems. Key temporal and spatial characteristics of each class are analyzed and, when appropriate, parameterized using well-known distributions. Our results indicate that 20% of all failures happen during a period of scheduled maintenance activities. Of the unplanned failures, almost 30% are shared by multiple links and are most likely due to router-related and optical equipment-related problems, respectively, while 70% affect a single link at a time. Our classification of failures reveals the nature and extent of failures in the Sprint IP backbone. Furthermore, our characterization of the different classes provides a probabilistic failure model, which can be used to generate realistic failure scenarios, as input to various network design and traffic engineering problems.

REFERENCES

• 1: C. Fraleigh, S. Moon, B. Lyles, C. Cotton, M. Khan, R. Rockell, D. Moll, T. Seely, and C. Diot, "Packet-level traffic measurements from the Sprint IP backbone," IEEE Network Mag., vol. 17, no. 6, pp. 6-16, Nov.-Dec. 2003.
• 2: K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, and C. Diot, "Measurement and analysis of single-hop delay on an IP backbone network," IEEE J. Sel. Areas Commun., vol. 21, no. 6, pp. 908-921, Aug. 2003.
• 3: Gianluca Iannaccone , Chen-nee Chuah , Richard Mortier , Supratik Bhattacharyya , Christophe Diot, Analysis of link failures in an IP backbone, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637238]
• 4: G. Iannaccone, C.-N. Chuah, S. Bhattacharyya, and C. Diot, "Feasibility of IP restoration in a tier-1 backbone," IEEE Netw., vol. 18, no. 2, pp. 13-19, Mar. 2004.
• 5: D. Oran, OSI IS-IS Intra-domain Routing Protocol, RFC Editor, 1990
• 6: S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot, "An approach to alleviate link overload as observed on an IP backbone," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 2003, vol. 1, pp. 406-416.
• 7: A. Markopoulou, G. Iannaccone, S. Bhatacharyya, C.-N. Chuah, and C. Diot, "Characterization of failures in an IP backbone," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, vol. 4, pp. 2307-2317.
• 8: C. Fraleigh, F. Tobagi, and C. Diot, "Provisioning IP backbone networks to support latency sensitive traffic," in Proc. IEEE INFOCOM, San Francisco, CA, Mar.-Apr. 2003, vol. 1, pp. 375-385.
• 9: Catherine Boutremans , Gianluca Iannaccone , Christophe Diot, Impact of link failures on VoIP performance, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507680]
• 10: A. Fumagalli and L. Valcarenghi, "IP restoration versus WDM protection: Is there an optimal choice?," IEEE Network Magazine, vol. 14, no. 6, pp. 34-41, Nov. 2000.
• 11: L. Sahasrabuddhe, S. Ramamurthy, and B. Mukherjee, "Fault management in IP-over-WDM networks: WDM protection versus IP restoration," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 21-33, Jan. 2002.
• 12: A. Alaettinoglou and S. Casner, "Detailed analysis of ISIS Routing Protocol on the Qwest backbone," NANOG [Online]. Available: http:// www.nanog.org/mtg-0202/ppt/cengiz.pdf
• 13: A. Nucci, B. Schroeder, S. Bhattacharyya, N. Taft, and C. Diot, "IGP link weight assignment for transient link failures," in Proc. 18th Int. Teletraffic Congr., Berlin, Germany, Sep. 2003.
• 14: B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world," IEEE J Sel. Areas Commun., vol. 20, no. 4, pp. 756-767, Apr. 2002.
• 15: M. Durvy, C. Diot, N. Taft, and P. Thiran, "Network availability based service differentiation," in Proc. IWQoS, Monterey, CA, Jun. 2003.
• 16: Srihari Nelakuditi , Sanghwan Lee , Yinzhe Yu , Zhi-Li Zhang , Chen-Nee Chuah, Fast local rerouting for handling transient link failures, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.359-372, April 2007 [doi>10.1109/TNET.2007.892851]
• 17: 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]
• 18: Y. Zhang, V. Paxson, and S. Shenker, "The stationarity of Internet path properties: Routing, loss and throughput," Tech. Rep. ICIR, 2000 [On-line]. Available: http://www.icir.org/
• 19: Michael Dahlin , Bharat Baddepudi V. Chandra , Lei Gao , Amol Nayate, End-to-end WAN service availability, IEEE/ACM Transactions on Networking (TON), v.11 n.2, p.300-313, April 2003 [doi>10.1109/TNET.2003.810312]
• 20: Craig Labovitz , Abha Ahuja , Farnam Jahanian, Experimental Study of Internet Stability and Backbone Failures, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.278, June 15-18, 1999
• 21: David Watson , Farnam Jahanian , Craig Labovitz, Experiences With Monitoring OSPF on a Regional Service Provider Network, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.204, May 19-22, 2003
• 22: Aman Shaikh , Chris Isett , Albert Greenberg , Matthew Roughan , Joel Gottlieb, A case study of OSPF behavior in a large enterprise network, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637236]
• 23: Ramana Rao Kompella , Jennifer Yates , Albert Greenberg , Alex C. Snoeren, IP fault localization via risk modeling, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.57-70, May 02-04, 2005
• 24: Srikanth Kandula , Dina Katabi , Jean-Philippe Vasseur, Shrink: a tool for failure diagnosis in IP networks, Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080173.1080178]
• 25: M. Steinder and A. Sethi, "Increasing robustness of fault localization through analysis of lost, spurious and positive symptoms," in Proc. IEEE INFOCOM, New York, NY, Jun. 2002, vol. 1, pp. 322-331.
• 26: Y. Ganjali, S. Bhattacharyya, and C. Diot, "Limiting the impact of failures on network performance," Sprint ATL Tech. Res. Rep. RR04- ATL-020666, 2003.
• 27: P. Tobias and D. Trindade, Applied Reliability, 2nd ed. London, U.K.: Chapman Hall/CRC, 1995.
• 28: L. Adamic, "Zipf, power-laws and Pareto: A ranking tutorial," Xerox Palo Alto Research Center, Palo Alto, CA [Online]. Available: http:// ginger.hpl.hp.com/shl/papers/ranking/ranking.html
• 29: Georgos Siganos , Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, Power laws and the AS-level internet topology, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.514-524, August 2003 [doi>10.1109/TNET.2003.815300]
• 30: Anja Feldmann , Anna C. Gilbert , Polly Huang , Walter Willinger, Dynamics of IP traffic: a study of the role of variability and the impact of control, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.301-313, August 30-September 03, 1999, Cambridge, Massachusetts, United States

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

          Nouns: IP

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance

Keywords:
failure analysis, intermediate system to intermediate system (IS-IS) protocol, link failures, modeling, routing