On Nonblocking Properties on the Benes Network
Petr Kolman · 1998
A network is called nonblocking if every unused input can be connected by a path through unused edges to any unused output, regardless of which inputs and outputs have been already connected. The Benes network of dimension n is shown to be strictly nonblocking if only a suitable chosen fraction of 1=n of inputs and outputs is used. This has several consequences. First, there is a very simple strict sense nonblocking network with N = 2 n inputs and outputs, namely a (n + log n + 1){ dimensional Benes network. Its depth is O(log N ), it has O(N log 2 N) edges and it is not constructed of expanders. Secondly it leads to a (3 log N){competitive randomized algorithm for a (log N){dimensional Benes network and a O(log 2 N){competitive randomized algorithm for a (log N){dimensional hypercube, for routing permanent calls.