Disa: A robust scheduling algorithm for scalable crosspointbased switch fabrics

Abstract—This paper presents and analyzes a high-perfor-mance, robust, and scalable scheduling algorithm for input-queued switches called distributed sequential allocation (DISA). In contrast to pointer-based arbitration schemes, the proposed algorithm is based on a synchronized output reservation process, whereby each input selects a designated output while taking into consideration both local transmission requests and the availability of global resources. The distinctiveness of the algorithm lies in its ability to offer high performance when multiple cells are transmitted within each switching interval. Relaxed switching-time requirements allow for the incorporation of commercially available crosspoint switches. The result is a pragmatic and scalable solution for high port-density switching platforms. The efficiency of the scheme and its robustness in the presence of admissible traffic, without the need for speedup, is established through analysis and computer simulations. Performance results are shown for various traffic sce-narios including nonuniform destination distribution, correlated arrivals and multiple classes of service. Index Terms—Input-queued switches, packet scheduling algo-rithms, quality-of-service (QoS), switch fabric, traffic modeling. I