A quasi-nonblocking self-routing network which routes packets in log2N time

A self-routing multi-log-N permutation network is presented and studied. This network has log₂N depth and N(log₂²N+log₂N )/2 nodes, where N is the number of network inputs. Its parallel routing algorithm runs in log₂N time. The network architecture guarantees that only a negligible quantity of information is blocked, while the quasi-totality of the information synchronously reaches the network outputs in log₂N steps. This network works in pipeline, it has a modular architecture suitable for very large N, it can be used as very high performance fast packet switching fabric, and it is suitable for information exchange in very-large-scale multiprocessor systems