Question 1: Explain why worst-case fair WFQ can have the absolute fairness bound.

Question 2: Consider two N x N internally non-blocking packet switches where N is very large. One is operated as a waiting system with very large input buffers and the other is operated as a loss system without input buffers. For the former, packets are dropped when the input buffers overflow, and for the latter, packets that lost contention are dropped. When the input load is 0.3, which system has a lower packet loss probability? How about when the input load is 1? Please justify your answer.

Question 3: Consider WFQ (weighted fair queuing). There are four equally weighted connections A, B, C and D to a WFQ scheduler. Initially, all these four connections are inactive. Now suppose that at time 0, a packet of size 3 units arrives at connection A, a packet of size 4 units arrives at connection B and a packet of size 2 units arrives at connection D; at time 2, a packet of size 2 units arrives at connection C; and at time 10, one more packet of size 3 units arrives at connection D. The outgoing link serving rate is one unit per second. Please specify the finish numbers of all these five packets. What is the round number when the system becomes idle? When is the system idle? Justify your answer.

Question 4:

Please prove that the maximum throughput of input queued switch is 0.586 when switch size N approaches infinity. Assume the incoming traffic is uniformly distributed.

Question 5:

Consider max-min weighted fair allocation. There are four connections with bandwidth demands of (6, 3, 10, 5) and weights (2, 4, 3, 1). The total network capacity is 20. What are the final fair shares for these four connections.

Question 6:

Consider an 8 x 8 Batcher-Banyan network. Label the input and output ports from 0 to 7, respectively (the lowest port is port 7).             Four packets arriving to the input side of the Banyan network: packet 1 at input port 1, destined to output port 5; packet 2 at input port 3, destined to output port 4; packet 3 at input port 5, destined to output port 7; packet 4 at input port 6, destined for output port 7. Which packets will be delivered during the current round? Justify your answer.