Method of providing restoration routes in a mesh network

• US 6,856,592 B2
• Filed: 03/15/2001
• Issued: 02/15/2005
• Est. Priority Date: 03/15/2001
• Status: Expired due to Term

• Current Assignee: Ciena Corporation, Ciena Luxembourg S.a.r.l. (Ciena Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Bach, Thuthuy, Grover, Wayne D., Doucette, John
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US09/808,173
• Publication Number:
  US 20020181393A1
• Time in Patent Office: 1,433 Days
• Field of Search: 370/216, 370/238, 370/254, 370/468, 370/225, 370/222, 370/406, 714/4, 707/104, 707/218, 707/220, 707/250, 340/2.1
• US Class Current: 370/216
• CPC Class Codes: H04J 14/0227 Operation, administration, maintenance or provisioning [OAMP] of WDM networks, e.g. media access, routing or wavelength allocation
• CPC Class Codes: H04J 14/0241 Wavelength allocation for communications one-to-one, e.g. unicasting wavelengths
• CPC Class Codes: H04J 14/0284 WDM mesh architectures
• CPC Class Codes: H04L 1/22 using redundant apparatus to increase reliability
• CPC Class Codes: H04L 41/0663 Performing the actions predefined by failover planning, e.g. switching to standby network elements

Abstract

A method of providing restoration routes for protecting traffic in a mesh network is described. The method comprises the steps of generating a set of eligible restoration routes for each span in the network, establishing a bi-criteria objective function in terms of route length and capacity cost for selecting a set of restoration routes, and selecting a set of restoration routes for each span from the eligible restoration routes in dependence upon the bi-criteria objective function. Embodiments of the invention may be useful for shortening the lengths, in terms of hops, of existing restoration routes in a mesh-restorable network and in some cases with negligible spare capacity penalty.

Claims

1. A method of determining restoration routes in a mesh network, the network comprising a plurality of network nodes Interconnected by spans and each span having a predetermined amount of working capacity, the method comprising the steps of:

a) generating a set of eligible restoration routes for each span in the network;

b) establishing a bi-criteria objective function in terms of route length and capacity cost for selecting a set of restoration routes; and

c) selecting a set of restoration routes for each span from the eligible restoration routes in dependence upon the bi-criteria objective function wherein the step (c) of selecting a set of restoration routes comprises;

determining an initial value of an intermediary variable in the bi-criteria objective function for identifying combinations of capacity and length of restoration routes to be selected;

selecting the restoration routes for each span according to the bi-criteria objective function; and

adjusting the value of the intermediary variable and repeating the selection of restoration routes for each span according to the adjusted bi-criteria objective function until a final value of the intermediary variable is reached.

2. The method of claim 1 wherein the final value of the intermediary variable is reached when further decreases in the average restoration route length require additional capacity on any one of the spans.

3. The method of claim 1 wherein the final value of the intermediary variable is reached when a knee in a plot of spare capacity cost in the spans versus the average restoration route length is reached.

4. The method of claim 1 wherein the final value of the intermediary variable is reached when an asymptote in a plot of spare capacity cost in the spans versus the average restoration route length is reached.

5. A method of determining network span capacity required for traffic protection in a mesh network comprising:

a) establishing a model describing the network including the interconnection of network nodes and spans, the cost of bandwidth capacity on each span, and the capacity demand between network nodes;

b) determining a working capacity placement on each span;

c) establishing a bi-criteria objective function in terms of route length and span capacity cost;

d) selecting a set of restoration routes for each span in dependence upon the bi-criteria objective function and the model; and

e) determining an amount of spare capacity, additional to the working capacity, required for each span in accordance with the selected set of restoration routes.

6. The method of claim 5 wherein the step (d) of selecting a set of restoration routes comprises:

determining an initial value of an intermediary variable in the bi-criteria objective function for identifying combinations of capacity and length of restoration routes to be selected;

selecting the restoration routes for each span according to the bi-criteria objective function; and

adjusting the value of the intermediary variable and repeating the selection of restoration routes for each span according to the adjusted bi-criteria objective function until a final value of the intermediary variable is reached.

7. The method of claim 6 wherein the final value of the intermediary variable is reached when further decreases in the average restoration route length require additional capacity on any one of the spans.

8. The method of claim 6 wherein the final value of the intermediary variable is reached when a knee in a plot of spare capacity cost in the spans versus the average restoration route length is reached.

9. The method of claim 6 wherein the final value of the intermediary variable is reached when an asymptote in a plot of spare capacity cost in the spans versus the average restoration route length is reached.

10. A method of providing restoration routes in a mesh network, the network comprising a plurality of network nodes interconnected by spans and having a protection routing control function, the method comprising the steps of:

a) establishing a model describing the network;

b) determining a working capacity placement on each span;

c) generating a set of eligible restoration routes for each span in the network;

d) establishing a bi-criteria objective function in terms of route length and capacity cost for selecting a set of restoration routes from the eligible restoration routes for each span;

e) selecting a set of restoration routes for each span in dependence upon the bi-criteria objective function;

f) determining an amount of spare capacity required for each span in accordance with the set of restoration routes selected for the span;

g) adapting the network to provide the spare capacity required for each span; and

h) communicating the set of restoration routes selected for each span to the protection routing control function in the network.

11. The method of claim 10 wherein the step (a) of establishing a model comprises:

establishing the interconnection of network nodes and spans;

determining the cost of capacity of each span of the network; and

determining the capacity demand between the network nodes.

12. The method of claim 11 wherein the step (e) of selecting a set of restoration routes comprises:

determining an initial value of an intermediary variable in the bi-criteria objective function for identifying combinations of capacity and length of restoration routes to be selected;

selecting the restoration routes for each span according to the bi-criteria objective function; and

adjusting the value of the intermediary variable and repeating the selection of restoration routes for each span according to the adjusted bi-criteria objective function until a final value of the intermediary variable is reached.

13. A method of providing network span capacity required for traffic protection in a mesh network comprising;

a) establishing a model describing the network including the interconnection of network nodes and spans, the cost of bandwidth capacity on each span, and the capacity demand between network nodes;

b) determining a working capacity placement on each span;

c) establishing a bi-criteria objective function in terms of route length and span capacity cost;

d) selecting a set of restoration routes for each span in dependence upon the bi-criteria objective function and the model; and

e) determining an amount of spare capacity, additional to the working capacity, required for each span in accordance with the selected set of restoration routes; and

f) adapting the network to provide the spare capacity required for each span.