Generalized loop-back recovery in optical mesh networks.
Current means of providing loop-back recovery, which is widely used in SONET, rely on ring topologies, or on overlaying logical ring topologies upon physical meshes. Loop-back is desirable to provide rapid preplanned recovery of link or node failures in a bandwidth-efficient distributed manner. We introduce generalized loop-back, a novel scheme for performing loop-back in optical mesh networks. We present an algorithm to perform recovery for link failure and one to perform generalized loop-back recovery for node failure. We illustrate the operation of both algorithms, prove their validity, and present a network management protocol algorithm, which enables distributed operation for link or node failure. We present three different applications of generalized loop-back. First, we present heuristic algorithms for selecting recovery graphs, which maintain short maximum and average lengths of recovery paths. Second, we present WDM-based loop-back recovery for optical networks where wavelengths are used to back up other wavelengths. We compare, for WDM-based loop-back, the operation of generalized loop-back operation with known ring-based ways of providing loop-back recovery over mesh networks. Finally, we introduce the use of generalized loop-back to provide recovery in a way that allows dynamic choice of routes over preplanned directions.
Introduction
For WDM networks to oer reliable high-bandwidth services, automatic self-healing capabilities, similar
to those provided by SONET, are required. In particular, pre-planned, ultrafast restoration of
service after failure of a link or node is required. As WDM networks mature and expand, the need has
emerged for self-healing schemes which operate over a variety of network topologies and in a manner
which is bandwidth e-cient. While SONET provides a known and robust means of providing recovery
in high-speed networks, the techniques used for SONET are not always immediately applicable
to WDM systems. Certain issues, such as wavelength assignment and wavelength changing, make
WDM self-healing dierent from SONET self-healing. Our purpose is to present a method for service
restoration in optical networks which has the following characteristics:
Speed: we want the speed of recovery to be of the order of the speed of switching and require
minimal processing overhead.
Transparency: we seek a method of recovery which can be done at the optical layer, without
regard for whatever protocol(s) may be running over the optical layer.
Flexibility: our method should not constrain primary routings and should provide a large choice
of back-up routes to satisfy such requirements as bounds on average or maximum back-up length.
In this paper, we present an approach which altogether moves away from rings. The rationale
behind our approach is that, while ring recovery makes sense over network topologies which are
composed of interconnected rings, rings are not fundamental to network recovery over mesh networks.
Indeed, even embedding rings over a given topology can have signicant implications for hardware costs
([BGSM94]). We present generalized loop-back, a new method of achieving loop-back recovery over
arbitrary two-link-redundant and two-node-redundant networks to restore service after the failure or
a link or a node, respectively. Loop-back recovery over mesh networks without the use of ring covers
was rst introduced in [FMB98, MFB99]. We represent each network by a graph, with each node
corresponding to a vertex and each two-ber link to an undirected edge. The graph corresponding
to a link (node)-redundant network is edge (vertex)-redundant. The principle behind generalized
loop-back is to create primary and secondary digraphs, so that, upon failure of a link or node, the
secondary digraph can be used to carry back-up tra-c that provides loop-back to the primary graph.
Each primary or secondary digraph may correspond to a wavelength on a ber or a full ber. The
secondary digraph is the conjugate of the primary digraph. Each direction in a link is associated with
a given primary graph. Our algorithms perform the choice of directions to establish our digraphs.
Our approach meets our three goals: speed, transparency and
exibility. Although we use preplanning
of directions, our network management protocol determines, in real time, the back-up route that
will be utilized. We do not however, require processing as in traditional dynamic recovery schemes. In
eect, our network management protocol provides dynamic real-time discovery of routings
along pre-planned directions determined by our direction selection algorithms. Since
our protocol (see Section 2.3) requires very simple processing and the optical layer remains responsible
for recovery (ensuring transparency), we have speed of recovery combined with
exibility. In
particular, depending on availability of links or wavelengths (which may be aected by congestion or
failures in the network), dierent back-up routes may be selected, but the selection will be automatic
and will not require active comparison, by the network management, of the dierent possible routes.
In Section 1.1, we give an overview of relevant work in the area of of network protection and
restoration. In Section 2.1, we discuss generalized loop-back recovery for link failure. In Section 2.2,
we present our method for loop-back recovery for node failures in arbitrary vertex-redundant networks.
A simple network protocol, presented in Section 2.3, allows for distributed operation of recovery from
link or node failure. When we consider recovery from node failures, we must contend with the fact
that a node may carry several tra-c
ows, all of which are disrupted when the node fails.
Section 3 of our paper considers a range of dierent applications for generalized loop-back:
We address the goal of
exibility in the choice of back-up routings. We present a means of
selecting directions for generalized loop-back so as to avoid excessive path lengths. Our algorithm
allows a choice among a large number of alternative directions. The choice of directions may
greatly aect the length of back-up paths. To avoid excessive loss and jitter along recovery paths,
we present heuristic algorithms that signicantly reduce the average and maximum length of
recovery paths over random choices of directions.
We may use generalized loop-back to perform wavelength-based recovery, which we term WDM-based
loop-back recovery, instead of ber-based recovery in mesh networks. We illustrate why the
method of cover of rings using double-cycle covers is not directly applicable to WDM loop-back
recovery.
Generalized loop-back can yield several choices of backup routes for a given set of directions. We
brie
y illustrate how generalized loop-back can be used to avoid the use of certain links.
Finally, in Section 4, we present conclusions and directions for further research.
1.1 Background
Methods commonly employed for link protection in high-speed networks can be classied as either
dynamic or pre-planned, though some hybrids schemes also exist ([SOOH93]). The two types
oer a tradeo between adaptive use of back-up (or \spare") capacity and speed of restoration
restoration typically involves a search for a free path using back-up
capacity ([HKSM94, GK93, Bak91]) through broadcasting of help messages ([CBMS93, FY94, Gro87,
Wu94]). The performance of several algorithms is given in ([BCS93, CBMS93]).
Overheads due to message passing and software processing render dynamic processing slow. For dynamic
link restoration using digital cross-connect systems, a two second restoration time is a common
goal for SONET ([FY94, Gro87, KA93, Sos94, Wu94, YH88]). Pre-planned methods depend mostly
on look-up tables and switches or add-drop multiplexers. For optical networks, switches may operate
in a matter of microseconds or nanoseconds. Thus, to meet our speed requirement, we consider
pre-planned methods, even though pre-planned methods suer from poorer capacity utilization than
dynamic systems, which use of real-time availability of back-up capacity.
Within pre-planned methods, we may distinguish between path and link or node restoration. Path
restoration refers to recovery applied to connections following a particular path across a network.
Link or node restoration refers to recovery of all the tra-c across a failed link or node, respectively.
Path restoration may be itself subdivided into two dierent types: live (dual-fed) back-up and event-triggered
back-up. In the rst case, two live
ows, a primary and a back-up, are transmitted. The
two
ows are link-disjoint if we seek to protect against link failure, or node-disjoint (except for the
end nodes) if we seek to protect against node failure. Upon failure of a link or node on the primary
ow, the receiver switches to receiving on the back-up. Recovery is thus extremely fast, requiring
action only from the receiving node, but back-up capacity is not shared among connections. In the
second case, event-triggered path restoration, the back-up path is only activated when a failure occurs
on a link or node along the primary path. Backup capacity can be shared among dierent paths
([WLH97]), thus improving capacity utilization for back-up channels and allowing for judicious planning
([BPG92, HBU95, GBV91, HB94, GKS96, SNH90, VGM93, Fri97, NHS97]). However, recovery
involves coordination between the sender and receiver after a failure event and action from nodes
along the back-up path. These coordination eorts may lead to signicant delays and management
overhead.
Pre-planned link or node restoration can be viewed as a compromise between live and event-triggered
path restoration. Pre-planned link restoration is not as capacity-e-cient as event-triggered
path restoration ([CWD97, RIG88, LZL94]), but is more e-cient than live back-up path restoration,
since sharing of back-up bandwidth is allowed. The tra-c along a failed link or node is recovered,
without consideration for the end points of the tra-c carried by the link or node. Thus, only the
two nodes adjacent to the failure need to engage in recovery. The back-up is not live, but triggered
by a failure. A comparison of the trade-os between end-to-end recovery and patch of a segment (we
assume a segment to be a single link or node), is given in [DW94]. An overview of the dierent types
of protection and restoration methods is given in [RM99] and comparisons between path protection
and event-triggered path protection are given in [RM99, RIG88, JVS95, JAH94, XM99].
Link or node restoration also benets from a further advantage, which makes it very attractive for
pre-planned recovery: since it is not dependent upon specic tra-c patterns, it can be pre-planned
once and for all. Thus, link or node restoration is particularly attractive at lower layers,
where network management may not be aware, at all locations of the network, of the origination and
destination, or of the format ([Wu94]) of all the tra-c being carried at that location. Therefore, in this
paper we concentrate on pre-planned link and node restoration in order to satisfy our transparency
requirement. Moreover, link restoration satises the rst part of our
exibility goal, since restoration
is done without consideration for primary routings.
For pre-planned link restoration, the main approaches have been through the use of covers of rings
and, more recently, through pre-planned cycles ([GS98]). The most direct approach is to design the
network in term of rings. The building blocks of SONET networks are generally self-healing rings
(SHRs) and diversity protection (DP) ([WCB91, Was91, WB90, SWC93, SGM93, SF96, STW95,
HT92]). SHRs are unidirectional path-switched
rings (UPSRs) or bi-directional line-switched rings (BLSRs), while DP refers to physical redundancy
where a spare link (node) is assigned to one or several links (nodes) ([Wu92] pp. 315-32). In rings, such
as BLSR, link or node restoration is simply implemented using loop-back. The waste of bandwidth due
to back-hauling may be remedied by looping back at points other than the failure location ([Mag97,
KTK94]).
Using only DP and SHRs is a constraint which has cost implications for building and expanding
networks ([WKC89]); see [Sto92] for an overview of the design of topologies under certain reliability
constraints. However, rings are not necessary to construct survivable networks ([NV91, WH91]).
Mesh-based topologies can also provide redundancy ([Sto92, JHC93, WKC88]). Ring-based architectures
may be more expensive than meshes ([BGSM94]), and as nodes are added, or networks are
interconnected, ring-based structure may cease to be maintained, thus limiting their scalability. Even
if we constrain ourselves to always use ring-based architectures, such architectures may not easily
bear changes and additions as the network grows ([WKC89, Wu92, WKC88]. For instance, adding
a new node, connected to its two nearest node neighbors, will preserve mesh structure, but may not
preserve ring structure. Our arguments indicate that, for reasons of cost and extensibility, mesh-based
architectures are more promising than interconnected rings.
Covering mesh topologies with rings is a means of providing both mesh topologies and distributed,
ring-based restoration. There are several approaches to covers of rings for networks in order to ensure
link restorability. One approach is to cover nodes in the network by rings ([Was91]). In this manner,
a portion of links are covered by rings. If primary routing is restricted to the covered links, then
link restoration can be eected on each ring in the same manner as in a traditional SHR, by routing
the back-up tra-c around the ring in the opposite direction to the primary tra-c. Using such an
approach, the uncovered links can be used to carry unprotected tra-c, i.e. tra-c which may not be
restored if the link which carries it fails.
To allow every link to carry protected tra-c, other ring-based approaches ensure every link is
covered by a ring. One approach to selecting such covers is to cover a network with rings so that
every link is part of at least one ring ([Gro92]). This approach suers from some capacity drawbacks.
With ber-based restoration, every ring is a four-ber ring. A link covered by two rings requires eight
bers; a link covered by n rings requires 4n bers. Alternatively, the logical bers can be physically
routed through four physical bers, but only at the cost of signicant network management overhead.
Minimizing the amount of ber required to obtain redundancy using ring covers is equivalent to nding
the minimum cycle cover of a graph, an NP-complete problem ([Tho97, ILPR81]), although bounds
on the total length of the cycle cover may be found ([Fan92]).
A second approach to ring covers, intended to overcome the di-culties of the rst approach, is
to cover every link with exactly two rings, each with two bers. The ability to perform loop-back
style restoration over mesh topologies was rst introduced in [ESH97, ES96]. In particular, [ESH97]
considers link failure restoration in optical networks with arbitrary two-link redundant arbitrary mesh
topologies and bi-directional links. The approach is an application of the double-cycle ring cover
([Jae85, Sey79, Sze73]). For planar graphs, the problem can be solved in polynomial-time; for non-planar
graphs, it is conjectured that double cycle covers exist, and a counterexample would have to
obey certain properties ([God85]). Node recovery can be eected with double cycle ring covers, but
such restoration requires cumbersome hopping among rings. In subsection 3.2, we consider double-
cycle covers in the context of wavelength-based recovery.
In order to avoid the limitations of ring covers, an approach using pre-congured cycles, or p-
cycles, is given in [GS98]. A p-cycle is a cycle on a redundant mesh network. Links on the p-cycle
are recovered by using the p-cycle as a conventional BLSR. Links not on the p-cycle are recovered
by selecting, along the p-cycle, one the paths which connect the nodes which are the end-points of
the failed link. We may note that some di-culty arises from the fact that several p-cycles may
be required to cover a network, making management among p-cycles necessary. The fact that a
single p-cycle may be insu-cient arises from the fact that a Hamiltonian might not exist, even in a
two-connected graph. Even nding p-cycles which cover a large number of nodes may be di-cult.
Some results ([Fou85, Jac80, ZLY85]) and conjectures ([HJ85, Woo75]) exist concerning the length of
maximal cycles in two-connected graphs. The p-cycle approach is in eect a hybrid ring approach,
which mixes path restoration (for links not on the p-cycle) with ring recovery (for links on the p-cycle).
Generalized Loop-back
2.1 Generalized Loop-back for Recovery from Link Failures
The gist of our approach is to eliminate the use of rings. Instead, a primary (secondary) digraph
(corresponding to a set of unidirectional bers or wavelengths) is backed up by another, secondary
(primary) digraph (corresponding to a set of unidirectional bers or wavelengths in the reverse direction
of the primary (secondary) digraph). After a failure occurs, we broadcast the stream carried
by the primary (secondary) digraph along the failed link onto the secondary (primary) digraph. We
later show a protocol which ensures that only a single connection arrives to each node on the back-up
path.When the back-up path reaches the node which lost its connection along the primary (secondary)
digraph because of the failure, the tra-c is restored onto the primary (secondary) digraph.
To illustrate our method, consider a simple sample network. Our algorithm works by assigning
directions to each of the two bers on each link. Figure 1.b shows in dashed arrow lines the directions
of the primary digraph for each link and in thin dashed lines the directions of the secondary digraph
for each link. The topology of the network is shown in bold lines without arrows. A break in a link
is shown by discontinued lines. The shortest back-up path is node 3 4.
Node 3 eliminates a duplicate connection which arrives to it via node 6 ! node 5 ! node 4 ! node 3.
Node 7 eliminates a duplicate connection which arrives to it via node 2 ! node 1 ! node 8 ! node
7. Note that back-haul need not always occur. For instance, in Figure 1.b, if the original connection
went from node 4 to node 2 via node 3, then after recovery the connection would commence at node
4 and traverse, in order, nodes 3, 6, 7 en route to node 2.
Not every assignment of directions provides the possibility for loop-back recovery. As an example,
consider in Figure 1.a the same network topology as in Figure 1.b with dierent directions. The
directions are provided in such a way that, when no failures are present, all nodes are reachable from
each other on the primary wavelength on ber 1 and on the secondary wavelength on ber 2. However,
the same link failure as in Figure 1.b is not recoverable. This example illustrates the importance of
proper selection of the directions on the links.
We may now formalize our approach. We dene an undirected graph E) to be a set of
nodes N and edges E. With each edge [x; y] of an undirected graph, we associate two directed arcs
(x; y) and (y; x). We assume that if an edge [x; y] fails, then arcs (x; y) and (y; x) both fail. A directed
graph is a set of nodes N and a set of directed arcs A. Given a set of directed arcs, A,
dene the reversal of A to be Ag. Similarly, given any directed graph
to be the reversal of P .
Let us consider that we have a two vertex (edge)-connected graph, or redundant graph
i.e. removal of a vertex (edge) leaves the graph connected. Our method is based on the construction
of a pair of directed spanning sub-graphs, each of which can
be used for primary connections between any pair of nodes in the graph. In the event of a failure,
connections on y are looped back around the failure using R. Similarly, connections on R are looped
back around the failure using B. For instance, if G were a ring, then B and R would be the clockwise
and counter-clockwise cycles around the ring.
To see how loop-back operates in a general mesh network, consider rst the case where an edge
fails. Assume (w; y) and (x; z) are arcs of R and that the shortest loop-back path around [x; y]
is node x ! node z !    ! node w ! node y. We create two looping arcs, Bloop x;z and Rloop y;w .
Bloop x;z is created at node x by attaching the tail of (z; x) 2 A to the head of (x; z) 2 A so that
signals which arrive for transmission on (x; y) in B are now looped back at x to R. Similarly, Rloop y;w
is created by attaching the tail of (w; y) 2 A to the head of (y; w) 2 A, so that any signal which arrives
for transmission on (w; y) in R is looped back to B at y. Figure 2 illustrates our loop-back example.
Edge [x; y] can be successfully bypassed as long as there exists a working path with su-cient capacity
from x to y in R and a working path with su-cient capacity from y to x in B.
Let us consider that we have an edge-redundant undirected graph E). We seek a directed
spanning sub-graph G, and its associated reversal
connected, i.e. there is a directed path in B from any node to any other
node.
condition 2: (i;
A.
Since R is connected i B is connected, condition 1 insures that any connection can be routed on
B or R. Condition 1 also ensures that loop-back can be performed. Suppose edge [x; y] fails. Also
suppose without loss of generality that (x; y) is an arc of B. In order to eect loop-back, we require
that there exist a path from x to y in Rn(y; x) and a path from y to x in Bn(x; y). Such paths
are guaranteed to exist because B and R are connected and such paths obviously do not traverse
(x; y) or (y; x). Hence, connectivity is su-cient to guarantee loop-back connectivity in the event of
an edge failure. Since condition 2 implies that (i; j) cannot be an arc of B and R, condition 2 ensures
that loop-back connections on R do not travel over the same arc as primary connections on B, and
vice-versa. Therefore, any algorithm which builds a graph B with properties 1 and 2 will su-ce. The
algorithm presented below is one such algorithm.
We start by choosing an arbitrary directed cycle G with at least 3 nodes (k  3).
Such a cycle is guaranteed to exist if G is edge-redundant. If this cycle does not include all nodes in
the graph, we then choose a new directed path or cycle that starts and ends on the cycle and passes
through at least one node not on the cycle. If the new graph does not include all nodes of the graph,
we again construct another directed path or cycle, starting on some node already included, passing
through one or more nodes not included, and then ending on another already included node. The
algorithm continues to add new nodes in this way until all nodes are included. We now formally
present the algorithm followed by the proof of its correctness.
ALGORITHM FOR SELECTING DIRECTIONS TO RECOVER FROM NODE
FAILURES
1.
2. Choose any cycle (c in the graph with k  3.
3.
4. If N
5.
6. Choose a path or cycle pc
) such that x j;0
and such that the
other vertices, x j;i , 1  i  L j are chosen outside of N j 1 . For a path, we require x j;0 6= x j;L j
and
A. For a cycle, we require L j < 3 and x
7.
8. Go to step 4.
We rst show that the algorithm for the edge-redundant case terminates if the graph is two edge-
connected, i.e. edge-redundant. We shall proceed by contradiction. The algorithm would fail to
terminate correctly i, at step 6, no new path or cycle pc j could be found but a vertex in N was
not included in N j 1 . We therefore assume, for the sake of contradiction, that such a vertex exists.
Because the graph is connected, there is an edge which connects some x in N j 1 to some
y in NnN j 1 . Because the graph is edge-redundant, there exists a path between x and y which does
not traverse e. Let be the last edge from which this path exits N
. Note that w and x can be the same, but if y. Similarly, y and z may
be the same, but then x 6= w. Now, there exists a path from x to w, passing through y, which would
be selected at step 6. Thus, we have a contradiction.
It is easy to see that Condition 2 is satised. Note that if (i; j) is already included in the directed
sub-graph, then Step 6 ensures that (j; i) cannot be added.
Therefore, all that remains to be shown is that B is connected. We use induction on the sub-graphs
obviously connected. Indeed, B 1 is an unidirectional ring. Assume B j 1 is connected, for
2. We need to show for all x; y 2 N j , there is a directed path from x to y in B j . There are 4
cases: (1) x, y
Case 1 follows from the induction hypothesis and the fact that A j is a superset of A j 1 .
For case 2, we have that x; y 2 pc j . Pick vertices l and k such that x
i.e. y comes after x on the path
is a path from x to y in
. If l < k, i.e. y comes before x on the path
), then there exists a path from x to x j;L j
on pc j and a path from x j;0 to y on pc j . If x
, then (x; x
is a path
from y to x in B j . If x j;0 6= x j;L j
, then, by the induction hypothesis, there exists a path p(x j;L j
from x j;L j
to x j;0 in B j 1 and hence on B j . Therefore, (x; x
a path from x to y.
For case 3, we have x 2 pc j , y 2 N j 1 . Pick k such that x by the induction
hypothesis, there exists a path from x j;L j
to y. Vertex x is therefore connected to y since there is a
path from x to x j;L j
on pc j .
For case 4, we have that y 2 pc j , x 2 N j 1 . There is a path from x to x j;0 by the induction
hypothesis, and from x j;0 to y on pc j .
A very simple network management protocol will enable recovery using our choice of directions
created by the above algorithm. When recovering from an arc failure on the primary (secondary)
digraph, the protocol need only broadcast on the secondary (primary) digraph. Each node retains
only the rst copy of the broadcast and releases all unnecessary connections created by the broadcast.
This simple concept is embedded in the protocol presented in Section 2.3.
2.2 Generalized Loop-back for Recovery from Node Failures
While the previous section dealt with recovery from link failures, we consider in this section the event
where a node fails. Note that the failure of a node entails the failure of all links incident upon the
failed node. The failure of a node therefore requires dierent techniques than those used to deal with
link failures.
Let us rst overview the operation of loop-back in a mesh network when there is failure of a node.
Each node connected by a link to the failed node, i.e. adjacent to the failed node, independently
performs loop-back in the same manner as if the link connecting the failed node to the looping node
had failed. We assume that only one primary connection per wavelength is incident upon each node
but that there may be several outputs along one wavelength per node. Thus, we allow the use of
multicasting at nodes. The purpose of our restriction on the connections through a node is to ensure
that, after loop-back, there are no collisions in the back-up graph. Multicasting applications are
particularly attractive for WDM networks, because splitting at optical nodes oers a simple and
eective way of performing multicasting. Note that two types of tra-c are looped back: tra-c
destined for the failed node and tra-c which only traversed the failed node. Let us rst consider the
rst type of tra-c in the case where a node, say j, performs loop-back on the link between j and
node k, the failed node. Node j receives on a back-up channel tra-c intended for node k. Only two
cases are possible: either link [j; k] failed but node k is still operational or node k failed. Note that
we have made no assumption regarding the ability of the network management system to distinguish
between the failure of a node and the failure of a link. Indeed, the nodes may only be aware that
links have ceased to function, without knowing whether the cause is a single link failure or a node
failure. Since we have a node-redundant network, our loop-back mechanism can recover from failure
of node j, which entails failure of link [j; k]. Hence, even if there has been failure of link [j; k] only,
node j can eliminate all back-up tra-c destined to node k, because the back-up mechanism ensures
that back-up tra-c destined for node k arrives to node k even after failure of node j. If node k failed,
then eliminating back-up tra-c destined for k will prevent such back-up tra-c from recirculating in
the network, since recirculation would cause collisions and congestion. Thus, regardless of whether a
node failure or a link failure occurred, back-up tra-c destined for the failed node will be eliminated
when a node adjacent to the failed node receives it. In SONET SHRs, a similar mechanism eliminates
tra-c intended for a failed node.
We may now illustrate our mechanism with a specic example applied to the network we have been
considering. Figure 3 shows a sample set of directions which can be selected for generalized loop-back
recovery from node failure. Let us rst consider the case where we have a primary connection along
the full line from node 1 to node 3 via node 2 and node 2 fails. The shortest loop-back path is node
3. Let us now consider the case where we have a primary
connection along the full line from node 1 to node 2 and node 2 fails. Then, the back-up path goes
from node 8 to node 7, which eliminates the connection, because node 7 is adjacent to node 2.
We model our network as a vertex-redundant undirected graph E). We seek a directed
spanning sub-graph G, and its associated reversal
Condition 1: B is connected, i.e. there is a directed path in B from any node to any other
node.
Condition 2: (i;
A.
Condition 3: For all x; n; y 2 N such that (x; n), (n; y) are arcs of B, there exists a directed
path from x to y in R which does not pass through n.
As in the edge-redundant case, Condition 1 insures that any connection can be routed on B or R.
However, unlike the edge-redundant case, connectivity is insu-cient to guarantee loop-back connectivity
after failure. Also as in the edge-redundant case, Condition 2 insures that loop-back connections
on R do not travel over the same arc as primary connections on B, and vice-versa. Condition 3 insures
that loop-back can be successfully performed and is equivalent to the statement that all 3 adjacent
nodes in B, x, n, y are contained in a cycle of B.
We perform loop-back for node failures in the same manner as described above for link failures.
For instance, let us select two distinct nodes w and z. Let p 1 be the path in B, i.e. the path traversed
over  1 on ber 1, from w to z and let n be a node other than w or z traversed by p 1 . We consider the
nodes x and y such that (x; n) and (n; y) are traversed in that order in p 1 . Thus, (x; n), (n; y) are in
A. Let p 2 be a path in R which does not include vertex n and which goes from vertex x to vertex y.
We perform loop-back from w to z using paths p 1 , p 2 at node n by traversing the following directed
circuit:
from w to x, we use path
at x, we loop-back from primary to secondary
from x to y, we use path
at y, we loop-back from secondary to primary
from y to z, we use path p 1 .
As discussed previously, this loop-back is more general than the type of loop-back used in a
ring. In particular, the loop-back is not restricted to use a back-haul route traversing successively
In order to guarantee loop-back, it is su-cient to select B and R so that, in the event
of any vertex (edge) failure aecting B or R, there exists a working path around the failure on the
other sub-graph.
Any sub-graph with Conditions 1-3 is su-cient to perform loop-back as described above. The
algorithm below guarantees these conditions by amending the algorithm for the edge-redundant case.
The edge-redundant algorithm fails to insure Condition 3 for two reasons. The rst reason is that
cycles are allowed in Step 6, i.e. pc possible in iteration j, and hence failure
of node x j;0 would leave both B and R disconnected. The second and more fundamental reason is
that the ordering of the nodes on the added paths in steps 6 and 7 is very unrestrictive.
Our algorithm starts by choosing a directed cycle of at least 3 vertices containing some arbitrary
s]. If this cycle does not include all nodes in the graph, we then choose a directed path
that starts on some node in the cycle, passes through some set of nodes not on the cycle, and ends
on another node on the cycle. If the cycle and path above do not include all vertices of the graph,
we again construct another directed path, starting on some node already included, passing through
one or more nodes not included, and then ending on another already included node. The algorithm
continues to add new nodes in this way until all nodes are included.
It is simple to show that, in a vertex-redundant graph, for any edge e, a cycle with 3 vertices must
exist containing e. It can also be seen that, for any such cycle, a path can be added as above, and
subsequent paths can be added, in arbitrary ways, until all nodes are included. It is less simple to
choose the direction of the added paths, and hence the B and R directed sub-graphs. The technique
we present relies in part on results presented [MFBG99, MFB97, FMB97, MFGB98]. We now present
the algorithm followed by the proof of its correctness.
ALGORITHM FOR SELECTING DIRECTIONS TO RECOVER FROM NODE
FAILURES
1. 1. Pick an arbitrary edge
2. (a) Choose any cycle (s; c in the graph with k  2.
(b) Order these nodes by assigning values such that
3.
4. If N
5.
6. (a) Choose a path
2, in the graph such that x
). The other vertices, x j;i , 1  i < L j , are chosen outside of
(b) Order the new vertices by assigning values such that v(x j;0
7.
8. Go to step 4.
Note in step 6b that v max  v(x j;L j
We rst show that the algorithm for the node-redundant
case terminates if the graph is vertex-redundant. We shall proceed by contradiction. The algorithm
would fail to terminate correctly, i at step 6 no new path p j could be found but a vertex in N was
not included in N j 1 . We assume for the sake of contradiction that such a vertex exists. Because of
the graph is connected, there is an edge [x; y] which connects some x in N j 1 to some y in NnN j 1 .
Pick a vertex q 2 N j 1 , such that q 6= x. Because the graph is node-redundant, there exists a path
between y and q which does not use x. Let be the last edge from which this path exits
. Note that possible. Now, there exists a path
from x to w, passing through y, which would be selected at step 6 in the algorithm. Therefore, we
have a contradiction.
We now prove that B satises Conditions 1-3. The fact that B is connected follows by induction
on j using almost identical arguments as used in the proof for the link-redundant case. In particular,
we can see by induction on j that there is a directed path in B j from x 2 N j to any y 2 N j . Since
these properties hold for each j, they also hold for the nal directed sub-graph B. We may therefore
state that B is connected. As in the edge-redundant case, Condition 2 is satised by the restrictions
on adding new arcs.
Finally, we prove that B satises Condition 3. We need to prove the fact that, for all x; n; y 2 N
such that (x; n), (n; y) are arcs of B, there exists a directed path from x to y in R which does not
pass through n. Since R is the reversal of B, we can prove the equivalent statement that there exists
a directed path from y to x in B which does not pass through n. The key observation is to note that
has a special property. In particular, it is the only arc in B for which the value of the
originating node is lower than the value of the terminating node, i.e.
all (i; From this property it immediately follows that all
directed cycles in B contain (t; s). To see this, let x be a cycle and note that, if (t; s)
were not traversed in this cycle, then v(x could not be
an arc in B. Also, since B is connected, we also have that (t; s) is the unique arc into s in B for,
otherwise, we could construct a cycle through s which did not pass through t.
Only two cases need to be considered to prove the desired property: First
consider is connected, there exists a path from y to x in B and this path need not
include s, since the only way to reach s is through t. Now consider n 6= s. There exists paths
n) from y to n and p(n; from n to x, both in B.
is a cycle, it includes s. Similarly, (n; xm ; xm n) is a cycle and
hence includes s. Therefore, there is a path starting at y, proceeding on p(y; n) until s (which is before
n in p(y; n)), starting in p(n; x) at s (which is after n in p(n; x) ), and ending at x.
2.3 Protocol
We now overview a protocol which ensures proper recovery, using generalized loopback for node or link
recovery. Our protocol is more involved than that need to recover only from a link failure, since we
must contend with the failure of all links adjacent to the failed node. However, our algorithm will also
operate properly for link failures without node failures. Our protocol uses negative acknowledgements
and labels, to establish correct rerouting. The signaling for the protocol may be performed over an
out-of-band control channel, or any in-band control channel scheme, such as a subcarrier multiplexed
signal.
Consider the failure of a primary ber from x to y. Failure of the ber may be due to failure of
the ber itself or of node y. When x detects the failure, it writes "y" into the failure label and loops
the primary stream back into the back-up digraph, splitting it across all outgoing arcs in the back-up
digraph. As the tra-c enters each new node, the node forwards the tra-c, again splitting it over
all outgoing arcs. Backup bers leaving a node can be pre-congured to split an incoming stream,
shortening the time required to
ood failure information across outgoing links. For nodes with only
one incoming stream, the route is fully pre-planned, and no tra-c is lost during the decision process.
For nodes with more than one incoming stream, the rst of the streams to receive tra-c is chosen
for forwarding. A stream that becomes active after the rst- typically owing to tra-c from the same
failure arriving via a dierent route- is dropped, and a negative acknowledgement (NACK)is returned
on the reverse back-up arc. A node that receives a NACK on an outgoing link ceases to forward tra-c
on that link. If all outgoing links for a node are NACKed, the node propagates a NACK on its own
incoming link, in eect releasing the connection on that link. If all outgoing links at x are NACKed,
recovery has failed (possibly multi-failure scenarios or scenarios where several connections over the
same wavelength were present at a failed node).
The NACK-based protocol can be extended with hop-count and signal-power (splitting) restrictions
to reduce the area over which a failure propagates, but such restrictions require more careful selection of
the back-up digraph to guarantee recovery from all single failures and to prevent signicant degradation
of multi-failure recovery possibilities.
The use of NACKs serves to limit the use of back-up arcs to those necessary to recovery. Another
approach to achieving this goal is to mark the successful route and forward tear-down messages
down all other arcs. The NACK scheme is superior to this approach in two ways. First, tear-down
messages must catch up with the leading edge of the tra-c, but cannot travel any faster. In the
worst case, a route is torn down only to allow a cyclic route to recreate itself, resulting in long-term
tra-c instabilities in the back-up digraph. To avoid this possibility, tear-down requires that nodes
remember the existence of failure tra-c between the time that they tear down the route and the time
that the network settles (a global phenomenon). A second point in favor of the NACK-based scheme
is that it handles multicast (possibly important for node failures) naturally by discarding only unused
routes. A tear-down scheme must know the number of routes to recover in advance or discover it
dynamically; the rst option requires a node to know the routes through its downstream neighbors,
while the second option is hard because of timing issues (when have all routes been recovered?).
Meanwhile, y detects the loss of the stream and begins listening for tra-c with its name or x's
name on the back-up stream. The second case handles failure of node x, which results in
ooding of
tra-c destined for x. Note that tra-c for x can also be generated owing to failure of a primary arc
ending at x, but, in such a case, y does not detect any failure and does not listen for back-up tra-c.
Once a stream with either name is received, it is spliced into the primary tra-c stream, completing
recovery. Other paths are torn down through NACKs.
Note that if a stream ends at a failed node x, no node listens for the back-up tra-c for node x,
and all connections carrying back-up tra-c for node x are eventually torn down.
While our protocol for node failure is more complicated than that for link failure, it is still relatively
simple. Node failure in ring-based systems is a very complex operation whenever a node is on more than
one ring. For double cycle cover, node recovery requires hopping among rings, and thus necessitates
a centralized controller with global knowledge of the network. Even for simple double-homed SONET
rings, node recovery involves the use of matched nodes. Proper operation of matched nodes requires
signicant inter-ring signaling as well as dual-fed path protection between rings.
Applications
3.1 Choice of Routings
In this Section, we present heuristic algorithms for selecting directions in the back-up graph. We
seek to select directions in such a way to avoid excessive length for back-up paths. We consider three
dierent algorithms.
The rst algorithm, which we term Heuristic 1, rst nds, for each link, a shortest loop which
includes that link. A loop is a directed cycle, thus a shortest loop is a directed cycle with the
minimum number of links. We order the shortest loops of all the links in ascending order of length.
Shortest loops with equal lengths are ordered arbitrarily with respect to each other. Beginning with
the rst shortest loop, in ascending order, we assign, whenever possible, directions according to the
directions of the arcs along the shortest loop.
The second algorithm, Heuristic 2, also relies on considering shortest loops but takes into account
the fact that the choice of direction on a link may aect other links. We create a heuristic measure of
this eect, which we call associate number (AN). The AN of link is the number of dierent shortest
loops which pass through that link. In particular, the AN can help us distinguish among links with
equal length shortest loops. We order the links in ascending order of AN. We begin, as for Heuristic 1,
by nding, for each link, a shortest loop which includes that link. Links with equal ANs are ordered
arbitrarily with respect to each other. Beginning with the rst link and progressing in ascending order
we assign directions, whenever possible, according to the shortest loop of the link being considered.
The last algorithm we consider is a random assignment of directions. While the number of possible
directions is exponential in the number of links, we may signicantly reduce that number by requiring
that the directions be feasible.
We apply our algorithms to three networks, NJ LATA, LATAX and ARPANET, shown in gures
4, 5 and 6. We consider the maximum length of a back-up path and the average length. Table 1
shows the results obtained from running the dierent algorithms for the three networks we consider.
times for each network and the best result was kept for the maximum and the
average. Note that the same choice of directions did not always yield both the best maximum and
the best average. Heuristic 2 was run in the same way as Heuristic 1. For the random algorithm, we
limited ourselves to 52 runs for NJ LATA, 128 runs for runs for ARPANET. The best
maximum and the best average were chosen in each case. Comparing the running time of running the
times versus the above number of times for the random algorithm, we obtain
that Heuristic 1 yielded a run time improvement of 72 %, 90 %, 88 % over random choice of directions
for NJ LATA, LATAX and ARPANET, respectively. Heuristic 2 yielded a run time improvement of 73
%, 91 %, 90 % over random choice of directions for NJ LATA, LATAX and ARPANET, respectively.
From our simulations, Heuristic 2 was slightly better than Heuristic 1 in terms of run time and average
back-up length.

Table

1: Comparison of the best results between heuristic algorithms and the method of selecting directions
randomly
Random Heuristic 1 Heuristic 2
Max. Avg. Max. Avg. Max. Avg.
3.2 WDM-based Loop-back Recovery
In ber-based restoration, the entire tra-c carried by a ber is backed by another ber. In ber-
based restoration it does not matter whether the system is a WDM system. If tra-c is allowed in
both directions in a network, ber-based restoration relies on four bers, as illustrated in Figure 7. In
WDM-based recovery, restoration is performed in a wavelength-by-wavelength basis.
WDM-based recovery requires only two bers, although it is applicable to a higher number of
bers.

Figure

8 illustrates WDM-based recovery. A two-ber counter-propagating WDM system can
be used for WDM-based restoration, even if tra-c is allowed in both directions. Note that WDM
restoration as shown on Figure 8 does not require any change of wavelength. Thus, tra-c initially
carried by  1 is backed up by the same wavelength. Obviating the need for wavelength changing is
economical and e-cient in WDM networks. One could, of course, back up tra-c from  1 on ber
ber 2, if there were advantages to such wavelength changing, for instance in terms of
wavelength assignment for particular tra-c patterns. We can easily extend the model to a system
with more bers, as long as the back-up for a certain wavelength on a certain ber is provided by
some wavelength on another ber. Moreover, we may change the ber and/or wavelengths from one
ber section to another. For instance, the back-up to  1 on ber 1 may be  1 on ber 2 on a two-ber
section and  2 on ber 3 on another section with four bers. Note, also, that we could elect not to
back up  1 on ber 1 and instead use  1 on ber 1 for primary tra-c. The extension to systems
with more bers, inter-wavelength back-ups and heterogeneous back-ups among ber sections can be
readily done.
There are several advantages to WDM-based recovery systems over ber-based systems. The rst
advantage is that, if bers are loaded with tra-c at half of total capacity or less, then only two
bers rather than four are needed to provide recovery. Thus, a user need only lease two bers, rather
than paying for unused bandwidth over four bers. On existing four-ber systems, bers could be
leased by pairs rather than fours, allowing two leases of two bers each for a single four-ber system.
The second advantage is that, in ber based-systems, certain wavelengths may be selectively given
restoration capability. For instance, half the wavelengths on a ber may be assigned protection, while
the rest may have no protection. Dierent wavelengths may thus aord dierent levels of restoration
QoS, which can be re
ected in pricing. In ber-based restoration, all the tra-c carried by a ber is
restored via another ber.
If each ber is less than half full, WDM-based loop-back can help avoid the use of counterpropagating
wavelengths on the same ber. Counterpropagating wavelengths on the same ber are intended
to enable duplex operation in situations which do not require a full ber's worth of capacity in each
direction and which have scarce ber resources. However, counterpropagation on the same ber is
onerous and reduces the number of wavelengths that a ber can carry with respect to unidirectional
propagation. Our WDM-based loop-back may make using 2 unidirectional bers preferable to using
counterpropagating bers, where one ber is a back-up for the other.
We may now draw a comparison between generalized loop-back and double cycle covers for WDM-based
loop-back recovery. The ability to perform restoration over mesh topologies was rst introduced
in [ESH97, ES96]. In particular, [ESH97] considers link failure restoration in optical networks with
arbitrary two-link redundant arbitrary mesh topologies and bi-directional links. The scheme relies on
applying methods for double cycle covers to restoration.
Let us rst discuss how double-cycle ring covers can be used to perform recovery. A double cycle
ring cover covers a graph with cycles in such a way that each edge is covered by two cycles. Cycles
can then be used as rings to perform restoration. Each cycle corresponds either to a primary or a
secondary two-ber ring. For two-edge connected planar graphs, a polynomial-time algorithm exists
for creating double cycle covers. For two-edge connected non-planar graphs, the fact that double cycle
covers exist is a conjecture, thus no algorithm except for exhaustive search exists. In this subsection,
we consider an example network and its possible double cycle covers. On the basis of these double
cycle covers, we discuss whether double cycle covers can be used in the context of WDM loop-back,
described in the previous section.
Let us consider a link covered by two rings, rings 1 and 2. If we assign a direction to ring 1 and
the opposite direction to ring 2, then ring-based recovery using the double cycle cover uses ring 2
to back up ring 1. In eect, this recovery is similar to recovery in conventional SHRs, except that
the two rings which form four-ber SHRs are no longer co-located over their entire length. Figure 9
shows the two possible double cycle covers, shown in thin lines, for a certain ber topology, shown in
bold lines. In the case of four ber systems, with two bers in the same direction per ring, we have
ber-based recovery, because bers are backed up by bers. For the type of WDM-based loop-back
we consider in this section, each ring is both primary for certain wavelengths and secondary for the
remaining wavelengths. For simplicity, let us again consider just two wavelengths. Figure 10 and 11
show that we cannot use one ring to provide WDM-based loop-back back-up for another unless we
perform wavelength changing and add signicant network management. We cannot assign primary
and secondary wavelengths in such a way that a wavelength is secondary or primary over a whole ring.
We may point out another drawback of the back-up paths aorded by double cycle covers. For
both ring covers shown in Figure 9, some links are covered by rings which are not of the same length.
For instance, in Figure 10, a break on a link may cause one direction to be backed up on ring 1,
while another direction may be backed up on ring 4. Thus, the back-up may traverse only three links
along ring 1 in one direction and seven links along 4 in the other direction. The two directions on
a link will therefore have dierent delays in their restoration time and incur dierent timing jitters.
Such asymmetry in the propagation for the back-up path does not occur in SHRs or in generalized
loop-back, since the back-up paths for both directions traverse the same links.
3.3 Plurality of Back-up Routes for Generalized Loop-back
We have mentioned that our algorithm can be used to perform recovery even when there is a change
in the conditions of the networks. In this section, we give a brief example of how such
exibility is
aorded. Figure 12 illustrates our example. We have single network, with a recovery sub-graph built
for link failure restoration. In case of failure of the link between node 2 and node 3, the recovery
back-up path is shown by a curving directed line. The shortest back-up path uses the link between
nodes 9 and 10, as shown on Figure 12. Suppose that the link between nodes 9 and 10 becomes
unusable for the back-up path, for instance because the link has failed or because all the wavelengths
on that link are used to accommodate extra tra-c. Then, the back-up path for a failure between
nodes 2 and 3 can be the path node 3 shown
by a curved line on Figure 12.b. Thus, the same back-up sub-graph can be used both when the link
between nodes 9 and 10 is available and when it is not available.
Note that not all links can be allowed to become unavailable. If the link between nodes 3 and 10
becomes unavailable, the restoration after failure of the link between nodes 2 and 3 is not possible.
However, it is possible to determine whether certain links are necessary for recovery in the case of
failure of other links. Since there are two paths in the back-up sub-graph from node 10 to node 9, the
link between nodes 9 and 10 is not necessary and that link can be freed up to carry extra tra-c, if
the need arises.
Recent results [MLT00] have shown that signicant savings, of the order of 25 %, can be achieved
using generalized loop-back over a variety of networks without sacricing the length of the longest
back-up and the ability to recover from double failures.
4 Summary and Conclusions
We have presented generalized loop-back, a novel way of implementing loop-back on mesh networks
without using ring-based schemes. We have established routings and protocols to ensure recovery
after a link or a node failure. Our method is guaranteed to work in polynomial time regardless of
whether the graph representation of the network is planar or not, whereas double cycle covers have
polynomial-time solution only for planar graphs. The gist of our method is to assign directions to
bers and the wavelengths traveling through them. Our method allows great
exibility in planning
the conguration of a network, as long as it has redundancy, while providing the bandwidth utilization
advantages typically associated with loop-back protection in SHRs. Recovery, as in SONET BLSR,
is performed by the nodes adjacent to the link or node failure. Moreover, our loop-back recovery
method does not require the nodes performing loop-back to distinguish between a node and a link
failure. We have shown that simple heuristic algorithms yield satisfactory results in terms of average
and maximum length of back-up paths. We have compared our method to the previously known
method for loop-back for link failure on mesh networks. That method ([ESH97]) is based upon double
cycle covers and we have shown that such a method may not be applied to WDM-based loop-back
systems. Moreover, we have shown by a simple example that generalized loop-back allows recovery to
be performed in a bandwidth-e-cient manner.
There are several areas of further work. One of them is considering the issue of wavelength
assignment jointly with back-up considerations, whether the back-up be loop-back, APS or hybrid.
Another issue is the determination of the back-up path. Broadcasting, or
ooding, in the back-up
wavelength causes that wavelength to be unavailable for other uses in parts of the network which
are not required to provide back-up. Some methods for determining back-up paths are presented in
[FMB98].
Another area for further research is the use of generalized loop-back to perform bandwidth-e-cient
recovery. As we discussed in Section 2.1, link and node restoration generally are less e-cient, in terms
of capacity utilization, than even-triggered path restoration. However, our scheme allows recovery
of links which are not included in the back-up sub-graph, as long as the end nodes are included in
the back-up sub-graph. This operation can be viewed as being akin to p-cycles, but with greater
exibility in the choice of the back-up sub-graph. Eliminating links from the back-up sub-graph is
economical in bandwidth but entails some degradation in terms of other performance metrics, such as
length of back-up path or recovery from two failures. Preliminary results show that signicant savings
in terms of bandwidth utilization can be achieved without appreciable aecting other performance
metrics ([MLT00]).



--R

A distributed link restoration algorithm with robust preplanning.
Performance analysis of fast distributed network restoration algorithms.
An architecture for e-cient survivable networks
Protection planning in transmission networks.
A multi-layer restoration strategy for recon gurable networks
A fast distributed network restoration algorithm.
Spare capacity assignment for di
Comparison of capacity e-ciency of DCS network restoration routing techniques
Automatic protection switching for link failures in optical networks with bi-directional links
Link failure restoration in optical networks with arbitrary mesh topologies and bi-directional links
Covering graphs by cycles.


Longest cycles in 2-connected graphs of independence number
Optimal spare capacity design for various protection switching methods in ATM networks.
Double search self-healing algorithm and its characteristics
Near optimal spare capacity placement in a mesh restorable network.
Techniques for

Dynamic bandwidth-allocation and path- restoration in SONET self-healing networks
A girth requirement for the double cycle cover conjecture.
The selfhealing TM network.
Case studies of survivable ring

An optimal spare-capacity assignment model for survivable networks with hop limits
The hop-limit approach for spare-capacity assignment in survivable networks

Dynamic recon

Covering graphs with simple circuits.
Hamilton cycles in regular 2-connected graphs
A survey of the double cycle cover conjecture.


Topologocial optimization of a communication network subject to a reliability constraint.
Veerasamy and J.
Distributed control algorithms for dynamic restoration in DCS mesh networks: Performance evaluation.
An ATM VP-based self-healing ring
ATM virtual path self-healing based on a new path restoration protocol
A bandwidth e-cient self-healing ring for B-ISDN





A dynamic recon
Design of survivable communication networks under performance constraints.

Survivable WDM mesh networks
Sums of circuits.
Interconnection of self-healing rings
An algorithm for survivable network design employing multiple self-healing rings

Distributed self-healing control in SONET
Service application for SONET DCS distributed restoration.
Design of Survivable Networks.
Survivable network planning methods and tools in taiwan.
A capacity comparison for SONET self-healing ring networks
Polyhedral decomposition of cubic graphs.
On the complexity of

Two strategies for spare capacity placement in mesh restorable networks.
An algorithm for designing rings for survivable
Feasibility study of a high-speed SONET self-healing ring architecture in future intero-ce networks
A multi-period design model for survivable network architecture selection for SDH/SONET intero-ce networks
Strategies and technologies for planning a cost-eective survivable network architecture using optical switches
Survivable network architectures for broad-band ber optic networks: Model and performance comparison

Backup vp preplanning strategies for survivable multicast ATM.
Maximal circuits of graphs ii.
Fiber Network Service Survivability.
A passive protected self-healing mesh network architecture and applications
A novel passive protected SONET bidirectional self-healing ring architecture
Restoration strategies and spare capacity requirements in self-healing ATM networks
Fitness: Failure immunization technology for network service survivability.
An improvement of jackson's result on hamilton cycles in 2-connected graphs
--TR
Covering graphs by cycles
A passive protected self-healing mesh network architecture and applications
On the Complexity of Finding a Minimum Cycle Cover of a Graph
Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks
Restoration strategies and spare capacity requirements in self-healing ATM networks
Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs
Fiber Network Service Survivability
Spare Capacity Assignment in Telecom Networks Using Path Restoration

--CTR
Timothy Y. Chow , Fabian Chudak , Anthony M. Ffrench, Fast optical layer mesh protection using pre-cross-connected trails, IEEE/ACM Transactions on Networking (TON), v.12 n.3, p.539-548, June 2004
Mansoor Alicherry , Randeep Bhatia, Simple pre-provisioning scheme to enable fast restoration, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.400-412, April 2007
Canhui Ou , Laxman H. Sahasrabuddhe , Keyao Zhu , Charles U. Martel , Biswanath Mukherjee, Survivable virtual concatenation for data over SONET/SDH in optical transport networks, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.218-231, February 2006
mesh networks;WDM;loop-back;network restoration