PERFORMANCE IMPROVEMENT IN SINGLE-STAGE AND MULTIPLE-STAGE SHUFFLE-EXCHANGE NETWORKS

An N x N delta network, constructed from B x B crossbar switches, consists of (log(,2)N)/(log(,2)B) stages with N/B switches in each stage (N and B are integer powers of 2). The outputs of the switches in each stage, except the last, are connected to the inputs of the switches in the next stage by the Perfect Shuffle connection or one of its variants. When two or more packets arriving at different inputs of the switch must be forwarded to the same output, only one of these packets is forwarded and the rest are blocked. In buffered delta networks each switch has finite capacity buffers to store the blocked packets. Switches of unbuffered delta networks have no buffers and blocked packets are lost. In a single-stage shuffle-exchange network, a single stage of switches performs the function of all the stages of a delta network by using feedback paths provided from the outputs of this stage back to its inputs. The throughput of unbuffered delta networks is known to be the solution of a quadratic recurrence relation. Fairly tight lower and upper bounds on the solution of this recurrence relation are derived in this thesis. These bounds have a simple functional form. Throughput of unbuffered delta networks can be improved either by replacing each link of the simple delta networks by parallel links, or by combining multiple delta subnetworks in parallel. The improvements in performance obtained by these modifications are compared. The throughput of networks with four parallel links is almost equal to the throughput of crossbars. These modifications can also be applied to buffered delta networks to increase their throughput. It is shown that the throughput of buffered delta networks can also be increased substantially by modifying the structure and operation of their crossbar switches. The use of parallel links for each switch connection results in the highest throughput improvement. Three new switch structures are proposed for single-stage shuffle-exchange networks. These switches use extra buffers to enhance performance and avoid the possibility of deadlocks