Link State Routing Explained

Routers use routing tables to make forwarding decisions. A routing table can be updated in three ways : automatic, manual, and dynamic. In the automatic method, the router automatically updates the routing table from the IP configuration we make on the router's interfaces. In the manual method, we manually update the routing table. In the dynamic method, we configure a routing protocol on all routers. The routing protocol allows routers to exchange routing information. From the exchanged information, routers automatically learn and select the best path for every subnet available in the network.

Routing protocols are categorized into three types: distance vector, link state, and hybrid . A distance vector routing protocol uses the number of routers on the path to measure the best path for every subnet. A link-state routing protocol uses the parameters that control the traffic flows on the path to measure the best path. A hybrid routing protocol uses both.

Link state routing

Link state routing works in three steps. In the first step, it discovers all available paths in the network. In the second step, it runs an algorithm known as Shortest Path First (SPF) on the path discovered in the first step to calculate the shortest path for every subnet in the network. In the third step, it adds all selected paths in the second step to the routing table. To save data for each step, it uses a separate table. For three steps, it uses three tables.

Let us understand these steps and tables in more detail.

In the first step, it discovers network paths. To discover network paths and their parameters, it exchanges routing information with directly connected routers. It exchanges routing information in the form of LSA (Link State Advertisement). A LSA contains a unique ID, source address, and a piece of routing information. It uses multicast to exchange LSAs. It exchanges LSAs only with neighbors. Two routers become neighbor only when their certain parameters match. All routers use a table, known as the neighbor table, to keep track of their neighbors.

In the second step, all neighbor routers exchange routing information. From the exchanged information, they build the topology of the entire network and save it into a table known as the topology table.

In the third step, they calculate the shortest path to each destination from the topology table and save it in the routing table.

Link state routing examples

IS-IS and OSPF are examples of link-state protocols. IS-IS was originally developed by DEC. It can route for TCP/IP, CLNP (Connectionless Network Protocol), and CLNS (Connectionless Network Service) traffic. ISPs use it as the routing protocol for their networks. On the positive side, it provides more scalability than OSPF. On the negative side, it is more complex to configure than OSPF.

OSPF was created in the mid-1980s to overcome the deficiencies and scalability issues of distance vector routing in large enterprise networks. It provides fast convergence with triggered incremental updates. It is one of the most widely used routing protocols in enterprise networks.

Link state routing updates

Link state routing uses multicast to exchange routing information. Since it uses multicast to exchange routing information, only the routers running the same link-state routing protocol receive routing information. It is different from the traditional distance vector routing. Distance vector routing uses broadcast to exchange routing information. In broadcast, all routers receive routing information, whether they are running the same routing protocol or not.

Apart from using multicast to exchange routing information, link state routing also verifies and acknowledges the received information. When a destination router receives a routing update, it responds to the source router with an acknowledgment. The source router uses the acknowledgment to confirm the routing update it sent.

A router keeps track of all routing updates it receives. When it receives a new routing update, it compares it with the previously received routing updates. If the recently received update has no new information, it ignores the update. If the update contains new information, it updates the topology table. The SPF algorithm uses the topology table to calculate the shortest path for every destination subnet in the network. If entries in this table change, the SPF algorithm automatically recalculates all paths and updates the routing table with path information. Due to this feature, entries in the routing table change only when the network topology changes.

Link state routing advantages

  • It uses a hierarchical structure. A hierarchical structure limits the distance that an LSA travels.
  • It uses multicasts to share routing information. Multicasts are sent to a group of devices. Only routers running the link state protocol will listen and process them.
  • It supports classless routing. Classless routing allows us to summarize a large group of contiguous subnets into smaller subnets.
  • It automatically detects and removes routing loops.

Link state routing disadvantages

  • It is complex.
  • It consumes more CPU and RAM than other routing methods.
  • Since it uses trigger updates, a flapping link can affect the stability of the network.

ComputerNetworkingNotes CCNA Study Guide Link State Routing Explained