Method and system for path identification in packet networks

• US 6,836,465 B2
• Filed: 11/29/2001
• Issued: 12/28/2004
• Est. Priority Date: 11/29/2001
• Status: Expired due to Term

• Current Assignee: Sons of Innovation LLC
• Original Assignee: Ipsum Networks, Inc. (Iptivia)
• Inventors: Rajan, Rajendran, Guerin, Roch
• Primary Examiner(s): Lee, Andy
• Application Number:
  US09/997,420
• Publication Number:
  US 20030099203A1
• Time in Patent Office: 1,125 Days
• Field of Search: 370/238, 370/389, 370/392, 370/400, 709/223, 709/224, 709/241, 709/242
• 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 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.

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

3. A method of identifying of path information in a routing domain operating according to a link state routing protocol, comprising:

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 a current topology and routing state of the routing domain;

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

specifying a starting point in the routing domain, a destination address in the routing domain, a starting time, and an ending time;

reviewing the time-stamped routing information contexts to identify the context having a time stamp that is latest yet still precedes contexts with a time-stamp preceding the starting time;

constructing at least one updated time-stamped routing information context by sequentially processing routing events from the time ordered list of routing events associated with the time-stamped routing information context until reaching the last routing event having a time-stamp that precedes the starting time; and

constructing path information between the starting point and the destination address using the updated time-stamped routing information context.

4. The method of claim 3 wherein constructing path information comprises:

identifying a plurality of paths from the updated time-stamped routing information context; and

assembling a subset of the plurality of paths into a least cost path between the starting point and the destination address.

5. The method of claim 4 wherein identifying a plurality of paths comprises identifying a plurality of paths through which the destination address is reachable.