Routing Algorithms

By: Roozbeh Razavi

Introduction:

A router is used to manage network traffic and finding the best route for packets to be sent. But have you ever thought that how routers do this? Its obvious that routers should have some information about network status, to make decision about how to send packets. But how do they gather this information? Indeed routers use “Routing algorithms” to find the best route to destination. When we say best route, we consider parameters like the number of Hops (a hop is the trip a data packet takes from one router or intermediate point to another in the network), time delay and communication cost of packet transmission. See figure 1.

Figure 1

Based on how routers gather information about structure of network and their analyzation of information to specify the best route, we have two major routing algorithms: “Global routing algorithms” And “Decentralized routing algorithms”.
In Global Routing algorithms, every router must have complete information about other routers in network and traffic status of network. These algorithms also known as LS (Link State) algorithms that will be described in next session.
Reverse in Decentralized routing algorithms, each router has information about the routers that is directly connected to and not about all routers in network. These Algorithms are also known as DV (Distance Vector) algorithms.

LS algorithms:
In LS algorithms every router has to follow these steps:

1-Identify the routers that are physically connected to them and get their IP addresses:
When a router starts working, first send a “HELLO” packet over network. All the routers that receive this packet, reply with a message that contains their IP addresses.
2-measure the delay time (or any important parameters of network such as average traffic) for neighbor routers:
:In order to do that routers send Echo packets over the network, every router that receives these packets replies with an Echo reply packet By dividing Round Trip Time by 2, routers can count the delay time. (Round Trip Time is a measure of the current delay on a network, found by timing a packet bounced off some remote host). Note that this time includes both transmission and processing times. (The time in which t packets reach the destination and the time in which the receiver processes it and replies.)
3-broadcast its information over a network for other routers and receive theirs:
In this step, all routers share their knowledge and broadcast their information to each other. In this way, every router can know the structure and status of network.
4-with an appropriate algorithm, Identify the best route between two nodes of network:
In this step, routers should choose the best route for packets to every node. They do it by using an algorithm such as “Dijkstra Shortest Path Algorithm”. In this algorithm, router, based on information that has been collected from other routers, build a graph of network. This graph shows the location of routers in network and their links. Also every link will be labeled with a number which is called weight of link and is also known as cost of link. This number is a function of delay time, average traffic and sometimes simply, it is the number of hops between nodes. For example if there were two links between a node to destination, the router chooses the link with the least weight.
Dijkstra algorithm concludes theses steps:
1-The router builds a graph of network and identifies source and destination nodes as V1 and V2 for example. Then it will build a matrix named “Adjacency Matrix”. In this matrix a [i, j] is a weight of link between Vi and Vj .if there was not a direct link between Vi and Vj this amount will be assumed as Infinity.

2-It builds a status record set for every node of network that contains three fields:

• The first field that shows the previous node. We call this field “predecessor” field.
• The second filed that shows the sum of weights from source to that node. We call this field “Length” field.
• The last field that shows the status of node. Each node can have one status mode: “Permanent” or “Tentative”. We call this filed as “Label” filed.

3-It initializes the parameters of status record set (for all nodes) and set their length to Infinity, and their label as tentative.
4-Assume V1 as t node and make its label as permanent. Note that when a label changes to permanent, it never changes again. T node just rules as an agent and noting more.
5-For all tentative nodes that are directly linked to t node, status record set should be updated.
6-From all the tentative nodes, choose the one whose weight to V1 is less and set it as t node.
7-If this node is not V2 (destination) then, go to step 5
8-If this node is V2 then extract its previous node from status record set and do this until return to V1.The nodes show the best route from V1 to V2.

Example of using Dijkstra algorithm:
Here we want to find the best route between A and E. (See figure 3) You can see that there are 6 possible routes between A and E (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE) and its obvious that ABDE is the best route because its weight is less than other routes. But life is not always so easy and there are some complicated cases in which we have to use algorithms to find the best route.

1-As you see in figure 2,the Source node (A) has been chosen as t node and so its label is permanent (we show permanent nodes with filled circles and t nodes with –> mark)

Figure 2

2-In this step you see that status record set of tentative nodes that have a direct link to t node, (B, C), has been changed. Also since B has less weight, it has been chosen as t node and so its label has changed to permanent. (See figure 3)

Figure 3

3-In this step like step 2,the status record set of tentative nodes that have a direct link to t node, (D, E), has been changed. Also since D has less weight, it has been chosen as t node and so its label has changed to permanent (See figure 4)

Figure 4

4-Here we don’t have any tentative node so we should just identify the next t node. Since E has the least weight, it has been chosen as t node.

Figure 5

5-E is the destination, so we shouldn’t continue. We are at end! So we have to identify the route. The previous node of E is D and previous node of D is B and its previous node is A. So the best route is ABDE. In this case the total weigh is 4 (1+2+1=4).
Although this algorithm works well, its so complicated that may take long time for routers to process it and so the efficiency of network fails. Also if a router gives wrong information to other routers, all routing decisions will be ineffective.
you can see the source of program written by C to understand this algorithm better:

DV algorithms:

DV algorithms are also known as Bellman-Ford routing algorithms and Ford-Fulkerson routing algorithms .In these algorithms every router has a routing table that show it the best route for any destination. Figure 6 show a typical routing table for router J

Now imagine that the link between A and B cut. At this time B corrects its table. After specific amount of time, routers exchange their tables and so B receive c’ routing table. Since C doesn’t know what has been happened to link between A and B, says that it has a link to A with the weight of 2. (1 for C to B and 1 for B to A, because it doesn’t know B has no link to A) B receives this table and thinks there is a separate link between C and A, so it corrects its table and changes infinity to 3 (1 for B to C and 2 for C to A, as C said). After a time again routers exchange their routing table. When C receives B’ routing table it see that B has changed weight of its link to A from 1 to 3,so it update its table and changes the weight of link to A to 4 (1 for C to B and 3 for B to A, as B said). This process loops until all nodes find out that the weight of link to A is infinity. This situation is shown in figure 8.In this way experts say DV algorithms have a slow convergence rate.

	B	C	D
Sum of the weight to A after link cut	,A	2,B	3,C
Sum of the weight to A after first updating	3,C	2,B	3,C
Sum of the weight to A after second updating	3,C	4,B	3,C
Sum of the weight to A after third updating	5,C	4,B	5,C
Sum of the weight to A after 4th updating	5,C	6,B	5,C
Sum of the weight to A after 5th updating	7,C	6,B	7,C
Sum of the weight to A after nth updating	…….	……	…….

Figure 8.Count to infinity problem

One way for solving this problem is that when routers want to send information to their neighbors, don’t send the information that is related to destinations that that neighbors are only way to link to them. For example in this case C shouldn’t give any information to B about A. Because B is the only way to A.

Hierarchical Routing:
As you see, in both LS and DV algorithms, every router has to save some information about other routers. When the network size grows and number of routers in network and consequently size of routing tables increase, routers can’t handle network traffic as efficient as they should. (Today there are more than 100000 routers in Internet). So we use hierarchical routing to overcome this problem. Let us examine this subject with an example:
Imagine a network with a graph shown in figure 10.we use DV algorithms to find best routes between nodes, so in this condition, every node of network, has to save a routing table with 17 record. Figure 9 shows a typical routing table for A.