Sorting networks with applications to hierarchical optical interconnects

The Banyan network is shown to have a computationally unsuitable structure for finding maximum passable subpermutations, which is proved NP-complete. Using some non-blocking properties on the cube and reverse Banyan networks, a network topologically equivalent to the Batcher sorter, but functionally equivalent to the Batcher-Banyan network is derived for routing incomplete permutations. A log₂ N(2w-1) stage radix sorter for w-bit inputs, including duplicate inputs, that uses only log₂ N+1 bit address headers for routing through each 2 log₂ N stages is shown, which can be used in sort-MIN type packet switches. Space-time sorting networks based on these principles are derived, which can be used in hierarchical wavelength multiplexed optical networks