A challenge for routing algorithms in optical multistage interconnection networks.(Report)

INTRODUCTION

The limitation of most digital systems' performance is by their communication or interconnection (Katangur et al., 2004). The interconnection network implements a main role in defining the overall performance of a multicomputer system. If the network cannot provide sufficient performance for particular application, messages will frequently be required to wait for data to arrive. Some of these applications are telephone switches, interconnection networks for multicomputer and distributed shared memory multiprocessors, clusters of workstations and personal computers, local area networks, wide area networks and networks in industrial applications (Denko et al., 2009).

Nowadays, Multistage Interconnection Networks (MINs) have importance because of their cost-effectiveness and is very popular in switching and communication applications. MINs are used in multiprocessing systems to provide cost-effective, high-bandwidth communication between processors and/or memory modules and in used in telecommunication and parallel computing systems for many years. A MIN normally connects N inputs (sources) to N outputs (destinations) and is referred to as an N x N MIN. The parameter N is called the size of the network. It has n stages (n = [log.sub.2]N). Each stage has N/2 Switching Elements (SEs); each SE has two inputs and two outputs connected in a certain pattern. MINs can be electronic MINs or optical MINs that in electronic MINs electricity are used, where as in optical MINs light is used to transmit the messages (Aggarwal and Kaur, 2008).

Optical MINs (OMINs) are an attractive solution in the design of high-speed communication networks and switches because of having high bandwidth, low error probability and large transmission capacity. The electronic MINs and the optical MINs have many similarities, but crosstalk problem in the optical switches is one major difference between them (Sharma et al., 2008). Recently, a new architecture is introduced that applies especially to multicasting in multistage interconnection networks. In addition to multicast traffic, Tutsch and Brenner (2003) provide additional views on MINs performance aspects under special cases using simulations. Those MINs are called Multilayer Multistage Interconnection Networks (MLMINs) that their needs are for routing capacity in the presence of multicast and broadcast traffic, their performance prediction and evaluation but in this study we focus on optical multistage interconnection networks (Vasiliadis et al., 2009; 2010).

The study is organized as follows. Second section will give an overview about the major problem in Optical Multistage Interconnection Networks. Third section explains about the window method and general description of the methodology. In fourth section we have reviewed five algorithms that are usual to use in this case. Fifth section is related to compare algorithms and final section gives the conclusion.

Problem overview: Crosstalk in OMINs is an important problem. To avoid crosstalk problem which is caused by coupling two signals within a switching element (Almazyad, 2011), various approaches have been proposed by many researchers. In this research, we are interested in a network called optical omega network which has shuffle-exchange connection pattern. to send messages from a source to a destination on Optical Omega Network without crosstalk, we need to divide the messages into several groups. We want to separate the messages without conflicts with other messages in the same group as well as we want to reduce the total number of the groups. Under the constraint of avoiding crosstalk, three approaches, space domain, time domain and wavelength domain have been proposed.

In this research, crosstalk-free …