Eiffel: Eifficient and Flexible Packet Scheduling

Ahmed Saeed, Yimeng Zhao, Nandita Dukkipati, Ellen Zegura, Mostafa Ammar, Khaled Harras, and Amin Vahdat

Georgia Institute of Technology, Carnegie Mellon University, and Google


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.



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.

Getting Started

Eiffel is implemented in the Linux kernel as a rate limiting Qdisc. No assumptions are made about the environment running either implementations.


  1. Clone the Eiffel linux repo
    git clone https://github.com/saeed/eiffel_linux.git
    cd eiffel_linux
  2. 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.
  3. Compile and install kernel using the .config file in the repo.
  4. 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.
  5. 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.


For questions/comments please email ahmed dot saeed at gatech dot edu