Tracerout是由Van Jacobson於1988年所開發的網路偵錯工具，它可以顯示由本地主機至目的主機的前進路徑。這個工具被廣泛地使用在偵測網路問題以及偵測Internet的連結關係。在實際的應用中，知道前進路徑中每一個經過的節點所屬的自治領域(Autonomous System)將是非常有用的。某些現存的traceroute程式提供將路過的節點對應到該節點所屬的自治領域號碼(AS number)的功能。這個對應功能的核心在於將各節點的IP位址轉換成該節點所屬的自治領域號碼。目前所有提供此一功能的traceroute程式都是依據Internet Routing Registry (IRR)的資料做對應。但是由於網路管理人員並沒有義務去註冊以及更新IRR上的資料，導致IRR資料庫所包含的資料不夠完整也無法反應Internet的現況。
在這篇論文中，我們設計一個名為AStraceroute的AS-level traceroute程式，它可以依據最新的BGP routing table以完成最完整並且能夠反應即時網路狀況的對應。另外，AStraceroute這個工具使用TCP SYN的封包以取代傳統traceroute使用的UDP封包，這可以使探測網路的封包得以穿透防火牆以得到更完整的路徑資訊。除此之外，AStraceroute除了顯示由本地端至目的地主機之間所經過的AS路徑之外，還會同時引入了[2]所提出的方法以顯示所經過的AS之間的關係，這個功能可以讓我們對所得到的AS路徑有更深入的瞭解。
我們的研究提供一個平台以取得Internet自治領域間的連結關係。對研究網路的人而言，這可以作為自治領域間的網路結構研究之基礎；對於網路管理者而言，這個資訊可以幫助他們在日後選擇對自己比較有利的上游網路服務供應商以及對等連接的網路服務供應商。

Traceroute[1] is a network diagnostic tool originally developed by Van Jacobson to identify the IP forwarding path from local host to a destination. This tool is widely used for detecting routing problems, characterizing the end-to-end forwarding path, and discovering the Internet topology. In practice, knowing the Autonomous System (AS) associated with each hop in the forwarding path is also quite valuable. Some of the existing traceroute versions provide additional features including mapping each hop to AS number. Mapping the IP addresses of each hop to origin AS number is the core of displaying the AS forwarding path in the traceroute tool. All existing traceroute tools with AS number mapping look up the origin AS number of each hop along the forwarding path based on the Internet Routing Registry (IRR) database. However, the network operators are not obligate to register and update the information on IRR, the registration information at IRR is incomplete and out-of-date.
In this thesis, we develop a new AS-level traceroute tool named AStraceroute
to map each hop to its AS number according to the up-to-date public vailable
BGP routing tables. Additionally, AStraceroute use TCP SYN to probe hosts for bypassing the firewalls on the path which discards the original traceroute UDP datagrams. Furthermore, our traceroute tool also inference the relationships between each hop, this part is based on the heuristic in [2]. Our work provides a framework for modeling the Internet’s AS-level topology for further research and helps the network operators to make decision on selecting a right upstream AS to connect or peer with.

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Background and Related Work . . . . . . . . . . . . . . . . . . . . 3
2.1 BGP, Border Gateway Protocol . . . . . . . . . . . . . . . . . . . 3
2.2 Original Traceroute . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 AS-Level Traceroute . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 AS Relationships Inference . . . . . . . . . . . . . . . . . . . . . . 9
3 Methodology for Obtaining Routing Data . . . . . . . . . . . . . 10
3.1 Sources of AS-Level Routing Data . . . . . . . . . . . . . . . . . . 10
3.2 OurMethodology of Obtaining Data . . . . . . . . . . . . . . . . 12
4 Comparing the BGP Routing Data Sets . . . . . . . . . . . . . . 16
4.1 Persistence of IP-to-ASMapping . . . . . . . . . . . . . . . . . . 16
4.2 The Coverage of Each Data Source . . . . . . . . . . . . . . . . . 21
4.3 Quantify the Out-of-DateData in the IRR Database . . . . . . . 27
5 AS-Level Traceroute . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1 IncludingMore Databases . . . . . . . . . . . . . . . . . . . . . . 29
5.2 TCP SYN Scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3 Relationship Inference . . . . . . . . . . . . . . . . . . . . . . . . 33
5.4 Comparison of AS-Level Traceroute Tools . . . . . . . . . . . . . 37
6 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . 42
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.2 FutureWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
A Available Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
A.1 TheWHOIS Service . . . . . . . . . . . . . . . . . . . . . . . . . 45
A.2 IRRToolSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
A.3 The Cisco BGP Query Commands . . . . . . . . . . . . . . . . . 50
B Public Domain Data Sources . . . . . . . . . . . . . . . . . . . . . 53
B.1 The Public Routers . . . . . . . . . . . . . . . . . . . . . . . . . . 53
B.2 The Route Views Project . . . . . . . . . . . . . . . . . . . . . . . 55
B.3 Internet Routing Registry . . . . . . . . . . . . . . . . . . . . . . 57
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

[1] [Online]. Available: ftp://ftp.ee.lbl.gov/traceroute.tar.gz
[2] L. Gao, “On Inferring Autonomous System Relationships in the Internet,”
IEEE/ACM Transactions on Networking, vol. 9, Dec 2001.
[3] [Online]. Available: http://www.traceroute.org
[4] [Online]. Available: http://www.ris.ripe.net/
[5] [Online]. Available: http://www.routeviews.org
[6] [Online]. Available: http://www.netlantis.org
[7] Y. Rekhter and T. Li, “A Border Gateway Protocol 4 (BGP-4),” Mar 1995.
[8] [Online]. Available: http://www.iana.org/assignments/as-numbers
[9] [Online]. Available: http://www.irr.net
[10] [Online]. Available: http://www.radb.net
[11] [Online]. Available: http://www.isc.org/sw/IRRToolSet/
[12] C. Alaettinoglu, C. Villamizar, E. Gerich, D. Kessens, D. Meyer, T. Bates,
D. Karrenberg, and M. Terpstra, “Routing Policy Specification Language
(RPSL),” Jun 1999.
[13] Z. M. Mao, J. Rexford, J. Wang, and R. H. Katz, “Towards an Accurate
AS-Level Traceroute Tool,” ACM SIGCOMM, pp. 365–378, 2003.
[14] [Online]. Available: http://www.research.att.com/˜jiawang/as traceroute/
[15] H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, “Towards
Capturing Representative AS-Level Internet Topologies,” SIGMETRICS
Perform. Eval. Rev., vol. 30, no. 1, pp. 280–281, 2000.
[16] J. Xia and L. Gao, “On the Evaluation of AS Relationship Inference,” IEEE
GLOBECOM, Nov 2004.
[17] G. Battista, M. Patrignani, and M. Pizzonia, “Computing the Types of
the Relationships Between Autonomous Systems,” Proc. IEEE INFOCOM,
March 2003.
[18] [Online]. Available: http://archive.routeviews.org/oix-route-views
[19] D. Meyer, J. Schmitz, C. Orange, M. Prior, and C. Alaettinoglu, “Using
RPSL in Practice,” Aug 1999.
[20] O. Bonaventure and B. Quoitin, “Common utilizations
of the BGP community attribute,” 2003. [Online]. Available:
http://www.watersprings.org/pub/id/draft-bonaventure-quoitin-bgpcommunities-
00.txt
[21] Y. Zhang, V. Paxson, and S. Shenker, “The Stationarity of Internet Path
Properties: Routing, Loss and Throughput,” ACIRI Technical Report, May
2000.
[22] S. McCreary and B. Woodcock. [Online]. Available:
http://www.pch.net/resources/data/exchange-points
[23] [Online]. Available: http://www.iana.org/assignments/ipv4-address-space
[24] [Online]. Available: http://oppleman.com/lft/
[25] [Online]. Available: http://pwhois.org/
[26] [Online]. Available: http://pwhois.org/try.who
[27] [Online]. Available: http://www.hping.org
[28] M. A. Ruiz-S´anchez, E. W. Biersack, and W. Dabbous, “Survey and Taxonomy
of IP Address Lookup Algorithms,” IEEE Network, April 2001.
[29] [Online]. Available: http://websrv.cs.fsu.edu/reference/itl/labs/bgp/bgp.htm
[30] [Online]. Available: http://www.radb.net/mirrorlist.html
59