On evil twin networks and the value of limited randomized routing

• Published in: IEEE transactions on parallel and distributed systems 2000-09, Vol.11 (9), p.910-925
• Main Authors: Alleyne, B.D., Scherson, I.D.
• Format: Article
• Language: English
• Subjects: Routing
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/71.879774

A dynamic two-stage Delta network (N inputs and outputs) is introduced and analyzed for permutation routing. The notion of evil twins is introduced and a deterministic procedure is given to route any permutation in no more than 2/sup 4//spl radic/N network cycles. Two limited randomized routing schemes are then analyzed. The first called Single Randomization yields on average at most N!+1 (N!=O(logN/loglogN)/sup 1/ and is the greatest integer such that (N!)!/spl les/N) network cycles and the second called Multiple Randomization yields on average at most upper bound [log(logN+1)]+2+1/N network cycles for any input permutation. The probability of any permutation requiring at least c network cycles more than the above average bounds is then shown to be at most 1/(c+1) for Single Randomization and 1/N/sup r/ for Multiple Randomization, respectively. It is then shown how the dynamic two-stage network can be physically realized as a three-stage network. Both the evil twin and Multiple Randomization algorithms have been integrated into an off-the-shelf ASIC from PMC-Sierra, Inc. (PM-73488) which has been designed as a building block for such a three-stage implementation. These routing schemes are also adapted to run on a recirculating network. Recirculation is used to effect a reshuffling of data as in the dynamic network, but with a considerable reduction in network cost.