Queue-Length Proportional and Max-Min Fair Bandwidth Allocation for Best Effort Flows
Tosmate Cheocherngngarn, Jean H. Andrian, Zhenyu Yang, Deng Pan · 2011
A group of switch schedulers make packet scheduling decisions based on predefined bandwidth allocation for each flow. Allocating bandwidth for best effort flows is challenging due to lack of allocation criteria and fairness principles. In this paper, we propose sequential and parallel algorithms to allocate bandwidth for best effort flows in a switch, to achieve fairness and efficiency. The proposed algorithms use the queue length proportional allocation criterion, which allocates bandwidth to a best effort flow proportional to its queue length, giving more bandwidth to congested flows. In addition, the algorithms adopt the max-min fairness principle, which maximizes bandwidth utilization and maintains fairness among flows. We first formulate the problem based on the allocation criterion and fairness principle. Then, we present a sequential algorithm and prove that it achieves max-min fairness. To accelerate the allocation process, we propose a parallel version of the algorithm, which allows different input ports and output ports to conduct calculation in parallel, resulting in fast convergence. Finally, we present simulation data to demonstrate that the parallel algorithm is effective in reducing the convergence iterations.