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

TitleThe complexity of computing virtual-time in weighted fair queuing schedulers
Publication TypeConference Paper
Year of Publication2004
AuthorsTayvar, H., and H. Alnuweiri
Conference NameCommunications, 2004 IEEE International Conference on
Pagination1996 - 2002 Vol.4
Date Publishedjun.
Keywordscomputational complexity, Internet, queueing theory, scheduling, time-stamps, virtual-time computing, virtual-time update operation, weighted fair queuing schedulers
Abstract

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.

URLhttp://dx.doi.org/10.1109/ICC.2004.1312870
DOI10.1109/ICC.2004.1312870

a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949
Email:

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2020 The University of British Columbia