Adaptive Routing Strategy for Large Scale Rearrangeable Symmetric Networks

Adaptive Routing Strategy for Large Scale Rearrangeable Symmetric Networks

Amitabha Chakrabarty (Dublin City University, Ireland), Martin Collier (Dublin City University, Ireland) and Sourav Mukhopadhyay (Dublin City University, Ireland)
Copyright: © 2010 |Pages: 11
DOI: 10.4018/jghpc.2010040105

Abstract

This paper proposes an adaptive unicast routing algorithm for large scale symmetric networks comprising 2 × 2 switch elements such as Bene?s networks. This algorithm trades off the probability of blocking against algorithm execution time. Deterministic algorithms exploit the rearrangeability property of Bene?s networks to ensure a zero blocking probability for unicast connections, at the expense of extensive computation. The authors’ algorithm makes its routing decisions depending on the status of each switching element at every stage of the network, hence the name adaptive routing. This method provides a low complexity solution, but with much better blocking performance than random routing algorithms. This paper presents simulation results for various input loads, demonstrating the tradeoffs involved.
Article Preview

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+baseline1 or omega+omega1 . 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+baseline1. The Beneˇs network is one MIN that has N = 2n inputs and outputs and comprises (2logN − 1) stages1 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ˇs network is a rearrangeable network (Hwang, Lin & Lioubimov, 2006; Yeh & Feng, 1968) from the family of Clos (Clos, 1953) type network. Fig 1 shows a 16 × 16 Beneš Network.

Figure 1.

16 × 16 Beneš network

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing