IP Library › Granted Patent US 12,261,768
Granted Patent B2
US 12,261,768 · App. 18/181,303 · Granted Mar 25, 2025

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

Inventors: Alessandro Improta (Massa, IT); Luca Sani (Lucca, IT); Dritan Suljoti (Parkland, FL); Sergey Katsev (Cortlandt Manor, NY)
Assignee: Catchpoint Systems, Inc.
H04L45/306H04L45/122H04L69/329
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,261,768
App. No.
18/181,303
Granted
Mar 25, 2025
Kind
B2
Abstract

The disclosed method and system increase routing efficiency by identifying a set of candidate Autonomous Systems (ASes) able to reduce average AS distances towards a set of target ASes. Starting from a list of Routing Information Base (RIB) snapshots and a set of target ASes, candidate ASes are ranked based on the gain they would provide in terms of AS distance if they were connected to the network administrator AS. A set of starting ASes may represent the ASes to which the administrator is already connected, and a set of forbidden ASes may represent the ASes to which the administrator does not want to connect. An exemplary web-based interface may show gains of candidate ASes, allowing the administrator to better understand how much an average AS distance toward the set of target ASes would improve.

Claims (44)

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

receiving, at a processor, one or more routing attributes included in one or more Routing Information Bases (RIBs); and

configuring the processor to:

identify one or more intermediate ASes from within the one or more routing attributes;

calculate distances between each of the one or more intermediate ASes;

generate an M×M matrix of the calculated distances, M being a number of ASes found in at least one of the one or more RIBs;

infer one or more candidate ASes from the one or more intermediate ASes using the matrix of the calculated distances;

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

identify at least one of the one or more candidate ASes having higher values of impact to connect along the one or more paths to reduce an average number of hops along the one or more paths, thereby increasing routing efficiency between the one or more given ASes and the one or more target ASes.

2. The method of claim 1 further including receiving, at the processor, a list of one or more starting ASes that are already connected to the one or more paths and a list of one or more ASes to avoid.

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

4. The method of claim 1 further including configuring the processor to create a topology of the one or more intermediate ASes, the topology having edges defined between the one or more intermediate ASes, the edges representing economic relationships between 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), the edges tagged as p2c, c2p, p2p, or s2s.

5. The method of claim 4 wherein the calculated distances 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 the one or more candidate ASes are inferred from the one or more intermediate ASes by determining whether or not individual intermediate ASes are able to be connected to the one or more paths, and wherein impacts of the one or more candidate ASes on the one or more paths are provided for a list of candidate ASes ranked by impact.

7. The method of claim 1 further including, prior to the configuring:

receiving, at the processor, a selection of at least one candidate AS to connect along at least one path; and

modifying, via the processor, the one or more routing attributes to reflect that the at least one candidate AS is connected along the at least one path.

8. A system for increasing routing efficiency between one or more given autonomous systems (ASes) and one or more target ASes in a border gateway protocol (BGP) session, the system comprising:

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

receive one or more routing attributes included in one or more Routing Information Bases (RIBs);

identify one or more intermediate ASes from within the one or more routing attributes;

execute a distance calculator configured to calculate distances between each of the one or more intermediate ASes;

generate an M×M matrix of the calculated distances, M being a number of ASes found in at least one of the one or more RIBs;

execute a gain analyzer configured to infer one or more candidate ASes from the one or more intermediate ASes using the matrix of the calculated distances;

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

identify at least one of the one or more candidate ASes having higher values of impact to connect along the one or more paths to reduce an average number of hops along the one or more paths, thereby increasing routing efficiency between the one or more given ASes and the one or more target ASes.

9. The system of claim 8 wherein the processor is further configured to receive a list of one or more starting ASes that are already connected to the one or more paths and a list of one or more ASes to avoid.

10. The system of claim 9 wherein the one or more given ASes are the one or more starting ASes.

11. The system of claim 8 wherein the processor is further configured to create a topology of the one or more intermediate ASes, the topology having edges defined between the one or more intermediate ASes, the edges representing economic relationships between 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), the edges tagged as p2c, c2p, p2p, or s2s.

12. The system of claim 11 wherein the calculated distances 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.

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

14. The system of claim 8 wherein the processor is further configured to:

receive a selection of at least one candidate AS to connect along at least one path; and

modify the one or more routing attributes to reflect that the at least one candidate AS is connected along the at least one path.

15. The method of claim 2 wherein computing the list of potential saved hops excludes connecting the one or more ASes to avoid.

16. The method of claim 1 wherein inferring the one or more candidate ASes from the one or more intermediate ASes comprises determining whether each of the one or more intermediate ASes is able to be connected to one or more of the one or more paths.

17. The method of claim 1 further including:

configuring the processor to infer economic relationships between pairs of adjacent intermediate ASes;

wherein calculating the distances between each of the one or more intermediate ASes is based on the inferred economic relationships.

18. The system of claim 9 wherein computing the list of potential saved hops excludes connecting the one or more ASes to avoid.

19. The system of claim 8 wherein the processor is further configured to infer the one or more candidate ASes from the one or more intermediate ASes by determining whether each of the one or more intermediate ASes is able to be connected to one or more of the one or more paths.

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

infer economic relationships between pairs of adjacent intermediate ASes; and

calculate the distances between each of the one or more intermediate ASes based on the inferred economic relationships.

Assignments (5)
SECURITY INTEREST Recorded Jan 16, 2026
From: CATCHPOINT SYSTEMS, INC.
To: GOLUB CAPITAL MARKETS LLC, AS COLLATERAL AGENT
Reel/Frame 073493/0823 →
RELEASE OF SECURITY INTEREST Recorded Dec 2, 2025
From: COMERICA BANK
To: CATCHPOINT SYSTEMS, INC.
Reel/Frame 073089/0753 →
NOTICE OF RELEASE OF SECURITY INTEREST Recorded Dec 3, 2024
From: ALLY BANK
To: CATCHPOINT SYSTEMS, INC.
Reel/Frame 069476/0311 →
SECURITY INTEREST Recorded Nov 22, 2024
From: CATCHPOINT SYSTEMS, INC.
To: COMERICA BANK
Reel/Frame 069371/0144 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 13, 2023
From: IMPROTA, ALESSANDRO; SANI, LUCA; SULJOTI, DRITAN; KATSEV, SERGEY
To: CATCHPOINT SYSTEMS, INC.
Reel/Frame 062960/0583 →
Continuity (3)
Continuation 17243248 · Apr 28, 2021
Provisional Application 63059803 · Jul 31, 2020
Related Publication 20230300066A1 · Sep 21, 2023
References Cited (26)
US 11627073B2 · Improta et al. · 2023 [cited by applicant]
US 20030120769A1 · McCollom · 2003 [cited by applicant]
US 20100002712A1 · Suzuki et al. · 2010 [cited by applicant]
US 20130132542A1 · Zhang · 2013 [cited by examiner]
US 20150172168A1 · Picconi · 2015 [cited by examiner]
US 20180077049A1 · Paul et al. · 2018 [cited by applicant]
US 20210344594A1 · Mendez et al. · 2021 [cited by applicant]
US 20220038366A1 · Improta et al. · 2022 [cited by applicant]
LINUX Foundation Collaborative Projects: FR Routing Project, Retrieved from Internet at: https://frrouting.org/, Retrieved from Internet on: Apr. 23, 2021, 3 pages. [cited by applicant]
Gregori, E. et al., “A Novel Methodology to Address the Internet AS-level Data Incompleteness,” IEEE/ACM Transactions on Networking, vol. 23, Issue 4, 14 pages (Aug. 2015). [cited by applicant]
Gregori, E. et al., “Isolario: a Do-ut-des Approach to Improve the Appeal of BGP Route Collecting,” arXiv.org:1611.06904v1, 10 pages (Nov. 2016). [cited by applicant]
Isolario Project: Interactive Collector Engine (ICE) and BGP Scanner, Retrieved from Internet at: https:/isolario.it/web_content/php/site_content/tools.php, Retrieved from Internet on: Apr. 23, 2021, 1 page. [cited by applicant]
Quagga Software Routing Suite, Retrieved from Internet at: https://www.quagga.net/, Retrieved from Internet on: Apr. 23, 2021, 1 page. [cited by applicant]
BGP Scanner, Retrieved from Internet at: https://gitlab.com/lsolario/bgpscanner/-/wikis/Home, Retrieved from Internet on: Apr. 28, 2021, 3 pages. [cited by applicant]
RIPE-NCC / bgpdump Utility and C Library for Parsing MRT Files, Retrieved from Internet at: https://github.com/RIPE-NCC/bgpdump, Retrieved from Internet on: Apr. 28, 2021, 2 pages. [cited by applicant]
Di Battista, et al., “Computing the Types of the Relationships between Autonomous Systems,” Submission To IEEE/ACM Transactions On Networking, pp. 1-14 (2003). [cited by applicant]
Dimitropoulos, X., et al., “Inferring AS Relationships: Dead End or Lively Beginning?,” In: Nikoletseas S.E. (eds) Experimental and Efficient Algorithms. WEA Lecture Notes in Computer Science, vol. 3503 (2005). [cited by applicant]
Hu, H. et al., “A Novel Method for Router-to-AS Mapping Based on Graph Community Discovery,” www.mdpi.com/journal/information, vol. 10, No. 87 (2019). [cited by applicant]
Leiner, B. M., “A Brief History of the Internet,” ACM SIGCOMM Computer Communication Review, vol. 39, No. 5, (Oct. 2009). [cited by applicant]
Fall 2019 ELEN6774 Topics in Networking: Internet Measurement: Retrievable at : http://www.columbia.edu/˜ebk2141/teaching/InternetMeasurement/2019FA, 7 pages (2019). [cited by applicant]
Gao, “On Inferring Autonomous System Relationships in the Internet,” IEEE/ACM Transactions on Networking, vol. 9, Issue 6, pp. 733-745; Dec. 2001. [cited by applicant]
Extended European Search Report for European Application No. 21188950.6, titled: Method And System To Identify A List Of Potential Border Gateway, Dated: Dec. 20, 2021. [cited by applicant]
Edman, M. and P. Syverson, “AS-awareness in Tor Path Selection,” Computer and Communications Security, ACM, 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, Nov. 9, 2009, pp. 380-389. [cited by applicant]
Smith, J.M. and M. Schuchard, “Routing Around Congestion: Defeating DDOS Attacks and Adverse Network Conditions via Reactive BGP Routing,” 2018 IEEE Symposium on Security and Privacy (SP), IEEE, May 20, 2018, pp. 599-61… [cited by applicant]
Non-Final Office Action for U.S. Appl. No. 17/243,248, entitled, “Method And System To Reduce A Number Of Border Gateway Protocol Neighbors Crossed To Reach Target Autonomous Systems,” dated Sep. 23, 2022. [cited by applicant]
Notice of Allowance for U.S. Appl. No. 17/243,248, entitled, “Method And System To Reduce A Number Of Border Gateway Protocol Neighbors Crossed To Reach Target Autonomous Systems,” dated Dec. 16, 2022. [cited by applicant]