Method and system for path identification in packet networks

• US 7,525,920 B2
• Filed: 07/20/2004
• Issued: 04/28/2009
• Est. Priority Date: 11/29/2001
• Status: Active Grant

• Current Assignee: Sons of Innovation LLC
• Original Assignee: Coactive Technologies Pte Limited
• Inventors: Guerin, Roch, Rajan, Rajendran
• Primary Examiner(s): LEE, CHI HO A
• Application Number:
  US10/895,156
• Publication Number:
  US 20050025059A1
• Time in Patent Office: 1,743 Days
• Field of Search: None
• 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 between a starting address and a destination address in a routing domain operated according to a link state routing protocol, comprising:

specifying an ordered list of routing events, wherein the ordered list comprises a list of all routing events received after a routing information context was constructed, wherein the routing information context represents a starting topology and a routing state of a routing domain;

providing the routing information context;

constructing path information between a starting address and a destination address using the routing information context;

updating the routing information context in accordance with a next routing event in the ordered list of routing events; and

repeating the constructing and updating steps above until reaching a last routing event in the ordered list of routing events.

2. 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:

for each current area along a path of travel, wherein the path of travel has an origin and a destination;

receiving first topology information pertaining to at least one non-local area,

identifying a source for the current area, wherein if the current area includes the origin, the source for the current area is the origin, wherein if the current area does not include the origin, the source for the current area corresponds to an exit point for a previous area along the path of travel,

identifying one or more exit points from the current area through which the destination is reachable,

determining second topology information based on the source and the one or more exit points,

selecting an exit point from the one or more exit points, wherein the selected exit point represents a least cost path to the destination based on the first topology information pertaining to a most recently updated topology between the exit point and the destination and the second topology information, and

constructing a least cost path segment for the area from the source to the exit point; and

concatenating each least cost path segment to form an end-to-end path.

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

4. The carrier of claim 2 wherein the identifying step further comprises identifying all exit points from the current area through which the destination is reachable.

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

for each current area in a multi-area routing domain along a path of travel, wherein the path of travel has an origin and a destination;

receiving first topology information pertaining to at least one non-local area,

identifying a source for the current area, wherein if the current area includes the origin, the source for the current area is the origin, wherein if the current area does not include the origin, the source for the current area corresponds to an exit point for a previous area along the path of travel,

identifying one or more exit points from the current area through which the destination is reachable,

determining second topology information based on the source and the one or more exit points,

selecting an exit point from the one or more exit points, wherein the selected exit point represents a least cost path to the destination based on the first topology information pertaining to a most recently updated topology between the exit point and the destination and the second topology information, and

constructing a least cost path segment for the area from the source to the exit point; and

concatenating each least cost path segment to form an end-to-end path.

6. The method of claim 5 wherein each least cost path segment comprises a series of routers and links or networks between routers.

7. The carrier of claim 5 wherein the identifying step further comprises identifying all exit points from the current area through which the destination is reachable.

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

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

generating an end-to-end path from a starting address to a destination address, wherein generating the end-to-end path comprises;

setting an area starting point to the starting address,

identifying a plurality of intra-area paths from the area starting point based on the topology information,

selecting an intra-area least cost path from the plurality of intra-area paths, wherein the intra-area least cost path includes an exit point,

concatenating the intra-area least cost path to the end-to-end path,

if the exit point does not correspond to the destination address;

choosing a next area based on the exit point, wherein the area starting point for the next area corresponds to the exit point, and

repeating the identifying, selecting and concatenating steps for the next area, and

if the exit point corresponds to the destination address, returning the end-to-end path.

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

10. The method of claim 8 wherein the identifying step further comprises identifying all exit points from an area through which the destination address is reachable.

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

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

generating an end-to-end path from a starting address to a destination address, wherein generating the end-to-end path comprises;

setting an area starting point to the starting address,

identifying a plurality of intra-area paths from the area starting point based on the topology information,

selecting an intra-area least cost path from the plurality of intra-area paths, wherein the intra-area least cost path includes an exit point,

concatenating the intra-area least cost path to the end-to-end path,

if the exit point does not correspond to the destination address;

choosing a next area based on the exit point, wherein the area starting point for the next area corresponds to the exit point, and

repeating the identifying, selecting and concatenating steps for the next area, and

if the exit point corresponds to the destination address, returning the end-to-end path.

12. The carrier of claim 11 wherein each intra-area least cost path comprises a series of routers and links or networks between routers.

13. The carrier of claim 11 wherein the identifying step further comprises identifying all exit points from an area through which the destination address is reachable.

14. A method of storing historical routing 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 number of routing events for which a complete context of routing and topology information of the routing domain will be maintained;

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

constructing a time ordered list of routing events as the events are received over time until the number of routing events identified in the identifying step is reached.

15. The method of claim 14, 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.

16. A method of identifying 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 number of routing events for which a complete context of routing and topology information of the routing domain will be maintained;

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

constructing a time ordered list of routing events as the events are received over time until the number of routing events identified in the identifying step is reached;

specifying a starting point in the routing domain, a destination address in the routing domain, and a starting 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.