Understanding Routing

November 13, 2019

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.

Understand the routing through an analogy

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.

What is the purpose of a router in the network?

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.

Two types of routing: Static routing & Dynamic routing

Routing can be divided into 2 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 (Fig:3A). 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 (Fig:3B). Dynamic routing is preferred over static routing because the routers update themselves according to any changes in the network .

Dynamic routing algorithms : Link state algorithm

Let’s learn about one of the most popular dynamic routing algorithms, the link state algorithm. The link state algorithm has 2 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.

1. Dijkstra’s shortest path algorithm

Consider this network. Here 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 a 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. After the end of the iteration, we get the routing table, the output.

Let’s take a look at the graph having nodes and vertices.

We will pick the first node A and calculate the distances to neighbouring nodes (C,D and B). If we take the route from A to C, it will cost is 4. If we take the route from A to D, it will cost is 8. However, if we take the route from A to B, then it will cost is only 1. So we prefer route from A to B over A to C and A to D and update it in the table (Fig:4D).

Now we move further and find next node from B, based on this neighbouring node distance calculations. Upon calculation we find that shortest distance is B to E. We will update this in the table as shown in Fig:4E.

We will repeat all these steps until all the vertices have been visited in the graph (Fig:4F).

2. Reliable flooding

Now we will 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 (Fig:5). 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 (Fig:6A). 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 shortest path algorithm to send the packet (Fig:6B). 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’s shortest path algorithm to determine the shortest path from itself to other nodes in the network.

Understanding OSPF (Open Shortest Path First)

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. If the data packets have to flow from Area 2 to Area 3, 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.