Method for determining prospective peering partners for an internet service provider

• US 8,050,193 B2
• Filed: 04/28/2006
• Issued: 11/01/2011
• Est. Priority Date: 04/28/2006
• Status: Expired due to Fees

• Current Assignee: Telecom Italia S.p.A.
• Original Assignee: Telecom Italia S.p.A.
• Inventors: Larosa, Giuseppe, Accetta, Daniele
• Primary Examiner(s): Phan; Man
• Application Number:
  US12/226,740
• Publication Number:
  US 20090190583A1
• Time in Patent Office: 2,013 Days
• Field of Search: 370238-352, 370389-401, 709203-214, 709220-239
• US Class Current: 370/254
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

A method for determining prospective peering partners for an internet service provider, includes gathering internet service provider'"'"'s routing and traffic information; gathering additional routing information from sources other than the internet service provider; identifying uncovered target autonomous systems based on the internet service provider'"'"'s routing and traffic information, the uncovered target autonomous systems being autonomous systems with non-null traffic and that are reachable by the internet service provider via a transit relationship; identifying paths from the internet service provider to the uncovered target autonomous systems based on the additional routing information; identifying intermediate autonomous systems along the identified paths; and determining at least a prospective peering partner for the internet service provider based on the identified intermediate autonomous systems.

Claims

1. A method for determining prospective peering partners for an internet service provider, comprising:

gathering internet service provider'"'"'s routing and traffic information;

gathering additional routing information from sources other than the internet service provider;

identifying uncovered target autonomous systems based on the internet service provider'"'"'s routing and traffic information comprising;

identifying all target autonomous systems for which the internet service provider provides accessibility,

for each identified target autonomous system, identifying all paths from the internet service provider to the target autonomous system, and

defining the target autonomous system as an uncovered target autonomous system if the following criteria are satisfied;

the target autonomous system is not a peer, a customer or an upstream provider of the internet service provider,

at least one path exists where the first autonomous system in the path is an upstream provider of the internet service provider, and

no path exists where the first autonomous system in the path is a peer or a customer of the internet service provider; and

wherein an uncovered target autonomous system is an autonomous system with non-null traffic from/to the internet service provider and that is reachable by the internet service provider only via a transit relationship; and

identifying distinct paths from the internet service provider to the uncovered target autonomous systems among those previously identified based on the additional routing information;

identifying intermediate autonomous systems along the identified paths; and

determining at least a prospective peering partner for the internet service provider based on the identified intermediate autonomous systems.

2. The method of claim 1, wherein the internet service provider'"'"'s routing and traffic information are internet service provider'"'"'s intra-domain information, and the additional routing information are extra-domain information.

3. The method of claim 1, wherein the internet service provider'"'"'s routing information comprises border gateway protocol-like tables, and internet service provider'"'"'s traffic information comprises traffic volumes handled by the internet service provider.

4. The method of claim 3, wherein the internet service provider'"'"'s border gateway protocol-like tables are gathered at interconnection points of an internet service provider'"'"'s network with external networks.

5. The method of claim 1, wherein the additional routing information comprises public border gateway protocol tables collected at public observation points.

6. The method of claim 1, wherein identifying distinct paths from the internet service provider to the uncovered target autonomous systems among those previously identified based on the additional routing information comprises:

identifying distinct paths each satisfying at least the following criteria;

the last autonomous system in the path is an uncovered target autonomous system;

the first autonomous system in the path has an active transit relationship with the internet service provider or is an autonomous system of a high-level-tier internet service provider; and

the path has the shortest length in terms of number of autonomous systems among the paths ending in said uncovered target autonomous system and having a first autonomous system.

7. The method of claim 1, wherein identifying intermediate autonomous systems along the identified paths comprises:

identifying autonomous systems other than the first and the last autonomous systems in the identified paths.

8. The method of claim 1, wherein determining at least a prospective peering partner for the internet service provider based on the identified intermediate autonomous systems comprises:

ranking the intermediate autonomous systems.

9. The method of claim 8, wherein ranking the intermediate autonomous systems comprises:

computing a connectivity value for each intermediate autonomous system, said connectivity value being indicative of the capacity of the internet service provider to increase the accessibility of target autonomous systems through a peering relationship with said intermediate autonomous system;

identifying distinct paths from the internet service provider to the uncovered target autonomous systems among those previously identified based on the additional routing information; and

identifying a specific autonomous system in each identified distinct path from the internet service provider to an uncovered target autonomous system based on the connectivity values of the autonomous systems in the same path.

10. The method of claim 9, wherein identifying a specific autonomous system based on the connectivity values of the autonomous systems in the same path comprises:

starting from the autonomous system preceding the uncovered target autonomous systems and moving toward the first autonomous system in the path, comparing the respective connectivity value of the current autonomous system with a threshold; and

identifying the last autonomous system having a connectivity value lower than the threshold.

11. The method of claim 10, further comprising:

computing said threshold based on the connectivity value of the internet service provider.

12. The method of claim 11, wherein computing said threshold comprises:

adding the connectivity value of the internet service provider and an offset value.

13. The method of claim 8, wherein ranking the intermediate autonomous systems further comprises:

computing a potential traffic volume handled by the identified specific autonomous systems.

14. The method of claim 13, wherein computing potential traffic volumes handled by the identified specific autonomous systems comprises:

determining the traffic volumes to the uncovered target autonomous systems potentially served by the specific autonomous systems.

15. The method of claim 14, wherein determining the traffic volumes to the uncovered target autonomous systems potentially served by the specific autonomous systems comprises:

determining the potential traffic volume handled by each specific autonomous system based on the traffic volume of the specific autonomous system and the traffic volume of the uncovered target autonomous system to which the identified distinct path comprising the specific autonomous systems, leads.

16. A method for improving the connectivity of an internet service provider, comprising determining at least a prospective peering partner for said internet service provider according to the method of claim 1, and establishing an interconnection between an autonomous system associated with said internet service provider and an autonomous system associated with said prospective peering partner.

17. A non-transitory computer readable medium encoded with a computer program product loadable into a memory of at least one computer and comprising software code portions for performing the method according to claim 1.