Patent ID: 8155126
Filing Date: 2012-04-10
Classification: H04L,H04Q

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