A Fair and Efficient Resource Allocation Scheme for Multi-Server Distributed Systems and Networks

摘要

Maintaining efficiency and fairness is a challenging problem in distributed systems and networks. In this paper, we focus on distributed multi-server systems and networks in which each user may be allocated resources by different servers. Reemphasizing polling systems as abstractions of resource sharing systems, in this paper, first we introduce a multi-server polling system in which each server (resource) can poll (be allocated to) only a subset of queues (users) in the system to model a wide range of multi-server systems such as multihomed networks and cloud computing. Then, to obtain a fair resource allocation vector to queues, a network utility maximization problem with a general utility function is defined. Depending on the type of the utility function, the presented scheme can attain different kinds of fairness such as weighted proportional and max-min fairness. Although maintaining fairness is important in many applications, providing efficiency is also crucial. Hence, we present an efficient algorithm to convert the obtained fair resource allocation vector into a Markovian routing matrix to determine the polling order of queues. This algorithm is capable of improving performance measures such as delay variance and mitigating short-term unfairness by minimizing the probability of consecutive polling of the same queue. Two distributed schemes are presented to obtain fairness and efficiency in even highly dynamic and distributed environments. The effectiveness of the presented schemes is also studied through simulation and numerical evaluation. Our results show their success in attaining fairness and efficiency in dynamic multi-server distributed systems and networks.