· Data
· People
Traceroute is widely used to detect routing problems, characterize end-to-end paths, and discover the Internet topology. Providing an accurate list of the Autonomous Systems (ASes) along the forwarding path would make traceroute even more valuable to researchers and network operators. However, conventional approaches to mapping traceroute hops to AS numbers are not accurate enough. Address registries are often incomplete and out-of-date. BGP routing tables provide a better IP-to-AS mapping, though this approach has significant limitations as well. Based on our extensive measurements, about 10% of the traceroute paths have one or more hops that do not map to a unique AS number, and around 15% of the traceroute AS paths have an AS loop. In addition, some traceroute AS paths have extra or missing AS hops due to Internet eXchange Points, sibling ASes managed by the same institution, and ASes that do not advertise routes to their infrastructure.
This project aims at building a scalable and accurate AS-level traceroute tool. We achieve this in the following key steps.
Step 0: We extract initial IP-to-AS mapping from the BGP tables that are obtained at a number of vantage points. This indicates the ASes that announce a given prefix as its origin ASes.
Step 1: Using the BGP tables as a starting point, we propose techniques for improving the IP-to-AS mapping as an important step toward an AS-level traceroute tool. Our algorithms draw on analysis of traceroute probes, reverse DNS lookups, BGP routing tables, and BGP update messages collected from multiple locations. We discussed how the improved IP-to-AS mapping allows us to home in on cases where the BGP and traceroute AS paths differ for legitimate reasons.
Step 2: We proposed 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 in Step 1, 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.
Step 3: We are investigating an automated process to update the IP-to-AS mapping as part of on-going work.
|
Organization |
Location |
Date |
Upstream providers |
|
UC Berkeley (AS 25) |
CA, |
June 6-8, 2003 |
Quest (209), Level 3 (3356) |
|
Univ of |
WA, |
June 4-8, 2003 |
Verio (2914), Cable & Wireless (3561) |
|
PSG home network (AS 3130) |
WA, |
April 30 - May 8, 2003 |
Sprint (1239), Verio (2914) |
|
AT&T Research (AS 6431) |
NJ, |
June 6-9, 2003 |
UUNet (701), AT&T (7018) |
|
ArosNet (AS 6521) |
UT, |
May 1-6, 2003 |
UUNET (701) |
|
Vineyard.NET (AS 10781) |
MA, |
June 4-9, 2003 |
UUNET (701), Sprint (1239), Level 3 (3356) |
|
Nortel (AS 14177) |
ON, |
May 1-6, 2003 |
AT&T Canada (15290) |
|
Peak Web Hosting (AS 22208) |
CA, |
May 1-8, 2003 |
Level 3 (3356), Global Crossing (3549), Teleglobe (6453) |
Step 0: Mapping extracted from BGP tables
Step 1: Mapping computed based on heuristics
Step 2: Mapping computed using dynamic programming algorithm
Step 0: IXPs learnt from public sources
Step 1: IXPs inferred by heurictics
Step 2: IXPs inferred by dynamic programming algorithm
Step 0: MOAS prefixes extracted from BGP tables
Step 1: MOAS prefixes computed based on heuristics
Step 2: MOAS prefixes computed using dynamic programming algorithm
Coming soon.