Deficit round robin scheduling with adaptive weight control
Mikkel Hagen- February 19, 2013Recently, I presented a paper, "Deficit round robin scheduling with adaptive weight control," co-authored with Ryan Zarick and Radim Bartos, at the 25th International Conference on Computer Applications in Industry and Engineering (ISCA-CAINE 2012). I highly recommend the ISCA-CAINE conference, as it includes quality papers from a broad spectrum of areas including: mobile applications, wireless sensor networks, finance industry, and many others. Out of the 40 papers that were accepted to the conference, our paper received the great honor of being voted the best paper. This included both a review of the quality of the writing as well as a critique of the presentation that I gave at the conference.
Deficit round robin (DRR) scheduling is increasingly popular in modern switches in order to determine when to schedule packets when multiple input ports are trying to transmit out a single output port. Weighted fair queuing (WFQ) is the gold standard of fairness in scheduling; however, it is rather complex for switches to implement. DRR, on the other hand, is a close approximation of WFQ, but it is significantly cheaper to implement.
For the purposes of this paper, we defined fairness to be where two streams are able to achieve the same overall throughput on a network. Using off-the-shelf switches, we showed that a switch using DRR has an issue with fairness while scheduling a stream of small frames and a stream of large frames. By performing a series of experiments, we quantified the fairness issue and developed a new scheduling algorithm (DRR-AWC).
DRR-AWC actively monitors the average size of the frames in input queues and adjusts the weights of the queues in order to favor the queues with smaller frames in them. This ultimately overcomes the previously identified fairness issue and allows streams of small frames to have the same throughput of larger frames. Using a well-known fairness index (Jain's Fairness Index) we plotted the fairness of the system before and after implementing our proposed algorithm in the below figure. This showed a significant increase in fairness using DRR-AWC, that also resulted in an over 30% increase in throughput for streams of the smallest frames.
Figure 1: A plot of the fairness of the system before and after implementing our algorithm.
About the Author
Mike has worked throughout the UNH-IOL in various consortia testing Fibre Channel, SAS, SATA, iSCSI, Data Center Bridging, iWARP, Infiniband and Wireless technologies. He has completed several large test tool development projects including automated test tools that both generate traffic and record results written in Visual Studio C++ for Fibre Channel, Java for iWARP and Java for Wireless testing. He has written several test suites including conformance and interoperability test suites along with tutorials for Fibre Channel, Data Center Bridging and iWARP Consortia.