A Fast Scheduling Algorithm for WDM Optical Networks

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.

Text FK_2000_22.pdf Download (785kB)

Actions (login required)

View Item