Performance analysis of finite-buffered multistage interconnection networks with various switching architectures
Tzung-I Lin, Leonard Kleinrock · 1990
We present analytical models for evaluating the performance of finite-buffered packet switching multistage interconnection networks using blocking switches and turn back switches under any general traffic pattern. Most of the previous research work has assumed the case of no buffers, single buffer or infinite buffers, and all of them assumed that processing elements have the same traffic pattern, either a uniform traffic pattern or a specific hot spot pattern. However, those models cannot be applied very generally. There is a need for an analytical model to evaluate the system performance under general conditions. Our approach is to create a model with approximates these networks, derive the system equations for this model, and then solve these equations iteratively. We first propose a decomposition and iteration model for a specific hot spot pattern. This model is then generalized to handle general traffic patterns using a transformation method. A superposition method and a weighting factor are then proposed to be used with the iteration model and the transformation method to analyze the interconnection networks with a general traffic condition where each processing element has its own traffic pattern and input rate. In order to account for the memory characteristic of a blocking which causes persistent blocking of packets contending for the same output ports, we propose an approximate method. Moreover, an analytical model is proposed to analyze a re-submission interconnection network where each processing element has a finite buffer space to accept the rejected packets from the network. A rate adjusted model is then proposed to reduce the time delay while maintaining the throughput at the same level. Finally, we develop an analytical model for interconnection networks using the turn back switches. The delay performance of packets passing through a particular path is analyzed using recurrence equations. The performance of the turn back switches and blocking switches are compared. This leads us to propose the rotating switch which combines the advantages of the turn back and the blocking switch; we then evaluate its performance relative to the blocking and the turn back switch.