Computer Network | Routing and Routing Algorithms | Part-I

📌Highlights: Hi friends ! In this post I will discuss about the concept of adaptive routing in computer network including how many type of routing and concept of algorithm in routing.We are going to explain about following algorithm such as Isolated routing algorithm, Centralised routing algorithm, Distributed routing algorithm (such as: Bellman-ford algorithm / Distance vector routing algorithm / Ford-Fulkerson algorithm,Flloyd warshall Algorithm / All pair shortest path algorithm,Hierarchical Routing Algorithm, Link State Routing Algorithm,Broad Casting Routing Algorithm,Multi Casting Algorithm.

Routing is a process of selecting appropriate route for transferring data. The mechanism inside the router by which routing process is done is called routing algorithm.

Routing is classified into two parts:

1. Adaptive Routing.

2. Non Adaptive Routing.

Adaptive Routing:

In adaptive routing router can select new path according to our circumstances. It can select new path / route for each packet.

Suppose if load increases / decreases on network layer or we can say that load is change on network layer or any route or line is damaged than at that condition router can change / select new route to send their packet.

Non Adapting Routing:

In non adaptive routing router can not change / select new route in any condition whether route is damaged or load is changed to send their packet.

Adaptive Routing Algorithms:

We know that adaptive routing algorithm are classified into following:

1. Isolated adaptive routing algorithm.

2. Centralised adaptive routing algorithm.

3. Distributed adaptive routing algorithm.

Isolated adaptive routing algorithm:

First of all we discuss about isolated adaptive routing. In this type of adaptive routing any IMP ( Interface message processor) can not discuss to other IMP for taking decision about route.It takes individual decision for selection of route is called Isolated adaptive routing.

In this diagram one IMP is give and from this IMP there are three routes for three different destination such as Delhi,Mumbai,Calcutta and there are one queue is also present corresponding to each route in IMP where the packet are stored.

In isolated adaptive routing the procedure for delivering a packet through any route is that, when any packet comes in IMP then it first check which queue contain minimum number of packets after comparing all the queue. When it get the queue of minimum packets then it select there corresponding route and send message or packet by using that communication line.

Modify the isolated adaptive routing by adding Non adaptive features:

Now after adding non adaptive routing feature one  routing table is created at each IMP which is fixed.

for example; it is just like if you want to go for Delhi then you must find which is correct (less time and less cost).

That means which route/line contain minimum no of packets that line are selected.

We did this modification because  may be queue have a minimum number of packets and if we select it, if we follow that route then it may take longer or more cost but here we follow the same Will do!

But if we add non-adaptive method too, then we will have a route which if we follow, it will not be time consuming or costly.

Centralised Adaptive Routing:

In this process we can ask any authorised IMP or central agency for taking routing decision is called centralised adaptive agency.

In above diagram a network is show when many IMP's are present. Among al  IMP there is one central IMP which is known as routing control centre (RCC).At central condition of line  whether it is working or not . So that RCC have a huge database about the lines. On the basis of this information RCC creart a table for each IMP for particular interval that mean the table is exist for a particular interval of time. whether it is 1 hour or more. It is totally depends on system design (RCC). These table are dynamic not static.

Those IMP's and lines which are present closer to RCC have more traffic because information of all IMP's are passes through that lines.

Suppose line of IMP A contain only information of A but if we talk about line of IMP Z is contain information of Y,P,Q,R,X,O,H,I etc. So here traffic is much more than A.

Drawback:

1. Not Reliable: It is not reliable because if RCC fails then whole system will stop.

2. Inconsistent: Inconsistently occur when table of one IMP are modified where other IMP are not then at that time they can not communicate properly.

Distributed adaptive routing algorithm:

In this process any IMP can take decision by discussing any other IMP then it is called distributed adaptive routing.

There are following type of distributed adaptive routing algorithm:

1. Bellman-ford algorithm / Distance vector routing algorithm / Ford-Fulkerson algorithm:

Distance vector routing is one of the most popular dynamic routing algorithm generally used in modern computer networks.

Distance vector routing algorithm works by having each router maintain a routing table (i.e a vector) that contain one entry for each router in subnet.

Procedure for creation of routing table:

Here we are crating a table for finding best route from Y to V

We know that any IMP contain information of our adjacent /neighbour IMP.

For example here Y contain information of X,P,Z,W. So we create table for there four IMP's.

Explanation:

Let we understand the above tables, In first row we consider all the neighbour / adjacent of Y such as P,X,W,Z. 

Write all IMP's of subnet in first column like :P,Q,R,S,T,U,V,W,X,Y,Z,M.

now we understand how to read columns

 0 is time taken from P to P

10 is time taken from Q to P

20 is time taken from R to P

30 is time taken from S to P

and so on.....

Similarly for other columns

22 is time taken from P to X

32 is time taken from Q to X

16 is time taken from R to X

and so on...

In the same way we will read other columns such as W,Z.

We know the time to reach their neighbour from Y (given)

Such as: 

YP : Time to reach Y to P is 5.

YX: Time to reach Y to P is 6.

YW: Time to reach Y to P is 10.

YZ: Time to reach Y to P is 3.

Now we understand how to do entry in new table:

We have two column in new table such as

1. via(line)

2. Cost

In via column we will enter those IMP's form (P,X,W,Z) which have less cost (with respect to time).

In cost column we will enter cost (less cost ) w.r.t time.

Procedure to calculate the cost:

Cost(w.r.t time) to travel from Y to their adjacent / neighbour IMP + Cost to travel from Adjacent IMP to another IMP.

Such as : 

1. For P

Cost to travel from Y to P is 5

Cost to travel from P to P is 0

than the total cost will be (5 + 0=5)

2. For X

Cost to travel from Y to X is 6

Cost to travel from X to P is 22

than the total cost will be (6 + 22=28)

3. For W

Cost to travel from Y to W is 10

Cost to travel from W to P is 22

than the total cost will be (10 + 22=32)

4. For Z

Cost to travel from Y to Z is 3

Cost to travel from Z to P is 20

than the total cost will be (3 + 20=23)

Now compare all the above calculated costs such as (5,28,32,23) select the minimum cost from all i.e 5.

Now enter this cost 5 in new table in cost field and "P" in via field.

In the same way calculate the other entries in new table.

2. Flloyd warshall Algorithm / All pair shortest path algorithm:

In this algorithm weight is given in time or distance .Time show delivery of packet from one node to another.

Let we first understand adjacency matrix for unweighted graph and weighted graph.

Adjacency matrix for unweighted graph:

In this type of graph we see if their is direct link between two node the we write 1 in table otherwise 0.

Example:

Adjacency matrix for weighted graph:

In weighted graph we can write three type of values in their table such as 

Infinite for where no direct path is available but indirectly we can reach.

Zero for where no path is available.

Weight for where direct path is available.

Example:

If we take distance than it is non adaptive but if we take time than it is adaptive.

Now here in this algorithm we make adjacency cost matrix for every node / IMP's.

Basic Cost Matrix will be:

Let we know how we create routing table in each IMP's using this algorithm:

Routing table for IMP-1:

This table is for IMP -1. It shows when we traverse from one IMP to another then we go from IMP-1 ,like when we go from IMP-2 to IMP-3 then we must go through IMP-1. (such as path is :2-1-3). If any direct path is available than then compare cost of direct cost to indirect cost and consider minimum cost in table. such as:

Direct cost (2-3) :11

Indirect cost (2-1-3) : 9

Here 9 is the minimum cost so we consider it.

Routing table for IMP-2:

Direct cost (1-3) : 4

Indirect cost (1-2-3) : 14

Here 4 is the minimum cost so we consider it.

Routing table for IMP-2:

Routing table for IMP-3:

Direct cost (2-1) : 5

Indirect cost (2-3-1) : 17

Here 5 is the minimum cost so we consider it.

These table show the shortest path among all IMP's

3. Hierarchical Routing Algorithm:

In hierarchical routing we can reduce the size of routing table. Suppose we have 720 IMP's in network than in this case we used to create 720 entries in routing table (fr collecting information for each IMP).

So for solving this problem. Total IMP's are divided into region and each region is further divided into cluster and each cluster is a collection of IMP's.

Let number of region =R

Number of cluster per region = C

Number of IMP's per cluster = I

If 720 IMP's in network , suppose if we have 24 cluster in a region, than each cluster contain 720/24=30 IMP's in each cluster.

Each cluster contain information of one IMP's and also contain information of one IMP in neighbour cluster.

Let 

R=8

C=9 per region

I=10 per cluster

Total IMP's = 8 X 9 X 10 = 720 IMP's

In the case of 3-dimension addressing.

If R=8  C=9  I=10

Total table size = 10+8+7

Just like Book → Page No → Line No → Word No

In general way :

Size of routing table is :

= I + (C-1) + (R-1)

= 10 + (9-1) + (R-1)

= 10 + 8 + 7

        OR

Size of table = I + C + R -2

Total IMP = I . C . R

= 10 X 8 X 7 = 720

Note :

If N is total IMP's and we are using 3-dimension addressing when (N=512) than what will be the value of I,C,R that will minimise the table size. 

For minimising I=C=R then the size of routing table will be minimum.

I³=N

I=N^1/3

Example If N=512

I=(512)^1/3 =8

That means  I=8, C=8, R=8

In Case if we are not getting complete number

Example : If N=612

I=(720)^1/3=8.9628

then we take near value whose product is equal to 612

i.e 8 X 9 X 10 =720

so,  I=8, C=9, R=10

Note : For 3D → I = N^1/3 = I.C.R

               4D → I = N^1/4 = I.C.R.2

4. Link State Routing Algorithm:

It is adaptive routing technique and distributed control.

In link state routing algorithm the routing table is developed with the use of distributed control adaptive mechanism. Each and every IMP suppose to collect link information from all its neighbours in regular interval of time and band on information collected routing table is developed.

Total number of three steps are required for above operation.

1. Learning About Neighbour: When ever router is initialise or routed it has to learn that who are the neighbour of it and what are their IP address.

It will send HELLO packet to each and every point to point line passing from it.Other side station suppose send its address as a reply of HELLO packet.

2. Measuring the line cost: Router suppose to know the delay in each point to point link passing from it. This can be accomplished by sending echo packet to all its neighbours. There station and neighbour suppose to immediately send back this echo packet back to original station.The total time of getting back of echo packet is measured and divided by two to get one way delay.

3. Building Link State Packets: Each IMP's of the router suppose to built a packet which contain information regarding delay in its all adjoining links.

4. Distribution of Link state packet: Link state packet developed by each and every IMP will be distributed through their respective neighbours in regular internal interval of time. If time is small than minor change in network condition can be adapted. Because of large number of link state packet per unit of time.

If distribution of link state packet is after large time than channel utilisation is high but changes in condition of the network can not be property adaptive.

5. Broadcast Routing Algorithm :

Sending a packet to all destination simultaneously is called broadcasting. It is used in the application where host need to send messages to many other host, for example, distribution of weather report, stock market, T.V and radio programs. 

Construct a sink tree / spanning tree for node A.

Spanning Tree: A tree in which all node are connected but no cycle is created is called spanning tree.

Here we connect minimum number of hopes.

6. Multi Casting  Routing Algorithm :

The procedure of sending a message to the group of widely separate process in network is called multi casting.

The message are send to well define group that are numerically large in size but small as compared to the network as a whole.

Example: different process work together in group as distributed database system. The routing algorithm is called multicast routing.

Multicast routing concerned with the fact that when a process join a group it must inform its host. It is important that router know about which of their host belong to which group. As the router tell their neighbour the information propagate through the subnet.

Example:

Construct a multi-casting spanning tree for router C in the subnet below for a group with member at routers A,B,C,D,E,F,I and K

Now Spanning tree for Router C is:

Advantage and Disadvantage of multi casting routing: 

Advantage: Unlike broad casting, it offers cheap way of sending message to large size group with efficiency. Thus it offers a cheap and efficient way of routing a message.

Disadvantage: It serve poorly to large network for which a big amount of tree are required. Thus very large storage may be need to store all trees.

Now it is the end of explanation of following algorithm such as Isolated routing algorithm, Centralised routing algorithm, Distributed routing algorithm (such as: Bellman-ford algorithm / Distance vector routing algorithm / Ford-Fulkerson algorithm,Flloyd warshall Algorithm / All pair shortest path algorithm,Hierarchical Routing Algorithm, Link State Routing Algorithm,Broad Casting Routing Algorithm,Multi Casting Algorithm. 

I hope it helpful for you, We will meet in next post about Non Adaptive Routing Algorithms till continue reading....