How Routing Algorithms Work - Notes, Computer, Engineering, Semester Notes | EduRev

: How Routing Algorithms Work - Notes, Computer, Engineering, Semester Notes | EduRev

 Page 1


How Routing Algorithms Work 
by Roozbeh Razavi 
If you have read the HowStuffWorks article How Routers Work, then you know that a router is 
used to manage network traffic and find the best route for sending packets. But have you ever 
thought about how routers do this? Routers need to have some information about network status 
in order to make decisions regarding how and where to send packets. But how do they gather this 
information?  
In this edition of HowStuffWorks, we'll find out precisely what information is used by routers in 
determining where to send a packet.  
The Basics 
Routers use routing algorithms to find the best route to a destination. When we say "best 
route," we consider parameters like the number of hops (the trip a packet takes from one router 
or intermediate point to another in the network), time delay and communication cost of packet 
transmission.  
 
Based on how routers gather information about the structure of a network and their analysis of 
information to specify the best route, we have two major routing algorithms: global routing 
algorithms and decentralized routing algorithms. In decentralized routing algorithms, each 
router has information about the routers it is directly connected to -- it doesn't know about every 
router in the network. These algorithms are also known as DV (distance vector) algorithms. In 
global routing algorithms, every router has complete information about all other routers in the 
network and the traffic status of the network. These algorithms are also known as LS (link state) 
algorithms. We'll discuss LS algorithms in the next section.  
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, it first sends a "HELLO" packet over network. Each router 
that receives this packet replies with a message that contains its IP address.  
2. Measure the delay time (or any other important parameters of the network, such as 
average traffic) for neighbor routers 
In order to do that, routers send echo packets over the network. Every router that 
Page 2


How Routing Algorithms Work 
by Roozbeh Razavi 
If you have read the HowStuffWorks article How Routers Work, then you know that a router is 
used to manage network traffic and find the best route for sending packets. But have you ever 
thought about how routers do this? Routers need to have some information about network status 
in order to make decisions regarding how and where to send packets. But how do they gather this 
information?  
In this edition of HowStuffWorks, we'll find out precisely what information is used by routers in 
determining where to send a packet.  
The Basics 
Routers use routing algorithms to find the best route to a destination. When we say "best 
route," we consider parameters like the number of hops (the trip a packet takes from one router 
or intermediate point to another in the network), time delay and communication cost of packet 
transmission.  
 
Based on how routers gather information about the structure of a network and their analysis of 
information to specify the best route, we have two major routing algorithms: global routing 
algorithms and decentralized routing algorithms. In decentralized routing algorithms, each 
router has information about the routers it is directly connected to -- it doesn't know about every 
router in the network. These algorithms are also known as DV (distance vector) algorithms. In 
global routing algorithms, every router has complete information about all other routers in the 
network and the traffic status of the network. These algorithms are also known as LS (link state) 
algorithms. We'll discuss LS algorithms in the next section.  
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, it first sends a "HELLO" packet over network. Each router 
that receives this packet replies with a message that contains its IP address.  
2. Measure the delay time (or any other important parameters of the 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 it takes the packets to reach 
the destination and the time it takes the receiver to process it and reply.  
3. Broadcast its information over the network for other routers and receive the other routers' 
information 
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 the network.  
4. Using an appropriate algorithm, identify the best route between two nodes of the network
In this step, routers choose the best route to every node. They do this using an algorithm, 
such as the Dijkstra shortest path algorithm. In this algorithm, a router, based on 
information that has been collected from other routers, builds a graph of the network. This 
graph shows the location of routers in the network and their links to each other. Every link 
is labeled with a number called the weight or cost. This number is a function of delay 
time, average traffic, and sometimes simply the number of hops between nodes. For 
example, if there are two links between a node and a destination, the router chooses the 
link with the lowest weight.  
The Dijkstra algorithm goes through these steps:  
1. The router builds a graph of the network and identifies source and destination nodes, as 
V1 and V2 for example. Then it builds a matrix, called the "adjacency matrix." In this 
matrix, a coordinate indicates weight. For example, [i, j] is the weight of a link between Vi 
and Vj. If there is no direct link between Vi and Vj, this weight is identified as "infinity."  
2. The router builds a status record set for every node on the network. The record contains 
three fields:  
• Predecessor field - The first field shows the previous node.  
• Length field - The second field shows the sum of the weights from the source to 
that node.  
• Label field - The last field shows the status of node. Each node can have one 
status mode: "permanent" or "tentative."  
3. The router initializes the parameters of the status record set (for all nodes) and sets their 
length to "infinity" and their label to "tentative."  
4. The router sets a T-node. For example, if V1 is to be the source T-node, the router 
changes V1's label to "permanent." When a label changes to "permanent," it never 
changes again. A T-node is an agent and nothing more.  
5. The router updates the status record set for all tentative nodes that are directly linked to 
the source T-node.  
6. The router looks at all of the tentative nodes and chooses the one whose weight to V1 is 
lowest. That node is then the destination T-node.  
7. If this node is not V2 (the intended destination), the router goes back to step 5.  
8. If this node is V2, the router extracts its previous node from the status record set and 
does this until it arrives at V1. This list of nodes shows the best route from V1 to V2.  
These steps are shown below as a flowchart.  
Page 3


How Routing Algorithms Work 
by Roozbeh Razavi 
If you have read the HowStuffWorks article How Routers Work, then you know that a router is 
used to manage network traffic and find the best route for sending packets. But have you ever 
thought about how routers do this? Routers need to have some information about network status 
in order to make decisions regarding how and where to send packets. But how do they gather this 
information?  
In this edition of HowStuffWorks, we'll find out precisely what information is used by routers in 
determining where to send a packet.  
The Basics 
Routers use routing algorithms to find the best route to a destination. When we say "best 
route," we consider parameters like the number of hops (the trip a packet takes from one router 
or intermediate point to another in the network), time delay and communication cost of packet 
transmission.  
 
Based on how routers gather information about the structure of a network and their analysis of 
information to specify the best route, we have two major routing algorithms: global routing 
algorithms and decentralized routing algorithms. In decentralized routing algorithms, each 
router has information about the routers it is directly connected to -- it doesn't know about every 
router in the network. These algorithms are also known as DV (distance vector) algorithms. In 
global routing algorithms, every router has complete information about all other routers in the 
network and the traffic status of the network. These algorithms are also known as LS (link state) 
algorithms. We'll discuss LS algorithms in the next section.  
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, it first sends a "HELLO" packet over network. Each router 
that receives this packet replies with a message that contains its IP address.  
2. Measure the delay time (or any other important parameters of the 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 it takes the packets to reach 
the destination and the time it takes the receiver to process it and reply.  
3. Broadcast its information over the network for other routers and receive the other routers' 
information 
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 the network.  
4. Using an appropriate algorithm, identify the best route between two nodes of the network
In this step, routers choose the best route to every node. They do this using an algorithm, 
such as the Dijkstra shortest path algorithm. In this algorithm, a router, based on 
information that has been collected from other routers, builds a graph of the network. This 
graph shows the location of routers in the network and their links to each other. Every link 
is labeled with a number called the weight or cost. This number is a function of delay 
time, average traffic, and sometimes simply the number of hops between nodes. For 
example, if there are two links between a node and a destination, the router chooses the 
link with the lowest weight.  
The Dijkstra algorithm goes through these steps:  
1. The router builds a graph of the network and identifies source and destination nodes, as 
V1 and V2 for example. Then it builds a matrix, called the "adjacency matrix." In this 
matrix, a coordinate indicates weight. For example, [i, j] is the weight of a link between Vi 
and Vj. If there is no direct link between Vi and Vj, this weight is identified as "infinity."  
2. The router builds a status record set for every node on the network. The record contains 
three fields:  
• Predecessor field - The first field shows the previous node.  
• Length field - The second field shows the sum of the weights from the source to 
that node.  
• Label field - The last field shows the status of node. Each node can have one 
status mode: "permanent" or "tentative."  
3. The router initializes the parameters of the status record set (for all nodes) and sets their 
length to "infinity" and their label to "tentative."  
4. The router sets a T-node. For example, if V1 is to be the source T-node, the router 
changes V1's label to "permanent." When a label changes to "permanent," it never 
changes again. A T-node is an agent and nothing more.  
5. The router updates the status record set for all tentative nodes that are directly linked to 
the source T-node.  
6. The router looks at all of the tentative nodes and chooses the one whose weight to V1 is 
lowest. That node is then the destination T-node.  
7. If this node is not V2 (the intended destination), the router goes back to step 5.  
8. If this node is V2, the router extracts its previous node from the status record set and 
does this until it arrives at V1. This list of nodes shows the best route from V1 to V2.  
These steps are shown below as a flowchart.  
 
 
We will use this algorithm as an example on the next page.  
Example: Dijkstra Algorithm 
Here we want to find the best route between A and E (see below). You can see that there are six 
possible routes between A and E (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE), and it's obvious 
that ABDE is the best route because its weight is the lowest. 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 the image below, 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 the -
-> symbol).  
 
 
Page 4


How Routing Algorithms Work 
by Roozbeh Razavi 
If you have read the HowStuffWorks article How Routers Work, then you know that a router is 
used to manage network traffic and find the best route for sending packets. But have you ever 
thought about how routers do this? Routers need to have some information about network status 
in order to make decisions regarding how and where to send packets. But how do they gather this 
information?  
In this edition of HowStuffWorks, we'll find out precisely what information is used by routers in 
determining where to send a packet.  
The Basics 
Routers use routing algorithms to find the best route to a destination. When we say "best 
route," we consider parameters like the number of hops (the trip a packet takes from one router 
or intermediate point to another in the network), time delay and communication cost of packet 
transmission.  
 
Based on how routers gather information about the structure of a network and their analysis of 
information to specify the best route, we have two major routing algorithms: global routing 
algorithms and decentralized routing algorithms. In decentralized routing algorithms, each 
router has information about the routers it is directly connected to -- it doesn't know about every 
router in the network. These algorithms are also known as DV (distance vector) algorithms. In 
global routing algorithms, every router has complete information about all other routers in the 
network and the traffic status of the network. These algorithms are also known as LS (link state) 
algorithms. We'll discuss LS algorithms in the next section.  
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, it first sends a "HELLO" packet over network. Each router 
that receives this packet replies with a message that contains its IP address.  
2. Measure the delay time (or any other important parameters of the 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 it takes the packets to reach 
the destination and the time it takes the receiver to process it and reply.  
3. Broadcast its information over the network for other routers and receive the other routers' 
information 
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 the network.  
4. Using an appropriate algorithm, identify the best route between two nodes of the network
In this step, routers choose the best route to every node. They do this using an algorithm, 
such as the Dijkstra shortest path algorithm. In this algorithm, a router, based on 
information that has been collected from other routers, builds a graph of the network. This 
graph shows the location of routers in the network and their links to each other. Every link 
is labeled with a number called the weight or cost. This number is a function of delay 
time, average traffic, and sometimes simply the number of hops between nodes. For 
example, if there are two links between a node and a destination, the router chooses the 
link with the lowest weight.  
The Dijkstra algorithm goes through these steps:  
1. The router builds a graph of the network and identifies source and destination nodes, as 
V1 and V2 for example. Then it builds a matrix, called the "adjacency matrix." In this 
matrix, a coordinate indicates weight. For example, [i, j] is the weight of a link between Vi 
and Vj. If there is no direct link between Vi and Vj, this weight is identified as "infinity."  
2. The router builds a status record set for every node on the network. The record contains 
three fields:  
• Predecessor field - The first field shows the previous node.  
• Length field - The second field shows the sum of the weights from the source to 
that node.  
• Label field - The last field shows the status of node. Each node can have one 
status mode: "permanent" or "tentative."  
3. The router initializes the parameters of the status record set (for all nodes) and sets their 
length to "infinity" and their label to "tentative."  
4. The router sets a T-node. For example, if V1 is to be the source T-node, the router 
changes V1's label to "permanent." When a label changes to "permanent," it never 
changes again. A T-node is an agent and nothing more.  
5. The router updates the status record set for all tentative nodes that are directly linked to 
the source T-node.  
6. The router looks at all of the tentative nodes and chooses the one whose weight to V1 is 
lowest. That node is then the destination T-node.  
7. If this node is not V2 (the intended destination), the router goes back to step 5.  
8. If this node is V2, the router extracts its previous node from the status record set and 
does this until it arrives at V1. This list of nodes shows the best route from V1 to V2.  
These steps are shown below as a flowchart.  
 
 
We will use this algorithm as an example on the next page.  
Example: Dijkstra Algorithm 
Here we want to find the best route between A and E (see below). You can see that there are six 
possible routes between A and E (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE), and it's obvious 
that ABDE is the best route because its weight is the lowest. 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 the image below, 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 the -
-> symbol).  
 
 
2. In this step, you see that the status record set of tentative nodes directly linked to T-node 
(B, C) has been changed. Also, since B has less weight, it has been chosen as T-node 
and its label has changed to permanent (see below).  
 
 
3. In this step, like in 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 its label has changed to permanent (see below).  
 
 
4. In this step, we don't have any tentative nodes, so we just identify the next T-node. Since 
E has the least weight, it has been chosen as T-node.  
 
 
5. E is the destination, so we stop here.  
We are at end! Now we have to identify the route. The previous node of E is D, and the previous 
node of D is B, and B's previous node is A. So the best route is ABDE. In this case, the total 
weigh is 4 (1+2+1).  
Although this algorithm works well, it's so complicated that it may take a long time for routers to 
process it, and the efficiency of the network fails. Also, if a router gives the wrong information to 
other routers, all routing decisions will be ineffective. To understand this algorithm better, here is 
the source of program written by C:  
 
#define MAX_NODES 1024        /* maximum number of nodes */ 
Page 5


How Routing Algorithms Work 
by Roozbeh Razavi 
If you have read the HowStuffWorks article How Routers Work, then you know that a router is 
used to manage network traffic and find the best route for sending packets. But have you ever 
thought about how routers do this? Routers need to have some information about network status 
in order to make decisions regarding how and where to send packets. But how do they gather this 
information?  
In this edition of HowStuffWorks, we'll find out precisely what information is used by routers in 
determining where to send a packet.  
The Basics 
Routers use routing algorithms to find the best route to a destination. When we say "best 
route," we consider parameters like the number of hops (the trip a packet takes from one router 
or intermediate point to another in the network), time delay and communication cost of packet 
transmission.  
 
Based on how routers gather information about the structure of a network and their analysis of 
information to specify the best route, we have two major routing algorithms: global routing 
algorithms and decentralized routing algorithms. In decentralized routing algorithms, each 
router has information about the routers it is directly connected to -- it doesn't know about every 
router in the network. These algorithms are also known as DV (distance vector) algorithms. In 
global routing algorithms, every router has complete information about all other routers in the 
network and the traffic status of the network. These algorithms are also known as LS (link state) 
algorithms. We'll discuss LS algorithms in the next section.  
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, it first sends a "HELLO" packet over network. Each router 
that receives this packet replies with a message that contains its IP address.  
2. Measure the delay time (or any other important parameters of the 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 it takes the packets to reach 
the destination and the time it takes the receiver to process it and reply.  
3. Broadcast its information over the network for other routers and receive the other routers' 
information 
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 the network.  
4. Using an appropriate algorithm, identify the best route between two nodes of the network
In this step, routers choose the best route to every node. They do this using an algorithm, 
such as the Dijkstra shortest path algorithm. In this algorithm, a router, based on 
information that has been collected from other routers, builds a graph of the network. This 
graph shows the location of routers in the network and their links to each other. Every link 
is labeled with a number called the weight or cost. This number is a function of delay 
time, average traffic, and sometimes simply the number of hops between nodes. For 
example, if there are two links between a node and a destination, the router chooses the 
link with the lowest weight.  
The Dijkstra algorithm goes through these steps:  
1. The router builds a graph of the network and identifies source and destination nodes, as 
V1 and V2 for example. Then it builds a matrix, called the "adjacency matrix." In this 
matrix, a coordinate indicates weight. For example, [i, j] is the weight of a link between Vi 
and Vj. If there is no direct link between Vi and Vj, this weight is identified as "infinity."  
2. The router builds a status record set for every node on the network. The record contains 
three fields:  
• Predecessor field - The first field shows the previous node.  
• Length field - The second field shows the sum of the weights from the source to 
that node.  
• Label field - The last field shows the status of node. Each node can have one 
status mode: "permanent" or "tentative."  
3. The router initializes the parameters of the status record set (for all nodes) and sets their 
length to "infinity" and their label to "tentative."  
4. The router sets a T-node. For example, if V1 is to be the source T-node, the router 
changes V1's label to "permanent." When a label changes to "permanent," it never 
changes again. A T-node is an agent and nothing more.  
5. The router updates the status record set for all tentative nodes that are directly linked to 
the source T-node.  
6. The router looks at all of the tentative nodes and chooses the one whose weight to V1 is 
lowest. That node is then the destination T-node.  
7. If this node is not V2 (the intended destination), the router goes back to step 5.  
8. If this node is V2, the router extracts its previous node from the status record set and 
does this until it arrives at V1. This list of nodes shows the best route from V1 to V2.  
These steps are shown below as a flowchart.  
 
 
We will use this algorithm as an example on the next page.  
Example: Dijkstra Algorithm 
Here we want to find the best route between A and E (see below). You can see that there are six 
possible routes between A and E (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE), and it's obvious 
that ABDE is the best route because its weight is the lowest. 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 the image below, 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 the -
-> symbol).  
 
 
2. In this step, you see that the status record set of tentative nodes directly linked to T-node 
(B, C) has been changed. Also, since B has less weight, it has been chosen as T-node 
and its label has changed to permanent (see below).  
 
 
3. In this step, like in 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 its label has changed to permanent (see below).  
 
 
4. In this step, we don't have any tentative nodes, so we just identify the next T-node. Since 
E has the least weight, it has been chosen as T-node.  
 
 
5. E is the destination, so we stop here.  
We are at end! Now we have to identify the route. The previous node of E is D, and the previous 
node of D is B, and B's previous node is A. So the best route is ABDE. In this case, the total 
weigh is 4 (1+2+1).  
Although this algorithm works well, it's so complicated that it may take a long time for routers to 
process it, and the efficiency of the network fails. Also, if a router gives the wrong information to 
other routers, all routing decisions will be ineffective. To understand this algorithm better, here is 
the source of program written by C:  
 
#define MAX_NODES 1024        /* maximum number of nodes */ 
#define INFINITY 1000000000      /* a number larger than every 
maximum path */ 
int n,dist[MAX_NODES][MAX_NODES];     /*dist[I][j] is the 
distance from i to j */ 
void shortest_path(int s,int t,int path[ ]) 
{struct state {                          /* the path being worked on */ 
int predecessor ;                     /*previous node */ 
int length                                /*length from source to this node*/ 
enum {permanent, tentative} label    /*label state*/ 
}state[MAX_NODES]; 
int I, k, min; 
struct state * 
                     p; 
for (p=&state[0];p < &state[n];p++){       /*initialize state*/ 
p->predecessor=-1 
p->length=INFINITY 
p->label=tentative; 
} 
state[t].length=0; state[t].label=permanent ; 
k=t ;                                                          /*k is the initial working 
node */ 
do{                                                            /* is  the better path from 
k? */ 
for I=0; I < n; I++)                                       /*this graph has n nodes 
*/ 
if (dist[k][I] !=0 && state[I].label==tentative){ 
            if (state[k].length+dist[k][I] < state[I].length){ 
         state[I].predecessor=k; 
         state[I].length=state[k].length + dist[k][I] 
      } 
} 
/* Find the tentatively labeled node with the smallest label. */ 
k=0;min=INFINITY; 
for (I=0;I < n;I++) 
     if(state[I].label==tentative && state[I].length < 
min)=state[I].length; 
     k=I; 
 } 
state[k].label=permanent 
}while (k!=s); 
/*Copy the path into output array*/ 
I=0;k=0 
Do{path[I++]=k;k=state[k].predecessor;} while (k > =0); 
} 
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 shows it the best route for 
any destination. A typical graph and routing table for router J is shown below.  
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!