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.

[img] PDF
666Kb

Abstract

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

Item Type:Thesis (Masters)
Subject:Routing protocols (Computer network protocols).
Chairman Supervisor:Associate Professor Mohamed Bin Othman, PhD
Call Number:FSKTM 2009 2
Faculty or Institute:Faculty of Computer Science and Information Technology
ID Code:7137
Deposited By: Nur Izyan Mohd Zaki
Deposited On:10 Jun 2010 02:02
Last Modified:27 May 2013 07:33

Repository Staff Only: item control page

Document Download Statistics

This item has been downloaded for since 10 Jun 2010 02:02.

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


Universiti Putra Malaysia Institutional Repository

Universiti Putra Malaysia Institutional Repository is an on-line digital archive that serves as a central collection and storage of scientific information and research at the Universiti Putra Malaysia.

Currently, the collections deposited in the IR consists of Master and PhD theses, Master and PhD Project Report, Journal Articles, Journal Bulletins, Conference Papers, UPM News, Newspaper Cuttings, Patents and Inaugural Lectures.

As the policy of the university does not permit users to view thesis in full text, access is only given to the first 24 pages only.