On-line optimal wavelength assignment in WDM networks with shared wavelength converter pool

ABSTRACT

In this paper, we study on-line wavelength assignment in wavelength-routed WDM networks under both unicast and multicast traffic where nodes in the networks have wavelength conversion ability. Since wavelength converters are still expensive and difficult to implement, we consider the case where nodes in networks have only a limited number of converters that are shared by all input channels. We study the problem of setting up connections in such networks using minimum number of wavelength converters. For unicast traffic, we first study the problem of setting up a lightpath on a given link-path with minimum number of conversions. We give a simple algorithm that solves it in O(tk) time where t is the number of links on the path and k is the number of wavelengths per fiber, as compared to the best known existing method that needs to construct an auxiliary graph and apply the Dijkstra's algorithm. We also consider the problem of setting up a lightpath while using wavelength converters at nodes with fewer available converters only when necessary, and give an O(tk) time algorithm. We then generalize this technique to WDM networks with arbitrary topologies and give an algorithm that sets up an optimal lightpath network-wide in O(Nk+Lk) time, where N and L are the number of nodes and links in the network, respectively. We also consider multicast traffic in this paper. Finding an optimal multicast light-tree is known to be NP-hard and is usually solved by first finding a link-tree then finding a light-tree on the link-tree. Finding an optimal link-tree is also NP-hard and has been extensively studied. Thus, we focus on the second problem which is to set up a light-tree on a given link-tree with minimum number of conversions. We propose a new multicast conversion model with which the output of the wavelength converter is split-table to save the usage of converters. We show that under this model the problem of setting up an optimal light-tree is NP-hard and then give efficient heuristics to solve it approximately.

REFERENCES

• 1: [1] B. Chen and J. Wang, "Efficient routing and wavelength assignment for multicast in WDM networks," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 97-109, Jan. 2002.
• 2: Ran Libeskind-Hadas , Rami Melhem, Multicast routing and wavelength assignment in multihop optical networks, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.621-629, October 2002 [doi>10.1109/TNET.2002.803907]
• 3: [3] D.-N. Yang and W. Liao, "Design of light-tree based logical topologies for multicast streams in wavelength routed optical networks," in Proc. IEEE INFOCOM, 2003, vol. 1, pp. 32-41.
• 4: [4] Y. Zhang et al., "An efficient heuristic for routing and wavelength assignment in optical WDM networks," in Proc. IEEE Int. Conf. Communications (ICC), 2002, vol. 5, pp. 2734-2739.
• 5: Lu Ruan , Dingzhu Du , Xiaodong Hu , Xiaohua Jia , Deying Li , Zheng Sun, Converter Placement Supporting Broadcast in WDM Optical Networks, IEEE Transactions on Computers, v.50 n.7, p.750-758, July 2001 [doi>10.1109/12.936240]
• 6: [6] B. Mukherjee, "WDM optical communication networks: Progress and challenges," IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1810-1824, Oct. 2000.
• 7: [7] W. Liang and X. Shen, "Improved lightpath (wavelength) routing in large WDM networks," IEEE Trans. Commun., vol. 48, no. 9, pp. 1571-1579, Sep. 2000.
• 8: [8] K.-C. Lee and V. O. K. Li, "A wavelength-convertible optical network," J. Lightw. Technol., vol. 11, no. 5, pp. 962-970, May-Jun. 1993.
• 9: [9] I. Chlamtac, A. Farag, and T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 909-913, Jun. 1996.
• 10: Walter J. Goralski, Optical Networking & WDM, Osborne/McGraw-Hill, Berkeley, CA, 2001
• 11: Rajiv Ramaswami , Kumar N. Sivarajan, Optical networks: a practical perspective, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 12: Ahmed Mokhtar , Murat Azizoğlu, Adaptive wavelength routing in all-optical networks, IEEE/ACM Transactions on Networking (TON), v.6 n.2, p.197-206, April 1998 [doi>10.1109/90.664268]
• 13: [13] C. Law and K. Y. Siu, "Online routing and wavelength assignment in single-hub WDM rings," IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 2111-2122, Oct. 2000.
• 14: Asuman E. Ozdaglar , Dimitri P. Bertsekas, Routing and wavelength assignment in optical networks, IEEE/ACM Transactions on Networking (TON), v.11 n.2, p.259-272, April 2003 [doi>10.1109/TNET.2003.810321]
• 15: Ezhan Karasan , Ender Ayanoglu, Effects of wavelength routing and selection algorithms on wavelength conversion gain in WDM optical networks, IEEE/ACM Transactions on Networking (TON), v.6 n.2, p.186-196, April 1998 [doi>10.1109/90.664267]
• 16: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 17: Hiroaki Harai , Masayuki Murata , Hideo Miyahara, Performance of Alternate Routing Methods in All--Optical Switching Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.516, April 09-11, 1997
• 18: [18] Z. Zhang and Y. Yang, "On-line optimal wavelength assignment in WDM networks with shared wavelength converter pool," in Proc. IEEE INFOCOM, 2005, pp. 694-705.
• 19: [19] L. H. Sahasrabuddhe and B. Mukherjee, "Light trees: Optical multicasting for improved performance in wavelength routed networks," IEEE Commun. Mag., vol. 37, no. 2, pp. 67-73, Feb. 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
      C.2.2 Network Protocols
          Subjects: Routing protocols
      C.2.3 Network Operations
          Subjects: Network management

General Terms:
Algorithms, Design, Management

Keywords:
multicast, on-line algorithms, optical networks, routing, shared wavelength converter pool, unicast, wavelength assignment, wavelength conversion, wavelength division multiplexing (WDM)