1 October 2006 Start wavelength selection method in optical burst switching networks under wavelength continuity constraint
Author Affiliations +
Optical Engineering, 45(10), 100502 (2006). doi:10.1117/1.2359433
Abstract
Considering the state of the art of wavelength conversion technology, it is likely to dictate a more limited and sparse deployment of wavelength converters in the optical burst switching (OBS) networks. Without wavelength conversion capabilities at optical switches, the start wavelength selection method becomes an important issue to avoid burst contention. We present a new start wavelength selection method, the minimum relative group combined interference level (Min-RGCIL) algorithm, which is a modified version of a proposed method called first-fit-TE (traffic engineering). The performance study indicates that the new method achieves better performance than the original one and is robust under Poisson and self-similar traffic.
Shan, Xie, Li, and Xu: Start wavelength selection method in optical burst switching networks under wavelength continuity constraint

1.

Introduction

Recent work1 presented a nonadaptive wavelength assignment policy called first-fit-TE (traffic engineering) to reduce wavelength contention in optical burst switching (OBS) networks using a greedy heuristic algorithm and the concept of “interference.” According to our knowledge, first-fit-TE is a good scheme for resolving the wavelength contention problem in the case of lack of wavelength converters. However, we feel that this algorithm is not perfectly satisfactory and adequately addressed, so that work remains to be done to develop a better wavelength assignment policy. In this paper, we present a modified and much more comprehensive algorithm called the Min-RGCIL (minumum–relative group combined interference level) algorithm.

2.

Problem of the Greedy Heuristic in First-Fit-TE

The main algorithm of first-fit-TE is a greedy heuristic algorithm, which always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems.2

To obviously illustrate our standpoint, we used a 16-node OBS network to do analysis, as shown in Fig. 1. In step 1 of first-fit-TE (Ref. 1), suppose three switches are about to be assigned to one group, such as g1 , and S3 has the least total combined interference level (CIL), so g1={S3} ; S13 has the least CIL(i,j) with switch S3 among all the unassigned switches, so g1 refreshes to be {S3,S13} ; S4 has the least CIL(i,j) with switch S13 among all the unassigned switches, so finally, g1={S3,S13,S4} . We might think that all the switches in group g1 already have few interferences. However, even if S13 has little interference with S3 and so do S4 and S13 , that does not mean S4 has little interference with S3 . Actually, the interference between S4 and S3 is quite large almost all the time. Thus, these three switches are not appropriate to be distributed to one group, otherwise they are about to be assigned the same start wavelength in step 3.

Fig. 1

Sixteen-node topology based on 14-node the National Science Foundation Network (NSFNet).

100502_1_1.jpg

The same problem also occurs in the third step of first-fit-TE, which also uses a greedy heuristic algorithm. Due to the shortcomings of the greedy heuristic algorithm used in the area of this research, work remains to be done to modify the original first-fit-TE algorithm to be a better start wavelength selection method.

3.

Min-RGCIL Algorithm—A New Start Wavelength Selection Method

Now, we put forward our Min-RGCIL algorithm with four new concepts.

Concept 1: d(i,j) . We define the distance between the start wavelengths of two switches Si and Sj as d(i,j) , whose start wavelengths are λm and λn , respectively. Since the search sequence of wavelength is circular:

1

d(i,j)=d(λm,λn)=W2mnW2.

We take W=16 , start(i){λ1,λ3,,λ15} for an example, as shown in Fig. 2, the distance between start(i)=λ1 , and start(j)=λ11 is 162111162=6 .

Fig. 2

Wavelength search sequence.

100502_1_2.jpg

Concept 2: GCIL(gi,gj) . This is the group combined interference level of two groups gi and gj , which represents the total interference level of the two groups that have been set in step 1.

2

GCIL(gi,gj)=Smgi,SngjCIL(m,n),ij.

Concept 3: RGCIL(gi,gj,λm,λn) : This is the relative group combined interference level, which is the remainder group combined interference level between two groups gi and gj , whose start wavelengths have been set to λm and λn , respectively:

3

RGCIL(gi,gj,λm,λn)={GCIL(gi,gj)d(λm,λn)ij0i=j.

Concept 4: Total_RGCIL. This is the sum of RGCIL(gi,gj,λm,λn) among all groups under one start wavelength selection method. It is the measurement of whole network interference level under one start wavelength selection method:

4

Total_RGCIL=gi,gj,λm,λnRGCIL(gi,gj,λm,λn).

The Min-RGCIL algorithm consists of three steps:

Step 1. Partition the set of N switches into K=N2 groups, g1,g2,,gK , where the operator is the ceiling function that returns the minimum integer value that is more than the operand. Both of the two switches in a given group will be assigned the same start wavelength. (It is possible that one switch is left alone, it forms a group singly.) Initially, calculate CIL(i,j) of the network, then follow the steps listed next and make sure that there are at most two switches in one group. The workflow of switches partition in step 1 is listed next with k=1 at the beginning.

  • 1. Find the switch that has the minimum total combined interference level j=1NCIL(i,j) among all the unassigned switches.

  • 2. Put the resulting switch, e.g., Si , in group gk , so that gk={Si} .

  • 3. Select the switch that has the minimum combined interference level CIL(i,j) with the switch already found among all the unassigned switches.

  • 4. Put the resulting switch, e.g., Sj , in group gk , so that gk={Si,Sj} .

  • 5. k=k+1 . If kK , go to item 1.

Step 2. Arbitrarily label the W wavelengths as λ1,,λw , and let x=WK . Evenly space the K start wavelengths across all W wavelengths, such that the k ’th start wavelength is the wavelength labeled λ1+[(k1)x] .

Step 3. Since the interference of the two switches in each group is now minimum, we assign a start wavelength to every group to minimize the interference among all the groups. Initially, always assign wavelength λ1 to group g1 . Then calculate the RGCIL(gi,gj) and Total_RGCIL using Eqs. 1, 2, 3, 4 for all start wavelength selection methods among the groups g1,,gK . Next, select the method whose Total_RGCIL is the minimum among all the results. This selection method is the globally optimal solution.

On the other hand, we should also discuss the possible case that the total number of available wavelengths is less than K , namely, W<K . We solve the problem in this manner, first suppose the network has K fictitious wavelengths, namely, let W=K , then run all the steps of Min-RGCIL algorithm. Then, according to the real number of available wavelengths, we combine the neighboring groups together in such a way that evenly distributes the nodes to each group. However, if the nodes cannot be evenly distributed, to not break the sequence of nodes in the outcome of step 3, we can split one group and distribute the two nodes to both neighboring groups. Finally, assign the real wavelengths in sequential order to each group. For an example, consider the case where nine nodes must be grouped to split three available wavelengths. The algorithm described in this paper would group the nodes (N) into five groups (G) in the first step, such as G1(N1,N3) , G2(N5,N7) , G3(N4,N9) , G4(N2,N6) , G5(N8) ; in the third step, five fictitious wavelengths λ1,λ2,λ3,λ4 , and λ5 are assigned to the five groups in sequential order so that G1(N1,N3) , G3(N4,N9) , G2(N5,N7) , G5(N8) , and G4(N2,N6) . Since the real number of wavelengths is three, we split group G3 and distribute the two nodes (N4,N9) to both neighboring groups. Thus, the start wavelength selection method is λ1,λ2 , and λ3 for G1(N1,N3,N4) , G2(N9,N5,N7) , and G3(N8,N2,N6) , respectively.

4.

Performance Evaluation

In this section, we use simulation to compare the OBS networks with the first-fit-TE and Min-RGCIL algorithms in terms of networkwide burst drop probability. We consider the network topology in Fig. 1. Each switch in our model is connected to several users, which transmit data packets simultaneously. The traffic model is Poisson and self-similar arrival, respectively. The routing algorithm is fixed shortest path first. If only three wavelengths are available, for first-fit-TE, the start wavelength selection method is (3,13,4,8,6,9)λ1 , (2,16,10,15,1)λ2 , (14,7,11,5,12)λ3 , with Total_RGCIL=1156.5 ; for Min-RGCIL, the start wavelength selection method is (13,3,12,5,2,16)λ1 , (6,9,8,4,15)λ2 , (10,1,14,7,11)λ3 , with Total_RGCIL=1115 , which means Min-RGCIL can provide less global interference, i.e., provide a more globally optimal solution. Since the number of wavelengths is even at most times, and if the number of wavelengths is too small, which means the network is weak in wavelength dimension, the start wavelength selection method seems not to be an important issue. Thus, in the study presented in this paper, we do analysis under the condition of 16 wavelengths and the transmission rate of each channel is 10Gbitss .

The start wavelength selection method for a 16-Node NSFNet is

(13,3)λ1,(12,5)λ3,(2,16)λ5,(6,9)λ7,
(8,4)λ9,(15,10)λ11,(1,14)λ13,(7,11)λ15.

Figure 3 shows the burst block probability of OBS networks under the wavelength continuity constraint (87.5% degree), with the FFT (first-fit-TE) and with MR (Min-RGCIL) algorithms, respectively (using dual-time threshold assembly algorithm and cascaded private subnet scheme).

Fig. 3

Block probability under Poisson and self-similar traffic.

100502_1_3.jpg

The simulation results indicate that the start wavelength selection method we describe to reduce traffic interference leads to a noticeable decrease in block probability. The block probability of OBS networks with the MR algorithm is around one order of magnitude lower than that of OBS networks without MR, and achieves better performance than FFT to a certain extent, especially with lower traffic load, where the start wavelength is mostly used. The performance is robust under Poisson and self-similar traffic, helping reduce the performance gap with respect to full wavelength conversion. The MR algorithm always returns the best result no matter how large the network scale. The potential problem of the MR algorithm is the complexity of computation. However, since we must do this calculation only before the start of network operation, and with the rapid progress of computing devices, the complexity of computation is acceptable to achieve a better network performance.

Consequently, the MR algorithm is a promising solution for OBS networks under the wavelength continuity constraint, and we hope that it will be especially useful when combined with other techniques.

References

1.  J. Teng and G. N. Rouskas, “Wavelength selection in OBS networks using traffic engineering and priority-based concepts,” IEEE J. Sel. Areas Commun.0733-8716, 23(8), 1658–1669 (2005). Google Scholar

2.  P. E. Black, “Greedy algorithm,” in Dictionary of Algorithms and Data Structures, Paul E. Black, Ed., NIST,  http://www.nist.gov/dads/HTML/greedyalgo.html Google Scholar

Liang Shan, Linzhen Xie, Zhengbin Li, Anshi Xu, "Start wavelength selection method in optical burst switching networks under wavelength continuity constraint," Optical Engineering 45(10), 100502 (1 October 2006). http://dx.doi.org/10.1117/1.2359433
JOURNAL ARTICLE
3 PAGES


SHARE
KEYWORDS
Switches

Switching

Optical networks

Algorithm development

Data modeling

Optical engineering

Optical switching

RELATED CONTENT

Tapered-width microcantilever for pull-in voltage control
Proceedings of SPIE (January 16 2003)
Retrieval based on image content using DC-image
Proceedings of SPIE (September 26 2001)
Digital tracking and control of retinal images
Proceedings of SPIE (June 24 1993)
A study of EB pattern write system design for 22...
Proceedings of SPIE (May 15 2007)

Back to Top