Link-State Routing Protocol

Link-state routing protocols are also known as shortest path first protocol. It maintains a complete picture of all the router running a link-state routing protocol in the complete network. All routers running a link-state routing protocol originates information of itself and its directly connected routers, links, and the state of those links as multicast messages.

The link-state router tries to maintain full networks topology by updating itself each time a change occurs in the network. Link-state routing protocols are based on the Shortest Path First (SPF) algorithm to find the best path to a destination. Shortest Path First (SPF) algorithm also known as the Dijkstra algorithm. The OSPF is the example of Link-State Routing Protocol.

Link State Process

Following is the process of the link-state routing protocol. The process is the same for both OSPF for IPv4 and OSPF for IPv6.

Link and Link-State

Link and Link-state is the first step in the routing process. Each router learns about its links and directly connected networks. When a router interface is configured with an IP address and subnet mask and also in the state of no shutdown, then it becomes part of that network. Refer to the topology in Figure below. R3 has just added to the network and the IP addresses on the router interface are not configured yet, only the physical connectivity has done. So, the router is not part of Link-State.

The network administrator now configured the IP addresses of the router interfaces connected to R2 and R5 and change the state of interfaces from shutdown to no shutdown. As they become active, R3 learns about its own directly connected networks. Without any routing protocols used, these directly connected networks are now entries in the routing table.

The interfaces of the router must be accurately configured with IP addresses and subnet mask, and the link must be in the state of no shutdown before the link-state routing protocol can learn about a link. Also, like distance vector protocols, the interface must be included in one of the network router configuration statements before it can participate in the link-state routing process.

link-state routers have direct information from all their neighbour routers. Each router originates information about itself, its directly connected links, and the state of those links. This information is passed around the network from the router to router, each router making a copy of it without changing.  So, every router gets identical information about the internetwork, and each router will independently calculate its own best paths.

In the reference topology the R3 link to its directly connected networks are:

• FastEthernet 0/0 – 192.168.2.0/24
• FastEthernet 0/1 – 192.168.3.0/24

The link-state information includes the following information:

• The interface’s IPv4 address and subnet mask
• The type of network, such as Ethernet or Serial link
• The cost of that link
• Any neighbour routers on that link

The link-state of R3 are the following:

Link1

Network: 192.168.2.0/24

IP address: 192.168.2.1

Type of network: Ethernet

Cost of that link: 10

Neighbours: None

Link2

Network: 192.168.3.0/24

IP address: 192.168.3.1

Type of network: Serial

Cost of that link: 64

Neighbours: None

Hello Protocol

The second step in the link-state routing process is the responsibility of meeting with neighbours on directly connected networks. Routers with link-state routing protocol use a Hello protocol for establishing and maintaining router neighbour relationships. A neighbour is any other router enabled with the same link-state routing protocol. The link-state routing protocol uses Hello, packets for neighbour discovery and also for recovery.

The protocol continues exchanging Hello packets between two adjacent neighbours and serves as a keep-alive function to monitor the state of the neighbour. If any router stops receiving Hello packets from a particular neighbour. This neighbour considered unreachable and so the link-state protocol clear this router from adjacency.

Now refer to Figure 1 above, R1 sends Hello packets to it’s all interfaces when the administrator configures it, to discover the link-state neighbours .R2, and R3 respond to the Hello packet with their own Hello packets as these routers have configured with the same link-state routing protocol as shown in figure 2. The FastEthernet 0/0 interface has no neighbours. So R1 not received any hello on this interface; therefore it does not continue with the link-state routing process steps for the FastEthernet 0/0 link.

OSPF Hello Packet

After the primary exchange of hello Packet, the routers add each other to their Neighbor Tables. Neighbour table is the list of connected OSFP-enabled routers. Hello, packets are not recorded in the OSPF database, but if the hello packet has not received from a particular neighbour for 40 seconds. The link-state routing protocol marked this particular neighbour as down. For example, If a link goes down for 20 seconds and again comes back to up status, OSPF will not take any notice.

If a link goes down for any time from a minute to half an hour, OSPF floods an LSA when it goes down, and floods another LSA when it up again. If a link was down for more than half an hour; LSAs originated by remote routers begin to age out. When the link comes back up, all these LSAs will be flooded again. If a link is down for more than an hour; any LSAs originated by remote routers will have aged out and been flushed. When the link comes back up, it will be as if it were new OSPF route

Building the Link State Packet (LSP)

The third step in the link-state routing process is the building of the link-state packet (LSP) containing the state of each directly connected link. It carries the information generated by a network router in a link-state routing protocol lists the router’s neighbours. It is a special datagram determining the names of routers including; the cost or distance to any neighbouring routers and linked local networks. It can also determine the new neighbour In case of link failure. The LSP also determine what the new neighbour is if a link failure occurs, and the cost of changing a link if required.

LSPs are queued for transmission and must time out at about the same time. The network is used to distribute the LSP, but cannot use the routing database. When a router has established adjacencies to other routers, then it can build its LSPs containing the link-state information about its links. Now refer to the figure below the LSP from R1 should contain the information like the following:

1. R1; FastEthernet network 192.168.0.0/24; Cost 1
2. R1 -> R2; Serial point-to-point network; 192.168.1.0/24; Cost 1
3. R1 -> R3; Serial point-to-point network; 192.168.3.0/24; Cost 1

Flooding LSP

After building the LSP each router flood the LSP to all neighbours in the link-state routing process. This is the fourth in step link-state routing process. The neighbour routers receive the LSP and save it in the database. All routers in the same routing area flood the link-state information to each other.

When a router receives the LSP from any of its interfaces, then the receiving router immediately sends that LSP to out to all interfaces except the receiving interface. This process continues from the router to router in the same area until all router receives the LSP.  When flooding LSP is completed then the link-state routing protocol calculates the SPF algorithm, thus the link-state routing convergence speed is very high.

The routers do not send LSPs periodically like the hello packet. It is only sent during the initial startup of the routing protocol on the router. After that, the LSPs is needed to flood when there are network changes occur in the topology. It is also needed when there are network breakdown occurs or after the network coming back.

The LSPs also included information, such as sequence numbers and ageing information, to help manage the flooding LSP process. Each router uses this information to determine if it has already received the LSP from another router or if the LSP has new and updated information than LSP already contained in the link-state database. This process allows a router to keep only the most current information in its link-state database. If we discuss the topology in the previous lesson building the Link State Packet. The R1 will flood the LSP packet to all its interfaces containing the following data.

1. R1; FastEthernet network 192.168.0.0/24; Cost 1
2. R1 -> R2; Serial point-to-point network; 192.168.1.0/24; Cost 1
3. R1 -> R3; Serial point-to-point network; 192.168.3.0/24; Cost 1

Building the SPF Tree

The routers in the same area use the link-state database and SPF algorithm to build the SPF tree. For example, in the figure below R1 build the SPF tree using the link-state information from all other routers. To start, the SPF algorithm read the router’s LSP to recognize networks and also the costs of the link.

In the first step, R1 identifies its directly connected networks and the costs of the network. After identifying the directly connected network, the R1 begin identifying unknown networks from R2 and R3. Then the SPF algorithm calculates the shortest paths to reach each network.

The SPF algorithm then calculates the shortest paths to reach each network. Each router in the area builds its own SPF tree separately from all other routers. To make sure accurate routing, the link-state databases used to build those trees must be identical on all routers.

Building the Link-State Database

Link-state database building is the last step in the link-state routing process. Each router in the link-state uses the database to build a complete map of the topology and also computes the best path to each destination network. All routers receive LSPs from every other link-state router in the same routing area. the

These LSPs stores in the link-state database. Each router maintains a separate link-state database for every area to which; it belongs in case of more than one area configured in the network. The link-state database also referred to as the topological database and routers belong to the same area have the same topological database for the area.

The databases for each area always process separately and link-state calculate; the shortest path separately for each area and the topological database; is flooded throughout the respected area only. The area database build of router links advertisements, network links advertisements; and summary link advertisements included external routes in all non-stub area databases.

Summary of Link-State Process

• Every router in an OSPF area will complete the following link-state process to exchange a state of convergence:
• Each router learns about each of its own directly connected networks and Links by detecting the interfaces in the upstate.
• All routers are responsible for “saying hello” to its neighbours on directly connected networks.
• Each router builds a Link-State Packet (LSP) containing the state of each directly connected link. The LSP containing neighbour, neighbour ID, link type and link bandwidth.
• Each router floods the LSP to all neighbours. Those neighbours store all LSPs received in a database. They 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.
• Each router floods the LSP to all neighbours who then store all LSP’s received in a database.
• All routers use the database to build a complete map of the topology and calculate the best path to each destination network using Dijkstra’s Algorithm

Important Term of Link-State Protocol

Topological database – It is a set of information collected from LSAs.

SPF algorithm– The shortest path first (SPF) algorithm is a calculate the SPF tree on the bases of information in the database.

Routing tables – A list of the known paths and interfaces.

LSA – A link-state advertisement (LSA); is a small packet of routing information that is sent among routers. It is a basic communication way of the OSPF routing protocol for the Internet Protocol (IP). It communicates the router’s local routing topology to all other local routers in the same OSPF area.

LSP – It is a packet containing information generated by a network router in a link-state routing protocol that lists the router’s neighbours. It is a special datagram determining the names of routers including the cost or distance to any neighbouring routers and linked local networks. It can also determine the new neighbour In case of link failure.