Link-State Routing

Link-state routing protocols are also known as shortest path first protocols and are built around Edsger Dijkstra’s shortest path first (SPF) algorithm. The SPF algorithm will be discussed in more detail below.

Link-state routing protocols are more complex than their distance vector counterparts. However, the basic functionality and configuration of link-state routing protocols are no more complex. Even the algorithm itself can be easily understood, as you will see.

Basic OSPF operations can be configured with a router ospf process-id command and a network statement, similar to other routing protocols such as Routing Information Protocol (RIP) and Enhanced Interior Gateway Routing Protocol (EIGRP).

Introduction to the SPF Algorithm
Dijkstra’s algorithm is commonly referred to as the shortest path first (SPF) algorithm. This algorithm accumulates costs along each path, from source to destination. Although Dijkstra’s algorithm is known as the shortest path first algorithm, this is in fact the purpose of every routing algorithm.

image011

In the picture above, each path is labelled with an arbitrary value for cost. The cost of the shortest path for R2 to send packets to the LAN attached to R3 is 27 (20 + 5 + 2 = 27). Notice that this cost is not 27 for all routers to reach the LAN attached to R3. Each router determines its own cost to each destination in the topology. In other words, each router calculates the SPF algorithm and determines the cost from its own perspective.

So exactly how does a link-state routing protocol work? The following list summarises the link-state routing process. All routers in the topology will complete the following generic link-state routing process to reach a state of convergence:

1. Each router learns about its own links, its own directly connected networks. This is done by detecting that an interface is in the up state, including a Layer 3 address.

2. Each router is responsible for meeting its neighbours on directly connected networks.

Similar to EIGRP, link-state routers do this by exchanging Hello packets with other link-state routers on directly connected networks.

3. Each router builds a link-state packet (LSP) containing the state of each directly connected link. This is done by recording all the pertinent information about each neighbour, including neighbour ID, link type, and bandwidth.

4. Each router floods the LSP to all neighbours, who then store all LSPs received in a database. Neighbours then flood the LSPs to their neighbours until all routers in the area have received the LSPs. Each router stores a copy of each LSP received from its neighbours in a local database.

5. Each router uses the database to construct a complete map of the topology and computes the best path to each destination network. Like having a road map, the router now has a complete map of all destinations in the topology and the routes to reach them. The SPF algorithm is used to construct the map of the topology and to determine the best path to each network. All routers will have a common map or tree of the topology, but each router will independently determine the best path to each network within that topology.

 

Advantages of a Link-State Routing Protocol
There are several advantages of link-state routing protocols compared to distance vector routing protocols.

Topological Map
Link-state routing protocols create a topological map, or SPF tree, of the network topology.

Distance vector routing protocols do not have a topological map of the network. Routers implementing a distance vector routing protocol only have a list of networks, which includes the cost (distance) and next-hop routers (direction) to those networks. Because link-state routing protocols exchange link states, the SPF algorithm can build an SPF tree of the network. Using the SPF tree, each router can independently determine the shortest path to every network.

Fast Convergence
There are several reasons why a link-state routing protocol converges faster than a distance vector routing protocol. When receiving a link-state packet (LSP), link-state routing protocols immediately flood the LSP out all interfaces except for the interface from which the LSP was received. A router using a distance vector routing protocol needs to process each routing update and update its routing table before flooding them out other interfaces, even with triggered updates. Faster convergence is achieved with link-state routing protocols. A notable exception is EIGRP.

Another reason that a link-state protocol converges faster is the lack of a hold-down timer, which is a distance vector routing protocol feature designed to give the network time to converge. Link-state routing protocols do not use a hold-down timer because any changes in the topology are flooded immediately with the entire routing domain using LSPs.

Event-Driven Updates
After the initial flooding of LSPs, link-state routing protocols only send out an LSP when there is a change in the topology. The LSP contains only the information regarding the affected link. Unlike some distance vector routing protocols, link-state routing protocols do not send periodic updates.

Hierarchical Design
Link-state routing protocols such as OSPF and IS-IS use the concept of areas. Multiple areas create a hierarchical design to networks, allowing better route aggregation (summarisation) and the isolation of routing issues within an area. Multi-area OSPF is outwith the scope of this course and you will probably use only one area, most like called area 0.

The advantages of link-state routing protocols are summarised in the following list:

■ Each router builds its own topological map of the network to determine the shortest path.

■ Immediate flooding of LSPs achieves faster convergence.

■ LSPs are sent only when there is a change in the topology and contain only the information regarding that change.

■ Hierarchical design is used when implementing multiple areas.

Memory Requirements
Link-state routing protocols typically require more memory, more CPU processing, and at times, more bandwidth than distance vector routing protocols. The memory requirements are because of the use of link-state databases and the creation of the SPF tree.

Processing Requirements
Link-state protocols can also require more CPU processing than distance vector routing protocols. The SPF algorithm requires more CPU time than distance vector algorithms such as Bellman-Ford because link-state protocols build a complete map of the topology.

Bandwidth Requirements
Flooding of link-state packets can adversely affect the available bandwidth on a network. This should only occur during initial startup of routers, but it can also be an issue on unstable networks.

Next – OSPF – Link-State Routing Protocol