Method and apparatus for determining network routing information based on shared risk link group information
First Claim
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;
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 any link that is determined to be in one of the shared risk link groups.
1 Assignment
0 Petitions
Accused Products
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.
69 Citations
20 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;
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 any link that is determined to be in one of the shared risk link groups. - View Dependent Claims (2, 3, 4, 9, 19)
-
-
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 S 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. - View Dependent Claims (10, 20)
-
-
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;
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. - View Dependent Claims (7, 8)
-
-
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;
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 any link that is determined to be in one of the shared risk link groups. - View Dependent Claims (12, 13, 14)
-
-
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 S 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;
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. - View Dependent Claims (17, 18)
-
Specification