Abstract
In this paper, we study the following problem. Given the network topology and traffic demand, determine how a minimum set of wavelength converters should be placed to ensure that the number of wavelengths needed will not exceed a given bound L+u, where L is the maximum link load in the network and u is a parameter defined by the network designer to reflect the overall availability of wavelength resources. This problem, however, is proved to be NP-hard. Hence we develop an efficient heuristic algorithm and extensive theoretical and experimental studies are carried out to verify the effectiveness and performance of the algorithm.
Chapter PDF
Similar content being viewed by others
Keywords
- Traffic Demand
- Wavelength Assignment
- Wavelength Converter
- Wavelength Division Multiplex Network
- Star Network
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Green, P.E.: Fiber-Optic Networks. Prentice-Hall, Cambridge (1992)
Green, P.E.: Optical Networking update. IEEE journal on Selected Areas on Communication 14, 764–779 (1996)
Elmirghani, J.M.H., Mouftah, H.T.: All-optical wavelength conversion technologies and applications in DWDM networks. IEEE Communications Magazine 38(3), 86–92 (2000)
Attygalle, M., Wen, Y.J., Nirmalathas, A.: Cascaded operation of all-optical wavelength converters based on nonlinear optical loop mirror, Lasers and Electro-Optics Society. In: LEOS 2002, November 10-14, vol. 2, pp. 463–464 (2002)
Kleinberg, J., Kumar, A.: Wavelength conversion in optical networks. In: Proc. 10th ACM-SIAM Symp. Discreate Algorithms (SODA), pp. 566–575 (1999)
Jia, X.H., Du, D.Z., Hu, X.D., Huang, H.J., Li, D.Y.: On the optimal placement of wavelength converters in WDM networks. Computer Communications 26, 986–995 (2003)
Jia, X.H., Du, D.Z., Hu, X.D., Huang, H.J., Li, D.Y.: Optimal placement of wavelength converters for guaranteed wavelength assignment in WDM networks. IEICE Trans. on Communication E85-B, 1731–1739 (2002)
Ramaswami, R., Sivarajan, K.N.: Routing and wavelength assignment in all-optical networks. IEEE/ACM Trans. Networking 3, 489–500 (1995)
Lee, K.C., Li, V.O.K.: A wavelength-convertible optical network. Journal on Lightwave Technology 11, 962–970 (1993)
Chlamtac, I., Ganz, A., Karmi, G.: Lightpath communications: an approach to high bandwidth optical WAN’s. IEEE Transactions on Communications 40(7), 1171–1182 (1992)
Kubale, M.: Graph colorings. American Mathematical Society, Providence (2004)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)
König, D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77, 453–465 (1916)
Shannon, C.E.: A theorem on coloring the lines of a network. J. Math. Phys. 28, 148–151 (1949)
Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz. 3, 9–17 (1964)
Wilfong, G., Winkler, P.: Ring routing and wavelength translation. In: Proc. 10th ACM-SIAM Symp. Discrete Algorithm (SODA), pp. 333–341 (1998)
Raghavan, P., Upfal, E.: Efficient routing in all-optical networks. In: Proc. 26th Annual ACM Symp. Theory of Computing (STOC), pp. 134–143 (1994)
Bafna, V., Berman, P., Fujito, T.: A 2-approximate algorithm for the undirected feedback set problem. SIAM Discrete Math. 12(3), 289–297 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 IFIP International Federation for Information Processing
About this paper
Cite this paper
Fang, C., Low, C.p. (2006). Optimal Wavelength Converter Placement with Guaranteed Wavelength Usage. In: Boavida, F., Plagemann, T., Stiller, B., Westphal, C., Monteiro, E. (eds) NETWORKING 2006. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems. NETWORKING 2006. Lecture Notes in Computer Science, vol 3976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11753810_87
Download citation
DOI: https://doi.org/10.1007/11753810_87
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34192-5
Online ISBN: 978-3-540-34193-2
eBook Packages: Computer ScienceComputer Science (R0)