A Fast Scheduling Algorithm for WDM Optical Networks

Cheah, Cheng Lai (2000) A Fast Scheduling Algorithm for WDM Optical Networks. Masters thesis, Universiti Pertanian Malaysia.

[img] PDF
822Kb

Abstract

Wavelength Division Multiplexing (WDM) is emerging as the most promising approach to exploit the huge bandwidth of optical fibre. This approach divides the optical spectrum into many different channels where each channel corresponds to a different wavelength. Single-hop WDM networks are attractive in local area environment where all the nodes can be connected to a single broadcast facility. In a single-hop WDM broadcast network, the transmitter must know when to transmit a packet and at which wavelength, while the receiver must know when to tune to the appropriate wavelength to receive the packet. This process requires some form of coordination. Many researches have focused on the scheduling algorithms that perform this kind of coordination. This thesis proposes a scheduling algorithm for the WDM broadcast networks. The algorithm employs a theory in graph, known as edge colouring of bipartite multigraph to produce the transmission schedule, which is free from collision due to the nature of the edge colouring. An optimal edge colouring of bipartite multi graph can be found in O(M log2 N) time, where M is number of packets selected for scheduling, and N is the number of the nodes. This time complexity can be improved to O(log3 N) by parallel processing using O(M) processors. Two variations of implementation of the scheduling algorithm have been proposed, namely the Variable Frame Size (VFS) and Limited Frame Size (LFS) schemes. These schemes use different criteria to select packets from the nodes for scheduling. The VFS scheme is simple, but supports only best effort transmissions. The LFS scheme ensures the frame size of the transmission schedule is bounded, thus enabling it to support bandwidth guarantee to the nodes up to a node's fair share of the network capacity. The LFS scheme is capable of supporting constant bit rate and unspecified bit rate service categories, analogous to the Asynchronous Transfer Mode (ATM) services. The results show that the LFS scheme performs better than the VFS scheme in terms of channel utilisation, packet loss probability and network throughput for all the simulated traffic patterns, especially at heavy loads. Besides, the LFS scheme respects any level of bandwidth guarantee, while the unused bandwidth can be used for best effort transmissions. The results also show that the VFS and LFS schemes are future-proof as they are able to capitalise on the increase in the number of wavelength channels.

Item Type:Thesis (Masters)
Chairman Supervisor:Associate Professor Borhanuddin Mohd Ali, PhD
Call Number:FK 2000 22
Faculty or Institute:Faculty of Engineering
ID Code:10486
Deposited By: Nur Kamila Ramli
Deposited On:26 Apr 2011 03:16
Last Modified:26 Apr 2011 03:17

Repository Staff Only: Edit item detail

Document Download Statistics

This item has been downloaded for since 26 Apr 2011 03:16.

View statistics for "A Fast Scheduling Algorithm for WDM Optical 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.