An Anticipation of Inter-Domain Routing Path

邊界閘道協定（BGP）是現今網際網路上各個網際網路服務提供者（ISP）或自治區（Autonomous System）之間運作的重要協定，現行的邊界閘道協定使用的是第四版的改良版本，第四版的邊界閘道協定與之前版本主要的不同是支援領域間無階級路由（CIDR），也因此網際網路上的路由數量每年都有相當大的成長，現今絕大多數的網際網路服務提供者及自治區都是利用邊界閘道協定動態地交換路由（Routing）資訊，利用邊界閘道協定多樣的控制及設定方式實行不同的路由政策（Policy）以控制網路流量由本身自治區內流出路徑；並藉由不同的設定影響網際網路上流入本身自治區的路徑。 現今的邊界閘道協定已經經過近十年的使用，絕大多數的路由器（Router）也都支援這個協定，但是因為邊界閘道協定與網際網路服務提供者或自治區有密切的關係，而且邊界閘道協定的參數及設定多樣化，並沒有一個策略準則可以適用於每一個網際網路服務提供者或自治區。而因為自治區提供的路徑對於網際網路上封包的傳輸有相當大的影響，因此如何找到適合自己自治區的網路服務提供者與找出自治區之間的路由便是一個相當重要的課題。所以在本篇論文中，我們提出一個方法利用公開但是有限的資源來推測自治區之間的路由，藉由這些路由的比較我們可以進一步得知自治區提供路由的優劣。 國際間對於邊界閘道協定的研究與資料歷年來持續地增加中，這代表對於網際網路現實環境的研究越來越受到重視，國內在這方面的發展與研究相對來說是極少的，可能的原因應該有：國內網際網路服務提供者對外的資訊不夠透明；相關的研究人員與專業人員間缺乏互動等等。 我們希望藉由這個研究，能打開國內對邊界閘道協定研究的大門，最後希望我們的研究可以提供各個自治區在做互聯關係建立時一個較佳的選擇。Border Gateway Protocol (BGP) routing protocol is the most important routing protocol between the Internet Service Providers (ISPs) or Autonomous Systems (ASs) in the Internet. The current version of BGP is 4. BGPv4 is formulated in 1995, and the most difference to the previous version is BGPv4 supporting Classless InterDomain Routing (CIDR). Almost all ISPs and ASs are using BGP to exchange routing table with each other. By using the settings and control elements of BGP, ISPs and ASs could implement different routing policies when they exchange BGP routes. ISPs and ASs could use different BGP policies to control the outbound network traffic, and influence inbound network traffic. Although BGP is working in the Internet almost a decade and most router support BGP today, there is no a set of policies or settings suitable for every ISP and AS. But AS routing path has high relative to packet forwarding in the Internet. Therefore how to find the more suitable way of setting AS policies and the relationship between ASs are important. In this thesis, we propose a methodology to infer AS routing paths by limited AS path resources in the Internet. And we could know which AS provides the best path for us by using our results. The research efforts about BGP and the Internet are getting more and more in those few years. But there are few papers about BGP or the Internet in our nation. The reasons might be that there is no enough routing information in public, and there is little interaction between researchers and the Internet operators here. We hope this work could give another view of BGP and could help ASs to know the correct settings and paths between ASs.1 Introduction ................................ 1 1.1 Routing Protocol Introduction ............... 1 1.2 BGP Introduction ............................ 4 1.2.1 BGP terminology ............................. 4 1.2.2 BGP Routing Control ......................... 7 1.2.3 BGP Best Path Selection ..................... 8 1.2.4 BGP Connection ............................. 10 1.3 Thesis Organization ........................ 12 2 Related Work ............................... 13 2.1 Internet Routing Growth .................... 14 2.2 Internet Routing Policies .................. 15 2.3 AS Relationship ............................ 17 2.4 AS Topologies .............................. 18 3 Proposed Inferring Methodology ............. 19 3.1 Extract AS routing ......................... 24 3.2 AS_DEGREE .................................. 25 3.3 Erase Repeat AS Paths ...................... 28 3.4 Possible Path for Source-Destination Pair .. 30 3.5 Best Path Prediction ....................... 31 4 Performance Evaluation ..................... 32 4.1 Best Path Prediction Result ................ 33 4.2 Reasons for Missing Best Path .............. 40 5 Concluding Remarks ......................... 42 5.1 Conclusions ................................ 42 5.2 Future Work ................................ 43 References ........................................ 44 Appendix .......................................... 4