基于PeeringDB與BGP路由表的域間路由實(shí)驗(yàn)研究

任東東+秦董洪

摘 要：文中基于PeeringDB與BGP路由表數(shù)據(jù)，設(shè)計(jì)了一套實(shí)驗(yàn)分析框架并開發(fā)相關(guān)核心算法，包括數(shù)據(jù)集提取算法、IXP特性分析算法、域間路徑含IXP的推斷算法以及域間路徑分類算法，分析了互聯(lián)網(wǎng)交換中心（IXP）統(tǒng)計(jì)特性以及IXP對(duì)域間路由的影響。實(shí)驗(yàn)結(jié)果為評(píng)估互聯(lián)網(wǎng)發(fā)展的相關(guān)工作提供了數(shù)據(jù)依據(jù)，有效支持IXP新型體系結(jié)構(gòu)與新型域間路由服務(wù)的研究。

關(guān)鍵詞：PeeringDB；邊界網(wǎng)關(guān)協(xié)議；互聯(lián)網(wǎng)交換中心；IXP

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2017）04-00-03

0 引 言

互聯(lián)網(wǎng)由成千上萬的自治系統(tǒng)（Autonomous System， AS）互聯(lián)而成。自治系統(tǒng)AS之間通過邊界網(wǎng)關(guān)協(xié)議（Border Gate Protocol， BGP）進(jìn)行路由通信，在選擇最佳路由和路由宣告時(shí)，BGP允許各自治系統(tǒng)使用自己的管理策略[1，2]。隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，互聯(lián)網(wǎng)服務(wù)供應(yīng)商（Internet Service Provider， ISP）為節(jié)約成本及提高客戶的路由性能，ISP會(huì)與其他ISP進(jìn)行peer互連，即建立互聯(lián)網(wǎng)交換中心（Internet Exchange Point， IXP），這是互聯(lián)網(wǎng)的關(guān)鍵基礎(chǔ)設(shè)施[3]。IXP體系結(jié)構(gòu)及其算法是影響互聯(lián)網(wǎng)路由交換及域間路由的重要環(huán)節(jié)，因此有必要對(duì)IXP結(jié)構(gòu)特性與IXP對(duì)域間路徑的影響進(jìn)行深入研究。

目前通過對(duì)互聯(lián)網(wǎng)測量數(shù)據(jù)的分析計(jì)算，試圖理解互聯(lián)網(wǎng)Internet生態(tài)系統(tǒng)及其形成機(jī)制，而這也是近期互聯(lián)網(wǎng)研究的熱點(diǎn)[3-5]。盡管目前已有大量的研究工作，但基于IXP的Internet生態(tài)系統(tǒng)研究仍然是很有挑戰(zhàn)性的研究課題[4，6]。目前國內(nèi)外對(duì)IXP進(jìn)行的初步研究，均側(cè)重對(duì)IXP體系結(jié)構(gòu)、IXP流量測量等方面[4-6]，還缺乏對(duì)IXP特性及其對(duì)域間路由影響方面的定量研究與分析。本文在PeeringDB與BGP路由表等真實(shí)互聯(lián)網(wǎng)數(shù)據(jù)的基礎(chǔ)上，通過設(shè)計(jì)一套實(shí)驗(yàn)框架并開發(fā)相關(guān)分析算法，深入研究分析了IXP結(jié)構(gòu)特性及其對(duì)域間路由的影響。實(shí)驗(yàn)結(jié)果為IXP新型體系結(jié)構(gòu)、域間路由協(xié)議的設(shè)計(jì)提供了有益的指導(dǎo)與參考。

1 域間路由特性與影響因素分析

1.1 域間路由與BGP協(xié)議

邊界網(wǎng)關(guān)協(xié)議（BGP）是事實(shí)上的域間路由協(xié)議，它包括路由導(dǎo)入、路由決策和路由宣告3個(gè)基本環(huán)節(jié)[1]。

在路由導(dǎo)入環(huán)節(jié)，BGP路由器根據(jù)AS配置的本地策略，對(duì)接收到的路由進(jìn)行預(yù)處理，如果符合本地策略則修改相關(guān)路由屬性后導(dǎo)入。

路由決策是指BGP路由器在選擇某個(gè)目的網(wǎng)絡(luò)的路由時(shí)，根據(jù)優(yōu)先級(jí)比較規(guī)則，選擇唯一一條最優(yōu)路由裝入轉(zhuǎn)發(fā)表中。

路由宣告指BGP路由器按照本地策略決定是否宣告該路由到鄰居BGP路由器中，每個(gè)目的網(wǎng)絡(luò)僅宣告一條最佳路由。AS在路由宣告時(shí)需要考慮商業(yè)關(guān)系的限制并遵循2條指導(dǎo)原則[1，2]，即AS宣告其自身和客戶路由給供應(yīng)商和對(duì)等服務(wù)商；AS接收客戶的所有路由，并宣告所有路由給客戶。

1.2 域間路由影響因素分析

1.2.1 多宿主（Multi-home）

為了提高互聯(lián)網(wǎng)的可靠性與健壯性，AS利用多宿主技術(shù)[4]通過使用多個(gè)ISP接入互聯(lián)網(wǎng)，獲得多條鏈路與Internet連接，從而建立一個(gè)可靠的網(wǎng)絡(luò)。多宿主技術(shù)對(duì)域間路由的影響主要包括以下兩方面：

（1）讓更多的邊緣AS加入互聯(lián)網(wǎng)，導(dǎo)致路由表規(guī)模的爆炸式增長；

（2）使用備份路徑改進(jìn)了AS網(wǎng)絡(luò)的可靠性。

1.2.2 對(duì)等互聯(lián)（Peer）與IXP

對(duì)等互聯(lián)（Peer）是指兩個(gè)AS互相為對(duì)方交換各自客戶路由信息而建立的網(wǎng)絡(luò)互連，但它們不會(huì)交換來自各自供應(yīng)商和其他對(duì)等AS的路由信息[3，4]。互聯(lián)網(wǎng)交換點(diǎn)（Internet Exchange Point， IXP）是由多個(gè)ISP或大型AS建立用來交換域間路由和流量的基礎(chǔ)設(shè)施[3，4]。IXP由一個(gè)以太局域網(wǎng)構(gòu)成，主要包括路由服務(wù)器（Route Server）和交換機(jī)，各ISP通過接入該局域網(wǎng)實(shí)現(xiàn)數(shù)據(jù)的互聯(lián)互通，各ISP通過路由服務(wù)器（Route Server）進(jìn)行路由數(shù)據(jù)的交換，ISP之間的流量則通過交換機(jī)完成。ISP之間建立IXP的主要優(yōu)勢包括以下兩方面：

（1）提高客戶路由性能，通過減少路徑長度達(dá)到降低網(wǎng)絡(luò)延遲的目的；

（2）節(jié)省轉(zhuǎn)發(fā)成本，通過降低上游ISP的轉(zhuǎn)發(fā)流量從而節(jié)省運(yùn)營成本。

2 數(shù)據(jù)集介紹

簡要介紹本文使用的兩個(gè)數(shù)據(jù)集——來自Routeviews項(xiàng)目[7]的BGP路由表與PeeringDB數(shù)據(jù)[8]。

BGP路由表：該數(shù)據(jù)集來自美國Oregon大學(xué)高級(jí)網(wǎng)絡(luò)中心的Routeviews項(xiàng)目，該項(xiàng)目的主要目標(biāo)是從多個(gè)不同自治系統(tǒng)的角度獲取全球Internet的路由視圖。Routeviews項(xiàng)目中的任意一臺(tái)路由器使用外部邊界網(wǎng)關(guān)協(xié)議（EBGP）對(duì)等會(huì)話并與多個(gè)AS相連，將收集到的路由信息存儲(chǔ)起來；這些路由器不通告任何信息給鄰居以免對(duì)全球域間系統(tǒng)造成影響。Routeviews項(xiàng)目采集的BGP路由表數(shù)據(jù)有Cisco格式和Zebra格式。本文實(shí)驗(yàn)選用的BGP路由表來自oix-route-views.routeviews.org路由器，該路由器與19個(gè)AS建立了26個(gè)對(duì)等會(huì)話，各項(xiàng)性能比較穩(wěn)定，捕獲了當(dāng)前Internet較為完整的域間路由視圖。

PeeringDB數(shù)據(jù)： PeeringDB是存儲(chǔ)ISP對(duì)等互連（Peering）信息并以Web展示的數(shù)據(jù)庫。該數(shù)據(jù)庫信息主要包括IXP相關(guān)信息與AS相關(guān)信息。IXP相關(guān)信息包括IXP地理位置，IXP成員，接入策略，互連策略與協(xié)議、聯(lián)系方式等；AS相關(guān)信息包括機(jī)構(gòu)名稱，AS號(hào)碼，IPv4宣告前綴、IPv6宣告前綴、流量類型（Traffic Ratios）等。該數(shù)據(jù)庫是了解全球網(wǎng)絡(luò)互連、IXP信息最權(quán)威的數(shù)據(jù)源，這些數(shù)據(jù)均由ISP定期維護(hù)更新。

3 實(shí)驗(yàn)設(shè)計(jì)與分析框架

3.1 總體設(shè)計(jì)框架

為了理解IXP結(jié)構(gòu)特性及其對(duì)域間路由的影響，我們?cè)赑eeringDB與BGP路由表基礎(chǔ)上設(shè)計(jì)了一個(gè)總體實(shí)驗(yàn)分析框架并開發(fā)了相關(guān)分析算法?？傮w實(shí)驗(yàn)框架如圖1所示。

3.2 實(shí)驗(yàn)指標(biāo)（屬性）的選取與分析

在實(shí)驗(yàn)設(shè)計(jì)中，我們選擇了4個(gè)主要的實(shí)驗(yàn)指標(biāo)。在IXP特性方面，主要考察IXP規(guī)模（即IXP所含AS成員的數(shù)目及其分布）與IXP全球分布；在IXP對(duì)域間路由的影響方面，主要考察域間路徑所含IXP數(shù)目與分布、域間路徑類型的分布。

3.3 分析算法設(shè)計(jì)

3.3.1 數(shù)據(jù)集獲取算法

目前IXP數(shù)據(jù)只有在PeeringDB （https：//www.peeringdb.com）存在，該數(shù)據(jù)格式采用基于Web的非結(jié)構(gòu)化形式呈現(xiàn)。為了方便實(shí)驗(yàn)，我們使用由python語言編寫的數(shù)據(jù)提取程序從該網(wǎng)站上抓取了實(shí)驗(yàn)所需的數(shù)據(jù)集。PeeringDB數(shù)據(jù)提取程序如下：

for each IXP：

for j=1，...，n

//send command to get the json_data

if len（json_data.keys（）） > 1：

asn = json_data['data'][0]['asn']

ix_num = len（json_data['data'][0]['netixlan_set']）

num = 0；

while （num < ix_num）：

ix_id=json_data['data'][0]['netixlan_set'][num]['ix_id']

if （dict.has_key（ix_id））：

dict[ix_id] = dict[ix_id] + ' ' + str（asn）

else：

dict[ix_id] = str（asn）

num = num + 1；

3.3.2 域間路徑含IXP的推斷

目前BGP路由表沒有包含或采集IXP的相關(guān)信息，所以無法了解域間路徑是否經(jīng)過IXP并經(jīng)過多少個(gè)IXP。若要統(tǒng)計(jì)這些數(shù)據(jù)，需要設(shè)計(jì)相應(yīng)的推斷算法，即根據(jù)BGP路由表與PeeringDB數(shù)據(jù)進(jìn)行推斷。通過PeeringDB我們可以知道每個(gè)IXP含有的AS成員，而對(duì)于BGP路由表中的任意一條域間路徑，可以測算該域間路徑中的任何一條邊（由兩個(gè)AS構(gòu)成）是否為某個(gè)IXP的成員，若是，則表明該邊包含了該IXP。具體推算算法如下：

pdb=obtainfrom（"www.peeringdb.com"）；

nixp=0；

do{

epath = getonepath（BGPrib）

for elink in epath

[as1，as2]=gettwoAS（elink）；

for eixp in pdb

if as1&as2 in eixp

nixp++；

else

continue；

}while empty（BGPrib）

3.3.3 域間路徑類型的計(jì)算

為了評(píng)估域間路徑是否經(jīng)過不同國家的自治系統(tǒng)AS，必須利用互聯(lián)網(wǎng)路由注冊(cè)IRR平臺(tái)[9]（Internet Routing Registry， IRR）提供的AS信息，該信息必須使用專門API向WHOIS服務(wù)器[10]查詢獲取。對(duì)于BGP路由表中的任意一條域間路徑，檢測該路徑上各AS所屬國別信息，最后可以統(tǒng)計(jì)出該域間路徑是否經(jīng)過不同國家所在的AS以及經(jīng)過國家的數(shù)目，從而推斷出域間路徑的類型。域間路徑推斷算法如下：

set cntr[]；

do{

epath = getonepath（BGPrib）

for enode in epath

asinf=whois（enode）；

cntr.add（asinf.country）；

num[epath]=len（cntr）；

}while empty（BGPrib）

4 實(shí)驗(yàn)結(jié)果

本節(jié)給出IXP規(guī)模、IXP全球地域分布、域間路徑含IXP的分布特性以及域間路徑類型等實(shí)驗(yàn)結(jié)果。

4.1 IXP規(guī)模與分布

一個(gè)IXP通常由多個(gè)AS或ISP構(gòu)成，其成員數(shù)通常為幾十或幾百個(gè)。實(shí)驗(yàn)給出了AS成員規(guī)模的統(tǒng)計(jì)分布，如圖2所示。目前整個(gè)互聯(lián)網(wǎng)有465個(gè)IXP，而位于荷蘭首都阿姆斯特丹的Amsterdam Internet Exchange （AIE） 是全球最大的IXP，它包含733個(gè)AS成員；在全球的465個(gè)IXP中超過50個(gè)AS成員的IXP有72個(gè)。鑒于IXP所含AS成員規(guī)模較大的問題，在IXP體系結(jié)構(gòu)及其交換算法設(shè)計(jì)時(shí)，必須考慮到它們的擴(kuò)展性尤其是Route Server路由交換性能方面的擴(kuò)展性。

4.2 IXP地域分布

目前全球有465個(gè)IXP交換點(diǎn)，但是地域分布極為不均，歐美發(fā)達(dá)國家IXP數(shù)量多，發(fā)展中國家IXP數(shù)量少。目前我國IXP個(gè)數(shù)為6，主要分布在香港、北京和上海等地。通常IXP數(shù)量體現(xiàn)了一個(gè)國家互聯(lián)網(wǎng)發(fā)展程度的高低。例如，互聯(lián)網(wǎng)最發(fā)達(dá)的美國擁有86個(gè)IXP，約占全球的18.5%；巴西，俄羅斯和德國的IXP數(shù)量均超過20；法國、日本、澳大利亞和阿根廷的IXP數(shù)量超過10。上述8個(gè)互聯(lián)網(wǎng)最發(fā)達(dá)國家所擁有的IXP數(shù)量占全球的46.7%，幾乎接近全球IXP數(shù)量的一半，而其他所有國家的IXP數(shù)量只占53.3%。全球IXP所在國分布見表1所列。

4.3 域間路徑含IXP的統(tǒng)計(jì)

域間路徑所含IXP的數(shù)目與分布如圖3所示。圖2給出不含IXP、含1個(gè)IXP和2個(gè)以上IXP的域間路徑所占比例，其中不含IXP的域間路徑比例為41.9%，含1個(gè)或2個(gè)以上IXP的域間路徑占58.1%。實(shí)驗(yàn)表明，不含IXP的域間路徑占比過多，在一定程度上顯示出IXP數(shù)量不夠，影響到域間路徑的路由性能。若此類域間路徑比例減少，則AS會(huì)通過更多的IXP來改善互聯(lián)網(wǎng)域間路徑的路由性能。

4.4 域間路徑類型統(tǒng)計(jì)

基于BGP路由表以及Whois所含的AS信息，我們推斷了域間路徑類型及分布。圖4所示為不同國家的域間路徑分布。數(shù)據(jù)顯示，不經(jīng)過第三方國家的域間路徑占比為29%，經(jīng)過一個(gè)第三方國家的域間路徑占比為44%，經(jīng)過多個(gè)第三方國家的域間路徑占比為25%。因此，本地路徑與多國路徑大致比例為1∶3，由于缺乏足夠的IXP而使得許多域間路徑必須經(jīng)過其他國家的ISP進(jìn)行路由交換，從而導(dǎo)致路由性能下降，路由成本增加。

5 結(jié) 語

本文基于PeeringDB與域間路由表，針對(duì)IXP結(jié)構(gòu)特性與IXP對(duì)域間路徑的影響進(jìn)行了相關(guān)的統(tǒng)計(jì)分析研究，主要分析結(jié)果顯示，IXP的AS成員規(guī)模變化較大，建議IXP體系結(jié)構(gòu)與算法在設(shè)計(jì)時(shí)必須考慮Route Server路由交換的擴(kuò)展性；至少經(jīng)過2個(gè)國家的域間路徑占比約為69%，表明目前IXP數(shù)量不足影響到互聯(lián)網(wǎng)路由交換的效率，導(dǎo)致路由性能下降以及路由成本增加。以上分析結(jié)果為評(píng)估IXP建設(shè)與發(fā)展的相關(guān)工作提供了數(shù)據(jù)依據(jù)，同時(shí)可以有效支持未來IXP新型體系結(jié)構(gòu)與域間路由的研究。

參考文獻(xiàn)

[1] Rekhter Y， Li T， Hares S. A border gateway protocol 4 （BGP-4）. RFC 4271[Z]. Internet Engineering Task Force， January 2006.

[2] 楊家海， 焦亮， 秦董洪，等.基于BGP路由表的域間路徑特性實(shí)驗(yàn)研究[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2015， 55（11）： 1190-1196.

[3] Brice Augustin ， Balachander Krishnamurthy ， Walter Willinger.IXPs： mapped[C].Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference， 2009， Chicago， Illinois， USA.

[4] Nikolaos Chatzis ， Georgios Smaragdakis ， Jan B?ttger ，et al.On the benefits of using a large IXP as an internet vantage point[C].Proceedings of the 2013 conference on Internet measurement conference， 2013， Barcelona， Spain.

[5] Gupta， A.， Vanbever， L.， Shahbaz， M.， et al. SDX： A Software Defined Internet Exchange[J]. Acm Sigcomm Computer Communication Review， 2014， 44（4）：579-580.

[6] Labovitz， C.， Iekel-Johnson， S.， Mcpherson D，et al.Internet inter-domain traffic[J].Acm Sigcomm Conference on Applications， 2010， 40（4）：75-86.

[7] University of Oregon Route Views Project[EB/OL]. http：//www.routeviews.org/.

[8] PeeringDB[EB/OL]. https：//www.peeringdb.com.

[9] Internet Routing Registry（IRR） [EB/OL].http：//www.irr.net/.

[10] Internet whois service[EB/OL].http：//www.whois.net/.

[11] 張衛(wèi)國.互聯(lián)網(wǎng)可擴(kuò)展路由算法研究[D].北京：清華大學(xué)， 2010.