CS204 Fall 2009

Group Project

Due: 11:59pm Sunday December 13, 2009

I. Summary

The project will be a non-trivial original piece of work, which is produced by an individual student or by 2  students working together as a team. The project could be structured in any of the following ways: 

• a prototype implementation to demonstrate the feasibility of some proposed network algorithm(s) that you either found in the literature, or came up with yourself.
• a measurement study, or the application of published measurements to study the properties of some existing network component (e.g., queue sizes in a router)
• a critical survey of some network-related topic. (However, they have to be thorough, synthesize the read material, and offer an interesting perspective on the state of the art.)

The end result should be at the level of a decent workshop paper. I will offer several ideas for projects related to traffic characterization issues we have been covering in lecture.  However, you are welcome to select a topic of your own choosing if you prefer. Please let me know ASAP when you have chosen a topic so I can offer suggestions on how to proceed before you (attempt to) do all the work.

II. Some Sample Topics

(1) Develop a solution to the problem of (mis)using large numbers of Ethernet MAC addresses to identify virtual devices.

Every piece of equipment connected to an IEEE 802.3 Ethernet or IEEE 802.11 WiFi network is assigned a unique 48-bit MAC address by its manufacturer. In this way, all 802 LANs world-wide are "plug-and-play" without any need to configure the equipment to avoid address conflicts. (In contrast to this approach, the USB protocol uses 7-bit addresses, so USB addresses for each device must be determined through a protocol during network initialization, and no network can have more than 127 devices no matter how hard you work at the configuration.) Possible options you might consider include:

1. Modify DHCP, for dynamic allocation of IP addresses, to add the option to give out a MAC address at the same time. Note that a virtual device must be hosted on a "real" physical device, which could be responsible for carrying out the request to the server. Since the current DHCP protocol uses the MAC address as the "key" to determine who is currently holding the lease for each dynmically-assignable IP address, a more-general solution is required to handle this case.
   
2. Modify the spanning-tree protocol for layer-two bridges (aka switches) so that the "root" of the spanning tree is responsible for handling the "leasing" of MAC addresses, either individually to a a specific end-device somewhere within the broadcast domain (aka "vlan"), or blocks of MAC addresses to an edge switch for "sub-leasing" to end-devices connected to the edge switch.
3. Since MAC addresses are stripped and replaced each time an IP datagram passes through a layer-3 router, one might consider whether proxy-ARP could handle the problem, if all the virtual devices where behind a switch/router that was configured to intercept all ARP requests to the virtual devices. But this still leaves the problem of MAC address assignment on the "inside" network, behind the proxy-ARP device.

The other dimension to the problem is to decide on which "pool" of MAC addresses should be used by this protocol for dynamically assignable MAC addresses? Currently, the format of a 48-bit MAC address consists of two parts: a 24-bit prefix called an OUI (== Organizationally Unique Identifier) representing the entity that created the MAC address (say Cisco), followed by a unique 24-bit sequence number for each device produced by that entity (say, the particular switch port to which my office computer is connected). Note that the first two bits on the wire for every MAC address are reserved for the "Individual/Group (I/G)" bit, followed by the "Universal/Local (U/L)" bit. When I/G ==1, then the MAC address specifies a group or multicast destination. Similarly, if U/L == 0 then the MAC address is globally unique following the rules set out by the IEEE, whereas if U/L == 1 then the MAC address is locally generated using any method whatsoever. Since there there are 2⁴⁶ (about 7 * 10¹³) locally administered MAC addresses in existence, and none of them can be used as a "permanent, unique" MAC address for some network device (real or otherwise), it would be nice to use them for this purpose. However, if you do so, then how to handle random users generating their own local MAC addresses that might conflict with this new use? I think the switches could handle this through Network Address Translation (NAT) at layer 2. On the other hand, if a single OUI were reserved for the purpose of supporting dynamically-assigned MAC addresses, can we be sure that we don't run out because different entities on the same broadcast domain are both trying to take control of their allocation.

(2) Congestion control via BCN and IEEE 802.1Qau.

Everyone knows about TCP congestion control, based on the receiver advertising a maximum window size it is committed to accept, and the sender adjusting its transmit window up or down to a maximum of the advertised window based on packet losses or other forms of congestion. However, congestion control algorithms have also been developed at lower protocol layers. For more than a decade, full-duplex Ethernet has offered a MAC control function that provides start/stop flow control using PAUSE frames, described in clause 31 of the IEEE 802.3 standard. More recently, layer-2 bridges have introduced a more powerful congestion control technique involving explicit control messages between the switch and the senders. The work started out as a proprietary Cisco protocol called "Backwards Congestion Notification (BCN)" and has now advanced into the IEEE standards process as project 802.1Qau.  How does this work, and will it become more successful than PAUSE frames?  Does it replace, complement or interfere with TCP congestion control?