Abstract

(joint work with Fabio Checconi, SSSUP S . Anna, Pisa and Paolo Valente, Universita` di Modena e Reggio Emilia)

Abstract:

Packet schedulers with tight bandwidth and delay guarantees must keep up with rapidly increasing link speeds at the core of the Internet and within enterprise switched Ethernets.

There is a trade-off between an algorithm’s complexity and the strength of the service guarantees it provides. State-of-the-art solutions range from fast round-robin schedulers with O(N) guarantees, to O(log N) timestamp-based schedulers with optimal guarantees. While approximated timestamp-based schedulers exist that achieve near-optimal service guarantees in O(1) time, they do so only with significant constants hidden in the O() notation. For 10 Gbps links and beyond, even the magnitude of an algorithm’s constants limits scalability.

We present QFQ , a truly practical WFQ scheduler with near-optimal guarantees and truly low complexity (250×86 instructions per packet, irrespective of number of flows and configuration parameters). QFQ combines known techniques to group flows and round timestamps with a novel approach to manipulate multiple groups of flows at once, thus cutting the constant factors in the algorithm’s complexity, and enhancing scalability.

Link to paper: http://info.iet.unipi.it/~luigi/papers/20090731-qfq-full.pdf

Speaker Bio:

Luigi Rizzo, an Associate Professor of Computer Science at the University of Pisa (and PC co-chair of SIGCOMM 2009 ) is visiting the SRG /CL Monday.

Luigi has made many well-known contributions to the networking community: from the IPFW software firewall and dummynet network emulation code in FreeBSD (now also available for Linux), to high-performance network device polling kernel code, to multicast congestion control, among many other interesting things.

Luigi has generously offered to give an impromptu talk on his recent work: he’s designed and implemented a new O(1) packet scheduling algorithm that features tighter worst-case complexity bounds than previous scheduling algorithms. Luigi’s new algorithm is well suited to high-throughput routers and switches, which must make packet scheduling decisions to keep up with exponentially increasing line rates.