Regenerator site selection for mixed line rate optical networks with flexible routing

In this paper, we study the problem of regenerator site selection for mixed line rate optical networks. The objective is to minimize the number of regenerator sites for a given set of requests whose routing is flexible. We show that the problem is NP-complete and propose several heuristic algorithms to address the problem. The heuristic algorithms first order the set of requests based on several parameters, such as the flexibility in regenerator site selection for each request, the minimum number of required regenerator sites for each request, and the line rate of each request. The heuristics then route each request using an auxiliary graph approach that attempts to minimize the number of additional regenerator sites for a request. The performance of the proposed heuristic algorithms is compared via simulation.