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

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 perfo...

Full description

Saved in:

Bibliographic Details
Main Author:	Raja Mohd Auzar, Tengku Dian Shahida
Format:	Thesis
Language:	English English
Published:	2009
Subjects:	Routing protocols (Computer network protocols).
Online Access:	http://psasir.upm.edu.my/id/eprint/7137/1/FSKTM_2009_2a.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-upm-ir.7137
record_format	uketd_dc
spelling	my-upm-ir.71372013-05-27T07:33:38Z Crosstalk-Free Scheduling Algorithms for Routing in Optical Multistage Interconnection Networks 2009-04 Raja Mohd Auzar, Tengku Dian Shahida 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 Routing protocols (Computer network protocols). 2009-04 Thesis http://psasir.upm.edu.my/id/eprint/7137/ http://psasir.upm.edu.my/id/eprint/7137/1/FSKTM_2009_2a.pdf application/pdf en public masters Universiti Putra Malaysia Routing protocols (Computer network protocols). Computer Science and Information Technology English
institution	Universiti Putra Malaysia
collection	PSAS Institutional Repository
language	English English
topic	Routing protocols (Computer network protocols).
spellingShingle	Routing protocols (Computer network protocols). Raja Mohd Auzar, Tengku Dian Shahida Crosstalk-Free Scheduling Algorithms for Routing in Optical Multistage Interconnection Networks
description	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
format	Thesis
qualification_level	Master's degree
author	Raja Mohd Auzar, Tengku Dian Shahida
author_facet	Raja Mohd Auzar, Tengku Dian Shahida
author_sort	Raja Mohd Auzar, Tengku Dian Shahida
title	Crosstalk-Free Scheduling Algorithms for Routing in Optical Multistage Interconnection Networks
title_short	Crosstalk-Free Scheduling Algorithms for Routing in Optical Multistage Interconnection Networks
title_full	Crosstalk-Free Scheduling Algorithms for Routing in Optical Multistage Interconnection Networks
title_fullStr	Crosstalk-Free Scheduling Algorithms for Routing in Optical Multistage Interconnection Networks
title_full_unstemmed	Crosstalk-Free Scheduling Algorithms for Routing in Optical Multistage Interconnection Networks
title_sort	crosstalk-free scheduling algorithms for routing in optical multistage interconnection networks
granting_institution	Universiti Putra Malaysia
granting_department	Computer Science and Information Technology
publishDate	2009
url	http://psasir.upm.edu.my/id/eprint/7137/1/FSKTM_2009_2a.pdf
_version_	1747810660933173248

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

Similar Items