Link-State Operations

Link-State Operations


  • Compare and contrast methods of routing and routing protocols

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 secondhand 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 algorithms 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.

Remember that link-state routing protocols have to maintain three tables: the topology table, the neighbor table (sometimes called an adjacency table), and the routing table.

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 the metrics for each subnet they are aware of. Knowing all the possible links and their associated metrics to reach them, the router can make firsthand decisions about which is 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.

Know that areas are used in link-state routing protocols to speed up convergence and confine instability by route summarization.

About the author


Leave a Comment