The complexity of computing virtual-time in weighted fair queuing schedulers

This paper presents two fundamental theorems that show that the O(N) complexity for updating the virtual time in a weighted fair queuing (WFQ) scheduler with N sessions is caused mainly by simultaneous departures of packets, and not by iterated deletion as was previously claimed. Iterated deletion is caused by an "avalanche" of consecutive, but not necessarily simultaneous, departures that incur more departures due to increments in available bandwidth from idling sessions. Iterated deletion potentially leads to large numbers of consecutive departures within a given time period. The number of departures is, however, a function of such implementation details as the resolution of the time-stamp and the scheduler clock. On the other hand, the problem of simultaneous time-stamps can not be solved by an increase in the time resolution of virtual-time update. Essentially, all equal time-stamps must be processed during a single virtual-time update operation. We present a proof to show that O(N) simultaneous departures can occur during a single virtual-time update. We also show that this is a fundamental property of WFQ that holds even under the most restrictive conditions, viz. all packets arrive serially to the scheduler (no simultaneous arrivals), and the input bit-rate does not exceed the output bit-rate.