Dynamic token bucket (DTB): a fair bandwidth allocation algorithm for high‐speed networks

Article type: Research Article

Authors: Kidambi, Jayakrishna | Ghosal, Dipak | Mukherjee, Biswanath

Affiliations: Department of Computer Science, University of California, Davis, CA 95616, USA E‐mail: jkidambi@cup.hp.com,{ghosal,mukherje}@cs.ucdavis.edu

Note: [] Correspondence author. Tel.: +1 530 752 5129; Fax: +1 530 752 4767.

Abstract: Fair allocation of available bandwidth to competing flows is a simple form of quality of service (QoS) that can be provided to customers in public networks. A number of packet‐scheduling and buffer‐management techniques have been proposed in the literature to achieve this goal efficiently. However, the complexity of the existing algorithms prevents a high‐speed implementation with the current state of router technology. We propose a computationally simpler mechanism based on token‐bucket policing to achieve almost equal bandwidth allocation for a set of competing flows. The proposed method adjusts the token‐bucket threshold dynamically and measures the instantaneous arrival rate of flows. It uses this information to decide whether or not to admit a packet arriving at the network edge. With minor modifications, our framework can be used in a variety of practical network environments ranging from the Internet to virtual private networks (VPNs) over Frame Relay. We present a detailed simulation study that evaluates the performance of our algorithm. The simulation results indicate that DTB is fair, efficient, and robust.

Journal: Journal of High Speed Networks, vol. 9, no. 2, pp. 67-87, 2000