On evil twin networks and the value of limited randomized routing

A dynamic 2-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×⁴√(N) network cycles. Two limited randomized routing schemes are then given and yield on average at most N_A+1+1/N (N_A=O(log N/log(log N=1))) and is the greatest integer such that (N_A)!⩽N and [log(log N+1)]+2+1/N network cycles for any input permutation. The probability of any permutation requiring at least c network cycles more than the average bounds above is at most 1/(c+1)! and 1/N^2exp(c)