An adaptive scheduling algorithm for differentiated serviceson WDM optical networksMaode Maa,*, Mounir HamdibaSchool of Electrical and Electronic Engineering, Nanyang Technological University, Nanyang Avenue, Singapore, Singapore 639798bDepartment of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, ChinaReceived 1 August 2002; revised 13 January 2004; accepted 20 January 2004AbstractOne of the important issues in the design offuture generation high-speed networks is to provide differentiated services to different types ofapplications with various time constraints. In this paper, we study the problem of providing real-time service to either hard or soft real-timemessages in conjunction with a normal transmission service to variable-length messages without time constraints in Wavelength-Division-Multiplexing (WDM) optical networks. We propose an adaptive scheduling algorithm to schedule and manage message transmissions insingle-hop passive-star coupler based WDM optical networks. We have analyzed the complexity of the algorithm to show its feasibility. Inaddition, we have conducted extensive discrete-event simulations to evaluate the performance of the proposed algorithm. This study suggeststhat when scheduling message transmission in WDM networks, a differentiated service should be designed to benefit the transmission of bothreal-time and non-real-time messages so that the overall performance of the network could be improved.q 2004 Elsevier B.V. All rights reserved.Keywords: Optical networks; Wavelength-Division-Multiplexing; Real-time scheduling; Medium access control protocol; Differentiated service1. IntroductionWavelength-Division-Multiplexing (WDM) is an effec-tive technique for utilizing the large bandwidth of an opticalfiber. This technique, by allowing multiple messages to betransmitted in parallel on a number of channels, has thepotential to significantly improve the performance of opticalnetworks. There are several topologies that have beenproposed for WDM optical networks 1,2. One promisingtopology, especially in a local or metropolitan networkingenvironment, is the single-hop passive-star coupled top-ology 3. Using this topology, a WDM optical network canbe configured as a broadcast-and-select network in which allof the inputs from various nodes are combined by a WDMpassive-star coupler. And the mixed optical information isbroadcasted to all destinations.To unleash the potential of single-hop passive-starcoupled WDM optical networks, efficient medium accesscontrol protocols and scheduling algorithms are neededtoallocatethenetworkresourcesoptimally,whilesatisfying the messages and system constraints 1. Themedium access control protocols in a single-hop passive-star coupled WDM optical network environment can bedivided into two main classes, namely pre-allocation-based and on-demand adaptive protocols14. Pre-allocation-based techniques assign transmission rights todifferent nodes in a static and pre-determined manner.The examples of pre-allocation-based protocols can befound in Refs. 36. On the other hand, there are twotypes of common on-demand adaptive protocols. One isthe token-passing protocol. The other is the reservation-based protocol, examples of which can be found in Refs.711. Reservation-based techniques allocate a channelas the control channel to transmit global informationregarding messages to all nodes in the system. Once suchinformation is received, all nodes invoke the samescheduling algorithm to determine when to transmit/receive a message and on which data channel. Reser-vation-based techniques have a more dynamic nature andassign transmission rights based on the run-time require-ments of the nodes in the network. In this paper, wefocus our attention on reservation-based techniques.0140-3664/$ - see front matter q 2004 Elsevier B.V. All rights reserved.doi:10.1016/com.2004.01.017Computer Communications 27 (2004) author. Tel.: 65-67904385; fax: 65-67920415.E-mail addresses: emdmantu.edu.sg (M. Ma), hamdics.ust.hk(M. Hamdi).Most of the scheduling algorithms proposed for reser-vation-based techniques can only schedule fixed-lengthpackets for transmissions. Recently, many researchers haverelaxed this constraint by allowing their schedulingalgorithms to schedule variable-length messages 9,16,17.As a result, these variable-length scheduling algorithms aremore general than fixed-length scheduling algorithms andadapt better to various traffic characteristics (e.g. bursty). Inaddition, they perfectly fit the current research trend of IP-over-WDM and WDM burst-switching 18. We adopt thesame strategy in this paper by allowing our schedulingalgorithms to handle variable-length messages.There are large amounts of research results on schedulingalgorithms for providing real-time service to messages withtime constraints in various networking environments, suchas ATM, FDDI, and wireless networks. Just few reports onmedium access control protocols