CS204 Fall 2008

1. In an Ethernet "switch" (i.e., a layer-2 transparent bridge), one can use the SNMP protocol to: (a) retrieve a count of the total number of octets (i.e., bytes) received from port i since the last time the switch was rebooted, and (b) select whether or not to run the Spanning Tree protocol on port i. What are the formats of the SNMP request packets and the associated response packets for querying this octet counter, and for instructing the Spanning Tree protocol to run. You must cite references from the appropriate standards document to explain the general format of the SNMP packet, the names of each object you wish to manage, and the format of the results returned.
2. Recall from lectures that Link Aggregation is a technique for simulating a single higher data-rate connection between endpoints (typically Bridges or large servers) by distributing the traffic across a set of parallel physical links (known as a Link Group), and that it provided a practical real-world example where trying to maintain strict layering of protocols gets into trouble. For this question, you will need to read sections from various IEEE 802 standards, which you can download from here. (Don't be frightened by the standards documents! I think it is an important skill for students to learn how to read standards, but we won't be doing a lot more of it in this class.)
   
1. Read chapters 7 (Principles of Bridge operation) and 17 (Rapid Spanning Tree Protocol) from the IEEE 802.1D-2004 standard, and briefly summarize the relationship (in terms of hierarchical layering and services used) between the RSTP application executing on this Bridge, the set of  Ports connected to the Bridge, and the MAC layer entities serving those Ports.
2. One possible approach for implementing Link Aggregation would be to add the functionality into the MAC Relay Entity in the Bridge. In other words, the MAC Relay Entity would need to be modified so that it learns which MAC addresses are associated with each Link Group (rather than individual Bridge Port), and its forwarding decisions would send a packet to any Bridge Port associated with the output Link Group. Briefly explain why this approach is not compatible with the Rapid Spanning Tree Protocol.
3. Now suppose Link Aggregation were placed below the MAC layer in the protocol hierarchy (so the distribution of traffic across the Link Group is pushed down to the interface between the MAC layer and Physical layer). Briefly explain why the requirement to maintain packet ordering across all packets belonging to a single "conversation" conflicts with the principle of layering in this case.
4. Read chapter 43 (Link Aggregation) from the IEEE 802.3-2005 Ethernet standard to see how the standards development process resolved this dilemma. (BTW, this is a very large document, and you will find chapter 43 in Section 3). Does this architectural approach solve the packet ordering problem in an extended (i.e., Bridged) LAN environment without violating the prinicple of layering?
   
5. Briefly describe the problem if we try to apply Link Aggregation to the ports of an IP router instead of a Bridge? Since IP routers don't mind networks that contain cycles, and certain well-known routing algorithms (such as OSPF) are happy to load-balance traffic across multiple equal-cost paths anyway, how much does this really matter?
   
3. This problem illustrates the point from the "End-to-End Arguments" paper, that adding link-level reliability may lead to a significant performance increase, even though it cannot by itself provide a reliable delivery service. Suppose Alice and Bob are connected by an N-hop path through an unreliable wireless network. In particular, assume that L=10% of the packet transmisions by a node, chosen at random, are not successfully received by its next-hop neighbor along the path.
1. Suppose "dumb" sensor node Alice sends periodic temperature readings (say) to gateway Bob using a lossy-datagram protocol like raw UDP, where there is no effort to detect and recover from packet losses. What fraction of Alice's sensor readings does Bob receive? (Make sure to express your answer in terms of L and N.)
2. Now assume that Alice and Bob add end-to-end reliability on top of their lossy-datagram protocol. For simplicity, assume that Bob has an "ideal timeout mechanism" that notifies him when each missing sensor reading should have arrived. Thus, Bob always sends an ACK/NACK control message to Alice in response to each sensor message she tried to send him, and somehow every one of Bob's ACK/NACK messages are reliably delivered to Alice. Whenever Alice receives a NACK, she immediately retransmits a duplicate copy of her most recent sensor message, and so on until she gets an ACK. (Assume that the roundtrip time for a single attempt is much smaller than the time between sensor readings, so we don't need to worry about queued requests.) In this case, what fraction of Alice's sensor readings does Bob recieve? On average, how many copies of each sensor message are transmitted over each hop along the path?
3. Now assume that we add link-level acknowledgmenets to the network. In this case, whenever a packet transmission by a node is not received by its next-hop neighbor along the path, this node immediately sends a duplicate copy of the same packet to the same next-hop neighbor, and so on until the packet has reliably reached the next-hop neighbor. How many copies of each sensor message are transmitted over each hop?
4. Compare the combined number of one-hop message transmissions required to deliver a single sensor message  all  the way from Alice to Bob in parts (b) and (c). What happens in each case as the number of hops (N) or loss probability (L) increases
   
4. GPS (Global Positioning System) allows one device to compute its own physical location using messages received from multiple trusted "beacons" with known locations. Protocols for solving the inverse problem, where multiple trusted "verifiers" jointly compute the physical location of a stranger, is an area of active research known as "position verification" or "secure localization." The key point is that the stranger might be dishonest, so the correctness of the protocol cannot depend on the stranger sending truthful information in its messages. Waters and Felten have proposed a secure localization system which  assumes that the stranger has a tamper-proof "device" issued by some trusted Certification Authority. The details of their protocol are not important for answering this question: all that matters is that (i) the trusted "device" is a separate entity from the untrusted stranger, and (ii) the verifier measures the round-trip time for the "device" to answer some skill-testing question to determine its distance from the verifier.
1. Waters and Felten do not describe the interface between their "device" and the stranger to whom it was issued. Assuming the "stranger" is a laptop computer, use the End-to-End Argument to explain why it is important to know whether the "device" is a simple add-on card that relies on the laptop's network interface to communicate with the verifier, or is completely self-contained (like a cell phone or PDA) and thus equipped with its own independent network interface.
2. If the "device" was completely self-contained, then clearly we could provide it with an internal GPS receiver and simply allow it tell the verifier of its location without resorting to skill testing questions and RTT measurements. What's wrong with this approach? (Think of the End-to-End Argument again, and the fact that the ultimate goal for the protocol is to determine the location of the stranger, and not simply the "device".)

What to turn in.