Research of the fairness control in optical burst switching networks

s inherited the advantages from the two others, where no optical buffer and high-speed optical switche are needed. 1.2 Communication principle of OBS networks In OBS networks, different types of incoming data are aggregated into data bursts before being sent (Figure 1.2a). At egress nodes, the bursts will be disassembled into original packets which are then delivered to their destination (Figure 1.2b). Figure 1.1 The process of assembling and disassembling at the edge OBS nodes 1.3 Operations within OBS networks 1.3.1 Assembling Burst assembling is a method of aggregating packets (such as IP packets, ATMs, etc.) from different access networks into larger burst at ingress nodes of the OBS network. 1.3.2 Signaling There are two main types of signaling protocols in OBS networks: JIT and JET, in which JET is the signaling protocol implemented for most OBS networks because it makes better use of the bandwidth. 5 1.3.3 Scheduling When a control packet arrives at a core node, a scheduling algorithm is called to schedule its following burst on an output link. There are three main scheduling mechanisms: (1) scheduling without void filling; (2) scheduling with void filling and (3) group scheduling. 1.3.4 Contention resolution As with any packet-switched network, contention also appears in OBS networks. That is when two burst simultaneously dispute the same resource at the same link (wavelength). Possible solutions to contentions in OBS networks include: wavelength conversion, using FDL, deflection routing and combination of the above solutions. 1.4 Fairness issues in OBS networks 1.4.1 The fairness concept in OBS networks According to Denda et al. [38], fairness is known as the satisfaction of individuals in the process of resource allocation. In the OBS network, fairness issues are distinguished by: delay fairness, throughput fairness and distance fairness, which are considered at edge and core nodes (Figure 1.7). FAIRNESS IN OBS NETWORKS EDGE NODES CORE NODES DELAY FAIRNESS THROUGHPUT FAIRNESS DISTANCE FAIRNESS Figure 1.7 Fairness classification based on consideration location 1.4.2 Delay fairness Fairness delay refers to establishing fairly a buffering delay (including assembling delay and offset time) for bursts of different QoS classes. 6 1.4.3 Throughput fairness Throughput fairness refers to the fair allocation of bandwidth between flows which share the same link. 1.5 Summary chapter 1 This chapter has introduced an overview of OBS networks and its operations, in which the burst assembly at the ingress node is focused on analysis because it plays an important role in the fairness of entire network. This chapter has also analyzed and evaluated the methods of fairness control that have been published so far. That is the basis for the thesis to identify the research objectives, as well as propose the improved architecture of ingress node with additional functional modules to ensure the implementation of the fairness solutions proposed by the thesis. 1.5.1 Distance fairness Distance fairness refers to dealing with contentions fairly (as measured by the data loss rate) based on the path length (number of hops) from source to destination. 1.6 Research objectives The thesis focuses on the fairness issues at the ingress node to improve the efficiency of delay and throughput fairness, with four main objectives: 1. Improving and proposing new solution of burst assembly for delay reduction that applies to each individual queue. 2. Improving and proposing new solution of delay fairness control that applies to multiple queues with different QoS levels. 3. Improving and proposing new solution of throughput fairness control that applies to flows of Poisson and Non-Poisson distribution. 4. Proposing new solutions of burst padding to improve communication performance. 7 CHAPTER 2: BURTS ASSEMBLY FOR DELAY REDUCTION AND DELAY FAIRNESS 2.1 Model of burst assembly for delay reduction 2.1.1 Issue of the burst assembly delay The end-to-end delay of a burst transmitted over an OBS network is mainly caused by four components: (1) the assembly delay at ingress node, (2) the offset time for resource reservation of the control packet, (3) burst switching delay at core nodes and (4) propagation delay over core network. Two first delays are collectively formed a common element which há the name the buffering delay; two latters usually do not change corresponding to a given implemented protocol. Therefore, the proposals usually focus on reducing the buffering delay. 2.1.2 Related works 2.1.2.1 Analysis of the published methodes of burst assembly for delay reduction There are 6 published methodes of burst assembly for delay reduction as shown in Table 2.1. Table 2.1 Comparison of the published methodes of burst assembly for delay reduction IE-BADR POQA JK-BADR BADR-EAT MTBA-TP BASTP Burst assembly method Timer-based Timer- based Timer- based Timer-based Hybrid Hybrid Assembly threshold fixed fixed fixed fixed fixed addaptivei Estimation method Based on the average speed of packets arriving in the estimated time period Based on the length of the last M bursts Based on the estimated error of the previous assembly Based on the density of the last M packets Based on the arrival speed of the last packet Based on M last burst assemblies Reduced delay To To To To t1 + To – Ta To 8 2.1.2.2 Comparison and analysis of simulation results Simulation is done with the following objectives:  Comparing the average estimattion error rate (Formula 2.8) between the methodes of burst assembly for delay reduction. (2.8) where M is the number of assembly times, e jL and Lj are the estimation size and the completed size of burst j.  Comparing the number of redundant packets transferred for the next burst of 100 consecutive assembly times between the methodes of burst assembly for delay reduction.  Analyzing the way to select the thresholds for BASTP, the best methode of burst assembly for delay reduction. The simulations are installed on a PC with 2.4 GHz Intel Core 2 CPU, 2G RAM. Packets arriving at the ingress node have a Poisson distribution with exponentially random size in the range of [500, 1000] bytes. Traffic loads ariving at the queues varies from 0.1 to 0.9. Simulations are performed in 1 second). Data were extracted from NS2 [71] with support package obs-0.9a. Other parameters include Ta = 6 ms, To = 2 ms a. Comparison of the average estimation rate Figure 2.3 shows a comparison of the average estimation error between the methods of burst assembly for delay reduction. The simulation results show that the estimation error of the statistical-based methods such as BASTP, BADR-EAT and POQA being lower than that of other methods. Figure 2.3 Comparison of the average estimation error rate of IE-BADR, JK-BADR, POQA, BADR-EAT, MTBA-TP and BASTP with normalized load to 0.5   M LLL R M j j e jj E     1 / 9 b. Comparison of the number of redundant packets transferred for the next burst Figure 2.6 Comparison of the number of redundant packets in 100 consecutive assembly times. c. Analizing the way to select the thresholds for BASTP As described in Figures 2.3 and 2.6, BASTP always gives the best simulation results. However, these results is often accompanied by a pairs of suitable selected threshold value (Lmin, Lmax). 2.1.2.3 Comments The above analysis, comparisons and evaluations (published in [CT1]) are the basis for proposing the improvements of burst assembly for delay reduction which are presented in the following sections. 2.1.3 Method of burst assembly for delay reduction iBADR 2.1.3.1 Introduction to the incoming traffic estimation method TW-EWMA To estimate the incoming traffic at a queue, Salad et al. [23] proposed the TW-EWMA method. Unlike other estimation methods that often count incoming packets at continuous observation intervals (estimation cycles), TW- EWMA only counts in a smaller estimation time window (Tw) to reduce the calculation cost (Figure 2.7). TW1 TW2 TW3 TWn Times a estimated cycle a estimated cycle Figure 2.1 The estimation time windows in TW-EWMA 2.1.3.2 Method of burst assembly for delay reduction iBADR The iBADR (improved Burst Assembly for Delay Reduction) method is also based on the idea of sending the control packet early at the time oa TTt 1 (Ta > To) and the corresponding burst is sent at the time aTt 2 10 ; As a result, the delay of packets carried in the current burst is reduced a period To. The thesis uses TW-EWMA [23] to estimate the arriving packet rate, thereby estimating the completed burst size. The authors in [23] set α to a fixed value (equal to 0.3), which does not in fact reflect the abnormal changing nature of the incoming traffic; The result is a significant estimation error. The thesis proposes to change α in a flexible way according to the ratio of current rate (cur) and average rate (λavg) of incoming packets as Formula 2.12. curavg cur avg cur          1 (2.12) In order to increase the accuracy of the estimation, the thesis flexibly adjusts the time threshold based on the average estimation error of the previous burst assembly times according to Equation 2.13. L LL RR e E )( )1(    (2.13) 2.1.3.4 Comparison and analysis of simulation results The simulation parameters for this part are similar to Section 2.1.2.2. a. Comparison of the average estimation error rate The results in Figure 2.8 show that iBADR has the smallest estimation error rate. Figure 2.8 Comparison of the average estimation error rate between iBADR and previous methods b. Comparison of the number of redundant packets in 100 consecutive assembly times Figure 2.10 shows a comparison on the number of redundant packets 11 between iBADR and previous methods, where the number of redundant bursts of iBADR is significant. Figure 2.10 Comparison of the number of redundant packets in 100 consecutive assembly times. 2.1.3.5 Comments Based on simulation results, iBADR achieved a estimation error rate lower than that of BASTP, but it generates relatively many redundant packets as shown in Figure 2.10. The method of burst asembly for delay reduction iBADR has been published in [CT2]. 2.1.4 Method of burst assembly for delay reduction OBADR 2.1.4.1 Description The OBADR (Optimal Burst Assembly for Delay Reduction) method is an improvement of iBADR, in addition to applying the burst length estimation method TW-EWMA with flexibly adjusted , the burst assembly process is a combination of the 2 assembly stages:  Stages 1: When the first packet arrives at a queue, the timer of the queue is triggered. The control packet is only sent to the core network when the timer reaches the threshold Tw, which is the size of the time window. The estimated length ( eL ) is also calculated based on TW- EWMA with flexibly adjusted .  Stages 2: The burst assembly process continues, but now based on the estimated length threshold. The burst is only completed when the number of packets arriving in the queue reaches the threshold eL . 2.1.4.3 Comparison and analysis of simulation results The simulation parameters for this part are similar to Section 2.1.2.2. 12 a. Comparison of the average estimation error rate Figure 2.11 shows that the average estimation error rate ( ER ) of OBADR is lower than that of all previous methods. Figure 2.11 Comparison of the average estimation error rate between OBADR and previous methods b. Comparison of the number of redundant packets in 100 consecutive assembly times Figure 2.13 Comparison of the number of redundant packets in 100 consecutive assembly times. As shown in Figure 2.13, OBADR does not generate redundant packets. This is due to the estimated lengths used as the length threshold in burst assembly. 2.1.5 Effect of the factor α on OBADR 2.1.5.1 Investigating the variation of α depending on the load changes With the normalized load changing from 0.1 to 0.9 and α changing from 0.1 to 0.9, the simulation results show that the estimation error is minimum when α has a distribution in the range of (0.4, 0.6). Thus, the fixed α setting is clearly not suitable when arriving load is varied. 13 2.1.5.2 Comparing the burst assembly efficiency when α is fixed and varied Simulation results show that dynamic α results in a better average estimation error than fixed α (α = 0.5) when the assembly time is small (from 2.5 ms to 5.5 ms). 2.1.5.3 Comments Based on the simulation results, flexible adjustment of α values (such as Equation 2.12) depending on the incoming traffic rate has increased the efficiency of estimating the complete burst length. This result also confirms the effect of flexible adjustment of α according to the incoming traffic rate. The results of this study were published in [CT4]. 2.1.6 Effect of OBADR on scheduling 2.1.6.1 Analyze the effect of OBADR on scheduling based on Engset method 2.1.6.2 Comparison of the analysis model and simulation result As shown in Figure 2.19, OBADR achieves a lower probability of burst loss compared to the traditional model in theory and simulation. Figure 2.2 Comparison on the probability of burst loss between OBADR and traditional model 2.1.6.3 Comments Based on the analysis and simulation results, OBADR has proven to be the most efficient burst assembly method in term of low estimation error, reduced delay and minimized burst loss rate. The method of burst assembly for delay reduction OBADR was published in [CT3]. 2.2 Model of burst assembly for delay fairness 2.2.1 Related works The models of burst assembly for delay reduction share a common idea of sending the control packet early before the burst is completed. Among these 14 models, only POQA [69] is associated with service differentiation. Specifically, the authors in [69] have set different offset times for bursts with different priority classes and adjusted the assembly times so that the higher priority burst is, the shorter the buffering time. As the example shown in Figure 2.21, the burst with the highest priority class class0 has the smallest assembly time Ta(0) and the largest offset time To(0), while the lowest priority class class2 has the longest assembly time Ta(2) and the smallest offset time To(2). class0 class1 class2 Ta(2) To(2) Ta(1) To(1) Ta(0) To(0) Figure 2.3 An example of time thresholds and offset times for 3 classes 2.2.2 Method of burst assembly for delay fairness BADF 2.2.2.1 Introduction to the delay fairness in OBS networks With the concept of delay fairness proposed in [69], higher priority burst will have a shorter buffering time. However, this interpretation has not yet shown the nature of the fair response to individuals in the notion of fairness. Therefore, the thesis supplements the concept of delay fairness as follows: Delay fairness is the satisfaction on delay between different priority bursts, such that the average ratio of the end-to-end delay to their limited delay is approximative. In addition, in order to meet the requirement for prioritizing delays in OBS networks, the following two constraints were added. 1. The higher the priority is, the lower the end-to-end delay is; and 2. The end-to-end delay of a burst is not greater than its limited delay (Example: RTT of IP packets carried in a burst). Thus, the concept of "delay fairness" added by the thesis implies the concept of delay fairness proposed in [69]. 2.2.2.2 Index of delay fairness Let D(i) be the average delay that packets must wait in queue i before being aggregated into a burst and Ta(i) is the assembly time of queue i, xi = D(i)/Ta(i) will reflect the delay of the packets in queue i. The thesis proposes a formula to calculate the DFI delay fairness index for different priority bursts based on 15 Jain's formula in [39] as follows:       n i ii n i ii xn x DFI 1 2 2 1 )(  (2.22) Fairness will increase as DFI approaches 1, and equals 1 when nn xxx   ...2211 , where i is the weight of xi, 0 < i < 1 and 1 1   n i i  . 2.2.2.3 Method of 2-stage burst assemly The Burst Assembly for Delay Fairness (BADF) method is also based on the idea of sending control packets early (see Section 2.1.3 and 2.1.4), but adding new points in the 2-stage assembly model. Stage 1 is a estimated time threshold-based burst assembly and Stage 2 is a estimated length threshold- based burst assembly. The 2-stage assembly model is in detail as follows: Stage 1: when the first packet arrives at queue i, the timer is triggered. The control packet is only sent when the timer reaches the estimated time threshold Te(i) = Ta(i) – To(i). The estimated burst length is calculated based on the TW- EWMA method [23]:  )()()())(1()()( iiiiiTiL curavgae   (2.25) During this period, the value of α(i) is adjusted to increase/decrease depending on the rate of packet arrival at queue i, calculated by α(i) = cur(i)/(avg(i) + cur(i)), instead of being fixed as in [23] Stage 2: the burst assemly algorithm continues until either the length threshold )(iL e or time threshold Ta(i) is reached. 2.2.2.5 Comparison and analysis of simulation results Assuming that incoming packets belong to three priority classes (K = 3), have Poisson distribution and have exponential distribution sizes in the range [500, 1000] bytes; three priority queues 1, 2 and 3 are therefore used with the offset times set to 0.3, 0.2 and 0.1 (ms), respectively. Simulation objectives include:  Comparing the DFI index between BADF and POQA;  Analyzing the impact of the delay fairness on the assembly time Ta(i) and the buffering delay; 16  Comparing the estimation error (Formula 2.8) between BADF and POQA. a. Comparison of the DFI index between BADF and POQA Figure 2.4 Comparison of the DFI index between BADF and POQA b. Analyzing the impact of the delay fairness on the assembly time Ta(i) and the buffering delay As shown in Figure 2.25, the assembly time Ta(i) decreases as the incoming traffic of packets increases, with class0 during the simulation period [0.4, 0.6] and with class2 during the simulation period [0.7 , 0.9]. Figure 2.5 Comparison of Ta(i) between 3 priority classes with BADF c. Comparison of the estimation error between BADF and POQA. Figure 2.60 Comparison of the estimation error between BADF and POQA 17 Figure 2.30 shows a comparison of the estimation error rate (Formula 2.8) between BADF and POQA, where the estimation error of BADF is much smaller than that of POQA. Figure 2.7 Comparison of the bandwidth wasting rate between BADF and POQA Figure 2.8 Comparison of re-send rate between BADF and POQA 2.2.2.6 Comments The BADF algorithm has been proven to effectively control the delay fairness between different QoS queues, based on DFI index, estimation error, and re-send rate. One drawback of BADF, however, is the high bandwidth wastage rate about 12% on average (Figure 2.31). However, if compared with the re-send rate of POQA (about 30% on average), BADF is better. The BADF algorithm and the above results have been published in [CT5]. 2.3 Summary chapter 2 This chapter presents two proposed models of delay reduction iBADR [CT2] and OBADR [CT3], and a model of delay fairness BADF [CT5]. Based on simulation results, iBADR and OBADR achieve lower delay than previous proposals. BADF also achieves the delay fairness which is almost optimal, while reducing the delay and minimizing the estimation error on the queues. 18 CHAPTER 3: THROUGHPUT FAIRNESS BASED ON BANDWIDTH ALLOCATION AND BURST PADDING 3.1 Model of bandwidth allocation with throughput fairness 3.1.1 Introduction to fair bandwidth allocation Fair bandwidth allocation, also known as rate fairness, refers to allocating bandwidth for connections proportional to the provided bandwidth to the available bandwidth [53]. 3.1.2 Related works So far, the models of fair bandwidth allocation in OBS networks are based on the max-min fair bandwidth allocation model in IP networks [16], such as MMFP and RFP. 3.1.3 Bandwidth allocation with throughput fairness TFBA 3.1.3.1 Architecture of the ingress node supporting QoS Consider an ingress node with an architecture as shown in Figure 3.3. Figure 3.1 Architecture of the ingress node supporting QoS 3.1.3.2 Maximum bandwidth ratio for each link in OBS networks Table 3.1 Maximum throughput rate per link with different normalized loads Normalized load 0.5 0.6 0.7 0.8 0.9 1.0 Maximum throughput 0.48616 0.572186 0.67152 0.72123 0.7213 0.71945 3.1.3.3 Description of TFBA The idea of TFBA is to adjust actual throughput close to the fair allocation bandwidth to ensure fair bandwidth allocation between flows. The process of allocating bandwidth with fairness throughput includes 4 steps: Step 1: Determine the fairness rate Fi for each connection 19 If the incoming traffic of flow i varies significantly, the bandwidth is first divided among the connections, the ratio Fi of each connection is determined as the minimum of the actual throughput (Ai) and the fairly allocated bandwidth. Connections with actual throughput less than the allocated bandwidth will not participate in the redundant bandwidth sharing process in the next time. The allocation is continued until the allocated bandwidth (m) does not change from the previous time (m = mprev) or all connections are satisfied (m = 0). Step 2: Determine the fairly allocated bandwidth ABi for each connection Let Bw be the maximum output bandwidth, the fair allocation bandwidth for connection i is determined by Equation 3.4 BwFAB ii  (3.4) where Fi is the fairness ratio determined in Step 1. Step 3: Measure the actual throughput ATi of each connection Actual throughput is determined by Formula 3.5 )(/)( iTipAT wwi  (3.5) where pw(i) is the number of packets arriving in the time window Tw(i). Step 4: Handling burst contention The burst contention problem is resolved based on a comparison between ATi and ABi to determine whether the incoming burst is in an overrate (overloaded) flow. If ATi > ABi, the incoming burst is in an overrate flow and will be dropped to reserve resources for the bursts in an underrate (unoverloaded) flow. Conversely, if ATi < ABi, the arrival burst is in underrate flow and the ratio ATi /ABi will be considered. If the value of ATi /ABi is smaller than that of ATj/ABj, the scheduled burst will be dropped. Conversely, if the value of ATi /ABi is greater than ATj/ABj, the incoming burst will be dropped. 3.1.3.4 Index of throughput fairness The fair bandwidth allocation approach proposed by the thesis also comes from the idea of max-min fairness, but based on the ratio between actual throughput and provided bandwidth, instead of probability of loss. as in [67], [53]. Specifically, set yi = ATi / ABi is the ratio between the actual throughput (ATi) and the fair allocation bandwidth (ABi) of flow i. Based on Jain's formula in [39], the thesis proposes the throughput fairness index (TFI) as follows: 20       n i ii n i ii yn y TFI 1 2 2 1 )(  (3.6) where σi is the weight that represents the actual used bandwidth compared to the provided bandwidth between the flows, 0 < σi < 1 and 1 1   n i i  . 3.1.3.6 Comparison and analysis of simulation results Simulation objectives include: - Comparing the byte loss rate between connections and the average byte loss rate among TFBA, MMFP and RFP - Comparing the fairness based on TFI among TFBA, MMFP and RFP. Because the simulation objective only considers the byte loss rate of the connections which share the same (or group of) output link(s), the Dumbbell simulation network as shown in Figure 3.5 is sufficient to evaluate the effectiveness of the proposed algorithm. Figure 3.2 Simulation network topology a. Comparison of the byte loss rate between connections Figure 3.3: Comparison of the byte loss rate between 3 connections with TBFA in 2 cases: (1) The total load does not exceed the link capacity and (2) the load of connection 3 spikes beyond the link capacity 21 Figure 3.4 Comparison of the average byte loss rate on 3 connections of TFBA, RFP and MMFP b. Compar