N-LOG N-DUAL SHUFFLE-EXCHANGE NETWORK WITH ERROR-CORRECTING ROUTING

This paper describes a dual shuffle-exchange switching network (DSN) t hat makes use of the principle of error-correcting routing. For motiva tion, parallels are drawn between error-correcting routing in switchin g and error-correcting coding in transmission. Based on a novel error- correcting and self-routing algorithm, we show by analysis and simulat ion that the DSN can achieve the Shannon's lower bound NlogN on switch complexity while satisfying four desirable criteria: 1) self-routing property; 2) no queueing of packets at the inputs or inside the switch ; 3) arbitrarily small packet-loss probability; 4) close-to-100% throu ghput. Different implementations of the basic DSN concept and their tr ade-offs are discussed.