Routing Convergence
When considering routing convergence with forwarding routing protocols, we must first highlight that a networking device is tasked with two planes of operation – the control plane and the data plane. The job of the data plane is to switch traffic across the router’s interfaces as fast as possible, i.e., the moving of the packets. The control plane has the more complex operation of putting together and creating the controls so the data plane can operate efficiently. How these two planes interact will affect network convergence time.
The network’s control plane finds the best path for routing convergence from any source to any network destination. For quick convergence routing, it must react quickly and be dynamic to changes in the network, both of the LAN and for WAN.
For pre-information, you may find the following posts helpful:
Convergence Routing |
|
- A key point: Video on IP Routing and routing convergence.
In this video, we will address routing convergence, also known as convergence routing. We know we have Layer 2 switches that create Ethernet. So all endpoints physically connect to a Layer 2 switch. And if you are on a single LAN with one large VLAN, you are ready with this setup as switches work out of the box, making decisions based on Layer 2 MAC addresses. However, if you need to go beyond, we need Routing, and to understand how to optimize your networking, you need to understand routing convergence.
- A key point: Convergence time definition.
I found two similar definitions of convergence time:
“Convergence is the amount of time ( and thus packet loss ) after a failure in the network and before the network settles into a steady state” Also, ” Convergence is the amount of time ( and thus packet loss) after a failure in the network and before the network responds to the failure.”
The difference between the two convergence time definitions is subtle but essential – steady-state vs. just responding. The control plane and its reaction to topology changes can be separated into four parts below. Each area must be addressed individually, as leaving one area out results in slow network convergence time and application time-out.
- A key point: Back to basic with IP routing
A router’s primary role is moving an IP packet from one network to another. Routers select the best loop-free path in a network that forwards a packet to its destination IP address. A router learns about nonattached networks through two means. We can either learn via static configuration or through dynamic IP routing protocols. Both static and dynamic are examples of routing protocols.
With dynamic IP routing protocols, we can handle network topology changes dynamically. Here we can distribute network topology information between routers in the network. When there is a change in the network topology, the dynamic routing protocol provides updates without intervention when a topology change occurs.
On the other hand, we have IP routing to static routes, which do not accommodate topology changes very well and can be a burden depending on the network size. However, static routing is a viable solution for minimal networks with no modifications.
Convergence Routing and Network Convergence Time
Network convergence connects multiple computer systems, networks, or components to establish communication and efficient data transfer. However, it can be a slow process, depending on the size and complexity of the network, the amount of data that needs to be transferred, and the speed of the underlying technologies.
For networks to converge, all of the components must interact with each other and establish rules for data transfer. This process requires that the various components communicate with each other and usually involves exchanging configuration data to ensure that all components use the same protocols.
Network convergence is also dependent on the speed of the underlying technologies.
To speed up convergence, administrators should use the latest technologies, minimize the amount of data that needs to be transferred, and ensure that all components are properly configured to be compatible. By following these steps, network convergence can be made faster and more efficient.
- Example: OSPF
To put it simply, convergence or routing convergence is a state in which a set of routers in a network share the same topological information. For example, we have ten routers in one OSFP area. OSPF is an example of a fast-converging routing protocol. A network of a few OSPF routers can converge in seconds.
The routers within the OSPF area in the network collect the topology information from one another through the routing protocol. Depending on the routing protocol used to collect the information, the routers in the same network should have identical copies of routing information.
Different routing protocols will have different convergence time. The time the routers take to reach convergence after a change in topology is termed convergence time. Fast network convergence and fast failover are critical factors in network performance. Before we get into the details of routing convergence, let us recap how networking works.
Unlike IS-IS, OSPF has fewer “knobs” for optimizing convergence. This is probably because IS-IS is being developed and supported by a separate team geared towards ISPs, where fast convergence is a competitive advantage.
Forwarding Paradigms
We have bridging routing and switching with data and the control plane. So we need to get packets across a network, which is easy if we have a single cable. You need to find the node’s address, and small and non-IP protocols would use a broadcast. When devices in the middle break this path, we can use source routing, path-based forwarding, and hop-by-hop address-based forwarding based solely on the destination address.
When protocols like IP came to play, hop-by-hop destination-based forwarding became the most popular; this is how IP forwarding works. Everyone in the path makes independent forwarding decisions. Each device looks at the destination address, examines its lookup tables, and decides where to send the packet.
Finding paths across the network
How do we find a path across the network? We know there are three ways to get packets across the network – source routing, path-based forwarding, and hop-by-hop destination-based forwarding. So we need some way to populate the forwarding tables. You need to know how your neighbors are and who your endpoints are. This can be static routing but is more than likely a routing protocol. Routing protocols have to solve and describe the routing convergence on the network at a high level.
So when we are up and running, events can happen to the topology that forces or makes the routing protocols react and perform a convergence routing state. For example, we have a link failure, and the topology has changed, impacting our forwarding information. So we must propagate the information and adjust the path information after the topology change. We know these convergence routing states to be Detect, Describe, Switch, and Find.
Rouitng Convergence | Convergence |
To better understand routing convergence, I would like to share the network convergence time for each routing protocol before diving into each step. The times displayed below are from a Cisco Live session based on real-world case studies and field research. From each of the convergence routing steps described above, we are separating them into the following fields – Detect, Describe, Find Alternative, and Total Time.
Routing Protocol | RIP | OSPF | EIGRP |
Detect | <1 second-best, 105 seconds average | <1 second-best, 20 seconds average | <1 second-best, 15 seconds average.30 seconds worst |
Describe | 15 seconds average, 30 seconds worst | 1 second-best, 5 seconds average. | 2 seconds |
Find Alternative | 15 seconds average, 30 seconds worst | 1-second average. | *** <500ms per query hop average Assume a 2-second average |
Total Time | Best Average Case: 31 seconds Average Case: 135 seconds Worse Case: 179 seconds | Best Average Case: 2 to 3 seconds Average Case: 25 seconds Worse Case: 45 seconds | Best Average Case: <1 second Average Case: 20 seconds Worse Case: 35 seconds |
*** The alternate route is found before the described phase due to the feasible successor design with EIGRP path selection.
Convergence Routing
Convergence routing: EIGPR
EIGRP is the fastest but only fractional. EIGRP has a pre-built loop-free path known as a feasible successor. The FS route has a higher metric than the successor, making it a backup route to the successor route. The effect of a pre-computed backup route on convergence is that EIGRP can react locally to a change in the network topology; nowadays, this is usually done in the FIB. EIGRP would have to query for the alternative route without a feasible successor, increasing convergence time.
You can, however, have Loop Free Alternative ( LFA ) for OSPF, which can have an alternate path pre-computed. Still, they can only work with specific typologies and don’t guarantee against micro-loops ( EIGRP guarantees against micro-loops).
TCP Congestion control
Ask yourself, is < 1-second convergence fast enough for today’s applications? Indeed, the answer would be yes for some non-critical applications that work on TCP. TCP has built-in backoff algorithms that can deal with packet loss by re-transmitting to recover lost segments. But non-bulk data applications like Video and VOIP have stricter rules and require fast convergence and minimal packet loss. For example, a 5-second delay in routing protocol convergence could mean several hundreds of voice calls being dropped. A 50-second delay for a Gigabit Ethernet link implies about 6.25 GB of information lost.
Adding resilience
To add resilience to a network, you can aim to make the network redundant. When you add redundancy, you are betting that outages of the original path and the backup path will not co-occur and that the primary path does not fate share with the backup path ( they do not share common underlying infrastructure, i.e., physical conducts or power ).
There needs to be a limit on the number of links you add to make your network redundant, and adding 50 extra links does not make your network 50 times more redundant. It does the opposite! The control plane is tasked with finding the best path and must react to modifications in the network as quickly as possible.
However, every additional link you add slows down the convergence of the router’s control plane as there is additional information to compute, resulting in longer convergence times. The correct number of backup links is a trade-off between redundancy versus availability. The optimal level of redundancy between two points should be two or three links. The fourth link would make the network converge slower.
Routing Convergence and Routing Protocol Algorithms
Routing protocol algorithms can be tweaked to exponentially back off and deal with bulk information. However, no matter how many timers you do, the more information in the routing databases results in longer convergence times. The primary way to reduce network convergence is to reduce the size of your routing tables by accepting just a default route, creating a flooding boundary domain, or some other configuration method.
For example, a common approach in OSPF to reduce the size of routing tables and flooding boundaries is to create OSPF stub areas. OSPF stub areas limit the amount of information in the area. For example, EIGRP limits the flooding query domain by creating EIGRP stub routers and intelligently designing aggregation points. Now let us revisit the components of routing convergence:
Routing Convergence Step | Routing Convergence Details |
Step 1 | Failure detection |
Step 2 | Failure propagation ( flooding, etc.) IGP Reaction |
Step 3 | Topology/Routing calculation. IGP Reaction. |
Step 4 | Update the routing and forwarding table ( RIB & FIB) |
Stage 1: Failure Detection
The first and foremost problem facing the control plane is quickly detecting topology changes. Detecting the failure is the most critical and challenging part of network convergence. It can occur at different layers of the OSI stack – Physical Layers ( Layer 1), Data Link Layer ( Layer 2 ), Network Layer ( Layer 3 ), and Application layer ( Layer 7 ). There are many types of techniques used to detect link failures, but they all generally come down to two basic types:
- Event-Driven notification – loss of carrier or when one network element detects a failure and notifies the other network elements.
- Polling-driven notification – generally HELLO protocols that test the path for reachability, such as Bidirectional Forwarding Detection ( BFD ). Event-driven notifications are always preferred over polling-driven ones as the latter have to wait for three polls before declaring a path down. However, there are some cases when you have multiple Layer devices in the path, and HELLO polling systems are the only method that can be used to detect a failure.
Layer 1 failure detection
Layer 1: Ethernet mechanisms like auto-negotiation ( 1 GigE ) and link fault signaling ( 10 GigE 802.3ae/ 40 GigE 802.3ba ) can signal local failures to the remote end.
However, the challenge is getting the signal across an optical cloud, as relaying the fault information to the other end is impossible. When there is a “bump” in the Layer 1 link, it is not always possible for the remote end to detect the failure. In this case, the link fault signaling from Ethernet would get lost in the service provider’s network.
The actual link-down / interface-down event detection is hardware-dependent. Older platforms, such as the 6704 line cards for the Catalyst 6500, used a per-port polling mechanism, resulting in a 1 sec detect link failure period. More recent Nexus switches and the latest Catalyst 5600 line cards have an interrupt-driven notification mechanism resulting in high-speed and predictable link failure detection.
Layer 2 failure detection
Layer 2: The layer 2 detection mechanism will kick in if the Layer 1 mechanism does not. Unidirectional Link Detection ( UDLD ) is a Cisco proprietary lightweight Layer 2 failure detection protocol designed for detecting one-way connections due to physical or soft failure and miss-wirings.
- A key point: UDLD is a slow protocol
UDLD is a reasonably slow protocol that uses an average of 15 seconds for message interval and 21 seconds for detection. Its time period has raised question marks to its use in today’s data centers. However, the chances of miswirings are minimal; Layer 1 mechanisms always communicate unidirectional physical failure, and STP Bridge Assurance takes care of soft failures in either direction.
STP Bridge assurance turns STP into a bidirectional protocol and ensures that the spanning tree never fails open and only fails to close. Failing open means that if a switch does not hear from its neighbor, it immediately starts forwarding on originally blocked ports, causing network havoc.
Layer 3 failure detection
Layer 3: In some cases, failure detection has to reply to HELLO protocols at Layer 3 and is needed when there are intermediate Layer 2 hops over Layer links and when you have concerns over uni-direction failures on point-to-point physical links.
All Layer 3 protocols use HELLOs to maintain neighbor adjacency and a DEAD time to declare a neighbor dead. These timers can be tuned for faster convergence. However, it is generally not recommended due to the increase in CPU utilization causing false positives and the challenges ISSU and SSO face. They are enabling Bidirectional Forwarding Detection ( BFD ) as the Layer 3 detection mechanism is strongly recommended over aggressive protocol times and using BFD for all protocols. Bidirectional Forwarding Detection ( BFD ) is a lightweight hello protocol for sub-second Layer 3 failure detection. It can run over multiple transport protocols such as MPLS, THRILL, IPv6, and IPv4, making it the preferred Layer 3 failure detection method.
Stage 2: Routing convergence and failure propagation
When a change occurs in the network topology, it must be registered with the local router and transmitted throughout the rest of the network. The transmission of the change information will be carried out differently for Link-State and Distance Vector protocols. Link state protocols must flood information to every device in the network, and the distance vector must process the topology change at every hop through the network. The processing of information at every hop may make you conclude that link-state protocols will always converge more quickly than path-vector protocols, but this is not the case. EIGRP, due to its pre-computed backup path, will converge more quickly than any link-state protocol.
To propagate topology changes as quickly as possible, OSPF ( Link state ) can group changes into a few LSA while slowing down the rate at which information is flooded, i.e., do not flood on every change. This is accomplished with link-state flood timer tuning combined with exponential backoff systems, for example, link-state advertisement delay / initial link-state advertisement throttle delay. Unfortunately, no such timers exist for Distance Vector Protocols. Therefore, reducing the routing table size is the only option for EIGRP. This can be done by aggregating and filtering reachability information ( summary route or Stub areas ).
Stage 3: Topology/Routing calculation
Similar to the second step, this is where link-state protocols use exponential backoff timers. These timers adjust the waiting time OSPF and ISIS wait after receiving new topology information before calculating the best path.
Stage 4: Update the routing and forwarding table ( RIB & FIB)
Finally, after the topology information has been flooding through the network and a new best path has been calculated, the new best path must be installed in the Forwarding Information Base ( FIB ). The FIB is a copy of the RIB in hardware, and the forwarding process finds it much easier to read than the RIB. However, again, this is usually done in hardware. Most vendors offer features that will install a pre-computed backup path on the line cards forwarding table so the fail-over from the primary path to the backup path can be done in milliseconds without interrupting the router CPU.
- DMVPN - May 20, 2023
- Computer Networking - April 7, 2023
- eBOOK – SASE Capabilities - April 6, 2023