Placement of wavelength converters for minimal wavelength usage in WDM networks
Proceedings - IEEE INFOCOM - Tập 3 - Trang 1425-1431 vol.3
Tóm tắt
An important goal of the design of WDM (wavelength division multiplexing) networks is to use less wavelengths to serve more communication needs. According to the wavelength conflict rule, we know that the number of wavelengths required in a WDM network is at least equal to the maximal number of channels over a fiber (called maximal link load) in the network. By placing wavelength converters at some nodes in the network, the number of wavelengths needed can be made equal to the maximal link load. In this paper we study the problem of placing the minimal number of converters in a network to achieve that the number of wavelengths in use is equal to the maximal link load. For duplex communication channels, we prove that an optimal solution can be obtained in polynomial-time. For unidirectional communication channels, which was proved to be NP-complete, we develop a set of lemmas which lead to an efficient approximation algorithm whose approximation ratio is two.
Từ khóa
#Intelligent networks #WDM networks #Optical wavelength conversion #Wavelength division multiplexing #Communication channels #Wavelength converters #Computer science #Polynomials #Optical fibers #Spread spectrum communicationTài liệu tham khảo
10.1137/S0895480195294994
venugopal, 1999, A heuristic for placement of limited range wavelength converters in all-optical networks, IEEE INFOCOM, 908
10.1109/90.748086
wilfong, 0, Ring routing and wavelength translation, Proceedings of 9-th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (1998), 333
10.1016/0020-0190(82)90022-9
10.1109/90.793026
10.1109/65.145161
10.1145/195058.195119
mihail, 0, Efficient access to optical bandwidth, Proceedings of 36-th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 1995, 548
10.1109/65.139139
10.1006/jagm.2000.1137
10.1109/50.233260
10.1109/INFCOM.1999.751481
10.1109/35.825645
subramaniam, 1996, Connectivity and sparse wavelength conversion in wavelength-routing networks, IEEE INFOCOM, 148
bondy, 1976, Graph theory with applications, 10.1007/978-1-349-03521-2
10.1109/49.510913
10.1137/S0097539792241175
10.1109/2.84902
10.1137/0201013
garey, 1979, Comuters and intractability: A guide to the theory of NP-completeness
10.1145/347792.347808
hochbaum, 1997, Approximation algorithms for NP-hard problems
harder, 1998, Gossiping in WDM all-optical square mesh networks, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 48, 75, 10.1090/dimacs/046/07