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 7,120,120 B2
• Filed: 02/15/2002
• Issued: 10/10/2006
• Est. Priority Date: 11/29/2001
• Status: Active Grant

• Current Assignee: Sons of Innovation LLC
• Original Assignee: Ipsum Networks, Inc. (Iptivia)
• Inventors: Guerin, Roch, Rajan, Rajendran
• Primary Examiner(s): Ngo, Ricky Q.
• Assistant Examiner(s): Haliyur, Venkatesh
• Application Number:
  US10/077,251
• Publication Number:
  US 20030072270A1
• Time in Patent Office: 1,698 Days
• Field of Search: 370/235, 370/238, 370/229, 370/238.1, 370/254, 370/351, 370/389, 370/401, 370/252, 709/241, 709/238
• US Class Current: 370/238
• 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 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, wherein the origin area is a level one 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;

for each exit point associated with the route entry, determining a shortest path in the origin area between the entry point and the exit point;

determining whether the route entry is a null or default entry;

if the route entry is not a null or default entry, for each exit point associated with the route entry, calculating a cost of reaching the route entry through the 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;

if the route entry is a null or default entry;

selecting at least one exit point into a level two area, wherein each selected exit point corresponds to a shortest path having a minimum cost, and

calculating a cost of reaching the route entry through each selected exit point by adding a cost of the shortest path to a cost of reaching the route entry from the exit point; and

identifying at least one total path to the specified destination through an exit point, wherein each total path comprises a concatenation of a plurality of hops between the entry point and the specified destination.

2. The method of claim 1 wherein 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.

3. The method of claim 1 wherein 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.

4. The method of claim 1 wherein the exit points returned in the extracting step are routers that are connected to the level two area.

6. The method of claim 1 wherein identifying at least one total path to the specified destination through an exit point comprises:

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

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

for each level two exit point associated with the level two route entry;

determining at least one shortest path in the level two area between the exit point and the level two exit point, and

calculating a total cost by adding a cost of a corresponding shortest path to a cost of reaching the level two route entry from the level two exit point;

eliminating level two exit points and shortest paths that do not correspond to a minimum cost from the set of level two exit points;

for each level two exit point through which the level two route entry is directly reachable, identifying a shortest path associated with the level two exit point, wherein the shortest path comprises a concatenation of a plurality of hops between the entry point and the specified destination;

eliminating, from the set of level two exit points, each level two exit point through which the route entry is directly reachable;

for each level two exit point remaining in the set of level two exit points;

identifying a level one area associated with the level two exit point,

retrieving a level one route entry in the level one area associated with the specified destination, and

determining at least one shortest path in the level one area between the level two exit point and the level one route entry; and

identifying at least one total path to the specified destination, wherein each total path comprises a concatenation of a shortest path in the origin area, a shortest path in the level two area, and a shortest path in the level one area.

5. 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, wherein the origin area is a level one 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;

for each exit point associated with the route entry, determining a shortest path in the origin area between the entry point and the exit point;

determining whether the route entry is a null or default entry;

if the route entry is not a null or default entry, for each exit point associated with the route entry, calculating a cost of reaching the route entry through the 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;

if the route entry is a null or default entry;

selecting at least one exit point into a level two area, wherein each selected exit point corresponds to a shortest path having a minimum cost, and

calculating a cost of reaching the route entry through each selected exit point by adding a cost of the shortest path to a cost of reaching the route entry from the exit point; and

identifying at least one total path to the specified destination through an exit point, wherein each total path comprises a concatenation of a plurality of hops between the entry point and the specified destination.

7. The computer-readable medium of claim 5 wherein identifying at least one total path to the specified destination through an exit point comprises:

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

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

for each level two exit point associated with the level two route entry;

determining at least one shortest path in the level two area between the exit point and the level two exit point, and

calculating a total cost by adding a cost of a corresponding shortest path to a cost of reaching the level two route entry from the level two exit point;

eliminating level two exit points and shortest paths that do not correspond to a minimum cost from the set of level two exit points;

for each level two exit point through which the level two route entry is directly reachable, identifying a shortest path associated with the level two exit point, wherein the shortest path comprises a concatenation of a plurality of hops between the entry point and the specified destination;

eliminating, from the set of level two exit points, each level two exit point through which the route entry is directly reachable;

for each level two exit point remaining in the set of level two exit points;

identifying a level one area associated with the level two exit point,

retrieving a level one route entry in the level one area associated with the specified destination, and

determining at least one shortest path in the level one area between the level two exit point and the level one route entry; and

identifying at least one total path to the specified destination, wherein each total path comprises a concatenation of a shortest path in the origin area, a shortest path in the level two area, and a shortest path in the level one area.

8. 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, wherein the origin area is a 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;

for each exit point associated with the route entry;

determining at least one shortest path in the origin area between the entry point and the exit point, and

calculating a total cost by adding a cost of a corresponding shortest path to a cost of reaching the route entry from the exit point;

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

for each exit point through which the route entry is directly reachable, identifying a shortest path associated with the exit point, wherein the shortest path comprises a concatenation of a plurality of hops between the entry point and the specified destination;

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

for each exit point remaining in the set of exit points;

identifying a level one area associated with the exit point,

retrieving a level one route entry in the level one area associated with the specified destination, and

determining at least one shortest path in the level one area between the exit point and the level one route entry; and

identifying at least one minimum total cost path to the specified destination, wherein each minimum total cost path comprises a concatenation of a shortest path in the origin area and a shortest path in the level one area.

9. 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 routine domain and an entry point in the origin area, wherein the origin area is a 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;

for each exit point associated with the route entry;

determining at least one shortest path in the origin area between the entry point and the exit point, and

calculating a total cost by adding a cost of a corresponding shortest path to a cost of reaching the route entry from the exit point;

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

for each exit point through which the route entry is directly reachable, identifying a shortest path associated with the exit point, wherein the shortest path comprises a concatenation of a plurality of hops between the entry point and the specified destination;

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

for each exit point remaining in the set of exit points;

identifying a level one area associated with the exit point,

retrieving a level one route entry in the level one area associated with the specified destination, and

determining at least one shortest path in the level one area between the exit point and the level one route entry; and

identifying at least one minimum total cost path to the specified destination, wherein each minimum total cost path comprises a concatenation of a shortest path in the origin area and a shortest path in the level one area.