Abstract |
Quality-of-Service guarantees in networks will soon be provided by using per-flow queueing and sophisticated schedulers. Most advanced scheduling algorithms rely on a common computational primitive: priority queues.The hardest scheduling disciplines are those belonging to the weighted round robin family. Large priority queues are built using heap data structures. When the number of elements in the queue varies fast, it is difficult for the heap to keep up. This work deals with a binary tree of comparators to locate the minimum, in a non-sorted set of elements. Such an architecture permits insertions and extractions of any number of elements in the priority queue. The comparison operation is studied extensively and a 2-element comparator, which is the main block of the binary tree, is designed. We present a new idea for the tree, where signals are propagated across each 2-element comparator and in depth through the tree levels, at the same time. %A novel propagation function ascertains that signals are carried %across each 2-element comparator as well as in depth through the %tree levels, in parallel. The binary tree of comparators is the heart of the the weighted round robin scheduler we have designed. All designs are desicribed in Verilog (HDL). In addition, designs were described in C code for verification purposes. Synthesis results are presented for delay, power and area.
|