Method and apparatus for discovering edge-disjoint shortest path pairs during shortest path tree computation

• US 6,928,484 B1
• Filed: 01/18/2000
• Issued: 08/09/2005
• Est. Priority Date: 01/18/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Huai, Jin, Anbiah, Anix, Baldwin, Gary
• Primary Examiner(s): Burgess, Glenton B.
• Assistant Examiner(s): PARTON, KEVIN S
• Application Number:
  US09/484,835
• Time in Patent Office: 2,030 Days
• Field of Search: 709/239, 709/240, 709/241, 709/242, 709/243, 370/395.42, 370/238
• US Class Current: 709/239
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method for identifying and choosing a shortest path segment that has an alternate edge disjoint path segment. While routing Unidirectional Path Switched Ring (UPSR) path segments in a graph, there may be several equal distance paths to choose the shortest path from. Choosing a certain path as the shortest path may minimize or eliminate the chance of finding an alternative path segment. A method is provided such that if multiple shortest paths from the source node to a particular destination node exist, the method selects the shortest path which has an alternate edge disjoint path, and which can be used for path protection. The particular shortest path chosen by the method is not necessarily the first shortest path constructed.

Claims

1. In a data communication network, a method for selecting protectable paths through a network by developing a shortest path tree rooted at a first node, said method comprising:

identifying a plurality of shortest paths having equal costs from said first node to a second node;

identifying one of said plurality of shortest paths that has an edge disjoint alternate path and is thus protectable by examining a parent node of each of said plurality of shortest paths to be one for which the parent node has not been marked, indicating that there is not a plurality of equal cost shortest paths to said parent node from said first node, said parent node being a last node before said second node on any path to said second node; and

marking said second node to indicate a plurality of shortest paths having equal costs from said first node to said second node.

2. The method of claim 1 further comprising:

using said set of paths in computation of a shortest path tree.

3. The method of claim 1 wherein said each of said shortest paths comprises either an individual path segment or a plurality of contiguous path segments, each of said path segments comprises an individual link or a plurality of contiguous links, and each of said links comprises a communications channel between two adjacent nodes.

4. The method of claim 1 wherein said equal costs are determined in accordance with a cost metric defined for said links of said network.

5. The method of claim 1 wherein at least one of said plurality of shortest paths was found in preceding computations in developing a shortest path tree.

16. The method of claim 1 further comprising:

adding one or more new path(s) to a set of paths in said network, said new path(s) including said identified shortest path and extending beyond said second node to one or more destination nodes adjacent to said second node.

6. In a data communication network, a computer program product for selecting protectable paths through a network by developing a shortest path tree rooted at a first node, said computer program product comprising:

code that causes identification of a plurality of shortest paths having equal costs from said first node to a second node;

code that causes identification of one of said plurality of shortest paths that has an edge disjoint alternate path and is thus protectable by examining a parent node of each of said plurality of shortest paths to be one for which the parent node has not been marked, indicating that there is not a plurality of equal cost shortest paths to said parent node from said first node, said parent node being a last node before said second node on any path to said second node;

code that causes marking of said second node to indicate a plurality of equal cost shortest paths from said first node to said second node; and

a computer-readable storage medium that stores the codes.

7. The computer program product of claim 6 further comprising:

code that uses said set of paths in computation of a shortest path tree.

8. The computer program product of claim 6 wherein each of said shortest paths comprises either an individual path segment or a plurality of contiguous path segments, each of said path segments comprises an individual link or a plurality of contiguous links, and each of said links comprises a communications channel between two adjacent nodes.

9. The computer program product of claim 6 wherein said equal costs are determined in accordance with a cost metric defined for said links of said network.

10. The computer program product of claim 6 wherein at least one of said plurality of shortest paths was found in preceding computations in developing a shortest path tree.

17. The computer program product of claim 6 further comprising:

code that causes addition of one or more new path(s) to a set of paths in said network, said new path(s) including said identified shortest path and extending beyond said second node to one or more destination nodes adjacent to said second node.

11. In a data communication network, apparatus for selecting protectable paths through a network by developing a shortest path tree rooted at a first node, said apparatus comprising:

means for identifying a plurality of shortest paths having equal costs from said first node to a second node;

means for selecting one of said plurality of shortest paths that has an edge disjoint alternate path and is thus protectable by examining a parent node of each of said plurality of shortest paths to be one for which the parent node has not been marked, indicating that there is not a plurality of equal cost shortest paths to said parent node from said first node, said parent node being a last node before said second node on any path to said second node; and

means for marking said second node to indicate a plurality of equal cost shortest paths from said first node to said second node.

12. The apparatus of claim 11 further comprising:

means for using said set of paths in computation of a shortest path tree.

13. The apparatus of claim 11 wherein said each of said shortest paths comprises either an individual path segment or a plurality of contiguous path segments, each of said path segments comprises an individual link or a plurality of contiguous links, and each of said links comprises a communications channel between two adjacent nodes.

14. The apparatus of claim 11 wherein said equal costs are determined in accordance with a cost metric defined for said links of said network.

15. The apparatus of claim 11 wherein at least one of said plurality of shortest paths was found in preceding computations in developing a shortest path tree.

18. The apparatus of claim 11 further comprising:

means for adding one or more new path(s) to a set of paths in said network, said new path(s) including said identified shortest path and extending beyond said second node to one or more destination nodes adjacent to said second node.

19. In a data communication network, apparatus for selecting protectable paths through a network by developing a shortest path tree rooted at a first node, said apparatus comprising:

a processor; and

a computer-readable storage medium storing software for execution by said processor, said software comprising;

code that causes identification of a plurality of shortest paths having equal costs from said first node to a second node;

code that causes identification of one of said plurality of shortest paths that has an edge disjoint alternate path and is thus protectable by examining a parent node of each of said plurality of shortest paths to be one for which the parent node has not been marked, indicating that there is not a plurality of equal cost shortest paths to said parent node from said first node, said parent node being a last node before said second node on any path to said second node; and

code that causes marking of said second node to indicate a plurality of equal cost shortest paths from said first node to said second node.

20. The apparatus of claim 19 wherein said software further comprises:

code that uses said set of paths in computation of a shortest path tree.

21. The apparatus of claim 19 wherein each of said shortest paths comprises either an individual path segment or a plurality of contiguous path segments, each of said path segments comprises an individual link or a plurality of contiguous links, and each of said links comprises a communications channel between two adjacent nodes.

22. The apparatus of claim 19 wherein said equal costs are determined in accordance with a cost metric defined for said links of said network.

23. The apparatus of claim 19 wherein at least one of said plurality of shortest paths was found in preceding computations in developing a shortest path tree.

24. The apparatus of claim 19 wherein said software further comprises:

code that causes addition of one or more new path(s) to a set of paths in said network, said new path(s) including said identified shortest path and extending beyond said second node to one or more destination nodes adjacent to said second node.