Sample Problems on Routing Algorithms (No Solutions will be posted)
1. Consider the following computer network where each node represents a router and the edge label is the corresponding link cost. All links are bi-directional. Use Dijkstra algorithm to find the shortest path from router “A” to every other router in the network.
1RR2
3
B
D
A
R 1
4
4
R 1
1
R 1
1
1
R 1
1
C
E
1
2. Consider the following network. Distance vector routing is used with the “minimum delay criteria” used. The following vectors have just come in to router C
From B: (5, 0, 8, 12, 6, 2)
From D: (16, 12, 6, 0, 9, 10)
From E: (7, 6, 3, 9, 0, 4)
The initial measured delays to routers B, D and E are 6, 3 and 5 respectively. What is C’s new routing table? The routing Table should have 3 columns, namely: Destination Router, Delay, and Next Hop Router. Show the details of your work. I am not interested in answers only.
B
C
D
F
A
E
F
3. For the network shown below, assume that the Bellman-Ford routing algorithm is used. Assume that initially each router knows the distance to its neighbors. Illustrate the following:
Initial routing table at node “1”
Final routing table at node”1″
Show clearly, how the algorithm would react if there is a failure in the link
connecting nodes “3” and node “6”
Note: the routing table at R1 should have three columns, namely: Destination, Cost and Next Hop.
521
2
4
3
1
6
3
1
4
3
2
2
5
4. Consider the following computer network where each node represents a router and the edge label is the corresponding link cost. Use Dijkstra algorithm to find the shortest path from router B to every other router in the network. Show your work step-by-step. Now suppose the link between router D and router F is down. Describe how the link-state protocol handles it. What would be the shortest path between router B and router G?
B1E 251
332
ACFH
4
627 D1G