Method and apparatus for inferring network paths

• US 8,155,126 B1
• Filed: 11/30/2005
• Issued: 04/10/2012
• Est. Priority Date: 06/03/2005
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Mao, Zhuoqing Morley, Qiu, Lili, Wang, Jia, Zhang, Yin
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): SWEET, LONNIE V
• Application Number:
  US11/289,944
• Time in Patent Office: 2,323 Days
• Field of Search: 370/381, 370/392, 370/395.31, 370/397, 709/218, 709/224, 709/242
• US Class Current: 370/397
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel

Abstract

Disclosed is a method and apparatus for inferring AS paths between two endpoint nodes communicating over a network having a plurality of nodes without having access to the endpoint nodes. The method and apparatus determine routing tables of at least some of the plurality of nodes. A relationship between each node is then inferred from the routing tables. The method and apparatus then determine a path between the two endpoint nodes from the relationship and the routing table determination.

Claims

1. A method for inferring a path between a first endpoint node and a second endpoint node in a network comprising:

obtaining a plurality of Border Gateway Protocol (BGP) routing tables;

generating a graph of the network topology based on the plurality of BGP tables, the graph of the network topology comprising a plurality of nodes and edges, each of the nodes associated with an autonomous system (AS) and each of the edges associated with a connection between two autonomous systems;

applying a stub removal procedure to generate a stubbed graph of the network topology, the stubbed graph removal procedure comprises removing from the graph of the network topology each of the plurality of nodes that is connected to a single edge;

inferring at a processor relationships between nodes in the network based on the plurality of BGP routing tables without having access to at least one of the first endpoint node and the second endpoint node, the relationships including customer-provider links, provider-customer links, and peering links, each of the relationships being associated with a respective routing policy;

identifying a point, wherein the point is a first hop autonomous system (AS) that a packet sent from the first endpoint node travels to before reaching the second endpoint node, wherein identifying a point comprises;

determining a first hop count from first endpoint node to the point, a second hop count from the point to the second endpoint node, and a third hop count from the first endpoint node to the second endpoint node; and

identifying the point as a transition point based on a comparison of the first hop count, the second hop count and the third hop count; and

determining at the processor the path between the first endpoint node and the second endpoint node, based on the transition point, the routing policies associated with the relationships and the stubbed graph of the network topology.

2. The method of claim 1 further comprising generating a graphical representation of the plurality of nodes from the routing tables.

3. The method of claim 2 wherein the graphical representation further comprises edges and links connecting the edges.

4. The method of claim 1 further comprising gathering a list of candidate first hop autonomous systems.

5. A system for inferring a path between a first endpoint node and a second endpoint node in a network comprising:

means for obtaining a plurality of Border Gateway Protocol (BGP) routing tables;

means for generating a graph of the network topology based on the plurality of BGP tables, the graph of the network topology comprising a plurality of nodes and edges, each of the nodes associated with an autonomous system (AS) and each of the edges associated with a connection between two autonomous systems;

means for applying a stub removal procedure to generate a stubbed graph of the network topology, the stubbed graph removal procedure comprises removing from the graph of the network topology each of the plurality of nodes that is connected to a single edge;

means for inferring relationships between nodes in the network based on the plurality of BGP routing tables without having access to at least one of the first endpoint node and the second endpoint node, the relationships including customer-provider links, provider-customer links, and peering links, each of the relationships being associated with a respective routing policy;

means for identifying a point, wherein the point is a first hop autonomous system (AS) that a packet sent from the first endpoint node travels to before reaching the second endpoint node, wherein identifying a point comprises;

means for determining a first hop count from first endpoint node to the point, a second hop count from the point to the second endpoint node, and a third hop count from the first endpoint node to the second endpoint node; and

means for identifying the point as a transition point based on a comparison of the first hop count, the second hop count and the third hop count; and

means for determining the path between the two endpoint nodes based on the routing policies associated with the relationships and the stubbed graph of the network topology.

6. The system of claim 5 further comprising means for generating a graphical representation of the plurality of nodes from the routing tables.

7. The system of claim 6 wherein the graphical representation further comprises edges and links connecting the edges.

8. The system of claim 5 further comprising means for gathering a list of candidate first hop autonomous systems.