Link State Routing

Link state routing is an interior protocol that updates the routers inside the autonomous system i.e it is an intradomain protocol. The link-state routing was introduced to overcome the shortcomings of the distance vector routing protocol.

The reason behind the replacement of distance vector routing protocol was it would take too long to propagate the information about the change in the cost of the link, or if the link becomes unavailable.

Content: Link State Routing

1. Working of Link State Routing
2. Building Routing Table

Working of Link State Routing

Whenever a new router is initialized inside the domain of an autonomous system the first thing it determines is the cost of the links on each of its interfaces. Once it determines the cost for the link at each of its interfaces the router advertises this information to all the routers present in the domain and it keeps monitoring the cost of the links onwards.

If the router observes any change in the cost of the link at any of its interfaces, then the router again advertises this change to all the routers in the domain. Now in this protocol, each router has information about the set of link costs of all the routers in the domain, so each router develops the topology of the entire domain. Each router having the topology of the domain can now calculate the shortest path and build a routing table using the Dijkstra algorithm.

The link-state routing protocol can not be used as an exterior routing protocol or inter-domain routing protocol. The reason behind not using the link-state routing as interdomain routing protocol is discussed below:

• In a large network like the Internet, different autonomous systems may use different link metrics. As the metrics vary from one network to another this prevents the link-state routing to be used as a consistent routing protocol.
• Link state routing involves the flooding of link-state information to all the routers in the domain. If we use it as an interdomain routing protocol, the flooding across multiple autonomous systems may be unmanageable.

The working of link-state routing can be stated in four simple steps.

1. When a router is initiated, it identifies its neighbors and their network address.
2. It set the cost metric of the link at each of its interfaces connecting it to its neighbor.
3. Advertise link-state packet (LSP) containing its link-state information to all other routers in the domain. Also, receive information from other routers.
4. Calculate the shortest path to every other router in the domain and prepare a routing table.

Discussing the working of link-state routing in brief let’s discuss the building of routing table at each router in the domain in brief.

Building Routing Tables

While building of routing table the routers have to ensure that they are showing the shortest path to every other router in the domain.  Building a routing table involves the following steps.

1. A router has to create a link-state packet (LSP) which contains a set of link costs at each interface of the router.
2. Distribute this LSP to all other routers in the domain, not just the neighboring ones.
3. Formation of shortest-path tree for each router.
4. Formation of routing table with the shortest path to other routers in the domain.

Let us discuss each step in more detail.

1.  Formation of Link State Packet (LSP)

The link-state packet has information about the router in detail. It has information about the router’s identity, list of links, sequence number, and age. The information about the router’s identity and list of links from the router help another router in the AS to understand and make a topology of the entire domain.

The sequence number of the LSP helps the receiving routers to compare between the old LSP and new LSP and it also facilitates the flooding feature of link-state routing. The age of LSP helps routers in the domain to decide the time at which the LSP must be discarded.

The LSP is created by routers in the domain at two events first when the topology of the domain gets changed and second at a regular interval.

1. Whenever there is a little change in the topology of the domain the LSPs are disseminated informing all the routers in the domain updating them about the change.
2. Dissemination of the LSPs at a periodic interval ensures that any router in the domain does not contain the old information. The timer set for the periodic dissemination of the LSP is around 60 min to 2 hours. The long interval prevents the flooding features from creating too much traffic in the domain.

2. Flooding of LSPs

The created LSPs are disseminated to all other routers present in the domain, not just the neighboring routers. This transmission of LSPs to all the routers in the domain is referred to as flooding.

In the first step, the created LSP is sent on the link at each interface of the router.

The routers receiving the LSPs first compare it with the LSP it has received earlier. If the new LSP is older than the previous LSP the newly received LSP is discarded else the router performs the following steps to ensure flooding.

1. First, the router discards the old LSP.
2. Secondly, the router disseminates a copy of LSP through all its interface other than the one through which it has received the LSP.

3. Creation of Shortest Path Tree

As each router in the domain has information about each other router in the domain so, each router creates the topology of the entire domain. To determine the shortest path to every other router in the domain, the shortest-path tree must be created for every router.

The shortest-path tree is a graph that has one root node (the router for which the shortest path tree is created) and several other nodes (rest of the routers in the domain) called leaf nodes. The shortest-path tree expresses a single and the shortest path to every other node in the tree.

The shortest-path tree is created for each router in the domain where the router for which the tree is created is considered as a root node for that tree. To determine the shortest path for each router, the Dijkstra algorithm is used which employs the following steps.

Initialization: Select the root node. Set the shortest distance from the root node to every other node as the cost between the root node and that corresponding node. The shortest distance between root node to root node is 0.

Iteration: This step is repeated until all the routers are added to the root node. This step has two sub-steps

• Add the next node: Search the next node that is not in the path of the root node and select node with minimum cost. Add the selected node to the path.
• Update: Now update the shortest distance for the rest of the nodes in the domain using the shortest distance of the node that we have just added to the path of step 2.

D_j = minimum (D_j, D_i + c_ij) for all remaining nodes

Let us take an example, in the figure below, there is a topology of an AS.

We will discuss how the shortest path tree for node A. First, we will initialize node A and set the shortest distance to its immediate neighbors.

Among the two immediate neighbors of node A, we will add a node to the path that has the shortest distance i.e. node B with shortest distance 2.

Now search for the nodes that are not added to the path yet (C, D, E) and select the one with the shortest distance i.e. node D.

Now, nodes B and D that we added to the path were directly connected to root node A and were at the shortest distance as compared to any other path. Further, we have node E and node C which can be reached by node A through node B or through node D. Let us check out which path is shortest.

D_j = minimum (D_j, D_i + c_ij)

D_E = minimum ((2+4) B, (3+5) D)

D_E = minimum ((6) B, (8) D)

D_E =6

Here we will choose the path for node E through node B. Similarly, we will calculate the shortest distance for node C.

D_C = minimum (D_j, D_i + c_ij)

D_C = minimum ((2+5) B, (3+5+2+4) D)

D_C = minimum ((7) B, (14) D)

D_C =7

Now, node E has the shortest distance so we will add node E to the path.

After adding node E to the path again explore the nodes that are not added to the path and there enlist their cost as the distance. Again select the node with the shortest distance so we will add node C to the path.

Now we are left with node F and node G we will calculate the shortest distance for node F and G as we calculate for node E and C. Now, among F and G the node with the shortest distance is node F so, we will update and add node F to the path. Also, the root node A can reach node G through node F with the shortest distance i.e.9. So finally we add node G.

4. Creating Routing Table

Using the shortest path tree each router creates a routing table which has three column destination, cost, and next router. In the figure below, I have given a routing table for router A. Similarly the routing table is created for all the routers in the domain.

So, this how the link-state routing protocol is used to route the packet in the autonomous system. The OSPF (open shortest path first) protocol is based on the link-state routing protocol.