Experience in black-box OSPF measurement

ABSTRACT

OSPF (Open Shortest Path First) is a widely used intra-domain routing protocol in IP networks. Internal processing delays in OSPF implementations impact the speed at which updates propagate in the network, the load on individual routers, and the time needed for both intra-domain and inter-domain routing to reconverge following an internal topology or a configuration change. An OSPF user, such as an Internet Service Provider, typically has no access to the software implementation, and no way to estimate these delays directly. In this paper, we present black-box methods (i.e., measurements that rely only on external observations) for estimating and trending delays for key internal tasks in OSPF: processing Link State Advertisements (LSAs), performing Shortest Path First calculations, updating the Forwarding Information Base, and flooding LSAs. Corresponding measurements are reported for production routers from Cisco Systems. To help validate the methodology, black-box and white-box (i.e., measurements that rely on internal instrumentation) are reported for a open source OSPF implementation, GateD.

REFERENCES

• 1: John Moy, "OSPF Version 2," Request for Comments 2328, April 1998.
• 2: John T. Moy, OSPF: Anatomy of an Internet Routing Protocol, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 3: Anindya Basu , Jon Riecke, Stability issues in OSPF routing, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.225-236, August 2001, San Diego, California, United States
• 4: A. S. Maunder and G. Choudhury, "Explicit Marking and Prioritized Treatment of Specific IGP Packets for IGP Convergence and Improved Network Stability and Scalability," Internet Draft draftietf-scalability-00.txt, work in progress, March 2001.
• 5: "Toward milli-second IGP convergence," Internet Draft draftalaettinoglu-isis-convergence-00.txt, work in progress, November 2000.
• 6: J. H. Dunn and C. E. Martin, "Framework for Router Benchmarking," Internet Draft draft-ietf-bmwg-rtr-framework-00.txt, work in progress, July 2000.
• 7: "http://www.cisco.com,".
• 8: OSPF complete implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 9: Don Libes , Tim O'Reilly , Tim C'Reilly, Exploring Expect, O'Reilly & Associates, Inc., Sebastopol, CA, 1996
• 10: Y. Rekhter and T. Li, "A Border Gateway Protocol 4 (BGP-4): RFC1771, March 1995.
• 11: R. Callon, "Use of OSI IS-IS for Routing in TCP/IP and Dual Enviornments," RFC1195, December 1990.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol verification

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Measurement, Performance

Keywords:
OSPF, SPF calculation, black-box measurements, routing