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

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.