Constrained max-min fair scheduling of variable-length packet-flows to multiple servers
Constrained max-min fair scheduling of variable-length packet-flows to multiple servers
复制标题
到多个服务器的可变长度数据包流的约束最大最小公平调度
DOI：
10.1007/s12243-017-0599-y
复制
发表时间：
2016
影响因子：
1.9
通讯作者：
Yiqiang Q. Zhao
中科院分区：
文献类型：
--
作者：
J. Khamse;G. Kesidis;I. Lambadaris;B. Urgaonkar;Yiqiang Q. Zhao
在本文中，我们研究了一个多服务器排队系统，其中每个用户被约束只能从指定的服务器子集获得服务。在这种情况下，公平的分组调度提出了新的挑战，我们在本文中解决。具体来说，我们观察到，在存在放置约束的情况下，不同服务器上可用资源（特别是带宽）的最大最小公平分配会导致不同水平的公平服务速率。为了实现最大最小公平服务速率，我们提出了一种受赤字轮询（DRR）算法启发的数据包调度算法。调度器以逐轮的方式将令牌分配给流，其中令牌在每轮开始时分配给流是加权的最大最小公平。因此，我们称之为多服务器最大最小公平DRR （MSMF-DRR）。通过最坏情况性能分析显示了MSMF-DRR算法在实现公平性方面的性能。除了分析结果外，还进行了数值实验来说明该算法所提供的服务隔离和延迟保证。通常，这种受约束的多服务器排队系统的调度器可以应用于许多现代数据网络应用程序，特别是在云计算中，其中虚拟机和/或进程争夺分布在异构服务器上的不同IT资源，而不同的进程可能由于其服务质量要求和服务器的异构性而具有优于服务器的首选项。
In this paper, we study a multi-server queuing system wherein each user is constrained to get service only from a specified subset of servers. Fair packet scheduling in such a setting poses novel challenges that we address in this paper. Specifically, we observe that max-min fair allocation of the available resource over different servers (notably bandwidth) in the presence of placement constraints results in different levels of fair service-rates. To achieve the max-min fair service rates, we propose a novel packet scheduler which is inspired by the deficit-round robin (DRR) algorithm. The scheduler allocates tokens to flows in a round-by-round manner, where token allocation to flows at the beginning of each round is weighted max-min fair. So, we have called it multi-server max-min fair DRR (MSMF-DRR). The performance of the MSMF-DRR algorithm in terms of achieving fairness is shown through a worst-case performance analysis. In addition to analytical results, numerical experiments are also carried out to illustrate service isolation and the delay guarantee that are provided by the algorithm. Generally, a scheduler for such a constrained multi-server queuing system can be applicable in many modern data-networking applications, especially in cloud computing wherein virtual machines and/or processes vie for different IT resources distributed over heterogenous servers, while different processes may have preferences over servers owing to their quality-of-service requirements and the heterogeneity of servers.