• 1.18 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.1 Solutions for An Overview of Networks.

    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
    │         │         │
    S1────────S2────────S3
              │
              │
              S4───D
    

    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?

    A───S1──────S2───B
        │       │
        │       │
    D───S4──────S3───C
    

    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 S1’s forwarding table will always include ⟨B,S2⟩ and ⟨D,S4⟩. This leaves only routes to the diagonally opposite nodes undetermined (eg S1 to C). Show that, no matter which next_hop entries are chosen for the diagonally opposite destinations, no routing loops can ever be formed. (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 local for simplicity. Indicate destinations for which there is more than one choice for next_hop.

    fivenodes.svg

    3.0. Consider the following arrangement of switches and destinations. Give forwarding tables (in neighbor form) for S1-S4 that include default forwarding entries; the default entries should point toward S5. The default entries will thus automatically forward to the “possible other destinations” shown below right.

    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).

    A───S1
        │         D
        │         │
    C───S3────────S4─────────S5────... possible other destinations
        │         │
        │         E
    B───S2
    

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

    S1──────S2
    │       │
    │       │
    S4──────S3
    
    (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 S1–S4 link is not used at all, not even for S1⟷S4 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). The given tables are consistent with the network diagrammed in exercise 4.0. Are the tables also consistent with a network in which S1 and S4 are not directly connected? If so, give such a network; if not, explain why S1 and S4 must be connected.
    (b). Now suppose S3’s table is changed to the following. Find a network layout consistent with these tables in which S1 and S4 are not directly connected. Do not add additional switches.
    S3: ⟨S1,S4⟩ ⟨S2,S2⟩ ⟨S4,S4⟩