Method and system for topology construction and path identification in a two-level routing domain operated according to a simple link state routing protocol

• US 20030072270A1
• Filed: 02/15/2002
• Published: 04/17/2003
• Est. Priority Date: 11/29/2001
• Status: Active Grant

• Current Assignee: Sons of Innovation LLC
• Original Assignee: Iptivia
• Inventors: Guerin, Roch, Rajan, Rajendran
• Granted Patent: US 7,120,120 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• 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/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04N 11/042 Codec means
• CPC Class Codes: H04N 19/184 the unit being bits, e.g. of the compressed video stream
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component

Abstract

A method and system for extracting and building end-to-end route information in a two-level, multi-area Internet protocol (IP) autonomous system (AS) operated according to a simple link state routing protocol such as the Integrated System to Integrated System (IS-IS) protocol is disclosed. The method and system enables a user, such as a network administrator, to explicitly identify a full set of paths (links and routers) that a given IP packet would potentially traverse from its entry point in the area of the AS where it originates until its exit point in its intended destination or exit area.

Claims

1. A method for constructing topology and routing information in a two level multi-area routing domain operated according to a simple link state routing protocol, comprising the steps of:

acquiring topology and routing information, including route entries, for each area in the routing domain, the routing domain comprising a plurality of level one areas and a level two area;

within each level one area, identifying possible level one exit points into the level two area;

for each level one exit point through which a route entry known in the level one area can be reached, determining a cost of reaching the route entry from the level one exit point;

for each route entry known in the level two area, identifying at least one level two exit point out of the level two area;

for each level two exit point through which a route entry can be reached, determining a cost of reaching the route entry from the level two exit point; and

for all exit points out of the level two area, determining the set of level one areas, if any, to which they connect.

2. A method for constructing end-to-end paths between a specified origin and a specified destination in a two-level multi-area routing domain operated according to a simple link state routing protocol, comprising the steps of:

acquiring topology and routing information for each area in the routing domain;

identifying an origin area and an entry point in the origin area;

determining whether the origin area is a level one area or level two area;

retrieving a route entry in the origin area, the route entry being associated with a specified destination;

extracting a set of exit points from the origin area through which the route entry associated with the specified destination can be reached; and

computing shortest paths in the origin area between the entry point and each exit point in the set of exit points.

3. The method of claim 2 wherein the origin area is a level one area and the route entry retrieved in the routing step is not a null or default entry, and further comprising the steps of:

for each exit point associated with the route entry, computing a cost of reaching the route entry through that exit point by adding a cost of the shortest path between the entry point and the exit point to a cost of reaching the route entry from the level one exit point; and

identifying at least one minimum total cost path to the specified destination through one of the exit points.

4. The method of claim 2 wherein the origin area is a level one area and the route entry retrieved in the retrieving step is a null or default entry, and further comprising the step selecting at least one exit point into the level two area, wherein at least one of the selected exit points corresponds to a minimum cost shortest path.

5. The method of claim 4 further wherein at least one of the selected exit points serves as an origin point into the level two area for extension of the shortest path to the specified destination, and wherein the level two area may be considered as an origin area for said extension of the shortest path.

6. The method of claim 2 wherein the origin area is a level one area, and the exit points returned in the extracting step are a function of whether a route entry associated with the specified destination address is present in a route table that is associated with the level one area.

7. The method of claim 2 wherein the origin area is a level two area, and the exit points returned in the extracting step are routers that advertised reachability for a route entry associated with the specified destination in a route table that is associated with the level two area.

8. The method of claim 2 wherein the origin area is a level one area, and the exit points returned in the extracting step are routers that advertised reachability for a route entry associated with the specified destination in a route table that is associated with the level one area.

9. The method of claim 2 wherein the origin area is a level one area, and the exit points returned in the extracting step are routers that are connected to the level two area.

10. The method of claim 2 wherein the origin area is a level one area, and the retrieving step comprises accessing a route table maintained for said area and failing to retrieve from said route table a non-null or non-default route entry associated with the specified destination.

11. The method of claim 2 wherein the origin area is a level two area, and the retrieving step comprises accessing a route table for said level two area and retrieving a route entry associated with the specified destination.

12. The method of claim 2 wherein the origin area is a level two area, and further comprising the steps of:

for each exit point obtained in the extracting step, computing a total cost by adding the cost of the corresponding shortest path to the cost of reaching the route entry from the exit point;

eliminating exit points and shortest paths that do not correspond to minimum total costs from the set of exit points;

identifying shortest paths associated with exit points through which the route entry is directly reachable;

eliminating, from the set of exit points, those exit points through which the route entry is directly reachable;

for each exit point remaining in the set of exit points, identifying a possible subsequent level one area into which the paths need to be extended; and

extending paths from each remaining exit point into the subsequent level one area.

13. The method of claim 12 wherein the last extending step comprises:

selecting an origin area exit point and an associated next level one area;

specifying a level one entry point in said next level one area based on the origin area exit point;

retrieving a next level route entry in said next level one area associated with the specified destination;

identifying a set of level one exit points from said next level one area through which the next level route entry can be reached, and determining a cost of reaching the route entry from each of those exit points;

computing shortest paths in said level one area between the level one entry point and the level one exit points, and for each level one exit point, computing a total cost by adding the cost of the corresponding shortest path to the cost of reaching the level one route entry from the level one area exit point;

eliminating level one exit points and shortest paths that do not correspond to minimum total costs; and

identifying shortest paths associated with level one exit points that correspond to minimum total cost paths.

14. A computer-readable medium containing instructions thereon for instructing a computing device to perform the steps of:

acquiring topology and routing information for each area in a multi-area routing domain that is operated according to a link state routing protocol;

identifying an origin area in the routing domain and an entry point in the origin area;

determining whether the origin area is a level one area or level two area;

retrieving a route entry in the origin area, the route entry being associated with a specified destination;

extracting a set of exit points from the origin area through which the route entry associated with the specified destination can be reached; and

computing shortest paths in the origin area between the entry point and each exit point in the set of exit points.

15. The medium of claim 14, wherein the instructions are further capable of instructing a computing device to perform the following steps if the route entry retrieved in the routing step is not a null or default entry:

for each exit point associated with the route entry, compute a cost of reaching the route entry through that exit point by adding a cost of the shortest path between the entry point and the exit point to a cost of reaching the route entry from the exit point; and

identify at least one minimum total cost path to the specified destination through one of the exit points.

16. The medium of claim 14 wherein the instructions are further capable of instructing the computing device, if the entry point is in a level one area and the route entry retrieved in the retrieving step is a null or default entry, to select at least one exit point into the level two area, wherein at least one of the selected exit points corresponds to a minimum cost shortest path.