Computer Networking • CS 414

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

   • Frames

   • ARP table

   • Hub

   • Virtual local area network (VLAN)

   • Random access protocol

   ---

   • Frames:

   The PDUs sent by the data-link layer.

   • ARP table:

   The table used by ARP to map an IP address to a MAC address.

   • Hub:

   A layer-2 device that passively connects LAN segments into a larger lan.

   • Virtual local area network (VLAN):

   A technique for segmenting a switch-connected LAN into operationally separate LANs (the virtual LANs).

   • Random access protocol:

   A shared-channel media-access protocol providing relatively unconstrained access to the channel and a method from recovering from channel-access conflicts (collisions).

2. Describe how ARP uses the MAC broadcast address.

   ---

   If a host’s ARP table fails to map an IP address to a MAC address, the ARP protocol queries every host on the network segment by sending an ARP resolution request addressed to the MAC broadcast address.

3. Give an example of an error that is not caught by an addition-based checksum but is caught by a division-based checksum. (Hint: this answer requires that you define an addition-based and a division-based checksum.)

   ---

   Define the addition-based checksum as the sum of the bytes in the message where each byte is interpreted as an 8-bit unsigned integer and the sum is interpreted as addition modulo 256 (This definition involves division; if that upsets you, you can define the sum as the running sum of arbitrary length). For example, the two-byte message 1 2 has checksum 1 + 2 = 3. This checksum doesn’t distinguish between the messages 1 2 and 2 1 (or the messages 10000001 10000010 and 00000001 00000010). Define the division-based checksum as 1) a zero-byte message has checksum 1 and 2) an n-byte message b_n, b_n-1, ..., b₁ has the checksum equal to the quotient of dividing b_n by the checksum of n-1-byte message b_n-1, ..., b₁. For example, the two-byte message 2 1 has checksum 2 (1/1 = 1, 2/1 = 2) and the message 1 2 has checksum 0 (2/1 = 2, 1/2 = 0).

4. Is it possible to have a small enough number of hosts on an Ethernet so that there is never be a collision? Justify your answer.

   ---

   No. The smallest number of hosts possible is zero, in which case you don’t have a network. A similar argument holds for 1 (although you can imagine a single host on an Ethernet segment connecting to a gateway to another network). With two hosts, there’s always the possibility of both hosts wanting to transmit simultaneously, leading to collisions (assuming the hosts are otherwise independent).

5. Compare and contrast switches and routers in at least two different aspects (and pronunciation isn’t one of the aspects).

   ---

   There are many:

   • Switches are layer-2 (data-link layer) devices, while routers are layer-3 (network) devices.
   • Switches model networks by connectivity only, while routers model networks by connectivity and other properties (delay, bandwidth, load and so on).
   • Routers interconnect networks, while switches interconnect hosts.
6. Describe a data-link layer protocol that turns a full-duplex link into a half-duplex link. You may assume an underlying link-layer protocol to take care of other, non-duplex, aspects of link-layer services. Clearly state your assumptions.

   ---

   The token-ring protocol is a half-duplex protocol: a host holding the token gets to send a message, and then sends the token to the next host. If the host holding the token has no message to send, it just sends the token.