MMM
YYYY
Designing Approximate and Deployable SRPT Scheduler: A Unified Framework
设计近似的可部署SRPT调度器:一个统一的框架
近似および展開可能なSRPTスケジューラの設計:統一的枠組み
비슷 한 배치 가능 한 SRPT 스케줄 러 설계:통 일 된 프레임 워 크
Diseño de un planificador SRPT desplegable aproximado: un marco unificado
Concevoir un ordonnanceur SRPT déployable approximatif: un cadre unifié
дизайн приближенных к возможности развертывания планировщиков SRPT: единые рамки
Zhiyuan Wang 王志远 ¹, Jiancheng Ye ², Dong Lin ², Yipei Chen 陈亿沛 ², John C.S. Lui 呂自成 ¹
¹ The Chinese University of Hong Kong
香港中文大学
² Network Technology Lab and Hong Kong Research Center, Huawei Technologies Co., Ltd.
华为技术有限公司 网络科技实验室 香港研发中心
2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS), 26 August 2021
Abstract

The scheduling policy installed on switches of datacenters plays a significant role on congestion control. Shortest-Remaining-Processing-Time (SRPT) achieves the near-optimal average message completion time (MCT) in various scenarios, but is difficult to deploy as viewed by the industry. The reasons are two-fold: 1) many commodity switches only provide FIFO queues, and 2) the information of remaining message size is not available.

Recently, the idea of emulating SRPT using only a few FIFO queues and the original message size has been coined as the approximate and deployable SRPT (ADS) design. In this paper, we provide the first theoretical study on ADS design. Specifically, we first characterize a wide range of feasible ADS scheduling policies via a unified framework, and then derive the steady-state MCT and slowdown in the M/G/1 setting. We formulate the optimal ADS design as a non-linear combinatorial optimization problem, which aims to minimize the average MCT given the available FIFO queues. To prevent the starvation of long messages, we also take into account the fairness condition based on the steady-state slowdown.

The optimal ADS design problem is NP-hard in general, and does not exhibit monotonicity or sub-modularity. We leverage its decomposable structure and devise an efficient algorithm to solve the optimal ADS policy. Numerical results based on the realistic heavy-tail message size distribution show that the optimal ADS policy installed on eight FIFO queues is capable of emulating the true SRPT in terms of MCT and slowdown.
2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS)_1
2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS)_2
2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS)_3
Reviews and Discussions
https://www.hotpaper.io/index.html
Self-polarized RGB device realized by semipolar micro-LEDs and perovskite-in-polymer films for backlight applications
A highly sensitive LITES sensor based on a multi-pass cell with dense spot pattern and a novel quartz tuning fork with low frequency
Multi-wavelength nanowire micro-LEDs for future high speed optical communication
Luminescence regulation of Sb3+ in 0D hybrid metal halides by hydrogen bond network for optical anti-counterfeiting
Breaking the optical efficiency limit of virtual reality with a nonreciprocal polarization rotator
Simultaneously realizing thermal and electromagnetic cloaking by multi-physical null medium
Generation of lossy mode resonances (LMR) using perovskite nanofilms
Acousto-optic scanning multi-photon lithography with high printing rate
Tailoring electron vortex beams with customizable intensity patterns by electron diffraction holography
Miniature tunable Airy beam optical meta-device
Data-driven polarimetric imaging: a review
Robust measurement of orbital angular momentum of a partially coherent vortex beam under amplitude and phase perturbations



Previous Article                                Next Article
About
|
Contact
|
Copyright © Hot Paper