UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Analysis and design of optical burst switching networks Kaheel, Ayman Malek 2005

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-ubc_2005-105135.pdf [ 8.71MB ]
Metadata
JSON: 831-1.0099850.json
JSON-LD: 831-1.0099850-ld.json
RDF/XML (Pretty): 831-1.0099850-rdf.xml
RDF/JSON: 831-1.0099850-rdf.json
Turtle: 831-1.0099850-turtle.txt
N-Triples: 831-1.0099850-rdf-ntriples.txt
Original Record: 831-1.0099850-source.json
Full Text
831-1.0099850-fulltext.txt
Citation
831-1.0099850.ris

Full Text

Analysis and Design of Optical Burst Switching Networks by Ayman Malek Kaheel B.Sc, Cairo University, 1995 M.Sc., University of Louisville, 1998 A THESIS SUBMITTED IN PARTIAL F U L F I L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF DOCTOR OF PHILOSOPHY in T H E F A C U L T Y OF G R A D U A T E STUDIES (Electrical and Computer Engineering) T H E UNIVERSITY OF BRITISH COLUMBIA June 3, 2005 © Ayman Malek Kaheel, 2005 i i Abstract Opt i ca l Burs t Swi tching ( O B S ) is a hybr id technique between coarse grain opt ical c ircui t switching and fine grain opt ica l packet switching. In O B S networks, user data is switched entirely in the opt ical domain , while control and management functions are performed i n the electrical domain. T h i s separation of the data plane and the control plane allows O B S networks to provide reasonably high levels of u t i l iza t ion while circumventing the need for opt ical buffering. In spite of O B S favorable features, several issues need to be addressed before O B S can be deployed i n the Internet backbone. T h e objectives of this thesis are twofold: devise new methods for quality-of-service (QoS) provisioning i n O B S networks, and develop new wavelength scheduling algori thms for enhancing the blocking probabi l i ty i n O B S networks. QoS provisioning is a major research problem in O B S networks. T h i s is ma in ly because of the absence of the concept of "packet queues" i n O B S networks. Th i s thesis proposes two approaches for QoS provisioning i n O B S networks. T h e first approach is a simple, yet effective scheme, called preemptive pr ior i t ized just enough t ime ( P P J E T ) . P P J E T provides better service for h igh pr ior i ty traffic by dropping reservations belonging to lower pr ior i ty traffic using a new channel scheduling a lgor i thm called preemptive latest Abstract in available unused channel w i t h void fill ing ( P L A U C - V F ) . S imula t ion results show that P P J E T outperforms offset-based QoS schemes both in terms of dropping probabi l i ty and end-to-end delay. A s a second approach for solving the QoS problem in O B S networks, we present a detailed architecture for provid ing quanti tat ive QoS guarantees w i t h respect to end-to-end delay, throughput, and packet loss probabi l i ty in labeled O B S networks. T h e architecture describes a novel approach for apply ing fair scheduling algori thms i n bo th the da ta plane of labeled O B S edge nodes and the control plane of core nodes wi thout the need for opt ical buffering. In addi t ion, we present analyt ical results for delay, throughput, and blocking probabi l i ty i n the proposed architecture. S imula t ion results demonstrate that the proposed architecture provides accurate and controllable service differentiation in labeled O B S networks. T h e absence of opt ical buffers i n O B S nodes, coupled w i t h the one way nature of O B S signaling protocols, drives the blocking probabi l i ty to become the ma in performance mea-sure i n O B S networks. T h i s give rise to the need for analyt ical models for calculat ing the blocking probabi l i ty in O B S networks. In this thesis we present an approximate analyt ical model for calculat ing the b locking probabi l i ty i n O B S networks. T h e proposed analyt ical model takes into consideration the peculiar characteristics of O B S networks. To verify its accuracy, we compared the model results w i t h results from a discrete-event s imulat ion model . T h e proposed model results are i n satisfactory agreement w i th s imulat ion results. T h e blocking probabi l i ty at an O B S node depends to a certain degree on how effi-Abstract iv ciently can the wavelength scheduling algori thm handle voids on wavelength channels. T h i s fact has led to a growing interest in the area of wavelength scheduling i n O B S net-works. In this thesis we survey all previously proposed wavelength scheduling algorithms for O B S networks. In addi t ion, we present two new wavelength scheduling algorithms: M i n - A V and M a x - N G V . We compared the performance of the newly proposed algo-r i thms to those previously proposed using discrete-event s imulat ion. S imula t ion results show that, i n general, the M i n - A V algor i thm performs better than a l l previously proposed algorithms. Previous ly proposed wavelength schedulers, i n addi t ion to the M i n - A V and M a x - A V algorithms, are considered to be greedy algorithms. They are greedy in the sense that they consider every reservation request individual ly , and make the choice that looks best at the moment. We present i n this thesis a new class of wavelength scheduling algorithms for O B S networks. T h e proposed wavelength scheduling algorithms process a batch of reservation requests together, instead of processing them one by one, and accept the requests that w i l l maximize the u t i l i za t ion of the wavelength channels. We describe an op t imal batch scheduler that serves as an upper bound on the performance of batch scheduling algorithms. Furthermore, we introduce four novel heuristic batch scheduling algori thms. S imula t ion results suggest that batch schedulers could significantly decrease the b locking probabi l i ty i n O B S networks. V Contents Abstract h Contents v List of Figures x l List of Tables x v List of Abbreviations x y i Dedication x i x Acknowledgements x x 1 Introduction 1 1.1 M o t i v a t i o n 1 1.1.1 A l l - O p t i c a l Networks 2 1.1.2 Qua l i ty of Service in A l l - O p t i c a l Networks 5 1.2 T h e Thesis 7 1.2.1 Objectives 7 Contents v i 1.2.2 Contr ibut ions 7 1.2.3 R o a d M a p 9 2 Overview of Optical Burst Switching Networks 11 2.1 Signal ing Protocols 12 2.2 O B S Core Nodes 14 2.3 O B S Edge Nodes 16 3 Wavelength Scheduling Algorithms in O B S Networks 19 3.1 Introduct ion 19 3.2 Previous Work 21 3.3 Proposed Algor i thms 25 3.3.1 M a x - N G V 25 3.3.2 M i n - A V 26 3.4 Performance Eva lua t ion 27 3.4.1 S imula t ion Setup 27 3.4.2 Simula t ion Results 29 3.5 Conc lud ing Remarks 34 4 A Novel Pr ior i ty Scheme for Supporting QoS in O B S Networks . . . 35 4.1 Introduct ion 35 4.2 Overview of P J E T 37 4.3 Introducing P P J E T 38 Contents v n 4.3.1 P L A U C - V F Channe l Scheduling A l g o r i t h m 39 4.4 Dropp ing Probab i l i ty Ca lcu la t ion in P P J E T 40 4.5 Performance Analys i s 43 4.5.1 Network Setup 44 4.5.2 Burs t Dropp ing Probab i l i ty 46 4.5.3 E T E delay 48 4.6 Conc lud ing Remarks 53 5 A N e w A n a l y t i c a l M o d e l for C o m p u t i n g B l o c k i n g P r o b a b i l i t y i n O B S N e t w o r k s 54 5.1 Introduct ion 54 5.2 B lock ing Probab i l i ty 55 5.3 Advance Reservation Systems 56 5.4 Proposed M o d e l 59 5.4.1 P rob l em Descr ip t ion and Assumpt ions 59 5.4.2 Traffic M o d e l 60 5.4.3 State Descr ip t ion 62 5.4.4 B l o c k i n g Probab i l i ty Ca lcu la t ion 64 5.5 Performance Eva lua t ion 67 5.5.1 Effect of Offset T i m e 68 5.5.2 Effect of Burs t Size 71 5.5.3 Compar i son w i t h Er lang 's Loss Formula 73 Contents v i i i 5.5.4 Effect of the number of wavelength channels 75 5.5.5 Effect of t ime slot size 76 5.6 Conc lud ing Remarks 80 6 Q u a n t i t a t i v e Q o S G u a r a n t e e s i n L a b e l e d O B S N e t w o r k s 82 6.1 Introduct ion 82 6.2 Proposed Archi tecture 84 6.2.1 O B S Edge node 85 6.2.2 Signal ing Pro toco l 88 6.2.3 O B S Core node 88 6.3 QoS guarantees 91 6.3.1 Weighted Fai r Queueing 91 6.3.2 B a n d w i d t h Guarantees 92 6.3.3 Delay guarantees 93 6.3.4 Burs t Loss Probabi l i ty 97 6.4 Performance Eva lua t ion 99 6.4.1 Delay Guarantees 101 6.4.2 Loss Probab i l i ty 102 6.4.3 B a n d w i d t h guarantees 107 6.5 Conc lud ing Remarks 107 7 B a t c h S c h e d u l i n g A l g o r i t h m s : A C l a s s o f W a v e l e n g t h S c h e d u l e r s i n Contents ix O B S N e t w o r k s I l l 7.1 Introduct ion I l l 7.2 B a t c h Scheduling 112 7.2.1 Definitions 113 7.2.2 Interval G r a p h Color ing 114 7.3 A n O p t i m a l B a t c h Scheduling A l g o r i t h m ( B A T C H - O P T ) 116 7.4 Heuris t ic B a t c h Scheduling Algor i thms 118 7.4.1 Smallest-Last Vertex Order ing (SLV) 119 7.4.2 M a x i m a l Cliques F i rs t ( M C F ) 122 7.4.3 Smallest Star t - t ime F i r s t Order ing (SSF) 125 7.4.4 Largest Interval F i r s t Order ing (L IF ) 126 7.5 Performance Eva lua t ion 126 7.5.1 Simula t ion Setup 127 7.5.2 B l o c k i n g P robab i l i t y vs. Offered L o a d 128 7.5.3 B lock ing P robab i l i ty vs. Offset T i m e Range 129 7.5.4 Effect of the Acceptance Delay 134 7.6 Conc lud ing Remarks 139 8 C o n c l u s i o n s a n d F u t u r e R e s e a r c h 140 8.1 Summary 140 8.2 Future W o r k 144 Contents x B i b l i o g r a p h y 146 A A l g o r i t h m for F i n d i n g M a x i m a l C l i q u e s i n I n t e r v a l G r a p h s 158 B Of f l ine O p t i m a l S c h e d u l i n g A l g o r i t h m 160 X I List of Figures 2.1 A n O B S network 12 2.2 T y p i c a l da ta burst format 14 2.3 B lock d iagram of an O B S core node 15 2.4 B lock d iagram of an O B S edge node (ingress) 17 2.5 B lock d iagram of an O B S edge node (egress) 17 3.1 Wavelength scheduling i n O B S nodes 21 3.2 I l lustrat ion of the L A U C a lgor i thm 23 3.3 I l lus t ra t ion of the L A U C - V F a lgor i thm 24 3.4 I l lus t ra t ion of the M i n - N G V algor i thm 24 3.5 I l lus t ra t ion of the M a x - N G V algor i thm 26 3.6 I l lus t ra t ion of the M i n - A V algor i thm 27 3.7 S imula t ion model used i n Section 3.4 29 3.8 Effect of the burst size on the performance of different wavelength schedul-ing algori thms i n terms of the burst b locking probabi l i ty 32 List of Figures x i i 3.9 Effect of the m a x i m u m offset t ime on the performance of different wave-length scheduling algorithms i n terms of the burst b locking probabil i ty. . 33 4.1 I l lustrat ion of the P L A U C - V F a lgor i thm 41 4.2 S imula t ion network model for Section 4.5 44 4.3 Compar i son between P P J E T and P J E T class 1 dropping probabili t ies in the case of constant burst sizes 46 4.4 Compar i son between P P J E T and P J E T class 1 dropping probabil i t ies i n the case of exponential ly dis t r ibuted burst sizes 47 4.5 Effect of the mean burst size on class 1 dropping probabi l i ty 49 4.6 Class 1 E T E delay comparison i n the case of exponential B m a x 51 4.7 Class 1 E T E delay comparison i n the case of constant B m a x 52 5.1 Example to i l lustrate the difference i n the loss protocol between advance reservation systems and O B S networks 58 5.2 Simplif ied O B S - J E T model 60 5.3 Simula t ion model for Section 5.5 68 5.4 I l lustrat ion of the F F - V F a lgor i thm 69 5.5 Effect of the burst 's offset t ime on its blocking probabi l i ty 70 5.6 Effect of the burst 's size on its b locking probabi l i ty 72 5.7 Compar ison between the proposed model and Er lang ' s loss formula. . . . 74 List of Figures x i i i 5.8 Effect of the number of wavelengths on the burst b locking b locking prob-abi l i ty 75 5.9 Effect of slot size on the accuracy of the proposed model 79 6.1 Funct iona l blocks of an O B S edge node 86 6.2 Funct iona l blocks of an O B S core node 89 6.3 I l lustrat ion of the v i r tua l queue concept 90 6.4 Burs ts arrivals to the burst queue depends on the values of a and Bmax- • 96 6.5 S imula t ion network topology for Section 6.4 100 6.6 End-to-end delay i n the case of conforming traffic flows 103 6.7 End-to-end delay when F E C 0 is non-conforming 104 6.8 I l lustrat ion of a sample path of the loss probabi l i ty 105 6.9 H i g h loss probabi l i ty for F E C 0 (non-conforming) 106 6.10 Throughput for conforming traffic 108 6.11 Throughput w i th F E C 0 non-conforming 109 7.1 Con t ro l burst scheduling using greedy algorithms 112 7.2 Con t ro l burst scheduling wi th batch queue 113 7.3 M a p p i n g batch scheduling to graph coloring 115 7.4 Interval graph example 121 7.5 I l lustrat ion of the S L V algor i thm 122 7.6 I l lustrat ion of the M C F algor i thm 125 List of Figures x i v 7.7 Simulat ion model for Section 7.5 127 7.8 B lock ing probabi l i ty vs. offered load in case of exponential ly dis t r ibuted burst sizes 128 7.9 B lock ing probabi l i ty vs. offered load in case of constant burst size 130 7.10 Block ing probabi l i ty vs. offset t ime range 131 7.11 Effect of offset time range on the burst b locking probabi l i ty 133 7.12 Block ing probabi l i ty vs. acceptance delay w i t h exponential ly dis t r ibuted burst sizes 135 7.13 B lock ing probabi l i ty vs. acceptance delay w i t h constant burst sizes. . . . 136 7.14 Effect of varying the acceptance delay and the offset t ime range on the blocking probabi l i ty 138 B . l Example for m i n i m u m cost flow construct ion 162 X V List of Tables 5.1 Execut ion t ime of the analyt ical model for different values of M 77 5.2 Slot size values and their corresponding mean burst sizes, offsets, and max offset values 78 6.1 Compar i son of average and worst-case delay values between analysis and s imulat ion 102 x v i List of Abbreviat ions C A T Conta iner iza t ion wi th Aggregat ion-Timeout C B Con t ro l Burs t C o S Class of Service D B D a t a Burs t Diffserv Differentiated Services E / 0 E lec t r ica l to O p t i c a l E T E E n d - t o - E n d F D L ( s ) F ibe r Delay Line(s) F E C ( s ) Forwarding Equivalence Class(es) F F U C F i r s t F i t Unscheduled Channe l F F - V F F i r s t F i t w i t h V o i d F i l l i n g F P Q Fa i r Packet Queueing G M P L S General ized M P L S G P S General ized Processer Shar ing I L P Integer Linear P rog ram Intserv Integrated Services List of Abbreviations xv 11 I P Internet P ro toco l J E T Just Enough T i m e J I T Just In T i m e L A U C Latest Ava i lab le Unscheduled Channe l L A U C - V F Latest Avai lab le Unused Channe l w i t h V o i d F i l l i n g L I F Largest Interval F i r s t L O B S Labeled O B S M a x - N G V M a x i m u m Newly Generated V o i d M C F M a x i m a l Cliques F i r s t M i n - A V M i n i m u m Ava i l ab le V o i d M i n - N G V M i n i m u m N e w l y Generated V o i d M P L S M u l t i - P r o t o c o l L a b e l Swi tching 0 / E O p t i c a l to E lec t r i ca l O B S O p t i c a l Bur s t Swi tch ing O P S O p t i c a l Packet Swi tch ing O S M O p t i c a l Swi tch ing M a t r i x O X C O p t i c a l Cross-Connect P J E T Pr io r i t i zed J E T P L A U C - V F Preempt ive L A U C - V F P P J E T Preemptive P J E T QoS Qua l i t y of Service List of Abbreviations X V l l l R F D Reserve F i x e d D u r a t i o n S C F Q Self-Clocked Fai r Queueing S C U Swi tch Con t ro l U n i t S F Q Start- t ime Fai r Queueing S L V Smallest-Last Vertex S S F Smallest Star t - t ime F i r s t T A G T e l l - A n d - G o T C P Transmission Con t ro l P ro toco l W D M Wavelength Div i s ion M u l t i p l e x i n g W F Q Weighted Fai r Queueing W R Wavelength Rou ted x ix Dedication T o my beloved parents. -*VWAJI ^dl ^ fw^ll S^ VAI ^ dl X X Acknowledgements Fi r s t and foremost, I am obediently thankful to A l l a h , praise and glory be to h im , for his countless blessings and mercy. W i t h o u t his guidance and mercy I can do nothing. I would like to express my heartfelt grati tude to my supervisor, D r . Hussein Alnuwei r i , for his guidance, technical advice, invaluable feedback, understanding, generous support , and friendship. I have passed through many personal and difficult circumstances dur ing the period of my P h . D . program. W i t h o u t D r . A lnuwe i r i genuine kindness, I do not th ink you would be reading these words today. I am very grateful to D r . Fayez Geba l i for his valuable suggestions, and technical assistance. A l t h o u g h he is very busy, I always found h i m easy to approach and available for help. I would like to thank D r . V i c t o r Leung for funding my research i n the early years of the program. I would like to express my appreciation to m y thesis committee for their valuable comments which enhanced the presentation of this thesis. I am also thankful for D r . W i l l Evans for the number of discussions that we had and for his help w i t h the minimum-cost flow problem. A ckn owledgem ents xxi I would like to thank Professors R ichard Anstee, W i l l Evans, N ick Jaeger, V i k r a m Kr ishnamur thy , V i c t o r Leung, and Vincen t W o n g for al lowing me to at tend their courses wi thout registering for them. I would like to express my sincere thanks to my friend D r . Watheq E l - K h a r a s h i for carefully reviewing my thesis. H i s valuable comments and suggestions have been very useful i n enhancing the presentation of this thesis. I also would like to thank my friends and colleagues Tamer K h a t t a b and A m r M o -hamed for in t roducing me to O B S networks and for our fruitful col laborat ion that lead to bu i ld ing our first O B S s imulat ion model. I have been blessed to come i n contact w i t h many wonderful people throughout m y study per iod at U B C . T h i s page is definitely not enough to mention a l l of them, but, the least I can say to them is: thank you for making my stay at U B C such a pleasant experience. A m o n g the many friends that I had dur ing my study period, the following friends had the most positive effect on my life: A h m e d , Anwar , A m r M , A m r W , K h a l e d , Tamer, Halfawy, Watheq , A b d o , Juna id , Tar iq , and A w a d . Words cannot describe my feelings toward my parents. I can only pray to G o d to reward them for their constant support , persistent encouragement, and most of al l for their unwavering love. I would like to express my love and deep appreciation to the person who stood beside me through a l l t imes, my wife Faten. She was always there for me w i t h comforting words, A cknowledgem en ts x x n encouraging thoughts, and a contagious smile. I would like to extend my thanks to my sisters, Rabab and May , for being a source of mot iva t ion and prayers. f would like also to thank my parents-in-law for a l l their prayers, encouragement, and support . Las t , but not least, I would like to thank my son and daughter, O m a r and M a r i a m , for a l l the joy and happiness they have brought to my life. 1 Chapter 1 Introduction 1.1 Motivation The exponential growth of the fnternet traffic drives the demands for higher bandwid th and high-speed Internet protocol (IP) routers at an unprecedented rate. It is projected that Internet traffic w i l l continue to double every year, regardless of conditions i n the financial markets [63]. The major technology at hand that is promising to meet the high bandwid th de-mand is opt ical networking w i t h wavelength-divis ion-mult iplexing ( W D M ) technology. The advances i n W D M technology are making it possible to harness the huge potent ial bandwidth of opt ical fibers (it was shown that i t is theoretically possible to send 100 terabits per second on a single fibre [49]). W D M is an opt ical mul t ip lex ing technique that allows better exploi ta t ion of the fiber capacity by simultaneously t ransmi t t ing data over mult iple wavelength channels. In t radi t ional opt ica l networks, W D M was used to solve the problem of t ransmit-t ing the required bandwid th on opt ica l l inks . In this type of opt ica l networks, da ta is t ransmit ted between nodes i n the opt ica l domain, but a l l the switching and intelligent Chapter 1. Introduction 2 rout ing functions at intermediate nodes are performed i n the electronic domain . There-fore, data has to go through optical-to-electrical ( O / E ) and electrical-to-optical ( E / O ) conversions at each node i t traverses. The ma in problem w i t h this type of network is that the switching and processing capabili t ies of electronic I P routers/switches lag behind the transmission capabilit ies of opt ica l fibers. I P routers w i t h capacities up to few hundred gigabits per second are currently available. A t the same time, commercia l ly available W D M fibers can achieve capacities around 1.6 Tbps (10 Gbps x 160 wavelength chan-nels) [23]. T h i s serious mismatch between the transmission capacity of opt ical fiber l inks and the electronic I P routers/switches stands against t ranslat ing the huge bandwid th provided by the opt ical l inks into a user available bandwid th . T h i s is one of the key drivers for the next generation of opt ical networks: a l l -opt ical networks. 1.1.1 All-Optical Networks In an al l-optical network, data is switched from ingress nodes to egress nodes i n an opt ica l form, wi thout undergoing any O / E conversions along its pa th [61]. T h e transfer of the switching function from electronics to optics results i n an increase i n the switching speed and i n the system throughput. In addi t ion, the e l iminat ion of O / E and E / O conversions results in a major decrease i n the overall system cost, since the equipment associated w i t h these conversions contributes a significant part of the to ta l cost of today's networks [56]. In the ul t imate al l -opt ical network, I P packets w i l l be entirely processed i n the opt ical Chapter 1. Introduction 3 domain (the header and the payload). However, it is not predicted that this k ind of a l l -opt ical networks w i l l be realized i n the foreseeable future because of the l imita t ions of the opt ical component technology. Furthermore, electronics w i l l be needed to perform intelligent control functions. Therefore, current approaches to al l -opt ical networks focus on the t ransi t ion from t radi t ional opt ical networks to a form of opt ical networks i n which control operations are performed i n the electrical domain and data is handled entirely i n the opt ical domain. Three ma in approaches exist for the gradual t ransi t ion to al l -opt ical networks: wavelength rout ing, opt ical packet switching, and opt ical burst switching. W a v e l e n g t h R o u t i n g N e t w o r k s In wavelength rout ing networks ( W R ) [18], an al l-optical pa th is established between edges of the network. Th i s opt ical path is called a l ightpath [6] and is created by reserving a dedicated wavelength channel on every l ink along the path. After a predefined period of t ime, the l ightpath is released. W R networks consist of opt ica l cross-connect ( O X C ) [9] devices connected by point-to-point fiber l inks i n an arbi t rary topology. O X C devices are capable of differentiating data streams based on the input port from which a data stream arrives and its wavelength [13]. B y having a configuration table w i th in each device, a cross connection can be setup between a certain wavelength on an input port and a wavelength (which might be different from the input wavelength) on an output port . A s a result, da ta t ransmit ted between l ightpath endpoints requires no processing, no O / E conversion, and no buffering at intermediate nodes. However, being a form of Chapter 1. Introduction 4 circuit switching networks, W R networks do not use stat ist ical sharing of resources and therefore, provides low bandwidth u t i l iza t ion . O p t i c a l P a c k e t S w i t c h i n g N e t w o r k s In packet switching networks, IP traffic is processed and switched at every IP router on a packet-by-packet basis. A n I P packet contains a payload and header. The packet header contains the information required for rout ing the packet while the payload carries the actual data. T h e future and ul t imate goal of opt ical packet switching ( O P S ) networks is to process the packet header entirely i n the opt ical domain [53, 62]. W i t h the current technology, it is not possible to do such processing i n the opt ical domain . A solution for this problem is to process the header i n the electronic domain and keep the payload in the opt ical domain [26]. T h i s process requires the packet payload to be delayed (optically buffered) un t i l the header is fully processed and the packet is classified, after which the packet is assigned a wavelength. T h e ma in advantage of O P S is that it can increase the networks bandwid th u t i l i za t ion by stat is t ical ly mul t ip lexing many packet streams together. However, because of the its synchronizat ion requirements, many technical challenges remain to be addressed for O P S to become a viable solut ion [12]. O p t i c a l B u r s t S w i t c h i n g Opt i ca l burst switching ( O B S ) is an opt ical switching technique that combines the ad-vantages of bo th W R networks and O P S networks [59, 67, 74]. S imi lar to W R networks, there is no need for buffering and electronic processing for data at intermediate nodes. Chapter 1. Introduction 5 A t the same t ime, O B S ensures high bandwid th u t i l iza t ion , just like O P S , by reserving bandwid th on a l ink only when data is actual ly required to be transferred through the l ink. In O B S networks, packets are assembled into bursts at network ingress and dis-assembled back into packets at network egress. E a c h burst consists of a header and a payload. O B S uses separate wavelength channels to t ransmit the burst payload and its header. T h i s physical separation of swi tching and transmission of the burst header and payload helps to facilitate the electronic processing of headers at opt ical core nodes, and provide an al l -opt ical pa th for the burst payload. Analys i s and design of O B S networks is the focus of this thesis. O B S has received a lot of attention dur ing the past few years and is fast becoming an important area of research. Since O B S exploits bo th the huge bandwid th i n fibers for switching/ t ransmiss ion and the sophisticated processing capabi l i ty of electronics, it is able to achieve cost reduction and uti l ize the technological advances in bo th opt ical and electronic domains, ft is believed that O B S is a potential method for bu i ld ing the next generation opt ical Internet. 1.1.2 Quality of Service in All-Optical Networks Over the past decade, a significant amount of work has been dedicated to the issue of providing QoS i n n o n - W D M IP networks. Basic IP assumes a best-effort service model . In this model , the network allocates bandwid th to a l l active users as best as it can, but does not make any explici t commitment as to bandwidth , delay, or actual delivery. T h i s service model is not adequate for many real-time applications that normal ly require Chapter 1. Introduction 6 performance assurances in terms of delay, throughput, and loss ratio. A number of enhancements have been proposed to enable offering different levels of QoS i n IP networks. T h i s work has culminated i n the proposal of the Integrated Services (Intserv) [15] and the Differentiated Services (Difl'serv) [16] architectures by the I E T F . Intserv achieves QoS guarantees through end-to-end resource (bandwidth) reservation for packet flows and performing per-flow scheduling i n a l l intermediate routers and switches. Diffserv, on the other hand, defines a number of per-hop behaviors that enable providing relative QoS advantages for different classes of traffic aggregates. B o t h schemes require sources to shape their traffic as a precondit ion for provid ing end-to-end QoS guarantees. Since Internet traffic is eventually aggregated and carried over the core networks, i t is imperat ive to address end-to-end QoS issues in W D M opt ical networks. However, previous QoS methods proposed for IP networks are difficult to apply in W D M opt ica l networks main ly due to the fact that these approaches are based on the store-and-forward mode l and mandate the use of buffers for contention resolution. Current ly , there is no opt ica l memory and the use of electronic memory i n an opt ica l switch necessitates O / E and E / O conversions w i th in the switch. Us ing O / E and E / O converters l imi t s the speed of the opt ical switch and increases the cost of the opt ical switch significantly. The only means currently available for provid ing a l imi ted buffering capabi l i ty i n opt ical switches is the use of fiber delay lines ( F D L s ) . F D L s are long fiber lines used to delay the opt ical signal for a par t icular per iod of t ime. However, F D L s cannot provide the full buffering capabi l i ty required by the classical QoS approaches. Chapter 1. Introduction 7 1.2 The Thesis ; 1.2.1 Objectives T h i s thesis has two ma in objectives. T h e first objective is to develop new methods for QoS provisioning in O B S networks. T h e unique features of O B S networks, such as the lack of packet queues and the physical separation between the burst header and the burst payload, stand against apply ing previously developed QoS methods i n O B S networks. The second objective of this thesis is to develop new algori thms for reducing the burst b locking probabi l i ty i n O B S networks. The absence of opt ical buffers in O B S nodes drives the blocking probabi l i ty to become the ma in performance measure i n O B S networks. 1.2.2 Contributions T h e major contributions of this work can be highlighted as follows: • T h e development of a new wavelength scheduling a lgor i thm called Min-AV. T h e developed a lgor i thm performs better, i n terms of b locking probabil i ty, than a l l previously proposed algorithms. T h e results appear i n [33]. • T h e proposal of a new scheme for QoS provis ioning i n buffer-less O B S networks called Preemptive Pr io r i t i zed Just Enough T i m e ( P P J E T ) . P P J E T provides better service for h igh pr ior i ty traffic by dropping reservations belonging to lower pr ior i ty traffic using a new channel scheduling a lgor i thm called Preemptive Latest Avai lab le Unused Channe l w i t h V o i d F i l l i n g ( P L A U C - V F ) . T h e results have been published Chapter 1. Introduction 8 i n [29],[30]. • T h e development of a new analyt ical model for calculat ing the blocking probabi l i ty i n Jus t -Enough-Time ( J E T ) based O B S networks. T h e developed analyt ica l model takes into consideration the effects of the burst offset t ime and the burst length on the blocking probabil i ty. T h i s work also appears in [37],[38],[39]. • T h e proposal of a new detailed architecture for provid ing quanti tat ive QoS guar-antees w i t h respect to end-to-end delay, throughput, and packet loss probabi l i ty i n buffer-less labeled opt ical burst switching ( L O B S ) networks. Results from this work appear in [31],[32]. • T h e proposal of a novel class of wavelength scheduling algori thms in O B S networks. T h e proposed wavelength scheduling algori thms process a batch of control bursts together instead of processing them one by one. Th i s work has been published i n [34],[35],[36]. • T h e establishment of the relationship between O B S systems and advance reserva-t ion systems. In addi t ion, the scheduling problem i n J E T - b a s e d O B S networks was formulated as instance of the well-known interval graph-coloring problem [3, 47, 52, 78]. Some other minor contributions are also summarized: • A survey of a l l previously proposed wavelength scheduling algori thms i n J E T - b a s e d O B S networks. T h i s survey also appears i n [33],[40]. Chapter 1. Introduction 9 • The proposal of a novel approach for apply ing fair scheduling algori thms i n both the da ta plane of L O B S edge nodes and the control plane of core nodes wi thout the need for opt ical buffering. • The description of an offline a lgor i thm for finding the op t imal schedule of bursts after receiving a l l the reservation requests. T h i s op t imal schedule can serve as a reference against which the performance of other algorithms can be compared. 1.2.3 Road Map Chapter 2 gives an overview of O B S networks. It describes the architecture of O B S edge nodes, O B S signaling protocols, and the architecture of O B S core nodes. Chapter 3 surveys al l previously proposed wavelength scheduling algori thms in J E T -based O B S networks. Addi t iona l ly , i t presents a new wavelength scheduling a lgor i thm i n JET-based O B S networks. Chapter 4 proposes a strict pr ior i ty scheme for QoS provisioning i n J E T - b a s e d O B S networks. T h i s scheme is called Preemptive Pr io r i t i zed J E T ( P P J E T ) . Chapter 5 presents a new analyt ical model for evaluating the b locking probabi l i ty in J E T - b a s e d O B S networks. Chapter 6 describes a detailed architecture for provid ing quanti tat ive QoS guarantees w i t h respect to end-to-end delay, throughput, and loss probabi l i ty i n buffer-less L O B S networks. Chapter 7 introduces a novel class of wavelength scheduling algori thms i n J E T - b a s e d Chapter 1. Introduction 10 O B S networks. T h e proposed wavelength scheduling algorithms process a batch of bursts together instead of processing them one by one. Chapter 8 concludes the thesis and outlines future research problems. 11 Chapter 2 Overview of Opt ica l Burs t Switching Networks O B S networks consist of O B S edge and core nodes connected by W D M links. Figure 2.1 shows a block diagram of an O B S network. Packets arrive to the O B S edge nodes from I P routers using conventional interfaces (e.g. gigabit Ethernet , I P / A T M , etc.). Edge nodes assembles the packets into bursts, which are then routed through the O B S network. W h e n bursts arrive at network egress they are disassembled into packets, which are to be forwarded to their next hops. T h e basic switching entity i n O B S is a burst. A burst is a t ra in of packets moving together from one ingress node to one egress node and switched together at intermediate nodes. A n opt ical burst consists of two parts, a header and a payload. T h e header is called the control burst (CB) and is t ransmit ted separately from the payload, which is called the data burst (DB). T h e C B is t ransmit ted first on a separate signaling channel to reserve the bandwid th along the pa th for the corresponding D B . After a given delay, the control burst is followed by the data burst, which travels over the same pa th reserved by the control burst. T h e delay between sending the C B and sending the D B is called Chapter 2. Overview of Optical Burst Switching Networks 12 Figure 2.1: A n O B S network. the burst offset time. T h e value of the offset t ime is chosen to be greater than or equal to the to ta l processing delay encountered by the C B . Le t d be the queuing and processing t ime for a C B at a single O B S node. A s s u m i n g the C B traverses H hops, the offset time (TQ) is selected such that TQ > Hd. 2.1 Signaling Protocols Signal ing (reservation) protocols i n O B S follow one of two schemes, namely, tell-and-go ( T A G ) scheme [25], and reserve-a-fixed-duration ( R F D ) scheme [60]. In T A G scheme, the control burst reserves the wavelength channel upon its arr ival to the O B S node. O n the other hand, i n R F D scheme the control burst reserves the wavelength channel for a par t icular t ime interval . Several signaling protocols have been proposed for O B S [59, 66, 72]. A m o n g these, two protocols are widely studied i n the literature: Jus t - In-Time (J IT) [72], and Just-Chapter 2. Overview of Optical Burst Switching Networks 13 Enough-T ime ( J E T ) protocol [79]. Other protocols can be considered a var ia t ion of one of these two. The J I T protocol follows the T A G scheme and works as follows. U p o n the arr ival of a C B to a core O B S node, a wavelength channel is immediate ly reserved if available. If no wavelength is available, the request is blocked and the corresponding D B is dropped. W h e n the wavelength is successfully reserved, it remains reserved un t i l the data burst transmission finishes. T h e only information that needs to be kept i n the network nodes is whether the wavelength is currently reserved or not. The J E T protocol, on the other hand, is based on the R F D scheme. It reserves a wavelength channel exactly for the transmission t ime of the burst. In J E T , the C B contains the destination address, the da ta burst length, the wavelength on which the associated da ta burst w i l l arrive, and the burst offset t ime. W h e n a C B arrives at a core node, a wavelength channel-scheduling a lgor i thm is invoked to find a suitable wavelength channel on the outgoing l ink for the corresponding D B . T h e wavelength channel is reserved for a dura t ion equal to the burst length s tar t ing from the arr ival t ime of the D B . Therefore, nodes employing the J E T protocol need to keep track of the avai labi l i ty of free t ime intervals on every wavelength channel. In this thesis we are main ly concerned w i t h J E T - b a s e d O B S networks ( O B S - J E T ) . A typ ica l da ta burst format is shown i n Figure 2.2. T h e preamble and postamble guard bands (Pre -Guard and Pos t -Guard) are necessary to overcome the uncertainty of da ta burst arr ival and data burst durat ion. T h e sync field contains synchronizat ion Chapter 2. Overview of Optical Burst Switching Networks 14 Pre-Guard Syne Post-Guard \ s \ Length N » m Packets A l Payload Figure 2.2: T y p i c a l da ta burst format. pat tern that is used to synchronize opt ical receivers at egress edge nodes. T h e length field indicates the length of the payload. T h e number of packets field ( N u m Packets) indicates the number of packets contained in the burst. T h e addi t ional information ( A l ) field may be used to locate the start of packets i n the payload field if padding is used. T h e control burst contains necessary rout ing information to be used by core nodes to route the associated data burst hop by hop to its dest ination edge node. In addi t ion to the rout ing information, the C B contains O B S specific information, which includes the D B durat ion (in R F D protocols), the wavelength on which the associated D B w i l l arrive, D B offset time, and possibly some QoS parameters. 2.2 OBS Core Nodes T h e general architecture of an 1 x 2 opt ical core O B S node is shown i n F igure 2.3, which main ly consists of an opt ical switching mat r ix ( O S M ) , a switch control unit ( S C U ) , an optical-to-electrical ( O / E ) converter, and an electrical-to-optical ( E / O ) converter. Con t ro l bursts are carried on dedicated control channels. General ly the te rm channel is used to represent a certain unidirect ional transmission capacity (in bits per second) Chapter 2. Overview of Optical Burst Switching Networks 15 I/P Fiber 4* O S M Control O / E -> Buffer > scu E / O -> -> -> W 0 v Routing& Signaling Information W(j , Wj, w2 > O/P Fiber 1 Wn , Wj, Wi O/P Fiber 2 Figure 2.3: B lock diagram of an O B S core node. between two adjacent nodes [74]. A channel may consist of one wavelength, or a por t ion of a wavelength i n case of t ime-divis ion mul t ip lex ing or code d iv is ion mul t ip lex ing . In this thesis a channel is equivalent to one wavelength. W h e n a C B arrives to a core node, it first gets converted to electrical form, then it gets t ime-stamped, arid thereafter it gets stored i n a conventional electronic buffer. For each control burst, the S C U performs a forwarding table lookup, then it decides on which outgoing l ink (port), da ta channel, and control channel to forward the C B and the corresponding D B . ff there are free data channels available at the D B arr ival t ime to the core node, the S C U configures the O S M to let the D B pass through. Otherwise, the D B is dropped. In addi t ion, the S C U updates the burst offset t ime field i n C B to reflect the processing delay incurred by the C B in the node. Generally, the S C U configures the O S M to allow the D B to pass only for a l imi ted window of t ime, equal to the D B Chapter 2. Overview of Optical Burst Switching Networks 16 durat ion, s tar t ing from the arrival t ime of the D B . If the D B arrives to the O B S node outside this window of t ime (either earlier or later), the D B is s imply dropped (blocked) since data bursts are opt ical analog signals. If no pa th is set up when a D B enters the opt ical switching matr ix , the D B is lost. The S C U invokes a scheduler to schedule the data burst on an outgoing data channel. T h e S C U keeps mult iple instances of the scheduler, one scheduler instance for each output data l ink. E a c h scheduler instance keeps track of the busy / id le periods on a single outgoing data l ink. The scheduler works as follows. It first reads the t ime-stamp and the da ta burst dura t ion information for the C B to determine when the corresponding D B w i l l arrive to the O B S node, and for how long it w i l l need the wavelength channel. Thereafter, it sends the information for the S C U . T h e burst offset t ime field is decremented at every core node by the amount of queueing, processing, and transmission delay in the node. In this thesis we assume that tunable wavelength converters exist i n O B S core nodes. A wavelength converter is a device that converts da ta from one incoming wavelength to another outgoing wavelength [61]. It is expected that wavelength converters w i l l contribute a significant part to the to ta l cost of O B S core nodes. 2.3 OBS Edge Nodes A simplified block diagram of O B S edge nodes is shown in Figure 2.4 (ingress part) and Figure 2.5 (egress part) . T h e ma in function of the ingress part is to assemble packets into bursts and send them into the network according to the O B S signaling protocol . Chapter 2. Overview of Optical Burst Switching Networks 17 N Inputs >-CB >-DB >-CB * - D B Control S C U Routing& Signaling Information Figure 2.4: B l o c k diagram of an O B S edge node (ingress). C B -D B -C B -D B -O / B O H Burst Disassembler N Inputs J Burst Disassembler Switch 7 \ Control S C U 1 Routing& Signaling Information M Outputs > Figure 2.5: B l o c k diagram of an O B S edge node (egress). Chapter 2. Overview of Optical Burst Switching Networks 18 Packets are assembled into bursts, according to their egress edge node addresses and QoS requirements, using a burst assembly a lgor i thm. Several burst assembly algori thms were proposed i n the li terature [4, 17, 41, 69, 74]. In this thesis the burst assembly process is carried out (where applicable) using the containerizat ion w i t h aggregation-timeout ( C A T ) a lgor i thm [41] [50]. In pr inc ipa l , the function of C A T algor i thm is to assemble the arr iv ing packets into bursts that are sent by the ingress O B S to the network's core. T w o parameters control this burst assembly process in C A T , namely the m a x i m u m burst size (Bmax) and burst assembly t imeout (Tmax). T h e m a x i m u m burst size controls the m a x i m u m number of bytes that can be i n the same burst. If the incoming traffic intensity is h igh enough, the m a x i m u m burst size is reached in a reasonable t ime. However, i f the traffic has a low arrival rate, the burst under assembly might have to wait for a relatively long t ime un t i l the m a x i m u m burst size is reached. In order to avoid large burst assembling delays, an assembly t imeout parameter is used. T h e egress part of the O B S edge node (Figure 2.5) receives bo th the control burst and the data burst. B o t h are forwarded to the burst disassembler, where the data burst gets disassembled back into packets. These packets are then forwarded to the their next hop. 19 Chapter 3 Wavelength Scheduling Algor i thms in O B S Networks 3.1 Introduction A s explained i n Chapter 2, when a C B arrives at an O B S node, a wavelength scheduling a lgor i thm is invoked to find a suitable wavelength channel on the outgoing l ink for the corresponding D B . The wavelength channel is reserved for a dura t ion equal to the burst length s tar t ing from the arr ival t ime of the D B . T h e information required by the scheduler such as the burst arr ival t ime and its dura t ion are obtained from the control burst. T h e scheduler keeps track of the availabil i ty of free t ime intervals (voids) on every wavelength channel. The absence of the concept of "packet queues" in O B S nodes, coupled wi th the one way nature of O B S signaling protocols, drives the burst b locking probabi l i ty to become the ma in performance measure i n O B S networks. T h e burst b locking probabi l i ty is the probabi l i ty that a wavelength reservation request w i l l not be granted due to the unavai labi l i ty of a free wavelength. Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 20 Different terms ha,ve been used i n the li terature to express the probabi l i ty of burst loss such as blocking probability, dropping probability, and loss probability. In this thesis, we adopt the following terminology. T h e term blocking probability is used to express burst loss that is due to unavai labi l i ty of a free wavelength. T h e term dropping probability is used whenever intentional dropping of bursts is involved. T h e term loss probability is a general term that is used when there are more than one possible reason for burst loss. T h e blocking probabi l i ty at an O B S node depends, to a certain degree, on how efficient can the wavelength scheduling a lgor i thm handle voids on wavelength channels. T h i s has led to a growing interest i n the area of wavelength scheduling i n O B S networks. A number of wavelength scheduling algorithms have been proposed i n the li terature [27, 51, 66, 74, 75]. In this chapter we survey al l previously proposed wavelength scheduling algorithms. In addi t ion, we present two new scheduling algorithms and compare the performance of the two new algorithms to exist ing ones. The rest of this chapter is organized as follows. Section 3.2 presents a survey of previously exist ing algorithms. T w o new wavelength scheduling algori thms are proposed i n Section 3.3. Section 3.4 presents s imulat ion results of the proposed algorithms and their comparisons w i th the exist ing ones. Conc lud ing remarks are provided in Section 3.5. Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 21 b o 1 I J <s! | I I | | 1 i' to I , f 1 I 1 1 1 ¥ ¥ t ime t ime Figure 3.1: Wavelength scheduling in O B S nodes. 3.2 Previous Work In O B S networks employing the J E T protocol ( O B S - J E T networks), a control burst ar r iv ing at a node represents a wavelength reservation request. A reservation request consists of a pair of values (ta,te). The value ta is determined based on the offset t ime, whereas te is determined based on ta and the length of the burst b as shown i n Figure 3.1. A wavelength scheduling a lgor i thm X is more efficient than wavelength scheduling algori thm Y, i f it increases the u t i l i za t ion of the wavelength channels and hence decreases the burst b locking probabil i ty. T h e burst blocking probabi l i ty is calculated as the ratio of bits blocked to bits sent. A wavelength channel is said to be unscheduled at t ime t when no burst is using the channel at or after that t ime. A channel is said to be unused for the dura t ion of voids between successive bursts and after the last burst assigned to the channel. Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 22 T h e most basic wavelength scheduling algori thm is the F i r s t F i t Unscheduled Channel ( F F U C ) a lgor i thm [51]. For each of the outgoing wavelength channels, the F F U C algo-r i t hm keeps track of the unscheduled t ime. Whenever a control burst arrives, the F F U C algor i thm searches a l l wavelength channels i n a fixed order and assigns the burst to the first channel that has unscheduled t ime less than the data burst arr ival t ime. The main advantage of the F F U C algor i thm is its computat ional simplici ty. Its ma in drawback is that i t results i n high blocking probabil i ty, since the a lgor i thm does not consider voids between bursts scheduled. In [66], Turner proposed the Latest Avai lab le Unscheduled Channel ( L A U C ) algo-r i t hm. The basic idea of the L A U C algor i thm is to increase channel u t i l i za t ion by min i -miz ing voids created between bursts. T h i s is accomplished by selecting the latest available unscheduled data channel for each arr iv ing data burst. For example, in Figure 3.2 wave-lengths 0 and 3 are unscheduled at t ime ta, and wavelength 0 w i l l be selected to carry the new data burst a r r iv ing at ta; thus, the void on wavelength 0 w i l l be smaller than the void that would have been created if wavelength 3 were selected. Therefore, L A U C yields better burst dropping performance than F F U C and does not add any computat ion overhead. However, since it does not take advantage of voids between bursts, as was the case for the F F U C , it s t i l l leads to a relatively high blocking probabil i ty. X i o n g et al . [74] proposed a channel a lgori thm called LAUC-VF (Latest Avai lab le Unused Channe l w i t h V o i d F i l l i n g ) . T h e basic idea of the L A U C - V F a lgor i thm is to minimize voids by selecting the latest available unused da ta channel for each arr iving Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 23 . t ime . t ime _ t ime | I t l4 | t« I I „ time I I Figure 3.2: I l lustrat ion of the L A U C algori thm. data burst. G i v e n the arr ival t ime ta of a data burst w i t h durat ion b to the optical switch, the scheduler first finds the outgoing data channels that are available for the t ime per iod of (ta; ta + b). ff there is at least one such data channel, the scheduler selects the latest available data channel, i.e., the channel having the smallest gap between ta and the end of the last da ta burst just before ta. Figure 3.3 illustrates that L A U C - V F chooses channel 2 i n the previous example. I izuka et a l . [27] proposed a scheduling algori thm that selects the data channel i n which the void newly generated after the burst ending t ime becomes m i n i m u m (we cal l it Min-NGV a lgori thm). Figure 3.4 illustrates an example for the algori thm. T h e M i n -N G V a lgor i thm chooses wavelength channel 1 since this choice w i l l generate the smallest void after the burst ending t ime. X u et al . [75] has proposed two algorithms: M i n i m u m Star t ing V o i d (Min-SV) and M i n i m u m E n d i n g V o i d (Min-EV). B o t h algorithms are based on computat ional geometry Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 24 3 * 1 t 3 1 1 t i ! i 1 i t2 1 New Burst '5 E 1 1 1 t 1 16 "] 1 f 1 ti ' a t ime t ime Figure 3.3: I l lustrat ion of the L A U C - V F algori thm. o — J — — L — — —*- t i m e New i'- i i 1 1 1 i i i t ime 1 1 «2 L, t ime t6 time Figure 3.4: I l lustrat ion of the M i n - N G V algor i thm. Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 25 techniques. T h e M i n - S V a lgor i thm performance is close to the performance of the L A U C -V F , while the M i n - E V algor i thm is the same as the M i n - N G V . However, M i n - E V and M i n - S V are claimed to be faster than M i n - N G V and L A U C - V F , respectively. 3.3 Proposed Algorithms In this section, two wavelength scheduling algorithms are proposed. T h e first a lgor i thm is called M a x i m u m Newly Generated V o i d ( M a x - N G V ) , and the second one is called M i n i m u m Avai lab le V o i d ( M i n - A V ) . 3.3.1 M a x - N G V The idea behind the M a x - N G V algor i thm is to minimize the burst b locking probabi l i ty by selecting the da ta channel that results i n the largest void after the burst ending t ime. T h i s way larger voids w i l l be available for future data bursts. G i v e n the arr ival t ime ta of a da ta burst w i t h dura t ion b to the opt ical switch, the scheduler first finds the outgoing data channels that are available for the t ime per iod of (ta; ta + b). If there is at least one such data channel, the scheduler selects the channel having the largest gap between {ta + b) and the start of the da ta burst just after (ta + b). In other words, the a lgori thm assigns the burst to the channel that results i n the largest newly generated void after the burst ending t ime. A n example for the M a x - N G V algori thm is i l lustrated i n Figure 3.5. Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 26 o t ime ^ t ime 2 t ime 4- ti me Figure 3.5: I l lustrat ion of the M a x - N G V algori thm. 3.3.2 M in -AV The basic idea of the M i n - A V a lgor i thm is to minimize voids by selecting the smallest void among a l l possible voids. G i v e n the arr ival t ime ta of a data burst w i th dura t ion b to the opt ical switch, the scheduler first finds the outgoing data channels that are available for the t ime period of (ta; ta + b). If there is at least one such data channel, the scheduler selects the data channel that has the smallest available void . Accordingly , the scheduler w i l l always minimize voids result ing from assigning the burst to the data channel. A n example for the M i n - A V algor i thm is shown i n Figure 3.6. The algori thm chooses channel 0 since it has the m i n i m u m void among al l possible voids. Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 27 New Bars) '3 I |*5 i I . , _ _ , I 1 time •)• 1 1 i k I I <« -> I ll I '< L. time I I I t 1 1 ' ? 1 I ' "~1 ! 1 I L time '1 'a tc t8 Figure 3.6: I l lustrat ion of the M i n - A V algori thm. 3.4 Performance Evaluation T h i s section presents experimental results on the proposed algorithms, M a x - N G V and M i n - A V , and their comparisons wi th the existing algorithms, L A U C - V F , M i n - N G V . Our ma in concern i n these experiments is the blocking probabil i ty. We ignore the L A U C algori thm i n our comparison since it is already known to be outperformed by the L A U C -V F algori thm i n terms of blocking probabil i ty. Addi t iona l ly , as indicated before, the performance of the L A U C - V F is an upper bound on the performance of the M i n - S V , while M i n - E V performance is s imilar to the performance of the M i n - N G V . 3.4.1 Simulation Setup Figure 3.7 shows the s imulat ion model used i n this section, which is based on the O P N E T [54] s imulat ion tool . It consists of a single O B S node connected to n traffic sources and a sink node. E a c h input l ink carries 2 separate wavelengths, one for data and one for Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 28 control . T h e output l ink carries five wavelengths, four for da ta and one for control, and each wavelength has transmission speed of approximately 2.5 Gbps (OC-48) . P rac t i ca l W D M systems typica l ly use larger numbers of wavelengths (e.g., 32-128 wavelengths). However, obta ining reliable results from a discrete-event s imulat ion of such systems would require running the s imulat ion for a prohibi t ively long t ime. Therefore, for the purpose of our research, we have used a relatively smal l number of wavelengths i n order to model and analyze our architecture i n a reasonable amount of t ime. S tudy ing the s imulat ion results of our model has revealed that the only impact of using a relatively smal l number of wavelengths is that the blocking probabi l i ty across various classes of service has uniformly increased. We assume that sources generate control and data bursts. Burs t sizes are exponen-t ia l ly dis t r ibuted wi th mean B units. T h e offset time has a uniform dis t r ibut ion over [0, Amax]. T h e mean burst size B and the m a x i m u m offset t ime Amax are varied to s tudy their effect. A l l traffic sources used are Poisson sources. T h e use of Poisson process to characterize the arrival process i n O B S networks has been heavily discussed i n the li terature [17, 24, 28, 74, 82]. It is generally accepted that Internet traffic is s tat is t ical ly self-similar [44, 57, 73]. However, i t has been shown that i n O B S networks the burst assembly process reduces the long-range and the short-range dependency of the traffic [17, 24, 74, 82]. In addi t ion, i n buffer-less O B S networks the influence of the long-range dependency of the self-similar traffic can be neglected and the arr ival process can be assumed to be Poisson process, as i l lustrated i n [28, 82]. Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 29 Figure 3.7: S imula t ion model used i n Section 3.4. T h e m a i n difference between scheduling algori thms compared in this section is the wavelength selection cri teria. Therefore, i n the O B S node we have implemented a general wavelength scheduling a lgor i thm that changes the void selection process depending on the par t icular a lgor i thm requested. A description of the a lgor i thm is given in A l g o r i t h m 3.1. T h e function Ge t_Void( i , t 0 , i e ) searches wavelength i for a void that can fit a burst a r r iv ing at t ime ta and ending at t ime te. In general, a void can be represented by an interval w i t h start t ime and end t ime tve. C lea r ly this interval can be semi-unbounded, i.e., tg = oo, if the channel is unscheduled at t ime tvs. If there is at least one such data channel, the function Select_Void selects a wavelength from those having available voids using the specified a lgor i thm (algol). 3.4.2 Simulation Results We study the effect of varying the m a x i m u m burst offset t ime and the mean burst size on the performance of the proposed algorithms, M a x - N G V and M i n - A V , and the existing algorithms, L A U C - V F , M i n - N G V . Le t A be the transmission t ime of 1024 bits on one Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 30 i n p u t : ta, te, algol o u t p u t : wl i n i t i a l i z e i <— 0, wl < 1 for % <— 0 to DatcL-WL-Num d o v[i] <— Get_Void (z , ta,te); e n d i f v is empty t h e n report failure i n finding an outgoing channel: stop; e n d wl <— Se lec t_Void (v , a lgo l ) ; reserve channel wl for da ta burst; report wl; A l g o r i t h m 3.1: General wavelength scheduling a lgor i thm Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 31 of the wavelengths, i.e., A = 1024/2377728000 = 4 .3e" 7 seconds. We express the offset t ime in terms of A . We also express B as multiples of 1024 bits. E a c h data point i n the following results is the average of 10 runs w i t h 10 different seeds. Effect of burst size In this subsection, we set the m a x i m u m offset t ime Amax= 100A. We perform two sets of simulations. T h e first set corresponds to mean burst size B= 160 (i.e., 5=163840 bits) , while the second set corresponds to B= 20. The burst inter-arrival t ime was also varied i n order to vary the offered load. Figure 3.8 i l lustrate the results. Result set marked as (1) i n Figure 3.8 corresponds to the case of B= 160. In this set of results, we see that a l l scheduling algorithms give approximately the same blocking probabil i ty. In the second set of results, which corresponds to 5 = 2 0 , the proposed M i n - A V algor i thm has the best performance among a l l algorithms, while M a x - N G V and M i n - N G V algori thms give the worst performance. Generally, smaller mean burst size causes more fragmentation for the wavelength channels than i n the case of larger mean burst size. Higher fragmentation levels of the wavelength channel causes the b locking probabi l i ty to increase. It is the job of the wavelength scheduler to decrease the level of fragmentation where possible. M a x - N G V and M i n - N G V are less successful in decreasing the level of fragmentation on channels when the mean burst size is smal l . Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 32 Figure 3.8: Effect of the burst size on the performance of different wavelength scheduling algorithms i n terms of the burst b locking probabil i ty. Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 33 0.45 0.4 - B - Min- NGV & offset=50 O- Min- NGV & offset=400 - • - Min-AV & offset=50 ••*• Min-AV & offset=400 (2) 0.35 - ) - MAX-NGV & offset=50 •+• MAX-NGV & offset=400 UAUC-VF & offset=50 •0 LAUC-VF &offset=400 TO O CL Total Traffic Load Figure 3.9: Effect of the m a x i m u m offset t ime on the performance of different wavelength Effect of offset time In this subsection, we assign to B an arbi trary value of 80 and vary the inter-arrival t ime to vary the offered load. We perform two sets of simulations. The first set corresponds to a m a x i m u m offset value equal to 5 0 A , whereas the second set corresponds to Amax= 400A. Results are shown i n Figure 3.9. Results from the first simulations set show that for smal l values of Amax a l l algo-r i thms typica l ly result i n approximately equal blocking probabil i ty. T h e second set of simulations shows that as Amax becomes larger, different algorithms result in different scheduling algorithms i n terms of the burst b locking probabil i ty. Chapter 3. Wavelength Scheduling Algorithms in OBS Networks 34 blocking probabi l i ty values. In addi t ion, results show that M a x - N G V and M i n - N G V produce higher b locking probabil i t ies than L A U C - V F , M i n - A V for larger values of Amax. W h e n the m a x i m u m offset t ime value increases, reservations' start t ime values are more dispersed i n time. T h i s causes the fragmentation of the wavelength channel to increase as the m a x i m u m offset t ime increases. Results in Figure 3.9 show that the M i n - A V and L A U C - V F algori thms pack reservations on wavelength channels better than M a x - N G V and M i n - N G V , which i n tu rn decreases the fragmentation of the wavelength channels.. 3.5 Concluding Remarks In this chapter, we surveyed previously proposed wavelength scheduling algorithms. Moreover, we have introduced two new wavelength reservation algorithms: M a x - N G V and M i n - A V . T h e performance of the proposed algorithms and their comparison wi th previously proposed algori thms was evaluated through discrete-event s imulat ion. S imu-la t ion results showed that the M i n - A V algor i thm performs at least as good as the best previously known algor i thm ( L A U C - V F ) in terms of blocking probabil i ty. Results also showed that M i n - A V is specially advantageous when mean burst size is smal l . 35 Chapter 4 A Novel P r io r i t y Scheme for Support ing QoS in O B S Networks 4.1 Introduction In this chapter, we present a novel scheme for QoS provisioning in buffer-less O B S net-works. We cal l this scheme Preempt ive Pr io r i t i zed J E T ( P P J E T ) . P P J E T provides service to different traffic classes based on a strict pr ior i ty order. The P P J E T scheme u t i -lizes the J E T signaling protocol , i n conjunction w i t h a new channel-scheduling algori thm, called Preemptive Latest Ava i l ab le Unused Channe l w i t h V o i d F i l l i n g ( P L A U C - V F ) . A number of related approaches appear i n the l i terature [2, 76, 80]. A signaling protocol , called Pr io r i t i zed Jus t -Enough-Time ( P J E T ) , has been proposed for providing priori ty-based service differentiation in O B S networks [80]. T h e m a i n drawback of P J E T is that it introduces a significant amount of delay for h igh pr ior i ty traffic in order to provide a reasonable isolat ion level from lower pr ior i ty traffic classes. T w o different preemptive schemes for QoS provis ioning i n O B S networks have been proposed in the li terature. Cankaya et al. [2] proposed a par t ia l preemptive schedul-Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 36 ing scheme. T h i s scheme combines propor t ional differentiation discipline w i t h par t ia l preemptive scheduling such that the burst dropping probabi l i ty is adjusted to be pro-por t ional to the parameters set by the network service provider. T h e a lgor i thm used for burst scheduling under this scheme has, however, high complexi ty due to the lengthly burst acceptance/rejection decision process i n intermediate switching nodes. Moreover, the propor t ional differentiation technique itself requires main ta in ing statistics about each class of service i n every node i n the network. T h i s information is updated wi th every control burst, which severely l imi t s the scalabil i ty of the approach considering the high volume of bursts i n O B S networks. A different scheme has been described by Y a n g et al. [76]. The i r scheme allows high pr ior i ty bursts to preempt low pr ior i ty bursts i n a probabil is t ic manner. However, the model given i n their paper to estimate the b locking probabi l i ty is incomplete because i t ignores completely the effects of the offset t ime and its d is t r ibut ion on the b locking probabil i ty. In addi t ion, their scheme cannot make use of void filling channel-scheduling algori thms, leading to much higher dropping probabil i t ies than the P J E T scheme. T h e rest of this chapter is organized as follows. Section 4.2 gives an overview of P J E T . In Section 4.3, we present the P P J E T scheme and the P L A U C - V F algori thm. We discuss an approximate method for calculat ing the dropping probabi l i ty in P P J E T i n Section 4.4. We evaluate the performance of the proposed scheme i n Section 4.5 and provide concluding remarks in Section 4.6. Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 37 4.2 Overview of PJET The P J E T protocol uses offset t ime as a way to provide different classes of service i n buffer-less O B S networks. Assume we have two classes of service: class 1 and class 0. Class f is the real-time service class that corresponds to applications that require low delay, bandwid th guarantee, and low dropping probabil i ty, while class 0 is the best effort service class. In order for class f to have higher pr ior i ty for bandwid th reservation, an addi t ional offset t ime, denoted tqos, is given to this class. The value of tqos is constant and considerably larger than the or iginal J E T offset t ime (T G ) . Add i t iona l ly , tqos needs to be larger than the m a x i m u m burst length in class 0. W i t h such long offset t ime, the dropping probabi l i ty of bursts i n class f becomes independent of the offered load in class 0 and only a function of the offered load in class 1. O n the other hand, the offered load i n both classes w i l l determine the dropping probabi l i ty of class 0. T h e authors i n [80] gave a simple analyt ical model to evaluate the dropping probabi l i ty as a function of tqos and concluded that to provide almost 100% isolation between classes 0 and 1, i t is sufficient to have tqos equal to 5 Lo , where L0 is the average burst size i n class 0. T h e ma in problem w i t h this protocol is that i t introduces a significant amount of delay for high pr ior i ty traffic. Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 38 4 .3 Introducing PPJET In this section we describe P P J E T , a novel pr ior i ty based scheme for QoS provisioning i n buffer-less O B S networks. Th i s scheme minimizes dropping of h igh pr ior i ty traffic by preempting reservations for lower pr ior i ty traffic. Consider the case of an O B S network support ing two priori ty classes, namely class 0 and class 1, where class 1 is given higher pr ior i ty over class 0 in terms of dropping probabi l i ty (i.e., class 1 has lower packet drop-ping probabi l i ty than class 0). A t the network ingress, incoming traffic is aggregated into bursts, such that each burst w i l l belong to either class 1 or class 0. Whenever a data burst is ready to be sent, the corresponding control burst is sent to request reservations at intermediate nodes for the data burst. W h e n class 1 reservation request arrives at an intermediate node it cannot be blocked (dropped) by a future class 0 request nor can it be blocked by an existing class 0 reservation for any dura t ion i n the future. It can only be blocked by an existing class 1 reservation, or a class 0 reservation that has a start t ime i n the past (that is to say, the reserved dura t ion has started already). T h e ma in advantage of P P J E T is that i t eliminates the need for the relatively large QoS offset period required by the P J E T scheme for provid ing strict priority. In P P J E T , reservation requests are signaled using J E T w i t h basic offset T0. T h e only modif icat ion required for the J E T protocol is to add to the C B a class-of-service (CoS) field indica t ing the class of service that the burst belongs to. To achieve the goal of providing a strict pr ior i ty for h igh pr ior i ty reservations, we propose a new channel scheduling algori thm, called P r e e m p t i v e - L A U C - V F ( P L A U C -Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 39 V F ) , to be used at ingress and intermediate O B S nodes to allocate wavelength channels for the data burst durat ion. 4.3.1 P L A U C - V F Channel Scheduling Algorithm In the P L A U C - V F algori thm, when a request belonging to a h igh pr ior i ty traffic class arrives, the a lgor i thm first searches the wavelength channels for voids that can accom-modate the new reservation, ff more than one void exist, the latest available unused data channel is selected. If no vo id can be found, the a lgor i thm finds, for each channel, the original reservations that blocked the new reservation request. If these reservations belong to lower pr ior i ty classes, the a lgori thm calculates the void that w i l l exist if these original reservations are dropped. Then , the a lgori thm selects the channel that has the void w i th the latest start-time among the newly created voids. Thereafter, the a lgor i thm drops the or iginal blocking reservations on the selected channel. For example, i n Figure 4.1(a) there is no void that is large enough to fit the new burst that is to arrive at t ime ta. T h e P L A U C - V F algori thm w i l l find bursts that might be dropped to create a new void that is large enough to fit the new arr iv ing burst. Channels 0 and 1 are not selected by the a lgori thm because the bursts that need to be dropped belong to the same C o S of the new burst. B o t h channels 2, 3 are eligible because suitable voids can be created by dropping lower C o S bursts. However, the a lgor i thm selects channel 3, as shown i n Figure 4.1(b), since its new void has the latest start t ime. A formal description of the a lgor i thm is given i n A l g o r i t h m 4.1. The P L A U C - V F a lgor i thm has similari t ies w i t h the a lgor i thm Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 40 described in A l g o r i t h m 3.1. The function Ge t JVb id is modified here to include a CoS parameter and also to return the reservations to be dropped, if any. After calculat ing al l suitable voids, the a lgor i thm part i t ions the set of voids into two subsets: the set of or iginal voids (ov) and the set of new voids (nv). T h e former set includes voids that already exist on wavelength channels, while the latter set includes voids that w i l l be cre-ated by dropping reservations belonging to lower CoS(s) . T h e set of bursts that need to be dropped in order to accommodate the new burst on wavelength i is kept i n d[i}. O n l y if ov set is empty, the nv set is considered by the a lgori thm. T h e function F i n d _ L S T _ V o i d is used to find the void w i t h the latest start t ime among ov i f ov is not empty, otherwise it is used on nv. T h e a lgor i thm terminates w i t h the reserved wavelength if a suitable void can be found or created, otherwise an error is reported. 4 .4 Dropping Probability Calculation in PPJET One possible method for approximat ing the dropping probabi l i ty i n P P J E T scheme is to model the output port as a M/G/k/k queue, and calculate the dropping probabi l i ty using the well-known Er lang ' s B-formula: Bp(Plk) = -p^- (4.1) In this equation, k is the number of wavelengths, and p is the total offered load. Consider 2 classes of service, class 0 and class 1. Class 1 corresponds to the high prior i ty Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 41 (a) C o S 1 » . time I, 1, J t, CoS =!) 3 CoS 0 ! . l ime I f 13> 0) Figure 4.1: I l lustrat ion of the P L A U C - V F algor i thm. Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 42 i n p u t : ta, te, cos o u t p u t : wl i n i t i a l i z e i <— 0,wl < 1 for i <— 0 to DataJWL-Num d o Get_Void(t a, te, cos); e n d i f v is empty t h e n report failure in finding an outgoing channel; stop: e n d ov[ } <— {v[i] | d[i] is empty}; nv[ } <— {v[i} | d[i] not empty}; i f ov not empty t h e n wl <— Find_LST_Void(ou); reserve channel wl for da ta burst; report wl; stop: else io/ <— Find_LST_Void(ra;); Drop (d[tij(!]); reserve channel wl for data burst; report wl; stop; e n d A l g o r i t h m 4 . 1 : P L A U C - V F a lgor i thm Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 43 traffic and class 0 corresponds to the best-effort traffic. Since P P J E T is a strict pr ior i ty scheme, the dropping probabi l i ty of class 1 (Pdrop,i) depends only on its traffic load. Thus , Pdrop,i can be direct ly obtained by Bp(pi,k). Class f offered load can be calculated as Xb, where b is the average burst size and A is the average arr ival rate. O n the other hand, the burst dropping probabi l i ty of class 0 (Pdrop,o) can be calculated from the following conservation law: tot — P\P<lrop,l + PoPdropfi (4-2) where p = pi + po and Pdrop,tot = Bp(p, k). Unfortunately, this approximat ion is not accurate because it neglects the effect of the offset t ime and the burst length dis t r ibut ion on the dropping probabil i ty. However, this approximat ion may be useful for dimensioning purposes. 4.5 Performance Analysis In this section, we compare the performance of P P J E T and P J E T in terms of dropping probabi l i ty and end-to-end ( E T E ) delay by means of s imulat ion. We restrict our analysis to two classes of service, namely, class 0 and class f. However, P P J E T and P J E T can both be generalized to more than two classes of service. In this discussion, class 1 corresponds to the high pr ior i ty traffic and class 0 corresponds to the best-effort traffic. Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 44 Sources Destinations Figure 4.2: S imula t ion network model for Section 4.5. 4.5.1 Ne two rk Setup The simulat ion is performed using a sophisticated discrete-event s imulat ion model based on O P N E T . The network topology used i n the s imulat ion is shown in Figure 4.2. The network consists of two types of O B S nodes, core O B S nodes and edge O B S nodes (ingress and egress). L i n k s shown as thick lines i n Figure 4.2 are W D M links capable of carrying five separate wavelengths, four for data and one for control. T h e transmission speed per wavelength is approximately 2.5 Gbps (OC-48) . L inks from traffic sources to ingress O B S devices and from egress O B S devices to the destination nodes are single wavelength l inks w i t h the same transmission speed. The burst assembly process is carried out using the C A T algori thm [41].The ma in advantage of the C A T algor i thm is that it regulates Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 45 the network traffic by producing bursts w i t h sizes that are approximately constant and equal to B m a x . Therefore, C A T enhances (i.e., reduces) burst dropping probabil i ty. A l l traffic sources used i n the s imulat ion are Poisson sources. Packet sizes are expo-nentially dis t r ibuted w i t h a mean equal to 1,024 bytes, and the mean packet inter-arrival t ime is varied to demonstrate the effect of network load. Sources are configured such that class 0 and class 1 shares of the total offered load are 2/3 and 1/3, respectively. We compare the performance of P P J E T and P J E T i n two cases. In the first case, we use the C A T algor i thm w i t h constant B m a x . In the second case, B m a x is varied from one burst to another according to an exponential d is t r ibut ion wi th a mean parameter, B m a x , that is changed from one s imulat ion scenario to another. T h e m a i n purpose of varying Bmax is to analyze the performance of P P J E T i n the presence of other burst assembly algorithms that may not behave as C A T . A n important parameter for evaluating the performance of P J E T is the ratio of the QoS-offset (tqos) to the mean burst size (Bmax). We cal l this ratio the isolation ratio. Th i s ratio determines the degree of isolation of class 1 traffic from traffic belonging to class 0. The higher the ratio the better the isolation between the two traffic classes. Previous research has shown that i n case of constant burst sizes it is sufficient to set the isolation ratio to 1 [80]. O n the other hand, i n case of exponentially dis t r ibuted burst sizes, class 1 is sufficiently isolated when the isolat ion ratio is equal to 5, and that any further increase to this ratio w i l l have m i n i m a l effect [80]. It is important to emphasize that P P J E T does not require extra offset t ime to achieve isolation, therefore, the isolat ion ratio is irrelevant Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 46 0.035 0.03 0 .025 TO 0.02 O _c & 0.015 Q 0.01 0 .005 —r— Q o S of fset /mean burst s ize=0.5 - Q o S of fset /mean burst size=1 a P P J E T A : & I * — , — - I ^ 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 1.05 1.1 Total Traff ic Load Figure 4.3: Compar i son between P P J E T and P J E T class 1 dropping probabil i t ies i n the case of constant burst sizes. to P P J E T . 4.5.2 Burst Dropping Probability W e perform two s imulat ion sets to compare class 1 dropping probabil i t ies (Pdrop,i) for P P J E T and P J E T as a function of the to ta l offered load. In the first set of simulations, we use a constant value for B m a x equal to 20,480 bytes. F igure 4.3 shows the results. T h e top two curves i n F igure 4.3 show Pdrop,i for P J E T when the isolat ion ratio is equal to 0.5 and 1. T h e bo t tom curve shows Pdrop,\ for P P J E T . In the second set of simulations, we use an exponential ly dis t r ibuted Bmax w i th mean Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 47 g.0.06 6 QoS offset/mean burst size=4 QoS offset/mean burst size=4.5 QoS offset/mean burst size=5 PPJET 0.03 '— 0.4 0.7 0.8 Total Traffic Load Figure 4.4: Compar i son between P P J E T and P J E T class 1 dropping probabil i t ies i n the case of exponential ly dis t r ibuted burst sizes. Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 48 value = 20,480 bytes. In addi t ion, we use three values for the P J E T isolat ion ratio: 4, 4.5, and 5. Figure 4.4 shows the result for this set of simulations. ft is obvious from Figure 4.3 and Figure 4.4 that P P J E T outperforms P J E T i n terms of dropping probabil i ty, especially i n the case of exponential ly dis t r ibuted burst sizes. Th i s can be explained by not ing that the offset method used i n the P J E T scheme for isolation is a statist ical method for providing priori ty. Stated otherwise: as the isolation ratio increases, the probability of b locking decreases. O n the other hand, P P J E T ' s method of guaranteeing prior i ty is determinist ic, since the P L A U C - V F a lgor i thm preempts lower pr ior i ty reservations. In Figure 4.5 we il lustrate the effect of Bmax on the dropping probabi l i ty of bo th P P -J E T and P J E T . We fix the isolat ion ratio for the P J E T scheme to 5. In this scenario, we use two values for Bmax: 20,480 bytes and 204,800 bytes. Results in F igure 4.5 demon-strate clearly that P P J E T performs better than P J E T , in terms of dropping probabil i ty, for smal l and large values of Bmax. fn addi t ion, it is apparent from the figure that P P J E T and P J E T provide better burst dropping probabi l i ty as the value of Bmax increases. 4.5.3 E T E delay fn our network model , a packet encounters four types of delays i n its pa th from source to destination: burst assembly delay (Da) i n the ingress O B S node, offset delay (D0), da ta burst t ransmission delay (Dt) and the queuing delay (Dq) at the output of the egress O B S node after the burst de-assembly process. Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 49 Figure 4.5: Effect of the mean burst size on class 1 dropping probabil i ty. Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 50 T h e offset delay D Q can be further d iv ided into two components, J E T offset t ime T0 and QoS offset tqos. The J E T offset time is constant for bo th P P J E T and P J E T , while QoS offset is equal to zero i n case of P P J E T . Note that the quanti ty D a is directly proport ional to B r n a x and inversely proport ional to the traffic load, while bo th D t and D q delay components are direct ly propor t ional to B m a x . In case of P J E T , D D is also direct ly proport ional to B m a x , while D a is constant i n P P J E T . Accordingly , the ma in difference i n E T E delay between P J E T and P P J E T is the QoS offset. In this subsection, the isolation ratio for P J E T is set to 5 for exponential ly dis t r ibuted B m a x , and is set to 1 for constant B m a x . Figure 4.6 compares the E T E delay for P P J E T and P J E T as a function of the tota l offered load. In this scenario, B m a x is exponentially dis tr ibuted, and we use two values for Bmax- 20480 bytes and 204800 bytes. Figure 4.6 shows that E T E delay decreases i n a l l cases as the traffic load increases. T h i s is due to the D a delay component that is inversely propor t ional to the traffic load. Furthermore, as B m a x increases the E T E delay increases due to the fact that D a , D t , and D q delay components are a l l propor t ional to B m a x . However, as explained earlier, the ma in advantage of P P J E T over P J E T w i t h respect to the E T E delay is in the e l iminat ion of the QoS offset which can be substantial ly large i n the case of large B m a x . T h i s fact is evident from the s imulat ion results in Figure 4.6, where the difference between the bo t tom two curves ( B m a x = 20480 bytes) for P P J E T and P J E T is substantial ly smaller than the difference between the two upper curves ( B m a x = 204800 bytes). F igure 4.7 shows similar results for constant B m a x . Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 51 \ B- — — ~"S „.._- -Q """"kx N ~ - " - i — —h-r-.--r1." ' ~ ~ — _ O - - •• - e - PJET and B = 20480 - e - PJET and B = 204800 PPJET and B = 20480 PPJET and B = 204800 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.E Total Traffic Load 0.9 1 1.1 Figure 4.6: Class 1 E T E delay comparison i n the case of exponential B„ Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 52 3.5 2.5 0.5 1 S - - 1 ~ e h-"~ - O - P J E T and B = 20480 — B - P J E T and B = 204800 - -k - P P J E T and B = 20480 l P P J E T and B = 204800 3 -£> ——... * i. .. . \ 3 —©•— 7 - G t —•• 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 Tota l Traffic L o a d Figure 4.7: Class 1 E T E delay comparison i n the case of constant B, Chapter 4. A Novel Priority Scheme for Supporting QoS in OBS Networks 53 4.6 Concluding Remarks In this chapter, we have presented a novel scheme for QoS provisioning in buffer-less O B S networks. T h i s scheme assigns different priorities to traffic classes and provides service to these classes based on strict pr ior i ty order. T h e proposed scheme achieves this goal by u t i l i z ing a new channel scheduling a lgor i thm called P L A U C - V F that allows for dropping reservations that belong to lower pr ior i ty traffic-classes i n order to fit new high pr ior i ty reservations. W e have presented several results on the performance of the proposed scheme for the case of two pr ior i ty levels. However, the scheme is general and can be used w i t h more than two service classes. W e have demonstrated that P P J E T achieves significant performance enhancements over P J E T i n terms of dropping probabi l i ty and E T E delay for h igh pr ior i ty traffic. 54 Chapter 5 A New Analytical Model for Computing Blocking Probability in OBS Networks 5.1 Introduction One of the m a i n performance measures in O B S networks is the b locking probabil i ty, which is the probabi l i ty that a wavelength reservation request w i l l not be granted due to the unavai labi l i ty of a free wavelength. To the best of our knowledge, most analyt ical models used for calculat ing the blocking probabi l i ty i n the J E T protocol are very simple to the degree of inadequacy. These models ignore impor tant factors that need to be considered when calculat ing the blocking probabil i ty, as w i l l be explained later in this chapter. T h e ma in objective of this chapter is to present a more elaborate analy t ica l model that captures the essential features of J E T - b a s e d O B S ( O B S - J E T ) networks, and gives stronger insight into factors that affect the b locking probabil i ty. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 55 In Section 5.2, we discuss key factors affecting the blocking probabi l i ty i n O B S - J E T networks and briefly describe previous models for calculat ing the b locking probabil i ty. We relate the problem of calculat ing the b locking probabi l i ty i n O B S - J E T networks to the problem of calculat ing the reservation probabi l i ty i n advance reservation systems in Section 5.3. We then propose a new analyt ical model i n Section 5.4. We validate the accuracy of the proposed model i n Section 5.5 by comparing i t to s imulat ion results and we conclude the chapter i n Section 5.6. 5.2 Blocking Probability T h e signaling protocol used in an O B S network is crucial i n determining the b locking probabi l i ty for data bursts i n that network. For the J I T protocol , the blocking probabi l i ty at a node can be calculated by model ing the output port as a M/G/k/k queue and using the well-known Er lang ' s B-formula for the loss probabi l i ty: Bp{p,k) = -P^- (5.1) i=0 In this equation, k is the number of wavelengths, and p is the offered load. For the J I T protocol the offered load is X(b + a), where A is the mean arr ival rate, a is the mean burst offset time, and b is the mean data burst length. T h i s formula is derived using the fact that each request blocks the channel for a t ime durat ion equal to the sum of the offset t ime and burst transmission delay. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 56 Erlang 's loss formula has also been used to approximate the b locking probabi l i ty for the J E T protocol by t reat ing the node's output l ink as a t radi t ional loss system w i t h an offered load of Xb [10] [71]. However, this approximat ion oversimplifies the problem by neglecting the effect of the offset t ime on the blocking probabil i ty. Moreover, if a void filling a lgor i thm is used i n conjunction w i t h the J E T protocol, the discrepancy between the approximat ion and the true blocking probabi l i ty w i l l become even larger. T h i s is due to the fact that Er lang ' s loss formula calculates the probabi l i ty that a channel w i l l be free on the arr ival of a burst, but i t does not consider if the channel remains free for the service durat ion (length) of the burst. Therefore, Er lang 's loss formula cannot be considered as a good approximat ion for the blocking probabi l i ty because i t fails to capture the effects of the offset t ime and the burst length. 5.3 Advance Reservation Systems T h e problem of calculat ing the blocking probability- i n O B S - J E T networks is s imilar to calculat ing the reservation probabili t ies i n classical advance reservation systems. A n advance reservation system can be defined as: • A system w i t h M servers. • A process of a r r iv ing requests to use the servers is given. • E a c h request is a pair of independent random variables: — an advance notice, A. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 57 — a service durat ion, B. • Loss protocol: A reservation is made if and only if, for its whole durat ion at least one of the set of M servers is free. Otherwise the reservation request is blocked. • The objective is a formula for the blocking or reservation probabili t ies. T h i s system appears i n many different applications, such as hotel reservations and videoconferencing systems. Several models exist in the literature for analyzing different reservation systems [22, 45, 46, .68]. However, each of these models has a set of s implifying assumptions that are applicable to their specific system of interest. Therefore, none of these models are direct ly applicable to the problem at hand. T h e ma in difficulty i n model ing the O B S - J E T systems, and any advance reservation systems i n general, is that a reservation request can be blocked by a reservation start-ing after its own start t ime. T h i s phenomenon of "retro-blocking" [45] becomes more significant as the advance notice dispersion becomes larger. One notable difference between O B S - J E T system and the advance reservation sys-tems, is the above mentioned loss protocol . In O B S - J E T , the reservation is accepted i f and only i f at least one wavelength is free at the s tar t ing t ime of the burst, and that part icular wavelength remains free for the dura t ion of the burst. Thus , i t is not sufficient to consider only the number of free wavelengths as i n the case of advance reservation systems, which further complicates the problem. The example of F igure 5.1 illustrates this difference, where a reservation request for a server arrives to a system of 4 servers. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 58 Reservat ion request t ime _ t ime time Figure 5.1: Example to i l lustrate the difference i n the loss protocol between advance reservation systems and O B S networks. T h e requested reservation is to start at t ime ta and lasts for a durat ion equal to (t e — ta). In classical advance reservation systems, this request w i l l be accepted because there is a free server at any t ime instant i n the t ime interval [ta, te]. In comparison, this reservation request w i l l be rejected (blocked) i n O B S - J E T systems, since there isn't any wavelength that is free on the start t ime of the reservation and remains free for the entire requested t ime interval. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 59 5.4 Proposed Model 5.4.1 Problem Description and Assumptions Assume that a C B requests a wavelength after a t ime units for a dura t ion equal to b t ime units. T h e request is accepted if at least one wavelength is free for a period of t ime equal to the request durat ion. Stated otherwise: i f tT is the C B arr ival t ime, then the request is granted if the request reservation interval [tr + a, tr + a + b] does not overlap w i t h an already reserved interval on at least one of the available wavelength channels. If there is no free interval, the C B and its corresponding D B are dropped. In order to make the model tractable, we simplify the problem by d iv id ing t ime into slots of w i d t h S. We assume that the offset a and the burst length b are integer mult iples of 6. T h e control burst arr ival process is assumed to constitute a Poisson process w i th a mean of A arrivals per t ime slot. The offset t ime A has a probabi l i ty d is t r ibut ion / ( a ) = P(A = a) for a = 0 ,1 , . . , and the data burst dura t ion B has the d is t r ibut ion gib) = P(B = b) for b = 1,2,... F igure 5.2 il lustrates the simplif ied O B S - J E T system. We assume that arrivals and departures occur at slot boundaries. Slots are numbered w i t h respect to the arr ival t ime slot of a reference C B . We use n to indicate the slot number. O u r model has s imilar assumptions as the model developed i n [45], which was developed for advance reservation systems. However, our model is significantly different from the model i n [45] because of the previously mentioned difference i n loss protocol between O B S - J E T systems and advance reservation systems. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 60 C B Control Channel A /Data Channels t a ...J i... D B time -time time time Figure 5.2: Simplif ied O B S - J E T model. 5.4.2 Traffic Model Assume we have a reference control burst a r r iv ing at certain t ime instant, and requesting to reserve a channel after n t ime slots from its arr ival t ime. W i t h o u t loss of generality, consider the arr ival t ime of the control burst to be slot 0, and start of the requested durat ion to be slot n. In order to calculate the blocking probabi l i ty of this request, we need to consider the number of arrivals at slot n seen at the t ime of the request. T h i s is because any reservation request that w i l l be generated i n the future (from t ime slots after slot 0) for slot n w i l l not affect the probabi l i ty of accept ing/blocking the reference reservation request. The number of data bursts whose start t ime is w i th in slot n , seen at the instant in Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 61 which the reference control burst arrives, is Poisson dis t r ibuted w i t h mean A, for n < 0 (5.2) n - l M l - £ / H I , f°r ™ > 0 a=0 T h i s equation can be justified as follows. The sum of the number of requests for t ime slot n from al l previous slots, inc luding slot n, is A. G i v e n a reference control burst a r r iv ing in t ime slot 0, the probabi l i ty that this C B w i l l request t ime slot n is f(n). Therefore, the number of requests from slot 0 to slot n is A / ( n ) . F r o m the point of view of the reference C B , the number of da ta burst arrivals i n slot n is the sum of requests from al l t ime slots before slot 0 i n addi t ion to requests from slot 0. Thus , the number of arrivals i n slot n seen by the reference C B , is the number of a l l possible requests (A) minus any future requests to be made i n t ime slots 1 to n for slot n. To further to i l lustrate Equa t ion 5.2, consider the following example. Assume that the offset t ime can have one of four values: 0, 1, 2, or 3, each w i t h a probabi l i ty of \ . Consider a reference control burst ar r iv ing at slot 0. T h e mean number of requests to slot 1, seen by the reference control burst, are the sum of requests in i t ia ted from slots -2, -1, and 0. Therefore the number of requests to slot 1 can be calculated as A{1 — | } = | A . In the same manner, the mean number of requests to slot 3, seen by the reference control burst, are the number of requests in i t ia ted from slot 0, and can be calculated as M i - i l + t + i}} = i A -Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 62 5.4.3 State Desc r i p t i on We use two M a r k o v chains to model our system. The first M a r k o v chain models the state of a single wavelength channel, and it is used to calculate the probabi l i ty that the wavelength channel w i l l be free for the durat ion of the data burst. W h i l e the second M a r k o v chain models the occupancy of an output l ink carrying mult iple da ta wavelength channels, and it is used to calculate the probabi l i ty that a wavelength channel w i l l be free upon the arr ival of the data burst. The m a i n idea behind our model is to calculate the t ransi t ional probabil i t ies w i th non-homogenous arrivals w i t h mean given by Equa t ion (5.2), while ignoring the retro-blocking phenomenon. Thereafter, we use the calculated t ransi t ional probabili t ies to express the blocking probabi l i ty tak ing into consideration the retro-blocking phenomenon. We assume that the data burst dura t ion has a geometric d is t r ibut ion g(b) = q(l — Q , ) f e _ 1 w i t h mean B and q = 1/B. Model for a single wavelength channel Let S^ represent the state of a wavelength i n t ime slot n. If the wavelength is occupied then = 1, otherwise S^ = 0. We assume that burst arrivals are uniformly dis-t r ibuted among wavelength channels on the output l ink. We denote arrivals to a single wavelength channel by A. Accordingly , A = A / M , where M is the number of wavelength channels on the output l ink. A wavelength channel can be modeled as a non-homogenous Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 63 M a r k o v chain w i th t ransi t ional probabi l i ty mat r ix Q^: Q(n) = («) («) 0^,0 Po,i 00 (n) Pl.O Pl.l T h e transi t ional probabil i t ies are defined as: (5.3) g - A ( n + 1 ) J = 0 l _ e - A ( « + D ; i = o, j? = 1 * = 1, j = 0 1 - qe~~x(n+1\ i = j = 1 (5.4) (5.5) M o d e l for o u t p u t l i n k Let denote the number of channels reserved on the output l ink i n slot n (Z^ = 0 , . . . , M) . T h e output l ink can be modeled as a non-homogenous M a r k o v chain w i th t ransi t ional probabi l i ty mat r ix X^: X ( n ) X -(«) 0^,0 (n) 1,0 X (n) C0,l (n) 1,1 ( » ) (") XM,0 XM,1 (n) 0,M r(n) 4.M (n) (5.6) Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 64 The transi t ional probabil i t ies are defined as: » y = p ( Z ( n + l ) = j | Z ( n ) = 0 j ().| V/ A („ + 1 ) A (n+i) (j- i+z)!> E ( : ) g 2 ( i - g ) i " z e z=0 J < M - 1 ,2 < j A f z=0 M - 1 i - E -A („+i ) _(zi±i l ) j<M-l,i>j j = M 2 = 0 T h e stationary probabil i t ies for Z ^ are given by n 7To 7Ti ... 7T M We obta in Tt by solving the following set of equations: M i=0 (5.7) (5. (5.9) (5.10) 5.4.4 Blocking Probability Calculation Let the probabi l i ty d is t r ibut ion of be 4n) = P { Z [ n ) = z ) , z = 0,1,...,M. A reservation request for a unit length da ta burst w i t h offset equal to a slots w i l l be blocked w i t h probabi l i ty v$. To calculate the b locking probabi l i ty for a reference data burst w i t h dura t ion b, we need to consider the state of the wavelength for a l l slots n = a,a + 1, ..,a + b — 1. W e can express the blocking probabi l i ty i n terms of the first-passage-time distr ibutions [42]. Le t Ts(a,b) be the probabi l i ty that, s tar t ing at state s Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks in t ime slot a, S^ remains i n state s for a durat ion equal to b t ime slots. Accordingly , the blocking probabi l i ty for a data burst w i t h offset a and dura t ion b can be wri t ten as: M - l BP{a,b) = l-%{a,b)YJv{:) (5-11) 2 = 0 W h a t Equa t ion (5.11) says is that the probabi l i ty the reservation request w i l l be accepted is equal to the probabi l i ty that at least one wavelength w i l l be free at the arr ival t ime of the data burst, and w i l l remain free for the durat ion of the data burst. T h e probabi l i ty can be calculated as i/W = nx(V 1 »...x('- 2 >^- 1 ) • (5.12) The symbol X^a~^ denotes the zth co lumn of the ma t r i x X ^ - 1 ) . E q u a t i o n 5.12 describes possible system evolut ion paths from being i n one of the in i t i a l states before slot 0 to the final state of having z wavelength channels occupied in slot a. T h e probabi l i ty that the wavelength w i l l be unused for the durat ion of the da ta burst can be expressed as: T o ( a , 6 ) = p 0 > ^ + 1 ) . . . p ^ - 2 ) (5.13) = g - ^ ( n + l ) g - ^ ( n + 2) _ g - A ( a + ( , - l ) (5.14) Equa t ion 5.13 describes the probabi l i ty that s tar t ing at state 0 i n slot a the channel w i l l remain i n state 0 for b slots. Note that pQ = P ( S ( ° + 1 ) = j | S ( a ) = i). If the offset Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 66 time has a uniform dis t r ibut ion i n [ 0 , ^ 4 m n J then Equa t ion (5.2) can be expressed as A(n) = \ for n < 0 (5.15) 0, for n > Amax Under the condi t ion that a + b — 1 < Amax, Equa t ion (5.14) can be rewri t ten using Equa t ion (5.15) as T 0 ( a , b) = g -A(6-l ) ( l - fc (a+6/2)) > w h e r e fc (5.16) T h e proof is as follows. Under the condi t ion that a + 6 — 1 < A n a s , E q u a t i o n (5.14) becomes a a-f-1 a + b —2 - A { l - E T Z - X } - i { l - E I T T } - A { 1 - £ T X T } lo(a,o) = e , = 0 e *=° . . . e 1 = 0 Let k 1 + A max T0(a,b) = e-^(1-fc(a+1))+(1-fc(a+2))+-+(1-fc(a+b-1))) - A E [ i - M « + i ) ] -A[(l-fea)(6-l)-fc(6-l)b/2] e -A(b-l)[l-fc(o+6/2)] n Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 67 5.5 Performance Evaluation In this section, we present several key results to i l lustrate the effect of offset-time and burst size parameters on the blocking probabi l i ty i n O B S - J E T networks. In addi t ion, we compare results obtained from the approximate model developed in the previous section w i t h results from a discrete-event s imulat ion model . Moreover, we compare our model results w i t h results obtained from Erlang 's loss formula. F ina l ly , we study the impact of the t ime slot size on the proposed model accuracy. Figure 5.3 shows the s imulat ion model used i n this section, which is based on the O P N E T s imulat ion tool . It consists of a single O B S node connected to traffic sources and a sink node. E a c h input l ink carries 2 separate wavelengths, one for data and one for control. T h e output l ink carries five wavelengths, four for da ta and one for control , and each wavelength channel has transmission speed of approximately 2.5 Gbps (OC-48) . We assume that sources generate control and data bursts. Sources generate bursts according to Poisson process and burst sizes are exponential ly dis t r ibuted w i t h mean B — 81920 bits. The offset time has a uniform dis t r ibut ion over [0, Amax\. T h e m a x i m u m offset t ime Amax was arbi t rary chosen to be 180 / i s . In each experiment we specify the chosen t ime slot size i n bits. T h e slot size i n seconds (5) can be calculated by d iv id ing the slot size expressed i n bits by the da ta channel bandwid th (2,377,728,000 bi ts /sec i n this example). The blocking probabi l i ty is calculated from the analyt ical model for offered load values ranging from O.f to 0.9. O n the other hand, the b locking probabi l i ty values obtained from the discrete-event s imulat ion correspond to offered load values ranging from 0.4 to Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 68 I S i c I Src 2 S r c n I W D M Figure 5.3: S imula t ion model for Section 5.5. 0.9. The smaller range is due to the fact that in order to get an accurate value for the blocking probabi l i ty from the discrete-event s imulat ion at low loads, the s imulat ion needs to be executed for prohibi t ively long times. The wavelength scheduling algori thm employed here is F i r s t F i t w i t h V o i d F i l l i n g ( F F -VF)[74] . T h e F F - V F a lgor i thm finds the first available data channel for each ar r iv ing da ta burst. G i v e n the arr ival t ime ta of a data burst w i t h durat ion b to the opt ical switch, the scheduler finds the first da ta channel that is available for the t ime period [ta, ta + b\. Figure 5.4 illustrates the F F - V F algori thm. A new burst arrives at t ime ta. A t t ime ta, wavelength 0 is ineligible because the void on this wavelength is too smal l to fit the new burst. T h e a lgor i thm chooses the first available wavelength channel, which is channel 1 i n this example. 5 . 5 . 1 Effect of Offset Time In this subsection, we s tudy the effect of the burst offset t ime on its b locking probabil i ty. T h e b locking probabi l i ty is calculated w i t h burst durat ion b — B and slot size = 20480 bits. F igure 5.5 shows the corresponding blocking probabi l i ty results. There are three Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 69 — | 1 * 4 -1 ! 1 t, I V ta ;.. time _ lime time time Figure 5.4: I l lustrat ion of the F F - V F algori thm sets of plots in Figure 5.5, each corresponds to a different offset t ime value. Each set consists of two plots, one corresponding to s imulat ion results and one corresponding to results obtained using the approximate analyt ica l model we developed in Section 5.4. Resul t sets 1, 2 and 3 correspond to offset t ime values a = 0.2Amax, a = 0.5Amax and a = Amax, respectively. F r o m the three sets, we observe that as the offset t ime value increases, the blocking probabi l i ty decreases (i.e., BP{():1.\,„„.,•) > /»'/ '(().5.-l , m i J .) > BP(Amax)) and approaches zero in the case of a = Amax. T h i s behavior is expected, since the further in the future the requested interval is, the less the number of requests for intervals i t w i l l intersect w i th . G i v e n a par t icular request for interval [ts, te], only those requests that have finishing times larger than ts can block this part icular request. T h i s fact has been exploi ted i n [80] to provide different levels of quality-of-service. T h e effectiveness and accuracy of our approximate analyt ical model is demonstrated Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 70 X X o J-I PL, 00 o o ffl 0.7 0.6 0.5 0.4 H 0.3 0.2 0.1 * Simul. with a = 0.2 A max a Approx. with a = 0.2 A max Simul. with a = 0.5 A max -e-, Approx. with a = 0.5 A max Simul. with a = A max _ Approx. with a = A max ( 1 ) ( 2 ) " , ± 4 . A - A — - - - • 4C- -( 3 ) L • - A - • ™.: 0.2 0.3 0.4 0.5 0.6 Total Traffic Load 0.7 0.8 0.9 Figure 5.5: Effect of the burst 's offset t ime on its b locking probabil i ty. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 71 by its satisfactory agreement w i t h the s imulat ion results i n Figure 5.5. The effect of the offset t ime on the blocking probabi l i ty in our model can be understood from E q u a t i o n (5.2). A s the value of a increases, the arr ival rate A( n ) decreases which , in turn , causes the b locking probabi l i ty to drop. In addi t ion, Equa t ion (5.16) shows the effect of the burst offset t ime on its b locking probabi l i ty i n the case of uniformly dis t r ibuted offset times. A s the value of a increases, the value of T0(a,b) increases and as a result, the b locking probabi l i ty decreases. 5.5.2 Effect of Burst Size In this subsection we study the effect of varying the burst size on the burst b locking probabil i ty. T h e blocking probabi l i ty is calculated w i t h offset t ime value a = 0.5Amax and slot size = 5f20 bits. We use two values for the burst size b i n this experiment: b^= 20480 bits (0.255) and b2= 122880 bits (1.5Z?). Figure 5.6 plots the resulting b locking probabi l i ty i n two sets of plots. Set 1 corre-sponds to using burst size equal to b\ and set 2 corresponds to using burst size equal to 62. It is clear from the figure that the blocking probabi l i ty value for b\ is less than its value for 62- T h i s is due to the fact that the value of b affects the probabi l i ty that the wavelength scheduler a lgori thm w i l l be successful i n finding a suitable t ime gap (void) on a wavelength to fit the incoming burst, intui t ively, the larger the burst size the lower the probabi l i ty of success. A s a result, the larger the value of b the larger the b locking probabil i ty. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 72 Simul. with b = 20480 . • -a• - Approx. with b = 20480 - 4 - Simul. with b= 122880 Approx. with b = 122880 ( 2 ) ' / •/ \ . / - ... " " U : J " •>•-•" ^ ; ( i ) )-—"'"" _ . - : 2-i 0.2 0.3 0.4 0.5 0.6 Total Traffic Load 0.7 0.8 0.9 Figure 5.6: Effect of the burst 's size on its b locking probabil i ty. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 73 A s i n the case of the previous subsection, the results plot ted i n Figure 5.6 exemplify the good agreement between our analyt ical model and s imulat ion results. The effect of the burst size can be understood from Equa t ion (5.14). Generally, the longer the burst the larger the number of probabi l i ty terms that get mul t ip l ied i n Equa t ion (5.14). Therefore, a larger value of b causes the probabi l i ty T0(a,b) to decrease which, i n turn , causes the blocking probabi l i ty BP(a, b) to increase. 5.5.3 Comparison with Erlang's Loss Formula In this subsection, we compare results obtained from Erlang 's loss formula (see Section 5.2) w i t h results from our proposed model . The blocking probabi l i ty is calculated w i t h the mean value for bo th the offset t ime and burst length (a = 0.5Amax, b = B.) and slot size = 20480 bits. Results from our model , s imulat ion, and Er lang 's B-formula are shown i n Figure 5.7. F igure 5.7 confirms that our model is much more accurate than Er lang ' s loss formula. In addi t ion, F igure 5.7 shows that the curve produced from our approximate model follows the same trend as the Er lang 's loss formula, thus providing strong evidence on the accuracy of our model . It is important to reemphasize that Er lang ' s loss formula does not consider the effect of either the offset t ime nor the burst length on the b locking probabil i ty, and only depends on the average load. Accordingly , changing the offset t ime value or the burst length w i l l not affect the results obtained from Erlang 's loss formula, as long as the offered load is the same. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 74 0.4 r 0.35 \ 0.3 [ 0.251 0- 0.2 h 0.15h 0.1 Approx. Model Simulation Erlang 0.05 / , / . '' / /<• , ? •> s J> V • ./ <-''/' / * " 0.1 0.2 0.3 0.4 0.5 0.6 Total Traffic Load 0.7 0.8 0.9 Figure 5.7: Compar i son between the proposed model and Er lang ' s loss formula. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 75 0.35 0.3 0.25 0.2 i 0.15 0.1 0.05 - x M = 64 - O - M = 32 — i — M = 16 - A - M = 8 —*- M = 4 ~ a - M = 2 o1— 0.1 0.2 0.3 0.4 0.5 0.6 Total Traffic Load 0.7 0.9 Figure 5.8: Effect of the number of wavelengths on the burst b locking b locking probabi l -ity. 5.5.4 Effect of the number of wave length channels We study i n this section the effect of the number of wavelength channels at the output l ink on the b locking probabil i ty. We assign different values for M (the number of wavelength channels): 2, 4, 8, 16, 32, and 64. T h e blocking probabi l i ty is calculated from the analyt ical model w i t h the mean value for the offset t ime (a = 0.5Amax), burst length b = 0.5B and slot size = 10240 bits. T h e offered load value is varied between 0.1 and 0.9 for every value of M. Results are shown i n F igure 5.8. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 76 Results in Figure 5.8 show that when M increases the value of the b locking probabi l i ty decreases. However, results also show that the effect of M on the b locking probabi l i ty decreases as M increases. In other words, increasing M beyond a certain value, M = 32 i n this case, have m i n i m a l effect on the blocking probabil i ty, and the offered load becomes the sole control l ing factor. It can be seen from the figure that the b locking probabi l i ty for the case of M = 64 is almost indist inguishable from the blocking probabi l i ty in the case of M = 32. It is impor tant to note here that the execution t ime of our analyt ical model increases as the number of wavelength channels increase. T h i s due to the fact that the size of the t ransi t ional probabi l i ty mat r ix X^n\ defined in Equa t ion 5.6, increases w i t h the number of wavelength channels. Therefore, the execution t ime of Equa t ion 5.12 increases w i t h M. To further i l lustrate the growth in the execution t ime of our model , Table 5.1 shows the execution t ime needed to calculate the results i n F igure 5.8. T h e table also shows the running t ime of the discrete-event s imulat ion for the case of M — 4. It is apparent from Table 5.1 that the execution t ime of the analyt ica l model increases significantly as M increases. Nevertheless, the execution t ime of the analy t ica l model is by far less than the execution t ime of the s imulat ion model . 5.5.5 Effect of t ime slot size T h e O B S - J E T network is not a t ime slotted network. However, our model assumes that t ime is slotted for simplici ty. Therefore, t ime slot t ing i n our model is an artifact of the Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 77 Table 5.1: Execu t ion t ime of the analyt ical model for different values of M M A n a l y t i c a l M o d e l S i m u l a t i o n 4 1 second 54 hours 16 ~ 15 minutes -32 ~ 2.6 hours -64 « 23 hours -model ing process. In this subsection, we study the impact of the slot size on the accuracy of our model and thereafter provide simple guidelines for the selection of the slot size. The blocking probabi l i ty is calculated w i t h the mean value for bo th the offset t ime and burst length. The offset t ime value used is a = 0.5Amax and the value of the burst size b is B. T h e values used for the slot size in bits are: 81920, 40960, 20480, 10240, 5120, and 4096 bits. T h e corresponding values expressed i n slots for the mean burst size, the burst offset value, and the m a x i m u m offset value are shown i n Table 5.2. T h e value of the offset t ime expressed i n slots can be calculated by d iv id ing its value (in seconds) by <5 (the slot size i n seconds). Results from our analyt ica l model are shown i n F igure 5.9. In Figure 5.9, the blocking probabi l i ty corresponding to slot size equal to 81920 is much lower from the rest of the curves and very far from the values obtained from the discrete-event s imulat ion of Subsection 5.5.3. T h i s observation can be explained by not ing that the burst size i n this case is 1 slot, which means that the effect of burst size is ignored. Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 78 Table 5.2: Slot size values and their corresponding mean burst sizes, offsets, and max offset values S l o t s ize B Offset v a l u e A 81920 1 3 5 40960 2 5 10 20480 4 10 20 10240 8 20 40 5120 16 40 80 4096 20 50 100 Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 79 •K Slot size = 4096 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Total Traffic Load Figure 5.9: Effect of slot size on the accuracy of the proposed model . Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 80 T h i s is evident from Equa t ion (5.16) where the value of To (a, b) becomes equal to 1 when the value of b is equal to 1. A s the slot size value decreases (i.e., value of b translates to a larger number of slots), the value of the blocking probabi l i ty becomes closer to values obtained from s imulat ion i n F igure 5.7. T h i s continues to be the case un t i l the value of b reaches 16 slots. A n y further decrease i n the slot size results i n identical b locking probabi l i ty values. Accordingly , our model produces accurate blocking probabi l i ty values when the slot size is chosen such that the value of b is larger than 4 slots and this applies for any value of b and B. 5.6 Concluding Remarks T h i s chapter presented an approximate analyt ica l model for calculat ing the blocking probabi l i ty i n O B S - J E T networks. The proposed model takes into account the effects of the offset t ime and burst dura t ion on the b locking probabili ty. To describe the data burst arr ival process we used a non-homogenous Poisson process whose mean value decreases w i t h the data burst arr ival t ime. Moreover, we expressed the b locking probabi l i ty i n terms of first passage t ime distr ibutions to account for the transient behavior of the wavelength channel for the dura t ion of the da ta burst. We verified the accuracy of the proposed model by compar ing it w i t h the results of a sophisticated discrete-event s imulat ion model . The model results were found to be i n very good agreement w i t h s imula t ion results, fn addi t ion to being accurate, our approximate model is orders of magnitude faster than the discrete-event s imulat ion: comput ing one point for the plots Chapter 5. A New Analytical Model for Computing Blocking Probability in OBS Networks 81 of Figures 5.5 to 5.7 take many hours of s imulat ion t ime, while i t takes about one second only for the same computa t ion using our model . 82 Chapter 6 Quantitative QoS Guarantees in Labeled O B S Networks 6.1 Introduction Labeled O p t i c a l Burs t Switching ( L O B S ) , proposed i n [58], is an integration of mul t i -protocol label switching ( M P L S ) [64], or its generalized version ( G M P L S ) [14], and opt ical burst switching ( O B S ) . M P L S is a forwarding technique that uses labels associated w i t h packets to make packet forwarding decisions i n network nodes. In M P L S , the entire set of possible packets are par t i t ioned into a set of Forwarding Equivalence Classes ( F E C s ) . A F E C is defined as a group of I P packets which are forwarded i n the same manner (e.g., over the same path, w i t h the same forwarding treatment). A number of approaches for QoS provisioning i n O B S networks have been proposed i n the li terature. These approaches can be classified into offset-based [81], strict pr ior i ty [77] [29], segmentation-based [70], or propor t ional QoS [5]. In offset-based mechanisms different burst loss probabil i t ies are obtained by assigning different offset values to different classes. T h e highest pr ior i ty class gets the largest offset Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 83 and thus is able to reserve resources ahead of other classes. T h e ma in disadvantage of this protocol is that it introduces a significant amount of delay for h igh pr ior i ty traffic. Str ict pr ior i ty schemes provide strict pr ior i ty for high pr ior i ty traffic class by dropping future reservations belonging to lower pr ior i ty traffic class. Therefore, a reservation request belonging to high pr ior i ty class can be only blocked by an exist ing reservation i n the same pr ior i ty level, or lower pr ior i ty reservation that has a start t ime i n the past (that is to say, the reserved durat ion has started already). Thus , dropping of high pr ior i ty traffic is min imized . However, this scheme is not flexible, since i t is not possible to control the bandwid th share or loss probabi l i ty for different service classes. Furthermore, i f the highest pr ior i ty traffic is misbehaving, the lower pr ior i ty traffic can starve. Burs ts i n segmentation-based mechanisms are composed of segments, each segment belonging to a certain pr ior i ty class. Content ion is resolved i n the core by dropping the lower pr ior i ty segments. Accordingly , the low pr ior i ty traffic w i l l get higher dropping probabi l i ty than the high pr ior i ty traffic. T h e drawback of this scheme is the increased complexi ty of burst assembly and scheduling. In proport ional QoS schemes, the burst loss probabi l i ty and average packet delay are adjusted to be propor t ional to the factors that the network service provider sets. A l t h o u g h this scheme is the most flexible scheme mentioned i n li terature, the propor t ional differentiation technique is not scalable as mentioned before in Section 4.1. The ma in goal of the aforementioned proposals is to provide relative service differen-t ia t ion wi th regards to packet loss probabil i ty. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 84 In this chapter, we describe a detailed architecture for provid ing quantitative QoS guarantees w i t h respect to end-to-end delay, throughput, and packet loss probabi l i ty i n buffer-less L O B S networks. The proposed architecture achieves its goal by deploying fair scheduling algorithms i n edge and core L O B S nodes. The use of fair scheduling algori thms i n the data plane of opt ical nodes has generally been avoided i n the literature. T h i s is due to the absence of the concept of "packet queues" i n opt ical nodes, beyond the number of packets that can be buffered (while in-flight) i n fiber delay lines. We w i l l present a novel approach for applying fair scheduling algorithms i n bo th the data plane of L O B S edge nodes and the control plane of core nodes wi thout the need for opt ical buffering, fn addi t ion, we present analyt ical expressions for the end-to-end delay and the b locking probabi l i ty i n the proposed architecture. T h e rest of this chapter is organized as follows. Section 6.2 introduces the proposed architecture and explains its components. We give a concrete example of how this ar-chitecture may provide QoS guarantees i n Section 6.3. fn Section 6.4, we evaluate the performance of the architecture through s imulat ion. Conc lud ing remarks are provided i n Section 6.5. 6.2 Proposed Architecture T h e proposed architecture is composed of a number of functional elements implemented i n network nodes, including packet classifier, burst assembler, s ignaling protocol, and traffic condi t ioning functions that include shaping and pol ic ing. We assume i n this architecture Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 85 that da ta bursts are assembled at the network ingress and delivered to the egress i n al l -opt ical domain. T h e network operator defines a set of F E C s i n the network, each wi th its own QoS parameters (e.g., bandwid th share, delay, and loss probabi l i ty) . Constraint-based rout ing and label d is t r ibut ion protocol are used to establish a path between ingress and egress nodes. In this section, we describe the edge node architecture, the employed signaling protocol , and the core node architecture. 6.2.1 OBS Edge node The functional blocks of an O B S edge node are i l lustrated i n Figure 6.1. Packets ar r iv ing at the ingress node are classified into one of the F E C s already defined by the network op-erator. These packets are then shaped and policed to conform w i t h the QoS requirements of their F E C . Packets are then assembled into bursts in the burst assembly queue. T h e burst assembly process is carried out using the CAT a lgori thm [41]. Thereafter, da ta bursts are inserted into the bursts queue and scheduled for processing by the reservation manager according to their QoS requirements. We propose the use of Fair Packet Queueing ( F P Q ) [65] algori thms for scheduling the processing of data bursts by the reservation manager. T h e F P Q scheduling discipline has three desirable properties: (a) it can guarantee an upper bound on delay to token-bucket constrained sessions; (b) it guarantees the upper bound on delay regardless of the behavior of other sessions (isolation); (c) i t can ensure relative fairness i n bandwid th al locat ion Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 86 Wavelength Reservation Optical Domain Ingress I/P 0 Electrical Network Ingress I/P n Figure 6.1: Funct ional blocks of an O B S edge node. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 87 among backlogged sessions. T h e part icular choice of the scheduler is not imposed by the architecture. Several F P Q algori thms have been proposed in the li terature, inc luding Weighted Fair Queueing ( W F Q ) [8], Self-Clocked Fair Queueing ( S C F Q ) [19], and Start-time Fair Queueing (SFQ) [21]. fn our O B S architecture, the F P Q scheduler is used to select, from the bursts queue, the data burst eligible for processing by the wavelength reservation manager, fn this context, there is a significant difference between the proposed implementat ion of the F P Q scheduler i n O B S edge nodes and its usage as a conventional packet scheduler. In the latter case, the packet selected by the F P Q scheduler is direct ly sent for transmission, whereas in our architecture the F P Q scheduler regulates the access to the reservation manager. Th i s difference appears more clearly when calcula t ing the queuing delay i n the burst queue, since the processing delay i n the reservation manager is independent of the burst 's length. T h e switch control uni t ( S C U ) invokes a wavelength reservation manager to decide on which outgoing data channel to forward the da ta burst. T h e p r imary job of the wavelength reservation manager is to process wavelength reservation requests and to keep track of the avai labi l i ty of free t ime intervals (voids) on every data wavelength channel on the l ink . T h e reservation manager exploits a wavelength scheduling a lgor i thm which can be any of the algorithms mentioned i n Chapter 3. T h e wavelength scheduling a lgor i thm tries to find a vo id on any of the output wavelengths, such that the void starts after the offset t ime and has a dura t ion equal to the D B transmission t ime. If the reservation is Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 88 successful, a control burst is generated. The generated C B is updated w i t h the F E C label and the reserved wavelength, then i t is sent out into the network. If the reservation fails, the D B is dropped. 6.2.2 Signaling Protocol We adopted the J E T protocol as the C B signaling protocol i n our architecture w i t h minor modificat ion. Basical ly, the destination field is replaced w i t h the M P L S label field. T h e label is assigned to the control burst at creation t ime according to the da ta burst 's F E C . In addi t ion to imp l i c i t l y point ing to the QoS information for the burst, the label simplifies the forwarding operation of the control burst by encoding the route of the burst, and thus specifying the output port i n intermediate nodes. 6.2.3 OBS Core node Figure 6.2 depicts the functional architecture of the O B S core node. A separate queue is established for each of the configured F E C s . W h e n a C B arrives at a core node, i t gets t ime-stamped w i t h its arr ival t ime, then classified based on its label and inserted i n the corresponding queue. In our architecture, we use a F P Q scheduling discipline to select the C B to be processed by the reservation manager. T h e fashion i n wh ich the F P Q scheduler is used here has two major differences from how it is used i n the O B S edge node or i n electronic packet networks. F i rs t , the actual data bursts are absent from the core node at the t ime of scheduling, therefore, they are scheduled through the processing Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 89 Control WL(s) cq d 03 O d3 SCU Control Bursts Scheduler F E C 0 Con t ro l Burs t Queue FEC I Control Burst Queue F E C 2 Con t ro l Burs t Queue F E C n Control Burs t Queue Wave leng th Reservat ion Manage r GO m O Control WL(s) Figure 6.2: Funct ional blocks of an O B S core node. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 90 a. Actual control burst queue b. Corresponding virtual data burst queue (constant length bursts) (variable length bursts) Figure 6.3: I l lustrat ion of the v i r tua l queue concept. of the "representative" control bursts. Second, the length used in calculat ing the eligible control burst is not the control burst length, rather, i t is the data burst length which is specified i n the control burst. Th i s implies that the scheduler is working on a "v i r tua l" queue structure of data bursts. T h i s concept is i l lustrated i n Figure 6.3. The actual control burst queue, shown i n Figure 6.3a, contains control bursts which have constant size. Us ing the data burst length field i n the control bursts, the F P Q scheduler creates a v i r t ua l queue for variable-sized data bursts, as shown i n Figure 6.3b, and uses this v i r t ua l queue to select the eligible control burst. Once a C B is selected i t w i l l be processed by the reservation manager which functions i n the same manner as the reservation manager i n the O B S edge node described earlier. T h e offset time field (T D ) contained i n the C B is then updated, based on the C B arr ival t ime-stamp, and label swapping is performed if necessary. T h e S C U keeps track of reservations on a l l wavelengths on a l l ports. W h e n the arrival t ime of a data burst is reached, the switching fabric is configured so that the data burst is switched transparently on its reserved wavelength. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 91 6.3 QoS guarantees In this section, we describe how the proposed architecture provides guarantees for band-wid th , end-to-end delay, and loss probabil i ty. The upper bound on the delay i n our architecture depends on the par t icular choice of the F P Q algori thm, since each F P Q has its own worst-case delay bound. To i l lustrate how the upper bound on the delay can be derived, we choose the well known Weighted-Fair-Queuing ( W F Q ) a lgor i thm for scheduling data bursts i n ingress nodes and for scheduling control bursts i n core nodes. We start by giving a brief review of W F Q calculations, then explain how W F Q can be adapted to O B S networks. 6.3.1 We igh ted Fa i r Queue ing W F Q belongs to the General ized Processor Shar ing ( G P S ) scheduling family [8]. In this a lgor i thm, each packet a r r iv ing to the output port is s tamped w i t h a finish t ime according to the following formula where is the finish t ime of the kth packet of the ith session, L\ is the packet length, a\ is its arr ival t ime, and is the reserved rate for session i. V(t) is the v i r tua l t ime function representing the progression of v i r tua l t ime i n G P S . Packets are then serviced i n the increasing order of their finish times. In W F Q , the worst case delay bound for session i that is constrained by a token bucket max{Flk-\V(a^} + L) (6-1) Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 92 w i t h parameters ( C T J , ^ ) [7] is 7 Lynax 0~i ~f~ Lrnax . . d-maxA ~ I 1,0.Z) r Ti where r is the output l ink capacity, CTJ is the token bucket depth for session i, and Vi is the token bucket rate for session i. W F Q is claimed to have high computa t ional complexity, which can be an issue for O B S nodes that are required to process control bursts at h igh speed. However, there are a number of W F Q variants that are computa t ional ly more efficient than W F Q (e.g., S C F Q and S F Q ) . It is important to reemphasize that the part icular choice of the scheduler is not enforced by our architecture, and any F P Q algor i thm can be used. 6.3.2 Bandwidth Guarantees E a c h of the configured F E C s has a weight (</>;) associated w i t h i t . T h i s weight represents its required share of bandwid th . Us ing W F Q , or any F P Q algori thm, and having a separate queue for each F E C , the number of wavelength reservation requests generated from a F E C w i l l be propor t ional to i t 's weight, and this applies bo th to ingress and core nodes. Accordingly , the rate (r;) received by F E C i at an output l ink is n = (1 - bp^r, (6.3) <P where bpi is the b locking probabi l i ty of F E C i at the output l ink, <f> is the sum of a l l backlogged F E C s ' weights at the output l ink, and r is the output l ink capacity. Admis s ion control po l icy need to be applied to insure that the sum of rates of a l l flows belonging to Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 93 a certain F E C does not exceed its reserved bandwid th share. If it exceeds its bandwid th share, only the misbehaving F E C w i l l be affected due to the isolation property of the F P Q algorithms. 6.3.3 Delay guarantees In our architecture, the tota l delay that a packet, belonging to F E C i, encounters in its pa th from ingress to egress is composed of six components: burst assembly delay (dati) i n ingress O B S node, queueing delay i n ingress node before being processed by the reservation manager (dqf), burst offset t ime (T0ii), packet transmission delay (dt,i), l ight propagation delay (d;^) and the queuing delay at the output of the egress O B S after the burst de-assembly process (de^). Thus the to ta l delay (Di) for packets belonging to F E C i is A = da<i + dgti + T0:i + dt-i + diti + de>l. (6.4) Note that the propagation delay di^ depends only on the to ta l l ight pa th length, while T0ti is proport ional to the number of O B S core nodes on that path . Therefore, d^i and TQ:i are uncontrollable quantities i n our architecture. In the following, we derive expressions for each of the delay components. The packet arr ival process to F E C i is assumed to be Poisson process w i t h mean value Aj packets/sec, and the packet size is assumed to have an average length of L bits . T h e average burst assembly delay can then be calculated as follows: Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 94 d, 1 N i 1 k=i (6.5) (6.6) (6.7) where dk is the assembly delay for packet number k i n the assembly queue, and N is the average number of packets i n a data burst belonging to F E C i. T h e variable N can have one of two possible values depending on the arr ival rate Aj, the F E C ' s m a x i m u m burst size (BmaXii) and the F E C ' s burst assembly t imeout (Tmaxi). In order to calculate the value of Ni we need to consider two possibilit ies: one is that TmaX:i is reached first, and the other is that B m a X t i is reached first, ff the t imeout is reached first, then Ni = \Tmax^. ff the m a x i m u m burst size is reached first, then N = [ m £ x - ' j . Thus , Equa t ion 6.5 can be rewrit ten as: ft is clear from Equa t ion 6.8 that da<i is direct ly propor t ional to BmaXti, the m a x i m u m burst size i n the C A T algori thm, and inversely propor t ional to the traffic load. T h e m a x i m u m burst queueing delay dq can be derived by mapping E q u a t i o n 6.2 to our specific problem. Reca l l from the discussion i n Subsection 6.2.1 that the da ta burst scheduler regulates the access to the reservation manager (not the output l i nk ) . Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 95 Therefore, the processing delay per D B is constant (we call it tdb) and does not depend on the D B length. T h e first term i n Equa t ion 6.2 models the s i tuat ion where a packet arrives at a busy scheduler and may have to wait up to ^f 3 - t ime before it is served. T h i s corresponds to the processing delay tdb i n our problem. T h e second term Gijri reflects the m a x i m u m delay for a burst of packets of length o%. It can be seen that this term can be substi tuted in our case w i t h ^ff, where Ni is the m a x i m u m number of data bursts ar r iv ing to the bursts queue of F E C i , and <fi is the sum of a l l backlogged F E C s ' weights. S imi la r ly the th i rd term can be mapped to - |^ r . Thus , the worst case m a x i m u m queueing delay for F E C i is , , . <f>Nitdb <ptdb dq,i = tdb-\ 1——. (6.9) <Pi <Pi The value of N can be calculated from the token bucket depth of F E C i as follows. r 1 i f tT-t ^ ^ m a x i ) (6.10) T h i s equation can be explained by looking at Figure 6.4. In F igure 6.4a, where <7; < Bmax,i, after the arr ival of a* bits to F E C i queue, the burst assembler has to wait extra t ime t — • B m a x ' i ~ t 7 ' un t i l the m a x i m u m burst size is reached, and thereafter one data burst is generated. W h i l e i n Figure 6.4b, on the arr ival of o~i bits, a number of bursts equal to [ B a i j w i l l be assembled. Hence Equa t ion 6.9 becomes dq,i=tdb+ —: h —— - (6.11) Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 96 arrival curve wi th slope r total bits arriva I curve with t slope r total bits Assembled B Bursts a A s s e m b l e d Bursts 111 QX\ time time a. B > a max b. B < a mux Figure 6.4: Burs ts arrivals to the burst queue depends on the values of a and B m a x . Accord ing to the above analysis, bounding the delay for traffic belonging to a F E C depends on shaping the input traffic so that a l l traffic flows belonging to that F E C conform to a token bucket w i t h parameters (ax,rx), where J 2 r x does not exceed the total F E C bandwidth reservation, and the ratio does not cause data burst queuing to be unacceptabil i ty large. The average burst queueing delay is approximately half the m a x i m u m value. The average queuing delay at the output of the egress O B S after the burst de-assembly process (ii e,t) can be calculated i n a manner s imilar to that of d 0 j j , however, we need to consider that mul t ip le bursts could arrive to the output queue in the same time. Therefore, dBti can be calculated as Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 97 1 M d ^ - M E I ^ - 1 ) (6-12) 2 fc=i dti .NAM + 1) , . „. = Jf{^—2 - - 1 } (6-13) dt,i I I fimai,i | ( M + l ) _ 1 \ \ ~> 1 BmaXij 2 V L L -I 2 - V ' A * — T m a x i L (6-14) i ( M + l ) 1\ 1 , 1 B m . t . i 2 V 2 J - J j ^ i ^ T - . r where M is the m a x i m u m number of bursts a r r iv ing to the same output queue at the egress node, which is equal to [Bai J- T h e packet transmission delay dt>i is equal to ^ , where C is the wavelength channel speed. T h e worst case value of de<i is given by dt,(M[^pi\ - 1). 6.3.4 B u r s t Loss P r o b a b i l i t y T w o factors control burst loss probabi l i ty for a F E C i n our architecture: conformance of the F E C traffic to the negotiated bandwid th share and B m a x for that F E C . Consider the case where a l l F E C s have the same value for B m a x , i f a l l F E C s traffic are well behaving, then a l l F E C s w i l l have the same loss probabi l i ty value and that value w i l l be a function of network u t i l i za t ion only. Assuming there is no pol ic ing at ingress, i f a F E C is sending traffic more than its reserved share, then that F E C ' s control bursts w i l l be queued for a longer t ime because of the isolat ion property of the scheduler, ff a control burst get queued for a t ime per iod longer than it 's remaining offset t ime value, then it w i l l be dropped w i t h i t ' s corresponding data burst. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 98 T h e value of Bmax affects the probabi l i ty that the reservation manager w i l l be suc-cessful i n finding a suitable t ime gap (void) on a wavelength to fit the incoming burst, in tui t ively , the larger the burst size, the lower the probabi l i ty of success. W e have pre-sented i n Chapter 5 an analy t ica l expression for calculat ing the burst b locking probabi l i ty at the output por t of an O B S node in terms of the burst 's length, offset t ime value and the total offered load. We have shown that for a given offset time value and traffic load, the blocking probabi l i ty increases as the value of B m a x increases, which confirms our in tu i t ion . If a par t icular F E C traffic conforms to the its negotiated -bandwidth share, then the blocking probabi l i ty for data bursts belonging to that F E C can be approximated as follows. Let the b locking probabi l i ty for a da ta burst w i t h length b, offset t ime T and ar r iv ing at node n be BP(b, pn,T), where pn is the offered load at node n. BP(b, pn,T) is the b locking probabi l i ty at a single O B S node, and can be calculated using the model given i n Chapter 5. The b locking probabi l i ty for a data burst w i t h offset t ime T and dura t ion b can be wr i t ten as: w-i BP(b,Pn,T) = 1 - S0(T,b,Pn) ^T)(pn) (6.15) here, v\ (pn) is the probabi l i ty that wavelength z w i l l be free at the arr ival t ime of the data burst, So(T, b, pn) is the probabi l i ty that the wavelength w i l l be unused for the dura t ion of the da ta burst, and W is the number of wavelength channels on the output l ink. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 99 Assume that the control burst traverses h nodes and that the offset-time is decre-mented at each node by an amount equal to a, the total b locking probabi l i ty BPtot can be expressed as BPtot = 1 - ((1 - BP(b, p i , T ) ) ( l - BP(b,p2,T- a)) ...(l-BP(b,Ph,T-(h-l)a))) (6.16) T h i s equation serves as an approximat ion of the b locking probabi l i ty for a part icular F E C , if that, F E C traffic conforms to its negotiated bandwid th share. T h i s is true even i n the existence of a non-conforming traffic belonging to other F E C s . Results from this equation w i l l be compared to s imulat ion results i n the following section. 6.4 Performance Evaluation In this section, we use results from extensive s imulat ion to demonstrate the performance of the proposed architecture i n terms of bandwid th guarantees to each traffic class, as well as loss probabi l i ty and end-to-end delay. T h e s imulat ion is performed using a so-phist icated discrete-event s imulat ion model based on O P N E T . T h e network topology used i n the s imulat ion is shown i n F igure 6.5. T h e network consists of bo th edge and core O B S nodes. Internal l inks i n the network model are wavelength-division-mult iplexing ( W D M ) l inks capable of car ry ing five separate wave-lengths. The transmission speed per wavelength is approximately equal to 2.5 Gbps Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 100 Figure 6.5: S imula t ion network topology for Section 6.4. (OC-48) . One of the wavelengths is used for control, while the remaining are used for data. L i n k s from sources to ingress O B S devices and from egress O B S devices to the desti-nat ion nodes (sinks i n Figure 6.5) are single wavelength l inks w i t h the same transmission speed. A l l traffic sources used are Poisson sources. T h e mean packet inter-arrival t ime is varied i n order to s tudy the effect of the network load. The packet size has exponential d is t r ibut ion w i t h a mean equal to 1024 bits. Furthermore, we set the m a x i m u m burst size Bmax to 20480 bits. We define three traffic classes, or F E C s , i n the s imulat ion network, namely, F E C 0, F E C 1, and F E C 2. We assign F E C 2 a weight of 3, F E C 1 a weight of 2, and F E C 0 a weight of 1. In addi t ion, we use W F Q as the D B scheduler i n the ingress and as the C B scheduler i n core nodes. T h e wavelength scheduling a lgor i thm used here is the L A U C - V F algori thm. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 101 6.4.1 Delay Guarantees F r o m the delay components explained i n Section 6.3, only three components are F E C -dependent, namely, burst assembly delay (da), burst queueing delay i n ingress node (dq), and de-assembly delay (de). Since the value of Bmax here is constant for a l l F E C s , the value of da is only dependent on the arr ival rate, and the value of de is equal for a l l F E C s . O n the other hand, the value of dq is dependent only on the F E C weight. T w o simulat ion experiments were performed. In the first experiment, a l l traffic sources conform to the contracted rate and to ta l offered load is equal to unity, while i n the second experiment traffic belonging to F E C 0 exceed its share. Results for the first experiment are shown i n Figure 6.6. Results i n Figure 6.6 confirm that the proposed architecture provides delay differentiation according to the F E C weight. Table 6.1 compares the average and m a x i m u m delay values i n F igure 6.6 against average and worst case delay values calculated using the analysis i n Section 6.3. It can be seen from the table that the average delay values from s imulat ion match those calculated using equations of Subsection 6.3.3. O n the other hand, there is a large discrepancy between s imulat ion and analysis when it comes to the worst case delay values. T h i s is expected since the worst-case delay values are intended to serve as an upper bound on the delay, and are generally hard to produce using s imulat ion. Figure 6.7 i l lustrate that when F E C 0 sends at a higher rate than the reserved rate, the end-to-end delay for F E C 0 increases significantly. T h i s increase is solely due to the dq delay component. In addi t ion, bo th F E C 1 and F E C 2 are unaffected by the overload Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 102 A v e r a g e D e l a y W o r s t C a s e D e l a y A n a l y s i s S i m u l a t i o n A n a l y s i s S i m u l a t i o n F E C 0 3.7E-05 3.6E-05 6.2E-05 3.7E-05 F E C 1 2.8E-05 2.8E-05 4.3E-05 2.9E-05 F E C 2 2.5E-05 2.5E-05 3.6E-05 2.60E-05 Table 6.1: Compar ison of average and worst-case delay values between analysis and s im-ulat ion. s i tuat ion. Th i s clearly shows the power of the architecture i n terms of traffic isolat ion and delay control. 6.4.2 Loss Probability In this subsection, we compare the loss probabi l i ty of the configured F E C s i n two si tu-ations: when al l sources conforming to the reserved rate and when the sources of F E C 0 send more than the configured rate. The loss probabi l i ty is calculated as the ratio of bits lost to bits sent. For the first s i tuation, we vary the offered load of each of the configured F E C s i n propor t ional to their bandwid th share, while keeping the to ta l network u t i l i za t ion below the value of one. Results shown i n Figure 6.8 i l lustrate a sample pa th of the loss probabi l -ity, and the corresponding values calculated from the analysis provided i n Section 6.3.4 (Equat ions 6.15 and 6.16). A s shown, the loss probabili t ies for a l l F E C s are approxi-mate ly equal to each other w i t h a value that is a function of the to ta l offered load only. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 103 x 10" 3.6 ou3.4 3, >» m a> •D3.2 T3 C HI •a c UJ 2.8 ft 4^t * *- 'K :/\ •* * * 4 * 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 Time (sec) Figure 6.6: End- to-end delay i n the case of conforming traffic flows. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 104 Figure 6.7: End- to-end delay when F E C 0 is non-conforming. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 105 0.25 0' -I r / / FEC 2 FEC 1 > FECO = Analysis / S i y""" 'V y "1'^--*'''^..--''"' ft'" 1 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Offered Load Figure 6.8: I l lustrat ion of a sample pa th of the loss probabil i ty. In addi t ion, Figure 6.8 shows that values obtained from our analysis can be considered a reasonably close approximat ion to the b locking probabi l i ty derived from our model . In the second experiment, we vary the offered load of F E C 0 beyond its reserved bandwid th share. Figure 6.9 shows the result ing loss probabil i ty. W h i l e F E C s 1 and 2 keep the same value of loss probabi l i ty as in Figure 6.8, the loss probabi l i ty of F E C 0 is increased significantly. Th i s due to the number of bursts sent exceeding the reserved rate, which causes the corresponding control bursts to suffer longer queueing delay i n the core nodes, wh ich i n tu rn causes them to miss the arr ival t ime of their associated da ta bursts and, consequently, bo th get dropped. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 106 Figure 6.9: H i g h loss probabi l i ty for F E C 0 (non-conforming). Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 107 6.4.3 B a n d w i d t h guarantees In this subsection, we perform two experiments to study the performance of the proposed architecture in terms of bandwidth guarantees. In the first experiment sources are con-figured such that the network u t i l iza t ion is equal to unity. Moreover, traffic is shaped at the ingress to conform to the reserved bandwid th share of each F E C . Figure 6.10 shows that the throughput for the three configured F E C s is propor t ional to their configured bandwid th share. Moreover, it can be seen from Figure 6.8 and Figure 6.10 that the throughput for each F E C and the to ta l throughput is i n conformance wi th Equa t ion 6.3. In the second experiment, traffic belonging to F E C s 1 and 2 conforms to their negotiated bandwid th share, while sources for F E C 0 send more than the contracted share such that the network u t i l i za t ion exceeds unity. It can be seen from Figure 6.11 that the three F E C s get their contracted bandwidth share only. Results in this section verify that the proposed architecture is capable of providing the contracted bandwid th share, even i n the presence of misbehaving sources, due to the fairness and isolation properties of the scheduler used. 6.5 Concluding Remarks This chapter introduced a new service differentiation architecture w i t h a powerful control-plane scheduling mechanisms for delivering concrete QoS guarantees i n L O B S networks. Service differentiation is achieved by a combined use of a burst assembly a lgor i thm and a Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 108 4.5 4 x 10 '(*..a. jsmttfrrnnr..trrrr. tamit-M-VM-U-*-• m:..i.af.*..#'....UAi. If) a 3[ 3 Q. -C 3 O FEC 2 FEC 1 FEC 0 2.5 _ 2-1.5 F 4' -f 4 vi 0 0.01 0.02 0.03 Time (sec) 0.04 0.05 Figure 6.10: Throughput for conforming traffic. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 109 4.5 4 —3.5 o CD </> £ 3 3 2 5 § 2 x 10 i J / * ! ** ~ i A J + t / V f : ft* , A " f f " ""CP' ' -4-1 • - * F E C 2 FEC 1 - FEC 0 V 0.01 0.02 0.03 Time (sec) 0.04 0.05 Figure 6.11: Throughput w i t h F E C 0 non-conforming. Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 110 fair queueing scheduler. The burst assembly a lgor i thm controls the b locking probabi l i ty and assembly delay using two parameters: the m a x i m u m burst size and the assembly t imeout. A F P Q scheduler is used i n edge nodes to regulate the access to a wavelength reservation algori thm, fn addi t ion, the chapter proposed a novel use of F P Q algorithms i n core O B S nodes to provide fair bandwid th al locat ion. We used the W F Q algor i thm as an example to show how the end-to-end delay can be derived. We presented analyt-ica l results for the end to end delay and the b locking probabi l i ty i n our architecture. S imula t ion experiments were conducted to verify the performance of the proposed archi-tecture. Results i l lustrated that the proposed architecture is able to flexibly support a wide range of service guarantees w i t h regards to throughput , end-to-end delay and packet loss probabil i ty. I l l Chapter 7 Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 7.1 Introduction In this chapter, we propose a novel class of wavelength schedulers. T h e proposed sched-ulers process a batch of bursts together instead of processing them one by one as i n the case of previously proposed algorithms. The rest of this chapter is organized as follows. We introduce the batch scheduling class of schedulers i n Section 7.2. Section 7.3 describes the op t ima l batch scheduler. In Section 7.4, we introduce four new heuristic batch scheduling algori thms. T h e proposed algorithms are evaluated i n Section 7.5 using a discrete event s imula t ion model . We conclude the chapter i n Section 7.6. Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 112 c: Control Burst Wavelength Queue Scheduler FIFO Figure 7.1: Con t ro l burst scheduling using greedy algorithms. 7.2 Batch Scheduling Wavelength schedulers previously proposed i n the li terature are considered to be greedy algorithms. T h e y are greedy i n the sense that they consider every request ind iv idua l ly and make the choice that looks best at the moment. Therefore, i f the request can be accepted (unblocked), it w i l l be indeed accepted. W h e n a C B arrive to an O B S node employing a greedy wavelength scheduling algori thm, i t is inserted into a F I F O queue. W h e n the wavelength scheduler is free, it dequeues the first packet on the queue and processes i t . Figure 7.1 describes this process. In this work, we pose the following question: W h a t if we defer the acceptance of some unblocked requests un t i l we see more requests? T h e in tu i t ion behind this question is that it may be advisable to reject an in i t i a l ly unblocked request i f later requests w i l l make better use of wavelength channels. To further i l lustrate the idea. Let the acceptance delay be d. Consider the case of d — oo. fn this case the system w i l l wait un t i l a l l reservation requests have been received, then it w i l l select requests that w i l l maximize the u t i l iza t ion . Obvious ly the case of d = oo is impract ica l . O u r proposal is to use an acceptable value of ri, such that we schedule a batch of reservation requests together, instead of using d = 0 as i n the case of Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 113 CBs Control Burst Batch Queue Queue FIFO Wavelength Scheduler ^ Figure 7.2: Con t ro l burst scheduling w i t h batch queue, greedy algorithms. To implement the above concept, we modify the burst scheduling process by inserting a queue before the wavelength scheduler and after the control burst queue, we cal l i t the batch queue, as shown in Figure 7.2. W h e n a control burst arrives to an O B S node, it gets inserted into the control burst queue. W h e n the wavelength scheduler becomes free, it w i l l wait for a smal l amount of delay, v iz . the acceptance delay d, then it moves a l l bursts that are i n the control burst queue to the batch queue, then processes a l l the C B s i n the batch queue together instead of the previously used greedy approach. T h e benefit of the batch queue, as w i l l be seen later, is to l imi t the delay that a control burst can incur dur ing the batch processing. 7.2.1 Definitions A graph G = (V, E) consists of a finite set V of elements called vertices, and a set E of pairs of vertices called edges. Le t V(G) represent the vertex set of G, and E(G) represent the edge set of G. We cal l adj(v) the adjacency set of vertex v, and we cal l the pair (v, w) an edge. Clear ly (v, w) G E if and only i f w 6 adj(v). Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 114 A subgraph H of G, denoted H C G, is a graph w i t h V(H) C V(G) and E(H) C E(G). T h e degree of v i n the subgraph H for any v 6 V(H), denoted deg(v\H), is the number of vertices of H adjacent to v, i.e., deg(v\H) — \adj(v\H)\. A n undirected graph G is called an interval graph if its vertices can be put into one-to-one correspondence wi th a set of intervals on the real line, such that two vertices are connected by an edge of G if and only if their corresponding intervals have nonempty intersection (have a common point) , fn other words, G is an interval graph provided that one can assign to each v £ V(G) an interval Iv such that Iu D /„ is nonempty if and only i f (u,v) G E. A n interval is defined by two points: left point (start of the interval) and right point (end of the interval). Le t 1(1) and r(I) correspond to the left and right points of interval I respectively. Intervals Iv and / „ overlap i f l(Iv) < l(Iu) < r(A>) or if l(Iu) < l(Iv) < r(Iu). A subgraph is called a clique, if every pair of vertices i n the subgraph is connected by an edge. A clique C is m a x i m a l i f there is no clique of G that properly contains C as a subset. Let size(C) be the number of vertices i n the clique, the m a x i m u m clique is the clique of greatest size among al l m a x i m a l cliques. 7.2.2 Interval Graph Coloring One of the most important applications of interval graphs is job scheduling. Consider a set of n jobs to be scheduled on k servers. F i n d i n g a feasible schedule is equivalent to finding a proper k-coloring of the corresponding interval graph, such that no two adjacent vertices can have the same color (overlapping jobs are assigned to different Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 115 (c) (d) Figure 7.3: M a p p i n g batch scheduling to graph coloring. servers). Interval graphs and graph coloring problems have been studied intensively i n the l i terature (see [3, 47, 52, 78] and references wi th in) . B a t c h scheduling i n O B S networks can be treated as a subset of the interval graph coloring problem. We have a set of da ta bursts that we want to assign to a number of wavelength channels. E a c h da ta burst corresponds direct ly to an interval on the real line, and assigning wavelength channels to bursts is s imilar to assigning colors to intervals, where no two overlapping bursts can be assigned to the same wavelength channel. Figure 7.3 gives an example for mapping batch scheduling to graph coloring. In Figure 7.3a, a batch consist ing of five bursts to be assigned to three wavelength channels. Figure 7.3b shows the corresponding interval graph. In Figure 7.3c, the interval graph is colored using three colors: 1, 2 and 3. Figure 7.3d shows the wavelength assignment of the batch. E a c h control burst represents a reservation request for an interval. T h e reservation request for da ta burst bi specifies a start t ime of the reservation l(bj), corresponding to Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 116 the arr ival t ime of the data burst, and an end t ime of the reservation r(bi). T h e weight w(bi) of burst bi is equal to (r(bi) — l(bi)). 7.3 An Optimal Batch Scheduling Algorithm (BATCH-OPT) T h e batch scheduling problem can be stated as follows: G i v e n k wavelengths and a set of n bursts {bi,.., bn} i n the batch, find a feasible schedule that maximizes the value of the da ta bursts accepted on the k wavelength channels. Note that n varies from one batch to another depending on the arrivals to the control burst queue. T h e value of the accepted bursts is s imply the sum of their weights. T h e weight of the burst is defined as the length of its corresponding interval. A number of algorithms exist i n the l i terature for f inding an opt imal feasible schedule of intervals while max imiz ing the to ta l weight of the selected intervals [1, 3, 78]. In [78], the authors formulated the problem as an instance of the interval graph coloring problem as explained next. G i v e n k colors and n intervals, the objective is to maximize the value of the legally colored graph. T h e problem is then reformulated as the following b inary integer linear program ( I L P ) : M a x i m i z e wTx subject to Ax < ek, xe {0,1}, where w is an n-vector representing the weights of the intervals, x is a binary n-vector Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 117 i n which Xj = 1 implies that interval j is to be selected, Xj = 0 otherwise. A is m x n clique mat r ix [20], in which m is the number of the m a x i m a l cliques i n the interval graph, where A^ = 1 i f interval j is i n the ith m a x i m a l clique, and A^ = 0 otherwise. A l s o , e is an m-vector of f s . f L P problems are generally N P - h a r d . However, for our part icular problem, the A mat r ix has the consecutive ones property, and A is thus totally unimodular'[55]. Therefore, we can relax the integrali ty constraint and solve the problem as a linear program i n po lynomia l t ime. T h i s f L P formulat ion can be used to find an offline op t imal schedule of bursts after receiving a l l the reservation requests. T h i s op t ima l schedule can serve as a reference against which the performance of other algori thms can be compared. A l t h o u g h i t is tempt ing to use the same 1 L P formulation for finding the op t ima l schedule for a batch of bursts, i t is not possible. T h e reason is that zero or more of the n bursts may not be assignable to one or more of the k wavelength channels due to already exist ing assignments of bursts belonging to previous batches. T h i s adds ext ra constraints to the problem. To find an op t ima l batch schedule, we formulate our problem as an instance of the scheduling with non-identical machines problem [f], in which we associate w i t h each interval (burst) a subset of servers (wavelength channels) on which it can be processed. Some bursts can not be processed on any wavelength channel, because a l l wavelength channels are busy i n the t ime intervals corresponding to these bursts, these bursts w i l l be dropped and not included i n the opt imiza t ion process. T h e authors i n [1] have given an Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 118 algori thm that finds the op t imal feasible schedule for the non-identical machines problem. T h e a lgor i thm ( B A T C H - O P T ) works as follows. F i r s t , bu i ld a list of events corresponding to the start and end times of the intervals being opt imized. Then , for each event construct the vertices corresponding to legal combinat ion of intervals and servers at the t ime of the event. T h e constructed vertices are used to bu i ld a directed graph. It then can be shown that the interval assignments along the longest path i n the directed graph represent the op t imal interval assignment to servers. Unfortunately, the above algori thm has an 0(nk+l) computat ional complexity, which is high when k is large, rendering this a lgor i thm imprac t ica l for use as an online batch scheduler. However, the a lgori thm is useful for comparison purposes since it serves as an upper bound on the performance of batch scheduling algorithms i n terms of b locking probabil i ty. 7.4 Heuristic Batch Scheduling Algorithms Because finding the op t ima l batch schedule has h igh computa t ional complexity, we have to tu rn our attention to heuristic algorithms. In this section we propose a number of batch heuristic algorithms for wavelength channel scheduling i n O B S networks. A l l of the proposed heuristic algorithms are based on performing the following two steps: 1. Impose a certain linear order on the control bursts i n the batch queue. 2. Traverse the bursts in this linear order, and assign the corresponding da ta bursts Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 119 to wavelength channels using a greedy void fi l l ing wavelength scheduling algori thm. A l t h o u g h the ordering process imposes a smal l addi t ional delay on the bursts i n the batch queue, this delay is l imi ted since the number of bursts in the batch queue is bounded by the acceptance delay value. If we were to order the bursts direct ly i n the F I F O queue shown i n F igure 7.1, then i t is possible that a control burst w i l l be delayed past the arrival t ime of the corresponding data burst because the number of bursts involved i n the ordering process w i l l not be bounded, and this shows the importance of the batch queue. In the following we propose four batch ordering algorithms: Smallest-Last Vertex Ordering (SLV), Maximal Cliques First Ordering (MCF), Smallest Start-time First Or-dering (SSF), and Largest Interval First Ordering (LIF). T h e first two algorithms rely on the structure of the interval graph corresponding to bursts under scheduling, while the last two algorithms uti l ize the properties of the ind iv idua l bursts. 7.4.1 Smal les t -Las t Ve r t ex Orde r i ng ( S L V ) T h e S L V heuristic a lgor i thm orders the vertices of the interval graph according to the smallest-last ordering [47]. The vertices Vj, v2, • • •, vn of a graph are said to be i n smallest last order whenever Vi has m i n i m u m degree in the m a x i m a l subgraph on the vertices v\, v2, • • •, Vi for al l i. Let 5(H) = minvev(H){deg(v\H)} be the m i n i m u m degree of graph H. A formal description of the S L V algor i thm is given i n A l g o r i t h m 7.1. T h e S L V algor i thm works as follows. Let vn be chosen to have m i n i m u m degree i n Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 120 i n p u t : G on n vertices o u t p u t : A n ordering vi, v2, • • •, vn of vertices of G , where deg(vi\Hi) = 6(Hi) for 1 < i < n ; i n i t i a l i z e i <— n, H <— G* w h i l e i > 1 d o Let be a vertex of m i n i m u m degree i n H; H <— H — Vi, i <— i — l\ e n d Repor t sequence Vj, v2, • • •, vn; A l g o r i t h m 7.1: S L V algor i thm G. For i = n — 1, n — 2 , . . . , 2 ,1 , let Vi be chosen to have m i n i m u m degree in JTYJ = ( V ( G ) — vn, vn_j,..., U j + i ) . F r o m the resulting sequence vi, v2, • • •, u n , where vn has the m i n i m u m degree in G, vertex vi w i l l be colored first. W h i c h means that the burst corresponding to v\ w i l l be assigned first to the first available wavelength. T h e process repeats unt i l each burst is either assigned to a wavelength channel or dropped. T h e a lgor i thm does not consider the weight of the bursts, and i t only at tempts to minimize the number of dropped bursts. T h e in tu i t ion behind the S L V algori thm is that i f a graph has only a few nodes of very large degree, then coloring these nodes early w i l l avoid the need for using a very large set of colors. T h i s means that assigning bursts which overlap the largest number of other bursts first to wavelength channels w i l l generally lead to min imiz ing the number of bursts to be dropped. T h e fact that any smallest-last vertex ordering minimizes the number of colors needed over n ! possible ordering is shown i n [48]. Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 121 4 2 1 3 5 (b) Figure 7.4: Interval graph example. To i l lustrate how the S L V a lgor i thm works, we use the simple graph given i n Figure 7.4. Figure 7.4a shows a batch of intervals and Figure 7.4b shows the corresponding interval graph. Intervals are numbered i n an ascending order according to their finish t ime. T h e S L V algor i thm selects the node w i t h the smallest degree, which is node 5 i n Figure 7.4b. T h e n it updates the graph and repeats, as shown i n Figure 7.5. If there is a tie, the node w i t h the smallest number is chosen. T h e final sequence is 5, 1, 2, 3, 4. Interval coloring w i l l be done i n the reverse order (i.e., 4, 3, 2, 1, 5). T h e S L V a lgor i thm has a computa t iona l complexi ty of 0 ( | £ 7 | + | V | ) [47]. For dense graph the complexi ty becomes 0(n2). T h e algori thm requires the input to be a graph. B u i l d i n g the graph from the interval list takes 0(n2) t ime. T h e L A U C - V F a lgor i thm require 0(nk log N) t ime to assign n bursts to wavelength channels. Therefore, the overall complexi ty of the S L V algor i thm is 0 ( n 2 + nklogN). Since the number of wavelength channels k is in the same order of magnitude as n, the overall complexi ty of the S L V Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 122 2 3 4 4 (c) (d) Figure 7.5: I l lustrat ion of the S L V algor i thm. a lgori thm can be reduced to O (nk log N). 7.4.2 Maximal Cliques First (MCF) T h e basic idea behind the M C F algor i thm is that since the m a x i m u m clique that can be colored is of size k, then our problem is equivalent to that of delet ing a subset of intervals such that a l l remaining cliques are of size k or less. To this end, the M C F algor i thm finds al l the m a x i m a l cliques i n the interval graph, then orders them i n an increasing order according to time. Le t {Ci,C2---Cm} be the set of m a x i m a l cliques i n G ordered such that Ci -< Cj for i < j . T h e a lgor i thm processes intervals belonging to Cj before intervals belonging to d for j > i. A formal description of the a lgor i thm is given i n A l g o r i t h m 7.2. The M C F algor i thm works as follows. It finds the list of m a x i m a l cliques i n the Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks i n p u t : G on n vertices, k o u t p u t : A list of vertices L i n i t i a l i z e H <— G w h i l e true d o Let C = list of a l l m a x i m a l cliques i n H w i th size > k; i f C is empty t h e n break; e n d Let cmax = clique w i t h latest occurrence t ime i n C ; Z 5ZZ6(c m a a ; ) k: for i <— 0 to z — 1 d o Vi = vertex w i t h smallest finish t ime in cmax; H ^ H - V i -S S U Vi] e n d e n d L L U Vj, \/VJ remaining i n G; A p p e n d 5 to the end of L; Report sequence L; A l g o r i t h m 7.2: M C F algor i thm Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 124 interval graph w i t h size larger than the number of available wavelengths. T h e a lgor i thm then finds the clique wi th the latest occurrence t ime among this list. Thereafter, the a lgor i thm removes the intervals w i t h the smallest finish t ime from the m a x i m a l clique (and from the graph) such that the size of the max ima l clique becomes equal to the number of the available wavelengths. T h i s process is repeated unt i l the size of a l l m a x i m a l cliques i n the graph are less than or equal to the number of wavelengths. A l l vertices remaining i n G are appended to the output list first, then the vertices removed by the a lgor i thm are appended to the end of the output list. F igure 7.6 shows how the M C F algor i thm is applied to the interval graph of Figure 7.4, for k — 2. In F igure 7.6b, the m a x i m a l cliques list of the interval graph is shown. T h e m a x i m a l clique that has the greatest finish t ime has two intervals only, then no updates are required here. T h e next m a x i m a l clique has three intervals, therefore, one interval needs to removed. T h e interval to be removed is the interval w i t h smallest finish t ime, which is interval 2. F igure 7.6c and Figure 7.6d shows the resulting interval graph and its m a x i m a l cliques list after removing node 2. T h e resulting node sequence is: 5, 4, 3, 1, 2, and interval 5 w i l l be assigned first. F i n d i n g the m a x i m a l cliques i n the interval graph requires end points of intervals to be sorted first, which can done in 0(n log n) t ime. T h e n we apply the M A X I M A L _ C L I Q U E S a lgor i thm described i n A p p e n d i x A , which requires 0(n) t ime. T h e M C F algori thm performs 0(n) updates per m a x i m a l clique. Since we have O(n) m a x i m a l cliques, the complexi ty of the M C F algor i thm is 0(n2). W h e n tak ing the L A U C - V F into considera-t ion, the overall complexi ty becomes 0(n2 + nklogN). Since k is i n the same order of Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 125 2 3 Maximal Cliques (c) (d) Figure 7.6: I l lustrat ion of the M C F algori thm. magnitude as n, the final complexi ty reduces to 0(nk log N). 7.4.3 Smal lest S ta r t - t ime F i r s t O rde r i ng (SSF) In S S F ordering, intervals are ordered according to their left most point (start t ime). Accordingly , a set of intervals {ii,i2, • • • ,in} are said to be i n S S F ordering i f l(ii) < l(i2) < ... < l(in)- Acco rd ing to the S S F algori thm, bursts that start earlier i n t ime are assigned to wavelength channels first. The idea behind the S S F a lgor i thm is to minimize the effect of the offset dispersion on the blocking probabil i ty. F i n d i n g the S S F ordering can be done i n 0(n log n) t ime, where n is the number of bursts i n the batch queue. Therefore, the overall complexi ty is dominated by the complexi ty of the L A U C - V F a lgor i thm, and it becomes 0(nk log N). Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 126 7.4.4 Largest In terva l F i r s t O rde r i ng ( L IF ) L I F a lgor i thm orders Intervals according to their weight. T h e L I F a lgor i thm outputs a sequence of intervals ii,i2, •••,in, where w(ij) > w(ik) for j < k. Us ing L I F ordering, bursts are sorted i n a descending order according to their size, and the burst w i t h the largest size is assigned first. The ra t ional behind the L I F a lgor i thm can be explained as follows. O u r a im is to maximize the number of bits accepted, therefore, i f more large bursts are accepted then we have moved closer to our a im. Intuitively, the probabi l i ty that a large burst w i l l be accepted is higher i f we t ry to assign it to a wavelength channel earlier i n the process. The L I F ordering can be found i n O ( n l o g n ) t ime, where n is the number of bursts i n the batch queue. Accordingly , the final complexi ty w i l l be 0(nk log N). 7.5 Performance Evaluation T h i s section presents experimental results on the proposed algorithms: S L V , M C F , S S F and L I F , and their comparisons w i t h the op t imal batch a lgor i thm ( B A T C H - O P T ) , and the greedy L A U C - V F a lgor i thm. O u r m a i n focus i n the following simulations is the b locking probabil i ty. Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 127 Figure 7.7: S imula t ion model for Section 7.5. 7.5.1 S imu la t i on Se tup Figure 7.7 shows the s imulat ion model used i n this section, which is based on the O P N E T s imulat ion tool , ft consists of a single O B S node connected to traffic sources and a sink node. E a c h input l ink carries two separate wavelengths, one for data and one for control . T h e output l ink carries five wavelengths, four for data and one for control , and each wavelength has transmission speed of approximately 2.5 Gbps (OC-48) . We assume that sources generate control and data bursts. Sources generate bursts according to Poisson process and the burst size has a mean value equal to B bits. The offset t ime has a uniform dis t r ibut ion over [Amin, Amax\. Le t A be the transmission t ime of 1024 bits on one of the wavelengths, i.e., A = 1024/2377728000 = 4.3e-7 seconds. We express the acceptance delay and the offset t ime in terms of A . In the following simulations, unless otherwise stated, we set the acceptance delay d to an arbi t rary value of 100A second, which is approximately 40/^sec. T h e greedy wavelength a lgor i thm used i n conjunction w i t h the batch algorithms is the L A U C - V F algori thm. Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 128 0.35 0.3 0.25 •§ 0.2 x> o eu t o n £ 0.15 0.05 -1- B A T C H O P T - * - L A U C V F - B - L I F -6- S L V -e - S S F - A - M C F 0.2 0.3 0.4 0.5 0.6 0.7 O.f Total Traffic Load 0.9 Figure 7.8: B l o c k i n g probabi l i ty vs. offered load i n case of exponential ly dis t r ibuted burst sizes. 7.5.2 B l o c k i n g P r o b a b i l i t y vs . Offered L o a d In this subsection, we study the performance of the proposed algori thms while varying the O B S node load. We study two scenarios. In the first scenario, we use exponential ly dis t r ibuted burst sizes w i t h mean value B = 81920 bits. T h e values of Amax and Amin are set to 150A seconds and 130A seconds, respectively. Figure 7.8 shows that the performance of the batch algori thms is upper bounded by the op t imum batch a lgor i thm as expected, and lower bounded by the greedy L A U C - V F a lgor i thm. T h e figure shows that the L I F a lgor i thm is the best performing a lgor i thm i n Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 129 this scenario, and its performance is very close to the B A T C H - O P T algori thm. Moreover, the figure shows that S L V and S S F algorithms perform sl ightly better than the L A U C - V F a lgori thm, however their results are not as significant when compared to the M C F and L1F algorithms. fn the second scenario we use constant burst size equal to 8f 920 bits. F igure 7.9 shows that the L f F algori thm i n this scenario performs exact ly as the L A U C - V F a lgor i thm. T h i s result is actually intui t ive since a l l intervals w i l l have the same size, thus no ordering w i l l actually take place. Addi t iona l ly , the results show that the S S F and S L V algorithms are the best performing algori thms in this scenario. Moreover, the M C F algor i thm i n this scenario performs significantly better than the L A U C - V F a lgor i thm, but not as good as the S S F and S L V algorithms. 7.5.3 B l o c k i n g P r o b a b i l i t y vs. Offset T i m e R a n g e We define the offset t ime range to be Amax — Amin. fn this subsection, we vary the value of Amin to study the effect of the offset t ime range on the performance of the batch scheduling algorithms. We use exponential ly dis t r ibuted burst sizes w i t h mean B — 81920 bits. T h e value of A m a x is set to 200A, and offered load is set to 99% of the l ink capacity. The value of A m i n is varied between 1 0 A and 150A. Figure 7.10 plots the b locking probabi l i ty against the offset t ime range value. Figure 7.10 illustrates that, generally, the b locking probabi l i ty increases as the offset t ime range increases. Addi t iona l ly , the rate of the increase i n the blocking probabi l i ty Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 130 Figure 7.9: B l o c k i n g probabi l i ty vs. offered load i n case of constant burst size. er 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 131 100 150 Offset Range Figure 7.10: B l o c k i n g probabi l i ty vs. offset t ime range. Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 132 is approximately equal for a l l algorithms, except for the S S F algori thm whose block-ing probabi l i ty increases at a lower rate. T h i s increase is due to the "retro-blocking" phenomena of the J E T signaling protocol (refer to Chapter 5), i n which, a reservation request can be blocked by another reservation start ing after its own t ime. Obvious ly this phenomena becomes more significant as the offset t ime range becomes larger. T h e blocking probabi l i ty of the S S F algor i thm increases at a lower rate because i t sorts the bursts according to their s tar t ing time, therefore, it minimizes the effect of the offset t ime range. To evaluate the effect of the offset t ime range on the performance of the batch schedul-ing algorithms, we implemented the offline op t imal ( O P T I M U M ) a lgor i thm given i n [1] (described i n appendix B ) , and compared the B A T C H - O P T a lgor i thm against i t . Figure 7.11 re-plots the b locking probabi l i ty curves for the L A U C - V F , B A T C H - O P T algorithms shown i n Figure 7.10, i n addi t ion to the b locking probabi l i ty curve for the O P T I M U M algor i thm. F igure 7.11 shows that the performance of the O P T I M U M algor i thm is not affected by the offset t ime range. Th i s is due to the fact that the O P T I M U M algor i thm waits un t i l a l l bursts are received before deciding on the bursts to be rejected, at which t ime the offset w i l l have m i n i m a l effect, because burst arrivals w i l l be equally dis t r ibuted over t ime. Furthermore, Figure 7.11 clearly shows that the difference between the performance of the B A T C H - O P T a lgor i thm and performance of the O P T I M U M algor i thm becomes very smal l when the offset t ime range is smal l ( 5 A ) . Th i s difference starts to increase as the Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 133 Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 134 offset t ime range increases. T h i s can be explained when we note that as the offset t ime range increases, the probabi l i ty of overlapping between intervals requested by bursts i n the batch queue decreases (refer to Chapter 5). In other words, as the offset t ime range increases, the requested intervals are more spread out i n t ime. T h i s w i l l decrease the effect of the op t imiza t ion done by the batch scheduling a lgor i thm and subsequently w i l l lead to higher b locking probabil i ty. 7.5.4 Effect of the Accep tance De lay In this subsection, we investigate the effect of the acceptance delay parameter (d) on the performance of the batch scheduling algorithms. We fix the value of the offset t ime range to 5 0 A and the offered load to 99% of the l ink capacity. F igure 7.12 and Figure 7.13 plot the blocking probabi l i ty of the B A T C H - O P T a lgor i thm versus the acceptance delay for exponentially dis t r ibuted burst sizes and constant burst sizes, respectively. T h e acceptance delay is varied between 10A and 150A. In addi t ion, the figure shows the blocking probabi l i ty for the L A U C - V F and O P T I M U M algorithms. It is impor tant to note that the acceptance delay is not a parameter of either the L A U C - V F or the O P T I M U M algorithms, therefore they have constant values i n the figure. Figure 7.12 and Figure 7.13 show that increasing the acceptance delay has the effect of enhancing the performance of the B A T C H - O P T algori thm, and br ing its performance closer to the performance of the O P T I M U M algori thm. O n the other hand, when the acceptance delay is decreased, the b locking probabi l i ty of the B A T C H - O P T a lgor i thm Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 135 o CL 0.33 0.32 0.31 0.3 0.29 .£ 0.28 o o m 0.27 0.26 0.25 0.24 - t - LAUCVF - * - BATCHOPT -©- OPTIMUM O 0 0 O © 0 6 ? © © o -• 0 50 100 150 Acceptance Delay Figure 7.12: B l o c k i n g probabi l i ty vs. acceptance delay w i t h exponential ly distr ibuted burst sizes. Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 136 0.32 r 0.314 r a 0.312 r 0.31 0.3081 0.306 h 3* M M * M * » « M M K -*- LAUC-VF -e- BATCHOPT OPTIMUM C r — * s e o * *—— X * k * —* #• 0.304 50 100 150 Acceptance Delay Figure 7.13: B l o c k i n g probabi l i ty vs. acceptance delay w i t h constant burst sizes. apter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 137 decreases and becomes closer to the L A U C - V F algori thm. Th i s effect is a t t r ibuted to the number of bursts available i n the batch queue. A s the acceptance delay increases, the number of bursts involved i n the op t imiza t ion process also increases, which gives better results i n terms of the blocking probabil i ty. It should be noted that a control burst w i l l incur a m a x i m u m of one acceptance delay per hop, as a result, it is necessary to increase the offset time per hop by an amount equal to the acceptance delay. Accordingly , increasing the acceptance delay w i l l cause an increase in the data burst end-to-end delay. Therefore, there is a tradeoff between the end-to-end delay and the blocking probabil i ty. However, Figure 7.12 and Figure 7.13 show that even a smal l processing delay yields a considerable performance enhancement over greedy algorithms. Figure 7.14 plots the b locking probabi l i ty of the B A T C H - O P T algor i thm when bo th the offset t ime range and the acceptance delay are varied. It is clear from the figure that the worst b locking probabi l i ty value occurs when the offset t ime range has a large value and i n the same time the acceptance delay has a smal l value. A s the offset t ime range decreases and the acceptance delay increases, the b locking probabi l i ty decreases. B o t h the offset t ime range and the acceptance delay affect the qual i ty of the op t imiza t ion process carried out by the B A T C H - O P T algor i thm. Increasing the offset t ime range decreases the probabi l i ty that the intervals requested are overlapping and accordingly decreases the effect of the op t imiza t ion process. O n the other hand, increasing the acceptance delay increases the number of bursts involved i n the op t imiza t ion process and subsequently Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 138 0.34 - , Acceptance Delay Figure 7.14: Effect of varying the acceptance delay and the offset t ime range on the b locking probabil i ty. Chapter 7. Batch Scheduling Algorithms: A Class of Wavelength Schedulers in OBS Networks 139 increases the effect the op t imiza t ion process. Therefore, we conclude from Figure 7.14 that large values of the processing delay are only required when the offset t ime range has a large value. 7.6 Concluding Remarks In this chapter, we have introduced a novel class of wavelength scheduling algori thms i n O B S networks called batch scheduling algori thms. W e have described an o p t i m u m batch scheduler that serves as an upper bound for the performance of the batch scheduling algorithms. We have introduced four heuristic batch scheduling algorithms: S L V , M C F , L I F and S S F . T h e M C F and L I F were shown to be superior i n scheduling variable size bursts. The L I F a lgor i thm is simpler than the M C F algor i thm, however, the L I F algo-r i t h m favors larger bursts. In case of constant size bursts, the S L V and S S F algori thms were shown to perform better than the other algori thms. Moreover, we have studied the effect of the acceptance delay parameter on the performance of the batch scheduling al -gori thms. We have shown that generally it is possible to obta in a reasonable performance enhancement using the batch scheduling algori thms even when the acceptance delay is smal l . 140 Chapter 8 Conclusions and Future Research We conclude this thesis w i th a summary of our contributions and suggestions for future work. 8.1 Summary The ma in objectives of this thesis were: • T h e proposal of new methods for QoS provisioning in O B S networks. • T h e development of new wavelength scheduling algorithms to reduce the blocking probabi l i ty i n O B S networks. T h e following is a summary of each of the work chapters, fn Chapter 3, we presented a survey of a l l previously proposed wavelength scheduling algorithms i n the literature for J E T - b a s e d O B S network. In addi t ion, we proposed two wavelength scheduling algo-r i thms: M i n - A V and M a x - N G V . We compared the performance of the newly proposed algorithms to those previously proposed using discrete-event s imulat ion. S imula t ion re-sults showed that, i n general, the best performing a lgor i thm is the M i n - A V algori thm. Chapter 8. Conclusions and Future Research 141 The advantage of the M i n - A V a lgor i thm becomes apparent when the average burst size is small , which shows that the M i n - A V algor i thm effectively reduces the fragmentation level of wavelength channels. Results in this chapter also appears in [33],[40]. Chapter 4 presented a simple and effective scheme for QoS provisioning i n buffer-less O B S networks. The scheme is called P P J E T , and it provides service to different traffic classes based on a strict pr ior i ty order. The P P J E T scheme util izes the J E T signaling protocol , i n conjunction w i t h a new channel-scheduling a lgor i thm called P L A U C - V F . P P J E T minimizes b locking of h igh pr ior i ty bursts by preempting reservations for lower pr ior i ty bursts. Therefore, i n P P J E T reservation requests for a burst can only be blocked by a reservation request w i t h equal or higher priori ty, or by a lower pr ior i ty burst that started service. We evaluate the performance of the P P J E T scheme through s imulat ion. Results showed that P P J E T can achieve significant performance enhancements over the well known P J E T scheme i n terms of b locking probabi l i ty and end-to-end delay. Results of this work have been published i n [29],[30]. In Chapter 5 we presented a new analyt ical model for calculat ing the b locking prob-abi l i ty i n J E T - b a s e d O B S networks. Relat ionship to the problem of calculat ing the reservation probabi l i ty i n advance reservation systems was also discussed. T h e proposed analyt ical model takes into consideration the effects of the burst offset t ime and the burst length on the b locking probabil i ty. W e used a (M-fT)-s ta te non-homogenous M a r k o v chain to describe the state of an output l ink car ry ing M wavelength channels. In addi-t ion, we modeled each wavelength channel by a 2-state M a r k o v chain. In the proposed Chapter 8. Conclusions and Future Research 142 model the offset t ime is drawn from a specified d is t r ibut ion so that wavelength reserva-t ion requests, made before a given t ime, bu i ld up to be a workload whose mean value declines w i t h the reservation start ing t ime. Furthermore, the b locking probabi l i ty we expressed in terms of first passage t ime distr ibut ions to account for the burst length. To verify its accuracy, the model results were compared w i t h results from a discrete-event s imulat ion model . T h e proposed model results were found to be in satisfactory agreement w i t h s imulat ion results. T h i s work also appears i n [37],[38],[39]. Chapter 6 presented a detailed architecture for provid ing quanti tat ive qual i ty of ser-vice guarantees i n L O B S networks, fn the proposed architecture, packets are assembled into data bursts based on their respective traffic class at ingress nodes. The burst as-sembly algori thm employs two parameters to control the burst b locking probabi l i ty and burst assembly delay. A fair packet queueing a lgor i thm is deployed i n each edge node to regulate access to a wavelength scheduler. For L O B S core nodes, we presented a novel approach for scheduling control bursts i n the control plane of these nodes to guaran-tee fair bandwid th al locat ion. Based on the information provided by the queued control bursts, the core scheduling a lgor i thm creates a v i r tua l queue of da ta bursts i n core nodes, then it selects the eligible control burst to be processed by the wavelength scheduler. We presented analyt ical results for the delay and the b locking probabi l i ty i n the proposed ar-chitecture, and used simulations to demonstrate that the proposed architecture provides accurate and controllable service guarantees i n L O B S networks. Results from this work appear i n [31],[32]. Chapter 8. Conclusions and Future Research 143 Chapter 7 proposed a novel class of wavelength scheduling algori thms for O B S net-works. The proposed wavelength scheduling algorithms schedule a batch of data bursts together instead of scheduling them one by one. Previously proposed wavelength schedul-ing algorithms are considered greedy algori thms in the sense that they consider every reservation request individual ly , and make the choice that looks best at the moment. O n the other hand, when the wavelength scheduler becomes free, a batch scheduling a lgor i thm w i l l wait for a smal l amount of t ime equal to the acceptance delay parameter, then i t w i l l process a l l the reservations requests in the batch queue together instead of the previously used greedy approach. T h i s acceptance delay enables the batch schedul-ing algorithms to accept the requests that w i l l maximize the u t i l i za t ion of wavelength channels. We clearly showed a relat ion between the problem of batch scheduling and the interval graph coloring problem. Based on this relation, we described an op t ima l batch scheduler that serves as an upper bound on the performance of batch schedul-ing algorithms. Furthermore, we introduced four heuristic batch scheduling algorithms. T h e performance of the proposed algorithms was evaluated using a discrete-event s imu-la t ion model . S imula t ion results suggested that batch schedulers could decrease the the b locking probabi l i ty by 25% compared the best previously known wavelength scheduling a lgor i thm. T h i s work has been published i n [34],[35],[36]. In conclusion, among the m a i n contributions of this thesis, we proposed: • T w o new methods for QoS provisioning i n O B S networks. • A n analyt ical model for calculat ing the blocking probabi l i ty i n O B S networks. Chapter 8. Conclusions and Future Research 144 • Several wavelength scheduling algorithms that are able to reduce the b locking prob-abi l i ty in O B S networks. 8.2 Future Work We present below a list of research problems that can be investigated as possible exten-sions for research work reported i n this thesis. 1. T h e in tu i t ion behind the work in Chapter 7 was that it may be advisable to reject an in i t i a l ly unblocked request if later requests w i l l make better use of wavelength channels. Our approach to the problem was delaying the acceptance or rejection of a request un t i l we see more requests. A different approach to the problem is possi-ble. If we assume that the arr ival process is known, for example non-homogenous Poisson process as i n the case of Chapter 5, then we could develop a selective burst acceptance mechanism, w i t h the objective of max imiz ing the u t i l i za t ion of wave-length channels, while e l iminat ing the need for the acceptance delay. In this case we only know the expectat ion of the future arrivals. A model that describes the system evolution w i l l need to be developed. In addi t ion, a set of decision rules w i l l need to be devised. 2. A number of new differentiated service mechanisms in O B S networks can be devised based on algorithms discussed i n Chapter 7. In part icular , i n Chapter 7 we have considered the weight of a burst to be equal to its size, however, preferential treat-Chapter 8. Conclusions and Future Research 145 merit of bursts could be achieved by assigning to the burst a weight that expresses its class of service. Accordingly , max imiz ing the weight of the accepted bursts would translate to accepting bursts from higher classes of service. T h e most i m -portant components of this work would be selecting the weight assignment scheme and the selection of the opt imiza t ion algori thm. 3. T h e Transmission Cont ro l P ro toco l ( T C P ) is one of the dominant transport pro-tocols today. T h e T C P protocol has unique features, e.g. congestion control and retransmission, that w i l l certainly be affected by the O B S network characteristics. Therefore, a fruitful area of future research would be to study the influence of burst assembly algorithms, offset-time, O B S signaling protocols on T C P ' s performance. It would be par t icular ly interesting to study the effect of mechanisms proposed in this thesis on T C P . 4. W o r k done i n this thesis has been evaluated using a highly detailed discrete-event s imulat ion model . Therefore, network topologies used were l imi ted i n dimension. It would be interesting to simulate the proposed mechanisms i n a network wi th large number of nodes, large number of wavelengths and a sophisticated topology. T h i s is indeed a challenging task as the number of events i n such network would be very large to the degree that the s imulat ion running t ime would be prohibi t ively long. One solution would be to redesign the s imulat ion model to run on parallel architectures. 146 Bibl iography [1] M . A r k i n and E . Silverberg. Scheduling jobs w i th fixed start and end times. Discrete Applied Mathematics, 1 8 ( l ) : l - 8 , November 1987. [2] H . Cankaya, S. Charcranoon, and T . S . E l - B a w a b . A preemptive scheduling tech-nique for O B S networks w i t h service differentiation, fn Proceedings of IEEE Global Telecommunications Conference- Globecom'03, pages 2704-2708, San Francisco, De-cember 2003. [3] M . C . Car l i s le and E . L . L l o y d . O n the K-co lor ing of intervals. Discrete Applied Mathematics, 59(3):225-235, M a y 1995. [4] M . Casoni , E . L u p p i , and M . L . M e r a n i . Impact of assembly algorithms on end-to-end performance i n opt ical burst switched networks w i t h different QoS classes, fn 3rd International Workshop on Optical Burst Switching, San Jos, December 2004. [5] Y . Chen , M . H a m d i , and D . Tsang . P ropor t iona l QoS over O B S networks. In Proceedings of IEEE Global Telecommunications Conference- Globecom'01, pages 1510-1514, San Anton io , November 2001. Bibliography 147 [6] I. Chlamtac , A . Ganz , and G . K a r m i . Pure ly opt ical networks for terabit com-municat ion. In Proceedings of IEEE INFOCOM 1989, volume 3, pages 887-896, Washignton, D C , A p r i l 1989. [7] R . L . C r u z . A calculus for network delay, Par t f: Network elements i n isolat ion. IEEE Transactions on Information Theory, 37(1):114—131, January 1991. [8] A . Demers, S. keshav, and S. Shenkar. Analys i s and s imulat ion of a fair queueing algori thm, fn Proceedings of ACM SIGCOMM'89, A u s t i n , September 1989. [9] P . De Dobbelaere, K . Fal ta , L . Fan , S. Gloeckner, and S. Pa t ra . D i g i t a l M E M S for opt ical switching. IEEE Communications Magazine, 40(3):88-95, M a r c h 2002. [10] K . Dolzer , C . Gauger, J . Spth , and S. Bodamer . Eva lua t ion of reservation mech-anisms for opt ical burst switching. AE International Journal of Electronics and Communications, 55( l ) :18-25, January 2001. [11] J . Edmonds and R . M . K a r p . Theoret ica l improvements i n algori thmic efficiency for network flow problems. Journal of the ACM, f 9(2):248-264, A p r i l 1972. [12] T . S. E l - B a w a b and J . D . Sh in . O p t i c a l packet switching i n core networks: between vis ion and reality. IEEE Communications Magazine, 40(9):60-65, September 2002. [13] J . M . E l m i r g h a n i and H . T . Mouf tah . Technologies and architectures for scalable dynamic dense W D M networks. IEEE Communications Magazine, 38(2):58-66, Feb-ruary 2000. Bibliography 148 [14] L . Berger et al . General ized M P L S ( G M P L S ) signaling functional description. RFC 3471, January 2003. [15] R . Braden et a l . Integrated services in the Internet architecture: an overview. RFC 1633, June 1994. [16] S. Blake et al . A n architecture for differentiated services. RFC 2475, December 1998. [17] A . Ge, F . Cal legat i , and L . T a m i l . O n opt ica l burst swi tching and self-similar traffic. IEEE Communications Letters, 4(3):98-100, M a r c h 2000. [18] N . G h a n i , S. D i x i t , and T . S. Wang . O n I P over w d m integration. IEEE Commu-nications Magazine, 38(3):72-83, M a r c h 2000. [19] S. Golestani . A self-clocked fair queueing scheme for broadband applications. In Proceedings-of IEEE INFOCOM'94, pages 636-646, Toronto, A p r i l 1994. [20] M . C . Golumbic . Algorithmic Graph Theory and Perfect Graphs. Academic Press, 1980. [21] P . Goya l , H . M . V i n , and Ft. Cheng. Star t - t ime fair queueing: A scheduling algo-r i t h m for integrated services packet swi tching networks. IEEE/ACM Transactions on Networking, pages 690-704, October 1997. Bibliography 149 [22] J . J . Harms and J . W . Wong . Performance evaluation of scheduling algori thms for bandwid th reservation. In Teletraffic and Datatraffic in a Period of Change, ITC 13, Denmark, June 1991. [23] B . Hi rosak i , K . E m u r a , S. Hayano, and H . Tsu t sumi . Next generation opt ical net-works as value-creation platform. IEEE Communications Magazine, 41(9):65-71, September 2003. [24] G . H u , K . Dolzer, and C M . Gauger. Does burst assembly really reduce the self-similari ty. In Proceedings of Optical Fiber Communication Conference-OFC'03, vo l -ume 86, pages 124-126, A t l an t a , M a r c h 2003. [25] G . Hudek and D . Muder . Signal ing analysis for a mul t i -swi tch al l -opt ical network. In Proceedings of IEEE International Conference on Communications-ICC'95, Seattle, June f995. [26] D . K . Hunter and I. Andronovic . Approaches to opt ical Internet packet switching. IEEE Communications Magazine, 38(9):116-122, September 2000. [27] M . I izuka, M . Sakuta, Y . Nishino, and I. Sasase. A scheduling a lgor i thm min imiz ing voids generated by ar r iv ing bursts in opt ical burst switched W D M network. In Proceedings of IEEE Global Telecommunications Conference- Globecom'02, Ta ipe i , November 2002. Bibliography 150 [28] M . Izal and J . A r a c i l . O n the influence of self s imi lar i ty on opt ical burst switching traffic. In Proceedings of IEEE Global Telecommunications Conference- Globecom'02, pages 2320-2324, Ta ipe i , November 2002. [29] A . Kahee l and H . Alnuwei r i . A strict pr ior i ty scheme for quality-of-service provi-sioning i n opt ical burst switching networks. In Proceedings of IEEE Symposium on Computers and Communications-ISC COS, volume 1, pages 16-21, Turkey, June 2003. [30] A . Kahee l and H . Alnuwei r i . P r i o r i t y scheme for support ing qual i ty of service i n opt ical burst switching networks. OS A Journal of Optical Networking, 3(9):707-719, September 2004. [31] A . Kahee l and H . Alnuwei r i . Quant i ta t ive QoS guarantees i n labeled opt ical burst switching networks. Submitted to IEEE/ACM Transactions on Networking, Septem-ber 2004. [32] A . Kahee l and H . Alnuwei r i . Quant i ta t ive QoS guarantees i n labeled opt ical burst switching networks. In Proceedings of Global Telecommunications Conference-GLOBECOM'04, volume 3, pages 1747-1753, Texas, 29 November-3 December 2004. [33] A . Kahee l and H . Alnuwei r i . Wavelength scheduling algorithms i n buffer-less op-t ica l burst switching networks. In Proceedings of IASTED International Multi-Conference on Wireless and Optical Communications-WOC'04, volume 1, pages 744-748, Canada , J u l y 2004. Bibliography 151 [34] A . Kahee l and H . Alnuwei r i . Ba t ch scheduling algorithms: a class of wavelength schedulers in opt ical burst switching networks. In Proceedings of IEEE International Conference on Communications-ICC'05, Korea , June 2005. [35] A . Kahee l and H . Alnuwei r i . B a t c h scheduling algorithms for opt ical burst switch-ing networks. In IFIP-TC6 International Conference on Networking-Networking'05, Ontar io , M a y 2005. [36] A . Kahee l and H . Alnuwei r i . Wavelength scheduling algori thms w i t h delayed accep-tance for opt ical burst switching networks. In Canadian Conference on Electrical and Computer Engmeering-CCECE'05, Saskatchewan, M a y 2005. [37] A . Kaheel , H . Alnuwei r i , and F . Gebal i . A new analyt ica l model for comput ing blocking probabi l i ty in opt ical burst switching networks. Submitted to IEEE Journal on Selected Areas in Communications, September 2003. [38] A . Kaheel , H . Alnuwei r i , and F . Gebal i . A n a l y t i c a l evaluation of b locking probabi l i ty i n opt ical burst switching networks. In Proceedings of IEEE International Conference on Communications-ICC'04, volume 3, pages 1548-1553, France, June 2004. [39] A . Kahee l , H . Alnuwei r i , and F . Geba l i . A new analyt ica l model for comput ing blocking probabi l i ty i n opt ical burst switching networks. In Proceedings of IEEE International Symposium on Computers and Communications-ISCC'0Jh volume 1, pages 264-269, Egyp t , 28 June-1 Ju ly 2004. Bibliography 152 [40] A . Kaheel , T . K h a t t a b , A . Mohamed , and H . Alnuwei r i . Quality-of-service mecha-nisms in I P - o v e r - W D M networks. IEEE Communications Magazine, 40(12):38-44, December 2002. [41] T . K h a t t a b , A . Mohamed , A . Kahee l , and H . Alnuwei r i . O p t i c a l packet switching wi th packet aggregation. In Proceedings of International Conference on Software, Telecommunications and Computer Networks-SoftCOM'02, volume 1, pages 741 -746, Italy, October 2002. [42] M . K i j i m a . Markov Processes For Stochastic Modeling. C h a p m a n and H a l l , 1997. [43] E . L . Lawler . Combinatorial Optimization: Networks and Matroids. Ho l t , Rinehar t and W i n s t o n , 1976. [44] W . E . Le land , M . S. Taqqu, W . Wi l l inge r , and D . V . W i l s o n . O n the self-similar na-ture of ethernet traffic (extended version). IEEE/ACM Transactions on Networking, 2(1):1-15, February 1994. [45] Y . L iang , K . L i ao , J . W . Roberts , and A . S imonian . Queueing models for reserved set up telecommunications services. In Teletraffic Science for New Cost-Effective Systems, Networks and Services, ITC 12, Italy, June 1988. [46] H . Luss. A model for reservations for systems for large scale conferencing services. The Journal of the Operational Research Society, 31(3):239-245, M a r c h 1980. Bibliography 153 [47] D . W . M a t u l a . Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):217-427, J u l y 1983. [48] D . W . M a t u l a , G . Marb l e , and J . D . Isaacson. Graph Theory and Computing, chapter G r a p h coloring algorithms, pages 109-122. Academic Press, 1972. [49] P. M i t r a and S. Jason. Nonlinear l imi t s to the information capacity of opt ical fibre communications. Nature, 411:1027-1030, June 2001. [50] A . Mohamed , A . Kahee l , T . K h a t t a b , and H . Alnuwei r i . Eva lua t ion of op-t ica l packet switch as edge device using opnet modeler. available online: "h t tp : / /www.opnet .com/opnetwork2002" , Augus t 2002. [51] C . M u r t h y and M . Gurusamy. WDM Optical Networks: Concepts, Design, and Algorithms. Prent ice H a l l , 2002. [52] S. O la r iu . A n op t ima l greedy heuristic to color interval graphs. Information Process-ing Letters, 37( l ) :21-25, January 1991. [53] M . J . O 'Mahony , D . Simeonidou, D . K . Hunter , and A . Tzanakak i . T h e appl icat ion of opt ical packet swi tching i n future communica t ion networks. IEEE Communications Magazine, 39(3):128-135, M a r c h 2001. [54] O P N E T technologies inc. Web page: h t t p : / / w w w . o p n e t . c o m / , Augus t 2004. [55] C . H . Papad imi t r i ou and K . Steigli tz . Combinatorial Optimization : Algorithms and Complexity. Dover Publ ica t ions , 1998. Bibliography 154 [56] G . I . Papad imi t r iou , C . Papazoglou, and A . S . Pomports is . O p t i c a l switching: Swi tch fabrics, techniques, and architectures. Journal of Lightwave Technology, 21(2):384-405, February 2003. [57] V e r n Paxson and Sal ly F l o y d . W i d e area traffic: T h e failure of Poisson modeling. IEEE/ACM Transactions on Networking, 3(3):226-244, June 1995. [58] C . Qiao. Labeled opt ica l burst switching for I P - o v e r - W D M integration. IEEE Com-munications Magazine, pages 104-114, December 2000. [59] C . Qiao and M . Y o o . Op t i ca l burst swi tching ( O B S ) - a new paradigm for an opt ical internet. Journal of High Speed Networks, 8( l ) :69-84, January 1999. [60] C . Qiao and M . Y o o . Choices, features, and issues in opt ica l burst switching. Optical Network Magazine, l (2) :36-44, A p r i l 2000. [61] R . Ramaswami and K . N . Sivarajan. Optical Networks: A Practical Prespective, second edition. M o r g a n Kau fmann Publ ica t ions , 2002. [62] M . Renaud, F . Mase t t i , C . Gui l lemot , and B . Bos t ica . Network and system concepts for opt ical packet switching. IEEE Communications Magazine, 35(4):96-102, A p r i l 1997. [63] Insight Research. D W D M , S O N E T , and photonics: T h e emerging al l -opt ical network 2001-2006. Technical report, h t tp : / /www. ins igh t -co rp .com/ , M a y 2001. Bibliography 155 [64] E . Rosen, A . Viswana than , and R . Ca l l on . M u l t i p r o t o c o l label swi tching architec-ture. RFC 3031, January 2001. [65] D . Stephens, J . Bennett , and H . Zhang. Implementing scheduling algori thms in high speed networks. IEEE Journal on Selected Areas in Communications, 17(6): 1145-1158, June 1999. [66] J . Turner. Terabit burst switching. Journal of High Speed Networks, 8(1):3—16, M a r c h 1999. [67] S. Verma, H Chaskar, and R . Rav ikan th . Op t i ca l burst switching: A viable solut ion for terabit ip backbone. IEEE Network Magazine, 14(6):48-53, November 2000. [68] J . T . V i r t a m o . A model of reservation systems. IEEE Transactions on Communi-cations, 40(1):109-118, January 1992. [69] V . Vokkarane and J . Jue. P r io r i t i zed burst segmentation and composite burst assem-bly techniques for QoS support i n opt ical burst-switched networks. IEEE Journal of Selected Areas of Communications (JSAC), 21(7):1198-1209, September 2003. [70] V . M . Vokkarane and J .P . Jue. P r io r i t i zed rout ing and burst segmentation for QoS i n optical burst switched networks. In Proceedings of Optical Fiber Communication Conference- OFC'02, pages 221-222, A n a h e i m , M a r c h 2002. [71] H . L . V u and M . Zukerman. B l o c k i n g probabi l i ty for pr ior i ty classes i n opt ica l burst switching networks. IEEE Communications Letters, 6(5):214-216, M a y 2002. Bibliography 156 [72] J . Y . W e i and R . I. M c F a r l a n d . Just- in-t ime signaling for W D M opt ical burst switching networks. Journal of Lightwave Technology, 18:2019-2037, December 2000. [73] W . Wi l l inger , M . S. Taqqu, R . Sherman, and D . V . W i l s o n . Self-similari ty through high-variabi l i ty: Stat is t ical analysis of Ethernet L A N traffic at the source level. IEEE/ACM Transactions on Networking, 5( l ) :71-86, A p r i l 1997. [74] Y . X i o n g , M . Vandenhoute, and C . Cankaya. Con t ro l architecture i n opt ical burst-switched W D M networks. IEEE Journal on Selected Areas in Communications, 18:1838-1851, October 2000. [75] J . X u , C . Qiao, J . L i , and G . X u . Efficient channel scheduling algori thms i n opt ical burst switched networks. In Proceedings of IEEE INFOCOM 2003, San Francisco, M a r c h 2003. [76] L . Y a n g , Y . J iang, and S. J iang. A probabil is t ic preemptive scheme for providing service differentiation i n O B S networks, fn Proceedings of IEEE Global Telecom-munications Conference- Globecom'03, pages 2689-2693, San Francisco, December 2003. [77] M . Y a n g , S. Q . Zheng, and D . Verchere. A QoS support ing scheduling a lgor i thm for opt ical burst switching d w d m networks, fn Proceedings of IEEE Global Telecommu-nications Conference, Globecom'01, San Anton io , November 2001. [78] M . Yannakakis . T h e m a x i m u m K-colorable subgraph problem for chordal graphs. Information Processing Letters, 24:133-137, January 1987. Bibliography 157 [79] M . Y o o . M . Jeong, and C . Qiao. A high-speed protocol for bursty traffic in opt ical networks. In SPIE Proceedings, All Optical Networking: Architecture, Control and Network Issues, 3230:79-90, November 1997. [80] M . Y o o and C . Qiao. A new opt ical burst switching protocol for support ing qual i ty of service. In SPIE Proceedings, All Optical Networking: Architecture, Control and Management Issue, 3531:396-405, November 1998. [81] M . Y o o , C . Qiao, and S. D i x i t . Op t i ca l burst switching for service differentiation in the next generation opt ical Internet. IEEE Communications Magazine, 39(2) :98-104, February 2001. [82] X . Y u , Y . Chen , and C . Qiao. Performance evaluation of opt ical burst switching w i t h assembled burst traffic input . In Proceedings of IEEE Global Telecommunications Conference- Globecom'02, pages 2330-2334, Taipei , November 2002. 158 Append ix A A l g o r i t h m for F ind ing M a x i m a l Cliques in Interval Graphs In this A p p e n d i x we describe an a lgor i thm that we developed for finding max ima l cliques in interval graphs. The a lgor i thm is called MAXIMAL-CLIQUES, and it is formally described i n A l g o r i t h m A . l . T h e M A X I M A L - C L I Q U E S a lgor i thm works as follows. The end points of the pre-sented intervals are sorted i n ascending order. The algori thms run through the list of end points and inspect point by point, ff the inspected point (e) is a left point, then interval v corresponding to point e is added to a set c. ff the point is a right point, and the previous inspected point is a left point, then this means that intervals contained i n c form a m a x i m a l clique. In this case c is added to C , which is the list of m a x i m a l cliques, and v is removed from c because the interval has ended. F ina l ly , i f point e is a right point , and the previous inspected point was a right point, then point v is s imply removed from c because the interval has ended. T h e M A X I M A L _ C L f Q U E S a lgor i thm required 0(n) t ime i f the end points are pre-sorted, and 0(n log n) i f the end points are not sorted. Appendix A. Algorithm for Finding Maximal Cliques in Interval Graphs 159 i n p u t : L i s t of intervals v\, v2, • • •, vn o u t p u t : L i s t of m a x i m a l cliques C i n i t i a l i z e e < 1, c <— (p, C <— <p Let {e i , e 2 , . . . , e2n} be a list of end points in ascending order: for i «— 1 to In d o e < 6 ,^ i f e is a left point t h e n Let v — interval corresponding to e; c <— C U D ; e n d i f is a n ^ / i i point) and (ewev is a left point) t h e n A d d c to C ; Let i> = interval corresponding to e; c <— c \ t>; e n d i f (e is a right point) and (eprev is a right point) t h e n Let v = interval corresponding to e; c <— c \ v; e n d e n d Repor t C ; A l g o r i t h m A . l : M A X I M A L - C L I Q U E S a lgor i thm 160 Append ix B Offline Opt imal Scheduling A lgo r i t hm Authors i n [1] gave an a lgor i thm for finding an op t ima l feasible schedule of intervals while max imiz ing the to ta l weight of the selected intervals. T h e scheduling problem is formulated as instance of minimum-cost flow problem [43]. 1. Represent the problem i n the form of an interval graph. 2. Identify al l m a x i m a l cliques qi,... ,qr of the interval graph. Order the m a x i m a l cliques according to t ime. 3. Const ruct a directed graph G as follows: (a) Create nodes VQ,. .. ,vr and arcs (i>j, t>i_i) for i = 1 , . . . , r . T h e costs on these arcs equal 0 and their capacities are infinite (each arc represents a clique). (b) For each interval , i f f is i n cliques qj,..., qj+i, add an arc (VJ_I,VJ+1) of cost Wi and capacity f. (c) For each clique j that is not of m a x i m u m size, we add an arc (VJ-I,VJ) of cost Appendix B. Offline Optimal Scheduling Algorithm 161 0 and capacity equal to (maximum-clique-size - size-of-g.,-). (d) Consider node v0 to be a source S, and vT to be a sink T. 4. We require a flow from 5 to T of (maximum-clique-size - k), where k is the number of available wavelengths. A n op t imal solut ion to this m i n i m u m cost flow problem is i n fact an op t imal solution to our original problem. If an arc corresponding to interval f has a non-zero flow on it in the min-cost flow solution, then we do not process this interval . Thus , we do not process a subset of intervals such that a l l remaining cliques are of size k or less. Th i s subset is of smallest possible value since it corresponds to a min-cost flow solution. To find the min-cost flow we used the a lgor i thm described i n [11]. A n example for this construct ion is shown i n F igure B . l . The m a x i m a l cliques i n the graph can be found using the a lgor i thm described i n A p p e n d i x A i n O ( n l o g n ) , where n is the number of intervals. T h e complexi ty of the m i n i m u m cost flow algori thm described i n [11] is equal to (required flow x complexi ty of the shortest pa th algori thm). In our case the required flow is 0(n), and the complexi ty of the shortest path a lgori thm is O ( n l o g n ) . Therefore, the to ta l complexi ty is 0 ( n 2 l o g n ) . Appendix B. Offline Optimal Scheduling Algorithm 162 | W ; = ; C \v=h 1 ! i 1 1 I ! W = 1 1 !• . ! J j 1—™ 1 I 11 w =i d\ w — e • i i a. The intervals. w = cost w= b, p = 1 w=0, p =1 b. The corresponding graph. Figure B . l : E x a m p l e for m i n i m u m cost flow construct ion 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0099850/manifest

Comment

Related Items