## Abstract

Advances in the development of colorless and nondirectional reconfigurable optical add–drop multiplexers (ROADMs) enable flexible predeployment of optoelectronic regenerators (reshaping, retiming, and reamplifying known as 3R) in future optical networks. Compared to the current practice of installing a regenerator only when a circuit needs them, predeployment of regenerators in specific sites will allow service providers to achieve rapid provisioning such as bandwidth-on-demand service and fast restoration. Concentrating the predeployment of regenerators in a subset of ROADM sites will achieve high utilization and reduces the network operational costs. We prove the resulting optimization problem is NP-hard and provide the proof. We present an efficient heuristic for this problem that takes into account both the cost of individual circuits (regenerator cost and transmission line system cost) and the number of regenerator sites. We validate our heuristic approach with integer linear programming (ILP) formulations for a small network. Using specific network examples, we show that our heuristic has near-optimal performance under most studied scenarios and cost models. We further enhance the heuristic to incorporate the probability of demand for each circuit. This enables a reduction in the number of regenerator sites by allowing circuits to use costlier paths if they have lower probability of being needed. We also evaluate the heuristic to determine the extra regenerator sites required to support diverse routing. In this paper, we provide detailed analysis, pseudocodes, and proofs for the models presented in our previous work [Nat. Fiber Optic Engineers Conf., 2012, NW3F.6; 9th Int. Conf. on Design of Reliable Communication Networks (DRCN), 2013, 139] and compare the heuristic results with ILP for a small-scale network topology.

© 2013 Optical Society of America

## I. Introduction

Traffic on backbone networks has increased by four orders of magnitude over the past 12 years and estimates on the growth rate going forward vary from 30% to 40% per year [1]. Though there has been rapid growth in traffic, the revenues of the telecommunication carrier are not keeping pace with this explosive growth. In order to bridge the gap and to sustain this traffic growth, the cost-effectiveness of optical networks must continue to improve. To date, advances in optical networks have mainly been in three areas: 1) improvements in fiber capacity, 2) improvements in optical reach (the distance over which a wavelength signal can be transmitted with adequate fidelity), and 3) the development and widespread adoption of reconfigurable optical add–drop multiplexers (ROADMs). If a circuit’s path is longer than the system’s optical reach (typically 1500–2800 km for modern long-haul systems), then one or more optoelectronic regenerators must be used to restore the signal, and each regenerator adds a cost comparable to a pair of endpoint transceivers. ROADMs enable any wavelength to bypass a node, terminate at the node, or be regenerated to maintain signal quality. Optical bypass allows operators to deploy far fewer transponders and regenerators, yielding significant cost savings [2–4]. At junction nodes where more than two fiber pairs meet, ROADMs also allow wavelength routing from any link to any other link, forming an optical mesh network.

The next generation of backbone networks will be deployed with ROADMs that are both colorless (any add/drop port can serve any wavelength) and nondirectional (any add/drop port can be routed to any internode path) [4]. Without these capabilities, each regenerator connected to the ROADM would be tied to a specific internode fiber pair and to a predetermined wavelength. In contrast, colorless and nondirectional ROADMs shown in Fig. 1 make it economically feasible to predeploy regenerators, enabling recovery from network failures without the need for manual intervention and dramatically reducing mean time to repair (MTTR) [5]. Regenerator predeployment also supports more rapid provisioning [6] and improved network efficiency through traffic grooming at the optical layer [7]. Finally, it is a necessary step on the path to more dynamic optical networks [8]. However, considering regenerator cost, it behooves system operators to predeploy them as efficiently as possible. Reducing the number of sites (we use “site” and “location” interchangeably) at which regenerators are predeployed can be an effective means of accomplishing this, provided one picks the regenerator sites wisely [9].

During the network design and planning process, selected network nodes (typically ROADMs) are designated as regenerator sites. The regenerator sites subset is chosen to ensure that regenerators can be placed among the set to satisfy the optical reach constraint for every possible demand. In some cases, additional requirements may also be placed on the routes allowed for a demand. The problem of picking a minimum set of regenerator sites $RS$ is defined as the regenerator location or placement problem (RLP) [10,11]. The problem has been studied in two flavors: 1) the unconstrained-routing regenerator location problem (URLP) and 2) the explicit-routing regenerator location problem (ERLP). URLP does not limit circuit routing in any way. While the solution may be optimal in a number of regenerator locations, individual circuits may incur high cost as a result of using longer routes or using more regenerators. ERLP constrains each route to a specified (typically min-distance) path, but individual circuits may use more regenerators than necessary. Reference [12] proves that URLP is NP-hard. The authors of [12] also propose and compare three heuristics for URLP. Reference [13] uses a biased random-key genetic algorithm to solve the URLP with improved results. Reference [14] proves the hardness of several different variants of the regenerator placement problem and gives approximation algorithms with worst-case performance guarantees.

Most previous RLPs have focused on minimizing the number of regenerator sites while still being able to route a circuit between any node pair [15,16]. While minimizing the number of sites is an important consideration, it should be balanced with the sum of the cost of individual circuits. So there are two additional major considerations to the overall network cost: 1) the cost of an individual circuit depends on the number of regenerators used as well as its transmission distance and 2) traffic demands in production networks tend to be highly nonuniform, meaning that the probability of a demand varies greatly among node pairs.

We take a holistic view of minimizing overall network cost by considering all three factors. We have proposed a new routing-constrained regenerator location problem [17] that constrains the connections to use least-cost paths (including the cost of regeneration). The cost model can be extended to include the transmission distance (which affects the cost of fiber, buildings, and amplifiers), as well as the regenerator count. For some customers with strict latency requirements, shorter transmission paths are needed, above and beyond the cost of the optical path. We build upon the routing-constrained regenerator location problem in [17] to take into account these additional practical considerations. The heuristics also incorporate [18] a projected traffic matrix to explore the trade-off between the cost of each circuit and the number of $|RS|$. For example, if a node pair is unlikely to have significant traffic, its path could be slightly more costly than the minimum cost path—if that enables $|RS|$ to be further reduced. In our heuristic, the allowable path cost deviation for each node pair is roughly inversely proportional to the probability of a connection between that node pair. The overall goal remains to minimize the total network cost, defined as the sum of a per-site cost and the total cost of active circuits. This paper goes beyond that presented in [18] by providing more detailed proofs, pseudocodes, integer linear programming (ILP) formulation for the problem, and comparison of the heuristic solution with ILP on a small-scale network topology.

The rest of the paper is organized as follows. In Section II, we start by defining a simple version of the problem where the cost of a circuit is given solely by the number of regenerators being used. We illustrate the problem with a small example network and provide a proof of NP-hardness. In Section III, we explain the proposed heuristic approach for reducing the regenerator sites and network costs and describe several variations. A lower bound on the optimal solution is provided. In Section IV, we propose a trade-off for reducing the number of regenerator sites by allowing a small increase in the cost of low-probability circuits. We determine the extra regenerator sites needed for link-disjoint paths in Section V. Section VI contains the experimental evaluation results of our algorithms on large-scale network topologies. Finally, in Section VII, we summarize the work and outline possible extensions.

## II. Problem Definition

We start by defining a version of the problem where the cost of a circuit is given only by the number of regenerators being used (in most cases, this is the dominant variable component of the circuit cost). The goal is to minimize the number of regenerator sites subject to the constraint that each circuit uses a minimum possible number of regenerators. This allows us to present the main ideas of the heuristic in a simple setting. Then as we add more parameters to the problem, we outline the necessary changes to the heuristic.

Let $\text{minregen}(u,v)$ be the minimum number of regenerators needed on any
route between nodes $u$ and $v$ assuming that regenerators are available at
*all* nodes. A route ${P}_{uv}$ between nodes $u$ and $v$ is called a *constrained* route if
it uses $\text{minregen}(u,v)$ regenerators. The constrained-routing regenerator
location problem (CRLP) can be formally defined as follows: given network topology
with link distances, and maximal optical reach distance, find a minimum set of
$RS$ such that between each node pair, at least one
constrained route is reachable using a subset of regenerators in
$RS$.

Figure 2 shows an example network with 10 nodes and 11 links. For simplicity, we assume that the link lengths are equal and the optical reach is 2.5 times the link length. For URLP, we need to place regenerators at only three locations: $RS=\{A,E,I\}$. Using just these three regenerator sites, every node pair has a valid path, but some of these paths (e.g., A–D) use more regenerators and more distance than they would if regenerator sites were unrestricted. For ERLP, we require shortest-distance routing between any two nodes and find that five locations are needed: $RS=\{A,C,E,G,I\}$. For CRLP using min-regeneration routes, where we have a little bit more freedom to select routes, the $RS$ set is reduced to four locations: $RS=\{A,J,D,F\}$. In this example, we found that URLP, with the most freedom to select routes, has the fewest regenerator locations in the solution, but involves more costly circuits, while ERLP, with no freedom to select routes, requires more regenerator locations, and CRLP lies in between.

We next formally prove the hardness of the CRLP problem. We define a *decision
version* of the CRLP problem (DCRLP) as follows: given network topology
with link distances and the optical reach distance, is there a set of
$K$
*or fewer regenerator sites,*
$RS$, such that between each node pair, at least one
constrained route is reachable using regenerators in $RS$.

**Theorem 1**. *DCRLP is NP-hard.*

*Proof:* Our proof uses a reduction from the vertex cover problem
(VCP) [19] to DCRLP. The VCP is defined as
follows: given an undirected graph $G=(N,E)$, where $N$ and $E$ represent a set of vertices and a set of edges,
respectively, and a positive integer $K\le |N|$, the VCP asks if there is a subset
${N}_{0}\subset N$ of cardinality at most $K$ such that ${N}_{0}$ contains at least one of the two endpoints of each
edge in $E$.

Given an instance ${I}_{1}$ of VCP $(N,E,K)$, we construct the corresponding instance ${I}_{2}$ of DCRLP $(N\prime ,E\prime ,K)$ by the following transformation. (An example is shown in Fig. 3.) 1) For any ${n}_{i}\in N$, create a network node ${n}_{i}\in N\prime $; 2) for any ${e}_{i}\in E$, create one node ${e}_{i}\in N\prime $, and add the following links in $E\prime $: $({e}_{i},{n}_{k})$ and $({e}_{i},{n}_{l})$, where ${n}_{k}$ and ${n}_{l}$ are two end nodes of ${e}_{i}$; 3) add two extra nodes $s$ and $t$ to $N\prime $, and add the following links to $E\prime $: $(s,{e}_{i})$ for any node ${e}_{i}$ and $(t,{n}_{j})$ for any node ${n}_{j}$; 4) add two nodes $S$ and $T$ in $N\prime $, and links $(s,S)$ and $(t,T)$ to $E\prime $; 5) for any node ${e}_{i}\in E$, we create another node ${E}_{i}$ in $N\prime $, and add links $({e}_{i},{E}_{i})$ to $E\prime $. Now we have graph $G\prime =(N\prime ,E\prime )$. Clearly, ${I}_{2}$ can be constructed from ${I}_{1}$ in polynomial time.

If we assume the optical reach to be one hop, we have the following observations on ${I}_{2}$:

- • If $d(x,y)$ denotes the minimum hop distance between nodes $x$ and $y$, we have $d(s,{e}_{i})=1$, $d(t,{n}_{j})=1$, $d(s,{n}_{j})=2$, $d(t,{e}_{i})=2$, and $d(s,t)=3$. If ${n}_{j}$ is an end node of ${e}_{i}$, then $d({e}_{i},{n}_{j})=1$; else $d({e}_{i},{n}_{j})=3$. Moreover, $d({e}_{i},{e}_{j})=2$ and $d({n}_{i},{n}_{j})=2$.
- • It is straightforward to see that $S$, $T$, and ${E}_{i}$ will not be selected as regeneration sites. On the other hand, $s$, $t$, and ${e}_{i}$ must be in
*RS*because $S$, $T$, and ${E}_{i}$ have to use $s$, $t$, and ${e}_{i}$, respectively, as regeneration sites for their traffic. - • To find a feasible solution of ${I}_{2}$, we need to examine possible regenerator sites (from nodes ${n}_{i}$) for node pairs between $t$ and ${e}_{i}$, ${E}_{i}$, $s$, or $S$.

Based on the observation above, the reduction follows from

- • If ${I}_{2}$ has a feasible solution, say set $R$ of regenerator sites, then node set $R\text{\hspace{0.17em}}\cup \text{\hspace{0.17em}}\{s,t,{e}_{i}\}$ is a feasible solution for ${I}_{1}$.
- • Conversely, suppose the instance ${I}_{1}$ of VCP has a feasible solution of node set $R\prime $; then node set $R\prime \text{\hspace{0.17em}}\cup \text{\hspace{0.17em}}\{s,t,{e}_{i}\}$ is a feasible solution of ${I}_{2}$.
- • Since VCP is NP-hard, we conclude that DCRLP is also NP-hard.

An algorithm for finding an optimal solution for CRLP can solve DCRLP by checking whether its solution has cardinality at most $K$. Thus we get the following:

**Corollary 1**. *If*
$P\ne NP$, *then no polynomial-time algorithm can find
an optimal solution to CRLP*.

*Proof*. We start the proof with an assumption that there exists a
polynomial-time optimal solution for CRLP when $P\ne NP$. Then it is easy to see that the optimal solution
can answer the feasibility of DCRLP. If the cardinality of the optimal solution is
$\le K$, then there exists a feasible solution for the
corresponding DCRLP; otherwise there is no solution. Thus, if there is a
polynomial-time optimal solution to CRLP, there is a polynomial-time solution to
DCRLP. However, we have proved that DCRLP is NP-hard. Therefore, our assumption is
invalid, and hence there is no polynomial-time optimal solution for CRLP when
$P\ne NP$.

## III. Greedy CRLP Heuristic

We first transform the CRLP problem into a graph problem of finding a set of nodes covering min-hop paths. Many other papers [20] and [21] have considered similar transformations. We augment the network graph by adding edges $(i,j)$ whenever nodes $i$ and $j$ are within the reach distance. Now all node pairs within the reach distance have a direct edge between them. An example transformation is shown in Fig. 2. Let us call the resulting graph ${G}_{A}$; then we claim a $1:1$ correspondence between min-regeneration paths in the network and min-hop paths in ${G}_{A}$.

**Lemma 1**. *If*
$P$
*is a min-hop path in*
${G}_{A}$, *then placing a regenerator on each
internal node of*
$P$
*results in a valid min-regeneration path in the network. Moreover for every
valid min-regeneration path in the network, we have a min-hop path in*
${G}_{A}$
*with direct links between adjacent pairs of regenerator sites*.

*Proof*. The proof follows from the following two observations showing
a $1:1$ correspondence between paths in
${G}_{A}$ and regenerator placements.

**Observation 1**: Consider a path in ${G}_{A}$. We know that any two adjacent nodes are within the
reach distance, so by placing a regenerator on each internal node and by replacing
any edges not in the network by a path of distance less than the reach distance, we
get a valid path in the network.

**Observation 2**: Suppose we start with a valid path in the network.
Consider the sequence of nodes where regenerators have been placed and we know that
any adjacent pair must be within the reach distance and hence should have a direct
link in the augmented graph ${G}_{A}$. So we can map the path in the network to a path in
${G}_{A}$ where the internal nodes are precisely the set of
nodes receiving regenerators placements.

In order to prove the claim on min-regeneration versus min-hop paths, consider a min-hop path $P$ with $k+1$ hops (and $k$ internal nodes). By Observation 1, we know that this maps to a $k$-regenerator valid path. We next show that this is indeed a min-regeneration path. Suppose not, and we have a path between these pairs of nodes with $k-1$ or fewer regenerators; then, by Observation 2, we get a path with $k-1$ or fewer internal nodes, contradicting that $P$ is a min-hop path.

To prove the other direction, consider a min-regeneration path with $k$ regenerators. By Observation 2, this maps to a path in $P$ in ${G}_{A}$ with $k$ internal nodes. Suppose $P$ is not a min-hop path; then there is a path $P\prime $ of fewer than $k$ intermediate nodes. By Observation 1, $P\prime $ can be transformed into a valid path with fewer than $k$ regenerators, thus leading to a contradiction.

So we have reduced the CRLP problem to picking a subset of nodes,
$RS$, such that each pair of nodes has a min-hop path in
${G}_{A}$ with all internal nodes in
$RS$. We describe the generic heuristic also called the
*barebone* heuristic, and the pseudocode is given in Algorithm 1.
The greedy heuristic maintains the following data structures:

- • A set $C$ of candidate regenerator sites (for future placement). Initialized to set $N$ (line 1).
- • A binary path matrix $P$ [initialized to the adjacency matrix of ${G}_{A}$ (line 4)] such that ${P}_{ij}$ is 1, if and only if we have a valid min-hop path between nodes $i$ and $j$ using the reach distance and regenerator site selected so far. The heuristic stops when all entries in $P$ are 1.
- • Min-hop matrix $D$ such that ${D}_{ij}$ gives the min-hop distance in $G$ between $i$ and $j$. Using the all-pairs shortest path (APSP), we compute the min-hop distance for all node pairs in ${G}_{A}$ (line 5). The matrix $D$ lets us check whether a node $v$ belongs to the min-hop path from $i$ to $j$: where ${D}_{iv}+{D}_{vj}$ is the length of the min-hop path from $i$ to $j$ that includes node $v$. By definition it is at least the length of the min-hop path, and the equality will happen when there is indeed a min-hop path going through node $v$.

This generic greedy heuristic picks what appears to be the next best (line 8) site from among nodes in $C$ (to be elaborated shortly), updates its data structures, and repeats these steps until all source-destination pairs have valid min-hop paths (in ${G}_{A}$) using existing regenerator sites. In the next few subsections, we give a number of customized enhancements to this heuristic, including a way of estimating how far it is from the optimal.

We use the $O(|E|+|N|)$ breadth-first search to compute the single-source shortest min-hop path and the $O({|N|}^{3})$ Floyd–Warshall algorithm for computing the APSP.

#### A. Seeding the Greedy Algorithm

For any node pair $(a,z)$, we have to place a regenerator on all
intermediate nodes in a min-hop path. *A priori*, we do not know
which min-hop path will be used. However, if node $v$ is in *all* min-hop paths
between $a$ and $z$, then a regenerator must be placed on node
$v$. Let us call this set of nodes
${R}^{+}$. Seed the algorithm by placing a regenerator on
all nodes in ${R}^{+}$.

Conversely, if node $u$ is not in any min-hop path, then an optimal regenerator assignment will not place a regenerator on node $u$. Let us call this set of nodes ${R}^{-}$.

We start by placing a regenerator at every node $v$ in ${R}^{+}$. If this regenerator placement creates a valid
$(i,j)$ path, then we update ${P}_{ij}=1$. Finally, we initialize the set of candidate
regenerator sites $C=N\backslash ({R}^{+}\text{\hspace{0.17em}}\cup \text{\hspace{0.17em}}{R}^{-})$. The set ${R}^{+}$ can be computed in $O(|E|\times {|N|}^{2})$ time by iterating over all nodes
$v$ and checking if deleting
$v$ changes the min-hop distance for at least one
pair. The set ${R}^{-}$ can be computed in $O({|N|}^{3})$ time by iterating over all nodes
$v$ and checking that for each pair
$(a,z)$, the shortest $a\text{-}z$ path *through*
$v$ is longer than the shortest
$a\text{-}z$ path.

#### B. Rank Function for Selecting Best Candidate

We use two different rank functions for picking the “best” candidate in $C$. One reasonable choice is to select the node that belongs to min-hop paths of the highest number of pairs from those that do not already have a valid path. Mathematically, we can define this rank of a candidate node as

The first term in the Boolean AND expression says that $(i,j)$ does not already have a path, and the second term says that $v$ is in a min-hop path between $i$ and $j$.

Another possibility is to only count source-destination pairs, which obtain a valid path as a result of placing a regenerator on node $v$:

While Eq. (2) results in a rapid convergence, it has a problem. During the initial phase of the heuristic, no single regenerator placement may result in a valid path, thereby assigning the rank of zero to all candidate nodes. We get around this by considering a weighted combination of the two rank rules, with a large weight assigned to the ramp as

The overall effect of using Eq. (3) is that the $\mathrm{ramp}(v)$ has the dominant effect in picking the “best” candidate, but if it cannot distinguish among multiple candidates, then the ${\mathrm{rank}}_{1}(v)$ acts as a tiebreaker.

#### C. Postprocessing to Improve the Solution

The greedy algorithm never deletes a site after it gets selected. So it is possible that it may select node ${v}_{1}$, but then a set of nodes selected later covers all source-destination pairs that ${v}_{1}$ was originally covering, rendering ${v}_{1}$ superfluous.

We add a simple postprocessing (PP) step. For each regenerator site $v$ in the output, we check whether deleting $v$ still enables all source-destination pairs to have valid paths. If yes, we delete $v$ and then repeat the check for the next node. We stop if we cycle through all nodes without being able to delete any of them.

Checking whether $v$ can be deleted is similar to checking its membership in ${R}^{+}$ and takes $O(|E|\times |N|)$ time. In the worst case, each deletion may require checking all nodes in the output, so altogether it can take time $O(\#\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}\text{\hspace{0.17em}}RS\times (\#\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{of deletions in}\text{\hspace{0.17em}}\mathrm{PP})\times |E|\times |N|)$.

Algorithm 2 depicts the CRLP heuristic with seeding ${R}^{+}$, ${R}^{-}$, and PP. The procedure for computing the set
${R}^{+}$ is described in lines 7–10. Line 11
assigns ${R}^{+}$ to regenerator sites $RS$ and updates the data structure (line 12). After
computing ${R}^{-}$ (line 13), the candidate set
$C$ is determined (line 14). The rank rules given
in Eqs. (1) and (3) are used to determine the best
candidate node, and the data structures are updated accordingly, until all node
pairs have a reachable path using the given $RS$ (lines 15–19). Finally, PP is used to
eliminate redundant *RS* (line 20).

#### D. Time and Space Complexity

The running time is given by

It is possible to improve these running times by use of more sophisticated dynamic graph algorithms and (for computing ${R}^{+}$) by adapting algorithms for the related problem of “most vital nodes.” We chose the simplest algorithms for ease of implementation and because the running times (less than 2 s, on a generic PC with 2.3 GHz CPU, for our 75 node topology) suffice for our purpose. We will show later that we get near-optimal results with this heuristic. In contrast, our attempt at ILP-based solutions (without any special customization) ran out of memory even with commercial packages.

#### E. Comment on ${R}^{+}$, ${R}^{-}$, and Lower Bound

The heuristic can be implemented without ${R}^{+}$ and ${R}^{-}$ and will still yield a solution in which all node pairs have valid paths. They serve different purposes.

Any reasonable ranking algorithm would leave out nodes from ${R}^{-}$, so not having ${R}^{-}$ does not change the behavior of the algorithm. The usefulness of ${R}^{-}$ is that, rather than computing the rank of the nodes in ${R}^{-}$ in each iteration, we exclude them after a one-time computation of $O({|N|}^{3})$.

${R}^{+}$ serves a more critical role. By seeding the algorithm with this set, it can hopefully lead to a better-quality solution. Moreover, as the following theorem shows, it can also be used to get a bound on how far the heuristic is from the optimal solution.

**Theorem 2**. *If the heuristic gives a solution of
cardinality*
$|{R}^{+}|$, *then it is optimal.
Otherwise,*
$1+|{R}^{+}|$
*is a lower bound on the cardinality of any solution*.

*Proof*. By definition of ${R}^{+}$, any solution must contain all nodes in
${R}^{+}$, so a heuristic solution of
${R}^{+}$ is certainly optimal. To see the claim on
$|{R}^{+}|+1$, notice that the only way the heuristic does
*not* stop at ${R}^{+}$ is if those regenerators are not sufficient, so
that we need at least one more regenerator.

For the networks we have tested so far, the solution produced by the heuristic turns out to be within at most 1 or 2 of the lower bound. There are many advantages to deriving a lower bound: It allows us to assess how far we are from the optimal without having to compute the optimal. It also gives us an efficient way to compute the optimal. For example, if we know that the heuristic solution is (say) within 3 of $|{R}^{+}|$, we can try a brute-force approach of adding one site (all $|N|$ possibilities) to ${R}^{+}$ and then checking whether any of them cover all node pairs. If not, we try all possible pairs of sites and finally all possible triplets of sites. Because of the upper bound given by the heuristic, we know that at least one of these $O({|N|}^{3})$ possibilities would succeed and give us the optimal set of regenerator sites.

It is also possible to improve this lower bound by treating the path matrix as the adjacency matrix of a graph and realizing that the resulting graph’s diameter decreases by at most 50% as a result of a single regenerator placement. This will give a lower bound $(LB)$:

where ${d}_{p}$ represents the diameter of the path matrix.#### F. Minimum Cost Paths

A min-regeneration path is not necessarily min-distance and vice versa. As an example, consider nodes $a$ and $z$ connected by two disjoint paths ${R}_{1}=a-v1-v2-v3-z$ and ${R}_{2}=a-v4-v5-z$. If the reach distance is 2000 km, the length of each link in ${R}_{1}$ is 1050 km, and the length of each link in ${R}_{2}$ is 1950 km, then ${R}_{1}$ is the shortest ($=\text{min-distance}$) path. But note that ${R}_{1}$ requires three regenerators, whereas ${R}_{2}$ requires only two and so is the min-regeneration path. Thus, we see that min-regeneration paths may incur distance penalty, also described as excess wavelength-kilometer penalty, and min-distance (shortest) paths may incur a regeneration penalty. By incorporating wavelength-kilometer as well as the number of regenerators in the cost model of the path (circuit), one can achieve the required trade-offs. We can define the cost of a path $R$ as

We modify the heuristic to find min-cost paths instead of min-regeneration paths as follows:

- 1) Change the definition of ${R}^{+}$ to the set consisting of nodes that belong to all min-cost paths between $a$ and $z$. A similar change applies to the definition of ${R}^{-}$.
- 2) Change the definition of the path matrix; $P$: ${P}_{ij}$ is 1 if we have a valid min-cost path between nodes $i$ and $j$ using the given regenerator placement.
- 3) The condition ${D}_{iv}+{D}_{vj}={D}_{ij}$ now applies to min-cost paths.

## IV. Number of Regenerator Sites Versus Cost of Paths

So far, we have applied a rigid constraint to min-cost paths only. However, the
number of regenerator sites can be further reduced if we allow the heuristic to pick
paths that are slightly more costly for rarely used routes. We extend the heuristic
to use a *latitude matrix*, $L$, such that for node pair $(i,j)$, we are allowed to pick any path that is of cost
within $1+{L}_{ij}$ of the min-cost $(i,j)$ path. If we have a traffic projection, we will
typically assign small or zero latitude to node pairs with heavy traffic demand and
larger latitude to node pairs with low traffic demand. The necessary changes to the
heuristic are as follows:

- 1) Change the definition of ${R}^{+}$ to the set consisting of nodes that belong to all paths between $i$ and $j$ of cost less than $1+{L}_{ij}$ of the min-cost $(i,j)$ path. To test the membership of node $v$ in ${R}^{+}$, we check whether deleting $v$ changes the min-cost path for at least one pair $(i,j)$ by more than a multiplicative factor of $1+{L}_{ij}$. A similar change applies to the definition of ${R}^{-}$.
- 2) Change the definition of the path matrix; $P$: ${P}_{ij}$ is 1 if we have a valid path between nodes $i$ and $j$ using the given regenerator placement such that the cost of the path is within $1+{L}_{ij}$ of the min-cost $(i,j)$ path.
- 3) In PP, for each node $v$ in the output, we check whether deleting $v$ still enables all source-destination pairs $(i,j)$ to have valid paths of cost within $1+{L}_{ij}$ of the min-cost $(i,j)$ path. We would like to point out a subtlety here with an example. If latitude is 5% and say the path with the original output is within 102% of the min-cost and deleting node $v$ raises the cost to 104% of min-cost, then we still delete node $v$ as the cost is within the threshold of latitude. So this is unlike the case without any latitude, where any increase suggests that node $v$ cannot be deleted from the output.

We present simulation results for several possible choices of the latitude matrix in Section VI.

## V. Regenerator Sites for Diverse Routes

Survivable optical networks can reconfigure and set up a connection upon failure, as
discussed in prior work [22]. Fast
reconfiguration for survivability can be achieved using
*link-disjoint* primary and backup (secondary) paths that are
precomputed for each request. For a given request, we use the path from CRLP as the
primary path, which carries the traffic under normal operation, while the backup
path is used upon link failure. Backup paths are usually unconstrained; here we
assume that they can share nodes with primary paths, as long as there are no shared
links (in our experience, complete ROADM failures are extremely rare events).

In this section we evaluate the proposed CRLP heuristic described in Section III for survivable optical networks. We determine the set of additional regenerator sites $({\mathrm{\Delta}}_{RS})$ required for the node pairs to have a valid reachable secondary path (if a disjoint path exists). We define $R{S}_{D}=R{S}_{\mathrm{CRLP}}\text{\hspace{0.17em}}\cup \text{\hspace{0.17em}}{\mathrm{\Delta}}_{RS}$, where $R{S}_{\mathrm{CRLP}}$ refers to the set of regenerator sites obtained using the CRLP heuristic.

First, let us return to the example network shown in Fig. 2. Note that for this topology, all node pairs have a disjoint path for the primary CRLP path. We have a CRLP solution for min-regeneration paths as shown in Fig. 2. For every node pair there exists a min-regeneration primary path, which we denote as $(\mathcal{R})$. We designate the disjoint path $(\mathcal{R}\prime )$ as valid if and only if it is reachable using the existing set of regenerator sites. For instance the min-regeneration path for node pair (B, E) is ${\mathcal{R}}_{BE}=\mathrm{B}\u2013\mathrm{C}\u2013\mathrm{D}\u2013\mathrm{E}$, and the disjoint path, ${\mathcal{R}}_{BE}\prime =\mathrm{B}\u2013\mathrm{A}\u2013\mathrm{I}\u2013\mathrm{J}\u2013\mathrm{E}$, is valid via regeneration at locations A and J. As an example of a node pair without a valid disjoint path, consider (A, D) with ${\mathcal{R}}_{AD}=\mathrm{A}\u2013\mathrm{I}\u2013\mathrm{J}\u2013\mathrm{E}\u2013\mathrm{D}$ and ${\mathcal{R}}_{AD}\prime =\mathrm{A}\u2013\mathrm{B}\u2013\mathrm{C}\u2013\mathrm{D}$. We define the diverse percentage $({p}_{d})$ as the percentage of node pairs with a valid disjoint path. For the network in Fig. 2, using $R{S}_{\mathrm{CRLP}}=\{A,D,J,F\}$, there are $10\times 9/2=45$ node pairs ($np$), and only 26 node pairs have valid $\mathcal{R}\prime $, so ${p}_{d}\approx 58\%$. If we require ${p}_{d}=100\%$ for the Fig. 2 network, then we must add sites in addition to the set $R{S}_{\mathrm{CRLP}}$.

An iterative process is used to choose these extra sites from candidate set ${C}_{D}$, defined as the set of intermediate nodes present in all the invalid disjoint paths (${\mathcal{I}}_{D}$), but $\notin R{S}_{\mathrm{CRLP}}$. In each iteration, we select a node ${c}_{d}\in {C}_{D}$ that belongs to the largest number of invalid disjoint paths $\mathcal{F}({c}_{d})$. For the network in Fig. 2, we have $\mathcal{F}(B)=14$. Adding node $B$ as a regenerator site increases ${p}_{d}$ to 84.4%. Finally, including node H (or node G) as well enables all node pairs to have a valid disjoint path, so that $({p}_{d}=100\%)$. Thus we select ${\mathrm{\Delta}}_{RS}=\{B,H\}$. For cost reasons, operators usually design optical networks to provide disjoint backup paths for most, but not all, possible node pairs. The few node pairs without valid disjoint paths might have backup paths transported over a disjoint path on an alternate or preexisting optical layer.

## VI. Experimental Evaluation

In this section, we evaluate the performance of the proposed CRLP heuristic for various backbone network topologies. We have studied two networks: 1) a US mesh network (USMESH) with 24 nodes and 43 bidirectional links [20] with modified link distances shown in Fig. 4 and 2) a continental US topology (CONUS) with 75 nodes and 99 bidirectional links shown in Fig. 6. CONUS is a fiber-optic backbone network developed for use in the research of large-scale DWDM networks [23].

We have compared the CRLP heuristic with an optimal ILP^{1} solution for min-regeneration on the USMESH topology. For reach distances of
1400, 1800, 2000, 2400, and 2500 km, the numbers of regenerator sites were 17,
12, 11, 8, and 9, respectively, for both the CRLP heuristic and the ILP solution.
From Fig. 5(b), we observe that
regenerator sites increase for a reach distance of 2500 km. By placing a
regenerator at node 11 (not a regenerator location for reach 2400 km), we have
a min-regeneration path for node pair (2, 15). For reach distance of 2400 km,
the node pair (2, 15) requires two regenerators along the shortest-path
(2–6–11–15). However, the algorithm picks the min-regeneration
path 2–6–9–12–11–15, with regenerations at 9 and
12, as these cover more node pairs than 6 and 11. From Fig. 5(b), we see the solutions from both methods
also include exactly the same individual regeneration locations. We did not evaluate
(optimal) ILP solutions for the CONUS topology because of the very long time to run
on a regular desktop (it also ran out of memory in several instances), but the lower
bound discussed in Subsection III.E
allows us to assess how far our heuristic is from the optimal.

For the rest of paper, we have evaluated the CONUS network because of its close
resemblance to carrier backbone networks. In Fig. 6 we show the *RS* for min-regeneration
(${c}_{r}=1$, ${c}_{m}=0$) CRLP.

#### A. Effect of Seeding With ${R}^{+}$

For all reach distances we considered, the heuristic solution for
min-regeneration (${c}_{r}=1$, ${c}_{m}=0$) was within 2 of ${R}^{+}$, meaning that it was at most 1 off from
optimal. For a reach distance of 2000 km, we found that
${R}^{+}$ (without any other sites) turned out to be a
solution. We were interested in seeing if not seeding with
${R}^{+}$ still leads to a good solution (albeit at
slower convergence), so we ran some simulations with a generic greedy algorithm
(without ${R}^{+}$) and found the solutions to be inferior in
general. The reason may be that a greedy algorithm does *local*
optimization, which may not lead to global optimization. Starting with an empty
set of sites, there is a greater likelihood of it deviating farther from the
global optimum. When the algorithm is seeded with ${R}^{+}$, it only has to pick a few additional sites, so
its scope of making wrong decisions is minimized. This suggests that our
customized enhancement of seeding with ${R}^{+}$ leads to a better-quality solution and speeds
up convergence.

If the variables in Eq. (4) are set to ${c}_{r}=0$ and ${c}_{m}=1$, then CRLP reduces to a min-distance (or min-delay) routing. For the third scenario, min-cost routing, we set the parameters as ${c}_{r}=1000$ and ${c}_{m}=1$, which is the most representative of the network cost. In other words, the cost of one regeneration is equivalent to 1000 km of fiber distance. We have compared the number of $|RS|$ obtained by our heuristic to the lower bound discussed in Subsection III.E. We have observed [17] that the heuristic solution is close to the lower bound in min-regeneration and min-cost cases at all reach distances.

In Fig. 7(a) we compare the number of regenerator sites obtained for all three scenarios, which were also presented in [17]. We observe that the $|RS|$ is lowest for the min-distance case and highest for the min-cost case. A smaller number of regenerator sites ($|RS|$) for min-distance routing causes more regenerations along the path, thereby increasing the overall network cost. We have also computed the sum of the costs of all circuits (assuming a uniform traffic matrix, where each node pair has the same number of circuits) for each case, and observed that, as expected, this cost is lowest for the min-cost case.

In Fig. 7(b) we plot the percentage
increase in the total network cost (compared to the min-cost case) for the
min-distance and min-regeneration constraints. The plotted cost does not include
the cost of spare regenerators, which will depend on the individual network
operator’s practices. Overall, although we see the min-distance case
achieves the smallest number of regenerator sites, its total network cost
(neglecting spares) is higher (about 5% for $\text{reach}=1800\text{\hspace{0.17em}}\text{\hspace{0.17em}}\mathrm{km}$). For the min-regeneration case, the
*RS* set expands, but the network cost is only moderately
higher than for the min-cost case. For a more complete solution to a real
network, one will have to specify the traffic matrix, the spare equipment
policy, and other operating practices.

As explained in Subsection III.F, a
min-regeneration path is not necessarily a min-distance (shortest) path and
*vice versa*. We have evaluated the excess
wavelength-kilometer penalty incurred by min-regeneration paths compared to the
min-distance paths. Note that these excess wavelength-kilometer penalties
translate to longer latencies for circuits using these paths. In Fig. 8(a) we observed that for approximately 85%
of the node pairs, the min-regeneration path coincides with the min-distance
path, so there is no wavelength-kilometer penalty. We also verify from
Fig. 8(a) that min-cost paths
(because they are trying to minimize a combination of the number of regenerators
and distance) consistently show lower excess wavelength-kilometer penalty than
min-regeneration CRLP [17]. For the rest
of the discussion we consider min-cost CRLP.

Figure 8(b) shows the highest excess wavelength-kilometer penalty for each percentile of node pairs for min-cost CRLP. That is, we computed the wavelength-kilometer penalty for each node pair and then computed the highest penalty for each percentile of node pairs. For example, the 99% value at a reach distance of 2000 km is approximately 100 wavelength-kilometers, meaning that when we pick the circuit routes so as to minimize their overall cost, 99% of the routes incur a distance penalty of less than 100 km (which translates into a latency penalty of less than 0.5 ms).

In describing the algorithm (Section III), we suggested two reasonable ranking rules [Eqs. (1) and (3)] and a PP step as an added optimization. We have evaluated the performance of our heuristic with different ranking rules, both with and without PP for all three scenarios: min-regeneration, min-distance, and min-cost. For min-distance CRLP, the PP step reduces the $|RS|$ especially for the lower reach distances (1500, 1800, and 2000 km). However, for the min-regeneration CRLP, the PP does not reduce the $|RS|$ for any reach distance and network topology. In the min-cost CRLP, PP improves the solution by one regenerator site for reach distances of 2400 and 2500 km. As explained earlier, we have two different rank rules, and neither was consistently better than the other. Therefore we have reported the minimum of the two solutions. (We can think of the final heuristic as invoking two heuristics in serial order and then picking the better one; this doubles the running time.) The $|RS|$ obtained using the two rank rules and the effects of PP are summarized in Table I.

#### B. Trade-Off Between Circuit Cost and $|RS|$

As explained in Section IV, allowing
the heuristic to pick paths that are more costly than min-cost paths can
potentially reduce $|RS|$. Figure 9(a) shows the effect of such latitude for min-cost CRLP, where we
define *latitude* as a parameter indicating the percentage by
which a node pair’s route is allowed to exceed the minimum cost for that
pair.

- 1)
*Fixed latitude:*We first consider the same latitude for all network node pairs. The leftmost values in Fig. 9(a) indicate $|RS|$ for strict min-cost, i.e., zero latitude for all node pairs. From Fig. 9(a) we observe that allowing a certain percentage of increase in the cost will reduce the $|RS|$ for most of the reach distances. For instance, by allowing 5% (0.05) latitude, we observe a reduction from 28 to 25 in the number of sites for a reach distance of 2000 km. - 2)
*Variable latitude:*We next consider applying a different latitude to different node pairs. The basic concept is that, if we have a demand matrix, then the latitude for a node pair should be inversely proportional to the amount of demand. Our techniques apply to any general demand matrix, but for the results in this section, we assume that the amount of demand between a node pair is proportional to the product of their populations. (This is the well-studied gravity model of demand).

We have studied several different latitude rules. For the first three, we classify node pairs to be high (${h}_{i}$, both nodes have a population exceeding 5 million), medium (${m}_{i}$, both nodes have a population exceeding 1 million and at least one node has a population less than 5 million), or low (${l}_{i}$, all other node pairs). We define latitude scenarios as ${L}_{1}$, ${L}_{2}$, and ${L}_{3}$ as ${L}_{1}=[{h}_{1}=5\%,{m}_{1}=10\%,{l}_{1}=15\%]$, ${L}_{2}=[0\%,5\%,10\%]$, and ${L}_{3}=[0\%,10\%,25\%]$, respectively. If no latitude was allowed to any $(np)$, then it is defined as ${L}_{0}$, which is the baseline CRLP.

The next two latitude rules ${L}_{4}$ and ${L}_{5}$ [given in Eqs. (6) and (7)] can be thought of as continuous versions of the first three latitude definitions. As is standard in gravity-based models, we define the probability of a demand between a node pair to be proportional to the product of the population of the cities at which they are located. If $\mathrm{Pop}(i)$ and $\mathrm{Pop}(j)$ are populations of a city at nodes $i$ and $j$, then we define the probability of the node pair $(i,j)$ as

In the definition of ${L}_{5}(i,j)$, we also cap the latitude at 20%, but it allows smoother changes. The definition also guarantees that the expected increase is at most 5%, as each node pair contributes at most $\mathrm{Pr}(i,j)\times {L}_{5}(i,j)\le ((5\times \mathrm{Pr}(i,j))/(\mathrm{Pr}(i,j)\times np))=(5/np)$ to this expectation.

From Table II we see that the latitude rule ${L}_{3}$ has the lowest $|RS|$, compared to ${L}_{1}$ and ${L}_{2}$. This is not surprising because ${L}_{3}$ allows latitude of up to 25%. However, this reduction in $|RS|$ comes with a cost penalty. In Fig. 9(b) we compare the percentage increase from the min-cost CRLP (${L}_{0}$) for ${L}_{1}$, ${L}_{2}$, and ${L}_{3}$, and ${L}_{3}$ has the highest cost penalty.

In Fig. 10(a) we evaluate the excess wavelength-kilometer penalty for various percentages of node pairs based on latitude rule ${L}_{3}$. Here we observe that among 99% of the node pairs, the highest deviation is approximately 300 km ($\approx 1.5\text{\hspace{0.17em}}\text{\hspace{0.17em}}\mathrm{ms}$) at a reach distance of 2000 km, which is higher than ${L}_{0}$ in Fig. 8(b).

Similar to the percentile calculations, we compute the highest wavelength-kilometer for various probabilities (${p}_{r}$) 1.00, 0.99, and 0.98 for both ${L}_{0}$ and ${L}_{3}$ as shown in Figs. 10(b) and 10(c). From Figs. 10(b) and Fig. 10(c), we observe that 99% of demands will have excess wavelength penalty of less than 50 km in the case of ${L}_{0}$ and 300 km for ${L}_{3}$ at an optical reach of 2000 km.

Each latitude rule presents a different point in the trade-off between minimizing the cost of circuits and $|RS|$. (Minimizing $|RS|$ can provide savings in shared infrastructure, operations, and predeployment of idle regenerators.) For instance, latitude rule ${L}_{3}$ reduces the $|RS|$, but there is a comparatively higher wavelength-kilometer penalty. From Table II we see that ${L}_{4}$ and ${L}_{5}$ have a number of regenerator sites slightly higher than ${L}_{3}$, but lower than ${L}_{0}$. In Fig. 11(a) we compare the percentage of node pairs that have excess wavelength-kilometer penalty for latitudes ${L}_{0}$, ${L}_{3}$, ${L}_{4}$, and ${L}_{5}$. We observe in Fig. 11(a) that the percentage node pairs for ${L}_{5}$ are near those of ${L}_{0}$.

We next consider *expected deviation*
$\overline{D}$ defined as $\overline{D}=\sum _{\forall (i,j),i\ne j}\mathrm{Pr}(i,j)\delta (i,j)$, where $\delta (i,j)$ is the wavelength-kilometer penalty for node
pair $(i,j)$. In Fig. 11(b) we plot the expected deviation for latitudes
${L}_{0}$, ${L}_{3}$, ${L}_{4}$, and ${L}_{5}$. We conclude that $\overline{D}$ for ${L}_{5}$ is almost the same as for
${L}_{0}$ for most of the reach distances. Thus
${L}_{5}$ seems to provide a very attractive trade-off
given the reduction in the $|RS|$ and minimal excess wavelength-kilometer
penalty.

We define the *network cost* for a given latitude
${L}_{k}$, where $k\in \{1,2,3,4,5\}$ as ${\text{Cost}}_{k}=\sum _{\begin{array}{l}\forall (i,j),i\ne j\end{array}}\mathrm{Pr}(i,j)\times {\text{Cost}}_{p}(i,j)$, where ${\text{Cost}}_{p}(i,j)$ is the cost of the circuit for a given node
pair $(i,j)$ calculated using Eq. (4), with ${c}_{r}=1000$ and ${c}_{m}=1$. We define the expected cost deviation of
various latitude rules from the min-cost CRLP (i.e., latitude is set to zeros
and the paths are strictly min-cost) as

From Fig. 12, we observe that ${L}_{2}$, ${L}_{4}$, and ${L}_{5}$ have low percentages of cost deviation compared to ${L}_{0}$.

Finally, we evaluate the ${\mathrm{\Delta}}_{RS}$ as defined in Section V for supporting backup paths on the CONUS topology shown in Fig. 6. In Table III, ${p}_{d}$ is the percentage of node pairs with a valid disjoint path using $R{S}_{\mathrm{CRLP}}$, and ${\mathrm{\Delta}}_{RS}$ is the number of additional regenerators required to provide backup paths to all node pairs. In the min-distance CRLP (${c}_{r}=0$ and ${c}_{m}=1$), we find that using $R{S}_{\mathrm{CRLP}}$, all node pairs have a valid disjoint path, i.e., ${p}_{d}=100\%$, and hence ${\mathrm{\Delta}}_{RS}=0$ for most of the reach distances. For min-regeneration (${c}_{r}=1$ and ${c}_{m}=0$) and min-cost (${c}_{r}=1000$ and ${c}_{m}=0$) CRLP, ${\mathrm{\Delta}}_{RS}\ne 0$.

## VII. Conclusion

To plan predeployment of regenerators effectively in practical networks, we have introduced a constrained routing regenerator location problem and presented a heuristic approach to address it. Unlike previous research work on regenerator placement, we pursue a holistic approach of minimizing overall network cost by considering a combination of the number of regenerators used and the wavelength-kilometer of individual circuits, as well as the probability of demand between each node pair and the number of sites. We start with a basic heuristic and then present various enhancements that refine the trade-off between the number of sites and the cost of individual circuits. The heuristic also constructs a lower bound, thus letting us evaluate how closely we approach the optimal. Extensive simulations on large topologies show that the heuristic achieves near-optimal results. Our heuristic algorithm can be easily tuned for practical ROADM networks where instead of a fixed reach distance, a reach table is used to specify all reachable paths in the network (such tables are generated by a vendor’s planning tools using detailed network information). Finally our experiments indicate that a small additional number of regenerator sites allow survivable connections between most node pairs. We further plan to extend this work to evaluate 1) the usage of regenerators at each selected site for dynamic traffic and 2) complex requirements of disjointness on connection between multiple node pairs.

## Appendix A

In this appendix, we present the ILP formulations for the proposed CRLP. Given the original graph $G=(N,E)$ with a set of $N$ vertices and a set of $E$ edges, we construct an augmented graph ${G}_{A}=(N,{E}_{A})$, such that we add an edge between two nodes if they are within the reach distance, where ${E}_{A}$ represents the set of augmented edges.

## A. Notations

- • $\text{role}(u)=1$ if regenerators are placed in $u$, 0 otherwise.
- • $\mathcal{K}$: the set of connection requests in the traffic matrix.
- • $\mathrm{src}(k)$: the source node of the $k$th request.
- • $tgt(k)$: the destination node of the $k$th request.
- • ${f}_{u,v}^{k}$: if the link $(u,v)$ is used for the $k$th request, the value is 1. Otherwise, the value is 0.
- • $\text{out}(u)$: the outgoing adjacent node set of node $u$.
- • $\text{in}(u)$: the incoming adjacent node set of node $u$.
- • $|N|$: the number of nodes in the network graph, where $N$ is the set of nodes.
- • ${H}^{k}$: given hops on request $k$.

## B. CRLP Formulation

**Objective**

**Constraints**

In the CRLP problem, we can select a path from all the routes that use the minimum number of regenerations. The paths that use the minimum number of regenerations are the shortest paths (in terms of path hops) in our newly generated graph ${G}_{A}$. In Eq. (A5), ${H}^{k}$ is the number of hops of the shortest path for connection $k$ in ${G}_{A}$. Equation (A2) makes sure that the number of links used on the connection equals the number of hops of the shortest path. By doing this, we guarantee that a path with minimum regeneration will be selected.

Constraints (A3)–(A5) are the flow conservation constraints for all connection requests. In constraint (A6), for a node $u$, which is used as the intermediate node for some connection, it will be a regeneration node.

## Acknowledgments

The authors acknowledge many useful suggestions and comments from D. Xu and G. Zussman and support from the CIAN NSF ERC (subaward Y503160). This paper was presented in parts at DRCN 2013 [18] and OFC/NFOEC 2012 [17].

## Notes

^{1} | ILP formulation is detailed in Appendix A. |

## References

**1. **A. Gerber and R. Doverspike, “Traffic types and growth in backbone
networks,” in Nat. Fiber Optic Engineers
Conf., Los Angeles, CA,
Mar. 2011,
pp. 1–3.

**2. **J. Simmons, E. L. Goldstein, and A. A. M. Saleh, “On the value of wavelength-add/drop in
WDM rings with uniform traffic,” in Nat.
Fiber Optic Engineers Conf., San Jose, CA,
Feb. 1998,
pp. 361–362.

**3. **W. Van Parys, P. Arijs, O. Antonis, and P. Demeester, “Quantifying the benefits of selective
wavelength regeneration in ultra long-haul WDM
networks,” in Optical Fiber Communication Conf.
and Exhibit, Anaheim, CA,
Mar. 2001, vol. 2,
paper TuT4.

**4. **M. D. Feuer, D. C. Kilper, and S. L. Woodward, “ROADMs and their system
applications,” in *Optical Fiber
Telecommunications*. Waltham, MA:
Academic, 2008,
pp. 293–343.

**5. **A. A. Mahimkar, A. Chiu, R. Doverspike, M. Feuer, P. Magill, E. Mavrogiorgis, J. Pastor, V. Sethi, D. Xu, S. Woodward, and J. Yates, “Outage detection and dynamic
re-provisioning in GRIPhoN: A globally reconfigurable intelligent photonic
network,” in Nat. Fiber Optic Engineers
Conf., Los Angeles, CA,
Mar. 2012, paper NM2F.5.

**6. **S. Woodward, M. Feuer, I. Kim, P. Palacharla, X. Wang, and D. Bihon, “Service velocity: Rapid provisioning
strategies in optical ROADM networks,” J.
Opt. Commun. Netw., vol. **4**,
no. 2,
pp. 92–98,
Feb. 2012. [CrossRef]

**7. **X. Zhang, M. Birk, A. Chiu, R. Doverspike, M. Feuer, P. Magill, E. Mavrogiorgis, J. Pastor, S. Woodward, and J. Yates, “Bridge-and-roll demonstration in GRIPhoN
(Globally Reconfigurable Intelligent Photonic
Network),” in Nat. Fiber Optic Engineers
Conf., San Diego, CA,
Mar. 2010,
pp. 1–3.

**8. **A. Chiu, G. Choudhury, G. Clapp, R. Doverspike, M. Feuer, J. Gannett, J. Jackel, G. Kim, J. Klincewicz, T. Kwon, G. Li, P. Magill, J. Simmons, R. Skoog, J. Strand, A. Lehmen, B. Wilson, S. Woodward, and D. Xu, “Architectures and protocols for capacity
efficient, highly dynamic and highly resilient core networks
[Invited],” J. Opt. Commun. Netw.,
vol. **4**, no. 1,
pp. 1–14,
Jan. 2012. [CrossRef]

**9. **M. Feuer, S. Woodward, I. Kim, P. Palacharla, X. Wang, D. Bihon, B. Bathula, W. Zhang, R. Sinha, G. Li, and A. Chiu, “Simulations of a service velocity
network employing regenerator site concentration,” in
Nat. Fiber Optic Engineers Conf., Los Angeles,
CA, Mar. 2012, paper NTu2J.5.

**10. **M. Flammini, A. Marchetti-Spaccamela, G. Monaco, L. Moscardelli, and S. Zaks, “On the complexity of the regenerator
placement problem in optical networks,” in
*Proc. 2nd Annu. Symp. Parallelism Algorithms and Architectures
(SPAA)*, 2009,
pp. 154–162.

**11. **S. Chen, I. Ljubic, and S. Raghavan, “The generalized regenerator location
problem,” in *Proc. Int. Network Optimization
Conf.*, 2009,
pp. 1–32.

**12. **S. Chen, I. Ljubic, and S. Raghavan, “The regenerator placement
problem,” Networks,
vol. **55**, no. 3,
pp. 205–220,
2010.

**13. **A. Duarte, R. Martí, and M. G. C. Resende, “Randomized heuristics for the regenerator
location problem,” Optimization Online, 2010.
[Online]. Available: http://www.optimization-online.org/DB_HTML/2010/08/2706.html.

**14. **M. Flammini, A. Marchetti-Spaccamela, G. Monaco, L. Moscardelli, and S. Zaks, “On the complexity of the regenerator
placement problem in optical networks,”
IEEE/ACM Trans. Netw., vol. **19**,
no. 2,
pp. 498–511,
Apr. 2011. [CrossRef]

**15. **G. Shen, W. Grover, T. Cheng, and S. Bose, “Sparse placement of electronic switching
nodes for low blocking in translucent optical
networks,” J. Opt. Netw.,
vol. **1**, no. 12,
pp. 424–441,
Dec. 2002.

**16. **X. Yang and B. Ramamurthy, “Sparse regeneration in translucent
wavelength-routed optical networks: Architecture, network design and
wavelength routing,” Photon. Netw.
Commun., vol. **10**,
pp. 39–53,
July 2005.

**17. **B. G. Bathula, R. Sinha, A. Chiu, M. Feuer, G. Li, S. Woodward, W. Zhang, K. Bergman, I. Kim, and P. Palacharla, “On concentrating regenerator sites in
ROADM networks,” in Nat. Fiber Optic
Engineers Conf., Los Angeles, CA,
Mar. 2012, paper NW3F.6.

**18. **B. G. Bathula, R. K. Sinha, A. L. Chiu, M. D. Feuer, G. Li, S. L. Woodward, W. Zhang, R. Doverspike, P. Magill, and K. Bergman, “Cost optimization using regenerator site
concentration and routing in ROADM networks
[Invited],” in 9th Int. Conf. Design of Reliable
Communication Networks (DRCN), Budapest,
Hungary, Mar. 2013,
pp. 139–147.

**19. **M. Garey and D. S. Johnson, *Computers and Intractability: A Guide to the Theory of
NP-Completeness*. W. H. Freeman and
Company, 1979.

**20. **S. Rai, C. F. Su, and B. Mukherjee, “On provisioning in all-optical networks:
An impairment-aware approach,” IEEE/ACM
Trans. Netw., vol. **17**,
no. 6,
pp. 1989–2001,
Dec. 2009. [CrossRef]

**21. **C. Gao, H. Cankaya, A. Patel, J. Jue, X. Wang, Q. Zhang, P. Palacharla, and M. Sekiya, “Survivable impairment-aware traffic
grooming and regenerator placement with connection-level
protection,” J. Opt. Commun. Netw.,
vol. **4**, no. 3,
pp. 259–270,
Mar. 2012. [CrossRef]

**22. **X. Yang, L. Shen, and B. Ramamurthy, “Survivable lightpath provisioning in WDM
mesh networks under shared path protection and signal quality
constraints,” J. Lightwave Technol.,
vol. **23**, no. 4,
pp. 1556–1567,
Apr. 2005. [CrossRef]

**23. **A. Chiu, G. Choudhury, G. Clapp, R. Doverspike, J. Gannett, J. Klincewicz, G. Li, R. Skoog, J. Strand, A. Von Lehmen, and D. Xu, “Network design and architectures for
highly dynamic next-generation IP-over-optical long distance
networks,” J. Lightwave Technol.,
vol. **27**, no. 12,
pp. 1878–1890,
June 2009. [CrossRef]

## Sun Z.

11/27/2013 3:10 AM

very good,the internet now are a big business opportunity!!