1.

Introduction

Recent work¹ 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.²

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 $g_1$ , and $S_3$ has the least total combined interference level (CIL), so $g_1=\left\{S_3\right\}$ ; $S_{13}$ has the least $\mathrm{CIL}(i,j)$ with switch $S_3$ among all the unassigned switches, so $g_1$ refreshes to be $\{S_3,S_{13}\}$ ; $S_4$ has the least $\mathrm{CIL}(i,j)$ with switch $S_{13}$ among all the unassigned switches, so finally, $g_1=\{S_3,S_{13},S_4\}$ . We might think that all the switches in group $g_1$ already have few interferences. However, even if $S_{13}$ has little interference with $S_3$ and so do $S_4$ and $S_{13}$ , that does not mean $S_4$ has little interference with $S_3$ . Actually, the interference between $S_4$ and $S_3$ 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).

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 $S_i$ and $S_j$ as $d(i,j)$ , whose start wavelengths are ${\lambda }_m$ and ${\lambda }_n$ , respectively. Since the search sequence of wavelength is circular:

We take $W=16$ , $\mathrm{start}\left(i\right)∊\{{\lambda }_1,{\lambda }_3,\dots ,{\lambda }_{15}\}$ for an example, as shown in Fig. 2, the distance between $\mathrm{start}\left(i\right)={\lambda }_1$ , and $\mathrm{start}\left(j\right)={\lambda }_{11}$ is $16∕2-\mid \mid 1-11\mid -16∕2\mid =6$ .

Fig. 2

Wavelength search sequence.

Concept 2: $\mathrm{GCIL}(g_i,g_j)$ . This is the group combined interference level of two groups $g_i$ and $g_j$ , which represents the total interference level of the two groups that have been set in step 1.

Concept 3: $\mathrm{RGCIL}(g_i,g_j,{\lambda }_m,{\lambda }_n)$ : This is the relative group combined interference level, which is the remainder group combined interference level between two groups $g_i$ and $g_j$ , whose start wavelengths have been set to ${\lambda }_m$ and ${\lambda }_n$ , respectively:

Concept 4: Total_RGCIL. This is the sum of $\mathrm{RGCIL}(g_i,g_j,{\lambda }_m,{\lambda }_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:

The Min-RGCIL algorithm consists of three steps:

Step 1. Partition the set of $N$ switches into $K=\lceil N∕2\rceil$ groups, $g_1,g_2,\dots ,g_K$ , where the operator $\lceil \rceil$ 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 $\mathrm{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.

Step 2. Arbitrarily label the $W$ wavelengths as ${\lambda }_1,\dots ,{\lambda }_w$ , and let $x=W∕K$ . Evenly space the $K$ start wavelengths across all $W$ wavelengths, such that the $k$ ’th start wavelength is the wavelength labeled ${\lambda }_{1+\left[\right(k-1\left)x\right]}$ .

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 ${\lambda }_1$ to group $g_1$ . Then calculate the $\mathrm{RGCIL}(g_i,g_j)$ and $\mathrm{Total}\_\mathrm{RGCIL}$ using Eqs. 1, 2, 3, 4 for all start wavelength selection methods among the groups $g_1,\dots ,g_K$ . 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 $\left(N\right)$ into five groups $\left(G\right)$ in the first step, such as $G1(N1,N3)$ , $G2(N5,N7)$ , $G3(N4,N9)$ , $G4(N2,N6)$ , $G5\left(N8\right)$ ; in the third step, five fictitious wavelengths ${\lambda }_1,{\lambda }_2,{\lambda }_3,{\lambda }_4$ , and ${\lambda }_5$ are assigned to the five groups in sequential order so that $G1(N1,N3)$ , $G3(N4,N9)$ , $G2(N5,N7)$ , $G5\left(N8\right)$ , 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 ${\lambda }_1,{\lambda }_2$ , and ${\lambda }_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)\leftarrow {\lambda }_1$ , $(2,16,10,15,1)\leftarrow {\lambda }_2$ , $(14,7,11,5,12)\leftarrow {\lambda }_3$ , with $\mathrm{Total}\_\mathrm{RGCIL}=1156.5$ ; for Min-RGCIL, the start wavelength selection method is $(13,3,12,5,2,16)\leftarrow {\lambda }_1$ , $(6,9,8,4,15)\leftarrow {\lambda }_2$ , $(10,1,14,7,11)\leftarrow {\lambda }_3$ , with $\mathrm{Total}\_\mathrm{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 $10\mathrm{Gbits}∕\mathrm{s}$ .

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

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.

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.