(Conference Paper) Designing Approximate and Deployable SRPT Scheduler: A Unified Framework
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), 2021-08-26

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.
Designing Approximate and Deployable SRPT Scheduler: A Unified Framework_1
Designing Approximate and Deployable SRPT Scheduler: A Unified Framework_2
Designing Approximate and Deployable SRPT Scheduler: A Unified Framework_3
  • Perspectives and challenges for lead-free energy-storage multilayer ceramic capacitors
  • Peiyao Zhao, Ziming Cai, Longwen Wu, Chaoqiong Zhu, Longtu Li, Xiaohui Wang
  • Journal of Advanced Ceramics
  • 2021-11-12
  • On the Asymptotic Stability of Wave Equations Coupled by Velocities of Anti-symmetric Type
  • Yan Cui, Zhiqiang Wang
  • Chinese Annals of Mathematics, Series B
  • 2021-11-12
  • Effects on the emission discrepancy between two-dimensional Sn-based and Pb-based perovskites
  • Zhang Tianju, Zhou Chaocheng, Lin Jia, Wang Jun
  • Chinese Optics Letters
  • 2021-11-11
  • Hydrogels with Dynamically Controllable Mechanics and Biochemistry for 3D Cell Culture Platforms
  • Hai-Yang Wu, Lei Yang, Jiang-Shan Tu, Jie Wang, Jin-Ge Li, Hong-Ying Lv, Xiao-Niu Yang
  • Chinese Journal of Polymer Science
  • 2021-11-09
  • Feature and Tendency of Technology Transfer in Z-Park Patent Cooperation Network: From the Perspective of Global Optimal Path
  • Jun Guan, Jingying Xu, Yu Han, Dawei Wang, Lizhi Xing
  • Journal of Data and Information Science
  • 2021-11-08
  • Mechanical Design and Dynamic Compliance Control of Lightweight Manipulator
  • Shao-Lin Zhang, Yue-Guang Ge, Hai-Tao Wang, Shuo Wang
  • International Journal of Automation and Computing
  • 2021-11-06
  • Scalping or Line-sitting: The Role of Speculators
  • Qianqian Chen, Zhenyang Shi, Yi Yang
  • Journal of Systems Science and Systems Engineering
  • 2021-11-06
  • Substrate damage and recovery after giant clam shell mining at remote coral reefs in the southern South China Sea
  • Shengnan Zhou, Qi Shi, Hongqiang Yang, Xiyang Zhang, Xiaoju Liu, Fei Tan, Pin Yan
  • Journal of Geographical Sciences
  • 2021-11-05
  • Some Questions Regarding Verification of Carleson Measures
  • Fangwen Deng, Caiheng Ouyang, Ru Peng
  • Acta Mathematica Scientia
  • 2021-11-05
  • Direct growth of hexagonal boron nitride films on dielectric sapphire substrates by pulsed laser deposition for optoelectronic applications
  • Gaokai Wang, Jingren Chen, Junhua Meng, Zhigang Yin, Ji Jiang, Yan Tian, Jingzhen Li, Jinliang Wu, Peng Jin, Xingwang Zhang
  • Fundamental Research
  • 2021-11-05
  • Climate Suitability Assessment of Human Settlements for Regions along the Belt and Road
  • LIN Yumei, LI Peng, FENG Zhiming, YANG Yanzhao, YOU Zhen, ZHU Fuxin
  • Chinese Geographical Science
  • 2021-11-03

  • pSAV: A Practical and Decentralized Inter-AS Source Address Validation                                A Proactive Failure Tolerant Mechanism for SSDs Storage Systems based on Unsupervised Learning
    Copyright © PubCard