지난 십여년동안 각 세션에게 대역폭을 공평하게 분배하기 위한 많은 연구가 수행되었다. 이 문제에 있어서 가장 중요한 도전은 확장성 있는 구현(scalable implementation)을 실현하면서도 동시에 높은 공평성을 성취하는 것이다. 여기서 높은 공평성이란 작은 시간 구간에 대해서도 대역폭이 공평하게 분배되는 것이다. 불행히도 현존하는 스케줄링 알고리즘들은 확장성 있는 구현에 문제점이 있거나 혹은 공평성이 철저히 낮다는 결점을 갖고 있다. 본 논문에서 우리는 확장성을 잃지 않으면서도 동시에 합리적인 수준의 공평성을 제공하는 패킷 스케줄링 알고리즘을 제안한다. 제안하는 알고리즘은 결손을 보완하는 계층적 라운드-로빈 알고리즘이다. 계층적 라운드-로빈 알고리즘은 구현 복잡도가 상수 시간인 반면, 성취할 수 있는 공평성은 PGPS(Packet-by-Packet Generalized Processor Sharing) 알고리즘과 비슷함을 보인다. PGPS 알고리즘은 N을 세션 수라고 할 때 정렬된 우선 순위 큐를 사용하기 때문에 O(log N) 구현 복잡도를 가지므로 확장성이 떨어진다.
For the last several decades, many researches have been performed to distribute bandwidth fairly between sessions. In this problem, the most important challenge is to realize a scalable implementation and high fairness simultaneously. Here high fairness means that bandwidth is distributed fairly even in short time intervals. Unfortunately, existing scheduling algorithms either are lack of scalable implementation or can achieve low fairness. In this paper, we propose a scheduling algorithm that can achieve feasible fairness without losing scalability. The proposed algorithm is a Hierarchical Deficit Round-Robin (H-DRR). While H-DRR requires a constant time for implementation, the achievable fairness is similar to that of Packet-by-Packet Generalized Processor Sharing(PGPS) algorithm. PGPS has worse scalability since it uses a sorted-priority queue requiring O(log N) implementation complexity where N is the number of sessions.
