link state and hybrid routing protocols

Distance vector routing protocols are ideal for small networks that have routers with slow processing power and limited memory resources. Today’s enterprises require significantly larger networks that can scale way beyond the limits of distance vector routing protocols. As networks grow larger, routing protocols must also be able to react to topology changes faster to ensure that all devices are aware of a change in a reasonable amount of time. Link state and balanced hybrid/advanced distance vector routing protocols were designed to overcome the scalability and convergence speed restrictions that hindered distance vector routing protocols.

 This article looks at how the innovators of these two classes of routing protocols, OSPF and EIGRP, achieve these feats and shows you how to implement and customize them in your configuration.

Link state operations

Recall that distance vector routing protocols use the Bellman-ford algorithm, which entails routing devices advertising directly connected networks that are sent to any neighbor listening on adjacent segments. When they receive the updates, they manipulate their routing tables and advertise the subsequent information to their directly connected neighbors.

One of the major downfalls of this algorithm is that the updates contain second-hand information from other routers, and the best pathway is chosen according to another device’s perception of the network. This is similar to following directions to a destination based on your friend’s sister’s boyfriend’s recollection of getting to that destination over his preferred roads and highways.

Link-state routing protocols use the Dijkstra Shortest Path First (SPF) algorithm, which is a complex and processor-intensive mathematical calculation for determining optimal paths. It’s different from distance vector routing algorithm because the calculations are actually done based on all possible routes to a destination that link-state routing protocols store in their topology tables. The best route that is chosen from the topology table for any given network is placed in the router’s routing table.

Routers receive this topology information from the neighbors they discovered by listening for link-state advertisements (LSAs) from other routers. In fact, link-state routing protocols establish a relationship with these neighbors and track them in yet another table, called the neighbor table, before even sending update information.

The updates that are exchanged between the routers contain not only the subnets that their neighbors know about but all the information about their link-states, including the status of the links and metrics for each subnet they are aware of. Knowing all the possible links and their associated metrics to reach them, the router can make first-hand decisions about which are the best path for it to take to reach each destination.

Returning to the preceding analogy, now you would learn about all the possible paths to the destination from your friend, your friend’s sister, her boyfriend, mapquest, and so on. You would base your decision on the best path using all that information.

After a router sends that topology information to its neighbors, it does not need to continuously send them that information repeatedly, as distance vector routing protocols require. Instead, link-state routing protocols send small hello LSAs every so often just to reassure neighbors that the router is still alive and ticking.

In the event of a topology change, a link-state update (LSU) is flooded to all routers, immediately alerting them of the topology change. In fact, link-state routers that receive this topology change notification flood the link-state update to their neighbors before processing and recalculating the change to update their own routing tables with the new information. Thus, there is no need for loop-prevention measures, as you witnessed with distance vector routing protocols because link-state routing protocols propagate this information and converge exponentially faster.

Because link-state routing protocols can scale to such large sizes, they can segment the routing domain into smaller systems, known as areas, so that devices do not have to maintain an excessive amount of information in their topology tables. What’s more, the routers that send information between these divisions summarize the subnets located inside the area connected to them to the rest of the autonomous system (AS). By minimizing the routing update traffic and overhead, you can speed up convergence and confine instability to a single area. Because the routers that perform this route summarization have a special function over the rest of the routers in the autonomous system, link-state routing protocols are hierarchical by design.

OSPF

The most widely used link-state routing protocols today is the IETF standard routing protocol called Open Shortest Path First (OSPF). Developed in 1988, this routing protocol was created to overcome the limitations that RIP presented for large-scale networks. We’ll have separate articles for the fundamentals of OSPF and show you how to apply them in your configuration.

Balanced Hybrid Operations

Balanced hybrid routing protocols are sometimes called Advanced distance vector routing protocols. The rationale behind this logic is that these routing protocols use similar metrics and have a maximum hop count as distance vector routing protocols.

However, balanced hybrid routing protocols discover neighbors and put them in a neighbor table before exchanging routing information, as well as keep lists of all possible routes in a topology table, just as link-state routing protocols do. By taking the best attributes from both classes of routing protocols, they have the pick of the litter, so to speak. This enables there routing protocols to be considered some of the more elite routing protocols.

EIGRP

EIGRP, the biggest contender for routing protocol stardom is a Cisco-proprietary routing protocol called Enhanced Interior Gateway Routing Protocol. As the name states, EIGRP is an enhanced version of the (now defunct) Cisco Distance vector routing protocol, IGRP. We’ll have separate articles to look at exactly how this routing protocol is actually one of the fastest-converging protocols that exist today.