Randomized Parallel Communications on an Extension of the Omega Network

Parallel communication algorithms and networks are central to large scale parallel computing and, also data communications. The paper identifies adverse source-destination traffic patterns, and proposes a scheme for obtaining relief by means of randomized routing of packets on simple extensions of the well-known Omega networks.