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