3.1 Routing
3.1.4 Link-state routing
Link-state routing algorithms, known cumulatively as shortest path first (SPF) protocols, maintain a complex database of the network's topology. Unlike distance-vector protocols, link-state protocols develop and maintain a full knowledge of the network's routers as well as how they interconnect. This is achieved via the exchange of link-state advertisements (LSAs) with other routers in a network.

Each router that has exchanged LSAs constructs a topological database using all received LSAs. An SPF algorithm is then used to compute reachability to networked destinations. This information is used to update the routing table. This process can discover changes in the network topology caused by component failure or network growth.

In fact, the LSA exchange is triggered by an event in the network, instead of running periodically. This can greatly expedite the convergence process because there is no need to wait for a series of arbitrary timers to expire before the networked routers can begin to converge!

If the internetwork depicted in Figure were to use a link-state routing protocol, the concerns about connectivity between New York and Minneapolis would be rendered moot. Depending on the actual protocol employed, and the metrics selected, it is highly likely that the routing protocol could discriminate between the two paths and try to use the best one. Figure summarizes the contents of the gateways' routing tables.

Note: In a Link-state Routing Protocol, other metrics besides hop count are used to calculate the optimum route to a destination.

As is evident in this table's routing entries for the New York-to-Minneapolis routes, a link-state protocol would remember both routes. Some link-state protocols may even provide a means to assess the performance capabilities of these two routes, and bias toward the better-performing one. If the better-performing path, for example the route through Philadelphia, were to experience operational difficulties of any kind (including congestion or component failure), the link-state routing protocol would detect this change and begin forwarding packets through Seattle.

Drawbacks to Link-State Routing

Despite all its features and flexibility, link-state routing raises two potential concerns:

  • During the initial discovery process, link-state routing protocols can flood the network's transmission facilities, and thereby significantly decrease the network's capability to transport data. This performance degradation is temporary but can be very noticeable depending on many variables and how the routing is deployed.

Whether this flooding process will impede a network's performance noticeably depends on two things: the amount of available bandwidth and the number of routers that must exchange routing information. Flooding in large networks with relatively small links (such as low-bandwidth DLCIs on a Frame Relay network) will be much more noticeable than a similar exercise on a small network with large-sized links (such as T3s).

  • Link-state routing is both memory and processor intensive. Consequently, more fully configured routers are required to support link-state routing than distance-vector routing. This increases the cost of the routers that are configured for link-state routing.

These are hardly fatal flaws in the link-state approach to routing. The potential performance impacts of both can be addressed, and resolved, through foresight, planning, and engineering.

What's Link-State Routing Good For?

The link-state approach to dynamic routing can be quite useful in networks of any size. In a well-designed network, a link-state routing protocol will enable your network to gracefully weather the effects of unexpected topological change. Using events, such as changes, to drive updates (rather than fixed-interval timers) enables convergence to begin that much more quickly after a topological change.

The overheads of the frequent, time-driven updates of a distance-vector routing protocol are also avoided. This allows more bandwidth to be used for routing traffic rather than for network maintenance, provided you design your network properly.

A side benefit of the bandwidth efficiency of link-state routing protocols is that they facilitate network scalability better than either static routes or distance-vector protocols. When compared with their limitations, it is easy to see that link-state routing is best in larger, more complicated networks or in networks that must be highly scalable. It may be challenging to initially configure a link-state protocol in a large network, but is well worth the effort in the long run.