Efficiency Improvement of the Fast Knockout Algorithm in Concentrator for ATM Switching
Li Hui · 1999
The Fast Knockout (FKO) algorithm constructs self-route concentrators from multi-stage cascades of 2×2 sorters. It is an especially efficient technique for m to n concentration when m and n are within the practical range. The algorithm calls a sub-algorithm for“pairing”.Different choices of the sub-algorithm result in different complexities of the FKO algorithm.A new pairing sub-algorithm that yields the best known efficiency within a wide range of m and n that covers all practical purposes. Within the given range,the efficiency improvement shows in about 20% of all cases.