- The amazing journey of data packets from a data center to your device forms the backbone of the internet. This data flow is governed to make the most efficient
transfer of the data. It is apparent from this animation that this governing of the data, from the source to the destination, through such a complicated
network is not an easy task. This whole process of the
efficient flow of data from the source to its
destination, is known as routing. Let's try to understand
routing through an analogy. Imagine a scenario where you
are trying to reach your home from your office. The roads are full of traffic. In this scenario, you look up the road and traffic
conditions on Google Maps. Based on the traffic situation
and the road conditions, you take the easiest
path to reach your home. Similarly, in routing, the decisions regarding
the movements of packets are taken based on the state of network and a device called a router makes these logical data decisions. The main purpose of having a router setup is to find the most efficient path through which the packets
can be transferred from source to destination. Using very sophisticated algorithms, the router makes the decision
as to which router or device the current packet has to be sent via. This procedure is
repeated until the packet finally arrives at the destination. Routing can be divided
into two categories, static and dynamic. In static routing, all the routes are set
in a router manually. Thus, if there is any
change in the network, there will not be any change in the route, unless someone manually corrects it. In dynamic routing, routes
are set by the software according to the current
state of the network. Network changes such as link failures, traffic changes and cost changes will be updated at every
discrete time step. And based on this information, new routes will be
decided at each time step. Dynamic routing is preferred
over static routing, because the routers update themselves according to any changes in the network. Let's learn about one of the most popular dynamic routing algorithms,
the link state algorithm. The link state algorithm has two parts, reliable flooding and Dijkstra's
shortest path algorithm. First, let us understand the Dijkstra's shortest path algorithm, an algorithm developed by the famous Dutch computer scientist, Edsger W. Dijkstra, in the year 1956. Consider this network. Here are the costs between
each node are marked. The challenge is to find
out the shortest path from one node to another. The Dijkstra algorithm
produces a table as its output, and using that we can
determine the shortest path in the network. This table is generated for the vertex A. And using this table, you
can predict the shortest path to any other point. If you want the shortest path to point I, just check the previous vertex. From this vertex, check its
previous vertex, and on, until you Reach point A. This table is generated
using an iterative method with the initial values
of the shortest distance as infinity. Due to a shortage of time, we are just animating the procedure used to generate this algorithm. After the end of the iteration, we get the routing table, the output. Now we look at the first part
in a link state algorithm, reliable flooding. You might have noted that to perfectly execute
Dijkstra's algorithm, each router should have the information of the entire topology. This is the first step
in link state routing. The neighborhood information of a router is known as its link state. This information can be the IP address of the neighboring router, cost of the neighboring links,
health of the links, etc. The small packets that contain
this neighbor information are known as link state packets. As mentioned in the name, we should accurately flood each
router with the link states of all the other routers in the topology. This is very similar to how gossip in a classroom
spreads like wildfire, from one student to another,
until everyone knows it. In a network, initially each router knows its own link state. For this small network, A passes its link state
packet to its neighbors, B passes the packet to
its neighbors and so on. In this way, all the nodes
will have the complete link state information of the topology. With this packet information, all nodes create or update a routing table and apply a Dijkstra's
shortest path algorithm to send the packet. However, flooding is not so simple. Consider a scenario where
three nodes, A, B and C are interconnected. Node A sends link state
information to B and C. Similarly, C sends the information to B, and B sends information to C again, and the process continues in a loop. This issue is known as looping. So, in an ideal scenario, you would want the node to
receive this information only once. So how do you overcome
the looping problem? Each packet is assigned a unique ID. When B receives this packet
with its unique ID from A and C, it does not send it to C. After the flooding operation, each node independently runs Dijkstra
shortest path algorithm to determine the shortest path from itself to other nodes in the network. The algorithm we saw is
implemented in a network with the help of protocols. Applying the flooding operation
to the entire global network is an almost impossible task. The protocol of the link
state routing algorithm is known as OSPF. In OSPF, the complete network is divided into several local areas. A backbone area is also created, which shares at least one
router from the local areas. This way a few border routers are created. You can see all the local areas are connected to the backbone
area via these border routers. In OSPF, the flooding operation
happens within a local area, not globally. If the packets of a local area need to travel to another local area, they have to go through the backbone area. This is clearly illustrated
in this animation. If the data packets have to flow from area two to area three, they have to pass through
the backbone area, not directly. This type of structure reduces the complexity of the operation by reducing the size of the routing table, and also helps in the
scalability of the network. We hope this video has
given you a good overview about the routing operation. Thank you
