6.7 Link-State Routing Algorithm

Link-state routing algorithms are known as shortest path first (SPF) protocols. Link-state routing algorithms 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 and how they interconnect by exchanging 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 (Mark A. Sportack 1999).
In a simple version, following this algorithm, each router (Banerjee 2004):

Discovers its neighbors and their Network Addresses by sending special packets called 'Hello' packets.

Estimates delay / cost or any other metric for reaching its neighbors by sending another special packet called

'Echo' packets.

Immediately applies its recent knowledge to form Link-state packet, which encapsulate this estimate; and,

sends (broadcasts) the packet to all the discovered routers.

Computes the shortest path to every other router using the Shortest Path Algorithm and updates the local

Routing Table.

Immediately forms fresh Link-State Packets (LSPs) and executes link state broadcast. (This is sometimes

called 'Controlled Flooding'.)

6.7 Link-State Routing Algorithm

Drawbacks to Link-State Routing

Despite all its features and flexibility, link-state routing raises two potential concerns (Mark A. Sportack 1999):

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.

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.

What's Link-State Routing Good For?

The link-state approach to dynamic routing can be quite useful in networks of any size. 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 (Mark A. Sportack 1999).
They facilitate network scalability better than either static routes or distance-vector protocols. 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 (Mark A. Sportack 1999).