Title :
An improved algorithm for optimal lightpath establishment on a tree topology
Author :
Xue, Guoliang ; Zhang, Weiyi ; Tang, Jian ; Thulasiraman, Krishnaiyan
Author_Institution :
Dept. of Comput. Sci. & Eng., Arizona State Univ., Tempe, AZ
Abstract :
Routing and wavelength assignment (RWA) aims to assign the limited number of wavelengths in a wavelength-division multiplexed (WDM) optical network so as to achieve greater capacity. In a recent paper, Datta et al. studied the problem of establishing a set of disjoint lightpaths on a tree topology using a single wavelength to maximize the total traffic supported by the chosen set of lightpaths. They discussed applications of this problem to RWA and presented a dynamic programming algorithm which optimally solves this problem in Oscr(n4+nDscr3) time, where n is the number of nodes in the network and Dscr is the maximum node degree. In this paper, we present an improved algorithm with a time complexity of Oscr(n2+nDscr2)
Keywords :
channel allocation; computational complexity; dynamic programming; optical fibre networks; telecommunication network routing; telecommunication network topology; telecommunication traffic; trees (mathematics); wavelength division multiplexing; RWA; WDM optical network; dynamic programming algorithm; lightpath establishment; network traffic; routing-wavelength assignment; tree topology; wavelength-division multiplexing; Dynamic programming; Heuristic algorithms; Network topology; Optical fiber networks; Optical wavelength conversion; Spread spectrum communication; WDM networks; Wavelength assignment; Wavelength division multiplexing; Wavelength routing;
Journal_Title :
Selected Areas in Communications, IEEE Journal on
DOI :
10.1109/JSAC-OCN.2006.22605