CSE 330 - Advanced Computer Networks
Fall 2006

Written Homework 1


Assigned: Thursday, Sept. 21; Due: Wednesday, Oct. 11, in class


Guidelines about homework.


Problem 1: (15 points) 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. How 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 with those used in these two protocols.

Problem 2: (20 points) Estimation of multicast group size. Consider the IP multicast abstraction. There is currently no way for sender to know the number of receivers for a multicast group. One way for the sender to determine the number of receivers would be for it to multicast a request for all receivers to send messages to the sender (which would require N messages total from N receivers to the sender).

Problem 3: (10 points) Concast.  We saw how Stoica's i3 architecture can be used to implement uncaist, multicast and anycast communication. Consider a model of communication known as concast, in which data sent from two senders is "fused" together before being sent to the receiver (for example, the data being fused might be two acks being sent by two multicast receivers back to a multicast sender).  For our purposes here, suppose that "fusing" means the addition of two values (one sent from each of two senders) that should be added together before being sent to the receiver.  Show how concast can be implemented using the i3 architecture and describe how and why your solution works.

Problem 4: (5 points) Leaky bucket.  Consider the leaky bucket policer in the class (slide 3-11 in Multiplexing). Suppose that we now want to police the peak rate, Rp, as well. Show how the output of the leaky bucket policer can be fed into a second leaky bucket policer so that the two leaky buckets in series police the average rate, peak rate and burst size. Be sure to give the bucket size and token generation rate for the second policer.