9.8: Epilog and Exercises
 Page ID
 11200
At this point we have concluded the basics of IP routing, involving routing within large (relatively) homogeneous organizations such as multisite corporations or Internet Service Providers. Every router involved must agree to run the same protocol, and must agree to a uniform assignment of link costs.
At the very largest scales, these requirements are impractical. The next chapter is devoted to this issue of verylargescale IP routing, eg on the global Internet.
9.9 Exercises
Exercises are given fractional (floating point) numbers, to allow for interpolation of new exercises. Exercise 2.5 is distinct, for example, from exercises 2.0 and 3.0. Exercises marked with a ♢ have solutions or hints at 24.8 Solutions for RoutingUpdate Algorithms.
1.0. Suppose the network is as follows, where distancevector routing update is used. Each link has cost 1, and each router has entries in its forwarding table only for its immediate neighbors (so A’s table contains ⟨B,B,1⟩, ⟨D,D,1⟩ and B’s table contains ⟨A,A,1⟩, ⟨C,C,1⟩).
2.0. Now suppose the configuration of routers has the link weights shown below.
2.5.♢ A router R has the following distancevector table:
destination 
cost 
next hop 

A 
2 
R1 
B 
3 
R2 
C 
4 
R1 
D 
5 
R3 
R now receives the following report from R1; the cost of the R–R1 link is 1.
destination 
cost 

A 
1 
B 
2 
C 
4 
D 
3 
Give R’s updated table after it processes R1’s report. For each entry that changes, give a brief explanation
3.0. A router R has the following distancevector table:
destination 
cost 
next hop 

A 
5 
R1 
B 
6 
R1 
C 
7 
R2 
D 
8 
R2 
E 
9 
R3 
R now receives the following report from R1; the cost of the R–R1 link is 1.
destination 
cost 

A 
4 
B 
7 
C 
7 
D 
6 
E 
8 
F 
8 
Give R’s updated table after it processes R1’s report. For each entry that changes, give a brief explanation, in the style of 9.1.5 Example 4.
3.5. At the start of Example 3 (9.1.4 Example 3), we changed C’s routing table so that it reached D via A instead of via E: C’s entry ⟨D,E,2⟩ was changed to ⟨D,A,2⟩. This meant that C had a valid route to D at the start.
How might the scenario of Example 3 play out if C’s table had not been altered? Give a sequence of reports that leads to correct routing between D and E.
4.0. In the following exercise, AD are routers and the attached subnets N1N6, which are the ultimate destinations, are shown explicitly. In the case of N1 through N4, the links are the subnets. Routers still exchange distancevector reports with neighboring routers, as usual. In the tables requested below, if a router has a direct connection to a subnet, you may report the next_hop as “direct”, eg, from A’s table, ⟨N1,direct,0⟩
5.0. Suppose A, B, C, D and E are connected as follows. Each link has cost 1, and so each forwarding table is uniquely determined; B’s table is ⟨A,A,1⟩, ⟨C,C,1⟩, ⟨D,A,2⟩, ⟨E,C,2⟩. Distancevector routing update is used.
Now suppose the D–E link fails, and so D updates its entry for E to ⟨E,,∞⟩.
5.5. In the network below, A receives alternating reports about destination D from neighbors B and C. Suppose A uses a modified form of Rule 2 of 9.1.1 DistanceVector Update Rules, in which it updates its forwarding table whenever new cost c is less than or equal to c_{old}.
Explain why A’s forwarding entry for destination D never stabilizes.
6.0. Consider the network in 9.2.1.1 Split Horizon:, using distancevector routing updates. B and C’s table entries for destination D are shown. All link costs are 1.
Suppose the D–A link breaks and then these update reports occur:

A reports ⟨D,∞⟩ to B (as before)

C reports ⟨D,2⟩ to B (as before)

A now reports ⟨D,∞⟩ to C (instead of B reporting ⟨D,3⟩ to A)
7.0. Suppose the network of 9.2 DistanceVector SlowConvergence Problem is changed to the following. Distancevector update is used; again, the D–A link breaks.
8.0. Suppose the routers are A, B, C, D, E and F, and all link costs are 1. The distancevector forwarding tables for A and F are below. Give the network with the fewest links that is consistent with these tables. Hint: any destination reached at cost 1 is directly connected; if X reaches Y via Z at cost 2, then Z and Y must be directly connected.
A’s table
dest 
cost 
next_hop 

B 
1 
B 
C 
1 
C 
D 
2 
C 
E 
2 
C 
F 
3 
B 
F’s table
dest 
cost 
next_hop 

A 
3 
E 
B 
2 
D 
C 
2 
D 
D 
1 
D 
E 
1 
E 
9.0. (a) Suppose routers A and B somehow end up with respective forwardingtable entries ⟨D,B,n⟩ and ⟨D,A,m⟩, thus creating a routing loop. Explain why the loop may be removed more quickly if A and B both use poison reverse with split horizon (9.2.1.1 Split Horizon), versus if A and B use split horizon only.
(b). Suppose the network looks like the following. The A–B link is extremely slow.
Suppose A and B send reports to each other advertising their routes to D, and immediately afterwards the C–D link breaks and C reports to A and B that D is unreachable. After those unreachability reports from C are processed, A and B’s reports sent to each other before the break finally arrive. Explain why the network is now in the state described in part (a).
10.0. Suppose the distancevector algorithm is run on a network and no links break (so by the last paragraph of 9.1.1 DistanceVector Update Rules the next_hopincrease rule is never applied).
11.0. It was mentioned in 9.5 LinkState RoutingUpdate Algorithm that linkstate routing might give rise to an ephemeral routing loop. Give a concrete scenario illustrating creation (and then dissolution) of such a loop.
12.0. Use the ShortestPathFirst algorithm to find the shortest path from A to E in the network below. Show the sets R and T, and the node current, after each step.
13.0. Suppose you take a laptop, plug it into an Ethernet LAN, and connect to the same LAN via WiFi. From laptop to LAN there are now two routes. Which route will be preferred? How can you tell which way traffic is flowing? How can you configure your OS to prefer one path or another? (See also 7.9.5 ARP and multihomed hosts, 7 IP version 4 exercise 11.0, and 12 TCP Transport exercise 13.0.)