1.
Introduction
Optical burst switching (OBS)^{1} is regarded as a promising switching technology for future WDM networks. Most of the studies on OBS networks assume that full wavelength conversion is available throughout the network. However, such capability is not at present a realistic assumption, because wavelength converters are expensive and immature. The absence of (full) wavelength conversion capabilities calls for good and efficient wavelength assignment policies. Traditional first-fit or random policies in optical circuit switching (OCS) networks are not appropriate for wavelength-continuous OBS networks, since the burst is transmitted without knowledge of the wavelength occupation status of the following links.
Currently, wavelength assignment policies can be classified into two categories: static approaches such as first-fit TE,^{2} and dynamic methods such as priority-based wavelength assignment (PWA).^{3} Static approaches do not require the exchange of any information among network routers. Thus, the assignment rules are determined during the network planning phase, depending on certain properties of the network like topology, routing paths, and traffic. In first-fit TE, different routers are assigned different start wavelengths. A modified version of first-fit TE, called first-fit MR, is proposed in Ref. 4 to achieve better performance. In dynamic methods, each source router keeps a wavelength priority database for every destination router, which is updated periodically based on feedback from the network. Therefore, the current priority of a wavelength reflects the likelihood that a burst transmission on this wavelength will be successful.
In this paper, a balanced static wavelength assignment (BSWA) approach is proposed. By assigning different wavelength order lists for different source-destination $\left(s\text{-}d\right)$ pairs, traffic that shares common links between different $s\text{-}d$ pairs is further balanced among wavelengths on those links. Numerical results show that BSWA significantly decreases the burst loss probability compared with all existing static approaches, and almost achieves the same performance as PWA with the advantage that no extra dynamic information is needed. Furthermore, a hybrid method is developed by combining BSWA and PWA to accelerate network convergence and reduce the initial burst loss.
2.
Balanced Static Wavelength Assignment Algorithm
First-fit TE only decides the starting wavelength for one source node, while BSWA has to decide the order of the entire wavelength list for one $s\text{-}d$ pair, based on the topology, traffic, and routing information of the network. BSWA tries to fully balance the traffic that shares common links between different $s\text{-}d$ pairs among wavelengths on those links. In PWA, such wavelength order lists are based on the history of prior burst transmissions, while in BSWA, they are carefully designed during the network planning phase, and no extra information exchange or signaling is needed.
Now we describe the BSWA in detail. An OBS network is represented by a graph $G(V,E)$ , where $V=\{{V}_{1},{V}_{2},\dots ,{V}_{N}\}$ is the set of nodes, and $E=\{{E}_{1},{E}_{2},\dots ,{E}_{M}\}$ is the set of unidirectional fiber links. The link $E({V}_{s},{V}_{d})$ connects ${V}_{s}$ to ${V}_{d}$ and contains $W$ different wavelengths labeled arbitrarily, say, ${\lambda}_{1},{\lambda}_{2},\dots ,{\lambda}_{W}$ . By $P\{{V}_{s},{V}_{d}\}$ we denote the routing path from ${V}_{s}$ to ${V}_{d}$ , and $\rho ({V}_{s},{V}_{d})$ is the given traffic load from ${V}_{s}$ to ${V}_{d}$ . We define $\mathrm{virtual}\_\mathrm{wl}\_\mathrm{cost}({V}_{i},{V}_{j},{\lambda}_{k})$ to be the virtual cost of wavelength ${\lambda}_{k}$ on link $E({V}_{i},{V}_{j})$ , and $\mathrm{path}\_\mathrm{cost}({V}_{s},{V}_{d},{\lambda}_{k})$ to be the cost of the path on ${\lambda}_{k}$ along which the source ${V}_{s}$ sends bursts to the destination ${V}_{d}$ .Thus, $\mathrm{path}\_\mathrm{cost}({V}_{s},{V}_{d},{\lambda}_{k})$ is calculated as
Eq. 1
$$\mathrm{path}\_\mathrm{cost}({V}_{s},{V}_{d},{\lambda}_{k})=\sum _{E({V}_{i},{V}_{j})\u220aP({V}_{s},{V}_{d})}\mathrm{virtual}\_\mathrm{wl}\_\mathrm{cost}({V}_{i},{V}_{j},{\lambda}_{k}).$$Balanced static wavelength assignment algorithm.
Input: $G(V,E)$ , $\rho ({V}_{s},{V}_{d})$ , $P({V}_{s},{V}_{d})\phantom{\rule{0.3em}{0ex}}\forall s$ , $d\u220a\{1,2,\dots ,N\}$ |
Output: $\mathrm{WA}({V}_{s},{V}_{d},t)\phantom{\rule{0.3em}{0ex}}\forall s$ , $d\u220a\{1,2,\dots ,N\},$ $t\u220a\{1,2,\dots ,W\}$ |
Initialization: $\mathrm{virtual}\_\mathrm{wl}\_\mathrm{cost}({V}_{i},{V}_{j},{\lambda}_{k})=0\phantom{\rule{0.3em}{0ex}}\forall i$ , $j\u220a\{1,2,\dots ,N\}$ , $t\u220a\{1,2,\dots ,W\}$ |
FOR $t\leftarrow $ from 1 to $W$ |
FOR $s\leftarrow $ from 1 to $N$ |
FOR $d\leftarrow $ from 1 to $N$ |
Step 1: Compute the $\mathrm{path}\_\mathrm{cost}$ for each wavelength that has not been assigned before for this $s\text{-}d$ pair. |
Step 2: Choose the ${\lambda}_{k}$ that has the least $\mathrm{path}\_\mathrm{cost}$ , and make it the wavelength assigned in this loop. That is, $\mathrm{WA}({V}_{s},{V}_{d},t)={\lambda}_{k}$ . |
Step 3: Update $\mathrm{virtual}\_\mathrm{wl}\_\mathrm{cost}({V}_{i},{V}_{j},{\lambda}_{k})\phantom{\rule{0.3em}{0ex}}\forall E({V}_{i},{V}_{j})\u220aP\{{V}_{s},{V}_{d}\}$ by $\mathrm{virtual}\_\mathrm{wl}\_\mathrm{cost}({V}_{i},{V}_{j},{\lambda}_{k})=\mathrm{virtual}\_\mathrm{wl}\_\mathrm{cost}({V}_{i},{V}_{j},{\lambda}_{k})+\rho ({V}_{s},{V}_{d})$ . |
The process of BSWA is stated as follows. First the cost of each wavelength on all links, $\mathrm{virtual}\_\mathrm{wl}\_\mathrm{cost}$ $({V}_{i},{V}_{j},{\lambda}_{k})$ is initialized to 0. Then we begin to assign wavelengths for the $s\text{-}d$ pairs one by one. The value of $\mathrm{path}\_\mathrm{cost}({V}_{s},{V}_{d},{\lambda}_{k})$ , $k\u220a\{1,2,\dots ,W\}$ , is calculated for each $({V}_{s},{V}_{d})$ pair, and ${\lambda}_{k}$ that has the least $\mathrm{path}\_\mathrm{cost}$ is chosen as the wavelength assigned for the $({V}_{s},{V}_{d})$ pair. Every time we assign a wavelength (e.g. ${\lambda}_{k}$ ) for an $s\text{-}d$ pair, we increase $\mathrm{virtual}\_\mathrm{wl}\_\mathrm{cost}({V}_{i},{V}_{j},{\lambda}_{k})$ on all the passing links of $P\{{V}_{s},{V}_{d}\}$ by $\rho ({V}_{s},{V}_{d})$ so that the wavelength is less likely to be chosen by other $s\text{-}d$ pairs if it is already heavily loaded. We continue to do this for all $s\text{-}d$ pairs, so that each pair is assigned a wavelength. The process described is called a searching loop. If we do such a searching loop $W$ times, we can get a list of the wavelength assignment order for each $s\text{-}d$ pair.
BSWA focuses on a wavelength assignment problem that assumes that the routing paths between all $s\text{-}d$ pairs have been given. We call it “balanced” because it balances the traffic that shares one common link among different wavelengths in the link. We have also proposed a novel load-balancing and routing algorithm for all OBS networks,^{5} which tries to balance the traffic load among all links. We believe that by combining the balanced routing in Ref. 5 and BSWA, the traffic can be balanced among both links and wavelengths and the burst loss probability will be further decreased.
3.
Combining BSWA and PWA (Hybrid Approach)
In PWA, the priority of each wavelength is undistinguished at the beginning. Thus, in the beginning period, the network suffers great burst loss like first-fit and random policies. To overcome this shortcoming, Teng and Rouskas^{2} have proposed a solution called PWA-TE by combining first-fit TE and PWA. Naturally, BSWA can also be incorporated into such a hybrid approach. Since the data structure of BSWA is the same as that of PWA, the results of BSWA can be directly used for the initial values of PWA. We initialize the priority of each wavelength according to the result of BSWA from $W$ to 1 ( $W$ is the number of wavelengths in a fiber), and the remaining part of the hybrid approach is identical to PWA. After the sender gets the feedback of a burst transmission, it can either add the priority by Inc or decrease the priority by Dec. The hybrid method can be described as follows:
Step 1. Use BSWA to compute an ordered list of wavelengths for each $s\text{-}d$ pair. Initialize the priority of each wavelength according to that wavelength order from $W$ to 1.
Step 2. Same as with PWA. Decide wavelength assignments in decreasing order of priority of the wavelengths, and choose the first free one to transmit the burst, or drop it if all the wavelengths are busy. Then update the priority according to the feedback of the burst transmission. If the burst transmission is successful, $p\leftarrow \mathrm{min}\{p+\mathrm{Inc},W\}$ , else $p\leftarrow \mathrm{max}\{p-\mathrm{Dec},1\}$ .
4.
Simulation Results
In this section, we use simulations to investigate the performance of BSWA and the hybrid approach in terms of burst loss probability and network convergence speed. The topology we use in this section is NSFNET (14 nodes, 21 bidirectional fiber links). The number of wavelengths on each link, $W$ , is set to 32 in our experiments. We assume every node has a uniform Poisson traffic pattern and no wavelength converters are available. Dijkstra’s shortest-path algorithm is used to calculate the route for each $s\text{-}d$ pair. The Inc and Dec of the PWA and hybrid approaches are set to 0.3 and 1.0, respectively.
Figure 1 plots the resulting burst loss probability of the different wavelength assignment schemes against the load on the network, expressed in erlangs per wavelength. The results show that first fit is the worst policy and the random policy also does not perform well, while our proposed static algorithm is the best among static policies in all situations, performs much better than first-fit TE, and almost achieves the same performance as dynamic approaches. The two dynamic algorithms work a little better than BSWA. However, unlike dynamic methods, BSWA does not need any dynamic information and is easy to implement.
To learn the network convergence performance of dynamic methods, we record the result in intervals and compute the burst loss probability at the end of each interval. The result is shown in Fig. 2. BSWA keeps the same performance, since the wavelength priority does not change over time. In the beginning period, PWA suffers high burst loss because wavelengths are undistinguished at the beginning. Both PWA-TE and our $\mathrm{BSWA}+\mathrm{PWA}$ approach can decrease the initial burst loss, but our approach performs better in the learning period of the dynamic approach. After about 7,000,000 bursts, the performance of the different approaches becomes almost the same. The hybrid method accelerates the network convergence and reduces the burst loss in the beginning period.
5.
Conclusion
In this letter, we have proposed a novel static wavelength assignment approach, called BSWA, which can greatly reduce the burst loss probability by balancing the traffic that shares common links among wavelengths on those links. Note that without extra dynamic information and signaling cost, BSWA can achieve almost the same performance as dynamic policies like PWA. Furthermore, by combining BSWA and PWA, a hybrid method is proposed to accelerate the network convergence and decrease the initial burst loss of PWA.
Acknowledgments
This work was supported by the National Natural Science Foundation of China (NSFC) under grants 60572006 and 6052130298, and the National 863 Program 2005AA122310.