RFC 4063

RFC 4063: Considerations When Using Basic OSPF Convergence Benchmarks 🎀

okay bestie, this one is an Informational RFC from April 2005 💖 It was written by V. Manral (SiNett Corp.), R. White (Cisco Systems), and A. Shaikh (AT&T Labs (Research)) 👑. It came out of the Network Working Group ✨ It doesn't list any RFCs it obsoletes or updates, so it's standing on its own 🦋

Status of This Memo ✨

This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.

so basically it's info, not a standard 🫶 and anyone can share it, no cap

Copyright Notice 💅

Copyright (C) The Internet Society (2005).

Abstract 🌸

this doc is about how well you can test single router control plane convergence, specifically for OSPF (Open Shortest First) 🧚 there are two big parts. the first looks at the perks and limits of specific OSPF convergence tests. the second is about the more general pitfalls you can fall into when you test routing protocol convergence 🙈

1. Introduction 💖

okay so there's a growing interest in testing single router control plane convergence for routing protocols ✨ lots of people are looking at testing methods that can tell you how long a network takes to converge after different network events happen. the framework you run a convergence test in matters a LOT when you try to apply the results 😭 it can majorly change the numbers, because deciding when a network counts as converged, which parts of the router's operation get included in the testing, and other stuff like that will totally shape the performance a routing protocol seems to have 💅

this document goes into detail about the benefits and pitfalls of the tests described in [BENCHMARK] 💜 it also explains how these measurements can help providers and the research community 🌈

NOTE: In this document, the word "convergence" refers to single router control plane convergence [TERM].

2. Advantages of Such Measurement 🍓

• to be able to compare iterations of a protocol implementation 🔥 it's often useful to compare two versions of the same implementation so you can see where improvements were made and where more improvements could go 👑
• to understand how a particular implementation on a particular device will perform, given a set of parameters (network conditions) 🦋 say you're trying to figure out how much processing power (device size) you need in a certain spot in a network. you could emulate the conditions that will exist at that point in the network and use the test described to measure several different routers. the results can give you one possible data point for making a smart decision 🧠

if the device being tested is going to be deployed in a running network, using routes taken from the network where the equipment will go, instead of some generated topology, the results will be closer to the device's real performance 💖 be sure to emulate, or take routes from, the actual spot in the network where the device will be (or would be) deployed 📍 for example, one set of routes might come from an ABR, one set from an area 0 only router, various sets from stub areas, and another set from various normal areas, etc. ✨

• to measure the performance of an OSPF implementation across a wide variety of scenarios 🌸
• to be used as parameters in OSPF simulations by researchers 🧚 some kinds of research may need to measure the individual delays of each parameter within an OSPF implementation. those delays can be measured using the methods defined in [BENCHMARK] 🔬
• to help optimize certain configurable parameters 💅 operators sometimes benefit from knowing the delay needed for individual tasks, so they can optimize resource usage in the network. for example, if the processing time on a router turns out to be x seconds, figuring out the rate at which to flood LSAs to that router would help so you don't overload the network 🫶

3. Assumptions Made and Limitations of Such Measurements 🙈

• the interactions of convergence and forwarding. testing is restricted to events happening within the control plane 🧠 forwarding performance is the main focus of [INTERCONNECT], and it's expected to be handled in work that follows from [FIB-TERM] 💜
• Duplicate LSAs are Acknowledged Immediately. a few tests rely on the property that duplicate LSA Acknowledgements aren't delayed and are done right away 😭 but if an implementation doesn't acknowledge duplicate LSAs immediately on receipt, the testing methods presented in [BENCHMARK] could give inaccurate measurements 💀
• it's assumed that SPF is non-preemptive 🔥 if SPF is implemented so that it can (and will) be preempted, the SPF measurements taken in [BENCHMARK] would include the times when the SPF process isn't running, which gives inaccurate measurements 😬 ([BENCHMARK] measures the total time taken for SPF to run, not the amount of time SPF actually spends on the device's processor.)
• some implementations may be multithreaded or use a multiprocess/multirouter model of OSPF 🌈 if any of the assumptions made during measurement get violated in that kind of model, the measurements could be inaccurate 🙃
• the measurements resulting from the tests in [BENCHMARK] may not provide the information you need to deploy a device in a large-scale network 🌍 the tests focus on individual components of an OSPF implementation's performance, and it may be hard to combine those measurements in a way that accurately shows a device's performance in a large-scale network 🥺 further research is needed in this area ✨
• the measurements described in [BENCHMARK] should be used with great care when comparing two different OSPF implementations from two different vendors 👑 for instance, there are lots of factors other than convergence speed to consider when comparing different vendors' products 💅 one difficulty is lining up the resources available on one device with the resources available on another 🎀

4. Observations on the Tests Described in [BENCHMARK] 🔍

some observations recorded while implementing the tests described in [BENCHMARK] are noted in this section 📝

4.1. Measuring the SPF Processing Time Externally 🧪

this is the most difficult test to perform 😭 measuring the time needed for an SPF calculation externally is hard because the amount of time between the first LSA that indicates a topology change and the duplicate LSA is critical 💜 if the duplicate LSA is sent too quickly, it may be received before the device being tested actually starts running SPF on the network change information 💀 if the delay between the two LSAs is too long, the device may finish SPF processing before it receives the duplicate LSA 🫠 it's important to closely investigate any delays between receiving an LSA and starting an SPF calculation on the tested device 🔎 you might need multiple tests with various delays to figure out which delay to use so you can measure the SPF calculation time accurately 🎯

some implementations may force two intervals between successive SPF calculations: the SPF hold time and the SPF delay 🌸 if an SPF hold time exists, it should be subtracted from the total SPF execution time 💅 if an SPF delay exists, it should be noted in the test results 📌

4.2. Noise in the Measurement Device 🔊

the device where measurements are taken (not the device being tested) also adds noise to the results 🙈 this shows up mainly as delay in packet processing and measurement output 💖 the biggest source of noise is usually the delay between the measuring device receiving packets and the device's output receiving information about those packets (which is where the event can be measured) 😤 here are some steps you can take to reduce this sampling noise:

• taking more samples will generally help the tester figure out what's noise and remove it from the results 🧠 this applies to the DUT as well 🫶
• try to take the time-stamp for a packet as early as possible 🕰️ depending on the operating system on the box, you can instrument the kernel to take the time-stamp when the interrupt is processed ⚡ this doesn't get rid of the noise completely, but it at least reduces it 🌷
• keep the measurement box as lightly loaded as possible 🍃 this applies to the DUT as well 💜
• having an estimate of the noise can also be useful 📊

the DUT also adds noise to the measurement too 💀

4.3. Gaining an Understanding of the Implementation Improves Measurements 🧚

the tester will (generally) not have access to internal information about the OSPF implementation being tested using [BENCHMARK] 🙃 but the more thoroughly the tester knows the implementation, the more accurate the test results will be 🎯 for instance, in some implementations, routes can be installed in local routing tables while SPF is still being calculated, which can dramatically affect how long the SPF calculation takes 😱

4.4. Gaining an Understanding of the Tests Improves Measurements 🌈

one way to get familiar with the tests described in [BENCHMARK] is to run them on an OSPF implementation where all the internal details are available 🔥 there's no guarantee that any two implementations will be similar, but this will give you a better understanding of the tests themselves 💖

5. LSA and Destination Mix 💅

okay so in a lot of OSPF benchmark tests, you need a generator that injects a bunch of LSAs 🦋 and there are a few different things you can vary about them:

• The number of destinations represented by the injected LSAs 🌸 Each destination is one reachable IP network. These end up as leaf nodes on the shortest path tree. The main performance hit should come from how long it takes to put destinations into the local routing table, plus the memory needed to store all that data. 💾
• The types of LSAs injected 🎀 There are a few LSA types that could show up depending on the situation. Inside an area, a router will probably receive types 1, 2, 3, 4, and 5. In a not-so-stubby area, though, type-7 LSAs take the place of the type-5 LSAs you'd otherwise get. Notes like this matter a lot in test results, so write them down! ✍️
• The number of LSAs injected 🔢 Within whatever set you inject, how many of each type you send matters too. This affects how well the shortest path algorithm handles a big pile of nodes and large shortest path first trees. 🌳
• The order of LSA injection 🔀 The order should not favor any particular data structure that the device under test uses to store its LSA database. Here's the tea: AS-External LSAs have AS-wide flooding scope, so any type-5 LSA that gets originated is flooded to all neighbors right away. The type-4 LSA is different. It announces the ASBR as a border router, and it gets originated in an area at SPF time, by the ABRs sitting on the edge of the area where the ASBR lives. If SPF isn't scheduled immediately on those ABRs, the type-4 LSA ends up going out after the type-5 LSAs have already reached a router in the adjacent area. So routes to the external destinations aren't added to the routers in the other areas right away. When routers that already have the type 5s finally get the type-4 LSA, all the external routes get added to the tree at the same time. That can give different results from a router that gets a type 4 saying "hey, there's a border router," and then gets the type 5s from that border router. Wild, right? 🤯

The ordering can be changed across different tests to show how efficiently the DUT stores things. Any ordering changes should be noted in the test results. 📝

6. Tree Shape and the SPF Algorithm 🌳

okay this section is my favorite, it's giving algorithm nerd energy 🤓✨

The complexity of Dijkstra's algorithm depends on the data structure used to store vertices along with their current minimum distances from the source. The simplest option is a list of the vertices that are currently reachable from the source. With a simple list of vertices, finding the minimum cost vertex takes O(size of the list). There are O(n) such operations if we assume every vertex is eventually reachable from the source. After the minimum cost vertex is found, the algorithm goes through all the edges of that vertex and updates the cost of the other vertices. With an adjacency list representation, doing this step over all the vertices takes O(E) time, where E is the number of edges in the graph. So the overall running time looks like this:

O(sum(i:1, n)(size(list at level i) + E).

So everything boils down to the size(list at level i). 🫶

If the graph is linear,

   root
    |
    1
    |
    2
    |
    3
    |
    4
    |
    5
    |
    6

and the source is a vertex on one end, then size(list at level i) = 1 for all i. Moreover, E = n - 1. So the running time is O(n). Simple and clean, bestie 💖

If the graph is a balanced binary tree,

    root
   /    \
  1      2
 / \    / \
3   4  5   6

size(list at level i) is a little more complicated. First, it goes up by 1 at each level up to a certain number, and then it goes back down by 1. If we assume the tree is a complete tree (like the one shown above) with k levels (1 to k), then size(list) goes like this: 1, 2, 3,

Then the number of edges E is still n - 1. It turns out the run-time for a tree like this is O(n^2). 😭

If the graph is a complete graph (a fully-connected mesh), then size(list at level i) = n - i. The number of edges E = O(n^2). Therefore, the run-time is O(n^2). Mesh networks really be out here making things hard 🕸️

Therefore, how well the shortest path first algorithm computes the best paths through the network depends on how the tree is built. The best practice is to make any emulated network look as much like a real network as possible. Pay special attention to the tree depth, how meshy the network is, the number of stub links versus transit links, and the number of connections and nodes to process at each level of the original tree. 🌿

7. Topology Generation 🧚

As networks get bigger, it gets harder and harder to actually build a large-scale network to test the properties of routing protocols and their implementations. 😩 That's why network emulators exist. They provide emulated topologies that can be advertised to a device under varying conditions. Route generators are usually one of three things: a specialized device, a piece of software that runs on a router, or a process running on another operating system, like Linux or another flavor of Unix.

Some of the characteristics this device should have are the following:

• The ability to connect to several devices using both point-to-point and broadcast high-speed media. 🔌 Point-to-point links can be emulated with high-speed Ethernet, as long as there's no hub or other device between the DUT and the route generator, and the link is configured as a point-to-point link within OSPF [BROADCAST-P2P].
• The ability to create a set of LSAs that look like a logical, realistic topology. 🗺️ For instance, the generator should be able to mix the number of point-to-point and broadcast links within the emulated topology, and inject varying numbers of externally reachable destinations.
• The ability to withdraw and add routing information into and from the emulated topology in order to emulate flapping links. 🎢
• The ability to randomly order the LSAs representing the emulated topology as they are advertised. 🎲
• The ability to log or otherwise measure the time between packets transmitted and received. ⏱️
• The ability to change the rate at which OSPF LSAs are transmitted. 🏎️
• The generator and the collector should be fast enough that they are not bottlenecks. 🚀 The devices should also have a measurement granularity at least as small as the granularity you want in the test results.

8. Security Considerations 🔐

⚠️ okay bestie, listen up. This one is short but it's serious. This document does not modify the underlying security considerations in [OSPF]. So go read [OSPF] for the real security picture, because this doc doesn't change any of it. 🫶

9. Acknowledgements 🙏

Thanks to Howard Berkowitz (hcb@clark.net) and the rest of the BGP benchmarking team for their support. Thanks also to Kevin Dubray (kdubray@juniper.net), who realized the need for this document. You're the real MVPs 👑

10. Normative References 📚

• [BENCHMARK] Manral, V., White, R., and A. Shaikh, "Benchmarking Basic OSPF Single Router Control Plane Convergence", RFC 4061, April 2005.
• [TERM] Manral, V., White, R., and A. Shaikh, "OSPF Benchmarking Terminology and Concepts", RFC 4062, April 2005.
• [OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.

11. Informative References 📖

• [INTERCONNECT] Bradner, S. and J. McQuaid, "Benchmarking Methodology for Network Interconnect Devices", RFC 2544, March 1999.
• [FIB-TERM] Trotter, G., "Terminology for Forwarding Information Base (FIB) based Router Performance", RFC 3222, December 2001.
• [BROADCAST-P2P] Shen, Naiming, et al., "Point-to-point operation over LAN in link-state routing protocols", Work in Progress, August, 2003.

Authors' Addresses ✨

Vishwas Manral
SiNett Corp,
Ground Floor,
Embassy Icon Annexe,
2/1, Infantry Road,
Bangalore, India

EMail: vishwas@sinett.com


Russ White
Cisco Systems, Inc.
7025 Kit Creek Rd.
Research Triangle Park, NC 27709

EMail: riw@cisco.com


Aman Shaikh
AT&T Labs (Research)
180 Park Av, PO Box 971
Florham Park, NJ 07932

EMail: ashaikh@research.att.com

Full Copyright Statement 🌈

Copyright (C) The Internet Society (2005).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property 🦋

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document, or the extent to which any license under such rights might or might not be available. Nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat, and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification, can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.

Acknowledgement 💖

Funding for the RFC Editor function is currently provided by the Internet Society. 🎀