Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

networks

What is link-state routing?

Adnan Abbas

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Routing tables

In computer networks, routing packets is a fundamental problem that is solved by routing tables stored in network elements like routers and switches. A routing table contains the routes to particular network destinations. We can see these in the diagram below:

Routers with their routing tables.

The diagram above shows a network topology with some routers and their respective routing tables, but an important question is how do we build these routing tables?

A routing table is only valid when the routes produced by it do not contain any deadends and loops. A key difference in various routing algorithms is the method by which they avoid loops. In addition, there is a cost function that needs to be minimized while computing these tables.

Link-state protocol

Link-state routing protocol approaches the problem by leveraging the global view of the entire network topology. If every router has a global view, it can compute the least-cost paths avoiding any loops.

Each router knows about its local link state. It periodically sends a message to inquire about the state of its neighbors (Whether the link is up or down, and the associated cost).

To enable the global view, each router sends its link-state to each of its neighbors. Upon which the neighbors send this update to its neighbors and so on. Learning the network topology in this way is known as flooding.

Routers flooding their link-states.

The routers do not send an update to the neighbors they received the link state from. As shown in the example above, 4 and 2 will not send an update to 1. Moreover, the routers also remember which updates they have seen, so they do not resend them.

Once the updates are flooded and the system has converged, the routers gain a global view of the topology, as shown below:

Routers with global view of the network topology.

After attaining the global view, each router runs an algorithm that computes least-cost paths to all other nodes. In most cases, they use the Dijkstra’s algorithm.

When to initiate flooding?

As discussed above, a router floods the updates to its neighbors. These updates are propagated ahead in the network. The need for initiation of this update can arise in the following scenarios:

  • Change in topology because of failure of a link.
  • Change in topology because of the addition of a link.
  • Change in the configuration as a result of cost update.
  • Periodic sharing of link-state information according to the network requirements.

RELATED TAGS

networks

CONTRIBUTOR

Adnan Abbas
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring