Question

How do we construct and maintain a routing table in a connectionless network - explain distance vector

Answer 1

Computer Network: Computer network is defined as connection between one or more system which is mainly used to share the peripheral devices( like printer), to share the files or for communication purpose etc.,

The connection between these computer can be constructed using any one of below method

i) Connection Oriented Service : - It is the communication service in which virtual connection is created before sending the packet over the network. It is more reliable. Routing is finalized before transmitting the data. it takes more time to transmit the data. All Packets follow the same path until the connection is disconnected.

ii) Connection less service : - In this service, packets are sent without creating any virtual connection over the network. It is less reliable. The routing is decided on the way while transmitting the data. It takes less time to transmit the data. Each packet is transmitted in different path.

There are n number of user using this computer network for there communication purpose, so we may have n number of protocols to ensure the connection national or world wide communication. To avoid this n number of rules for each network connection, we must develop one standard protocol which is followed by everyone.

ISO OSI model is a open system interconnection model developed by ISO in 1984. It transmitting the data from one system to another system by using these 7 layers. They are

1. Application layer
2. Presentation Layer
3. Session Layer
4. Transport Layer
5. Network Layer
6. Data Link Layer
7. Physical Layer.

From these layer now we are going to see function of Network layer.

Network Layer

Network Layer is responsible to find the routing of the packet from one network to another network by using some routing algorithm.

Routing Algorithms-

• Used to determine the routing of packets in a network.
• It has Classified into two parts based on the connection services

i. Nonadaptive algorithms or Static Routing Algorithm

• The routing decision is not based on the measurement or estimations of current traffic however the choice of the route is done in advance, and known as static routing. Connection Oriented Service mainly following these type of static algorithm method.
• Example : Shortest path Routing, Flooding

ii. Adaptive algorithms or Dynamic Routing Algorithm

• For these algorithms the routing decision can be changed if there are any changes in topology or traffic etc. This is called as dynamic routing. Connection Less Networks are using these algorithm method to forward the packet.
• Example Distance Vector Routing, Link State Routing

Now , we will discuss about distance vector routing.

Distance Vector Routing Algorithm-

Distance Vector Routing is a dynamic routing algorithm.

Steps-

Step-01:

Each router prepares its routing table. By their local knowledge. each router knows about-

• All the routers present in the network
• Distance to its neighboring routers

Step-02:

• Each router exchanges its distance vector with its neighboring routers.
• Each router prepares a new routing table using the distance vectors it has obtained from its neighbors.
• This step is repeated for (n-2) times if there are n routers in the network.
• After this, routing tables converge / become stable.

Distance Vector Routing Example-

Consider-

• There is a network consisting of 4 routers.
• The weights are mentioned on the edges.
• Weights could be distances or costs or delays.

Step-01:

Each router prepares its routing table using its local knowledge.

Routing table prepared by each router is shown below-

At Router A-

Destination	Distance	Next Hop
A	0	A
B	2	B
C	∞	–
D	1	D

At Router B-

Destination	Distance	Next Hop
A	2	A
B	0	B
C	3	C
D	7	D

At Router C-

Destination	Distance	Next Hop
A	∞	–
B	3	B
C	0	C
D	11	D

At Router D-

Destination	Distance	Next Hop
A	1	A
B	7	B
C	11	C
D	0	D

Step-02:

• Each router exchanges its distance vector obtained in Step-01 with its neighbors.
• After exchanging the distance vectors, each router prepares a new routing table.

This is shown below-

At Router A-

• Router A receives distance vectors from its neighbors B and D.
• Router A prepares a new routing table as-

• Cost of reaching destination B from router A = min { 2+0 , 1+7 } = 2 via B.
• Cost of reaching destination C from router A = min { 2+3 , 1+11 } = 5 via B.
• Cost of reaching destination D from router A = min { 2+7 , 1+0 } = 1 via D.

Explanation For Destination B Router A can reach the destination router B via its neighbor B or neighbor D. It chooses the path which gives the minimum cost. Cost of reaching router B from router A via neighbor B = Cost (A→B) + Cost (B→B)= 2 + 0 = 2 Cost of reaching router B from router A via neighbor D = Cost (A→D) + Cost (D→B) = 1 + 7 = 8 Since the cost is minimum via neighbor B, so router A chooses the path via B. It creates an entry (2, B) for destination B in its new routing table. Similarly, we calculate the shortest path distance to each destination router at every router.

Thus, the new routing table at router A is-

Destination	Distance	Next Hop
A	0	A
B	2	B
C	5	B
D	1	D

At Router B-

• Router B receives distance vectors from its neighbors A, C and D.
• Router B prepares a new routing table as-

• Cost of reaching destination A from router B = min { 2+0 , 3+∞ , 7+1 } = 2 via A.
• Cost of reaching destination C from router B = min { 2+∞ , 3+0 , 7+11 } = 3 via C.
• Cost of reaching destination D from router B = min { 2+1 , 3+11 , 7+0 } = 3 via A.

Thus, the new routing table at router B is-

Destination	Distance	Next Hop
A	2	A
B	0	B
C	3	C
D	3	A

At Router C-

• Router C receives distance vectors from its neighbors B and D.
• Router C prepares a new routing table as-

• Cost of reaching destination A from router C = min { 3+2 , 11+1 } = 5 via B.
• Cost of reaching destination B from router C = min { 3+0 , 11+7 } = 3 via B.
• Cost of reaching destination D from router C = min { 3+7 , 11+0 } = 10 via B.

Thus, the new routing table at router C is-

Destination	Distance	Next Hop
A	5	B
B	3	B
C	0	C
D	10	B

At Router D-

• Router D receives distance vectors from its neighbors A, B and C.
• Router D prepares a new routing table as-

• Cost of reaching destination A from router D = min { 1+0 , 7+2 , 11+∞ } = 1 via A.
• Cost of reaching destination B from router D = min { 1+2 , 7+0 , 11+3 } = 3 via A.
• Cost of reaching destination C from router D = min { 1+∞ , 7+3 , 11+0 } = 10 via B.

Thus, the new routing table at router D is-

Destination	Distance	Next Hop
A	1	A
B	3	A
C	10	B
D	0	D

Step-03:

• Each router exchanges its distance vector obtained in Step-02 with its neighboring routers.
• After exchanging the distance vectors, each router prepares a new routing table.

This is shown below-

At Router A-

• Router A receives distance vectors from its neighbors B and D.
• Router A prepares a new routing table as-

• Cost of reaching destination B from router A = min { 2+0 , 1+3 } = 2 via B.
• Cost of reaching destination C from router A = min { 2+3 , 1+10 } = 5 via B.
• Cost of reaching destination D from router A = min { 2+3 , 1+0 } = 1 via D.

Thus, the new routing table at router A is-

Destination	Distance	Next Hop
A	0	A
B	2	B
C	5	B
D	1	D

At Router B-

• Router B receives distance vectors from its neighbors A, C and D.
• Router B prepares a new routing table as-

• Cost of reaching destination A from router B = min { 2+0 , 3+5 , 3+1 } = 2 via A.
• Cost of reaching destination C from router B = min { 2+5 , 3+0 , 3+10 } = 3 via C.
• Cost of reaching destination D from router B = min { 2+1 , 3+10 , 3+0 } = 3 via A.

Thus, the new routing table at router B is-

Destination	Distance	Next Hop
A	2	A
B	0	B
C	3	C
D	3	A

At Router C-

• Router C receives distance vectors from its neighbors B and D.
• Router C prepares a new routing table as-

• Cost of reaching destination A from router C = min { 3+2 , 10+1 } = 5 via B.
• Cost of reaching destination B from router C = min { 3+0 , 10+3 } = 3 via B.
• Cost of reaching destination D from router C = min { 3+3 , 10+0 } = 6 via B.

Thus, the new routing table at router C is-

Destination	Distance	Next Hop
A	5	B
B	3	B
C	0	C
D	6	B

At Router D-

• Router D receives distance vectors from its neighbors A, B and C.
• Router D prepares a new routing table as-

• Cost of reaching destination A from router D = min { 1+0 , 3+2 , 10+5 } = 1 via A.
• Cost of reaching destination B from router D = min { 1+2 , 3+0 , 10+3 } = 3 via A.
• Cost of reaching destination C from router D = min { 1+5 , 3+3 , 10+0 } = 6 via A.

Thus, the new routing table at router D is-

Destination	Distance	Next Hop
A	1	A
B	3	A
C	6	A
D	0	D

These will be the final routing tables at each router.