Fast knockout algorithm for self-route concentration
Concentration has been a popular technique for resolving contention in switching. In particular, self-route concentration is useful inside ATM switching fabrics in many ways. This paper presents an efficient algorithm for the construction of self-route concentrators from multi-stage cascades of 2 x 2 sorters, where the main criterion on the complexity is the number of stages in the cascade. The algorithm extensively generalizes the existing Fast Knockout algorithm and mixes in some k-sorting technique. The result includes a best known construction of m-to-n self-route concentrator for all m and n within the practical range. (C) 1999 Elsevier Science B.V. All rights reserved.
fast knockout algorithm self-route concentration atm switching fabric k-sorting algorithm