A low-cost architecture for the implementation of worst-case-fair schedulers in ATM switches

The discrete-rate approach has been proposed in Bennett et al. (1997) as a low-complexity solution for the implementation of worst-case-fair schedulers which approximate the generalized processor sharing (GPS) policy in ATM systems. The total implementation cost with this approach is even competitive with the cost of non-worst-case-fair schedulers implemented with conventional priority queues. Two discrete-rate techniques have been proposed. The one presented in Bennett et al. achieves near-optimal delay and fairness properties, but the discrete-rate scheduler needs to maintain a timestamp for each connection, which significantly contributes to the total cost. The second technique, presented in Chiussi and Francini (1998), does not require per-connection timestamps, and thus further reduces complexity; however, although the scheduler achieves near-optimal delay bounds and is worst-case fair, its fairness in distributing excess bandwidth is compromised. In this paper, we introduce a new discrete-rate technique for reducing the implementation cost of worst-case-fair GPS-related schedulers in ATM systems while maintaining near-optimal performance; the technique uses only a single bit per connection, and achieves delay bounds and fairness indices that are identical to the ones of the discrete-rate scheduler using per-connection timestamps. The new technique works well with the generalized discrete-rate approach presented in Chiussi and Francini to increase the number of discrete rates that the scheduler can support