Home

Schedule/Notes

Readings

Assignments

TA info

Policies

Homework #2: Design Principles
Assigned: Friday 10/9
Due Wednesday 10/21 4:30 pm (main CS office)

1. TCP Timers. Why do you think that backoff timers in TCP are not randomized as in Ethernet? Does TCP's timeout mechanism allow TCP to spread transmissions over longer periods of time (adaptively) as in Ethernet? Explain.

2. Analysis of discrete time CSMA/CD. In class I presented an informal derivation of an expression for the system throughput of CSMA/CD in terms of the offered load. In this problem, you will repeat the argument for a discrete time system. The fact that the system is discrete time will allow you to make a less informal argument.

Define S and G as in class. Also assume that the arrival process of all packets is Poisson with rate G. Assume that time is divided into fixed length intervals of length a ( equal to the end to end propagation delay. Further assume that the time to transmit a packet is 1 and that 1/a is an integer. Suppose that k users generate packets in the i-th interval. Then at the start of the (i+1)-th interval, all k users sense the channel and if it is idle, start to transmit. If k = 1, then the user transmits over 1/a time intervals. One additional interval is required for the channel to clear. If k > 1, then a collision occurs and the users become aware of it at the end of the (i+1)-th time interval. An additional time interval is needed for the channel to clear.

• Derive an expression for S in terms of the offered load G. How does this compare to what we derived in class.
• Consider a variant of the system that is used in 802.11 (WiFi). Here a user senses whether or not the channel is idle. If so, it transmits, otherwise it waits a random amount of time. As with CSMA/CD, a collision may occur if two or more users transmit during the same slot. Unlike CSMA/CD however, a user I unable to detect a collision. Consequently all users transmit their entire data. They then learn of the collision when the base station returns a negative acknowledgment (or a lack of an acknowledgment). Assume that again users use backoff timers to reschedule their retransmissions and that transmissions and retransmissions can be captured by a Poisson process where packets (original transmissions and retransmissions) are offered at rate G. As before, derive an expression for the system throughput S as a function of G and the propagation delay (. This is referred to as carrier sense multiple access (CSMA).
• Plot S vs G for both CSMA and CSMA/CD. What is lost in the wireless setting when users no longer have the ability to detect collisions?

3. Randomization and indirection: Crowds. Read the paper, M. Reiter, A. Rubin, "Crowds: Anonymity for Web Transactions" ACM Transactions on Information and System Security. You only need to read sections 1, 2 and 4. What are randomization and indirection used in this protocol? Pick two examples of randomization and indirection that we studied in class, and compare and contrast the use of randomization and indirection in Crowds, and in these two protocols.

4. Leaky buckets. Consider two leaky buckets in series, with parameters (r₁,b₁) and (r₂,b₂); traffic arriving to be send into the network arrives to the first leaky bucket. Now consider the output traffic leaving the second leaky bucket. Give the parameters of an equivalent single leaky buket (r₃,b₃) that provides the same policing as the two leaky buckets in series in terms of the parameters r₁, r₂ b₁, b₂ of the two original leaky buckets.