Constrained max-min fair scheduling of variable-length packet-flows to multiple servers
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.
|Keywords||Cloud computing, Convex optimization, K-server algorithms, Max-min fairness, Packet scheduling, Placement constraints, Resource allocation|
|Journal||Annales des Telecommunications/Annals of Telecommunications|
Khamse-Ashari, J. (J.), Kesidis, G. (G.), Lambadaris, I, Urgaonkar, B. (B.), & Zhao, Y. (2017). Constrained max-min fair scheduling of variable-length packet-flows to multiple servers. Annales des Telecommunications/Annals of Telecommunications, 1–19. doi:10.1007/s12243-017-0599-y