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 [24]. 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 | PPT Slide | 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 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 Puv between nodes u and v is called a constrained route if it uses 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 | PPT Slide | 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|N|, the VCP asks if there is a subset N0N of cardinality at most K such that N0 contains at least one of the two endpoints of each edge in E.

Given an instance I1 of VCP (N,E,K), we construct the corresponding instance I2 of DCRLP (N,E,K) by the following transformation. (An example is shown in Fig. 3.) 1) For any niN, create a network node niN; 2) for any eiE, create one node eiN, and add the following links in E: (ei,nk) and (ei,nl), where nk and nl are two end nodes of ei; 3) add two extra nodes s and t to N, and add the following links to E: (s,ei) for any node ei and (t,nj) for any node nj; 4) add two nodes S and T in N, and links (s,S) and (t,T) to E; 5) for any node eiE, we create another node Ei in N, and add links (ei,Ei) to E. Now we have graph G=(N,E). Clearly, I2 can be constructed from I1 in polynomial time.

 

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

Download Full Size | PPT Slide | PDF

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

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

Based on the observation above, the reduction follows from

  • • If I2 has a feasible solution, say set R of regenerator sites, then node set R{s,t,ei} is a feasible solution for I1.
  • • Conversely, suppose the instance I1 of VCP has a feasible solution of node set R; then node set R{s,t,ei} is a feasible solution of I2.
  • • 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 PNP, 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 PNP. Then it is easy to see that the optimal solution can answer the feasibility of DCRLP. If the cardinality of the optimal solution is 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 PNP.

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 GA; then we claim a 11 correspondence between min-regeneration paths in the network and min-hop paths in GA.

Lemma 1. If P is a min-hop path in GA, 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 GA with direct links between adjacent pairs of regenerator sites.

Proof. The proof follows from the following two observations showing a 11 correspondence between paths in GA and regenerator placements.

Observation 1: Consider a path in GA. 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 GA. So we can map the path in the network to a path in GA 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 k1 or fewer regenerators; then, by Observation 2, we get a path with k1 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 GA with k internal nodes. Suppose P is not a min-hop path; then there is a path P of fewer than k intermediate nodes. By Observation 1, P 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 GA 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 GA (line 4)] such that Pij 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 Dij 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 GA (line 5). The matrix D lets us check whether a node v belongs to the min-hop path from i to j:
    Div+Dvj=Dij,
    where Div+Dvj 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 GA) 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.

Tables Icon

Algorithm 1. Barebone CRLP Heuristic

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 Pij=1. Finally, we initialize the set of candidate regenerator sites C=N\(R+R). The set R+ can be computed in O(|E|×|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-z path through v is longer than the shortest a-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

rank1(v)=|{(i,j)|(Pij=0)(Div+Dvj=Dij)}|.

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:

ramp(v)=|{(i,j)|(Pij=0)(Piv=1)(Pvj=1)(Div+Dvj=Dij)}|.

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

rank2(v)=rank1(v)+(|N|1)×ramp(v).

The overall effect of using Eq. (3) is that the ramp(v) has the dominant effect in picking the “best” candidate, but if it cannot distinguish among multiple candidates, then the rank1(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 v1, but then a set of nodes selected later covers all source-destination pairs that v1 was originally covering, rendering v1 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|×|N|) time. In the worst case, each deletion may require checking all nodes in the output, so altogether it can take time O(#ofRS×(#of deletions inPP)×|E|×|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

O((|RS|×(#of deletions inPP)da+da)×|N|3),
where da is the average degree in G. The space complexity is the size of data structures, O(|N|2).

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.

Tables Icon

Algorithm 2. CRLP Heuristic: Seeding R+, R, and PP

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

LB=log(dp),
where dp 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 R1=av1v2v3z and R2=av4v5z. If the reach distance is 2000 km, the length of each link in R1 is 1050 km, and the length of each link in R2 is 1950 km, then R1 is the shortest (=min-distance) path. But note that R1 requires three regenerators, whereas R2 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

cr×number of regenerations inR+cm×length ofR,
where cr (cm) is the unit regeneration (wavelength-kilometer) cost. The two extreme cases are the following: setting cr=1 and cm=0 reduces to the CRLP problem, whereas setting cr=0 and cm=1 becomes the ERLP problem with min-distance paths.

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: Pij is 1 if we have a valid min-cost path between nodes i and j using the given regenerator placement.
  • 3) The condition Div+Dvj=Dij 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+Lij 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+Lij 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+Lij. A similar change applies to the definition of R.
  • 2) Change the definition of the path matrix; P: Pij 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+Lij 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+Lij 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 (ΔRS) required for the node pairs to have a valid reachable secondary path (if a disjoint path exists). We define RSD=RSCRLPΔRS, where RSCRLP 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 (R). We designate the disjoint path (R) 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 RBE=BCDE, and the disjoint path, RBE=BAIJE, 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 RAD=AIJED and RAD=ABCD. We define the diverse percentage (pd) as the percentage of node pairs with a valid disjoint path. For the network in Fig. 2, using RSCRLP={A,D,J,F}, there are 10×9/2=45 node pairs (np), and only 26 node pairs have valid R, so pd58%. If we require pd=100% for the Fig. 2 network, then we must add sites in addition to the set RSCRLP.

An iterative process is used to choose these extra sites from candidate set CD, defined as the set of intermediate nodes present in all the invalid disjoint paths (ID), but RSCRLP. In each iteration, we select a node cdCD that belongs to the largest number of invalid disjoint paths F(cd). For the network in Fig. 2, we have F(B)=14. Adding node B as a regenerator site increases pd to 84.4%. Finally, including node H (or node G) as well enables all node pairs to have a valid disjoint path, so that (pd=100%). Thus we select Δ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 | PPT Slide | PDF

 

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

Download Full Size | PPT Slide | PDF

 

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

Download Full Size | PPT Slide | PDF

We have compared the CRLP heuristic with an optimal ILP1 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 (cr=1, cm=0) CRLP.

A. Effect of Seeding With R+

For all reach distances we considered, the heuristic solution for min-regeneration (cr=1, cm=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 cr=0 and cm=1, then CRLP reduces to a min-distance (or min-delay) routing. For the third scenario, min-cost routing, we set the parameters as cr=1000 and cm=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 | PPT Slide | 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 reach=1800km). 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 | PPT Slide | 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.

Tables Icon

TABLE I. RS With Different Rank Rules and PP

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

 

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

Download Full Size | PPT Slide | PDF

We have studied several different latitude rules. For the first three, we classify node pairs to be high (hi, both nodes have a population exceeding 5 million), medium (mi, both nodes have a population exceeding 1 million and at least one node has a population less than 5 million), or low (li, all other node pairs). We define latitude scenarios as L1, L2, and L3 as L1=[h1=5%,m1=10%,l1=15%], L2=[0%,5%,10%], and L3=[0%,10%,25%], respectively. If no latitude was allowed to any (np), then it is defined as L0, which is the baseline CRLP.

The next two latitude rules L4 and L5 [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 Pop(i) and Pop(j) are populations of a city at nodes i and j, then we define the probability of the node pair (i,j) as

Pr(i,j)=Pop(i)Pop(j)(i,j),ijPop(i)Pop(j).
If Pop(i) and Pop(j) both are 5 million, then we define the rule L4 such that it allows a latitude of 3%. As the product of the populations decreases, we allow larger latitudes, but we cap it at 20%.
L4(i,j)=min(20,25Pop(i)×Pop(j)×3).

In the definition of L5(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 Pr(i,j)×L5(i,j)((5×Pr(i,j))/(Pr(i,j)×np))=(5/np) to this expectation.

L5(i,j)=min(20,5Pr(i,j)×np).

From Table II we see that the latitude rule L3 has the lowest |RS|, compared to L1 and L2. This is not surprising because L3 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 (L0) for L1, L2, and L3, and L3 has the highest cost penalty.

Tables Icon

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

In Fig. 10(a) we evaluate the excess wavelength-kilometer penalty for various percentages of node pairs based on latitude rule L3. Here we observe that among 99% of the node pairs, the highest deviation is approximately 300 km (1.5ms) at a reach distance of 2000 km, which is higher than L0 in Fig. 8(b).

 

Fig. 10. (a) Highest excess wavelength penalty among certain % node pairs for min-cost CRLP with latitude L3. (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 L3.

Download Full Size | PPT Slide | PDF

Similar to the percentile calculations, we compute the highest wavelength-kilometer for various probabilities (pr) 1.00, 0.99, and 0.98 for both L0 and L3 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 L0 and 300 km for L3 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 L3 reduces the |RS|, but there is a comparatively higher wavelength-kilometer penalty. From Table II we see that L4 and L5 have a number of regenerator sites slightly higher than L3, but lower than L0. In Fig. 11(a) we compare the percentage of node pairs that have excess wavelength-kilometer penalty for latitudes L0, L3, L4, and L5. We observe in Fig. 11(a) that the percentage node pairs for L5 are near those of L0.

 

Fig. 11. (a) Percentage of node pairs with wavelength-kilometer penalty for zero latitude, L3, L4, and L5. (b) Expected deviation (D¯) for zero latitude, L3, L4, and L5.

Download Full Size | PPT Slide | PDF

We next consider expected deviation D¯ defined as D¯=(i,j),ijPr(i,j)δ(i,j), where δ(i,j) is the wavelength-kilometer penalty for node pair (i,j). In Fig. 11(b) we plot the expected deviation for latitudes L0, L3, L4, and L5. We conclude that D¯ for L5 is almost the same as for L0 for most of the reach distances. Thus L5 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 Lk, where k{1,2,3,4,5} as Costk=(i,j),ijPr(i,j)×Costp(i,j), where Costp(i,j) is the cost of the circuit for a given node pair (i,j) calculated using Eq. (4), with cr=1000 and cm=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

D¯c=CostkCost0Cost0×100,k{1,2,3,4,5}.

From Fig. 12, we observe that L2, L4, and L5 have low percentages of cost deviation compared to L0.

 

Fig. 12. Expected cost deviation (D¯c) for Lk, where k{1,2,3,4,5}.

Download Full Size | PPT Slide | PDF

Finally, we evaluate the ΔRS as defined in Section V for supporting backup paths on the CONUS topology shown in Fig. 6. In Table III, pd is the percentage of node pairs with a valid disjoint path using RSCRLP, and ΔRS is the number of additional regenerators required to provide backup paths to all node pairs. In the min-distance CRLP (cr=0 and cm=1), we find that using RSCRLP, all node pairs have a valid disjoint path, i.e., pd=100%, and hence ΔRS=0 for most of the reach distances. For min-regeneration (cr=1 and cm=0) and min-cost (cr=1000 and cm=0) CRLP, ΔRS0.

Tables Icon

TABLE III. Evaluation of ΔRS for Diverse Routes on CONUS Topology

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 GA=(N,EA), such that we add an edge between two nodes if they are within the reach distance, where EA represents the set of augmented edges.

A. Notations

  • role(u)=1 if regenerators are placed in u, 0 otherwise.
  • K: the set of connection requests in the traffic matrix.
  • src(k): the source node of the kth request.
  • tgt(k): the destination node of the kth request.
  • fu,vk: if the link (u,v) is used for the kth request, the value is 1. Otherwise, the value is 0.
  • out(u): the outgoing adjacent node set of node u.
  • 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.
  • Hk: given hops on request k.

B. CRLP Formulation

Objective

minuVrole(u).

Constraints

(u,v)Efu,vk=Hk,kK,
vout(s)fs,vkvin(s)fv,sk=1;kK,s=src(k),
vin(t)fv,tkvout(t)ft,vk=1,kK,t=tgt(k),
vout(u)fu,vk=vin(u)fv,uk,kK,uV(src(k)ortgt(k)),
role(u)vout(u)fu,vkN,kK,uV(src(k)ortgt(k)),fu,vk,role(u){0,1}.

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 GA. In Eq. (A5), Hk is the number of hops of the shortest path for connection k in GA. 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

1ILP 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]  

References

  • View by:
  • |
  • |
  • |

  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]

2012 (3)

2011 (1)

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]

2010 (1)

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

2009 (2)

2005 (2)

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.

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]

2002 (1)

Antonis, O.

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.

Arijs, P.

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.

Bathula, B.

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.

Bathula, B. G.

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.

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.

Bergman, K.

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.

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.

Bihon, D.

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]

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.

Birk, M.

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.

Bose, S.

Cankaya, H.

Chen, S.

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

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

Cheng, T.

Chiu, A.

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]

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]

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.

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.

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.

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.

Chiu, A. L.

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.

Choudhury, G.

Clapp, G.

Demeester, P.

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.

Doverspike, R.

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]

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]

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.

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.

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.

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.

Feuer, M.

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]

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]

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.

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.

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.

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.

Feuer, M. D.

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.

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.

Flammini, M.

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]

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.

Gannett, J.

Gao, C.

Garey, M.

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

Gerber, A.

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.

Goldstein, E. L.

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.

Grover, W.

Jackel, J.

Johnson, D. S.

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

Jue, J.

Kilper, D. C.

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.

Kim, G.

Kim, I.

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]

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.

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.

Klincewicz, J.

Kwon, T.

Lehmen, A.

Li, G.

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]

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]

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.

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.

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.

Ljubic, I.

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

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

Magill, P.

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]

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.

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.

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.

Mahimkar, A. A.

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.

Marchetti-Spaccamela, A.

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]

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.

Mavrogiorgis, E.

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.

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.

Monaco, G.

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]

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.

Moscardelli, L.

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]

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.

Mukherjee, B.

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]

Palacharla, P.

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]

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]

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.

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.

Pastor, J.

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.

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.

Patel, A.

Raghavan, S.

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

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

Rai, S.

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]

Ramamurthy, B.

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.

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]

Saleh, A. A. M.

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.

Sekiya, M.

Sethi, V.

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.

Shen, G.

Shen, L.

Simmons, J.

Sinha, R.

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.

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.

Sinha, R. K.

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.

Skoog, R.

Strand, J.

Su, C. F.

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]

Van Parys, W.

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.

Von Lehmen, A.

Wang, X.

Wilson, B.

Woodward, S.

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]

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]

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.

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.

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.

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.

Woodward, S. L.

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.

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.

Xu, D.

Yang, X.

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]

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.

Yates, J.

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.

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.

Zaks, S.

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]

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.

Zhang, Q.

Zhang, W.

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.

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.

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.

Zhang, X.

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.

IEEE/ACM Trans. Netw. (2)

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]

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]

J. Lightwave Technol. (2)

J. Opt. Commun. Netw. (3)

J. Opt. Netw. (1)

Networks (1)

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

Photon. Netw. Commun. (1)

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.

Other (13)

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.

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.

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

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 .

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.

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.

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.

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

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.

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.

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.

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.

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.

Cited By

OSA participates in Crossref's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (12)

Fig. 1.
Fig. 1. Colorless and nondirectional ROADM.
Fig. 2.
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.
Fig. 3.
Fig. 3. VCP to DCRLP transformation: (a)  G and (b)  G .
Fig. 4.
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.
Fig. 5.
Fig. 5. Comparison for number of regenerator sites on USMESH for min-regeneration CRLP.
Fig. 6.
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).
Fig. 7.
Fig. 7. (a) Number of regeneration sites for different CRLP. (b) Percentage increase in total cost with one circuit on each route.
Fig. 8.
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.
Fig. 9.
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.
Fig. 10.
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 .
Fig. 11.
Fig. 11. (a) Percentage of node pairs with wavelength-kilometer penalty for zero latitude, L 3 , L 4 , and L 5 . (b) Expected deviation ( D ¯ ) for zero latitude, L 3 , L 4 , and L 5 .
Fig. 12.
Fig. 12. Expected cost deviation ( D ¯ c ) for L k , where k { 1 , 2 , 3 , 4 , 5 } .

Tables (5)

Tables Icon

Algorithm 1 Barebone CRLP Heuristic

Tables Icon

Algorithm 2 CRLP Heuristic: Seeding R + , R , and PP

Tables Icon

TABLE I RS With Different Rank Rules and PP

Tables Icon

TABLE II | R S | for Various Latitude Scenarios Considered in the Proposed Heuristic

Tables Icon

TABLE III Evaluation of Δ R S for Diverse Routes on CONUS Topology

Equations (17)

Equations on this page are rendered with MathJax. Learn more.

D i v + D v j = D i j ,
rank 1 ( v ) = | { ( i , j ) | ( P i j = 0 ) ( D i v + D v j = D i j ) } | .
ramp ( v ) = | { ( i , j ) | ( P i j = 0 ) ( P i v = 1 ) ( P v j = 1 ) ( D i v + D v j = D i j ) } | .
rank 2 ( v ) = rank 1 ( v ) + ( | N | 1 ) × ramp ( v ) .
O ( ( | R S | × ( # of deletions in PP ) d a + d a ) × | N | 3 ) ,
L B = log ( d p ) ,
c r × number of regenerations in R + c m × length of R ,
Pr ( i , j ) = Pop ( i ) Pop ( j ) ( i , j ) , i j Pop ( i ) Pop ( j ) .
L 4 ( i , j ) = min ( 20 , 25 Pop ( i ) × Pop ( j ) × 3 ) .
L 5 ( i , j ) = min ( 20 , 5 Pr ( i , j ) × n p ) .
D ¯ c = Cost k Cost 0 Cost 0 × 100 , k { 1 , 2 , 3 , 4 , 5 } .
min u V role ( u ) .
( u , v ) E f u , v k = H k , k K ,
v out ( s ) f s , v k v in ( s ) f v , s k = 1 ; k K , s = src ( k ) ,
v in ( t ) f v , t k v out ( t ) f t , v k = 1 , k K , t = tgt ( k ) ,
v out ( u ) f u , v k = v in ( u ) f v , u k , k K , u V ( src ( k ) or tgt ( k ) ) ,
role ( u ) v out ( u ) f u , v k N , k K , u V ( src ( k ) or tgt ( k ) ) , f u , v k , role ( u ) { 0 , 1 } .