Abstract: 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.

Key words: long-term fairness, queue scheduling, queuing delay, long-term optimization, historical information