Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.2, pp.163-190 (March 2001)

An Efficient Scheme of General Weighted Fair Allocation
for Enhanced Best-Effort Service in High Speed Networks

Yen-Jen Chan and Suh-Yin Lee*
Department of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.
E-mail: ctchen@csie.nctu.edu.tw
*E-mail: sylee@csie.nctu.edu.tw

This research is focused on enhanced best-effort service, which provides the minimum bandwidth guarantee and distributes the available bandwidth fairly to packet flows in a high speed network. These goals can be reached when the bandwidth allocation is general weighted (GW) fair among the flows. GW fairness ensures the minimum rate for every flow and, furthermore, allocates the excess bandwidth (the available bandwidth minus the sum of the minimum rates) to the flows in a way that is proportional to their weights. In the proposed scheme, switches coordinate to efficiently achieve GW fair allocation. In the process of achieving fairness, a switch not only takes O(log N) time for bandwidth allocation among N active flows when receiving feedback from its neighbor node, but also keeps the packet queue length below a target threshold. As a result, better performance in terms of end-to-end delay, packet loss ratio, and throughput can be achieved. A proof to show that the scheme can achieve GW fair allocation is presented. Finally, simulation results illustrate and suggest a good and justifiable system design.

Keywords: general weighted fairness, weighted max-min fairness, unconstrained flow, normalized fair share, critical flow

Full Text () Retrieve PDF document (200103_01.pdf)

Received January 14, 2000; revised May 25, 2000; accepted July 25, 2000.
Communicated by Nen-Fu Huang.