Method for stochastic selection of improved cost metric backup paths in shared-mesh protection networks
First Claim
Patent Images
1. A method of selecting paths comprising the steps of:
- a) computing a plurality of first shortest paths from a source point to a destination point each including of a serial chain of at least one communications link;
b) selecting K first shortest paths from the plurality;
c) ordering the selected K first shortest paths from shortest to longest;
d) for each first shortest path of K, i) computing the cost of the first shortest path as substantially equal to the combined cost of the links included in the first shortest path;
ii) selecting a lowest estimated cost second shortest path from the remainder of the elements of K, where the estimated cost of the second shortest path is computed as substantially equal to the combined estimated cost of the links included in the second shortest path and the cost of a link corresponds to the cost of using the link scaled by a probability that the link can be shared by the second shortest path and a path already provisioned using a channel of the link;
e) selecting the lowest estimated combined cost first and second shortest path pair.
3 Assignments
0 Petitions
Accused Products
Abstract
A method of path selection in shared-mesh restoration networks that results in efficient use of network resources, using only the network state information available locally at each network element. The method uses probability theory to develop an estimate of protection channel sharing opportunities and encourages sharing of protection channels if possible
29 Citations
19 Claims
-
1. A method of selecting paths comprising the steps of:
-
a) computing a plurality of first shortest paths from a source point to a destination point each including of a serial chain of at least one communications link;
b) selecting K first shortest paths from the plurality;
c) ordering the selected K first shortest paths from shortest to longest;
d) for each first shortest path of K, i) computing the cost of the first shortest path as substantially equal to the combined cost of the links included in the first shortest path;
ii) selecting a lowest estimated cost second shortest path from the remainder of the elements of K, where the estimated cost of the second shortest path is computed as substantially equal to the combined estimated cost of the links included in the second shortest path and the cost of a link corresponds to the cost of using the link scaled by a probability that the link can be shared by the second shortest path and a path already provisioned using a channel of the link;
e) selecting the lowest estimated combined cost first and second shortest path pair. - View Dependent Claims (2, 3, 4)
-
-
5. A method of selecting paths comprising the steps of:
-
a) creating a first graph representing a network having a topology containing network elements interconnected by communications links wherein each network element is represented by a vertex and each communication link interconnecting adjacent network elements is represented by an edge, the first graph containing a source vertex corresponding to an ingress network element and a destination vertex corresponding to an egress network element;
b) using the first graph to calculate a plurality of paths between the source and destination vertices;
c) selecting K first shortest paths between source vertex and destination vertex;
d) for each first shortest path;
i) computing the cost of the first shortest path;
ii) creating a second graph substantially based on the first graph wherein the second graph includes edges and estimated edge costs and an edge associated with the first shortest path is modified from the first graph;
iii) selecting a lowest estimated cost second shortest path from source vertex to destination vertex from the second graph wherein the estimated cost of the second shortest path is substantially equal to the combined estimated costs of the edges comprising the second shortest path and the estimated cost of an edge corresponds to the cost of using the edge scaled a probability that the edge can be shared by the second shortest path and a path already provisioned using a channel of the edge;
e) selecting the lowest estimated combined cost first and second shortest path pair. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12)
-
-
13. A shared mesh protection network wherein paths are provisioned according to a method comprising;
-
a) generating a list of at least one candidate pair of paths including one primary path and one associated backup path between a source network element and a destination network element;
b) selecting a lowest estimated path pair from the list where the cost of the primary path is substantially equal to the cost of the network resources included in the primary path and the estimated cost of a backup path corresponds to the cost of the network resources included in the backup path scaled by the probability that existing network resources can be shared by the backup path;
c) using signaling to attempt to establish the selected path pair;
d) eliminating the selected path pair from the list if it can not be established and attempting to establish a new lowest estimated cost path pair;
e) returning an error signal to a network operator if no candidate path pair from the list can be allocated. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
Specification