Computer Networking • CS 514

Test 3, 15 October 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.

Always justify answers unless the question explicitly states it’s not necessary. Some questions require reasonable assumptions in order to be answered. In such cases the answer should clearly state the assumptions made. Answers should be no longer than 75 to 100 words.
  1. Keeping in mind that giving an example of X is not defining X, briefly (in one or two sentences, 25 to 30 words total) define:

    • Forwarding

    • Routing

    • Virtual circuits

    • Longest prefix match

    • Tunnel

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

    • Forwarding:
    Moving PDUs from a router’s input ports to the output ports under the direction of the forwarding table.

    • Routing:
    Determining the best paths between network end-points; may also include determining the forwarding tables based on the paths discovered.

    • Virtual circuits:
    PDU flows through a network defined by VC tables at each router.

    • Longest prefix match:
    A technique for resolving ambiguity in forwarding-table look-up. When a PDU destination matches more than one forwarding-table entry, the longest prefix match is selected.

    • Tunnel:
    Encapsulating one protocol’s PDUs as a payload in another protocol’s PDUs, usually to overcome some localized network deficiency, such as when IPv6 islands must traverse IPv4 oceans.

  2. What is address (or route) aggregation? Why is it useful?

    Address aggregation involves combining forwarding-table entries when 1) the destination subnet addresses in the entries share

  3. The cost of using a link between two routers in network N drops by half. Explain how this new information is used by the routers in N. Assume the network routers are using a link-state algorithm. Make sure your answer is complete and consistent with the behavior of link-state algorithms.

    Assume the network has gone through initialization, and each router in the network has converged to the network model. The routers adjacent to the cost-adjusted link broadcast updated neighbor-cost information to the network. Each router receives the broadcast and adjusts the network model based on the broadcast information. Each router runs a shortest-path algorithm over the adjusted network model and, if there are path changes, updates the forwarding table to reflect the changes.

  4. Nd and Nvc are two networks with identical hardware and network topologies. Nd provides datagram services and Nvc provides virtual-circuit services. Which of these two networks places greater importance on having up-to-date routing information? Justify your answer.

    Up-to-date routing information is more important to Nd than to Nvc. Every Nd router makes a routing decision on every PDU. Nvc routers only make routing decisions when the virtual circuit is set up. Once PDUs flow through a virtual circuit, routers in Nvc merely rewrite virtual-circuit identifiers and forward PDUs. Assuming the same traffic in each network, Nd makes far more routing decisions than does Nvc and consequently up-to-date routing information is more important in Nd than it is in Nvc.

  5. A colleague of yours has developed the PDU-per-port flooding algorithm. Each router in the PDU-per-port algorithm keeps track of which flood PDU shows up on each router port and only floods those PDUs arriving on a port for the first time. Your boss asks you your opinion of your colleague’s algorithm. What do you say?

    My colleague’s flooding algorithm has the great virtue of being correct: It floods PDUs and eventually stops the flood. Unfortunately, my colleague’s algorithm has the great deficit of being ridiculously expensive. A good flood algorithm broadcasts each PDU r times per flood, where r is the number of routers in the network. My colleague’s algorithm broadcasts each PDU p times, where p is the total number of interfaces at all routers in the network (p has to be at least twice r (why?) and is most likely much more than r).

  6. Given a typical IP router (that is, a router capable of handling IP PDUs), describe how you’d modify the router to discover communication flows in IP traffic. Given the flow information discovered, describe a change you’d make to the router to exploit the flow information to provide better service to IP traffic. You may answer this question for IP in general, or your answer may be relative to a particular IP-based protocol (which you should identify). For the second question (router changes for better IP service), consider only one service improvement and related router changes.

    Lots of flows can be defined. The IP header source and destination addresses defines a flow of all IP traffic between the two identified hosts. The IP header protocol type refines the flow to a particular protocol’s traffic between the hosts, such as all TCP or UDP traffic. If you want to violate layering (what the heck, why not?) retrieving the port numbers from the payload header, assuming they’re defined, further refines the flow to traffic between processes on each host. Once a flow has been identified, all kinds of service improvements can be created for the flow, almost all of which boil down to either treating flow PDUs better than other PDUs by, for example, moving flow PDUs to the head of any queues, or treating other PDUs worse than flow PDUs by, for example, dropping other PDUs before flow PDUs.

This page last modified on 2014 October 15.