The Regenerator Location Problem

by Si Chen, Ivana Ljubic, S. Raghavan


Intro: In optical networks, the strength of an optical signal deteriorates as it gets farther from the source due to transmission impairments in the fiber (attenuation, dispersion, cross-talk). In other words, the distance an optical signal may be sent without losing or falsifying the information is limited. Therefore, it is necessary to regenerate the signals periodically using regenerators. Given an optical network, the regenerator location problem searches for the subset of regenerators to be installed at minimum cost, so that each pair of nodes can communicate with each other.

Definition: Mathematically, the regenerator location problem (RLP) can be described as follows. We are given:
  1. a network G = {N,F,D} where N is the set of nodes, F is the set of edges, and D is the associated distance matrix of edges,
  2. a maximum distance of dmax that determines how far a signal can traverse before its quality deteriorates and needs to be regenerated, and
  3. a non-negative cost w(i) for installing regenerator at node i, for each i in N.
The goal is to determine a subset of nodes L of minimum cost, such that for every pair of nodes in N there exists a path in G with the property that there is no subpath (i.e., a subsequence of edges on the path) with length > dmax without internal regenerators.
Complexity: The problem is NP-complete (see [1]).
In case of uniform regenerator costs, the RLP is equivalent to the Maximum Leaf Spanning Tree Problem (MLSTP) (aka the Minimum Connected Dominating Set problem).
Input graph G after preprocessing
(two nodes are connected iff the length of the
shortest path ≤dmax)
[Example]
A feasible RLP solution


[Example]
Corresponding MLSTP solution


[Example]
BENCHMARK INSTANCES
Data Format: Graphs are provided after preprocessing, i.e., we proceed with the distance matrix D as follows: a node pair (u,v) is connected by an edge iff the length of the shortest path between u and v is ≤dmax. The nodes that are not connected by an edge are called not directly connected or NDC node pairs.
  • Each instance file starts with "nNodes" which is the number of total nodes and then "nPairs" which is the number of NDC node pairs, followed by a nNodes x nNodes matrix A, denoted by "Cost", and followed by a list of NDC node pairs, denoted by "UnPairedArc". Finally, if instances are weighted, before providing the "Cost" matrix, a list of node weights, denoted by "Weight" is given.
  • a(u,v)=0 in the matrix "Cost" indicates that there is a direct connection between nodes u and v.
Bibliography:
  1. S. Chen, I. Ljubic, and S. Raghavan: The regenerator location problem, Networks 55(3): 205-220, 2010
Contact: ivana.ljubic @univie.ac.at