Optimal regenerator placement in translucent optical networks

The distance an optical signal can travel, before its quality degrades to a level that requires 3R-regeneration, is called the optical reach. In a translucent optical network, if an optical signal has to be communicated over a distance that exceeds the optical reach, the signal is regenerated at selected nodes of the network, so that the signal quality never degrades to an unacceptable level. Given a value of the optical reach, the goal of the Regenerator Placement Problem   (RPP), in networks handling ad-hoc demands for lightpaths, is to find the minimum number of nodes capable of 3R regeneration necessary in the network and their positions, so that every pair of nodes (u,v)(u,v) can establish a lightpath (either transparent or translucent) from u to v. In this paper we have presented two Integer Linear Program (ILP) formulations that can optimally solve the RPP problem for practical-sized networks within a reasonable amount of time. The first formulation works for networks having 35 nodes or less. The second formulation works for larger networks as well (we have reported results with up to 140 nodes). We have used a branch-and-cut approach to implement the second formulation, where we have intercepted the optimization process with control callbacks from the CPLEX callable library to introduce new constraints, as needed.