Abstract of: Probabilistic Fair Queueing
Packet scheduling constitutes the core problem in efficient fair
allocation of bandwidth to competing flows. To date, numerous
algorithms for packet scheduling have been suggested and
tested. However, only a few of them are currently deployed. One of the
key reasons for rarity of applied packet scheduling methods lies in
the complexity of their implementation. In this paper we describe and
experiment with a family of randomized algorithms for packet
scheduling. The algorithms we present are simple to implement and
require small amounts of computation time. Specifically, we present an
O(1) probabilistic weighted fair queuing algorithm that emits packets
from flows with an improved delay jitter. We present experimental
results with the proposed randomized algorithms which suggest that the
algorithms may form a vailable alternative to the currently deployed
deterministic fair queuing algorithms.