Method and system to reduce a number of border gateway protocol neighbors crossed to reach target autonomous systems

1. A computer-implemented method of increasing routing efficiency between a plurality of given autonomous systems (ASes) and respective sets of target ASes in a border gateway protocol (BGP) session, the method comprising:

receiving, at a processor, a set of Routing Information Bases (RIBs) indicated by a user; and

configuring the processor to:

parse the RIBs by extracting respective sets of routing attributes from the RIBs;

identify a set of intermediate ASes from within the respective sets of routing attributes;

infer economic relationships between pairs of adjacent intermediate ASes, wherein the economic relationships include at least one of customer-provider (c2p or p2c), peer-to-peer (p2p), or sibling-to-sibling (s2s);

calculate distances between intermediate ASes and create an M×M matrix of distances between intermediate ASes in memory, wherein M is a number of ASes found in at least one of the RIBs;

infer candidate ASes from the set of intermediate ASes using the matrix of distances;

for each respective AS described in the matrix of distances, compute a list of potential saved hops to reach every target AS if the respective AS were connected along paths defined between given ASes and target ASes; and

output results, including the list of potential saved hops, to the user to identify candidate ASes having higher values of impact to connect along the paths to reduce an average number of hops along the paths, thereby increasing routing efficiency between the given ASes and the target ASes.

2. The method of claim 1 further including receiving a list of starting ASes that are already connected to the paths and a list of ASes to avoid.

3. The method of claim 2 wherein the given ASes are the starting ASes.

4. The method of claim 1 further including configuring the processor to create a topology of intermediate ASes, the topology having edges defined between intermediate ASes, the edges representing economic relationships between intermediate ASes, the edges tagged as p2c, c2p, p2p, or s2s.

5. The method of claim 4 wherein the calculated distances between intermediate ASes include components of downhill distances calculated for edges tagged as p2c or s2s, and components of overall distances calculated for edges tagged as p2c, c2p, p2p, or s2s.

6. The method of claim 1 wherein candidate ASes are inferred from the set of intermediate ASes by determining whether or not individual intermediate ASes are able to be connected to the paths, and wherein the impacts of the candidate ASes on the paths are provided for a list of candidate ASes ranked by impact.

7. The method of claim 6 wherein the list of candidate ASes ranked by impact is output via a user interface.

8. The method of claim 7 wherein the user interface also shows an average distance for a candidate AS selected from the ranked list by the user.

9. The method of claim 6 wherein the list of candidate ASes ranked by impact is output to a text-based computer file and stored in memory.

10. The method of claim 1 further including receiving, at the processor, a selection, from the user, of at least one candidate AS to connect along the path, and while considering the selected candidate AS to be connected along the path, further configuring the processor to:

parse the Ms by extracting respective sets of routing attributes from the RIBs;

identify intermediate ASes from within the respective sets of routing attributes;

infer economic relationships between pairs of adjacent intermediate ASes;

calculate, or load from memory, distances between intermediate ASes and create or update an M×M matrix of distances between intermediate ASes in memory, wherein M is a number of ASes found in at least one of the RIBs;

infer candidate ASes from the set of intermediate ASes using the matrix of distances;

for each respective AS described in the matrix of distances, compute a list of potential saved hops to reach every target AS if the respective AS were connected along paths defined between given ASes and target ASes; and

output results, including the list of potential saved hops, to the user to identify candidate ASes having higher values of impact to connect along the paths to reduce an average number of hops along the paths, thereby increasing routing efficiency between the given ASes and the target ASes.

11. A system for increasing routing efficiency between a plurality of given autonomous systems (ASes) and respective sets of target ASes in a border gateway protocol (BGP) session, the system comprising:

a set of Routing Information Bases (RIBs) indicated by a user; and

a processor and a non-transitory memory device having processor instructions stored thereon, the instructions, when loaded, configuring the processor to:

receive the set of RIBs directly via a user input or by loading the set of RIBs from the memory device;

parse the RIBs by extracting respective sets of routing attributes from the RIBs;

identify intermediate ASes from within the respective sets of routing attributes;

infer economic relationships between pairs of adjacent intermediate ASes,

wherein the economic relationships include at least one of customer-provider (c2p or p2c), peer-to-peer (p2p), or sibling-to-sibling (s2s);

calculate distances between intermediate ASes and create an M×M matrix of distances between intermediate ASes in memory, wherein M is a number of ASes found in at least one of the RIBs;

infer candidate ASes from the set of intermediate ASes using the matrix of distances;

for each respective AS described in the matrix of distances, compute a list of potential saved hops to reach every target AS if the respective AS were connected along paths defined between given ASes and target ASes; and

output results, including the list of potential saved hops, to the user to identify candidate ASes having higher values of impact to connect along the paths to reduce an average number of hops along the paths, thereby increasing routing efficiency between the given ASes and the target ASes.

12. The system of claim 11 wherein the processor is further configured to receive a list of starting ASes that are already connected to the paths and a list of ASes to avoid.

13. The system of claim 12 wherein the given ASes are the starting ASes.

14. The system of claim 11 wherein the processor is further configured to create a topology of intermediate ASes, the topology having edges defined between intermediate ASes, the edges representing economic relationships between intermediate ASes, the edges tagged as p2c, c2p, p2p, or s2s.

15. The system of claim 14 wherein the calculated distances between intermediate ASes include components of downhill distances calculated for edges tagged as p2c or s2s, and components of overall distances calculated for edges tagged as p2c, c2p, p2p, or s2s.

16. The system of claim 11 wherein candidate ASes are inferred from the set of intermediate ASes by determining whether or not individual intermediate ASes are able to be connected to the paths, and wherein the impacts of the candidate ASes on the paths are provided for a list of candidate ASes ranked by impact.

17. The system of claim 16 further including a user interface, and wherein the list of candidate ASes ranked by impact is output via the user interface.

18. The system of claim 17 wherein the user interface also shows an average distance for a candidate AS selected from the ranked list by the user.

19. The system of claim 16 wherein the list of candidate ASes ranked by impact is output to a text-based computer file and stored in the memory device.

20. The system of claim 11 wherein the processor is further configured to:

receive a selection, from the user, of at least one candidate AS to connect along the path;

consider the selected candidate AS to be connected along the path;

parse the Ms by extracting respective sets of routing attributes from the RIBs;

identify intermediate ASes from within the respective sets of routing attributes;

infer economic relationships between pairs of adjacent intermediate ASes;

calculate, or load from the memory device, distances between intermediate ASes and create or update an M×M matrix of distances between intermediate ASes in memory, wherein M is a number of ASes found in at least one of the RIBs;

infer candidate ASes from the set of intermediate ASes using the matrix of distances;

for each respective AS described in the matrix of distances, compute a list of potential saved hops to reach every target AS if the respective AS were connected paths defined between given ASes and target ASes; and

output results, including the list of potential saved hops, to the user to identify candidate ASes having higher values of impact to connect along the paths to reduce an average number of hops along the paths, thereby increasing routing efficiency between the given ASes and the target ASes.

21. A computer-implemented method of increasing routing efficiency between a plurality of given autonomous systems (ASes) and respective sets of target ASes in a border gateway protocol (BGP) session, the method comprising:

receiving, at a processor, a set of Routing Information Bases (RIBs) indicated by a user; and

configuring the processor to:

parse the RIBs by extracting respective sets of routing attributes from the RIBs;

identify a set of intermediate ASes from within the respective sets of routing attributes;

infer economic relationships between pairs of adjacent intermediate ASes, wherein the economic relationships include at least one of customer-provider (c2p or p2c), peer-to-peer (p2p), or sibling-to-sibling (s2s);

calculate distances between intermediate ASes;

infer candidate ASes from the set of intermediate ASes using the calculated distances;

perform a saving inference by computing, for respective candidate ASes, potential impacts on paths defined between given ASes and target ASes if the respective candidate ASes are connected along the paths and construct a list of candidate ASes sorted by impact on the paths; and

output results, including the list of candidate ASes sorted by impact, to the user to identify candidate ASes having higher values of impact to connect along the paths to reduce an average number of hops along the paths, thereby increasing routing efficiency between the given ASes and the target ASes.

22. A computer-implemented method of increasing routing efficiency between a plurality of given autonomous systems (ASes) and respective sets of target ASes in a border gateway protocol (BGP) session, the method comprising:

receiving, at a processor, a set of Routing Information Bases (RIBs) indicated by a user; and

configuring the processor to:

parse the RIBs by extracting respective sets of routing attributes from the RIBs;

identify a set of intermediate ASes from within the respective sets of routing attributes;

infer economic relationships between pairs of adjacent intermediate ASes, wherein the economic relationships include at least one of customer-provider (c2p or p2c), peer-to-peer (p2p), or sibling-to-sibling (s2s);

calculate distances between intermediate ASes;

perform a status inference by computing distances of each target AS from the given AS, using the calculated distances, to determine if any intermediate AS is unable to be connected;

infer candidate ASes, determined by the status inference as being able to be connected, from the set of intermediate ASes;

perform a saving inference by computing, for respective candidate ASes, potential impacts on paths defined between given ASes and target ASes if the respective candidate ASes are connected along the paths, and compute a list of potential saved hops to reach every target AS if the respective AS were connected along the paths; and

output results, including the list of potential saved hops, to the user to identify candidate ASes having higher likelihood of contributing to an overall reduction in the number of AS hops to connect along the paths to reduce an average number of hops along the paths, thereby increasing routing efficiency between the given ASes and the target ASes.