Algorithms for routing and wavelength assignment based on solutions of LP-relaxations

Abstract

In this letter, we consider the problem of maximizing the number of lightpaths that may be established in a wavelength routed optical network (WRON), given a connection matrix, i.e., a static set of demands, and the number of wavelengths the fiber supports. The problem of establishing all the connections of the connection matrix using the fewest number of wavelengths has been investigated in Banerjee and Mukherjee (1996) and Baroni et al. (1998). We call the former problem max-RWA (problem of maximizing the number of lightpaths) and the latter problem min-RWA (minimizing the number of wavelengths). In this letter, we only consider WRONs with no wavelength conversion capabilities. We formulate the max-RWA problem when no wavelength conversion is allowed as an integer linear programme (ILP) which may be solved to obtain an optimum solution. We hope to solve the ILP exactly for small size networks (few nodes). For moderately large networks (tens of nodes) we develop algorithms based on solutions obtained by solving the LP-relaxation of the ILP formulation. Results obtained for networks such as NSFNET and EONNET are presented.