Network restoration under link or node failure using preconfigured virtual cycles

The design of telecommunication networks is such that there is provision of end-to-end path protection to multiple demands under a single link or node failure in the networks. Restoration routes are provided on Preconfigured Virtual Cycles (PVC's), where each demand is assigned one restoration route and specific restoration wavelengths on a segment of one cycle. Multiple demands may share restoration wavelengths, and the number of restoration wavelengths may vary among the PVC links. First, a plurality of candidate PVC's are generated where each demand may be assigned to multiple candidates. Assignment of demands with common failure scenarios are allowed, under certain conditions, to the same PVC. Next, a set of PVC's is selected from among the candidates, while minimizing total reserved restoration capacity and ensuring that all demands are protected. Next duplicate assignments are eliminated. Finally, conflicts of wavelength assignments are resolved. The invention focuses primarily on optical networks.

FIELD OF THE INVENTION

The present invention relates to the design of telecommunications networks where demands are protected from a single link or node failure. Specifically, the invention relates to the design of preconfigured cycles used to restore affected demands instantaneously in the event of a failure where the restoration capacity on the cycles can be shared by different demands. The invention focuses primarily on optical networks.

BACKGROUND OF THE INVENTION

Modern telecommunications networks transport an enormous amount of information. Current optical networks are already capable of transporting 100 channels on a single optical fiber, where each channel can carry 40 gigabits per second. Since companies, government agencies, and the military are dependent on receiving uninterrupted service, instantaneous service restoration in the event of link or node failures has become critically important. Even service interruptions for small durations may cause significant disruptions to the exchange of information and may lead to significant financial losses and to inability of executing mission critical tasks.

This invention focuses on optical networks where almost instantaneous restoration in the event of network failures is critically important. Providing dedicated restoration capacity to each of the demands would provide adequate protection, but would be prohibitively expensive. Numerous papers discuss providing protection through variants of shared mesh restoration methods where restoration capacity can be shared by multiple demands with diverse working routes (i.e., with diverse original provisioned routes); for example, the paper by J. Kennington, E. Olinick, A. Ortynski, and G. Spiride, “Wavelength Routing and Assignment in a Survivable WDM Mesh Network”,Operations Research51, 67-79, 2003. Shared mesh restoration methods use restoration capacity efficiently at the expense of requiring switching and wavelength conversions along intermediate nodes of restoration routes. Furthermore, these methods may require extensive real-time quality testing of end-to-end restoration routes in order to guarantee adequate transmission integrity. Therefore, meeting stringent restoration time requirements for end-to-end restoration routes with adequate quality may be quite challenging.

Preconfigured restoration methods that do not require intermediate switching and wavelength conversions along restoration routes are a topic of considerable research for optical networks. The challenge is to design preconfigured restoration capacity that can be shared by various demands in the event of a failure; thus, achieving almost instantaneous, reliable restoration, while still using much less restoration capacity than dedicated restoration routes. It should be noted that ring architectures have been widely used for Synchronous Optical Networks (SONET) and for Wavelength Division Multiplexing (WDM) networks; see, for example, the paper by S. Cosares, D N. Deutsch, I. Saniee, and O. J. Wasem, “SONET Toolkit: A Decision Support System for Designing Robust and Cost-effective Fiber-optics Networks”,INTERFACES25, No. 1, 20-40, 1995. The resulting networks consist of multiple interconnecting rings where both the demands' working routes and their respective restoration routes are restricted to use only the rings. Local demand may use only a single ring while long distance demands may be routed through multiple interconnected rings. This architecture guarantees very fast and reliable restoration at the expense of significant infrastructure capacity since, typically, working routes restricted to rings are significantly longer than the shortest possible routes and half of the ring capacities is reserved for restoration.

Combining the advantages of arbitrary, often referred to as mesh, working routes with preconfigured restoration methods that allow for capacity sharing without resorting to intermediate switching and wavelength conversions on restoration routes seems to be an attractive approach. A. Kodian and W. D. Grover, “Failure-Independent Path-Protecting p-Cycles: Efficient and Simple Fully Preconnected Optimal-Path Protection”,Journal of Lightwave Technology23, 3241-3259, 2005, A. Kodian, W. D. Grover, and J. Doucette, “A Disjoint Rout-Sets Approach to Design of Path-Protecting p-Cycle Networks”,Proceedings of Workshop on Design of Reliable Communication Networks(DRCN2005), 231-238, Naples, Italy, October 2005, and D. Baloukov, W. D. Grover, and A. Kodian, “Toward Jointly Optimized Design of Failure-Independent Path Protecting p-Cycle Networks”,Journal of Optical Networking7, 62-79, 2008, present a method for mesh working routes of the demands, where end-to-end restoration routes are provided on preconfigured cycles. In their method, referred to as the Failure Independent Path Protecting (FIPP) p-cycles method, multiple demands that do not have any common failure scenarios can be protected by the same cycle. However, their method does not support the assignment of demands with common failure scenarios on the same cycle. Furthermore, their method allows splitting restoration for multiple-wavelength demands across multiple routes in the same or different cycles.

T. Y. Chow, F. Chudak, and A. M. Ffrench, “Fast Optical Layer Mesh Protection Using Pre-Cross-Connected Trails”,IEEE/ACM Transactions on Networking12, 539-548, 2004, present a method that protects mesh working routes of the demands on restoration routes, referred to as trails, that are not constrained to be on cycles but are flexible to follow other structures such as paths with or without loops. Their method allows the sharing of restoration capacity of a trail by multiple demands that do not have any common failure scenario. Their method assigns one demand at a time, thus, constructing trails sequentially. Hence, the resulting design of trails depends on the order in which the demands are assigned. A. Grue and W. D. Grover, “Improved Method for Survivable Network Design Based on Pre-Cross-Connected Trails”,Journal of Optical Networking6, 200-216, 2007, applied their FIPP p-cycles method to designing trails for restoration. Again, a trail can support only demands with no common failure scenario and restoration routes of a demand may be split among multiple trails.

H. Luss and R. T. Wong, “Survivable Telecommunications Network Design Under Different Types of Failures”,IEEE Transactions—SMC, Part A: Systems and Humans34, 521-530, 2004, propose a method that constructs a single cycle that includes all end-nodes of the mesh routes of the demands. Restoration routes for all demands are constructed on the cycle using a pre-specified rule, such as using the shortest route on the cycle. Note that using a single cycle for restoring all demands may lead to inefficient use of capacity due to long restoration routes and the need to protect all demands on that cycle. The method was invented primarily for logical networks (e.g., IP-MPLS); in optical networks a single restoration cycle that includes all end-nodes of the demands may not even exist. Also, the method provides only restoration routes, but does not address the issue of wavelength assignments which is critical when demands that have common failures are assigned to the same cycle.

The present invention provides end-to-end path protection for demands with mesh routes in the network. Restoration routes are provided on segments of cycles where the end-nodes of a working route are the end-nodes of the restoration route for the corresponding demand on the cycle. The method allows multiple demands to share restoration capacity. These demands include those with no common failure scenarios as well as selective demands that do have common failure scenarios, thus achieving more effective use, of restoration capacity than previous methods. Also, the method provides a single restoration route for each of the demands which is often desired by users of optical networks as it simplifies considerable management of traffic at the end-nodes. Nevertheless, the method can readily be modified to allow for multiple restoration routes per demand.

SUMMARY OF THE INVENTION

The present invention designs survivable optical networks that provide end-to-end path protection from any single link or node failure on preconfigured cycles. The working routes of the demands are provided as input and are arbitrary. The restoration routes and the wavelengths assigned to each of these routes are preconfigured. Upon a link or node failure, affected demands are rerouted to their preconfigured restoration routes without any knowledge of the precise failure location. When an end-node of a demand fails, the demand is lost and cannot be restored. For each demand, only a cycle segment that connects its two end-nodes and has no overlapping links with the working route of the demand is used for restoration, where the restoration wavelengths assigned to the demand on its restoration route may be shared with restoration routes for other demands.

For each of the demands, the method generates multiple candidate cycles that can restore the demand on a segment of the cycle. The method attempts to assign additional demands to the candidate cycle, provided that they can be protected by the cycle. These include demands with no common failure scenarios (also referred to as disjoint demands), demands with common failure scenarios but non-overlapping restoration routes, and certain demands with common failure scenarios that can be protected on the cycle without increasing restoration capacity. Each of the restoration routes is also assigned specific wavelengths. Since the restoration route for each of the demands uses only a segment of the cycle, the number of restoration wavelengths that need to be reserved may differ on different links of the cycle. Hence, these cycles are referred to as Preconfigured Virtual Cycles (PVC's). The cost of a restoration wavelength on a link depends on the link length. Often, but not always, this cost is simply proportional to the link length.

Once all candidate cycles are generated for all demands, the method determines an optimal set of selected PVC's so that the total restoration wavelengths cost on restoration routes is minimized while each of the demands is assigned to at least one PVC. Thereafter, the method adjusts the solution so that each demand would be assigned to precisely one of the selected PVC's. Finally, the method resolves potential conflicts among restoration wavelengths and working routes wavelengths, and among restoration wavelengths assigned to restoration routes on adjacent PVC's.

The present invention uses restoration capacity more effectively than previous preconfigured restoration methods by facilitating the assignment of multiple demands, including certain demands with common failure scenarios, to a cycle where each demand uses a restoration route on only a segment of the cycle. It also enforces rerouting of each of the demands into a single restoration route, which is often required. The method can readily be modified to handle the case where demands can be rerouted onto multiple restoration routes.

The present invention will be more clearly understood when the following description is read in conjunction with the accompanying drawings.

DETAILED DESCRIPTION

The present invention designs survivable optical networks that provide end-to-end path protection from any single link or node failure. The restoration routes and the restoration wavelengths assigned to each of these routes are specified on Preconfigured Virtual Cycles (PVC's), where the number of restoration wavelengths may differ on different links of a cycle (hence the name “virtual cycles”). Upon a link or node failure, affected demands are rerouted to their preconfigured restoration routes and assigned restoration wavelengths without any knowledge of the precise failure location. When an end-node of a demand fails, the demand is lost and cannot be restored. Referring now to the figures and toFIG. 1in particular, there is shown a flow chart100that describes the present invention.

Step101is prepare input where the input comprises:G(N, A)=A network where N is the set of nodes and A is the set of links. Notation |•| is used to denote the number of elements in a set; e.g., |N| denotes the number of nodes in the network.d=Index for demands; d=1, 2, 3, . . . , where D is the set of all demands. Demand d has end-nodes idand jd.Pd=The working route used by demand d to connect its end-nodes idand jdwhen demand d is not affected by a link or node failure. ∥Pd∥ denotes the length of the working route.Wd=The set of wavelengths required by demand d in its working route; d ε D.H=The set of cycles in network G(N, A). This set is obtained by employing known techniques. The set H needs to be prepared only once for a given network topology and is thereafter used for multiple execution of designing a survivable network for different demand inputs.h=Index for cycles; h ε H.

At step102the demands d ε D are sorted in non-increasing order of the number of wavelengths |Wd| required by the demands.

At step103a demand is selected, say d1, that has not yet been selected from the top of the sorted list of demands. This demand is referred to as the lead demand.

At step104all cycles in the set of cycles H that can restore the lead demand in the event of a link or node failure that affect the lead demand are found. A cycle can restore the lead demand if it has a restoration route on the cycle that connects both end-nodes of the demand and that does not overlap with any intermediate node of the working route of the lead demand. If a demand shares only its two end-nodes with the cycle, it is referred to as straddling demand and it has two restoration routes on the cycle. If the demand can be restored on the cycle, but is non-straddling, it has one restoration route on the cycle. The set of cycles that can restore demand d is denoted as Hd. In particular, Hd1is the set of cycles that can restore the lead demand d1.

At step105the method selects a cycle not yet selected from among the set Hd1.

At step106a large number of Preconfigured Virtual Cycles (PVC's) is generated, each of which may protect multiple demands. Consider the lead demand d1selected in step103and cycle h1selected in step105. The method generates PVC c1by assigning to cycle h1the lead demand and possibly other demands. The following notations are used:c=Index for PVC's; c=1, 2, 3, . . . , where C is the set of all candidate PVC's generated.Dc=The set of demands assigned to PVC c; c ε C. For each of the demands d ε Dc, the working route Pdand the set Wdof wavelengths used on the working route are known from the input.Rdc=The restoration route on PVC c used by demand d to connect its end-nodes idand jdwhen demand d is affected by a link or node failure.Vdc=The set of wavelengths used by demand d in its restoration route on PVC c; d ε Dc. Set Vdcmay differ from Wd, but the number of restoration wavelengths in Vdcis |Vdc|=|Wd|.Sc=Cost of PVC c. This cost is the sum over all links of PVC c of the number of restoration wavelengths on a link multiplied by the cost per wavelength on the link. The cost of a restoration wavelength on a link depends on the link length. Often, but not always, this cost is simply proportional to the link length. Scis readily computed from Rdcand Vdcfor all d ε Dcas this information implies the specific restoration wavelengths assigned on each of the links along the cycle.

Consider lead demand d1and cycle h1selected in step105from among the cycles in set Hd1. The method generates a candidate PVC that would include demand d1and, perhaps, other demands. The resulting PVC is referred to as PVC c1and will be included in the set C of candidate PVC's. PVC c1is characterized by cycle h1, the set Dc1of demands assigned, the restoration routes Rdc1and set of wavelengths Vdc1assigned to each of the demands d ε Dc1, and the “cost” Sc1of the PVC. In addition, PVC c1specifies the demand information, including the working route Pdand the set of wavelengths Wdassigned to each of the demands d ε Dc1.

Generation of the candidate PVC's is the most critical part of the method and will be explained later in detail.

At step107a check is made whether a PVC was generated for each of the cycles in Hd1. If not, the method returns to step105in order to select another cycle. If all cycles in Hd1were selected, the method continues with step108.

At step108one more candidate PVC for demand d1is generated. Specifically, the shortest cycle in Hd1is selected and only demand d1is assigned to that cycle. Selecting this candidate PVC in the final solution is equivalent to providing dedicated restoration capacity to demand d1. Computational results suggest that, typically, it is best to protect some demands through dedicated restoration capacity.

At step109a check is made whether all demands in D were selected in step103. If not, the method returns to103in order to select the next demand in D. If all demands in D were selected, the method completed the generation of the set C of candidate PVC's. It should be noted that the number of candidate PVC's in C is a small fraction of all PVC's that can be generated. Nevertheless, the method is expected to select a subset of PVC's from among those in C which provides protection to all demands at a near-minimum restoration wavelengths cost.

At step110a set of PVC's is selected. First, duplications and dominated PVC's are eliminated from the set C of candidate PVC's. Consider PVC's c1and c2. If Dc1Dc2and Sc1≦Sc2, then PVC c2is deleted from the set C of candidate PVC's. The method then determines an optimal set of PVC's from among those remaining in C so that each of the demands in D is assigned to at least one PVC while minimizing the cost of selected PVC's. This optimization problem is well-known by the name set covering problem and it can be solved by commercially available integer programming solvers (e.g., the CPLEX software by ILOG Inc, an IBM company). These solvers are capable of solving very large set covering problems very fast. Let xc=0, 1 be decision variable where xc=1 if PVC c is selected and xc=0 if it is not selected. Let adc=1 if demand d ε Dcand adc=0 otherwise. The set covering problem is formulated as follows:

The⁢⁢Set⁢⁢Covering⁢⁢ProblemMin⁢∑c∈C⁢Sc⁢xcso⁢⁢that∑c∈C⁢adc⁢xc≥1,⁢∀d∈Dxc=0,1,⁢∀c∈C,
where C* refers to the optimal set of PVC's selected by the solution to the set covering problem.

Some of the demands in D may be assigned to multiple PVC's in C*. At step111demands that are assigned to multiple PVC's are deleted so that each of these demands will be assigned to a single PVC while attempting to maximize the decrease in the cost of the PVC's in C*. This can be achieved through various heuristic algorithms, for example, by deleting one demand from one PVC at a time; specifically, the demand that results in the largest cost decrease. A version of such an algorithm is described below, where DP refers to the set of demands that are assigned to more than one PVC.

Elimination of Duplications AlgorithmInitializationFor each demand d ∈DP,For each PVC c ∈C*,If d ∈Dc, compute the cost reduction in PVC c if demand d isdeleted from c.End.End.Elimination of a demand from a PVCDetermine the demand-PVC combination, referred to as (d*, c*), thatyields the largest cost reduction.Delete demand d* from Dc*.If demand d* is now assigned to only one PVC in C*, delete d* from DP.If DP = Ø, stop. Otherwise, re-compute, for each d ∈DP ∩Dc*, the costreduction in PVC c* if demand d is deleted from c*.Repeat “Elimination of a demand from a PVC”.End of Algorithm.

To reduce computation of the cost reductions at the risk of realizing less saving, it may be reasonable to keep restoration routes and wavelength assignments unchanged. Upon completion, a solution is obtained with C* as the selected set of PVC's, while each of the demands d ε D is assigned to exactly one of these PVC's.

At this point, in step112a near-optimal solution is determined comprising a set C* of PVC's where each of the demands d ε D is assigned to a single PVC c ε C*. Consider a specific demand d1assigned to PVC c1. Demand d1is characterized by its working route Pd1and the set of wavelengths Wd1the demand uses on the working route. Demand d1has restoration route Rd1c1on PVC c1. This restoration route uses the set Vd1c1of restoration wavelengths. The wavelengths assigned during the generation and selection of the PVC's ignored (i) possible conflicts between wavelengths assigned to working demands and those assigned to restoration routes, and (ii) possible conflicts between restoration wavelengths assigned in different PVC's. Consider PVC's c1and c2, and suppose demand d1is assigned to PVC c1whereas demand d2is assigned to PVC c2. Furthermore, suppose demands d1and d2have common failure scenarios and their restoration routes on PVC's c1and c2share one or more links. Then, if both demands fail, and their restoration wavelengths are overlapping, a conflict will arise.

The method provides an algorithm that guarantees that no wavelength conflicts will occur upon a link or node failure while attempting to minimize the overall number of different wavelengths used for restoration in the network. LetNVc=Number of different restoration wavelengths used in PVC c.RRc=Set of restoration routes in PVC c.r, p=Indices for restoration routes in RRc.d(r)=The demand associate with restoration route r.Ic1c2=1 if PVC's c1and c2have joint links and if there is a demand in Dc1that has a common failure scenario with a demand in Dc2.

Wavelengths Reassignment AlgorithmSort the PVC's in C* in non-increasing order of NVc.While not all PVC's in C* are marked,Select from top of the list an unmarked PVC, say c1.Find set Sc1= {all marked PVC's c ∈C* for which Ic1c= 1 }.For each link m of PVC c1, construct set Qm= {wavelengths that cannot be usedby restoration routes of PVC c1on link m}. Forbidden wavelengths include thosethat: (i) are taken by some working route that uses link m, and (ii) are taken by somerestoration route of a PVC in Sc1that uses link m.If Qm= Ø for all links m of PVC c1, mark PVC c1without changing the assignedwavelengths of all restoration routes in RRc1and go to “End—2”.Sort restoration routes in RRc1in non-increasing order of (i) number of wavelengthsrequired by the route, and (ii) number of links in the route.While not all restoration routes in RRc1are selected,Select route r from top of the list. Note that route r is the restoration route ofdemand d(r) and it requires |Wd(r)| wavelengths.Find the wavelengths that cannot be used by route r. These include: (i) union ofall wavelengths in Qmfor all links m included in route r, and (ii) wavelengthsused by a previously selected route p ∈RRc1that has a common link with route rand d(r) and d(p) have a common failure scenario.Assign to route r the lowest |Wd(r)| wavelengths that can be assigned.End_1.End_2.End of Algorithm.

A simpler algorithm can be used wherein each PVC is reduced to a node in a graph and a link connects nodes c1and c2if Ic1c2=1. Node c1requires NVc1restoration wavelengths, while adjacent nodes would have non-overlapping wavelength numbers (and a node cannot use wavelengths used by working routes that pass through links of the PVC represented by the node). Reassignment of wavelengths is then accomplished by solving a simplified version of the wavelengths reassignment algorithm described above. The solution may, though, require more restoration wavelengths.

At step113the network design is complete and protects all demands from any single link or node failure using preconfigured virtual cycles. The solution comprises the set C* of selected PVC's. For each PVC c ε C*, the method specifies the set of assigned demands Dc, where each demand is assigned to a single PVC in C*. For each of the demands, the method specifies its assigned restoration route and assigned restoration wavelengths. For example, consider demand d1assigned to PVC c1, where demand d1is characterized by its working route Pd1and the set Wd1of wavelengths the demand uses on the working route. The method specifies demand d1's restoration route Rd1c1on PVC c1and the set Vd1c1of restoration wavelengths assigned to demand d1on its assigned restoration route.

PVC c1is generated by assigning lead demand d1and, perhaps, other demands to cycle h1. The cost Sc1of PVC c1is the sum over all links of PVC c1of the number of restoration wavelengths on a link multiplied by the length of the link, and is readily computed from the restoration routes and restoration wavelengths assigned to the demands in Dc1. The recorded design results in step113are incorporated into the network design to protect the network from a single link or node failure.

The discussion below explains how the method generates a PVC as stated in step106ofFIG. 1.

Referring now toFIG. 2, there is shown an example200of a single PVC and the demands assigned. Nodes201to210and the links (identified by the end-nodes) that interconnect these nodes (201,202), (202,203), . . . , (209,210), (210,201) specifies the restoration cycle under consideration. In addition, the figure shows several other nodes211-214and several other links that are not on the restoration cycle. The figure shows working routes of seven demands215-221and the number of wavelengths required by each (the specific wavelengths used on the working routes are not required here, but were required by the wavelengths reassignment algorithm in order to resolve wavelength conflicts). For example demand215is a connection between nodes204and209, its working route includes links (204,213) and (213,209), and it requires two wavelengths.

Consider the generate PVC in step106inFIG. 1for the cycle presented inFIG. 2with demand215as the lead demand. The following illustrates the generation of the corresponding PVC. The method sorts the demands in a non-increasing order of the required number of wavelengths. The sorted list is not necessarily unique, but the lead demand must be the first on the list (no demands with more wavelengths than the lead demand would be assigned to this cycle). Suppose the sorted list is demands215,216,217,218,219,220,221. Demand215is assigned restoration wavelengths1and2on, as yet, an undetermined restoration route (since it is a straddling demand, there are two alternatives). Next, since demand216has no common failure scenario with demand215(also referred to as disjoint demands), it is assigned restoration wavelengths1and2on an undetermined restoration route. Next, since demand217has no common failure scenario with previously assigned demands, it is assigned restoration wavelength1on restoration route (208,209), (209,210), . . . , (205,206). Note that demand217is non-straddling and, thus, has a unique restoration route on the cycle. Next, since demand218has no common failure scenario with previously assigned demands, it is assigned restoration wavelength1on restoration route (201,202), (202,203), . . . , (208,209). Next, since demand219has no common failure scenario with previously assigned demands, it is assigned restoration wavelength1on an undetermined restoration route. Next, demand220has a common failure scenario with demand215, but these two demands can be assigned non-overlapping restoration routes. Therefore, demand220is assigned restoration wavelength1on restoration route (205,206), (206,207), (207,208), and the restoration route of demand215is fixed as (209,210), (210,201), (201,202), (202,203), (203,204). Next demand221has a common failure scenario with demand219and their restoration routes overlap. However, since demand215has no common failure with demand221, it was already assigned restoration wavelengths1and2and its restoration route covers an entire restoration route of demand221, demand221can be assigned restoration wavelength2on restoration route (209,210), (210,201), (201,202) without using any new restoration wavelengths along its restoration route. Demand221is referred to as being “shadowed” by demand215. If demand221could not be shadowed by a previously assigned demand, it would not be assigned to this PVC.

Note that only demands216and219remain with an undetermined restoration route. The method then assigns restoration route (202,203), (203,204) to demand216and restoration route (210,201), (201,202), (202,203) to demand219. It can now readily be seen that this PVC has two restoration wavelengths on links (209,210), (210,201), (201,202), (202,203), (203,204) and a single restoration wavelength on links (204,205), (205,206), (206,207), (207,208), (208,209) in order to protect the seven assigned demands from any single link or node failure.

The description below further explains the generation of a PVC. Consider lead demand d1and a specific cycle h1ε Hd1. The method generates PVC c1that will provide restoration to d1and, perhaps, to other demands. Let Lh1d1be the set of all demands d ε D that can be protected under link or node failure by cycle h1and that do not require more wavelengths than d1. Limiting the demands considered for sharing in this way is justified since each demand will serve as the lead demand. In addition to the lead demand, the method considers assigning demands, one at a time, to cycle h1, generating PVC c1under the following rules:(a) A demand whose working route does not have a joint failure scenario with any previously assigned demand (end-nodes may be shared).(b) A demand whose working route has common failure scenarios with previously assigned demands, but it has a restoration route that is non-overlapping with a restoration route of each of these demands.(c) A demand whose working route has common failure scenarios and overlapping restoration routes with previously assigned demands, but it can share restoration wavelengths with a previously assigned demand with which it does not have common failure scenarios.

Rule (c) is illustrated again throughFIG. 2. Suppose demand215was already assigned wavelengths1and2on restoration route (209,210), (210,201), (201,202), (202,203) and (203,204), and demand219was already assigned wavelength1. Demand221can be assigned wavelength2“for free” since demand215has a restoration route that covers a restoration route of demand221and these two demands have no common failure scenario. Demand215is referred to as a “shadowing demand” and demand221is referred to as a “shadowed demand”.

The method provides a heuristic algorithm that generates PVC c1for lead demand d1on cycle h1. The algorithm consists of three parts executed sequentially:Demand Assignment Algorithm;Demand Routing Algorithm; andDrop Demands Algorithm.

In the version described below, the algorithm first assigns, one at a time, demands that satisfy rules (a) or (b). Thereafter, when no more demands can be assigned by these rules, it attempts to assign, one at a time, unassigned demands by rule (c); note that the latter assignments do not lead to an increase in the restoration capacity since the restoration route of a demand assigned by rule (c) is shadowed by another demand along its entire restoration route. Note that the demands assigned may depend on the order in which they are processed. Similar variants of demand assignments can be used, for instance, attempting to assign each of the demands, one at a time, based on rules (a), (b) and (c). The Demand Assignments Algorithm, described below, generates PVC c1associated with lead demand d1and cycle h1.

Demand Assignment AlgorithmInitializationDetermine set Lh1d1, where the demands in Lh1d1are sorted in non-increasing order of thenumber of required wavelengths. Let demand d1be at the top of the list.Initialize M = Ø.Assignment of Demands [Rules (a) and (b)]While there are unselected demands in Lh1d1,Select from top of the list demand d that was not yet selected (selecting demands in thisorder will, in general, yield better results; however, other selection rules, such as randomselection can be used).If d does not share a common failure scenario with any of the previously assigneddemands to PVC c1, then, assign demand d to PVC c1with restoration wavelengths Vdc1={1, 2, ..., |Wd|}. If d is non-straddling, fix its restoration route Rdc1(it is unique);otherwise, if d is straddling, leave its restoration route undetermined.If d was assigned, go to select next demand on the list; otherwise continue.Suppose d shares a common failure scenario with at least one of the previously assigneddemands to PVC c1. Then,(a)If these previously assigned demands and d can be routed so that d's restorationroute does not overlap with a restoration route of these previously assigneddemands, then: Assign demand d to PVC c1with restoration wavelengths Vdc1={1, 2, ..., |Wd|} and fix the routes of these demands (unless already fixed) and ofd.(b)If d was not assigned, place d in a list M.End.Assignment of Demands [Rule (c)]While there are unselected demands in list M,Note: M is already sorted like Lh1d1.Select from top of the list demand d that was not yet selected.Suppose d has common failure scenarios with a set S of previously assigned demands toPVC c1.(a)Find the set of all wavelengths that do not exceed | Wd1| and that are notassigned to any of the demands in S whose fixed (or shorter if not fixed)restoration route overlaps the shorter restoration route of d (in case of a tie,select arbitrarily). Let K denote the set of these wavelengths. If K includes lessthan |Wd| wavelengths, demand d is not assigned and the algorithm proceedswith next demand in M.(b)Find all previously assigned demands that shadow demand d. Demand eshadows d if it satisfies the following conditions: (i) Its restoration wavelengthsinclude at least |Wd| wavelengths that are also in K; (ii) it does not sharecommon failure scenarios with d; and (iii) the shorter restoration route of d isin e's fixed (or shorter if not fixed) restoration route. If no shadowing demandsexist, demand d is not assigned and the algorithm proceeds with the nextdemand in M.(c)Select a shadowing demand, say, demand e (first priority should be given to ademand whose routing has already been fixed), assign demand d to PVC c1andfix the routing of all the demands not yet fixed in S′ ∪ {d } ∪ {e} to theirshorter routes (where S′ includes the demands in S whose shorter restorationroute does not overlap with the selected restoration route of d). Assign d thelowest |Wd| restoration wavelengths in K that are also used by demand e.End.End of Algorithm.

During the assignment algorithm, some of the straddling demands assigned by rule (a) may not have their restoration route fixed. Note that in the assignment procedure for demands in the set M, the algorithm enforced the use of the shortest restoration routes for some of the demands involved (unless the routes were already fixed) in order to limit the search while still achieving effective use of restoration capacity. Alternatively, the algorithm may search for a combination of restoration routes that would facilitate shadowing at the expense of additional computational effort. Note that the presentation above ignores possible wavelength conflicts with wavelengths of working routes or with restoration wavelengths in other PVC's. Wavelength conflicts are resolved in step112ofFIG. 1.

Next, the method provides a routing algorithm that fixes restoration routes that have not yet been fixed on PVC c1. Since all demands with undetermined routes are disjoint with no common failure scenario, it can be shown that it is optimal to fix their restoration routes so that there is some link on cycle h1that does not carry any of these restoration routes. Let Q be the set of all demands assigned to PVC c1whose restoration routes have not been fixed, and let ENQ be the set of end-nodes of the demands with undetermined restoration routes. The routing Algorithm is described below for PVC c1.

Routing AlgorithmFor each end-node in set ENQ,Consider end-node i. Determine restoration route for each of thedemands in Q that avoids the link that is clockwise from node i oncycle h1.Evaluate the total restoration capacity on PVC c1reserved under therouting above for all assigned demands (including those fixed duringthe demand assignment algorithm).End.Select the minimum-cost solution and fix the restoration routes of all thedemands in Q accordingly.End of Algorithm.

At this point, the method assigned a set of demands to PVC c1. Each of these demands was assigned restoration wavelengths and a restoration route. However, it may be the case that deleting some of these demands from this PVC may lead to a better overall set of candidates. In principle, exchanges of demands among candidate PVC's can be explored, however, this approach may require significant computational effort. Instead, a more narrow search can be used to delete a demand from a PVC if the decrease in restoration capacity in the PVC exceeds the restoration capacity used by a PVC that provides dedicated restoration to that demand. Let Δc1be the set of demands assigned to PVC c1. A version of a heuristic for dropping demands from a PVC, referred to as Drop Demand Algorithm, is presented below for PVC c1. Other variants can obviously be used.

Drop Demands AlgorithmSort the demands in Δc1in non-increasing order of their restoration routelength multiplied by the number of wavelengths required by the demand.For each demand d ∈Δc1,Compute the cost reduction of PVC c1if demand d is deleted.(Computation of the objective function can be simplified by keepingrestoration routes and wavelength assignments unchanged at the riskof underestimating the savings.)Compute the savings relative to protecting this demand by theleast-cost PVC that provides dedicated restoration to demand d.If the savings is positive, drop the demand from PVC c1.End.End of Algorithm.

This completes the detailed description of generating PVC c1, as noted in step106ofFIG. 1.

The present invention can readily be modified to handle the case when restoration routes of each of the demands can be split among multiple restoration routes. While generating candidate PVC's, each demand is assumed to require only one wavelength. Hence, the demand assignment algorithm is simplified since rule (c) does not apply. In the solution to the set covering problem used for selecting an optimal set of PVC's, each of the cycles may be selected multiple times so that each of the demands d ε D will be assigned at least |Wd| times. As a result, each demand may be assigned to different selected PVC's with one or more wavelength on each of these PVC's, and restoration wavelengths of a straddling demand may be split between the two restoration routes on the same PVC.

Various aspects of the present disclosure may be embodied as a program, software, or computer instructions embodied in a computer or machine usable or readable medium, which causes the computer or machine to perform the steps of the method when executed on the computer, processor, and/or machine.

The system and method of the present disclosure may be implemented and run on a general-purpose computer or computer system. The computer system may be any type of known or will be known systems and may typically include a processor, memory device, a storage device, input/output devices, internal buses, and/or a communications interface for communicating with other computer systems in conjunction with communication hardware and software, etc. A module may be a component of a device, software, program, or system that implements some “functionality”, which can be embodied as software, hardware, firmware, electronic circuitry, or etc.

While there has been described and illustrated a method for network restoration under link or node failure using preconfigured virtual cycles, it will be apparent to those skilled in the art that modifications and variations are possible without deviating from the principles and broad teachings of the present invention which shall be limited solely by the scope of the claims appended hereto.