Authors:
Tal Anker,
Roi Cohen,
Danny Dolev and
Yoram Singer.
In proceedings of IEEE Workshop on High Performance Switching and
Routing (HPSR'01 ), May 2001.
Abstract:
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. This paper describes a family
of randomized algorithms for packet scheduling. These algorithms 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. Experimental results of the proposed randomized algorithms
suggest that the randomized approach is a viable alternative to the
currently deployed deterministic fair queuing algorithms.
Download paper (Conference Version):
ps,
ps.gz,
anker@cs.huji.ac.il
Last modified: Mon Feb 21 18:59:01 EST 2000