Tal Anker, Roi Cohen, Danny Dolev and Yoram Singer:
Authors:
Tal Anker,
Roi Cohen,
Danny Dolev and
Yoram Singer.
Technical Report HUJI-CSE-LTR-2000-30 The Hebrew University of
Jerusalem, Computer Science Department, July 2000.
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.
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.
Download paper (technical report):
ps,
ps.gz,
anker@cs.huji.ac.il
Last modified: Mon Feb 21 18:59:01 EST 2000