Open Access
Add to BibSonomyAbstract
In order to solve the differentiated service problem in optical burst switching (OBS) networks, we propose a dynamic fiber delay line (FDL) bank partitioning algorithm, which divides a FDL bank into several groups, using a feed-forward output buffering architecture. In the analysis, three classes and groups are considered for traffic and FDL, respectively, and each group is assigned to each class. This paper shows that the loss differentiation in OBS networks is easily accomplished in Poisson traffic environments when our dynamic algorithm is adopted.
©2007 Optical Society of America
1. Introduction
OBS technology is being studied in order to provide an optical Internet backbone. In OBS, data is transported in various-size units, called bursts [1]. Also, in OBS, there is a strong separation between the control and data planes, which allows for great network manageability and flexibility. In addition, its dynamic nature leads to high network adaptability and scalability, which makes it quite suitable for transmission of bursty traffic.
Although OBS has received considerable attention in the past few years, there are still a lot of challenging problems to be solved in respect of the edge routers, offset time decision and the burst assembly mechanism [2]. On the other hand, core routers need protection and restoration mechanisms [3], and a contention resolution scheme [4]. Additionally, one of the most important issues is the need for service differentiation schemes for various applications. Various QoS mechanisms have been proposed for OBS networks [5, 6, 7, 8].
In our paper, FDLs are used to achieve service differentiation, especially loss differentiation, between classes. In order to accomplish loss differentiation, we propose a dynamic FDL partitioning algorithm which can efficiently support loss differentiation. The FDLs are dynamically partitioned depending on QoS requirements. Furthermore, the FDL reservation policies of each class are different.
The paper is organized as follows. Section 2 shows buffering architectures. Section 3 displays our algorithm and calculates the loss probabilities of each class. Section 4 compares the analyzed results with those obtained through extensive simulations. Finally, section 5 concludes the paper.
2. Buffering architecture
In this paper, we assume that all architectures do not have any wavelength converters. Optical buffers can be classified into feed-forward and feedback architecture [9, 10]. In a feed-forward architecture, each delay line connects an output port of a switching element at a given stage to an input port of another switching element in the next stage. In a feedback architecture, each delay line connects an output port of a switching element at a given stage to an input port of a switching element in the same stage or a previous stage. Also, according to the position of the buffers, optical buffers are categorized into three major configurations: input buffering, output buffering, and shared buffering [9]. While buffers are dedicated for each input and output port in input and output buffering, respectively, they can be shared by all switch ports in shared buffering. Among all buffering architectures, input buffering is never proposed for optical implementation due to its poor performance [11].
Due to sharing the same buffer by bursts headed for different output ports in shared buffering architectures, the calculation complexity of buffer performance can be very high [9, 10]. Therefore, as shown in Fig. 1, we only consider a feed-forward output buffering architecture. In the architecture, each wavelength has a dedicated FDL bank, which consists of many FDLs, and a direct FDL, which has a zero delay value. With sufficiently large buffers, a feed-forward output buffered switch can achieve the best possible burst loss performance. Sometimes, if the buffer size is arbitrarily large, then burst loss can be zero [11]. However, increasing the buffer size is limited in practice because large buffers will increase the cost of FDLs. Nevertheless, because a switch fabric is assumed as non-blocking in the most cases, the numerical analysis of FDL buffers can be easily made in this architecture [9, 12].
In addition to the buffering architectures, the burst forwarding performance can be affected by two major issues [9]. The first issue is the distribution of the lengths of the FDLs. FDL buffers can be configured as either degenerate buffers (linear increment of delay line lengths) or non-degenerate buffers (non-linear increment of delay line lengths). Degenerate means that the lengths of FDLs are consecutive multiples of a certain delay unit (D), but non-degenerate means that the lengths of FDLs can be an arbitrary set that does not require consecutive multiples of a certain delay unit (D).
Another important factor is the burst forwarding policy. Generally, there are two kinds of scheduling policies: void-filling and non-void-filling. In OBS networks, voids may occur because the FDLs can provide only a fixed amount of delay. With a void-filling policy, an incoming packet can be switched to any FDL, as long as there is no contention at the output port. As a result, the FIFO (First-In-First-Out) discipline of certain output ports may be violated.
Although the output buffering architectures require a significantly greater amount of FDLs than the shared buffering architectures, the output buffering architecture is considered. Also, we consider a degenerate FDL length configuration and a non-void-filling scheduling scheme. So, the length of the ith FDL is i × D and bursts are scheduled in a FIFO (non-void filling) manner. When a burst arrives, it can be forwarded to the first available buffer with minimum delay, ensuring the FIFO ordering discipline. Also, we assume that the switch fabric are non-blocking, and that the processing process for burst header packets (BHPs) is exponential.
3. Dynamic FDL bank partitioning scheme
3.1. Algorithm
We assume that the OBS nodes have N FDLs, that there are n classes, where class 1 is the highest class and class n is the lowest one, and that they do not have any wavelength converters.
From Fig. 2, when a BHP of class i arrives, the node identifies whether or not the available FDLs exist within FDL group i. If the available FDLs are found, then the node checks the validation of the FIFO ordering discipline. If there are no FDLs available within the group, or the FIFO ordering discipline is violated, the node continuously checks the next group up to the group n. If the available FDLs do not exist, the loss probability of class i, PBim, is increased. If PBim is greater than the target loss probability of the class, PBit, the over-indicator-counter of the class, OIi, is increased and is compared with the over-threshold-indicator of the class, OTi. If OIi is greater than OTi, then the number of FDLs of the class, which is defined as NFi ({(NF 1,NF 2,… ,NFn)∣Σn i=1 NFi = N}), is increased by one and the number of FDLs of the class n, NFn, is decreased by one. However, if NFi has already reached the maximum value, which is defined as NFmaxi, or NFn has already reached the minimum value, NFminn, the node cannot run the configuration process because of a starvation problem.
On the other hand, from Fig. 2, when an available FDL is found, PBim is compared with PBit. If PBim is less than PBit , then the under-indicator-counter, UIi, is increased by one and is compared with the under-threshold-indicator, UTi. If UIi is greater than UTi, then NFi is decreased by one and NFn is increased. However, if the NFi has already reached the minimum value, NFmini, the node cannot run the configuration process.
Because burst ordering sequence should be maintained, void-filling reservation schemes, such as LAUC-VF (Latest Available Unused Channel with Void Filling) [13], can not be applied in our algorithm. However, other reservation schemes, such as LAUC (Latest Available Unscheduled Channel) [14], which schedules the bursts on channels resulting in the minimum gap and maintains burst ordering sequence, can be applied.
3.2. Loss probability analysis
Under the assumption that the arrival process is Poisson with rate λ and there are k FDLs, we can determine the loss probability of the FDLs as follows [12]
Fig. 3. (a) FDL partitioning scheme to maintain the burst ordering sequence. Group 1 is used by only class 1, group 2 by class 2 and class 1, and group 3 by all classes, and (b) relationship between classes and FDL groups.
where F is the set that consists of {f 0,f 1, … ,fk}, where state fi ∈ F is reached by the buffer when a burst is switched to delay line i and fills the buffer, τfi¯ is the mean residual lifetime of the burst length as follows [12]
and pfi is the steady-state probabilities which can be calculated exactly by numerically solving the balance equations. In the Eq. (2), τ is the length of the last inserted burst and p τfi (τ) is the probability that the buffer will remain in the same state during a time τfi given by the residual lifetime of τ after an elapsed time Dk - Di, where Dk is the length of the FDL k in the group and Di is the length of the FDL i in the same group, as follows [12]
where p τ(∙) is the distribution of τ.
Figure 3(a) shows the FDL partitioning scheme of our algorithm. If i < j, the shortest FDL of FDL group j should be longer than the longest one of FDL group i to maintain the FIFO ordering discipline. We now derive the loss probability of class i, denoted by BPi (i = 1,2,…,n - 1,n). In order to find the loss probability of each class, we should know the blocking probability of each FDL group, denoted by Bi(i = 1,2,…,n - 1,n).
From Fig. 3(b), each Bi can be calculated. Let us derive B 1 for FDL group 1. Since lower classes than class 1 cannot reserve the FDLs within group 1,B 1 is only dependent on the class 1 traffic. So, we can obtain B 1 = f(F 1,λ1) using Eq. (1), where F 1 = {f 0,f 1,…f n1}, and the carried traffic by FDL group 1 is λ1 - λ1 ∙ B 1. For the case of B 2 for FDL group 2, we have to consider two kinds of carried traffic. One is class 2 traffic and the other is class 1 traffic, which did not reserve the FDLs within group 1. The remaining traffic of class 1 should attempt to use the FDLs of group 2. So, we can get B 2 = f{F 2 ,λ2 + λ1 ∙B 1), where F 2 = {f n1+1,f n1+2,…,f n2}, and the carried traffic by FDL group 2 is λ2 + λ1 ∙ B 1 - (λ2 + λ1 ∙B 1) ∙B 2. For the case of Bi for FDL group i, we can obtain the blocking probability as follows
where Fi = {f ni-1+1, f ni-1+2, …, f ni}.
Now we can calculate the loss probability (BPi, where 1 ≤ i ≤ n) of each class using the above equations. In order to fail to send the first class traffic, all groups are blocked. So, BP 1 = ∏n i=1= Bi, and for class 2 traffic, BP 2 = ∏n i=2=Bi. Similarly, we can get the loss probability of class j as follows
4. Performance evaluation
We extensively simulated our algorithm using OPNET simulation tool [15]. The simulation model assumes that all data wavelength channels have the same FDL architecture and number of FDLs, and that there are three classes such as class 1, class 2, and class 3, where class 1 is the highest class and class 3 is the lowest one. Also, we assume that the distribution ratio of class 1, class 2, and class 3 is 10%, 20%, and 70%, respectively, that the target loss probability for class 1 is 10−4 and for class 2 is 10−3, that the transmission rate of each channel is 1 Gbps, and that the burst size distribution is exponential with the average length of 20 Kbits. Steady state conditions are only considered.
Before starting the analysis and simulations, we should find some simulation parameter values such as OT 1 and UT 1 for class 1, and OT 2 and UT 2 for class 2. If the threshold values are large, the fluctuation can be reduced, but the loss differentiation between classes can be degraded because of the insensitive operation of partitioning FDLs. On the other hand, if the small threshold values are used, the target loss probabilities can be easily achieved, but the fluctuation and processing burden increases enormously. Through extensive simulations, we found the optimal threshold values as follows: 2, 50, 20, and 450 for OT 1, UT 1, OT 2, and UT 2, respectively. For the rest of the paper, we use these threshold values. Also, we define NFmini and NFmaxi as 1 and {N - ΣN j=1∣j≠i}, respectively.
All simulations assume that the FDLs are multiples of the constant delay unit, D. So, the length of the 0th FDL is 0 and the ith FDL is i × D. Figure 4 shows the loss probabilities obtained by simulations when N = 31 and 63, and D, which is normalized by the mean burst size, changes. From Fig. 4, we can discover that when 31 FDLs are used, and when the D is less than about 0.45 in the case of 63 FDLs, the overall loss probabilities are always very high, which means that we may not be able to achieve the target loss probabilities for all classes. On the other hand, we can find out that when 63 FDLs are used and the D is greater than about 0.55, the overall loss probabilities are lower than 10−3. From the figure, we can know that our dynamic FDL partitioning algorithm may be meaningless in these two cases. For the rest of the paper, we selected the D as 0.5.
Figure 5(a) shows the loss probabilities of each class as a function of the offered load when 63 FDLs are used. The target loss probability for class 1 is set as 10−4, for class 2 as 10−3, and class 3 is the best-effort service. Also, the FIFO ordering discipline was considered in all scenarios. Firstly, our results (represented as C) are compared with the classless cases (represented as CL). As can be seen in the figure, despite using FDL buffers, loss differentiation is not achieved between classes in classless case. When the offered load is less than 0.5, the loss probabilities of all classes are lower than 10−4. So, the dynamic FDL partitioning algorithm is useless. However, as the offered load is more than 0.5, the loss probabilities of all classes are greater than 10−4. Therefore, in order to accomplish loss differentiation, we should use our algorithm. From the figure, loss differentiation is well achieved, but the loss probabilities of class 3 is increased rapidly and is much higher than those of classless case. This means that loss differentiation is achieved at the expense of the class 3 traffic, the best-effort traffic. Next, the results obtained from numerical analysis (represented as A) are in good agreement with those from the simulations (represented as S). As can be seen by comparing the loss probabilities between all classes, loss differentiation is achieved by taking advantage of our algorithm. However, as can be seen in Fig. 5(a), when the offered load is 0.9, loss differentiation is not achieved perfectly because of a starvation problem.
Fig. 4. Loss probabilities as the function of the delay unit (D) which is normalized by the mean burst size. The offered load is 0.7 and any classes are not considered.
Fig. 5. (a) blocking probabilities for each class when 63 FDLs are used and the D is 10 ∙ 10−6, and (b) number of FDLs when offered load is 0.7, and 63 FDLs are used after system arrives at steady state conditions.
Figure 5(b) shows that the number of FDLs varies according to different classes when the offered load is 0.7. As a result of the algorithm, we can get the number of FDLs for each group while guaranteeing the target loss probabilities and achieving loss differentiation between classes. As can be seen in the figure, the number of FDLs for group 1 is from 8 to 11 and the variation is quite small. However, the number of FDLs for group 2 varies severely from 26 to 52. Again, this figure shows that in order to achieve the target loss probabilities for class 1 and 2, the number of FDLs used by class 3 is relatively quite low while the distribution rate of class 3 is 70% of the total traffic.
5. Conclusion
FDLs and the dynamic FDL partitioning algorithm have been used to achieve the loss differentiation in OBS networks. In order to achieve the loss differentiation in OBS networks, we proposed a dynamic FDL partitioning algorithm and used a feed-forward output buffering architecture. Also, we analyzed the loss probabilities, selected several threshold values and the constant delay unit, and found the optimal number of FDLs for each class. Without our algorithm, all classes have almost the same loss probabilities. However, in our case where FDLs and our algorithm are adopted, loss differentiation is easily achieved. This means that the target loss probabilities can be easily achieved, though the resource of the lowest class was sacrificed considerably.
Acknowledgments
This work was supported by the Korea Science and Engineering Foundation (KOSEF) grant funded by the Korea government (MOST) (No. R11-2000-074-01001-0).
References and links
1. C. Qiao and M. Yoo, “Optical burst switching (OBS)- a new paradigm for an optical internet,” J. High Speed Networks 8, 69–84 (1999).
2. K. Long, R. S. Tucker, and C. Wang, “A new framework and burst assembly for IP DiffServ over optical burst switching networks,” in Proceedings of IEEE GLOBECOM technical conference (IEEE, San Francisco, 2003), 3159–3164.
3. S. Oh, Y. Kim, M. Yoo, and H. H. Hong, “Survivability in the optical internet using the optical burst switch,” ETRI J. 24, 117–130 (2002). [CrossRef]
4. S. K. Lee, K. Sriram, H. S. Kim, and J. S. Song, “Contention-based limited deflection routing in OBS networks,” in Proceedings of IEEE GLOBECOM technical conference (IEEE, San Francisco, 2003), 2633–2637.
5. M. Yoo, C. Qiao, and S. Dixit, “QoS performance of optical burst switching in IP-over-WDM networks,” IEEE J. Sel. Areas Commun. 18, 2062–2071 (2000). [CrossRef]
6. V. M. Vokkarane and J. P. Jue, “Prioritized burst segmentation and composite burst-assembly techniques for QoS support in optical burstswitched networks,” IEEE J. Sel. Areas Commun. 21, 1198–1209 (2003). [CrossRef]
7. C. Loi, W. Liao, and D. N. Yang, “Service differentiation in optical burst switched networks,” in Proceedings of IEEE GLOBECOM technical conference (institute of electrical and electronics engineers, Taipei, 2002), 2313–2317.
8. Q. Zhang, V. M. Vokkarane, B. Chen, and J. P. Jue, “Early drop and wavelength grouping schemes for providing absolute QoS differentiation in optical burst-switched networks,” in Proceedings of IEEE GLOBECOM technical conference (IEEE, San Francisco, 2003), 2694–2698.
9. T. Zhang, K. Lu, and J. P. Jue, “Shared fiber delay line buffers in asynchronous optical packet switches,” IEEE J. Sel. Areas Commun. 24, 118–127 (2006). [CrossRef]
10. D. K. Hunter, M. C. Chia, and I. Andonovic, “Buffering in optical packet switches,” IEEE J. Lightwave Technol. 16, 2081–2094 (1998). [CrossRef]
11. M. J. Karol and M. G. Hluchyj, “Input versus output queueing on a space-division packet switch,” IEEE Trans. Commun. 35, 1347–1356 (1987). [CrossRef]
12. R. C. Jr. Almeida, J. U. Pelegrini, and H. Waldman, “Delay-line buffer modeling for asynchronous optical networks,” in Optical networking and communications, A. K. Somani and Z. Zhang, Eds., Proc. SPIE5285, 381–391 (2003). [CrossRef]
13. Y. Xiong, M. Vandenhoute, and H. C. Cankaya, “Control architecture in optical burst-Switched WDM networks,” IEEE J. Sel. Areas Commun. 18, 1838–1851 (2000). [CrossRef]
14. J. S. Turner, “Terabit burst switching,” J. High Speed Networks 8, 3–16 (1999).
15. OPNET, http://www.opnet.com/.
