1.0 Give forwarding tables for each of the switches S1-S4 in the following network with destinations A, B, C, D. For the next_hop column, give the neighbor on the appropriate link rather than the interface number.

A B C    S1S2S3   S4D 

2.0 Give forwarding tables for each of the switches S1-S4 in the following network with destinations A, B, C, D. Again, use the neighbor form of next_hop rather than the interface form. Try to keep the route to each destination as short as possible. What decision has to be made in this exercise that did not arise in the preceding exercise?

AS1S2B     DS4S3C 

2.5 In the network of the previous exercise, suppose that destinations directly connected to an immediate neighbor are always reached via that neighbor; eg S1s forwarding table will always include B,S2 and D,S4. Show that, no matter what next_hop entries are chosen for the diagonally opposite destinations (eg S1 to C), no routing loops will ever form. (Hint: the number of links to any diagonally opposite switch is always 2.)

2.7 Give forwarding tables for each of the switches A-E in the following network. Destinations are A-E themselves. Keep all route lengths the minimum possible (one hop for an immediate neighbor, two hops for everything else). If a destination is an immediate neighbor, you may list its next_hop as direct or localfor simplicity. Indicate destinations for which there is more than one choice for next_hop.

3.0 Consider the following arrangement of switches and destinations. Give forwarding tables (in neighbor form) for S1-S4 that includedefault forwarding entries; the default entries should point toward S5. Eliminate all table entries that are implied by the default entry (that is, if the default entry is to S3, eliminate all other entries for which the next hop is S3).

AS1  D   CS3S4S5    E BS2 

4.0 Four switches are arranged as below. The destinations are S1 through S4 themselves.

S1S2     S4S3 

(a). Give the forwarding tables for S1 through S4 assuming packets to adjacent nodes are sent along the connecting link, and packets to diagonally opposite nodes are sent clockwise.

(b). Give the forwarding tables for S1 through S4 assuming the S1S4 link is not used at all, not even for S1S4 traffic.

5.0 Suppose we have switches S1 through S4; the forwarding-table destinations are the switches themselves. The tables for S2 and S3 are as below, where the next_hop value is specified in neighbor form:

S2: S1,S1 S3,S3 S4,S3

S3: S1,S2 S2,S2 S4,S4

From the above we can conclude that S2 must be directly connected to both S1 and S3 as its table lists them as next_hops; similarly, S3 must be directly connected to S2 and S4.

(a). Must S1 and S4 be directly connected? If so, explain; if not, give a network in which there is no direct link between them, consistent with the tables above.

(b). Now suppose S3s table is changed to the following. Find a network layout consistent with these tables in which S1 and S4 are not directly connected.

S3: S1,S4 S2,S2 S4,S4

While the table for S4 is not given, you may assume that forwarding does work correctly. However, you should not assume that paths are the shortest possible; in particular, you should not assume that each switch will always reach its directly connected neighbors by using the direct connection.

6.0 (a) Suppose a network is as follows, with the only path from A to C passing through B:

... ABC ... 

Explain why a single routing loop cannot include both A and C.

(b). Suppose a routing loop follows the path AS₁S₂ ... S_nA, where none of the S_i are equal to A. Show that all the S_imust be distinct. (A corollary of this is that any routing loop created by datagram-forwarding either involves forwarding back and forth between a pair of adjacent switches, or else involves an actual graph cycle in the network topology; linear loops of length greater than 1 are impossible.)

7.0 Consider the following arrangement of switches:

S1S4S10AE     S2S5S11B     S3S6S12CDF 

Suppose S1-S6 have the forwarding tables below. For each destination A,B,C,D,E,F, suppose a packet is sent to the destination from S1. Give the switches it passes through, including the initial switch S1, up until the final switch S10-S12.

S1: (A,S4), (B,S2), (C,S4), (D,S2), (E,S2), (F,S4)

S2: (A,S5), (B,S5), (D,S5), (E,S3), (F,S3)

S3: (B,S6), (C,S2), (E,S6), (F,S6)

S4: (A,S10), (C,S5), (E,S10), (F,S5)

S5: (A,S6), (B,S11), (C,S6), (D,S6), (E,S4), (F,S2)

S6: (A,S3), (B,S12), (C,S12), (D,S12), (E,S5), (F,S12)