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. Unfortunately, these advantages come at a price. Link-state protocols require more memory and processing power from the router, and more knowledge and expertise from the administrator than do distance-vector protocols.

Link-state protocols are based on the Dijkstra 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 Chapter 4, OSPF in a Single Area, and Chapter 5, Multiarea OSPF.

Routers running a link-state protocol, such as OSPF, are concerned with the states (for example, up or down) of links (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 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.

After an initial flood of LSAs provides 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 every minute or so. Moreover, 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 Inter-Domain Routing (CIDR), 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. So why are not link-state protocols used exclusively for routing? Link-state protocols 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, which potentially makes link-state routing cost-prohibitive for organizations with tight budgets and legacy hardware.
  • Link-state protocols require complex administration. Configuring link-state routing can be a daunting task, and many administrators prefer to avoid its complexity and stick to distance-vector routing. Even capable administrators may opt for a straightforward distance-vector protocol on simple networks.