Wavelength rerouting in optical networks, or the Venetian Routing problem

TitleWavelength rerouting in optical networks, or the Venetian Routing problem
Publication TypeJournal Articles
Year of Publication2002
AuthorsCaprara A, Italiano GF, Mohan G, Panconesi A, Srinivasan A
JournalJournal of Algorithms
Pagination93 - 125
Date Published2002/11//
ISBN Number0196-6774
KeywordsApproximation algorithms, Label Cover, Optical networks, Shortest paths, Wavelength rerouting, Wavelength-division multiplexing

Wavelength rerouting has been suggested as a viable and cost-effective method to improve the blocking performance of wavelength-routed wavelength-division multiplexing (WDM) networks. This method leads to the following combinatorial optimization problem, dubbed Venetian Routing. Given a directed multigraph G along with two vertices s and t and a collection of pairwise arc-disjoint paths, we wish to find an st-path which arc-intersects the smallest possible number of the given paths. In this paper we prove the computational hardness of this problem even in various special cases, and present several approximation algorithms for its solution. In particular we show a non-trivial connection between Venetian Routing and Label Cover.