fAHRW+: Fairness-aware and locality-enhanced scheduling for multi-server systems

This paper discusses scheduling issues of multi-server systems. There are three desirable properties of multi-server scheduling: load balancing, fairness and locality. The three properties are often conflicting with each other. There is no scheduling scheme that possesses all the three properties. In this paper, we first propose the fairness-aware highest random weight (fHRW) scheduling algorithm as an attempt to achieve fairness and locality. fHRWtries to service packets proportionally according to priorities of flows and schedule the packets from the same flow onto the same server. Then, we solve the imbalanced load issue of fHRW by improving the hash function HRW to an adaptive HRW (AHRW). fAHRW is more efficient (in terms of load balancing) and fair than fHRW, but it still may suffer unfairness in some cases. We further enhance fAHRW to fAHRW⁺ by proposing a new hash function AHRW⁺ that considers fairness as well as locality. Extensive simulations have been carried out to evaluate the performance of fAHRW⁺. The results show that fAHRW⁺ can provide good load balancing, locality and fairness.