Deficit Round Robin (DRR) is a packet scheduling algorithm that operates as follows. The DRR scheduler scans all N buffers in a specified round-robin sequence. A deficit counter c(i) is maintained for each buffer i (i = 1 . . . N). When a non-empty buffer i is scanned, its deficit counter c(i) is incremented by a quantum value (i.e., c(i) = c(i) + ). The value of the deficit counter is the maximum amount of bytes that can be sent from that buffer at that point in time: if the deficit counter is greater or equal than the size L(i) of the packet at the head of buffer i, this packet can be transmitted and the value of the counter is decremented by the packet size (i.e., c(i) = c(i)L(i)). When that transmission is complete, the size of the next packet at the head of buffer i is compared to the counter value c(i), and so on. Once the buffer i is empty, or the value of the deficit counter is insufficient (i.e., c(i) < L(i)), the scheduler is ready to scan the next buffer. If a buffer is empty, its deficit counter value is reset to 0.

1. Suppose that a router interface has four buffers and that each buffer contains one packet. The length of the packets are 16, 10, 12, and 8 bytes, respectively. The quantum is 4 bytes. Assume that all counters are equal to 0 initially. The link transmits 1 byte per nanosecond. Show the deficit counter at each buffer as a function of time and indicate when each of the four packets will be transmitted. You can assume that there are no other packet arrivals.

2. Suppose now that N = 2 and that each buffer is never empty. Suppose that the packets of the first buffer are four times larger than the packets in the second buffer. How does the DRR scheduler share the transmission capacity among the two buffers? You can assume that the smallest packet size is an integer multiple of .

3. Suppose that N=4 and that the transmission capacity is 10Mbps. You want to provide at least 4Mbps to buffer-1, 2Mbps to buffer-2, 1Mbps to buffer-3 and 1Mbps buffer-4. How would you modify the previous DRR algorithm to make it weighted so that you can share the transmission capacity in this unequal manner?