Computer Networking • CS 414

Test 3, 5 March 2014


This test has six questions. The test runs the entire class period, starting at 4:30 and 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:

    • Broadcast routing

    • Gateway routers

    • Static routing algorithm

    • Subnet mask

    • Fragment


    • Broadcast routing:
    Routing which sends a PDU to every host in the network.

    • Gateway routers:
    Routers that connect two or more autonomous systems.

    • Static routing algorithm:
    A routing algorithm in which the forwarding tables are determined once by an external agent.

    • Subnet mask:
    A number giving the size in bits of the network portion of an IP address.

    • Fragment:
    A fractional piece of a PDU.

  2. T is a forwarding table used in a router from a datagram network. Would it be possible to use T in a router from a virtual-circuit network? Justify your answer.


    No, a forwarding table from a datagram network cannot be used in a virtual-circuit network. An entry from a datagram-network forwarding table contains two items: the destination address and the next-hop link (the output port). An entry from a virtual-circuit network forwarding table needs four items: the destination address, the next-hop link, the old virtual-circuit ID, and the new virtual-circuit ID. The datagram-network forwarding table entry is missing the virtual-circuit ID information.

  3. A router in a network N uses forwarding table T. Does every router in network N use the forwarding table T, or does each router have its own, different forwarding table? Justify your answer.


    No, each router has a forwarding table which may be different from other forwarding tables used in the network. A router's output (next-hop) ports are specific to that router, and need not be the same from router to router. Differences in output ports shows up as differences in the forwarding tables.

  4. Assuming the payload of an IP PDU is destined for the transport layer, describe the steps taken by the network layer to demultiplex the PDU.


    A PDU destined for the transport layer has to be demultiplexed with respect to the transport-layer protocol: TCP, UDP, and so on. The IP protocol in the network layer examines the next-protocol field in the IP header and uses that value to demultiplex to the proper transport-layer protocol.

  5. Explain how is it possible that an autonomous system (AS) can choose its intra-AS routing algorithm without coordinating with other autonomous systems.


    There are two main reasons. First, most of the information gathered by an intra-AS routing algorithm remains in the AS. If another AS has no knowledge of the information produced, it has no opportunity to express an opinion about how the information is produced.

    Second, to the extend that intra-AS routing algorithms produce information relevant outside the AS, the important aspect the information itself and not how it was produced (as long as it was produced correctly).

  6. Describe the smallest possible forwarding table that still enables the router to function as a router (pay attention to that “as a router”).


    Zero entries: a router with zero entries would throw all PDUs on the floor and respond with "destination not reachable" error messages. While this is how a router should behave, it is not behaving like a router in the sense of routing packets.

    One entry: a router with a single-entry forwarding table acts like a (slow) wire, assuming the entry was a default entry. If the single entry was a network address, the router acts as a wire for PDUs destined for the network and acts like a bit-bucket for all other PDUs, as in the zero-entry case.

    Two entries: A router with a two-entry forwarding table acts like a router, moving input PDUs between more than one possible output port. If one of the entries it the default, the router handles all packets; otherwise, the router only moves the PDUs to the destinations given in the forwarding table.

This page last modified on 2014 March 5.