Link state routing protocol
Link state routing protocols operate by flooding link state information into the network. The link state information is stored in a link state database, sometimes called a topological database, and each router has a copy of this database.
The link state database includes information such as the number of ports on each router, the Network Layer address and current state of those ports, and the subnetworks to which those ports connect. In a very real sense, there is sufficient information in the database for the router to generate a complete map of the internetwork, to label each router with its appropriate addresses, and to label each port with its current state and cost. Then, using a shortest path first (SPF) algorithm (e.g., Dijkstra’s Algorithm), each router can calculate the shortest path from itself to every known subnetwork and use the information to populate a routing table.
Link State Routing Protocols and Routing Updates
The visual depicts what happens in an internetwork implementing a link state routing protocol when a link failure occurs. The router experiencing the link failure (or any other change in the status of one of its ports) generates a link status update on each of its active ports. That link status message is flooded throughout the internetwork, resulting in an altered link state database at each router. Each router then recalculates its routes and updates its routing table. In the network depicted on the visual, all of the routers discover that they no longer have a viable route to Subnetwork 3. This subnetwork has been isolated from the rest of the internetwork and will remain so until the link failure is fixed.
This description of link state protocol operation is highly simplified. Link state routing protocols are complex and must deal with potentially complex issues. How these issues are addressed differs depending on the specific link state routing protocol being discussed. Some of the issues that must be addressed follow.
- How a newly installed router initiates itself. In order for the router to correctly populate its link state database, it must obtain a copy of the link state database from one of the active routers. At the same time, it must distribute information about itself and its ports to the rest of the routers in the network.
- Detecting the complete failure of a router. A router may be able to send a link status update on its active ports when one of its ports fails, but it is unlikely to notify the rest of the network that it is about to crash, nor can it send the updates posthumously. Somehow, the routing protocol must define a strategy by which the other routers can detect the absence of one of their peers.
- How routers ensure that their database is correct. If any router’s database contains incorrect information, the routing table it builds will also be incorrect. The routers must have a strategy for ensuring, perhaps even periodically checking, the database correctness.
- How to reconnect a network that has been divided by a failure. When a network failure causes the internetwork to split into two unconnected internetworks, the link state databases in the two separated internetworks eventually lose all information related to the subnetworks they can no longer reach. When the failure is resolved and the internetwork is made whole, the two portions of the network must synchronize their databases.
- Minimizing bandwidth consumed by flooding updates in large internetworks. Although link status messages are small, as the network grows large, the number of updates that might be transmitted at any one moment grows quickly. And flooding is still an inefficient (though highly reliable) method of sending information.
- Minimizing the size of the link state database in large internetworks. A large internetwork (i.e., many routers and subnetworks) means a large link state database. A large link state database requires a significant amount of memory to store, and a significant amount of processing power to run, the calculations necessary to generate a routing table. This is especially a problem when the router is integrated into a server, which needs to focus its memory and processing resources on servicing user applications.
Link State Routing Protocol Examples
The accompanying table shows three examples of link state protocols and the Network Layer protocols that they support. These “newer” protocols are designed to coexist with the older distance vector protocols so that a forklift upgrade is not necessary.
Link State Routing Protocols Assessed
Link state routing protocols have several advantages. The fact that the routers flood link state information throughout the internetwork reduces the convergence time of the network. Each router maintains its own database, which should be identical to all other databases in the network. Convergence time is now bound by the time it takes a message to travel across the network (even extremely large networks can have transmission time under a few seconds), and the interval between routing table generations. This means that the size of the internetwork contributes a negligible amount to the convergence time, making link state routing protocols suitable for very large internetworks.
The fact that the information flooded into the network usually consists of small packets with a few items of link state information, instead of full routing tables, means that a link state protocol generally uses less bandwidth than a distance vector protocol. This is true even though flooding typically implies a significant load of traffic. Most link state routing protocols, however, define a number of mechanisms to control (and minimize) the flood of information.
Link state protocols have the disadvantage of being fairly complex to implement. All routers in the network require redundant databases. Routing table calculation is also a more complex process than simply comparing routing table entries. In short, link state protocols tend to be more memory-intensive and processor-intensive than distance vector routing protocols.
While these disadvantages seem trivial in an era of high-powered microprocessors and inexpensive random access memory (RAM), they should not be underestimated. Today’s networks are increasingly large, multiprotocol, and complex. In addition, servers commonly provide the routing function. In a multiprotocol router (which could be concurrently running several different routing protocols) or a server providing routing function (which also has to support services to clients), the processor and memory demands of a link state routing protocol may have a significant impact.
Another serious drawback is the complexity of many link state routing protocols. They are significantly more complex than are distance vector routing protocols. While some network administrators might be willing to wade through the complexity in order to achieve better network reliability and performance, many are not. The ones who are willing tend to be administrators of relatively large or mission critical internetworks. Smaller internetworks, however, will probably operate fine using distance vector routing protocols.
|<mp3>http://podcast.hill-vt.com/podsnacks/2007q2/link_state.mp3%7Cdownload</mp3> | Link state routing protocols|