Eiffel: Efficient and Flexible Software Packet Scheduling

Introduction

Problem:

  1. The need for programmable scheduling is increasing because of the more sophisticated policies

  2. Cpu utilization of kernel packet pacing is up to 10 - 12% nowadays.

Key Insights:

  1. Now scheduling policy that has m ranking functions associated with a packet typically requires m priority queues in which this packet needs to be enqueued and dequeued, which translates roughly to O(m logn) operations per packet for a scheduler with n packets enqueued.
    The priority can be represented as integers and integer priority queues can have O(1) for packet insertion and extraction thus will make origin O(m logn) lower to the O(m) based on FFS(find first set CPU instruction) (if we can introduce this promotion,it may get some benefit and how can we separate our work from theirs?)
  2. packet scheduling programming models do not both support per-flow packet scheduling and reordering of packets on a dequeue operation (I think the first one may be more related to our topics)

Design

FFS based queue

data in Bitmap Meta data:
0 represents none in this priority queue and the opposite is 1.

use FFS (find first set) instruction to find max or min priority queue

Hierarchical FFS-based queue

The reason why Hierarchical FFS-based queue is confused to me.
(FFS instruction only can find max or min in 6 bit based on fig 2. And in order to control more priorities, multi-plane is introduced)

Circular Hierarchical FFS-based queue

One word bitmap may still not undertake the mount of priority queues and Circular Hierarchical FFS-based queue can handle this issue. Read the paper to learn this design

Thought

This paper is a NSDI 19 paper, the reason why I read this paper is to find some scheduling design for the scheduling of LINUX IO stack.

However, what I learn from this paper is not a concrete algorithm for mutil-queue scheduling but a software scheduling model suited for any mutil-queue scheduling policy.