TY - JOUR

T1 - On the routing and wavelength assignment in multifiber WDM networks

AU - Saad, Mohamed

AU - Luo, Zhi Quan

PY - 2004/11/1

Y1 - 2004/11/1

N2 - This paper addresses the problem of routing and wavelength assignment (RWA) in multifiber WDM networks with limited resources. Given a traffic matrix, the number of fibers per link, and the number of wavelengths a fiber can support, we seek to maximize the carried traffic of connections. We formulate the problem as an integer linear program (ILP), and show that the lightpaths selected by this formulation can indeed be established by properly configuring the optical switches. An upper bound on the carried traffic can be computed by solving the linear programming (LP)-relaxation of the ILP formulation. It is shown that this bound can be also computed exactly, and in polynomial-time, by solving a significantly simplified LP which considers only one wavelength. The bound can, thus, easily scale to an arbitrarily large number of wavelengths. Furthermore, we demonstrate that any instance of the RWA problem is also an instance of the more general maximum coverage problem. This allows us to take a greedy algorithm for maximum coverage and obtain an algorithm which provides solutions for the RWA problem that are guaranteed to be within a factor of (1 - (1/e)) of the optimal solution. Each iteration of the greedy algorithm selects a set of lightpaths that realizes, using one wavelength, the maximum number of connection requests not previously realized. Computational results confirm the high efficiency of our proposed algorithm.

AB - This paper addresses the problem of routing and wavelength assignment (RWA) in multifiber WDM networks with limited resources. Given a traffic matrix, the number of fibers per link, and the number of wavelengths a fiber can support, we seek to maximize the carried traffic of connections. We formulate the problem as an integer linear program (ILP), and show that the lightpaths selected by this formulation can indeed be established by properly configuring the optical switches. An upper bound on the carried traffic can be computed by solving the linear programming (LP)-relaxation of the ILP formulation. It is shown that this bound can be also computed exactly, and in polynomial-time, by solving a significantly simplified LP which considers only one wavelength. The bound can, thus, easily scale to an arbitrarily large number of wavelengths. Furthermore, we demonstrate that any instance of the RWA problem is also an instance of the more general maximum coverage problem. This allows us to take a greedy algorithm for maximum coverage and obtain an algorithm which provides solutions for the RWA problem that are guaranteed to be within a factor of (1 - (1/e)) of the optimal solution. Each iteration of the greedy algorithm selects a set of lightpaths that realizes, using one wavelength, the maximum number of connection requests not previously realized. Computational results confirm the high efficiency of our proposed algorithm.

KW - Greedy algorithms

KW - Integer linear programming (ILP)

KW - Multifiber networks

KW - Routing

KW - Wavelength assignment

UR - http://www.scopus.com/inward/record.url?scp=9744224396&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=9744224396&partnerID=8YFLogxK

U2 - 10.1109/JSAC.2004.829646

DO - 10.1109/JSAC.2004.829646

M3 - Article

AN - SCOPUS:9744224396

VL - 22

SP - 1708

EP - 1717

JO - IEEE Journal on Selected Areas in Communications

JF - IEEE Journal on Selected Areas in Communications

SN - 0733-8716

IS - 9

ER -