3.1 Routing  
  3.1.5 Link-state routing protocols  
Link-state routing protocols offer greater scalability and faster convergence than distance vector protocols such as RIP and IGRP. Link-state routing protocols require more memory and processing power from the router and more knowledge and expertise from the administrator than distance vector routing protocols. 

Link-state protocols are based on the Dijkestra algorithm, sometimes referred to as the shortest path first (SPF) algorithm. The most common link-state routing protocol, Open Shortest Path First (OSPF), is examined in Module 6.

Routers running a link-state protocol are concerned with the state of link interfaces on other routers in the network. A link-state router builds a complete database of all the link states of every router in its area. In other words, a link-state router gathers enough information to create its own map of the network. Each router then individually runs the SPF algorithm on its own map, or link-state database, to identify the best paths to be installed in the routing table. These paths to other networks form a tree with the local router as its root.

Instead of learning routes and then broadcasting the routes with incremented distances to neighbors, link-state routers advertise the states of their own links to all other routers in the area so that each router can build a complete link-state database. These advertisements are called link-state advertisements (LSAs). Unlike distance vector routers, link-state routers can form special relationships with their neighbors and other link-state routers, to ensure that the LSA information is properly and efficiently exchanged.

There is an initial flood of LSAs to provide routers with the information that they need to build a link-state database. Routing updates occur only when a link-state changes or if no changes have occurred, after a specific interval. If a link state changes, a partial update is sent immediately. The partial update contains only link states that have changed, not a complete routing table. An administrator concerned about WAN link utilization will find these partial and infrequent updates an efficient alternative to distance vector routing, which sends out a complete routing table at each update interval. When a change occurs link-state routers are all notified immediately by the partial update. Distance vector routers have to wait for neighbors to note the change, increment the change, and then pass it on to the next neighbor down the line.

The benefits of link-state routing include faster convergence and improved bandwidth utilization over distance vector protocols. Link-state protocols support classless interdomain routing (CIDR), variable-length subnet mask (VLSM), and supernetting. This makes them a good choice for complex, scalable networks. In fact, link-state protocols generally outperform distance vector protocols on any size network. Link-state protocols do have two major disadvantages:

  • Link-state routing may overtax low-end hardware. Link-state routers require more memory and processing power than distance vector routers, potentially making link-state routing cost-prohibitive for organizations with tight budgets and legacy hardware.
  • Link-state routing protocols require complex administration. Configuring link-state routing can be a daunting task, and many administrators prefer to avoid its complexity and implement distance vector routing. Even capable administrators may choose a distance vector protocol on a small network.
 

Web Links

The IP Routing Protocols

http://www.cisco.com/univercd/cc/td/doc/product/ software/ssr90/rpc_r/54043.htm