1 September 2007 New and improved approaches for wavelength assignment in wavelength-continuous optical burst switching networks
Author Affiliations +
Abstract
Considering the economic and technical aspects of wavelength converters, full wavelength conversion capability will not be available throughout optical networks in the foreseeable future. This letter investigates the wavelength assignment problem in wavelength-continuous optical burst switching (OBS) networks. First, we develop a novel static approach, termed balanced static wavelength assignment (BSWA), which outperforms all other static strategies, and achieves almost the same performance as dynamic strategies with the advantage that no extra dynamic information is needed. Then, we apply BSWA to a dynamic approach to accelerate network convergence and reduce the initial burst loss. Numerical results show that our approaches make significant improvements in the burst loss probability in OBS networks.
Zhu, Ni, Du, Li, Zheng, Guo, and Zhang: New and improved approaches for wavelength assignment in wavelength-continuous optical burst switching networks

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 (s-d) pairs, traffic that shares common links between different s-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-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-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={V1,V2,,VN} is the set of nodes, and E={E1,E2,,EM} is the set of unidirectional fiber links. The link E(Vs,Vd) connects Vs to Vd and contains W different wavelengths labeled arbitrarily, say, λ1,λ2,,λW . By P{Vs,Vd} we denote the routing path from Vs to Vd , and ρ(Vs,Vd) is the given traffic load from Vs to Vd . We define virtual_wl_cost(Vi,Vj,λk) to be the virtual cost of wavelength λk on link E(Vi,Vj) , and path_cost(Vs,Vd,λk) to be the cost of the path on λk along which the source Vs sends bursts to the destination Vd .Thus, path_cost(Vs,Vd,λk) is calculated as

1

path_cost(Vs,Vd,λk)=E(Vi,Vj)P(Vs,Vd)virtual_wl_cost(Vi,Vj,λk).
The goal of the algorithm is to get wavelength order lists WA(Vs,Vd,t) for all Vs-Vd pairs. When there is a burst transmission from Vs to Vd , Vs searches the wavelengths in order from WA(Vs,Vd,1) to WA(Vs,Vd,W) and chooses the first free wavelength. A formal description of BSWA is given below:

Balanced static wavelength assignment algorithm.

Input: G(V,E) , ρ(Vs,Vd) , P(Vs,Vd)s , d{1,2,,N}
Output: WA(Vs,Vd,t)s , d{1,2,,N}, t{1,2,,W}
Initialization: virtual_wl_cost(Vi,Vj,λk)=0i , j{1,2,,N} , t{1,2,,W}
FOR t from 1 to W
FOR s from 1 to N
  FOR d from 1 to N
   Step 1: Compute the path_cost for each wavelength that has not been assigned before for this s-d pair.
   Step 2: Choose the λk that has the least path_cost , and make it the wavelength assigned in this loop. That is, WA(Vs,Vd,t)=λk .
   Step 3: Update virtual_wl_cost(Vi,Vj,λk)E(Vi,Vj)P{Vs,Vd} by virtual_wl_cost(Vi,Vj,λk)=virtual_wl_cost(Vi,Vj,λk)+ρ(Vs,Vd) .

The process of BSWA is stated as follows. First the cost of each wavelength on all links, virtual_wl_cost (Vi,Vj,λk) is initialized to 0. Then we begin to assign wavelengths for the s-d pairs one by one. The value of path_cost(Vs,Vd,λk) , k{1,2,,W} , is calculated for each (Vs,Vd) pair, and λk that has the least path_cost is chosen as the wavelength assigned for the (Vs,Vd) pair. Every time we assign a wavelength (e.g. λk ) for an s-d pair, we increase virtual_wl_cost(Vi,Vj,λk) on all the passing links of P{Vs,Vd} by ρ(Vs,Vd) so that the wavelength is less likely to be chosen by other s-d pairs if it is already heavily loaded. We continue to do this for all s-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-d pair.

BSWA focuses on a wavelength assignment problem that assumes that the routing paths between all s-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 Rouskas2 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:

  1. Step 1. Use BSWA to compute an ordered list of wavelengths for each s-d pair. Initialize the priority of each wavelength according to that wavelength order from W to 1.

  2. 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, pmin{p+Inc,W} , else pmax{pDec,1} .

In Ref. 2, Teng and Rouskas have pointed out that the best range for Inc is from 0.2 to 0.4, while the value of Dec should be in the range 0.8 to 1.2. Our simulations show that these ranges also suit the hybrid BSWA+PWA approach.

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-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.

Fig. 1

Burst loss probability versus load.

090504_1_1.jpg

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 BSWA+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.

Fig. 2

Burst loss probability versus number of bursts, load=0.2 .

090504_1_2.jpg

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.

References

1.  C. Qiao and M. Yoo, “Optical burst switching (OBS)—a new paradigm for an optical internet,” J. High Speed Netw. 8(1), 69–84 (1999). Google Scholar

2.  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 10.1109/JSAC.2005.851794 23(8), 1658–1669 (2005). Google Scholar

3.  X. Wang, H. Morikawa, and T. Aoyama, “Priority-based wavelength assignment algorithm for burst switched WDM optical networks,” IEICE Trans. Commun.0916-8516 E86-B(5), 1508–1514 (2003). Google Scholar

4.  L. Shan, L. Xie, Z. Li, and A. Xu, “Start wavelength selection method in optical burst switching networks under wavelength continuity constraint,” Opt. Eng.0091-3286 10.1117/1.2359433 45, 100502 (Oct.2006). Google Scholar

5.  Y. Du, T. Pu, H. Zhang, and Y. Guo, “Adaptive load balancing routing algorithm for optical burst-switching networks,” in Proc. Optical Fiber Communication Conf., OThF7, ComSoc (2006). Google Scholar

Chunlei Zhu, Wenda Ni, Yu Du, Yanhe Li, Xiaoping Zheng, Yili Guo, Hanyi Zhang, "New and improved approaches for wavelength assignment in wavelength-continuous optical burst switching networks," Optical Engineering 46(9), 090504 (1 September 2007). https://doi.org/10.1117/1.2776337
JOURNAL ARTICLE
3 PAGES


SHARE
Back to Top