Method and system for path identification in packet networks

• US 8,218,447 B2
• Filed: 04/14/2009
• Issued: 07/10/2012
• Est. Priority Date: 11/29/2001
• Status: Expired due to Term

• Current Assignee: Sons of Innovation LLC
• Original Assignee: Circadence Corporation
• Inventors: Rajan, Rajendran, Guerin, Roch
• Primary Examiner(s): Lee, Andrew
• Application Number:
  US12/423,392
• Publication Number:
  US 20090196184A1
• Time in Patent Office: 1,183 Days
• Field of Search: 370/238, 370/400, 709/241
• 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/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 multi-area Internet protocol (IP) autonomous system (AS) is disclosed. The method and system enable 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 source area of the AS where it originates until its exit point in its intended destination area.

Claims

1. A method of identifying a path of travel for a packet in a multi-area domain operated according to a link state routing protocol, comprising the steps of:

receiving topology information from a plurality of individual areas in a domain;

identifying a plurality of intra-area least cost paths from the topology information;

assembling a subset of the plurality of intra-area least cost paths into an end-to-end path between a starting address and a destination address;

wherein the identifying step comprises;

identifying at least one exit point from a first area through which the destination address is reachable;

constructing at least one least cost path segment within the first area between the starting address and at least one of the exit points;

selecting at least one of the least cost path segments to result in at least one selected first area least cost segment;

for at least one of the exit points associated with at least one of the selected least cost path segments, identifying a second area within the domain to which said at least one exit point is connected;

identifying at least one exit point from the second area through which the destination address is reachable;

constructing at least one least cost path segment within the second area between the at least one exit point of the first area and at least one exit point of the second area; and

selecting at least one of the least cost segments within the second area to result in at least one selected second area least cost segment;

wherein the assembling step comprises connecting one of the selected first area least cost segments and one of the selected second area least cost segments.

2. The method of claim 1 wherein each least cost path comprises a series of routers and links or networks between routers.

3. The method of claim 1 wherein the exit point from the first area is the destination address.

4. The method of claim 1 wherein the exit point of the second area is the destination address.

5. The method of claim 1 wherein the second constructing and selecting steps are repeated for one or more additional areas, and wherein the assembling step comprises connecting the least cost segments for all areas for which said steps have been performed.

6. The method of claim 1 wherein the identifying step further comprises identifying all exit points from the first area through which the destination address is reachable.

7. The method of claim 1 wherein each constructing step comprises constructing all possible least cost path segments;

and

the assembling step comprises connecting a plurality of the least cost path segments between the starting address and the destination address.

8. A computer-readable carrier containing instructions thereon that are capable of instructing a computing device to perform the steps of:

receiving topology information from a plurality of individual areas in a multi-arca routing domain;

identifying a plurality of intra-area least cost paths from the stored topology information; and

assembling a subset of the plurality of intra-area least cost paths into an end-to-end path between a starting address and a destination address;

wherein the instructions relating to the identifying step comprise instructions that instruct the computing device to;

identify at least one exit point from a first area through which the destination address is reachable;

construct at least one least cost path segment within the first area between the starting address and at least one of the exit points;

select at least one of the least cost path segments to result in at least one selected first area least cost segment,

for at least one of the exit points associated with at least one of the selected least cost path segments, identify a second area within the routing domain to which said at least one exit point is connected;

identify at least one exit point from the second area through which the destination address is reachable;

construct at least one least cost path segment within the second area between at least one of the exit points of the first area and at least one of the exit points of the second area;

select at least one of the least cost segments within the second area to result in at least one selected second area least cost segment; and

the instructions relating to the assembling step comprise instructions to connect one of selected first area least cost segments and one of the second area least cost segments.

9. The carrier of claim 8 wherein each least cost path comprises a series of routers and links or networks between routers.

10. The carrier of claim 8 wherein the instructions further comprise instructing the computing device to repeat the second constructing and selecting steps for at least one additional area, and

wherein the instructions relating to the assembling step instruct the computing device to connect the least cost segments for all areas for which said steps have been performed.

11. A method of storing historical routing information in a routing domain operating according to a link state routing protocol, comprising the steps of:

storing a plurality of routing events advertised in a routing domain as they are received over time;

identifying a set of time instants for which a complete context of routing and topology information of the routing domain will be maintained;

at each time instant identified in the identifying step, constructing at least one time-stamped routing information context by storing data structures representing current topology and routing state of the routing domain; and

for each of the time-stamped routing information contexts, constructing a time ordered list of routing events as the events are received over time until the next time instant identified in the identifying step;

wherein the routing domain comprises a multi-area routing domain, the time-stamped routing information contexts are logically partitioned through the separate storage of information pertaining to each area in the routing domain, and where the constructing step comprises constructing a separate time ordered list of routing events for each area in the routing domain.