NDLI: Scalable and accurate identification of AS-level forwarding paths

Content Provider	IEEE Xplore Digital Library
Author	Mao, Z.M. Johnson, D. Rexford, J. Jia Wang Katz, R.
Copyright Year	2004
Description	Author affiliation: Michigan Univ., East Lansing, MI (Mao, Z.M.)
Abstract	Traceroute is used heavily by network operators and researchers to identify the IP forwarding path from a source to a destination. In practice, knowing the autonomous system (AS) associated with each hop in the path is also quite valuable. In previous work we showed that the IP-to-AS mapping extracted from BGP routing tables is not sufficient for determining the AS-level forwarding paths. By comparing BGP and traceroute AS paths from multiple vantage points, Z. Morley Mao et al. (2003) proposed heuristics that identify the root causes of the mismatches and fix the inaccurate IP-to-AS mappings. These heuristics, though effective, are labor-intensive and mostly ad hoc. This paper proposes a systematic way to construct accurate IP-to-AS mappings using dynamic programming and iterative improvement. Our algorithm reduces the initial mismatch ratio of 15% between BGP and traceroute AS paths to 5% while changing only 2.9% of the assignments in the initial IP-to-AS mappings. This is in contrast to the results of Z. Morley Mao et al. (2003), where 10% of the assignments were modified and the mismatch ratio was only reduced to 9%. We show that our algorithm is robust and can yield near-optimal results even when the initial mapping is corrupted or when the number of probing sources or destinations is reduced. Our work is a key step towards building a scalable and accurate AS-level traceroute tool
Starting Page	1605
Ending Page	1615
File Size	924475
Page Count	11
File Format	PDF
ISBN	0780383559
ISSN	0743166X
DOI	10.1109/INFCOM.2004.1354573
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-03-07
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Internet Delay Dynamic programming Iterative algorithms Network topology Probes IP networks Cellular neural networks Protocols
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Scalable and accurate identification of as-level forwarding paths (2004).

Scalable and Accurate Identification of AS-Level Forwarding Paths (2004)

Distributed center-location algorithms: proposals and comparisons

On the scalability of router forwarding tables: Nexthop-Selectable FIB aggregation

Semi-dynamic routing protocols for anycast packet forwarding

Distributed center-location algorithms

DIG: an overlay network for Internet multicasting

Exploring the Local Connectivity Preference in Internet AS Level Topology

Subnet level network topology mapping

Scalable and accurate identification of AS-level forwarding paths

Similar Documents

Scalable and accurate identification of as-level forwarding paths (2004).

Scalable and Accurate Identification of AS-Level Forwarding Paths (2004)

Distributed center-location algorithms: proposals and comparisons

On the scalability of router forwarding tables: Nexthop-Selectable FIB aggregation

Semi-dynamic routing protocols for anycast packet forwarding

Distributed center-location algorithms

DIG: an overlay network for Internet multicasting

Exploring the Local Connectivity Preference in Internet AS Level Topology

Subnet level network topology mapping

Scalable and accurate identification of AS-level forwarding paths