Wormhole switched input-buffered and middle-buffered routers with virtual channels are analyzed in this paper. Middle buffering refers to the placement of virtual channels between the demultiplexers and multiplexers of a crossbar switch. An analytical model for multistage interconnection networks using middle-buffered switches is developed. In addition, extensive simulation is conducted to assess the performance of the two buffering techniques in different network topologies. The study demonstrates that middle buffering with virtual channels provides better performance than input buffering with virtual channels in multistage interconnection networks, two-dimensional meshes, and hypercubes.

An analytical model for virtual channel flow control in n-dimensional hypercubes using the e-cube routing algorithm is developed. The model is based on determining the values of the different components that make up the average message latency. These components include the message transfer time, the blocking delay at each dimension, the multiplexing delay at each dimension, and the waiting delay at the source node. The first two components are determined using a probabilistic analysis. The average degree of multiplexing is determined using a Markov model, and the waiting delay at the source node is determined using an M/M/m queueing system. The model is fairly accurate in predicting the average message latency for different message sizes and a varying number of virtual channels per physical channel. It is demonstrated that wormhole switching along with virtual channel flow control make the average message latency insensitive to the network size when the network is relatively lightly loaded (message arrival rate is equal to 40% of channel capacity), and that the average message latency increases linearly with the average message size. The simplicity and accuracy of the analytical model make it an attractive and effective tool for predicting the behavior of n-dimensional hypercubes.>

An efficient fully adaptive wormhole routing algorithm for n-dimensional meshes is developed. The routing algorithm provides full adaptivity at a cost of one additional virtual channel per physical channel irrespective of the number of dimensions of the network. The algorithm is based on dividing the network graph into two acyclic graphs that contain all of the physical channels in the system. Virtual channels are classified as either waiting or nonwaiting channels. Busy channels that a message waits for to become available are classified as waiting channels, otherwise they are classified as nonwaiting channels. Thus, a message considers nonwaiting channels first to reach its destination. If all non-waiting channels are busy, the message considers waiting channels. Messages acquire waiting channels in two phases. In each phase, waiting channels belonging to one acyclic network graph are traversed. This 2-phase routing algorithm could be either minimal or nonminimal. However, we concentrate on minimal routing. It is demonstrated that this adaptive routing algorithm can utilize the virtual paths (channels) between any two nodes more efficiently than any of the present algorithms with the same hardware requirement.>

A simple model, called the direction restriction model, for developing partially adaptive routing algorithms for n_dimensional meshes is introduced in this paper. This model is based on dividing a system into two unidirectional networks that contain all physical channels of the system.