PERFORMANCE ANALYSIS OF CIRCUIT SWITCHING BASELINE INTERCONNECTION NETWORKS Manjal Lee and Chuan-lin Wu Department of Electrical Engineering University of Texas at Austin Austin, TX 78712 Abstract Performance evaluation, using both analytlcal and simulation models, of circuit switching baseline networks is presented. Two configurations of the baseline networks, single and dual, are evaluated. In each configuration, two different conflict resolution strategies, drop and hold, are tried to see the performance difference. Our analytical models are based on a more realistic assumption. New analyses are given and are verified by simulation results. In single network configuration, it is shown that the drop strategy is better than the hold strategy in the case that the data transfer time is longer than I0 cycles under a high request rate. In the dual network configuration, five different communication strategies are investigated and the optimum performance level is shown to be dependent on the length of the data transfer time. I. Introduction Multistage interconnectlon networks have been proposed by many research groups for interconnecting multlple processors [1]. Performance evaluation work on the networks has also been done quite extensively [2-5]. However, previous evaluation models are commonly based on the unrealistic assumption that a blocked request is discarded and an independent request is generated to replace the previously blocked and yet unserved request. This assumption helps researchers simplify the theoretical model, but the slmpllficatlon will result in discrepancies in predicting network performance. In addition, there is no quantitative measure existing on how to choose a way to handle the blocked request between the two alternatives: hold and drop. In the hold strategy, the blocked request holds the partial path already established and waits for a release of the blockage. In the drop strategy, the blocked request abandons the partial path already established and starts over again. A quantitative measure on each strategy will provide insight information on the switching element design. Furthermore, most previous works consider only a single interconnectlon network. However, more than one network can be used in a system to enhance the performance. It is desirable to know how multiple networks can enhance the performance. In this paper trying to solve the above problems, we formulate new models of c~rcult switching baseline Interconnectlon networks [6,7]. The rest of the paper is organized as follows. Section II describes the network organizations which we will analyze. Assumptions for analytical model are presented in section III. For comparison, the regeneration model is described in section III, which uses the assumption that a blocked request is discarded and an independent request is generated. Sections IV and V present new analytical models on the hold and drop strategies respectively. Simulation and numerical results are provided in Section Vl for comparison, followed by the conclusion. II. Network Operations The baseline network [6] is used here for study. The results obtained apply to other similar networks since topological equivalence has been proven [6] A baseline network that has 8 input ports and 8 output ports is shown in Fig.l. stage Z stage 3 e e s e c e i v e s Fig. 1. 8×8 baseline network. A processor that is connected to an input port and can generate and send requests to other processors is called a sender while a processor that is connected to an output port and receives requests is called a receiver. A circuit connection between a sender and a receiver is called a path. A 2x2 switching element is shown in Fig.2. A request from either one of the inputs can be connected to either one of the outputs if the output is not occupied by some other request. If the switching element connects an input to an 0194-7111/84/0000/0082501.00© 1984 IEEE 82output as requested, we say that the request is passed. A path between an input and output in a switching element is called a switching connection. When a request has arrived at the input of a switching element in stage i and if it has not passed the switching element, we say that the request is in stage i. In general, there are three possible states for a request at a switching element as shown in Fig.2. No other request Other request already Nothe requests arrived arrived in the established a switching at the same cycle other input node connection Prob{pass}=l Prob{pass)=l/2 Prob{pass}-3/4 (a) (b) (c) Fig. 2. Probability of estab]Ishlng a connection in a swltch~ng element. In state (a), there is no previous request from the inputs and the probability for a new request to pass is equal to 1. In state (b), there is a request already passed, and probability for a new request to pass is equal to I/2. State (c) has two requests arrival at the same cycle. If both requests ask for a same output, one will be passed while the other is blocked. The choice between the requests in the conflicting case depends on priority set in the switching element. The probability for a request to pass in state (c) is equal to 3/4 given that intended output for each request is equally distributed between both outputs. When a sender generates a request, it is delivered through a llnk to an input of a switching element in stage I. The request will pass stage 1 with probability of I, 0.5, or 0.75 depending on the state of the other input of the switching element. Requests that pass stage 1 will progress to stage 2 and so on the same way. When a request passes stage n ( =log2N ), where N is the number of senders or receivers a path is established between the sender and the receiver. A request can pass