9.9: Epilog and Exercises

At this point we have concluded the basics of IP routing, involving routing within large (relatively) homogeneous organizations such as multi-site 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 very-large-scale 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 Routing-Update Algorithms.

1.0. Suppose the network is as follows, where distance-vector 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⟩).

(a). Suppose each node creates a report from its initial configuration and sends that to each of its neighbors. What will each node’s forwarding table be after this set of exchanges? The exchanges, in other words, are all conducted simultaneously; each node first sends out its own report and then processes the reports arriving from its two neighbors.

(b). What will each node’s table be after the simultaneous-and-parallel exchange process of part (a) is repeated a second time?

Hint: you do not have to go through each exchange in detail; the only information added by an exchange is additional reachability information.

2.0. Now suppose the configuration of routers has the link weights shown below.

(a). As in the previous exercise, give each node’s forwarding table after each node exchanges with its immediate neighbors simultaneously and in parallel.

(b). How many iterations of such parallel exchanges will it take before C learns to reach F via B; that is, before it creates the entry ⟨F,B,11⟩? Count the answer to part (a) as the first iteration.

2.5.♢ A router R has the following distance-vector 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 distance-vector 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, A-D are routers and the attached subnets N1-N6, which are the ultimate destinations, are shown explicitly. In the case of N1 through N4, the links are the subnets. Routers still exchange distance-vector 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⟩

(a). Give the initial tables for A through D, before any distance-vector exchanges.

(b). Give the tables after each router A-D exchanges with its immediate neighbors simultaneously and in parallel.

(c). At the end of (b), what subnets are not known by what routers?

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⟩. Distance-vector routing update is used.

Now suppose the D–E link fails, and so D updates its entry for E to ⟨E,-,∞⟩.

(a). Give A’s table after D reports ⟨E,∞⟩ to A

(b). Give B’s table after A reports to B

(c). Give A’s table after B reports to A; note that B has an entry ⟨E,C,2⟩

(d). Give D’s table after A reports to D.

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 Distance-Vector 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 distance-vector 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)

(a). Give A, B and C’s forwarding-table records for destination D, including the cost, after these three reports.

(b). What additional reports (a pair should suffice) will lead to the formation of the routing loop?

(c). What (single) additional report will eliminate the possibility of the routing loop?

7.0. Suppose the network of 9.2 Distance-Vector Slow-Convergence Problem is changed to the following. Distance-vector update is used; again, the D–A link breaks.

(a). Explain why B’s report back to A, after A reports ⟨D,-,∞⟩, is now valid.

(b). Explain why hold down (9.2.1.3 Hold Down) will delay the use of the new route A–B–E–D.

8.0. Suppose the routers are A, B, C, D, E and F, and all link costs are 1. The distance-vector 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 forwarding-table 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 distance-vector algorithm is run on a network and no links break (so by the last paragraph of 9.1.1 Distance-Vector Update Rules the next_hop-increase rule is never applied).

(a). Prove that whenever A is B’s next_hop to destination D, then A’s cost to D is strictly less than B’s. Hint: assume that if this claim is true, then it remains true after any application of the rules in 9.1.1 Distance-Vector Update Rules. If the lower-cost rule is applied to B after receiving a report from A, resulting in a change to B’s cost to D, then one needs to show A’s cost is less than B’s, and also B’s new cost is less than that of any neighbor C that uses B as its next_hop to D.

(b). Use (a) to prove that no routing loops ever form.

11.0. It was mentioned in 9.5 Link-State Routing-Update Algorithm that link-state 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 Shortest-Path-First 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 Wi-Fi. 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.)