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
  • Broadband ultrasound generator over fiber-optic tip for in vivo emotional stress modulation
  • Jiapu Li, Xinghua Liu, Zhuohua Xiao, Shengjiang Yang, Zhanfei Li, Xin Gui, Meng Shen, He Jiang, Xuelei Fu, Yiming Wang, Song Gong, Tuan Guo, Zhengying Li
  • Opto-Electronic Science
  • 2025-07-25
  • Non-volatile reconfigurable planar lightwave circuit splitter enabled by laser-directed Sb2S3 phase transitions
  • Shixin Gao, Tun Cao, Haonan Ren, Jingzhe Pang, Ran Chen, Yang Ren, Zhenqing Zhao, Xiaoming Chen, Dongming Guo
  • Opto-Electronic Technology
  • 2025-07-18
  • Progress in metalenses: from single to array
  • Chang Peng, Jin Yao, Din Ping Tsai
  • Opto-Electronic Technology
  • 2025-07-18
  • 30 years of nanoimprint: development, momentum and prospects
  • Wei-Kuan Lin, L. Jay Guo
  • Opto-Electronic Technology
  • 2025-07-18
  • Review for wireless communication technology based on digital encoding metasurfaces
  • Haojie Zhan, Manna Gu, Ying Tian, Huizhen Feng, Mingmin Zhu, Haomiao Zhou, Yongxing Jin, Ying Tang, Chenxia Li, Bo Fang, Zhi Hong, Xufeng Jing, Le Wang
  • Opto-Electronic Advances
  • 2025-07-17
  • Coulomb attraction driven spontaneous molecule-hotspot paring enables universal, fast, and large-scale uniform single-molecule Raman spectroscopy
  • Lihong Hong, Haiyao Yang, Jianzhi Zhang, Zihan Gao, Zhi-Yuan Li
  • Opto-Electronic Advances
  • 2025-07-17
  • Multiphoton intravital microscopy in small animals of long-term mitochondrial dynamics based on super‐resolution radial fluctuations
  • Saeed Bohlooli Darian, Jeongmin Oh, Bjorn Paulson, Minju Cho, Globinna Kim, Eunyoung Tak, Inki Kim, Chan-Gi Pack, Jung-Man Namgoong, In-Jeoung Baek, Jun Ki Kim
  • Opto-Electronic Advances
  • 2025-07-17
  • Research progress on generating perfect vortex beams based on metasurfaces
  • Xiujuan Liu, Manna Gu, Ying Tian, Mingfeng Zheng, Bo Fang, Zhi Hong, Chee Leong Tan, Xufeng Jing
  • Opto-Electronic Science
  • 2025-07-09
  • Non-volatile tunable multispectral compatible infrared camouflage based on the infrared radiation characteristics of Rosaceae plants
  • Xin Li, Xinye Liao, Junxiang Zeng, Zao Yi, Xin He, Jiagui Wu, Huan Chen, Zhaojian Zhang, Yang Yu, Zhengfu Zhang, Sha Huang, Junbo Yang
  • Opto-Electronic Advances
  • 2025-07-09
  • Spectro-polarimetric detection enabled by multidimensional metasurface with quasi-bound states in the continuum
  • Haoyang He, Fangxing Lai, Yan Zhang, Xue Zhang, Chenyi Tian, Xin Li, Yongtian Wang, Shumin Xiao, Lingling Huang
  • Opto-Electronic Advances
  • 2025-06-30
  • Emerging low-dimensional perovskite resistive switching memristors: from fundamentals to devices
  • Shuanglong Wang, Hong Lian, Haifeng Ling, Hao Wu, Tianxiao Xiao, Yijia Huang, Peter Müller-Buschbaum
  • Opto-Electronic Advances
  • 2025-06-27
  • CW laser damage of ceramics induced by air filament
  • Chuan Guo, Kai Li, Zelin Liu, Yuyang Chen, Junyang Xu, Zhou Li, Wenda Cui, Changqing Song, Cong Wang, Xianshi Jia, Ji'an Duan, Kai Han
  • Opto-Electronic Advances
  • 2025-06-27



  • 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