A case study of OSPF behavior in a large enterprise network

ABSTRACT

Open Shortest Path First (OSPF) is widely deployed in IP networks to manage intra-domain routing. OSPF is a link-state protocol, in which routers reliably flood "Link State Advertisements" (LSAs), enabling each to build a consistent, global view of the routing topology. Reliable performance hinges on routing stability, yet the behavior of large operational OSPF networks is not well understood. In this paper, we provide a case study on the eharacteristics and dynamics of LSA traffic for a large enterprise network. This network consists of several hundred routers, distributed in tens of OSPF areas, and connected by LANs and private lines. For this network, we focus on LSA traffic and analyze: (a) the class of LSAs triggered by OSPF's soft-state refresh, (b) the class of LSAs triggered by events that change the status of the network, and (c) a class of "duplicate" LSAs received due to redundancy in OSPF's reliable LSA flooding mechanism. We derive the baseline rate of refresh-triggered LSAs automatically from network configuration information. We also investigate finer time scale statistical properties of this traffic, including burstiness, periodicity, and synchronization. We discuss root causes of event-triggered and duplicate LSA traffic, as well as steps identified to reduce this traffic (e.g., localizing a failing router or changing the OSPF configuration).

References

1. Christian Huitema, Routing in the Internet, Prentice Hail, 2000.
2. Denise Pappalrdo, "Can One Rogue Switch Buckle AT&T's Network?," Network World Fusion, February 2001.
3. Anindya Basu and Jon G. Riecke, "Stability Issues in OSPF Routing," in Proc. ACM SIGCOMM, August 2001.
4. Aman Shaikh, Mukul Goyal, Albert Greenberg, Raju Rajan, and K.K. Ramakrishnan, "An OPSF Topology Server: Design and Evaluation," IEEE J. Selected Areas in Communications, vol. 20, no. 4, May 2002.
5. Aman Shaikh and Albert Greenberg, "Experience in Black-box OSPF Measurement," in Proc. ACM SIGCOMM lnternet Measurement Workshop (IMW), November 2001.
6. Craig Labovitz, Abha Ahuja, and Farnam Jahanian, "Experimental Study of Internet Stability and Wide-Area Network Failures," in Proc. International Symposium on Fault-Tolerant Computing, June 1999.
7. Cengiz Alaettinoglu, Van Jacobson, and Haobo Yu, "Toward Milli-Second IGP Convergence," Expired Internet Draft draftalaettinoglu-isis-convergence-00.txt, November 2000.
8. Cengiz Alaettinoglu and Steve Casner, "ISIS Routing on the Qwest Backbone: a Recipe for Subsecond ISIS Convergence," Presentation at NANOG 24, http://www.nanog.org/mtg-0202, February 2002.
9. Craig Labovitz, Rob Malan, and Farnam Jahanian, "Internet Routing Stability," IEEE/ACM Trans. Networking, vol. 6, no. 5, pp. 515--558, October 1998.
10. Craig Labovitz, Rob Malan, and Farnam Jahanian, "Origins of Pathological Internet Routing Instability," in Proc. IEEE INFOCOM, March 1999.
11. John T. Moy, OSPF: Anatomy of an Internet Routing Protocol, Addison-Wesley, January 1998.
12. John T. Moy, "OSPF Version 2," Request for Comments 2328, April 1998.
13. Anja Feldmann and Jennifer Rexford, "IP Network Configuration for Intra-domain Traffic Engineering," IEEE Network Magazine, September 2001.
14. "Cisco Systems," http://www.cisco.com.
15. "OSPF LSA Group Pacing," htttp://www.cisco.com/univercd/cc/td/doc/product/soflware/ios 113ed/113a_2/58cfeats/osp fpace.htm.
16. Sally Floyd and Van Jacobson, "The Synch_onization of Periodic Routing Messages," IEEE/ACM Trans. Networking, vol. 2, no. 2, pp. 122--136, 1994.
17. Ashok Erramilli and Leonard J. Forys, "Oscillations and Chaos in a Flow Model of a Switching System," IEEE J. Selected Areas in Communications, vol. 9, no. 2, pp. 171--178, February 1991.
18. M. Bennett, M. E Schatz, H. Rockwood, and K. Wiesenfed, "Huygens' Clocks," Proceedings (A) of the Royal Society, 2001.

Index Terms

• Networks

  • Network properties

    • Network structure

  • Network protocols

    • Network layer protocols

      • Routing protocols

    • Transport protocols

  • Network services

    • Network management

  • Network types

    • Public Internet