The role of FDLS in scheduling in obs networks - Vo Viet Minh Nhat

75 JOURNAL OF SCIENCE, Hue University, Vol. 69, No. 6, 2011 THE ROLE OF FDLS IN SCHEDULING IN OBS NETWORKS Vo Viet Minh Nhat1 and Nguyen Hong Quoc2 1 Faculty of Hospitality and Tourism, Hue University 2 College of Pedagogy, Hue University Abstract. Scheduling in a node plays an important role in improving the efficiency of exploiting the bandwidth of optical burst switched networks. However, a burst cannot be scheduled and will be dropped if resources, including a wavelength channel and a position of scheduling an arriving burst on the channel, are not available. A solution to this problem is to use an FDL buffer to delay the appearance of the arriving burst at output, by changing the position of scheduling the arriving burst on the selected available wavelength channel, hopefully there exists an available resource at the delayed output time. This article focuses on analyzing the role of FDL buffer in scheduling and evaluating its performances basing on the simulation results on NS2. Keywords: OBS, Scheduling, FDL buffer. 1 Introduction To satisfy the increasing demands for bandwidth in backbone networks such as the Internet, many models of optical network have been studied and proposed. In these models, wavelength routing (WR) networks are relatively easy to be installed, but difficult to handle on variable increment flows and frequently changed-status links. Optical packet switching (OPS) networks are obviously the next choice to overcome the above disadvantages, but they require more advanced technologies such as optical buffer and optical packet switching fabric which are currently unavailable. A new approach is the model of optical burst switching (OBS) which combines the advantages of wavelength routing and optical packet switching networks. Fig. 1. The offset time is calculated at least equal to the total of processing and transmission time from source to destination 76 From the first proposal of C. Qiao and M. Yoo [1][2], OBS models quickly get much attention from both academic and industrial communities [3][4]. Within an OBS network, an ingress node will gather incoming data (e.g. IP packets) into bursts and each burst is then sent out after its control packet (burst header packet, BHP). The control packet is transmitted on one channel (called the control channel) separated from the channels carrying burst data (called the data channel) and it was sent before its burst data an offset time (Fig. 1). At the intermediate (core) nodes (from source to destination), the control packet will reserve the necessary resources for its data burst coming later. When arriving at the egress node, the original data will be retrieved from the data burst and sent to their destination. Scheduling is considered one of the important operations in OBS networks. When a burst arrives at a node, depending on the burst destination, the corresponding resources at output, including the wavelength which carries the arriving burst and the position (timeslot) on which the burst wants to be scheduled, will be provided. However, if there is no resource available at the output, for example if the wavelength carrying the burst is unavailable, or there is no position to schedule the burst, or both wavelength and position are unavailable, the burst will be dropped. In this case, it is called a burst blocking in scheduling. Similar to the methods of contention resolution presented in [5], a solution is to use fiber delay links (FDLs), meaning that a blocked arriving burst is put into a FDL buffer (including one or several of fiber delay links) to delay its output (changing the position of scheduling the burst on an output wavelength), with the hope that another available position on the same output wavelength is found after the delay. Another approach is to use a wavelength converter to change the wavelength carrying the current burst to another available wavelength at output. The last solution is deflection routing; this means that the output port of the arriving burst is changed so that the resources, including the wavelength and the position of scheduling the burst, are available. This article focuses on the approach that uses the FDL buffer. The structure of the article is as follows: Section 2 describes the architectures of OBS networks with the use of FDL buffer. Based on these architectures, the algorithms of scheduling integrating with FDLs are presented in Section 3. Through the simulation results on the NS2-obs0.9a package presented in Section 4, the effectiveness of using FDL in scheduling on OBS networks will be analyzed. 2 Architecture of OBS node integrated with FDL As shown in [8], there are two architectures of FDL buffer proposed for an OBS core node: the architecture of FDL located at input (input-buffer) as shown in Fig. 1a and the architecture of FDL arranged in output (output-buffer) as shown in Fig. 1b. 77 (a) (b) Fig. 2. Architecture of an OBS core node with FDLs arranged at input (a) or output (b) [6] In the architecture of FDL located at input, n FDLs corresponding to n data channels (wavelengths) at an input port are used in order to avoid any contention that may occur when a lot of arriving bursts dispute on the same FDL at the same time. FDL 78 buffers can be fixed (including FDLs having the same length), dynamic (including FDLs having different lengths) or hybrid (combination of fixed and dynamic). The delay of a burst may be feed forward, this means that the burst is delayed only once by a FDL, or loop back, it means that the burst is delayed repeatedly on the same FDL. The architecture of FDL buffer allocated at output is similar to the one of input FDL buffer, with the only difference being its placement (at output). 3 Algorithms of scheduling in combination with FDL buffer Based on the architectures of OBS core node integrating with FDLs, the algorithms of scheduling in combination with FDLs were also proposed in [6] and [7]. These scheduling algorithms are classified into two groups: scheduling with or without void filling. The parameters used in the scheduling algorithms are:  LAUTi (latest available unscheduled time): the latest position on the channel i from which resources are available for scheduling.  Void: the idle time between two scheduled bursts on a data channel.  Sa and Ea: the arrival and end time of an arriving burst. Its length is then La = (Ea-Sa).  Si,j and Ei,j: the start and end time of a burst scheduled on the channel i at the position j.  MAX_DELAY: the accepted maximum delay done by a FDL. 3.1 The DFMOC algorithm Fig. 3. A case of the DFMOC algorithm [6] The algorithm of DFMOC (Delay-First Minimum Overlap Channel) [6] belongs to the group of scheduling without void filling. The DFMOC algorithm calculates the overlap 79 of an arriving burst with the scheduled bursts on all available channels and selects the channel with the minimum overlap (i.e. LAUTi-Sa is minimum). If the overlap is greater than or equal to the total of the arriving burst length (La) and the maximal delay capacity of FDL (MAX_DELAY), the burst will be entirely dropped; otherwise, the burst will be delayed in the period of minimum overlap with an appropriate FDL and then scheduled on the selected channel. In Fig. 3, channel D2 was chosen because LAUT2-Sa is minimal. 3.2 The DFMOC-VF algorithm The algorithm of DFMOC-VF (Delay-First Minimum Overlap Channel with Void Filling) [6] belongs to the group of scheduling with void filling. The DFMOC-VF algorithm considers all voids on available channels and selects the void whose overlap is minimal (i.e. Ei,j-Sa is minimum). In the case the overlap is greater than or equal to the total of the arriving burst length (La) and the maximal delay capacity of FDL (MAX_DELAY), the burst will be dropped entirely; otherwise, the arriving burst will be delayed in the period of minimum overlap with an appropriate FDL. In Fig. 4, channel D1 was chosen because E1,2-Sa is minimal. Fig. 4. A case of the DFMOC-VF algorithm [6] 3.3 The BR-WFR algorithm The algorithm of BR-WFR (Burst Rescheduling with Wavelength and Last-hop FDL reassignment) [7] reschedules some scheduled bursts by both reassigning and delaying. As shown in Fig. 5a, burst 7 could not find any available channel for its scheduling. The solution for this case is that burst 5 on channel D2 is rescheduled on channel D3 so that burst 7 can be scheduled on channel D2 (Fig. 5b). 80 (a) (b) Fig. 5. The effectiveness of rescheduling: (a) burst 7 cannot de scheduled; (b) burst 7 can be scheduled by reassigning the wavelength of burst 5 [7] However, the scheduling may also fail if the positions of burst 5 and 6 are as shown in Fig. 6a. The solution for this case is both to delay and reassign the wavelength of burst 5 from channel D2 to D3. (a) (b) Fig. 6. The effectiveness of rescheduling: (a) burst 7 cannot de scheduled; (b) burst 7 can be scheduled by delaying and reassigning the wavelength of burst 5 (source [7]). 3.4 Discussions Clearly, all the three algorithms of DFMOC, DFMOC-VF and BR-WFR require FDL buffers which could delay a burst in variant periods of time depending on the minimal value of (LAUTi-Sa) or (Ei,j-Sa). However, such buffers of dynamic FDLs are ideal and the present optical technology has not yet been able to produced them. It is noted that a kilometer of fiber results in a delay of about 5 microseconds [8]; then a FDL buffer will have a huge size if it is composed of many FDLs of variant fixed-lengths. The only fibers in use now are the buffers of FDLs having the same fixed-length. From the practical constraints, we propose two scheduling algorithms without and with void filling with the fixed FDLs basing on two algorithms of LAUC (Latest Available Unscheduled Channel) [9] and LAUC-VF (Latest Available Unscheduled Channel with Void Filling) [10]. The objective of these proposals is to reduce the number of dropped bursts when an arriving burst cannot find any available resources in scheduling. 3.5 The LAUC algorithm with fixed FDLs Assume that the length of fixed FDLs is MAX_DELAY. Different from the DFMOC algorithm, in which the channel with the minimum overlap is selected for the purpose of 81 the delayed scheduling time being little different from the originally planned time, the LAUC algorithm with fixed FDLs (LAUC-FF) calculates the overlap of an arriving burst on all available channels and selects the channel with the greatest overlap so that the length of this overlap (LAUTi-Sa) is less than or equal to MAX_DELAY. The purpose in this case is to create the minimal void after the scheduling; therefore the bandwidths of channels can be used effectively. If such channel is found, the arriving burst is scheduled into it; if not, the burst will be dropped entirely. The description of the LAUC-FF algorithm is as follows: Step 1: initiate i = 0; sc = -1; overlapmax = ; Step 2: If (i  W) go to step 5; Step 3: If (MAX_DELAY (LAUTi-Sa)) & (LAUTi-Sa > overlapmax) then overlapmax = LAUTi-Sa; sc = i; Step 4: increase i = i+1; go to step 2; Step 5: If (sc ≠ -1) then scheduling the burst on channel sc; Step 6: End. 3.6 The LAUC-VF algorithm with fixed FDLs Similar to the LAUC-FF algorithm, the LAUC-VF algorithm with fixed FDLs (LAUC- VF-FF) calculates the overlap of an arriving burst on all available channels and selects the channel with the greatest overlap so that the overlap length (Ei,j-Sa) is less than or equal to MAX_DELAY. The purpose of the LAUC-VF-FF algorithm is to produce a minimum void after scheduling; therefore the bandwidths can be utilized more effectively. It is noted that the void must be large enough so that the delayed arriving burst can be scheduled on (Si,j+1≥ Ea+MAX_DELAY). If a channel satisfying these conditions is found, the arriving burst will be scheduled on that channel; otherwise, the burst will be dropped. The description of the LAUC-VF-FF algorithm is as follows: Step 1: initiate i = 0; sc = -1; overlapmax = ; Step 2: If (i  W) go to step 5; Step 3: Find a void on channel i so that (Si,j+1>=Ea+MAX_DELAY) & (MAX_DELAY(Ei,j-Sa)) If (Ei,j-Sa>overlapmax) then overlapmax = Ei,j-Sa; sc = i; Step 4: increase i = i+1; go to step 2; Step 5: If (sc ≠ -1) then scheduling the burst on channel sc; Step 6: End. 82 4 Simulation and analysis The impact of FDLs in scheduling is simulated on the package OBS 0.9a [11] in the environment of network simulator NS2 [12]. A network topology similar to the NSFNet network is established with 14 core nodes (Ci, i = 14 .. 27), each of which connects to an edge node (Ei, i = 0. .13) to gather data streams from externals, as shown in Fig. 7. The data streams are generated between pairs of nodes Ei and Ej (i, j = 0 .. 13), according to the Poisson distribution. These data streams are density to generate the bursts which arrive at an intermediate node at variant times. By that way, the gaps created between two successive arriving bursts are diverse so that the advantages of the algorithms appear evidently. Fig. 7. Topology of simulated OBS network similar with NSFNet Simulation results in Fig. 8 have shown that both the LAUC-FF and the LAUC- VF-FF have the number of dropped bursts fewer than that of the LAUC and LAUC-VF, when considering in the entire network and at a particular node, e.g. C17 (as shown in Fig. 8a). However, the delays of LAUC-FF and LAUC-VF-FF are greater than the LAUC and LAUC-VF, due to the use of an FDL (as shown in Fig. 8b). 30.00 32.00 34.00 36.00 38.00 40.00 42.00 44.00 46.00 LAUC LAUC-FF LAUC-VF LAUC-VF-FF D ro pp ed /s en t b ur st s Entire netw ork At C17 (a) 83 2.2 2.21 2.22 2.23 2.24 2.25 2.26 LAUC LAUC-FF LAUC-VF LAUC-VF-FF B ur st d el ay (m s) Entire netw ork (b) Fig. 8. Comparison of the rate of dropped-over-sent bursts and the delay between the algorithms of LAUC, LAUC-FF, LAUC-VF, LAUC-VF-FF. When increasing the number of FDLs used at each core node, the number of dropped bursts decreases significantly (as shown in Fig. 9a). This is evidently because the contention at an output port is resolved, but the delay of burst transmission will be longer (as shown in Fig. 9b). 30.00 32.00 34.00 36.00 38.00 40.00 42.00 44.00 1 FDL 2 FDLs 3 FDLs 4 FDLs D ro pp ed /s en t b ur st s Entire netw ork At C17 (a) 2.2 2.21 2.22 2.23 2.24 2.25 2.26 1 FDL 2 FDLs 3 FDLs 4 FDLs B ur st d el ay (m s) Entire netw ork (b) Fig. 9. Comparison of the rate of dropped-over-sent bursts and the delay when increasing the number of FDLs The effectiveness of FDLs in scheduling depends also on the length of FDLs used. In the case of LAUC-FF, the safe delay of an arriving burst which overlaps with another scheduled burst is the double of its length (MAX_DELAY=2La), as shown in Fig. 10a, and this is unnecessary to be longer because of the ineffectiveness of 84 exploiting the bandwidth of wavelength channels. But in the case of LAUC-VF-FF, it attention must be paid to the void length to schedule an arriving burst. As shown in Fig. 10b, an arriving burst cannot find any free location for scheduling, so it is put into a FDL with the hope to find another free location after a delay. However, by delaying MAX_DELAY, it is no free location because of being overlapped with another scheduled burst, whereas there is an available void for the burst if it is delayed a time shorter than MAX-DELAY. The safe delay of an arriving burst in this case is then: aa a LDELAYMAXL v 2_1  where va is the average rate of bursts arriving at a node and La is the average length of bursts. (a) the case of LAUC-FF (b) the case of LAUC-VF-FF Fig. 10. (a) the safe delay of an arriving burst MAX_DELAY is 2La and (b) No free location is found after the delay of MAX-DELAY, while there is an available void if the contended burst is delayed a time ε (ε<MAX-DELAY) 5 Conclusion The article has presented the role of fiber delay lines in scheduling in optical burst switching networks. In fact, scheduling an arriving burst should not be done if the resources at output port (including a free wavelength and a position to schedule the burst) are unavailable. To solve this congestion, the use of FDLs is a solution to change (to delay) position to be scheduled of the burst to a new location available. However, due to some limitations of current optical technologies, the buffer of dynamic FDLs has not yet existed, but only the FDLs of fixed lengths can be used. This has caused difficulties when applying the scheduling algorithms that require the dynamic FDL buffers. We therefore proposed two scheduling algorithms with fixed FDLS and demonstrated the effectiveness of this combination through the simulation results on NS2-obs. We have also shown how to determine the appropriate length for FDLs. This is important in designing burst switching nodes with fixed FDL buffer. 85 References 1. M. Yoo and C. Qiao, A high speed protocol for bursty traffic in optical networks,” SPIE’s All-Optical Communication Systems: Architecture, Control and Protocol Issues, vol. 3230, (1997), 79–90. 2. C. Qiao and M. Yoo, Optical burst switching (OBS)-a new paradigm for an optical internet, Journal High Speed Networks, vol. 8, (1999), 69–84. 3. Y. Xiong, M. Vandenhoute, and H.C. Cankaya, Control architecture in optical burst- switched WDM networks, IEEE Journal on Selected Areas in Communications, vol. 18, (2000), 1838–1851. 4. L. Xu, H. Perros, and G. Rouskas, Techniques for optical packet switching and optical burst switching, IEEE Communications Magazine, vol. 39, no. 1, (2001), 136–142. 5. C.M. Gauger, M. Kửhn and J. Scharf, Comparison of Contention Resolution Strategies in OBS Network Scenarios, 6th International Conference on Transparent Optical Networks ICTON 2004, July 4-8, 2004, Wroclaw, Poland. 6. V.M. Vokkarane, G.P.V. Thodime, V.U.B. Challagulla, and J.P. Jue, Channel Scheduling Algorithms using Burst Segmentation and FDLs for Optical Burst-Switched Networks, in Proceedings, IEEE International Conference on Communications (ICC), 2003. 7. Tan, M. Gurusamy and B. Wang, Burst Rescheduling with Wavelength and Last-hop FDL Reassignment in WDM Optical Burst Switching Networks, In Proceedings of IEEE ICC, volume 2, (2003), 1448-1452. 8. K. Laevens, M. Moeneclaey and H. Bruneel, Queueing analysis of a single-wavelength Fiber-Delay-Line buffer, Telecommunication Systems, 2006, Vol. 31, No. 2-3, 259- 287. 9. Y. Xiong, M. Vandenhoute, and H. Cankaya, Design and analysis of optical burst- switched networks, in Proc. SPIE’99 Conf. All Optical Networking:Architecture, Control, Management Issues, vol. 3843, Boston, MA, Sept. 19-22, (1999), 112–119. 10. Y. Xiong, M. Vandenhoute, and H.C. Cankaya, Control architecture in optical burst- switched wdm networks, IEEE Journal on Selected Areas in Communications, vol. 18, (2000), 1838–1851. 11. Obs-ns Simulator. 12. Ns2 Simulator.