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: © 2012 |Pages: 11
DOI: 10.4018/978-1-4666-0056-0.ch015

Abstract

This paper proposes an adaptive unicast routing algorithm for large scale symmetric networks comprising 2 × 2 switch elements such as Beneš networks. This algorithm trades off the probability of blocking against algorithm execution time. Deterministic algorithms exploit the rearrangeability property of Beneš 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.
Chapter Preview
Top

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) 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š 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

978-1-4666-0056-0.ch015.f01

Complete Chapter List

Search this Book:
Reset