Question 1

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

Question 2:

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

Question 3

Consider max-min weighted fair allocation. There are four connections with bandwidth demands of (6, 5, 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 4:

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.