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
  • Three-dimensional multichannel waveguide grating filters
  • Si-Yu Yin, Qi Guo, Shan-Ren Liu, Ju-Wei He, Yong-Sen Yu, Zhen-Nan Tian, Qi-Dai Chen
  • Opto-Electronic Science
  • 2024-08-14
  • Ka-Band metalens antenna empowered by physics-assisted particle swarm optimization (PA-PSO) algorithm
  • Shibin Jiang, Wenjun Deng, Zhanshan Wang, Xinbin Cheng, Din Ping Tsai, Yuzhi Shi, Weiming Zhu
  • Opto-Electronic Science
  • 2024-07-26
  • Complete-basis-reprogrammable coding metasurface for generating dynamically-controlled holograms under arbitrary polarization states
  • Zuntian Chu, Xinqi Cai, Ruichao Zhu, Tonghao Liu, Huiting Sun, Tiefu Li, Yuxiang Jia, Yajuan Han, Shaobo Qu, Jiafu Wang
  • Opto-Electronic Advances
  • 2024-07-26
  • Optical micro/nanofiber enabled tactile sensors and soft actuators: A review
  • Lei Zhang, Yuqi Zhen, Limin Tong
  • Opto-Electronic Science
  • 2024-07-26
  • Soliton microcomb generation by cavity polygon modes
  • Botao Fu, Renhong Gao, Ni Yao, Haisu Zhang, Chuntao Li, Jintian Lin, Min Wang, Lingling Qiao, Ya Cheng
  • Opto-Electronic Advances
  • 2024-07-25
  • Focus control of wide-angle metalens based on digitally encoded metasurface
  • Yi Chen, Simeng Zhang, Ying Tian, Chenxia Li, Wenlong Huang, Yixin Liu, Yongxing Jin, Bo Fang, Zhi Hong, Xufeng Jing
  • Opto-Electronic Advances
  • 2024-07-23
  • Spin-controlled generation of a complete polarization set with randomly-interleaved plasmonic metasurfaces
  • Sören im Sande, Yadong Deng, Sergey I. Bozhevolnyi, Fei Ding
  • Opto-Electronic Advances
  • 2024-07-23
  • An inversely designed integrated spectrometer with reconfigurable performance and ultra-low power consumption
  • Ang Li, Yifan Wu, Chang Wang, Feixia Bao, Zongyin Yang, Shilong Pan
  • Opto-Electronic Advances
  • 2024-07-17
  • OptoGPT: A foundation model for inverse design in optical multilayer thin film structures
  • Taigao Ma, Haozhu Wang, L. Jay Guo
  • Opto-Electronic Advances
  • 2024-07-10
  • Paving continuous heat dissipation pathways for quantum dots in polymer with orange-inspired radially aligned UHMWPE fibers
  • Xuan Yang, Xinfeng Zhang, Tianxu Zhang, Linyi Xiang, Bin Xie, Xiaobing Luo
  • Opto-Electronic Advances
  • 2024-07-05
  • Multiplexed stimulated emission depletion nanoscopy (mSTED) for 5-color live-cell long-term imaging of organelle interactome
  • Yuran Huang, Zhimin Zhang, Wenli Tao, Yunfei Wei, Liang Xu, Wenwen Gong, Jiaqiang Zhou, Liangcai Cao, Yong Liu, Yubing Han, Cuifang Kuang, Xu Liu
  • Opto-Electronic Advances
  • 2024-07-05



  • 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