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

摘要

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.