Computer Networking • CS 514

Test 4, 29 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:

    • Forward error detection

    • Multiple-access protocol

    • Exponential backoff

    • LAN addressing

    • Byte stuffing

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

    • Forward error detection:
    An error detection scheme which adds redundant bits to the data, giving the receiver the potential to determine if errors occurred during transmission.

    • Multiple-access protocol:
    A protocol which gives a group of hosts non-conflicting access to a shared medium.

    • Exponential backoff:
    A method for controlling retransmission that requires each retransmitting host randomly select a back-off period from an interval that grows exponentially with the number of consecutive retranmissions.

    • LAN addressing:
    Data-link layer addresses assigned to the network interface card.

    • Byte stuffing:
    A technique for escaping meaningful bytes in a payload by preceding them with an escape byte value.

  2. Explain why link-layer switching is transparent to hosts.

    Link-layer switching is transparent to hosts because link-layer addressing is flat; there is no hierarchical structure in a link-layer network. All hosts on the same data-link layer network (LAN) are peers and may address each other directly, independently of whether or not they share a single bus-based interconnect or a sequence of LANs interconnected by layer-2 switches.

  3. Bumble is a layer-3 network that assigns each host a Bumble address based on some function (the SHA-1 hash function, for example) of the hosts MAC address. Would an ARP-like protocol be needed by the layer-2 network supporting a Bumble network? If an ARP-like protocol is needed, briefly describe the protocol's function; otherwise explain why an ARP-like protocol is not needed.

    An ARP-like protocol isn't needed if the protocol implementer doesn't care about layering (and they usually don't) and the Bumble to MAC function is invertable. In this case the data-link layer uses the inverse function to generate the destination MAC address. This scheme assumes the Bumble network spans only a single LAN.

    An ARP-like protocols isn't needed if the protocol implementer cares about layering or the Bumble to MAC function is not invertable, but the implementer doesn't care about efficiency. In this case the data-link layer broadcasts layer-2 PDUs to all other hosts on the LAN. Each host receives the PDU and sends the payload up to the Bumble layer, which either 1) recognizes the destination Bumble address as its own and continues processing the PDU, 2) doesn't recognize the Bumble address and tosses the PDU, or 3) is a Bumble router and forwards the PDU according to its forwarding table.

    An ARP-like protocol is needed if the protocol implementer cares about layering, the Bumble to MAC function is not invertable, and efficiency is a concern. The ARP-like protocol behaves in the usual way: broadcast Bumble-address resolution, point-to-point positive response with snooping, and a default response leading to a Bumble router in case of no response.
  4. N hosts are connected to a layer-2 switch in a star architecture. From the time the network is powered up, what is the minimum number of broadcasts the switch has to initiate before it no longer needs to broadcast? What is the maximum number of broadcasts the switch needs to initiate before it no longer needs to broadcast? Justify your answers.

    Assume 1) all network components power up at the same time, 2) each host sends often enough to avoid being aged out of the forwarding table, and 3) a host cannot send to itself via the data-link layer. Clearly state any other assumptions you make.

    If hosts pair up and do a request-response interaction, the switch will broadcast for the request and not for the response, leading to N/2 broadcasts, which fills the switch table. If N is odd, the unpaired host can't cause a broadcast because every host it could possibly send to is in the switch table.

    If there's a host that receives but never sends, the switch will broadcast every time the host receives a PDU.

  5. A colleague of yours knows that CRC codes are much better at error detection then are parity bits. Observing that your company's data-link layer uses a one-bit parity code to detect frame errors, your colleague recommends the data-link layer software be rewritten to use CRC with a generator polynomial of 1 (which your colleague recognizes as a degree 0 polynomial). Your boss asks you if your colleague's advice should be followed. What answer do you give your boss? Justify your answer.

    Alas, my colleague's idea is worthless. Dividing anything by 1 is always exact with no remainder, so my colleague's scheme will never detect an error.

  6. N > 1 hosts can be arranged as a ring at the data-link layer: each host has a connection to two different hosts (note that means each host has two network interfaces), and there is a path between any two hosts. Describe a MAC-sublayer protocol that lets any two hosts in the ring exchange layer-2 PDUs.

    Your protocol description should be in general terms; you need not go into details about frame layout and message exchange sequences for example. However, make sure you cover the basics. You needn't describe frame address fields, but you should describe how hosts are addressed. Describe the steady-state operation of your protocol; don't worry about network start-up or shut-down, or how the protocol handles catastrophic error conditions. Make sure you clearly state your assumptions.

    This protocol is simple unreliable datagram service. One of the network interfaces on a host is the receiving host, the other is the sending host. Two consecutive hosts on the ring are wired sender to receiver. A host is addressed by the lowest of its two MAC addresses.

    When a host has a PDU to send, it sends it. A host prefers sending its own PDUs over forwarding its neighbor's PDUs. Incoming PDUs are buffered until the receiver is done sending; if the buffer overflows the incoming PDUs are discarded without acknowledgment.

    A host h receiving a PDU 1) forwards the PDU to the next host if the PDU isn't addressed to h, 2) keeps the PDU for further processing if the PDU is addressed to h, or 3) tosses the PDU if it was sent by h.
This page last modified on 2014 November 3.