Method and apparatus for provisioning a hop limited protection pathway in a network
View Patent ↗Method and apparatus for provisioning a protection pathway of a link joining a first point in a network and a second point in the network. The method includes the step of determining a shortest path between the first point and the second point in a protection graph, computing a length of said shortest path, determining if said link should be added to the protection graph according to said computed length and setting the shortest path in the protection graph as protection path for said link. The second step of determining includes evaluating the protection graph to determine if there no existing path or an existing path that is longer than a hop limit. Based on this evaluation, the method either adds the link or makes no change to the protection graph.
1. A non-transitory computer readable medium, wherein computer instructions, when processed by a computer, adapt the operation of the computer to perform the steps for provisioning hop-limited protection paths in a network having a plurality of nodes interconnected by a plurality of links, comprising:
dividing each of the plurality of links into a plurality of parallel sublinks to create a plurality of subnetworks, wherein each of the plurality of subnetworks includes the plurality of nodes interconnected by a plurality of subnetwork links, wherein of the plurality of subnetwork links comprises one or more of a respective plurality of parallel sublinks;
sorting sublinks in a subnetwork of the plurality of subnetworks;
wherein the sublinks are sorted according to the ratio:
u
(
e
ij
)
+
w
′
(
e
i
)
u
(
e
ij
)
+
u
′
(
e
i
)
where:
e i represents a link,
e ij represents a sublink of the link e i ,
u represents total link capacity,
u′ represents total capacities of the links previously considered, and
w′ represents total working capacity previously considered.
2. The non-transitory computer readable medium of claim 1 , wherein the computing spanner comprises:
for each subnetwork:
determining a shortest path in the spanner within the subnetwork between a first point and the a second point, wherein the first point and the second point define a subnetwork link;
computing a length of the shortest path; and
evaluating the computed length to determine whether the subnetwork link should be added to the spanner.
3. The non-transitory computer readable medium of claim 2 , wherein the sublinks are sorted according to link capacity.
4. A non-transitory computer readable medium containing a program which, when executed, performs the steps of provisioning a hop-limited protection paths in a network having a plurality of nodes interconnected by a plurality of links, comprising:
dividing each of the plurality of links into a plurality of parallel sublinks to create a plurality of subnetworks;
sorting the sublinks of each subnetwork;
determining a shortest path in a protection graph between a first point and a second point, wherein the first point and the second point are joined by a link of the network;
computing a length of the shortest path between the first point and the second point in the protection graph; and
evaluating the computed length of the shortest path by comparing the computed length with a hop limit to determine whether the link should be added to the protection graph;
wherein the link is added to the protection graph if there is no path between the first point and the second point in the protection graph or the computed length is longer than the hop limit.
5. The computer readable medium of claim 4 , wherein the shortest path in the protection graph is set as a protection path for the link if the computed length is shorter than or the same as the hop limit.
6. The computer readable medium of claim 4 , wherein the sublinks of each subnetwork are sorted according to the ratio:
u
(
e
ij
)
+
w
′
(
e
i
)
u
(
e
ij
)
+
u
′
(
e
i
)
where:
e i represents a link,
e ij represents a sublink of the link e i ,
u represents total link capacity,
u′ represents total capacities of the links previously considered and
w′ represents total working capacity previously considered.
7. An apparatus for provisioning a protection path of a link joining a first point in a network and a second point in the network, the apparatus comprising:
means for dividing each of the plurality of links into a plurality of parallel sublinks to create a plurality of subnetworks;
means for sorting the sublinks of each subnetwork;
means for determining a shortest path between the first point and the second point in a protection graph;
means for computing a length of the shortest path;
means for evaluating the length of the shortest path to determine whether the link should be added to the protection graph; and
means for setting the shortest path in the protection graph as the protection path for the link;
means for dividing links of the network into a plurality of parallel sublinks to create a plurality of subnetworks.
8. The apparatus of claim 7 , wherein the means for evaluating further comprise:
means for determining if a path between the first point and the second point in the protection graph exists, or if the computed length is longer than the hop limit.
9. The apparatus of claim 7 , wherein the sublinks are sorted according to the ratio:
u
(
e
ij
)
+
w
′
(
e
i
)
u
(
e
ij
)
+
u
′
(
e
i
)
where:
e i represents a link,
e ij represents a sublink of the link e i ,
u represents total link capacity,
u′ represents total capacities of the links previously considered, and
w′ represents total working capacity previously considered.
10. A non-transitory computer readable medium, wherein computer instructions, when processed by a computer, adapt the operation of the computer to perform the steps for provisioning a hop-limited protection path in a network having a plurality of nodes interconnected by a plurality of links, comprising:
dividing a number of links in the network into a plurality of parallel links to define thereby a plurality of subnetworks;
sorting the sublinks of each subnetwork;
for each subnetwork, determining a shortest path between first and second points in a protection graph associated with the subnetwork by evaluating each of the plurality of parallel links forming the subnetwork and updating the protection graph associated with the subnetwork in response to the shortest path length information; and
adapting the hop-limited protection path according to the protection graph of the shortest hop subnetwork exhibiting sufficient capacity.
11. The non-transitory computer readable medium of claim 10 , further comprising:
computing a length of the shortest path between the first point and the second point in the protection graph; and
evaluating the computed length of the shortest path to determine whether the link should be added to the protection graph.
12. The non-transitory computer readable medium of claim 10 , further comprising sorting each link in each subnetwork according to the link capacity, said determining being a shortest path for each subnetwork performed according to a capacity sorted link order.
13. The non-transitory computer readable medium of claim 10 , wherein the evaluating comprises: comparing the computed length of the shortest path with a hop limit.
14. The non-transitory computer readable medium of claim 13 , wherein the link is added to the protection graph if there is no path between the first point and the second point in the protection graph or the computed length is longer than the hop limit.
15. The non-transitory computer readable medium of claim 13 , wherein if the computed length is shorter than or the same as the hop limit, the shortest path in the protection graph is set as a protection path for the link.