Year
Month
(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
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.
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
  • Scaling metasurface design: from reusable unit cells to full-metasurface inverse design
  • Eunbi Jang, Jiwan Hong, Ho-Jun Lee, Seokju Choi, Hyewon Suk, Chanik Kang, Sunae So, Haejun Chung
  • Opto-Electronic Science
  • 2026-10-20
  • Ultrafast all-optical biomimetic encoder for spiking neural networks
  • Qijun Bian, Fangchen Hu, Junlian Jia, Aolong Sun, Sizhe Xing, Boyu Dong, An Yan, Ziwei Li, Jianyang Shi, Nan Chi, Junwen Zhang
  • Opto-Electronic Science
  • 2026-10-20
  • Windmill-shaped multi-unit piezoelectric ceramic tuning fork for cooperatively enhanced photoacoustic methane sensing
  • Botao Liu, Guowei Han, Runqiu Wang, Xuan Yang, Haiyue Sun, Shunda Qiao, Ying He, Angelo Sampaolo, Vincenzo Spagnolo, Yufei Ma
  • Opto-Electronic Science
  • 2026-10-20
  • Ultrafast laser direct writing of highly conductive copper micropatterns
  • Songyan Xue, Chunsan Deng, Mingduo Zhang, Huace Hu, Fayu Chen, Leimin Deng, Jianguo Liu, Hui Gao, Wei Xiong
  • Opto-Electronic Manufacturing
  • 2026-09-30
  • Recent advances in fiber-tip integration based on femtosecond laser 3D printing
  • Yuye Xuan, Dezhi Zhu, Dejun Liu, Ying Wang, Yiping Wang, Changrui Liao
  • Opto-Electronic Manufacturing
  • 2026-09-30
  • Neural holography enabled multi-beam steering for multi-task classifier
  • Lin Wu, Mian Wu, Zhen Li, Ying Qiu, Zichen Liu, Yongquan Zeng, Guozhen Liang, Hanbing Li, Guoxing Zheng, Zhixue He, Xi Xiao, Qi Jie Wang, Jin Tao, Shaohua Yu
  • Opto-Electronic Technology
  • 2026-09-30
  • Laser direct writing of nonlinear metasurfaces on phase-change material Ge₂Sb₂Te₅ for enhanced third harmonic generation
  • Lanpeng Guo, Haochong Liu, Shixin Gao, Ming Tang, Minghui Hong, Tun Cao
  • Opto-Electronic Technology
  • 2026-09-30
  • Nearly vertically emitted nonlinear light sources with high efficiencies enabled by high-Q nearly-degenerate polygon modes
  • Chuntao Li, Yingnuo Qiu, Renhong Gao, Lingling Qiao, Jielei Ni, Min Wang, Jintian Lin, Ya Cheng
  • Opto-Electronic Technology
  • 2026-09-30
  • Multiple degrees-of-freedom optical encryption via pixel-resolved vectorial holography
  • Jianzhong Peng, Haoxian Zhou, Mengzhe Shen, Dapeng Wang, Yu Chen, Renlong Zhang, Fangrui Lin, Xiaoyu Weng, Junle Qu
  • Opto-Electronic Technology
  • 2026-09-30
  • Recent progress on mid-infrared and terahertz dual-comb spectroscopy
  • Zhuoren Wan, Min Li, Binbin Liu, Yu Xia, Yuan Chen, Xiuxiu Zhang, Dongxu Zhu, Yan Dai, Sinan Tao, Hua Li, Ming Yan, Heping Zeng
  • Opto-Electronic Technology
  • 2026-09-30
  • Optical packaging of photonic integrated circuits: bottlenecks and potential solutions
  • Rodrigo Rendeiro, Hugo Neto, Diogo Vaz, Carla Rodrigues, Heming Wei, Jan Nedoma, Antonio Teixeira, Francisco Rodrigues, Carlos Marques
  • Opto-Electronic Technology
  • 2026-09-30



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