## New strategy for optimizing wavelength converter placement

Optics Express, Vol. 13, Issue 2, pp. 545-551 (2005)

http://dx.doi.org/10.1364/OPEX.13.000545

Acrobat PDF (102 KB)

### Abstract

This paper proposes a new strategic alternate-path routing to be combined with the particle swarm optimization (PSO) algorithm to better solve the wavelength converters placement problem. The strategic search heuristic is designed to provide network connectivity topologies for the converters to be placed more effectively. The new strategy is applied to the 14-node NSFNET to examine its efficiency in reducing the blocking probability in sparse wavelength conversion network. Computed results show that, when applied to the identical optimization framework, our search method outperforms both the equal-cost multipath routing and traffic-engineering-aware shortest-path routing.

© 2005 Optical Society of America

## 1. Introduction

1. S. Gao, X. Jia, C. Huang, and D. Du, “An optimization model for placement of wavelength converters to minimize blocking probability in WDM networks,” OSA/IEEE J. Lightwave Technol. **21**, 684–694 (2003). [CrossRef]

2. C.F. Teo, Y.C. Foo, S.F. Chien, Andy L.Y. Low, B. Venkatesh, and A.H. You, “Optimal placement of wavelength converters in WDM networks using particle swarm optimizer,” in *Proceedings of IEEE International Conference on Communications* (Institute of Electrical and Electronic Engineers, Paris, 2004), pp. 1669–1673.

*et al*. proposed the application of equal-cost multipath (ECMP) routing and traffic-engineering(TE)-aware shortest-path routing in converter placement problem [3

3. Y. C. Foo, Youngseok Lee, C. F. Teo, S. F. Chien, and Andy L. Y. Low, “Enhancing wavelength converter placement optimization with traffic-engineering-aware shortest-path routing,” IEICE Electron. Express **1**, 416–422 (2004), http://joi.jlc.jst.go.jp/JST.JSTAGE/elex/1.416. [CrossRef]

3. Y. C. Foo, Youngseok Lee, C. F. Teo, S. F. Chien, and Andy L. Y. Low, “Enhancing wavelength converter placement optimization with traffic-engineering-aware shortest-path routing,” IEICE Electron. Express **1**, 416–422 (2004), http://joi.jlc.jst.go.jp/JST.JSTAGE/elex/1.416. [CrossRef]

## 2. Problem formulation

1. S. Gao, X. Jia, C. Huang, and D. Du, “An optimization model for placement of wavelength converters to minimize blocking probability in WDM networks,” OSA/IEEE J. Lightwave Technol. **21**, 684–694 (2003). [CrossRef]

*G*=(

*V*,

*E*), which consists of a set of nodes,

*V*, and a set of directed links,

*E*. The state vector (

*x*

_{1},

*x*

_{2},…,

*x*

_{n}) indicates the placement of converters on a network with

*n*nodes. The binary variable

*x*

_{i}is set to be 1 if node

*i*is equipped with a converter; 0 if otherwise. The blocking probability on a link

*l*

_{ij}connecting node

*i*and

*j*is defined as the probability that a specific wavelength on this link is occupied. The blocking probability

*ρ*

_{ij}can be computed by:

*F*is the number of wavelengths on each link;

*s*to node

*t*, which also represents the arrival probability of a call from

*s*to

*t*.

*P*

_{st}is the path between node

*s*and node

*t*on which

*λ*

_{st}(the traffic load from

*s*to

*t*) is routed.

*S*(

*P*

_{st}) is the end-to-end success probability of a call on path

*P*

_{st}. The segment of the path,

*d*, is the set of links between two consecutive converter nodes; or between an end node and its nearest converter node in the path. Given traffic matrix

*T*and

*k*converters, the optimization objective is to determine the values in (

*x*

_{1},

*x*

_{2},…,

*x*

_{n}), so that the overall blocking probability of the network is minimized, or conversely, the overall success probably of the network is maximized.

## 3. Converter placement optimization

### 3.1 ECMP and TE-aware shortest-path routing

4. Youngseok Lee and B. Mukherjee, “Traffic-engineering-aware shortest-path routing and its application in IP-over-WDM networks,” J. Opt. Netw. **3**, 133–151 (2004), http://www.osa-jon.org/abstract.cfm?URI=JON-3-3-133. [CrossRef]

4. Youngseok Lee and B. Mukherjee, “Traffic-engineering-aware shortest-path routing and its application in IP-over-WDM networks,” J. Opt. Netw. **3**, 133–151 (2004), http://www.osa-jon.org/abstract.cfm?URI=JON-3-3-133. [CrossRef]

4. Youngseok Lee and B. Mukherjee, “Traffic-engineering-aware shortest-path routing and its application in IP-over-WDM networks,” J. Opt. Netw. **3**, 133–151 (2004), http://www.osa-jon.org/abstract.cfm?URI=JON-3-3-133. [CrossRef]

*F*

_{i}}, over the most congested link

*l*

_{c}, with the maximum link load,

*L*

_{max}.

*F*

_{i}, select an alternate path, and determine “induced flows” that also have to change their paths to meet the destination-based forwarding rule.

*F*

_{i}and induced flows determined in [Step 4] can reduce

*L*

_{max}, exchange the current shortest path with the alternate path.

*F*

_{i}as examined.

*l*

_{c}, go to [Step 3].

*F*

_{i}}, go to [Step 4]; otherwise, terminate.

### 3.2 Particle swarm optimization (PSO) algorithm

## 4. Strategic search heuristic

*k*-shortest candidate routes. With this insight, we propose a search method that will further explore the possible routing configurations based on the given traffic demand matrix and multiple equal-cost shortest paths (ECSP) between source-destination pairs. The heuristic starts by identifying all the ECSP between each node pairs and arranges these paths using either ECMP or TE-aware shortest-path algorithms. When ECMP is applied, the ECSP are sorted according to the sequence for which these paths are identified. For TE-aware sorted multiple paths, the first path in each ECSP sets will produce the minimum link load according to [4

**3**, 133–151 (2004), http://www.osa-jon.org/abstract.cfm?URI=JON-3-3-133. [CrossRef]

*s*and node

*t*is labeled as

*A*

_{st},

*B*

_{st}, and

*C*

_{st}respectively. Different sets of network connectivity topology are derived using all the possible combinations of these paths as shown in Table 2.

*η*, which is defined as:

*N*is the total number of network nodes,

*k*is the number of wavelength converters,

*α*is the number of attempts needed to find the optimal placement of the wavelength converter in order to obtain the minimum blocking probability.

## 5. Results and discussions

1. S. Gao, X. Jia, C. Huang, and D. Du, “An optimization model for placement of wavelength converters to minimize blocking probability in WDM networks,” OSA/IEEE J. Lightwave Technol. **21**, 684–694 (2003). [CrossRef]

2. C.F. Teo, Y.C. Foo, S.F. Chien, Andy L.Y. Low, B. Venkatesh, and A.H. You, “Optimal placement of wavelength converters in WDM networks using particle swarm optimizer,” in *Proceedings of IEEE International Conference on Communications* (Institute of Electrical and Electronic Engineers, Paris, 2004), pp. 1669–1673.

*ECMP0*and

*TE0*represents the topology obtained originally using ECMP and TE-aware shortest-path routing, respectively. Based on the relatively high blocking probability of

*ECMP0*, it is obvious that the standard ECMP is not the best method in deriving network connectivity topology on which the optimal placement of converters will be determined by BPSO. The proposed search heuristic is then applied to both the original set of paths generated by ECMP and TE-aware shortest-path algorithms. Different connectivity topologies are produced based on the path selection pattern as described in Table 2. For example,

*TE1*is derived by applying the path selection criteria

*set1*in Table 2 to the set of TE-aware sorted multiple paths. As evident from Fig. 1, few newly generated topologies

*TE1*,

*ECMP4*, and

*ECMP5*result in lower blocking probability after the BPSO is employed to equip the network with fixed number of wavelength converters. Comparing the results obtained by

*TE0*and

*TE1*, the

*TE1*exhibits more strength especially when the given number of converters is less than half of the network size. Both

*ECMP4*and

*ECMP5*outperform the standard

*TE0*regardless of the number of converters assigned.

*TE1*. In general, the efficiency of the BPSO-based technique is low for small

*k*≤9, all the topologies included in the experiment have the chance of yielding optimization process with efficiency exceeding 90%. Computed results shown in Fig. 1 and Fig. 2 imply that the proposed search heuristic is effective and efficient in producing network connectivity topology that will result in the further reduction of blocking probability in sparse wavelength conversion network. Since the proposed solution is based on off-line computation, new results can be obtained by repeating the simulation when given arbitrary physical network topologies and the corresponding traffic demand matrices.

## 6. Conclusion

3. Y. C. Foo, Youngseok Lee, C. F. Teo, S. F. Chien, and Andy L. Y. Low, “Enhancing wavelength converter placement optimization with traffic-engineering-aware shortest-path routing,” IEICE Electron. Express **1**, 416–422 (2004), http://joi.jlc.jst.go.jp/JST.JSTAGE/elex/1.416. [CrossRef]

## Acknowledgments

## References and links

1. | S. Gao, X. Jia, C. Huang, and D. Du, “An optimization model for placement of wavelength converters to minimize blocking probability in WDM networks,” OSA/IEEE J. Lightwave Technol. |

2. | C.F. Teo, Y.C. Foo, S.F. Chien, Andy L.Y. Low, B. Venkatesh, and A.H. You, “Optimal placement of wavelength converters in WDM networks using particle swarm optimizer,” in |

3. | Y. C. Foo, Youngseok Lee, C. F. Teo, S. F. Chien, and Andy L. Y. Low, “Enhancing wavelength converter placement optimization with traffic-engineering-aware shortest-path routing,” IEICE Electron. Express |

4. | Youngseok Lee and B. Mukherjee, “Traffic-engineering-aware shortest-path routing and its application in IP-over-WDM networks,” J. Opt. Netw. |

5. | J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in |

**OCIS Codes**

(060.2330) Fiber optics and optical communications : Fiber optics communications

(060.4250) Fiber optics and optical communications : Networks

**ToC Category:**

Research Papers

**History**

Original Manuscript: November 12, 2004

Revised Manuscript: January 13, 2005

Published: January 24, 2005

**Citation**

Y. Foo, S. Chien, Andy Low, C. Teo, and Youngseok Lee, "New strategy for optimizing wavelength converter placement," Opt. Express **13**, 545-551 (2005)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-13-2-545

Sort: Journal | Reset

### References

- S. Gao, X. Jia, C. Huang, and D. Du, �??An optimization model for placement of wavelength converters to minimize blocking probability in WDM networks,�?? OSA/IEEE J. Lightwave Technol. 21, 684-694 (2003). [CrossRef]
- C.F. Teo, Y.C. Foo, S.F. Chien, Andy L.Y. Low, B. Venkatesh, and A.H. You, �??Optimal placement of wavelength converters in WDM networks using particle swarm optimizer,�?? in Proceedings of IEEE International Conference on Communications (Institute of Electrical and Electronic Engineers, Paris, 2004), pp. 1669-1673.
- Y. C. Foo, Youngseok Lee, C. F. Teo, S. F. Chien, and Andy L. Y. Low, �??Enhancing wavelength converter placement optimization with traffic-engineering-aware shortest-path routing,�?? IEICE Electron. Express 1, 416-422 (2004), <a href="http://joi.jlc.jst.go.jp/JST.JSTAGE/elex/1.416.">http://joi.jlc.jst.go.jp/JST.JSTAGE/elex/1.416.</a> [CrossRef]
- Youngseok Lee and B. Mukherjee, �??Traffic-engineering-aware shortest-path routing and its application in IP-over-WDM networks," J. Opt. Netw. 3, 133-151 (2004), <a href="http://www.osa-jon.org/abstract.cfm?URI=JON-3-3-133.">http://www.osa-jon.org/abstract.cfm?URI=JON-3-3-133.</a> [CrossRef]
- J. Kennedy, and R. C. Eberhart, �??Particle swarm optimization,�?? in Proceedings of IEEE International Conference on Neural Networks (Institute of Electrical and Electronic Engineers, Piscataway, NJ, 1995), pp. 1942-1948.

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article | Next Article »

OSA is a member of CrossRef.