OSA's Digital Library

Optics Express

Optics Express

  • Editor: Michael Duncan
  • Vol. 13, Iss. 2 — Jan. 24, 2005
  • pp: 545–551
« Show journal navigation

New strategy for optimizing wavelength converter placement

Y. C. Foo, S. F. Chien, Andy L. Y. Low, C. F. Teo, and Youngseok Lee  »View Author Affiliations


Optics Express, Vol. 13, Issue 2, pp. 545-551 (2005)
http://dx.doi.org/10.1364/OPEX.13.000545


View Full Text Article

Acrobat PDF (102 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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

Both of the optimization algorithms presented in [1

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]

] and [2

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.

] only consider the fixed single shortest-path routing, which is known to perform poorly for network resource provision. Single shortest-path routing, though computational less intensive, tends to route traffic along the already congested shortest paths between node pairs while leaving other longer uncongested paths under-utilized. To overcome the inefficiency of shortest-path routing, Foo 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]

]. These routing schemes guarantee higher level of network-wide load balance and resource utilization efficiency. Computed results in [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]

] showed that an optimization framework consists of TE-aware shortest-path routing and binary PSO (BPSO)-based algorithm is highly effective and efficient in reducing the blocking probability in sparse wavelength conversion networks.

2. Problem formulation

ρij=s,tλstijF
(1)

where F is the number of wavelengths on each link; λstij is the end-to-end traffic load from node s to node t, which also represents the arrival probability of a call from s to t.

The overall success probability of this model can be represented by the geometric average which is defined as:

Max(s,tS(Pst)λst)exp(s,tλst)1,s.t.i=1nxi=k,xi{0,1},i=1,2,,n
(2)

3. Converter placement optimization

3.1 ECMP and TE-aware shortest-path routing

• [Step 1] Calculate ECMPs for all node pairs.

• [Step 2] Initialize a random set of single shortest paths that satisfy the destination based forwarding rule.

• [Step 4] For each candidate flow, Fi , select an alternate path, and determine “induced flows” that also have to change their paths to meet the destination-based forwarding rule.

• [Step 5] If by swapping paths of Fi and induced flows determined in [Step 4] can reduce Lmax , exchange the current shortest path with the alternate path.

• [Step 6] Mark Fi as examined.

• [Step 8] If the flows to be examined remain in {Fi }, go to [Step 4]; otherwise, terminate.

3.2 Particle swarm optimization (PSO) algorithm

After the network connectivity topologies have been derived, BPSO is used to solve the NP-hard converter placement problem. The original PSO algorithm is a parallel evolutionary computation technique developed by Kennedy and Eberhart [5

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

] based on the social behavior metaphor. Unlike other evolutionary optimization methods, such as Genetic Algorithm (GA), PSO requires relatively small amount of computation resources since it does not rely on crossover and mutation processes. The algorithm is initialized with a population of random candidate solutions, conceptualized as particles. Each particle is assigned a randomized velocity and is iteratively moved through the problem space. It is attracted towards the location of the best fitness achieved so far by the particle itself and by location of the best fitness achieved so far across the entire population.

In the system model of our study, a node will either be equipped with 1 converter or none. Using the binary codification, the string ‘10010’ indicates the presence of converters at first and fourth node of a 5-node network. Hence the converter placement problem can be formulated as a binary programming problem and be solved by BPSO. The pseudocodes of the BPSO algorithm incorporated in the optimization process are shown in Table 1.

Table 1. Algorithm for BPSO-based converter placement problem solver

table-icon
View This Table
| View All Tables

4. Strategic search heuristic

Table 2. Search heuristic for single shortest-path connectivity topology

table-icon
View This Table
| View All Tables

η=CkNαCkN×100%
(3)

where N is the total number of network nodes, k is the number of wavelength converters, CkN is the binomial coefficient; and α 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

Fig. 1. Blocking probability vs. number of wavelength converters, k

Fig. 2. Efficiency η vs. number of wavelength converters

6. Conclusion

Acknowledgments

The authors from Multimedia University Malaysia wish to thank the Malaysia Ministry of Science, Technology & Innovation for supporting the research under the Intensification of Research in Priority Areas (IRPA) grant 09-99-01-0070-EA066.

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

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]

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]

5.

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.

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

  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.
  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), <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]
  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), <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]
  5. 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.

Figures

Fig. 1. Fig. 2.
 

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited