A three-stage ATM switch with cell-level path allocation

A method is described for performing routing in three-stage asynchronous transfer mode (ATM) switches which feature multiple channels between the switch modules in adjacent stages. The method is suited to hardware implementation using parallelism to achieve a very short execution time. This allows cell-level routing to be performed, whereby routes are updated in each time slot. The algorithm allows a contention-free routing to be performed, so that buffering is not required in the intermediate stage. An algorithm with this property, which preserves the cell sequence, is referred to as a path allocation algorithm. A detailed description of the necessary hardware is presented. This hardware uses a novel circuit to count the number of cells requesting each output module, it allocates a path through the intermediate stage of the switch to each cell, and it generates a routing tag for each cell, indicating the path assigned to it. The method of routing tag assignment described employs a nonblocking copy network. The use of highly parallel hardware reduces the clock rate required of the circuitry, for a given-switch size. The performance of ATM switches using this path allocation algorithm has been evaluated by simulation, and is described