Programmable calendar queues for high-speed packet scheduling

Naveen Kr Sharma, Chenxingyu Zhao, Ming Liu, Pravein G. Kannan, Changhoon Kim, Arvind Krishnamurthy, Anirudh Sivaraman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Packet schedulers traditionally focus on the prioritized transmission of packets. Scheduling is often realized through coarse-grained queue-level priorities, as in today's switches, or through fine-grained packet-level priorities, as in recent proposals such as PIFO. Unfortunately, fixed packet priorities determined when a packet is received by the traffic manager are not sufficient to support a broad class of scheduling algorithms that require the priorities of packets to change as a function of the time it has spent inside the network. In this paper, we revisit the Calendar Queue abstraction and show that it is an appropriate fit for scheduling algorithms that not only require prioritization but also perform dynamic escalation of packet priorities. We show that the calendar queue abstraction can be realized using either dataplane primitives or control-plane commands that dynamically modify the scheduling status of queues. Further, when paired with programmable switch pipelines, we can realize programmable calendar queues that can emulate a diverse set of scheduling policies. We demonstrate the power of this abstraction using three case studies that implement variants of LSTF, Fair Queueing, and pFabric in order to provide stronger delay guarantees, burst-friendly fairness, and starvation-free prioritization of short flows, respectively. We evaluate the benefits associated with these scheduling policies using both a custom simulator and a small-scale testbed.

Original languageEnglish (US)
Title of host publicationProceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020
PublisherUSENIX Association
Pages685-699
Number of pages15
ISBN (Electronic)9781939133137
StatePublished - 2020
Event17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020 - Santa Clara, United States
Duration: Feb 25 2020Feb 27 2020

Publication series

NameProceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020

Conference

Conference17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020
CountryUnited States
CitySanta Clara
Period2/25/202/27/20

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Programmable calendar queues for high-speed packet scheduling'. Together they form a unique fingerprint.

Cite this