Sharp snapshots of the internet's graph with HONE / Alexander Marder.

Format:

Book

Thesis/Dissertation

Author/Creator:

Marder, Alexander, author.

Contributor:

University of Pennsylvania. Department of Computer and Information Science, degree granting institution.

Smith, Jonathan M., degree supervisor.

Language:

English

Subjects (All):

Computer science.

Computer and Information Science--Penn dissertations.

Penn dissertations--Computer and Information Science.

Local Subjects:

Computer science.

Computer and Information Science--Penn dissertations.

Penn dissertations--Computer and Information Science.

Genre:

Academic theses.

Physical Description:

1 online resource (135 pages)

Contained In:

Dissertations Abstracts International 81-09B.

Place of Publication:

[Philadelphia, Pennsylvania] : University of Pennsylvania ; Ann Arbor : ProQuest Dissertations & Theses, 2019.

Language Note:

English

System Details:

Mode of access: World Wide Web.

text file

Summary:

Measuring, diagnosing, and debugging the Internet is surprisingly difficult. The end-to-end argument that pushes complexity to the network edge to ease evolution makes these goals harder by restricting network observables. A consequence has been the inability to address the challenge, posed to the networking community for nearly two decades, of taking accurate snapshots of the Internet graph. Heuristic Optimization of Network Estimation (HONE), described in this thesis, creates accurate graph snapshots that delineate the borders between Internet networks and illuminate interdomain links. Three novel technical contributions lead to HONE's success. First, HONE establishes a novel iterative constraint satisfaction framework that extracts constraints from traceroute collections; until HONE previous approaches relied on outside constraints. Second, the HONE framework is easily extended to incorporate new heuristics and data sources, making it inherently "future-proof." Third, HONE is the first snapshot technique to account for traceroute phenomena caused by layer 3 virtual private networks (L3VPNs). I validated these claims through the design, implementation, and evaluation of three experimental systems - MAP-IT, bdrmapIT, and vrfinder - that together form HONE. All the components advance the state-of-the-art toward accurate interface and router-level snapshots of the Internet's graph. The first component, MAP-IT, proposes the iterative constraint satisfaction framework at the core of HONE that allows it to use constraints drawn from the traceroute. The second component, bdrmapIT, extends the MAP-IT framework by incorporating methodologies from an independently designed system. bdrmapIT adapts heuristics designed for a narrow instance of the Internet snapshot problem and generalizes them for global Internet traceroutes. The final component, vrfinder, addresses the problem that L3VPNs cause routers to report the forwarding address in response to traceroute probes, violating general traceroute semantics. vrfinder is the first technique to identify forwarding address in traceroute, and extends bdrmapIT with additional heuristics designed for L3VPN forwarding addresses, further improving HONE's accuracy. HONE achieves the best-known accuracy for this problem on traditional IPv4 and IPv6 networks (92.5% - 100.0%), as well as forL3VPNs (88.7% - 95.7%).

Notes:

Source: Dissertations Abstracts International, Volume: 81-09, Section: B.

Advisors: Smith, Jonathan M; Committee members: Boon Loo; Andreas Haeberlen; Vincent Liu; kc claffy.

Department: Computer and Information Science.

Ph.D. University of Pennsylvania 2019.

Local Notes:

School code: 0175

ISBN:

9781392397114

Access Restriction:

Restricted for use by site license.

This item must not be sold to any third party vendors.