Networking / Beginners

---

Link-State Routing Protocols

Link-state algorithms (also known as shortest path first algorithms) flood only incremental changes that have occurred since the last routing table update. During this incremental update, each router sends only that portion of the routing table that describes the state of its own links, as opposed to its entire routing table.

Link-state routing protocols require routers to periodically send routing updates to their neighboring routers in the internetwork. In addition, link-state routing protocols are quick to converge their routing updates across the network in comparison to distance vector protocols.

The speed at which they converge makes link-state protocols less prone to routing loops than distance vector protocols. However, link-state protocols also require more CPU power and system memory. One of the primary reasons that additional CPU power and memory are needed is that link-state protocols are based on the distributed map concept, which means that every router has a copy of the network map that is regularly updated. In addition to the size of the routing table, the number of routers in an area and the number of adjacencies amongst routers also has an affect on router memory and CPU usage in linkstate protocols. These factors were obvious in the old fully meshed asynchronous transfer mode (ATM) networks, where some routers had 50 or more OSPF adjacent peers and performed poorly.

Link-state protocols are based on link-state algorithms, which are also called shortest path first (SPF) algorithms or Dijkstra algorithms. "SPF in Operation," later in this tutorial, covers the SPF algorithm in more detail.

A simple way to understand how link-state technology operates is to picture the network as a large jigsaw puzzle; the number of pieces in your puzzle depends on the size of your network. Each piece of the puzzle holds only one router or one LAN. Each router "draws" itself on that jigsaw piece, including arrows to other routers and LANs. Those pieces are then replicated and sent throughout the network from router to router (via link-state advertisements [LSAs]), until each router has a complete and accurate copy of each piece of the puzzle. Each router then assembles these pieces by using the SPF algorithm.

NOTE The principle of link-state routing is that all the routers within an area maintain an identical copy of the network topology. From this map, each router performs a series of calculations that determine the best routes. This network topology is contained within a link-state database, where each record represents the links to a particular node in the network.

Each record contains the following pieces of information:

• Interface identifier
• Link number
• Metric information regarding the state of the link

Armed with that information, each router can quickly compute the shortest path from itself to all other routers.

The SPF algorithm determines how the various pieces of the puzzle fit together. Figure below illustrates all of these pieces put together in operation.

Link-state protocols such as OSPF flood all the routing information when they first become active in link-state packets. After the network converges, they send only small updates via link-state packets.