Scalable architectures for integrated traffic shaping and link scheduling in high-speed ATM switches

Emerging broad-band switches must accommodate the diverse traffic parameters and quality-of-service requirements of voice, data, and video applications. End-to-end performance guarantees depend on connections complying with traffic contracts as their cells travel through the network. This paper presents a leaky-bucket shaper architecture that scales to a large number of connections with diverse burstiness and bandwidth parameters. In contrast to existing designs, the proposed architecture arbitrates fairly between connections with conforming cells by carefully integrating leaky-bucket traffic shaping with ratebased scheduling algorithms. Through a careful combination of per-connection queueing and approximate sorting, the shaper performs a small, bounded number of operations in response to each arrival and departure, independent of the number of connections and cells. When the shaper must handle a wide range of rate parameters, a hierarchical arbitration scheme can reduce the implementation overheads and further limit interference between competing connections. Through simulation experiments, we demonstrate that the architecture limits cell-shaping delay and traffic distortions, even in periods of heavy congestion. The efficient combination of traffic shaping and link scheduling results in an effective architecture for managing buffer and bandwidth resources in large, high-speed ATM switches.