Eiffel - Eifficient and Flexible Packet Scheduling

Packet scheduling determines the ordering of packets in a queuing data structure with respect to some ranking function that is mandated by a scheduling policy. It is the core component in many recent innovations to optimize network performance and utilization. Eiffel solves the problem of providing efficient and programmable schedulers in software. Software schedulers have several advantages over hardware including shorter development cycle and flexibility in functionality and deployment location. Eiffel substantially improves current software packet scheduling performance, while maintaining flexibility, by exploiting underlying features of packet ranking; namely, packet ranks are integers and, at any point in time, fall within a limited range of values.

FAQ

What motivated the work?

Packet scheduling is the core component in many recent innovations to optimize network performance and utilization. It has proven difficult to achieve scheduler efficiency in software schedulers, especially handling packets at high line rates, without limiting the supported scheduling policies. Furthermore, CPU-efficient implementation of even the simplest scheduling policies is still an open problem for most platforms. Eiffel tackles and solves this pressing need in modern networks.

How does Eiffel achieve both efficiency and flexibility?

Eiffel leverages a key characterstic of packet ranks: packet ranks can be represented as integers that at any point in time fall within a limited window of values. Thus, Eiffel employs integer priority queues that have O(1) overhead for packet insertion and extraction. Then, Eiffel combines multiple priority queues to implement arbitrarily complex scheduling policies.

What's the overhead of Eiffel?

Eiffel shifts the overhead of packet scheduling, from being dependent on the number of packets enqueued or the number of flows with enqueued packets, to the complexity of the scheduling policy itself (e.g., number of priority classes).

Can I program using Eiffel?

You can express policies using Eiffel programming primitives presented in the paper. The Eiffel abstraction provides a direct mapping to the way priority queues should be structured to implement the policy. All examples presented in the paper were hard coded following the aforementioned approach. A compiler that converts Eiffel primitvies to priority queues is under development.

What are the limitations of Eiffel?

Eiffel provides it CPU efficiency at the expense of using extra memory. Eiffel requires preallocation of memory (provisioning for the worst case) as well as using slack memory that requires a total preallocation of 2x the worst case memory requirement of a memory efficient algorithm.
Eiffel is a software-only solution and does not handle the complexities arising from implementing it in hardware.

Tutorial

Clone the Eiffel linux repo
git clone https://github.com/saeed/eiffel_linux.git cd eiffel_linux
Checkout the FFS-based Qdisc for a full Eiffel-based rate limiter
git checkout working_ffs-based_qdisc
Note that for Carousel experiments the working_ffs-based_qdisc branch can also be used as a Linux implementation of Carousel as it relies on a time-based data structure for packet sorting and TSQ backpressure. For a Timing Wheel-based implementation, checkout the v4.10-gq branch.
Compile and install kernel using the .config file in the repo.
Install GQ Qdisc
tc qdisc add dev eth1 root gq
Replace eth1 with name of the networking device for which you are applying the rate limit.
The install qdisc will enforce the pacing rate set by the congestion control algorithm applied to a flow. To enforce a custom rate limit, use the SO_MAX_PACING_RATE socket option to set the custom rate.

Eiffel: Eifficient and Flexible Packet Scheduling

FAQ