Packet scheduling is essentially a decision making process. Below is a subset of typical packet scheduling algorithms, highlighted by the common denominators: metadata leveraged to support the decision, the logic of the decision, and the feature(s).

The summary focuses on the Dequeue interface, neglecting the Enqueue interface and possible Active Queue Management (AQM). Hopefully, it could help to obtain a fast overview of the characteristics of the canonical packet scheduling algorithms. For further details, there are papers illuminating insights on the abstractions of scheduling policies/queueing disciplines, e.g., Programmable Packet Scheduling at Line Rate.

First In First Out (FIFO)/First Come First Serve (FCFS)
  • Metadata: the packet's time of arrival
  • Logic: advance the packet with the earliest arrival
  • Feature: work-conserving; also known as Drop Tail if combined with a simple if-full-then-drop buffer management policy
Strict Priority (SP)
  • Metadata: the packet type of service field or features to support a more complex service differentiation method
  • Logic: advance the packet belonging to the service of top priority (after classification); FIFO is applied to packets with the same priority
  • Feature: work-conserving
Stochastic Fair Queueing (SFQ)
Shortest Job First (SJF)
  • Metadata: flow size
  • Logic: similar to the equivalence in OS, SJF advances the flow with minimum flow size
  • Feature: work-conserving; assume the flow size is known
Earliest Deadline First (EDF)
  • Metadata: the deadline for the flow
  • Logic: advance the packet with the minimum deadline
  • Feature: work-conserving; assume the deadline of the flow is encoded in the packet field
Shortest Remaining Process Time
  • Metadata: the remaining flow size
  • Logic: advance the packet belong to the flow with minimum remaining flow size
  • Feature: work-conserving; optimal in terms of minimizing flow completion time (in a single link)
  • Literature: pFabric
Start Time Fair Queueing (STFQ)
  • Metadata: the virtual starting time maintained by the scheduler
  • Logic: advance the packet with the minimum virtual starting time; update the value upon each Dequeue
  • Feature: work-conserving
  • Literature: Start-time Fair Queuing
Hierarchical Packet Fair Queueing (HPFQ)
Round Robin (RR)/Weighted Round Robin (WRR)
Deficit Round Robin (DRR)
  • Metadata: a quantum that is added to the deficit of each queue
  • Logic: track the credits for each flow and send the packet that fits the flow's deficit
  • Feature: work-conserving/non-work-conserving variants; approximate the bit-by-bit round robin; memory inefficient due to the cost of maintenance
Token/leaky Bucket
  • Metadata: the number of tokens per step/constant leaky rate
  • Logic: for the token packet (with the limited size of tokens), the packet will be forwarded only if there are enough tokens; for the leaky bucket, packets are always queued (and might be dropped due to constraint size) on the bucket and the bucket strives for a constant fixed rate service;
  • Feature: conduct traffic shaping/rate-limiting; non-work-conserving; token bucket can be of variable rate while leaky bucket constant rate; token bucket throws away tokens but not packets while leaky packet discards packets when the bucket is full
Least Slack-Time First (LSTF)
  • Metadata: the slack value
  • Logic: slacking initialization at network edges and slack modification (deduced by queueing time) at the network core; the packet with the minimum slack value is prioritized for scheduling
  • Feature: slack value encodes the concept of path history of the packet; slack initialization is flexible
  • Literature: A New Algorithm for Scheduling Periodic, Real-Time Tasks, Universal Packet Scheduling