一种使用历史信息的长期公平队列调度算法

摘要

经典的基于时延的队列调度仅关注调度时刻的队列延时,对历史信息并无记忆性,从而在业务流突变时排队延时公平性无法得到保障.本文提出一种长期公平调度算法,不仅综合考虑队列长度、到达速率等即时参量,而且考虑历史参量——历史延时累计量,使得调度更加理性,排队延时不会随流量突变而突变.另外,3个调度参量的关系式并非人为给出,而是通过对长期公平性的建模和对长期优化问题的推导得来.仿真对比了WRR,RPF,EDF算法,证实该算法中的队列延时不仅具有较高的公平性还具有较高的稳定性.%The classical delay-based queuing scheduling only focuses on the queuing delay in its scheduling instance,but without memorizing the historical information.Therefore fairness of its queuing delay cannot be guaranteed when the traffic flows suffer unexpected great change.A long-term fairness oriented scheduling algorithm was proposed,which had not only synthetically considered the instantaneous parameters,i.e.queue length and the traffic arrival rate,but also considered the historical parameter,i.e.the historical accumulation of delay.Using this algorithm,the scheduling could be more rational,and the queuing delay wouldn't change as vastly as the traffic flows.In addition,another contribution in this paper is that the relationship among the aforementioned three parameters were not'be given',but'be deduced'.In another word,this paper modeled the long-term fairness and then solved the long-term optimization problem,so as to obtain the relationship.At last,the proposed algorithm was compared with the WRR,RPF and EDF algorithms,confirming that the algorithm in this paper could gain higher fairness and higher stabilization.