Link State Routing Protocols

Link-state routing protocols are like using a map. With a map, you can see all of the potential routes and determine your own preferred path. Link-state routing protocols create a topological map of the network and each router uses this map to determine the shortest path to each network. Routers running a link-state routing protocol send information about the state of its links to other routers in the routing domain. Link-state routing protocols are also known as shortest path first protocols and built around Edsger Dijkstra's shortest path first (SPF) algorithm.

The IP link-state routing protocols are :

• OSPF
• IS-IS

Basic OSPF operations can be configured with a router ospf process-id command and a network statement, similar to other routing protocols like RIP and EIGRP.

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.

In the figure, each path is labeled 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. 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

Each router learns about its own links, its own directly connected networks

The shortest path is not necessarily the path with the least number of hops. For example, look at the path to the R5 LAN. You might think that R1 would send directly to R4 instead of to R3. However, the cost to reach R4 directly (22) is higher than the cost to reach R4 through R3 (17).

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

Routers with link-state routing protocols use a Hello protocol to discover any neighbors on its links. A neighbor is any other router that is enabled with the same link-state routing protocol. 

Similar to EIGRP's Hello packets, when two link-state routers learn that they are neighbors, they form an adjacency. These small Hello packets continue to be exchanged between two adjacent neighbors which serve as a "keepalive" function to monitor the state of the neighbor. If a router stops receiving Hello packets from a neighbor, that neighbor is considered unreachable and the adjacency is broken.

Each router builds a Link-State Packet (LSP) containing the state of each directly connected link.

Once a router has established its adjacencies, it can build its link-state packets (LSPs) that contain the link-state information about its links. A simplified version of the LSPs from R1 is:

1. R1; Ethernet network 10.1.0.0/16; Cost 2

2. R1 -> R2; Serial point-to-point network; 10.2.0.0/16; Cost 20

3. R1 -> R3; Serial point-to-point network; 10.3.0.0/16; Cost 5

4. R1 -> R4; Serial point-to-point network; 10.4.0.0/16; Cost 20

Each router floods the LSP to all neighbors, who then store all LSPs received in a database.

Each router floods, immediately, its link-state information to all other link-state routers in the routing area. Whenever a router receives an LSP from a neighboring router, it immediately sends that LSP out all other interfaces except the interface that received the LSP. This process creates a flooding effect of LSPs from all routers throughout the routing area. 

Remember that LSPs do not need to be sent periodically. An LSP only needs to be sent:

• During initial startup of the router or of the routing protocol process on that router
• Whenever there is a change in the topology, including a link going down or coming up, or a neighbor adjacency being established or broken

Each router uses the database to construct a complete map of the topology and computes the best path to each destination network. 

After each router has propagated its own LSPs using the link-state flooding process, each router will then have an LSP from every link-state router in the routing area. These LSPs are stored in the link-state database. Each router in the routing area can now use the SPF algorithm to construct the SPF trees that you saw earlier. 

Advantages of Link-State Routing Protocol

There are several advantages of link-state routing protocols compared to distance vector routing protocols. 

Builds a 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

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 for link-state routing protocols. A notable exception is EIGRP

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 for better route aggregation (summarization) and the isolation of routing issues within an area

Modern link-state routing protocols are designed to minimize the effects on memory, CPU, and bandwidth. The use and configuration of multiple areas can reduce the size of the link-state databases. Multiple areas can also limit the amount of link-state information flooding in a routing domain and send LSPs only to those routers that need them. When there is a change in the topology, only those routers in the affected area receive the LSP and run the SPF algorithm. This can help isolate an unstable link to a specific area in the routing domain