UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A fair bandwidth distribution algorithm with a bandwidth reservation extension Sunna, Raed J.


The algorithm presented in this thesis is designed to provide all flows sharing an output link of a router with a fair share of the bandwidth, while at the same time guarantying a high total bandwidth utilization. This Fair Bandwidth Distribution algorithm (FBDA) is designed to work with already existing responsive (e.g. TCP) and nonresponsive (e.g. UDP) transport layer protocols. The basic idea in the algorithm is to use packet dropping to indicate to a specific flow that it is taking too much bandwidth and that it should slow down. All accepted packets are saved in one output buffer and are scheduled in a first-come first-service manner. Determining which packet should be dropped is done by assigning to each flow in the output queues of the router one per-connection variable. This variable is used to keep track of how much bandwidth the flow is consuming compared to its fair share since the last packet it lost. This same variable is also used with some upper thresholds to control nonresponsive and other aggressive flows.The average queue size is effectively controlled by providing an upper limit to the value of the average flow size (the average number of packets per flow in the queue) used in the different calculations. This is needed to have enough free buffer space for bursty traffic. An extension to the algorithm provides for allocating certain portions of the bandwidth to specific nonresponsive flows. This is done by using the same variable mentioned earlier as a counter to represent the number of packets that the flow can pass through the gateway in a specific period of time. If this variable reaches zero, all the packets for that flow will be dropped until the end of the current period. A very simple mechanism is designed to allow all the flows with a reserved bandwidth to share the same buffer space with all other flows, without overflowing the buffer. This will reduce the overhead and allow for optimal bandwidth utilization.

Item Media

Item Citations and Data


For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.