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
  • Dynamic interactive bitwise meta-holography with ultra-high computational and display frame rates
  • Yuncheng Liu, Ke Xu, Xuhao Fan, Xinger Wang, Xuan Yu, Wei Xiong, Hui Gao
  • Opto-Electronic Advances
  • 2024-01-25
  • Multi-dimensional multiplexing optical secret sharing framework with cascaded liquid crystal holograms
  • Keyao Li, Yiming Wang, Dapu Pi, Baoli Li, Haitao Luan, Xinyuan Fang, Peng Chen, Yanqing Lu, Min Gu
  • Opto-Electronic Advances
  • 2024-01-25
  • Physics-informed deep learning for fringe pattern analysis
  • Wei Yin, Yuxuan Che, Xinsheng Li, Mingyu Li, Yan Hu, Shijie Feng, Edmund Y. Lam, Qian Chen, Chao Zuo
  • Opto-Electronic Advances
  • 2024-01-25
  • Advancing computer-generated holographic display thanks to diffraction model-driven deep nets
  • Vittorio Bianco, Pietro Ferraro
  • Opto-Electronic Advances
  • 2024-01-16
  • Inverse design for material anisotropy and its application for a compact X-cut TFLN on-chip wavelength demultiplexer
  • Jiangbo Lyu, Tao Zhu, Yan Zhou, Zhenmin Chen, Yazhi Pi, Zhengtong Liu, Xiaochuan Xu, Ke Xu, Xu Ma, Lei Wang, Zizheng Cao, Shaohua Yu
  • Opto-Electronic Science
  • 2024-01-09
  • Improved spatiotemporal resolution of anti-scattering super-resolution label-free microscopy via synthetic wave 3D metalens imaging
  • Yuting Xiao, Lianwei Chen, Mingbo Pu, Mingfeng Xu, Qi Zhang, Yinghui Guo, Tianqu Chen, Xiangang Luo
  • Opto-Electronic Science
  • 2024-01-05
  • Wide-spectrum optical synthetic aperture imaging via spatial intensity interferometry
  • Chunyan Chu, Zhentao Liu, Mingliang Chen, Xuehui Shao, Guohai Situ, Yuejin Zhao, Shensheng Han
  • Opto-Electronic Advances
  • 2023-3-10
  • Flat soliton microcomb source
  • Xinyu Wang, Xuke Qiu, Mulong Liu, Feng Liu, Mengmeng Li, Linpei Xue, Bohan Chen, Mingran Zhang, Peng Xie
  • Opto-Electronic Science
  • 2023-12-29
  • Smart palm-size optofluidic hematology analyzer for automated imaging-based leukocyte concentration detection
  • Deer Su, Xiangyu Li, Weida Gao, Qiuhua Wei, Haoyu Li, Changliang Guo, Weisong Zhao
  • Opto-Electronic Science
  • 2023-12-28
  • Exceptional-point-enhanced sensing in an all-fiber bending sensor
  • Zheng Li, Jingxu Chen, Lingzhi Li, Jiejun Zhang, Jianping Yao
  • Opto-Electronic Advances
  • 2023-12-12
  • All-optical object identification and three-dimensional reconstruction based on optical computing metasurface
  • Dingyu Xu, Wenhao Xu, Qiang Yang, Wenshuai Zhang, Shuangchun Wen, Hailu Luo,
  • Opto-Electronic Advances
  • 2023-12-12



  • 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