Review on
Stratified Round Robin: A Low Complexity Packet Scheduler with Bandwidth Fairness and Bounded Delay


Through a background survey, we see there are a group of fair scheduling algorithms all sharing same basic ideas: Put flows into classes based on their weight approximating to some scale, schedule flow classes using deadline based algorithms and then schedule flows in each class using some variant of Round Robin. By hybriding these two types of algorithms, the new scheduler can achieve approximate WFQ performance (low delay and low burstiness) and RR complexity(O(1)). The approximate sorting can be done in different method. This paper shows a method fitting for simple hardware implementation.

Though the paper provides a practical implementation for the scheduler, the intrinsic idea is not quite new. Some previous research papers have alreay developed the similiar method with only a slight variant (Smoothed RR, Aliquem, Bin sorting etc.). The paper does refer these papers but doesn't compare with these works. A newer paper (FRR) pursues the same approach but uses other variant of the inter and intra packet scheduling algorithms and proves to achieve better delay performance.

The paper claims that the timestamp-based algorithms need to sort packet deadline and therefore suffer from complexity logarithmic in the number of flow N. The paper fails to mention an efficient implementation of such kind of algorithms with only O(1) complexity: approximate radix sorting or timing wheels.

Generally, all deadline-based scheduling algorithms bound the queue head packet's delay. I am not sure why the paper emphasizes the so called single packet delay bound as if it is a unique feature of SRR. For example, the paper said that its worst case single packet delay is independent of the number of flow. Actually, the worst case delay is still decided by the number of flow. What's more, the bound appears to be too large comparing with the GPS model or WFQ.

Burstiness of Stratified RR is not as good as other similar algorithms either. In same class, the largest flow weight can be as large as two times of the smallest flow weight. This means in one schedule slot this flow can send 2 times of size of the longest packet.

The paper is well written, easy to understand and practical for implementation. Considering its impact and originality to the research area, I vote it to be ranked in the lower high class among the papers reviewed so far.

Haoyu Song