Performance Analysis of Packet Switching Interconnection Networks with Finite Buffers Aristotel Tentov and Aksenti Grnarov Computer Science Department, Faculty of Electrical Engineering University "St. Kiril i Metodij" Karpos bob., 91000, Skopje, Macedonia E-mail: tot o@cerera . et f . ukim e edu mk Abstract In this paper, a mathematical method for analysis of syn- chronous packet-switching interconnection networks with jinite buffering capacity at the output of switching elements is presented. The proposed mathematical method is general in that it analyzed interconnection networks under uniform and nonuniform traflc with blocking. The existing meth- ods for analysis of buffered interconnection networks have assumed either single or infinite buffers at each input (or output) port of a switch, as well as uniform traflc pattem of the networks. Firstly, in the papel; a general model of synchronous buffered switching element, using outpue buffering, under assumption of finite buffer size for a very general class of trafic, is presented. Traflc can be uniform or nonuniform. It is assumed that the subsequent stages of the network are nearly independent and a model is ex- tended for entire network under this assumption. Analytical results obtained with proposed model are then compared with each othel; and it is shown that the proposed mathe- matical method is more general then the known models of interconnection networks. Index Terms - multistage interconnection networks, per- formance analysis, finite buffer size, nonuniform traffic dis- tribution, blocking probability. 1. Introduction There is a great demand for application-specific multi- stage interconnection networks (MIN) in areas such as mul- tiprocessor systems, high-speed communications based on the asynchronous transfer mode (ATM) and parallel com- puter systems. MIN are used for interconnection of a large number of processors and memory modules in multiprocessor systems and for the resource arbitration and token distribution in the 1089-6503/96 $5.00 0 1996 IEEE Proceedings of EUROMICRO-22 data flow computers [5], as main building blocks of switch fabrics in ATM switches [ 111, and for the high speed packet- switching computer communications in parallel computers [l]. In all these applications, MIN are a critical part of the overall system performance. Consequently, extensive studies have been done on characterizing their performance behavior. Dias and Jump [7] analyzed the performance of delta networks with single buffers based on the timed Petri-net model. Robertazzi [ 131 present analysis of the performance of a packet switch based on single-buffered banyan net- works, which was presented in the earlier work done by Jenq [14]. Kruskal and Snir [3], [4] studied the performance of banyan networks with infinite buffers. The performance of MIN's (multiple but finite buffers at each input port of a switch) has only partially been known through simulation [5], [7]. Common characteristic of all of this performance analysis was that they have considered only banyan (delta) networks based on (2x2) crossbar switches. These networks are unique path networks, which provide a unique path for each input-output connection. The performance of single and multiple buffered delta networks constructed from switching elements (SE's) of ar- bitrary sizes and types (crossbar or bus), as well as the performances of single and multiple buffered, multiple-path networks (plus-minus-2' networks) have been analytically studied by H. Yoon et al. [8]. Theimer et al. [lo] ex- panded lenq's model by introducing a blocked state for the single-buffered banyan network composed of 2c2 switch- ing elements (SE). Hsiao and Chen [12] also considered the blocked state for the single-buffered banyan networks. Ding and Bhuyan [6] showed that the performance of MIN can be improved by adopting the concept of small clock cycle using a model similar to Yoon's [8]. This models are based on some unrealistic assumptions or too complex to be generalized for multibuffered MIN's or large size SE. Mun and Youn [ 151 modeled multibuffered MIN's with 3902x2 SE, with finite buffers on each input port. Their model considered the correlation of packet movements between two adjacent stages as well as subsequent network cycles, and it takes the blocked state into account. This model however is not generalized for nonuniform network traffic and for switches with different sizes. Labarta, Doming0 and Casals [9] analyzed omega networks based on 2x2 SE, with finite buffers on each output port, under assumption of uniform traffic. In our previous paper [2], we presented an analytic model, which can be used to analyze MIN’s constructed from SE’s of an arbitrary size and type (crossbar or bus), with finite size buffers on each output port, under a very general class of uniform and nonuniform traffic. One of the shortcomings of this model is that it didn’t take the effect of blocking into account. In this paper, a general analytic model for the perfor- mance evaluation of MIN’s is presented. It effectivelly mod- els MIN’s from SE’s of various sizes and types, with finite buffers on output ports, under assumption of uniform and nonuniform traffic thaking into account effect of blocking. Characteristics of the model, as well as necessary assump- tion which were made in the process of its development give the assurance that the model is general and that it covers a great deal of different types of MIN’s. The rest of the paper is organized as follows. Delta networks and their main characteristics are briefly described in Section 2. The new analytic method for performance analysis of MIN’s with finite output buffers is introduced in Section 3. In section 4, the proposed analytic model is used to analyze the performance of synchronous MIN’s in the case of uniform and nonuniform traffic pattern. Conclusions are given in Section 5. 2. Delta Networks Interconnection networks connect source and destination elements through stages of switches. An (N x N) delta network consists of n stages of N/s (s x s) crossbar switches, where N=sn. A packet movement through the network can be controlled locally at each SE by a single base-s digit of the destination address. An example of an (8 x 8) delta network is given in Fig. 1. Basic building block of an interconnection network is s-input, s-output (sxs) buffered switch (Fig. 2).