UPM Institutional Repository

Crosstalk-Free Scheduling Algorithms for Routing in Optical Multistage Interconnection Networks


Raja Mohd Auzar, Tengku Dian Shahida (2009) Crosstalk-Free Scheduling Algorithms for Routing in Optical Multistage Interconnection Networks. Masters thesis, Universiti Putra Malaysia.


Multistage Interconnection Networks (MINs) have been used in telecommunication networks for many years. Significant advancement in the optical technology have drawn the idea of optical implementation of MINs as an important optical switching topology to meet the ever increasing demands of high performance computing communication applications for high channel bandwidth and low communication latency. However, dealing with electro-optic switches instead of electronic switches held its own challenges introduced by optics itself. Limited by the properties of optical signals, optical MINs (OMINs) introduce optical crosstalk, as a result of coupling two signals within each switching element. Therefore, it is not possible to route more than one message simultaneously, without optical crosstalk, over a switching element in an OMIN. Reducing the effect of optical crosstalk has been a challenging issue considering trade-offs between performance and hardware and software complexity. To solve optical crosstalk, many scheduling algorithms have been proposed for routing in OMIN based on a solution called the time domain approach, which divides the N optical inputs into several groups such that crosstalk-free connections can be established. It is the objective of the research presented in this thesis to propose a solution that can further optimize and improve the performance of message scheduling for routing in the optical Omega network. Based on Zero algorithms, a Modified Zero algorithm is developed to achieve a crosstalk-free version of the algorithm. Then, the Fast Zero (FastZ) algorithm is proposed, which uses a new concept called the symmetric Conflict Matrix (sCM) as a pre-scheduling technique. Extended from the FastZ algorithms, another three new algorithms called the FastRLP, BRLP and FastBRLP algorithms are developed to achieve different performance goals. Lastly, a comparison is made through simulation between all algorithms developed in this research with previous Zero-based algorithms as well as traditional Heuristic algorithms since equal routing results can be obtained between all algorithms. Through simulation technique, all three FastZ, BRLP and FastBRLP algorithms have shown the best results when the average execution time is considered. The FastRLP and FastBRLP algorithms on the other hand have shown the best results when the average number of passes is considered. It is proven in this thesis that the new approach has by far achieved the best performance among all the algorithms being tested in this research

Download File


Download (682kB)

Additional Metadata

Item Type: Thesis (Masters)
Subject: Routing protocols (Computer network protocols).
Call Number: FSKTM 2009 2
Chairman Supervisor: Associate Professor Mohamed Bin Othman, PhD
Divisions: Faculty of Computer Science and Information Technology
Depositing User: Nur Izyan Mohd Zaki
Date Deposited: 10 Jun 2010 02:02
Last Modified: 27 May 2013 07:33
URI: http://psasir.upm.edu.my/id/eprint/7137
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item