Heavy-Traffic Optimal Size-and State-Aware Dispatching

被引：0

作者：

Xie R. ^{[1
]}

Grosof I. ^{[2
,3
]}

Scully Z. ^{[4
]}

机构：

[1] Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, CA

[2] Carnegie Mellon University, Computer Science Department, Pittsburgh, PA

[3] Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA

[4] School of Operations Research and Information Engineering, Cornell University, Ithaca, NY

来源：

Performance Evaluation Review | 2024年 / 52卷 / 01期

基金：

美国国家科学基金会;

关键词：

asymptotic optimality; dispatching; fcfs; heavy traffic; latency; response time; sojourn time;

D O I：

10.1145/3673660.3655059

中图分类号：

O211 [概率论（几率论、或然率论）];

学科分类号：

摘要：

We study the problem of dispatching jobs to multiple FCFS (First-Come, First-Served) queues. We consider the case where the dispatcher is size-aware, meaning it learns the size (i.e. service time) of each job as it arrives; and state-aware, meaning it always knows the amount of work (i.e. total remaining service time) at each queue. While size-and state-aware dispatching to FCFS queues has been extensively studied, little is known about optimal dispatching for the objective of minimizing mean delay. In this work, we propose the first size-and state-aware dispatching policy, called CARD (Controlled Asymmetry Reduces Delay), that provably minimizes mean delay in heavy traffic. This work summarizes our full paper. © 2024 Owner/Author.

引用

页码：7 / 8

页数：1

共 15 条

[1]

Down D.G., Wu R., Multi-layered round robin routing for parallel servers, Queueing Systems, 53, pp. 177-188, (2006)

[2]

Feng H., Misra V., Rubenstein D., Optimal state-free, sizeaware dispatching for heterogeneous M/G/-type systems, Performance Evaluation, 62, 1-4, pp. 475-492, (2005)

[3]

Grosof I., Scully Z., Harchol-Balter M., Load balancing guardrails: Keeping your heavy traffic on the road to low response times, Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3, 2, pp. 1-31, (2019)

[4]

Harchol-Balter M., Crovella M.E., Murta C.D., On choosing a task assignment policy for a distributed server system, J. Parallel and Distrib. Comput., 59, 2, pp. 204-228, (1999)

[5]

Harchol-Balter M., Scheller-Wolf A., Young A.R., Surprising results on task assignment in server farms with high-variability workloads, Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems., pp. 287-298, (2009)

[6]

Hurtado-Lange D., Theja Maguluri S., A load balancing system in the many-server heavy-traffic asymptotics, Queueing Systems, 101, 3-4, pp. 353-391, (2022)

[7]

Hyytia E., Jacko P., Righter R., Routing with too much information?, Queueing Systems, 100, 3-4, pp. 441-443, (2022)

[8]

Hyytia E., Penttinen A., Aalto S., Size-and state-aware dispatching problem with queue-specific job sizes, European Journal of Operational Research, 217, 2, pp. 357-370, (2012)

[9]

Hyytia E., Righter R., On Sequential Dispatching Policies, 2022 32nd International Telecommunication Networks and Applications Conference (ITNAC)., pp. 1-6, (2022)

[10]

Hyytia E., Righter R., On Dynamic Size-Aware Dispatching and Computation of the Optimal Actions, (2023)

← 1 2 →