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>

A Markov Chain based analysis for deflection routing in n-dimensional regular mesh networks is presented. Detailed analyses are given for the 2D mesh, and a generalization to higher dimensions is outlined. Analytic results are shown to agree very closely with simulations. A basic routing scheme in which all packets have equal priority and a priority scheme in which packets with fewer alternative routes are given priority are proposed and analyzed. Results show that the priority scheme gives higher maximum throughput and lower average packet delay than the basic scheme by reducing average deflections under heavy loads. With the priority scheme, the network performance is almost identical to that of the optimal diagonal routing scheme. By doubling the number of links the throughput is always more than doubled. The authors conclude that in the 2D case, bidirectional links are more cost-effective than unidirectional ones assuming the cost is the number of optical transceivers.>

The design and approximation analyses of discrete-time buffered crossbar and banyans with cut-through switching are presented. The crossbar switches can contain: (1) input FIFO (first in, first out) queuing, (2) input bypass queuing where the FIFO discipline is relaxed, (3) a novel scheme called restricted output queuing where the number of simultaneous arrivals to an output queue is upper bounded, or (4) a novel combination of input FIFO and restricted output queuing. An analysis for the delay distribution of a packet leaving the network is presented. Restricted output queuing (or combined input and restricted output queuing) can rival the performance of pure output queuing, while requiring far less hardware.>