Devices, systems, and/or methods for determining internet topology

• US 8,521,904 B1
• Filed: 12/16/2008
• Issued: 08/27/2013
• Est. Priority Date: 12/16/2008
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Pei, Dan, Oliveira, Ricardo, Willinger, Walter, Zhang, Lixia, Zhang, Beichuan
• Primary Examiner(s): Avellino, Joseph
• Assistant Examiner(s): CONAWAY, JAMES E
• Application Number:
  US12/335,820
• Time in Patent Office: 1,715 Days
• Field of Search: 709/238, 370254-258
• US Class Current: 709/238
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

Certain exemplary embodiments can provide a method, which can comprise, based upon a quantified completeness of a determined topology of an interconnected set of Autonomous Systems of the Internet, at a user interface of an information device, automatically rendering a determined identity of a customer to which telecommunications products will be offered.

Claims

1. A method comprising:

determining a topology of an interconnected set of autonomous systems of the internet via a machine, wherein provider-customer links in the topology are identified as links that only appear in routes propagated from a single tier-1 autonomous system;

quantifying a completeness of the topology by utilizing a no-valley and prefer customer routing policy and via the provider-customer links in the topology;

rendering a machine-determined identity of a customer to which telecommunications products are to be offered at a user interface of an information device;

determining an upper bound estimate of a number of peer-peer links missing from the topology via an equation;

V(n)=L−

A(1−

nβ

)=(L−

A)+Aβ

n

wherein n is a count of monitors, V(n) is a count of visible peer-peer links after observing n monitors, L is a total count of peer-peer links in the internet, β

is a size of a small scope, and A is a total count of links having the small scope; and

rendering, at the user interface of the information device, the upper bound estimate of the number of peer-peer links missing from the topology.

2. The method of claim 1, further comprising:

machine-determining the topology via routeviews and ripe-routing information service.

3. The method of claim 1, wherein:

a set of rules follows an assumption that the topology comprises all links between tier-1 autonomous systems in the internet.

4. The method of claim 1, further comprising:

identifying a set of links that appear in routes propagated from a plurality of tier-1 autonomous systems to monitors as the provider-customer links in the topology via the no-valley and prefer customer routing policy.

5. The method of claim 1, further comprising:

filtering links from the topology that have been determined to have a lifetime of less than two days via the no-valley and prefer customer routing policy.

6. The method of claim 1, further comprising:

designating identified links as peer-peer links that are not designated as the provider-customer links or tier 1 to tier 1 links.

7. The method of claim 1, further comprising:

quantifying the completeness of the topology based upon the peer-peer links.

8. The method of claim 1, further comprising:

inferring a count of public peers of an autonomous system the topology based upon reverse domain name system lookups.

9. The method of claim 1, further comprising:

determining an upper bound of peer-peer links missing from the topology based upon an inferred count of public peers of a content provider.

10. The method of claim 1, further comprising:

labeling an autonomous system as a stub autonomous system based upon a determination that the autonomous system has less than four customers.

11. The method of claim 1, further comprising:

labeling an autonomous system as a small internet service provider based upon a determination that the autonomous system has between five and ninety customers.

12. The method of claim 1, further comprising:

labeling an autonomous system as a large internet service provider based upon a determination that the autonomous system has greater than ninety customers.

13. The method of claim 1, further comprising:

determining an expected count of peer autonomous systems via an equation;

P_c=Σ

_i(1−

(1−

q)ⁿ_i)

wherein C is a content provider, P_c is the expected count of peer autonomous systems to the content provider, i represents all networks that have at least one common presence with the content provider, q is a fixed fraction of networks collocated at an internet exchange point with the content provider, and n is a count of internet exchange points where both C and i have presence.

14. A system comprising:

a processor configured to;

determine a topology of an interconnected set of autonomous systems of the internet, wherein peer links in the topology are identified as links that only appear in routes propagated from a single tier-1 autonomous system;

quantify a completeness of the topology via a no-valley and prefer customer routing policy and via provider-customer links in the topology;

render an identity of a telecommunications customer that has been determined to be leaving a telecommunications provider at a user interface;

determine an upper bound estimate of a number of peer-peer links missing from the topology via an equation;

V(n)=L−

A(1−

nβ

)=(L−

A)+Aβ

n

wherein n is a count of monitors, V(n) is a count of visible peer-peer links after observing n monitors, L is a total count of peer-peer links in the internet, β

is a size of a small scope, and A is a total count of links having the small scope, and

render the upper bound estimate of the number of peer-peer links missing from the topology at the user interface.

15. A machine-readable medium comprising machine-implementable instructions for activities comprising:

determining a topology of an interconnected autonomous systems of the internet, wherein peer links in the topology are identified as links that only appear in routes propagated from a single tier-1 autonomous system;

quantifying a completeness of the topology by utilizing a no-valley and customer routing policy and by utilizing provider-customer links in the topology;

rendering a determined identity of a customer to which telecommunications products are to be offered at a user interface of an information device;

determine an upper bound estimate of a number of peer-peer links missing from the topology via an equation;

V(n)=L−

A(1−

nβ

)=(L−

A)+Aβ

n

wherein n is a count of monitors, V(n) is a count of visible peer-peer links after observing n monitors, L is a total count of peer-peer links in the internet, β

is a size of a small scope, and A is a total count of links having the small scope;

rendering, at the user interface of the information device, the upper bound estimate of the number of peer-peer links missing from the topology; and

filtering links from the topology that have been determined to have a lifetime of less than two days.