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:
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 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.
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:
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.
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:
Free Resources