- 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