Minimizing ADMs on WDM directed fiber trees
Tóm tắt
This paper proposes a polynomial-time algorithm for Minimum WDM/SONET Add/Drop Multiplexer Problem (MADM) on WDM directed fiber trees whether or not wavelength converters are used. It runs in timeO(m2n), wheren andm are the number of nodes of the tree and the number of the requests respectively. Incorporating T. Erlebachet al.’s work into the proposed algorithm, it also reaches the lower bound of the required wavelengths with greedy algorithms for the case without wavelength converters. Combined with some previous work, the algorithm reduces the number of required wavelengths greatly while using minimal number of ADMs for the case with limited wavelength converters. The experimental results show the minimal number of required ADMs on WDM directed fiber trees.
Tài liệu tham khảo
Ralf Klasing. Methods and problems of wavelength-routing in all-optical networks. InProc. MFCS98 Workshop on Communication, RWTH Press, Aachen, Aug. 1998, pp. 1–9.
John M Senior, Michael R Handley, Mark S Leeson. Developments in wavelength division multiple access networking.IEEECommunications Magazine, Dec. 1998, 36(12): 28–36.
Thomas Erlebach, Klaus Jansen, Christos Kaklamaniset al. Optimal wavelength routing on directed fiber tree.Theoretical Computer Science, 1999, 221: 119–137.
Barry R, Humblet P. Models of blocking probability in all-optical networks with and without wavelength changers.IEEE JSAC/IEEE-OSA JLT: Special Issue on Optical Networks, 1996, 14(5): 858–867.
Gerstel O, Sasaki G, Ramaswami R. Dynamic wavelength allocation in WDM ring networks with little or no wavelength conversion. InThe 34th Allerton Conf. on Communications, Control, and Computing, Monticello, IL, 1996, pp. 32–43.
Kovacevic M, Acampora A. Benefits of wavelength translation in all-optical clear-channel networks.IEEE JSAC/IEEE-OSA JLT: Special Issue on Optical Networks, 1996, 14(5): 868–880.
Raghavan P, Upfal E. Efficient routing in all-optical networks. InProc. the 26th ACM Symp. Theory of Computing, New York, 1994, pp. 134–143.
Liu Liwu, Li Xiangyang, Wang Pengjun, Frieder Ophir. Wavelength assignment in WDM rings to minimize SONET ADMs. InIEEE INFOCOM 2000, Tel Aviv, Israel, pp. 1020–1025.
Luisa Gargano, Ugo Vaccaro. Routing in all-optical networks. Algorithmic and graph-theoretic problems. InNumbers, Information and Complexity, Feb., 2000, pp. 555–578.
Gargano L. Limited wavelength conversion in all-optical tree networks. InProc. the 25th International Colloquium on Automata, Languages, and Programming (ICALP’98), LNCS 1443, Springer, Aalborg, Denmark, July 1998, pp. 544–555.
Auletta V, Caragiannis I, Kaklamanis Cet al. Efficient wavelength routing in trees with low-degree converters.Multichannel Optical Networks: Theory and Practice, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 1998, 46: 1–13.
Kumar V, Schwabe E. Improved access to optical bandwidth in trees. InProc. the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’97), New Orleans, Louisiana, 1997, pp. 437–444.