After yet another series of devastating wars that have caused unbelievable destruction (and resulted in yet another trilogy from Tolkien), the inhabitants of Middle Earth have decided to set up a Security Council to maintain peace and harmony

COMP 290-078: Problem set
1999/09/02

(Due 09/09) Packets from three connections arrive at a scheduler scheduling a link at a rate of 1 data-unit per time-unit. The three connections are characterized as follows:

Connection i	f_i	*packet arrivals: a packet of size l_i* data units every p_i time units**
1	0.6	l₁ = 1, p₁ = 3
2	0.2	l₂ = 1, p₂ = 4
3	0.2	l₃ = 2, p₃ = 10

What is the GPS schedule for this system over the time interval [0,10)?

Plot the virtual time function V(t) as a function of the real-time t for the above scheduler over the (real-)time interval [0,10)

For each packet p_i^k that completes service in the interval [0,10) in the GPS schedule, determine its arrival time a_i^k, its completion time f_i^k, its virtual arrival time V(a_i^k), and its virtual completion time V(f_i^k).

Determine the WFQ schedule for this system over the interval [0,10)

(Due 09/09) In order to schedule packets according to the WFQ scheduling discipline, a scheduler must keep track of the virtual time function. In excruciatingly painful detail (e.g., annotated pseudocode), describe the algorithm that would need to be executed by the WFQ scheduler for this purpose. Assuming that there are n active connections in the system, analyze the computational complexity of your algorithm from the following two perspectives

what is the worst-case amount of time (in big-Oh notation) that your algorithm would take when a new packet arrives on one of the connections?

suppose that the scheduler processes a total of N packets during a particular time interval, and that the total amount of time that your virtual-clock algorithm executes is W. What is the worst-case value of the ratio (W/N), when expressed in big-Oh notation in terms of n and N?

(Due 09/16) Write a brief (one/ two-page) summary of the following paper

Jon C. R. Bennett and Hui Zhang. WF²Q: Worst-case fair weighted fair queueing. Proceedings of IEEE INFOCOMM, San Francisco, 1996. (Available off the second author’s Web homepage).

Your summary should be a self-contained description of the main ideas in the paper. Although you should be familiar with the technical details (the proofs) presented in the paper, you do not need to include these in your summary (except for techniques you consider to be particularly "neat" or novel).