Methods and apparatus for selecting multiple paths taking into account shared risk

• US 20020191545A1
• Filed: 06/14/2001
• Published: 12/19/2002
• Est. Priority Date: 06/14/2001
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Ar Card
• Inventors: Pieda, Peter Steven, Carpini, Walter Joseph
• Granted Patent: US 6,882,627 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

Methods, systems, computer readable media are provided which facilitate the selection of multiple paths through a network represented by a network topology which take into account shared risk which may exist between network resources. The method involves identifying a first path through the network topology from a source node to a destination node, the first path comprising a first sequence of network resources. For at least one shared risk group, a determination is made if any of the at least one shared risk group includes any of the first sequence of network resources, a shared risk group being a group of network resources within the network topology which have a shared risk. A topology transformation is performed of the network topology into a virtual topology which discourages the use of network resources in any shared risk group determined. A second path through the virtual topology is identified from the source node to the destination. The method may be adapted to encourage node and/or edge disjointness.

Claims

1. A method of selecting multiple paths through a network represented by a network topology representing an interconnected set of network resources, the method comprising:

a) identifying a first path through the network topology from a source node to a destination node, the first path comprising a first sequence of network resources;

b) for at least one shared risk group, determining if any of the at least one shared risk group includes any of the first sequence of network resources, a shared risk group being a group of network resources within the network topology which have a shared risk;

c) performing a SRG (shared risk group) topology transformation of the network topology into a virtual topology which discourages the use of network resources in any shared risk group determined in step b);

d) identifying a second path through the virtual topology from the source node to the destination node, the second path comprising a second sequence of network resources.

2. A method according to claim 1 wherein the network resources comprise nodes and links.

3. A method according to claim 1 wherein each said at least one shared risk group comprises a respective group of nodes.

4. A method according to claim 3 wherein performing the SRG topology transformation on the network topology comprises, for each node requiring SRG transformation:

transforming the node requiring transformation into two interconnected nodes;

providing a forward unidirectional link between the two interconnected nodes, and assigning the forward unidirectional link a cost;

transforming any bi-directional link into the node requiring transformation into a first unidirectional link into one of the two interconnected nodes, and a second unidirectional link out of the other of the two interconnected nodes.

5. A method according to claim 4 wherein the cost assigned to each forward unidirectional link is greater than a sum of costs for all links in the network topology.

6. A method according to claim 4 further comprising performing a ND (node-disjointness) transformation of every node in the first path other than the source node and the destination node.

7. A method according to claim 6 wherein the ND transformation of a node which has not been SRG transformed comprises transforming the node into a respective interconnected pair of nodes, and providing for each such pair of nodes a respective forward unidirectional link and a respective reverse unidirectional link between the pair of nodes, the forward unidirectional link being assigned a cost to encourage node disjointness.

8. A method according to claim 7 wherein each said respective reverse unidirectional link is assigned a cost of zero.

9. A method according to claim 7 wherein the ND transformation of a node which has been SRG transformed comprises providing a zero-cost reverse unidirectional link between the pair of interconnected nodes into which the node was SRG transformed, and increasing a cost assigned to the forward unidirectional link between the pair of interconnected costs to encourage node disjointness.

10. A method according to claim 1 wherein each said at least one shared risk group comprises a respective group of links.

11. A method according to claim 10 wherein performing a SRG topology transformation on the network topology comprises:

for each link requiring transformation, transforming the link requiring transformation into a forward unidirectional link and a reverse unidirectional link each having a respective cost.

12. A method according to claim 11 wherein for each unidirectional link, a respective cost is assigned which is larger than a sum of the costs assigned to all links in the topology.

13. A method according to claim 12 wherein a larger cost is assigned to unidirectional links which form part of the first path than for forward unidirectional links which do not form part of the first path.

14. A method according to claim 11 wherein an additional cost is added to each forward unidirectional link which forms part of the first path, and wherein a cost assigned to each reverse unidirectional link which forms part of the first path is equal to negative the original cost for the link, so as to encourage edge disjointness.

15. A method according to claim 14 wherein the cost assigned to each reverse unidirectional link which does not form part of the first path is equal to that assigned to the corresponding forward unidirectional link.

16. A method according to claim 14 wherein the cost assigned to each forward unidirectional link is equal to the original cost plus a first constant value if the forward link is part of the first path, plus a second constant if the forward link is part of a shared risk group determined in step b).

17. A method according to claim 11 wherein the cost assigned to each forward unidirectional link is greater than a sum of costs for all links in the network topology.

18. A method according to claim 2 the shared risk groups comprises at least one shared risk group of nodes, and at least one shared risk group of links.

19. A method according to claim 18 wherein performing a topological transformation on the network topology comprises:

a) for each node requiring SRG transformation;

transforming the node requiring transformation into two interconnected nodes;

providing a forward unidirectional link between the two interconnected nodes, and assigning the forward unidirectional link a cost;

transforming any bi-directional link into the node requiring transformation into a first unidirectional link into one of the two interconnected nodes, and a second unidirectional link out of the other of the two interconnected nodes;

b) for each link requiring SRG transformation;

increasing a cost associated with the link requiring transformation by a first amount if the link requiring transformation is part of the first path, and by a second smaller amount if the link requiring transformation is not part of the first path.

20. A method according to claim 1 further comprising:

identifying if there are any unnecessary shared links between the first and second path;

in the event there are unnecessary shared links between the first and second paths, performing a path coalescence to eliminate the unnecessary shared links.

21. A method according to claim 20 wherein performing a path coalescence to eliminate the unnecessary shared links comprises:

forming a set containing all links of the first and second path;

forming a new first path by selecting a link from the set starting at the source node and ending at a subsequent node;

for a sequence of subsequent nodes, selecting a link from the set starting at the subsequent node and ending at another subsequent node, until the another subsequent node is the destination node;

forming a new second path from links in the set remaining after the formation of the first path.

22. A method according to claim 1 further comprising:

in the event at least two paths cannot be found which do not share at least one resource having shared risks, revising the at least one shared risk group to be less restrictive and then re-executing steps b) through d).

23. A method according to claim 22 further comprising:

defining a hierarchy of resources, the hierarchy having a plurality of levels, with resources assigned to a given level in the hierarchy being contained by a resource assigned to a higher level in the hierarchy, wherein a shared risk between any two resources in a lower level of the hierarchy is also considered a shared risk between any pair of resources in a higher level of the hierarchy which contain the two resources of the lower level of the hierarchy;

wherein a first attempt is made to define first and second paths which do not share any risk at the highest level of the hierarchy of resources;

upon failure of the first attempt, at least one subsequent attempt is made to define first and second paths which do not share any risk at a level of the hierarchy of resources below the highest level of the hierarchy of resources.

24. A method according to claim 23 wherein subsequent attempts are made for respective lower levels of the hierarchy of resources until first and second paths are identified which do not share risk at the respective lower level.

25. A method according to claim 1 further comprising:

while transforming the network topology, performing further transformations which encourage the selection of the first and second path in a maximally edge disjoint manner.

26. A method according to claim 1 further comprising:

while transforming the network topology, performing further transformations which encourage the selection of the first and second path in a maximally node disjoint manner.

27. A method according to claim 1 wherein the shared risk groups include at least one group selected from:

shared risk captive office group, shared risk node group, shared risk link card group, shared risk trench group, shared risk conduit group, shared risk fiber group.

28. A method according to claim 23 further comprising:

defining a first hierarchy comprising a first level which is line cards, a second level which is nodes, and a third level which is captive offices;

defining a second hierarchy comprising a first level which is fibers, a second level which is conduits and a third level which is trenches.

29. A processing platform-readable medium having code means stored thereon for instructing a processing platform to select multiple paths through a network represented by a network topology representing an interconnected set of network resources, the medium comprising:

first code means for identifying a first path through the network topology from a source node to a destination node, the first path comprising a first sequence of network resources;

second code means adapted to, for at least one shared risk group, determine if any of the at least one shared risk group includes any of the first sequence of network resources, a shared risk group being a group of network resources within the network topology which have a shared risk;

third code means for performing a SRG (shared risk group) topology transformation of the network topology into a virtual topology which discourages the use of network resources in any shared risk group determined by the second code means;

fourth code means adapted to identify a second path through the virtual topology from the source node to the destination node, the second path comprising a second sequence of network resources.

30. A network management platform comprising:

means for maintaining or obtaining network topology information;

means for identifying a first path through the network topology from a source node to a destination node, the first path comprising a first sequence of network resources;

means adapted to, for at least one shared risk group, determine if any of the at least one shared risk group includes any of the first sequence of network resources, a shared risk group being a group of network resources within the network topology which have a shared risk;

means for performing a SRG (shared risk group) topology transformation of the network topology into a virtual topology which discourages the use of network resources in any shared risk group determined by the second code means;

means adapted to identify a second path through the virtual topology from the source node to the destination node, the second path comprising a second sequence of network resources.