Adaptive Routing Strategy for Large Scale Rearrangeable Symmetric Networks

Introduction

High performance computing today requires a high performance communication system. This is typically an optical system in today’s state of the art, although optical switches suffer from imperfections such as the crosstalk effect (Ho, 1999), which worsens with increasing port capacity. The increasing bandwidth of state of the art computers means that, over time, increasing the throughput of interconnection networks by increasing port capacity will become problematic. Hence, the use of Multistage Interconnection Networks (MINs) (Wu & Feng, 1980) with a large number of port numbers, each of comparatively low transmission capacity will be design alternatives for high throughput optical switches. MINs allow large switching networks to be constructed efficiently from smaller subnetworks. Such networks include the baseline (Wu & Feng, 1980), omega (Lawrie, 1975), data manipulator (Feng, 1974), flip (Batcher, 1976), and SW-Banyan(S = F = 2) (Goke & Lipovski, 1973) networks. A major issue with such networks is their blocking properties - they cannot establish connecting paths for all input-output requests simultaneously. A solution to the blocking problem is to concatenate one such network with its reverse, for example: baseline+baseline−1 or omega+omega−1 . This combination will give a symmetric structure among the link patterns in the network from center stage. The Beneˇs network is one such symmetric network commonly constructed with baseline+baseline−1. The Beneš network is one MIN that has N = 2n inputs and outputs and comprises (2logN − 1) stages¹ of 2 × 2 switch elements. This network is a permutation network (Benes, 1965) because it can realizeall N! possible patterns of input-output requests. Benes (1965) and Beizer (1968), showed that the Beneš network is a rearrangeable network (Hwang, Lin & Lioubimov, 2006; Yeh & Feng, 1968) from the family of Clos (Clos, 1953) type network. Figure 1 shows a 16 × 16 Beneš Network.

Figure 1.

16 × 16 Beneš network