© 1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Transactions on Networking
Volume 6 Number 5, October 1998

Table of Contents for this issue

Complete paper in PDF format

Internet Routing Instability

Craig Labovitz, Student Member, IEEE, G. Robert Malan, Student Member, IEEE, and Farnam Jahanian, Member, IEEE

Page 515.

Abstract:

This paper examines the network interdomain routing information exchanged between backbone service providers at the major U.S. public Internet exchange points. Internet routing instability, or the rapid fluctuation of network reachability information, is an important problem currently facing the Internet engineering community. High levels of network instability can lead to packet loss, increased network latency and time to convergence. At the extreme, high levels of routing instability have led to the loss of internal connectivity in wide-area, national networks. In this paper, we describe several unexpected trends in routing instability, and examine a number of anomalies and pathologies observed in the exchange of inter-domain routing information. The analysis in this paper is based on data collected from BGP routing messages generated by border routers at five of the Internet core's public exchange points during a nine month period. We show that the volume of these routing updates is several orders of magnitude more than expected and that the majority of this routing information is redundant, or pathological. Furthermore, our analysis reveals several unexpected trends and ill-behaved systematic properties in Internet routing. We finally posit a number of explanations for these anomalies and evaluate their potential impact on the Internet infrastructure.

References

  1. P. Bloomfield, Fourier Analysis of Time Series: An Introduction.New York: Wiley, 1976.
  2. H.-W. Braun, P. S. Ford, and Y. Rekhter, "CIDR and the Evolution of the Internet," in Proc. INET'93, SDSC Rep. GA-A21364, republished in ConneXions, Sept. 1993 (InterOp93 version).
  3. B. Chinoy, "Dynamics of Internet routing information," in Proc. ACM SIGCOMM'93, Sept. 1993, pp. 45-52.
  4. D. Estrin, Y. Rekhter, and S. Hotz, "A scalable inter-domain routing architecture," in Proc. ACM SIGCOMM'92, Baltimore, MD, Aug. 1992, pp. 40-52.
  5. S. Floyd and V. Jacobson, "The synchronization of periodic routing messages," IEEE/ACM Trans Networking, vol. 2, pp. 122-136, Apr. 1994.
  6. R. Govindan and A. Reddy, "An analysis of inter-domain topology and route stability," in Proc. IEEE INFOCOM '97, Kobe, Japan, Apr. 1997.
  7. C. Hedrick, "An introduction to IGRP," Center for Computer and Information Services, Laboratory for Computer Science Research, Rutgers Univ., Piscataway, NJ, Aug. 1991.
  8. B. Halabi, Internet Routing Architectures.Indianapolis, IN: New Riders, 1997.
  9. J. Honig, D. Katz, M. Mathis, Y. Rekhter, and J. Yu, "Application of the border gateway protocol in the Internet," RFC-1164, June 1990.
  10. D. O'Leary, Cisco Systems, Inc., private communication, Jan. 1997.
  11. K. Lougheed and Y. Rekhter, "A border gateway protocol (BGP)," RFC-1163, June 1990.
  12. B. Metcalf, "Predicting the Internet's catastrophic collapse and ghost sites galore in 1996," InfoWorld, vol. 127, no. 50, p. 143, Dec. 1995.
  13. J. Moy, "OSPF version 2," RFC-1247, July 1991.
  14. H. Nielsen, J. Gettys, A. Baird-Smith, E. Prud'hommeaux, H. Lie, and C. Lilley, "Network performance effects of HTTP/1.1, CSS1, and PNG," in Proc. ACM SIGCOMM'97, Cannes, France, Aug. 1997.
  15. V. Paxson, "End-to-end routing behavior in the Internet," in Proc. ACM SIGCOMM'96, Stanford, CA, Aug. 1996.
  16. Y. Rekhter, "Scalable support for multi-homed multi-provider connectivity," NANOG, Ann Arbor, MI, Oct. 1996.
  17. Y. Rekhter and C. Topolcic, "Exchanging routing information across provider boundaries in the CIDR environment," RFC-1520, Sept. 1993.
  18. K. Varadhan, R. Govindan, and D. Estrin, "Persistent routing oscillations in inter-domain routing," USC/ISI, available at the Routing Arbiter project's home page at USC/ISI.
  19. C. Villamizer, R. Chandra, and R. Govindan, "Draft-ietf-idr-route-dampen-00-preview," Internet Engineering Task Force Draft, July 21, 1995.
  20. C. Villamizer, "TCP response under loss conditions," NANOG Presentation, San Francisco, CA, Feb. 1997.
  21. M. Yajnik, J. Kurose, and D. Towsley, "Packet loss correlation in the MBone multicast network," in Proc. IEEE Global Internet Conf., London, England, Nov. 1996.