Computer Networking • CS 514

Test 3, 5 March 2014

This test has six questions. The test runs the entire period, ending at 6:20. When you finish the test, you may leave.

1. Keeping in mind that giving an example of X is not defining X, briefly (in one or two sentences, 25 to 30 words) define:

   • Multicast routing

   • Autonomous system

   • Dynamic routing algorithm

   • Tunneling

   • Head-of-line blocking

   ---

   • Multicast routing:

   Routing in which PDUs are copied and distributed efficiently to a subset of hosts.

   • Autonomous system:

   A collection of networks under the authority of a single entity.

   • Dynamic routing algorithm:

   A routing algorithm that continuously recomputes the network model to adjust for changes in network conditions.

   • Tunneling:

   Encapsulating one PDU as the payload of another PDU.

   • Head-of-line blocking:

   Blocking that occurs when a PDU at the head of a queue is blocked and prevents unblocked PDUs behind it from progressing.

2. Consider a routing algorithm R of your choice. How does R’s operation change if it used in a datagram network compared to if it’s used in a virtual-circuit network.

   ---

   A routing algorithm’s operation is independent of its use in a datagram or VC network, and will not change based on the network type. A routing algorithm’s operation has three functions: build a model for the network, find the best paths through the network and generate the forwarding table. There is no need to change any of these functions based on network type.

   VC and datagram forwarding tables are different, but the difference has no effect on routing-algorithm operation. Datagram and VC networks may have different views of best paths through the network (hop-count vs bandwidth, for example), but these differences have no significant effect on routing-algorithm operation.

3. If a router uses shadow forwarding tables, does each input port get the same shadow table? Justify your answer.

   ---

   Each input port gets the same shadow forwarding table. There are at least two ways to justify this claim. First, any PDU entering a router has to be forwarded in the same way regardless of the input port on which the PDU enters the router. This means each input port needs the same shadow routing table. Second, shadow forwarding tables were developed to relieve the performance-degrading memory contention resulting from all input ports accessing the same forwarding table.

4. How many IP addresses does a router have? Justify your answer.

   ---

   There is a one-to-one correspondence between the number of interfaces a router has and the number of IP addresses the router has: a router with N interfaces has N IP addresses, and vice versa.

5. Assuming IPv4 addressing, what is maximum network hierarchy depth possible? What does the resulting network topology look like? Justify your answer. Assume network addresses and host ids have to be at least one bit long, and that all addresses are devoted to point-to-point addressing (that is, no broadcast, multicast, anycast or the like).

   ---

   The maximally deep network topology under the assumptions given in the problem is a complete binary tree of depth 32 (or 31, or 30, depending on how you want to count). At the root (depth 0), the router forwards on a.b.c.d/1 and has two children (neighbors), one handling 0.b.c.d/1 and the other handling 128.b.c.d/1. A router at depth i forwards to its two children on a.b.c.d/(i + 1).

6. Given that a router uses longest prefix matching when searching its forwarding table, explain how is it possible for the forwarding table to have more than 32 entries.

   ---

   It is true that there are at most 32 (or 31, or 30 depending on your assumptions) possible prefix lengths. However, prefix of length i bits can encompass up to 2ⁱ different IP addresses. For example, there are 2⁶ = 64 IP addresses covered by a six-bit prefix.