Routing - Link State Protocols

Link State protocols differ from Distance-Vector protocols in several ways, but in a nutshell a link state protocol uses a different and complex mathematical formula to compute the best route to a given network based on the actual condition of the network (or rather, the "state of the link"). Where distance-vector protocols gather their information by obtaining all possible routes that their neighbours provide, link state protocols discover their neighbours and keep the information from them in a neighbour table. Their neighbours update the condition of the networks they have knowledge of, and each router then uses Dijkstra's "Shortest Path First" algorithm to compute the best route. An example of a link-state protocol is Open Shortest Path First, or OSPF, which is an industry standard protocol that can be used between any vendor's equipment.

LS protocols send out Link State Announcements, or LSA's when they first come on line, this alerts their neighbours that they exist and that there are networks connected to them. Because each router needs to update their own routing table based on the state of their neighbours, this is a very processor-intense operation. The nice thing about LS protocols is that this only happens when there is a change in the topology (contained in the topology table which holds all possible routes to all possible networks). The updates are sent in Link State Updates, or LSU's.
One reason that LS protocols are much faster to converge than Distance Vector protocols is that a link state protocol, when it receives an update of a change in topology via LSU, forwards that info out to all its neighbours even before updating its own topology table. Getting the info out takes precedence, so all routers know the condition of the network before bothering to change their own routing tables.

LS protocols also do not send out regular updates like distance vector protocols do. They only send out changes when they occur, so once the network is converged there is very little network management traffic. Routers only send out small LSA Hello packets to make sure everyone is still alive and well.

To keep routing tables manageable and link state calculation to a reasonable time frame, LS protocols are typically separated into sections, or Areas. These areas are connected to a single area (called a backbone area), and routers in each area only maintain a topology table for other routers in their area. Between these areas, routes are summarized to keep tables manageable.

I'll be looking more in-depth at the actual protocols and perhaps comparing and contrasting them a bit in the upcoming posts.