Method and apparatus for determining network routing information based on shared risk link group information

• US 7,428,213 B2
• Filed: 11/21/2003
• Issued: 09/23/2008
• Est. Priority Date: 11/21/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Filsfils, Clarence, Ward, David, Vasseur, Jean Philippe, Previdi, Stefano B.
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): Mui; Gary
• Application Number:
  US10/719,003
• Publication Number:
  US 20050111349A1
• Time in Patent Office: 1,768 Days
• Field of Search: 370216-228, 370/238, 370/242, 370/254, 370/255
• US Class Current: 370/228
• CPC Class Codes: H04B 1/71635 Transmitter aspects H04B1/7174 takes precedence
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04W 88/06 adapted for operation in multiple networks or having at least two operational modes, e.g. multi-mode terminals
• CPC Class Codes: H04W 88/10 adapted for operation in multiple networks, e.g. multi-mode access points

Abstract

A method and apparatus are disclosed for performing a shortest path first network routing path determination in a data communications network based in part on information about links that are associated as shared risk link groups. Micro-loops are avoided in computing shortest path first trees by considering whether links are within shared risk link groups. In a first approach, for each link state packet in a link state database, listed adjacencies are removed if the link between the node originating the LSP and the reported adjacency belongs to a shared risk link group for which one component (local link) is known as down, and a shortest path first computation is then performed. In a second approach, during the SPT computation and after having added a first node to a path, each neighboring node is added to a tentative tree if and only if, a link between the first node and the neighboring node does not belong to a shared risk link group for which one component (local link) is known as down.

Claims

1. A method of determining network routing information based on shared risk link group information in a data communications network comprising nodes and links, the method comprising the computer-implemented steps of:

receiving information identifying a failed link in the network;

receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

accessing a link state database that stores information defining one or more links and adjacent nodes;

determining whether each link defined in the link state database is in the one or more shared risk link groups; and

removing an adjacent node from the link state database for a link other than the failed link that is determined to be in one of the shared risk link groups.

2. A method as recited in claim 1, performed as part of determining a shortest path through the network from a source to a destination.

3. A method as recited in claim 1, further comprising the steps of:

determining whether a graph of the data communications network based on the link state database is disconnected; and

if the graph is disconnected, then determining a new shortest path through the network to a destination network element without removing any link that has not been explicitly reported by another network element as failed.

4. A method according to any of claim 1, 2, or 3, further comprising the steps of:

initiating a timer prior to the accessing step;

when the timer expires, determining a new shortest path through the network to a destination network element.

5. A method of determining network routing information based on shared risk link group information in a data communications network comprising nodes and links, the method comprising the steps of:

receiving information identifying a failed link in the network;

receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

determining the set of links S logically comprising all links belonging to the one or more shared risk links groups to which the failed link belongs;

during computation of a shortest path first tree, after having added a node X to a path, adding each neighbor Ni of node X to a tentative tree if and only if a link (X, Ni) does not belong to S.

6. A method of determining network routing information based on shared risk link group information in a data communications network comprising nodes and links, the method comprising the steps of:

receiving information identifying a failed link in the network;

receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

initiating computation of a shortest path first tree;

adding a first node to a path as part of the computation;

determining a set of neighbors of the first node; and

adding each neighbor node to a tentative tree if and only if a link between the first node and the neighbor node does not belong to one of the shared risk link groups.

7. A method as recited in claim 6, further comprising the steps of:

determining whether a graph representing the data communications network is disconnected; and

if the graph is disconnected, then determining a new shortest path through the network to a destination network element without removing any link that has not been explicitly reported by another network element as failed.

8. A method according to any of claim 6 or 7, further comprising the steps of:

initiating a timer prior to the accessing step;

when the timer expires, determining a new shortest path through the network to a destination network element.

9. A computer readable storage medium storing one or more sequences of computer executable instructions for determining network routing information based on shared risk link group information in a data communications network comprising nodes and links in a data communications network having as elements links and nodes, which instructions, when executed by one or more processors, cause the one or more processors to perform

receiving information identifying a failed link in the network;

receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

accessing a link state database that stores information defining one or more links and adjacent nodes;

determining whether each link defined in the link state database is in the one or more shared risk link groups; and

removing an adjacent node from the link state database for a link other than the failed link that is determined to be in one of the shared risk link groups.

10. A computer readable storage medium storing one or more sequences of computer executable instructions for determining network routing information based on shared risk link group information in a data communications network comprising nodes and links in a data communications network having as elements links and nodes, which instructions, when executed by one or more processors, cause the one or more processors to perform

receiving information identifying a failed link in the network;

receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

determining the set of links S logically comprising all links belonging to the one or more shared risk links groups to which the failed link belongs;

during computation of a shortest path first tree, after having added a node X to a path, adding each neighbor Ni of node X to a tentative tree if and only if a link (X, Ni) does not belong to S.

11. An apparatus for generating routing information based on shared risk link group information in a data communications network having as elements nodes and links, comprising:

means for receiving information identifying a failed link in the network;

means for receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

means for accessing a link state database that stores information defining one or more links and adjacent nodes;

means for determining whether each link defined in the link state database is in the one or more shared risk link groups; and

means for removing an adjacent node from the link state database for a link other than the failed link that is determined to be in one of the shared risk link groups.

12. An apparatus as recited in claim 11, implemented as part of a means for determining a shortest path through the network from a source to a destination.

13. An apparatus as recited in claim 11, further comprising:

means for determining whether a graph of the data communications network based on the link state database is disconnected; and

means for determining, if the graph is disconnected, a new shortest path through the network to a destination network element without removing any link that has not been explicitly reported by another network element as failed.

14. An apparatus according to any of claims 11, 12, or 13, further comprising:

means for initiating a timer prior to the accessing step;

means for determining, when the timer expires, a new shortest path through the network to a destination network element.

15. An apparatus for determining network routing information based on shared risk link group information in a data communications network comprising nodes and links, the apparatus comprising:

means for receiving information identifying a failed link in the network;

means for receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

determining the set of links S logically comprising all links belonging to the one or more shared risk links groups to which the failed link belongs;

means for adding, during computation of a shortest path first tree, after having added a node X to a path, each neighbor Ni of node X to a tentative tree if and only if a link (X, Ni) does not belong to S.

16. An apparatus for determining network routing information based on shared risk link group information in a data communications network comprising nodes and links, the apparatus comprising:

means for receiving information identifying a failed link in the network;

means for receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

means for initiating computation of a shortest path first tree;

means for adding a first node to a path as part of the computation;

means for determining a set of neighbors of the first node; and

means for adding each neighbor node to a tentative tree if and only if a link between the first node and the neighbor node does not belong to one of the shared risk link groups.

17. An apparatus as recited in claim 16, further comprising:

means for determining whether a graph representing the data communications network is disconnected; and

means for determining, if the graph is disconnected, a new shortest path through the network to a destination network element without removing any link that has not been explicitly reported by another network element as failed.

18. An apparatus according to any of claims 16 or 17, further comprising:

means for initiating a timer prior to the accessing step;

means for determining, when the timer expires, a new shortest path through the network to a destination network element.

19. An apparatus for generating routing information in a data communications network having as elements links and nodes, the apparatus comprising:

one or more processors;

a network interface communicatively coupled to the processor and configured to communicate one or more packet flows among the processor and a network; and

a computer readable medium storing one or more sequences of instructions for generating routing information which instructions, when executed by one more processors, cause the one or more processors to perform;

receiving information identifying a failed link in the network;

receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

accessing a link state database that stores information defining one or more links and adjacent nodes;

determining whether each link defined in the link state database is in the one or more shared risk link groups; and

removing an adjacent node from the link state database for a link other than the failed link that is determined to be in one of the shared risk link groups.

20. An apparatus for generating routing information in a data communications network having as elements links and nodes, the apparatus comprising:

one or more processors;

a network interface communicatively coupled to the processor and configured to communicate one or more packet flows among the processor and a network; and

a computer readable medium storing one or more sequences of instructions for generating routing information which instructions, when executed by one more processors, cause the one or more processors to perform

receiving information identifying a failed link in the network;

receiving information defining one or more shared risk link groups to which the failed link belongs,

each of the one or more shared risk link groups logically comprising two or more links, one of the two or more links being the failed link, and each link in a shared risk link group sharing a physical resource whose failure risks affecting all of the links in the shared risk link group;

determining the set of links S logically comprising all links belonging to the one or more shared risk links groups to which the failed link belongs;

during computation of a shortest path first tree, after having added a node X to a path, adding each neighbor Ni of node X to a tentative tree if and only if a link (X, Ni) does not belong to S.