Routing and wavelength assignment in optical networks from edge disjoint path algorithms

Abstract

Routing and wavelength assignment (RWA) problems in wavelength-routed optical networks are typically solved using a combination of integer programming and graph coloring. Such techniques are complex and make extensive use of heuristics. We explore an alternative solution technique in the well-known maximum edge disjoint paths (EDP) problem which can be naturally adapted to the RWA problem. Maximum EDP is NP-hard, but now it is known that simple greedy algorithms for it are as good as any of the more complex heuristic solutions. In this paper we investigate the performance of a simple greedy maximum edge disjoint paths algorithm applied to the RWA problem and compare it with a previously known solution method.