Randomized routing of virtual connections in essentially nonblocking log N-depth networks

An optimal N/spl times/N circuit switching network with /spl theta/(N/spl times/N) bandwidth has a lower bound of /spl theta/(N/spl middot/log N) hardware, which includes all crosspoints, bits of memory and logic gates, and a lower bound of /spl theta/(logN) set-up time. To date no known self-routing circuit switching networks with explicit constructions achieve these lower bounds. The authors consider a randomized routing algorithm on a class of circuit switching networks called "extended dilated banyans". It is proven that the blocking probability of an individual connection request is O[log/sub b/ N/spl middot/(k/d)/sup d/], where d is the dilation factor and k is a constant. With a dilation of /spl theta/(log log N) and a loading >