CS 268 Midterm Exam (Example) Name: SID: Problem Points 1 2 3 4 5 Total Remember to be concise1) End-to-End (20 pts) (a) State the end-to-end arguments. (10 pt) (b) Give one example of functionality that according to end-to-end arguments should be implemented at the application layer, and one example of functionality that can be implemented at a lower layer, i.e., link or network layer. Justify your examples. (Use no more than two phrases for each example.) (10 pt)2) RED (20 pts) (a) Name two problems RED tries to address. Explain. (10 pts) (b) Explain briefly how RED works. (10 pts)3) Lookup (20 pts) (a) Explain briefly how Patricia tries work. What are the computation and the space complexities of this algorithm? (5 pts) (b) Give one example in which you might prefer to use Patricia tries over Lulea’s lookup algorithm. (5 pts) (c) Propose a technique to decrease the time complexity of Patricia-based routing lookup. Identify the tradeoffs of the proposed change. (10 pts)4) Fair Queueing (20 pts) (a) Consider a set of n flows with the arrival rates of 1 Mbps, 2 Mbps, …, and n Mps, respectively, and assume that all flows traverse a link with capacity of n Mps. What is the min-max fair rate f ? (10 pts) (b) Explain the concept of virtual system time? Why is it needed? (10 pts)5) TCP Congestion Control (20 pts) (a) Describe fast retransmission and fast recovery algorithms; pseudocode preferred. (5 pts) (b) Design a flow control protocols that achieves a throughput that is N times higher – where N is given – than the throughput of a single TCP flow between the same source and destination. Explain the design rationales. (15
View Full Document
Unlocking...