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].

 

Fig. 1. Colorless and nondirectional ROADM.

Download Full Size | PDF

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.

 

Fig. 2. Example network consisting of 10 nodes and 11 links. Solid lines represent original edges, and dotted lines represent augmented edges for reach equal to 2.5 times the link length. Filled circles represent regenerator locations obtained for min-regeneration CRLP.

Download Full Size | PDF

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.

 

Fig. 3. VCP to DCRLP transformation: (a) $G$ and (b) $G\prime$.

Download Full Size | PDF

If we assume the optical reach to be one hop, we have the following observations on $I_2$:

Based on the observation above, the reduction follows from

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:

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.

Algorithm 1. Barebone CRLP Heuristic

View Table | View all tables in this article

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^{+}\cup 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{of}RS\times (\#\text{of deletions in}\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.

Algorithm 2. CRLP Heuristic: Seeding $R^{+}$, $R^{-}$, and PP

View Table | View all tables in this article

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)$:

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:

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:

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}}\cup {\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}–\mathrm{C}–\mathrm{D}–\mathrm{E}$, and the disjoint path, ${\mathcal{R}}_{BE}\prime =\mathrm{B}–\mathrm{A}–\mathrm{I}–\mathrm{J}–\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}–\mathrm{I}–\mathrm{J}–\mathrm{E}–\mathrm{D}$ and ${\mathcal{R}}_{AD}\prime =\mathrm{A}–\mathrm{B}–\mathrm{C}–\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].

 

Fig. 4. US mesh topology used for heuristic evaluation with ILP. Link weights are the distance in km. Node numbers are used in the $y$ axis of Fig. 5.

Download Full Size | PDF

 

Fig. 5. Comparison for number of regenerator sites on USMESH for min-regeneration CRLP.

Download Full Size | PDF

 

Fig. 6. CONUS network topology. Circles indicate regenerator sites appearing in the solution set for reach distance of 1800 km; $c_r=1$ and $c_m=0$ (min-regeneration).

Download Full Size | PDF

We have compared the CRLP heuristic with an optimal ILP¹ 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.

 

Fig. 7. (a) Number of regeneration sites for different CRLP. (b) Percentage increase in total cost with one circuit on each route.

Download Full Size | PDF

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\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.

 

Fig. 8. (a) Percentage of node-pair paths with excess length, compared to the shortest-distance path. (b) Highest excess wavelength penalty among certain % node pairs for min-cost CRLP.

Download Full Size | PDF

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.

TABLE I. RS With Different Rank Rules and PP

View Table | View all tables in this article

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.

 

Fig. 9. (a) Number of regeneration sites for min-cost CRLP ($c_r=1000$, $c_m=1$) versus different latitudes for a given reach distance (km). (b) Percentage increase from $L_0$ for allowing small latitude from the min-cost paths.

Download Full Size | PDF

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.

TABLE II. $|RS|$ for Various Latitude Scenarios Considered in the Proposed Heuristic

View Table | View all tables in this article

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\mathrm{ms}$) at a reach distance of 2000 km, which is higher than $L_0$ in Fig. 8(b).

 

Fig. 10. (a) Highest excess wavelength penalty among certain % node pairs for min-cost CRLP with latitude $L_3$. (b) Highest deviation using probability of a node pair for min-cost CRLP with zero latitude. (c) Highest deviation using probability of a node pair for min-cost CRLP with latitude $L_3$.

Download Full Size | PDF

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$.

 

Fig. 11. (a) Percentage of node pairs with wavelength-kilometer penalty for zero latitude, $L_3$, $L_4$, and $L_5$. (b) Expected deviation ($\overline{D}$) for zero latitude, $L_3$, $L_4$, and $L_5$.

Download Full Size | PDF

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$.

 

Fig. 12. Expected cost deviation (${\overline{D}}_c$) for $L_k$, where $k\in \{1,2,3,4,5\}$.

Download Full Size | PDF

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$.

TABLE III. Evaluation of ${\mathrm{\Delta }}_{RS}$ for Diverse Routes on CONUS Topology

View Table | View all tables in this article

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.