Link-State Routing Basics - dummies

By Edward Tetz

Compared to distance-vector routing, link-state routing optimizes routing structures by performing calculations on the best routes instead of just passing full routing table information between routers. Link-state routing only sends interface information about the different interfaces existing on a router and the networks to which the router is connected. So, rather than send a 20-to-50–entry routing table, link-state updates send only the information about the router’s four to six interfaces.

Understanding link-state protocol

Each router puts all the link-state information it receives in a topological database, which is a table that contains link information about all known routers. It does not define routes; instead, it records all the information required to get to every network segment connected to every router after the routing information is calculated.

There will probably be more than one route to each network, so it is important to evaluate each and every possible route to find the best route to each network segment. You can do so using the Shortest Path First (SPF) algorithm, which then builds the SFP tree.

Since the router knows about all of the links on the network, it is able to evaluate all links from itself to determine the most efficient way to reach every other network segment on the network. This is referred to as the shortest path to each of those network segments. All of the shortest paths are stored in one location, which is referred to as the SFP tree.

After the SFP tree is built, the router reviews it to find the best possible route to each network. After the best routes are found, the router adds them to its own routing table. This routing table is built on each router, but it should be the same for all routers that receive the same updates, because they all use the same process to build the routing table.

When a router starts up and sends its initial link-state information to its neighbors, it reduces network overhead by only sending updates to its link information. These Link State Advertisements (LSA) are flooded out to all routers in their area or zone. LSAs are simply updates on their link status, so one is sent whenever a link is connected or disconnected.

Working with your strengths

This system of handling updates seems to be the key to the strength of link-state protocols. Although some variance occurs between the two protocols, in general, link-state protocols are different than distance-vector protocols in the following ways — you can decide if these differences represent benefits or drawbacks:

  • Cost metrics are the main determining factor of route selection. These cost metrics are the point of evaluation to determine the best links, which may include the speed and capacity of the links.

  • Less frequent routing updates.

  • High degree of scalability to support much larger networks.

  • Division of overall network into smaller segments to limit scope of routing changes.

  • Only sends updates on link status and topology changes.

  • Triggered updates can immediately notify systems of changes, reducing convergence times.

  • Network design can reduce the size of the link-state database. When the network ID are laid out to support route summarization, then the reduce number of routes will reduce the size of the link-state database.

  • Limited age of data, because LSA aging always keeps information current.

  • Routing loops are almost eliminated because routers know what the entire network topology looks like.

  • Large amounts of memory are required to support not only the routing table, but also the link-state database and adjacency database (which is table listing neighboring devices).

  • Execution of the Dijkstra algorithm (the mathematical formula used to perform the shortest path calculation) requires the use of CPU cycles on the router, and for larger networks, this requirement means more CPU time spent on calculations.

  • In large network implementations, link-state protocols can require a great deal of tuning to function properly. This necessity can present significant challenges to a network administrator.

If you have sufficient CPU and memory resources on your network routers and your network layout is not overly complicated, you should not suffer from the issues related to link-state protocols — but only reap the benefits. There is no reason that link-state protocols should not be used as primary routing protocol on your network.