一種復(fù)合的自治域級拓?fù)浒l(fā)現(xiàn)方法

胡一非，程　光

(1. 東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 211189；2. 東南大學(xué) 計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 211189)

?

一種復(fù)合的自治域級拓?fù)浒l(fā)現(xiàn)方法

胡一非1,2，程光1,2

(1. 東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 211189；2. 東南大學(xué) 計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 211189)

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，面對新的挑戰(zhàn)，傳統(tǒng)網(wǎng)絡(luò)逐漸力不從心，軟件定義網(wǎng)絡(luò)(software-defined network,SDN)領(lǐng)銜的未來網(wǎng)絡(luò)應(yīng)運(yùn)而生，隨之而來的是各類網(wǎng)絡(luò)測量技術(shù)紛紛針對未來網(wǎng)絡(luò)發(fā)生演變，但拓?fù)浣Y(jié)構(gòu)測量在傳統(tǒng)網(wǎng)絡(luò)環(huán)境下的作用仍然不可忽視。在自治域級的網(wǎng)絡(luò)拓?fù)渲校總€(gè)自治域都可以簡化為一個(gè)點(diǎn),而用兩點(diǎn)之間的連線表示自治域間的鄰接關(guān)系。近年來有許多相關(guān)的研究展示了不同的拓?fù)浒l(fā)現(xiàn)算法。提出了一種簡單高效的方法來推斷自治域級的拓?fù)?利用在網(wǎng)絡(luò)中部署高速采集器采集邊界網(wǎng)關(guān)協(xié)議(border gateway protocol,BGP)路由器上的路由表以及BGP協(xié)議的更新信息來推斷網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并判定自治域的相關(guān)屬性。實(shí)驗(yàn)證明了該方法能夠達(dá)到預(yù)期效果，全面、準(zhǔn)確地推斷網(wǎng)絡(luò)在自治域級的拓?fù)浣Y(jié)構(gòu)。

自治域；拓?fù)浒l(fā)現(xiàn)；邊界網(wǎng)關(guān)協(xié)議(BGP)

0　引　言

近幾年來互聯(lián)網(wǎng)飛速發(fā)展，網(wǎng)絡(luò)的規(guī)模變得越來越龐大，結(jié)構(gòu)也越來越復(fù)雜。由于傳統(tǒng)網(wǎng)絡(luò)的一些固有缺陷導(dǎo)致未來網(wǎng)絡(luò)逐漸興起，吸引了大量研究者的關(guān)注，各國爭相建設(shè)相關(guān)的基礎(chǔ)設(shè)施，在這方面，我國建成了目前世界上最大的IPv6網(wǎng)絡(luò)中國下一代互聯(lián)網(wǎng)(China next generation internet，CNGI)。雖然網(wǎng)絡(luò)技術(shù)在進(jìn)步，但在新的網(wǎng)絡(luò)體系結(jié)構(gòu)中，拓?fù)錅y量仍然顯得尤為重要，不僅為各類創(chuàng)新型實(shí)驗(yàn)提供了基本的服務(wù)，而且在例如分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)屬性[1]、推斷網(wǎng)絡(luò)層級結(jié)構(gòu)[2]、在仿真軟件中構(gòu)造拓?fù)渖善鱗3]以及診斷網(wǎng)絡(luò)故障等任務(wù)中均有著不可缺的作用。目前互聯(lián)網(wǎng)的結(jié)構(gòu)可以看作許多互相連接的子網(wǎng)絡(luò)，我們把這些子網(wǎng)絡(luò)稱之為自治域(autonomous system，AS)，而邊界網(wǎng)關(guān)協(xié)議[4](border gateway protocol,BGP)就是運(yùn)行在自治域間用來交換連接信息一種域間路由協(xié)議。對于整個(gè)互聯(lián)網(wǎng)，如果不關(guān)注自治域內(nèi)的結(jié)構(gòu)就可以被視作一張圖，每個(gè)自治域?yàn)橐粋€(gè)點(diǎn)，而自治域之間的連接則為一條邊。

自治域級的拓?fù)浣Y(jié)構(gòu)可以通過BGP的路由信息來推斷。BGP路由表中的每一項(xiàng)都包含了一個(gè)“AS路徑”的屬性，記錄了到達(dá)一個(gè)特定IP地址前綴所經(jīng)過的AS號，通過求出多個(gè)BGP路由表中的“AS路徑”的并集，我們可以對網(wǎng)絡(luò)的拓?fù)渥鲆粋€(gè)大致的推斷；另外，由于網(wǎng)絡(luò)波動(dòng)，鏈路故障及配置錯(cuò)誤等原因觸發(fā)的BGP更新報(bào)文也包含了“AS路徑”這一屬性，因此，可以用來作為通過BGP路由表推斷出拓?fù)涞囊环N補(bǔ)充。本文依托國防科技大學(xué)面向廣域網(wǎng)實(shí)驗(yàn)床的軟件定義組網(wǎng)方法-軟件定義實(shí)驗(yàn)床(software difined testbed,SDTB)，提出了一種通過采集BGP路由表和BGP路由更新信息來推斷自治域級拓?fù)涞姆椒?，并為二維路由實(shí)驗(yàn)和 IPv6 大規(guī)模編址實(shí)驗(yàn)提供了支撐，相比其他方法，可以用最小的代價(jià)得到最完整的拓?fù)湫畔?，另外，還提供了一系列相關(guān)的輔助拓?fù)湫畔?，比如時(shí)間戳，結(jié)點(diǎn)類型等，方便用戶決策。

1　相關(guān)工作

拓?fù)浒l(fā)現(xiàn)一直以來都是一個(gè)很有價(jià)值的研究問題，很多研究者在這一方面已經(jīng)取得了很多成果。目前主流的方法分為主動(dòng)和被動(dòng)2種。文獻(xiàn)[5]介紹了一種通過主動(dòng)發(fā)送探測包,采集往返時(shí)延(round trip time,RTT)時(shí)延信息，從而推斷拓?fù)浣Y(jié)構(gòu)的方法，分析比較了幾個(gè)影響實(shí)驗(yàn)結(jié)果的重要因素，并著重展示了4種圖形化拓?fù)浣Y(jié)構(gòu)的技術(shù)，文獻(xiàn)[6-7]提出了另一種主動(dòng)測量的啟發(fā)式方法來推測自治域級的拓?fù)浣Y(jié)構(gòu)，但主要采集的是traceroute的數(shù)據(jù)，通過首先得到路由級的拓?fù)涠瓮茢嘧灾斡蚣壍耐負(fù)?，難點(diǎn)在于要建立一個(gè)IP地址與AS編號的映射，以及如何確定一臺路由器是否為邊界路由器。針對邊界路由器的判斷，文獻(xiàn)[8]給出了一種基于規(guī)則的新方法，區(qū)別于傳統(tǒng)的基于別名的方法，有更好的性能表現(xiàn)。以上是一些主動(dòng)測量的方法，能夠在精度以及信息覆蓋面上更勝被動(dòng)測量一籌，但邊界路由器的判定算法過于復(fù)雜，導(dǎo)致測量周期太長，且過分依賴現(xiàn)有的映射信息數(shù)據(jù)庫，當(dāng)處在實(shí)驗(yàn)網(wǎng)絡(luò)或仿真網(wǎng)絡(luò)環(huán)境而非真實(shí)互聯(lián)網(wǎng)時(shí)則有很大困難。文獻(xiàn)[9]指出在大規(guī)模的網(wǎng)絡(luò)環(huán)境中，通過發(fā)送traceroute主動(dòng)探測包發(fā)現(xiàn)拓?fù)鋾a(chǎn)生大量冗余流量的缺點(diǎn)。在引入Bloom Filter來降低冗余流量的同時(shí)，將監(jiān)測站按流量目的地址進(jìn)行分組，進(jìn)一步緩解了在網(wǎng)絡(luò)規(guī)模較大時(shí)性能下降的問題。相比主動(dòng)測量方法，被動(dòng)方法在難度上要低，同時(shí)具有精度低，信息覆蓋面小的問題，文獻(xiàn)[10]最早采用了純被動(dòng)的方法，采集BGP更新報(bào)文，通過對IP地址前綴以不同的更新頻度來聚類，推斷網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。另外，RouteView[11]和歐洲IP網(wǎng)絡(luò)路由信息服務(wù)(réseaux IP européens routing information service,RIPERIS)[12]是2個(gè)著名的采集真實(shí)互聯(lián)網(wǎng)BGP信息的項(xiàng)目，它們通過部署在全球各自的節(jié)點(diǎn)，采集來自互聯(lián)網(wǎng)的真實(shí)BGP信息，為研究者提供第一手的數(shù)據(jù)資料。

2　拓?fù)浒l(fā)現(xiàn)算法

2.1基于BGP路由表

BGP協(xié)議與開放式最短路徑優(yōu)先(open shortest path first,OSPF)[13]等鏈路狀態(tài)協(xié)議不同，它并不維護(hù)一個(gè)全局的視圖，每個(gè)運(yùn)行BGP協(xié)議的邊界路由器選擇它認(rèn)為最好的路徑并廣播給它的鄰居，導(dǎo)致的結(jié)果就是每一個(gè)不同的路由器都有可能存儲著不同的路徑信息；另外，同一個(gè)自治域中可能會存在多個(gè)邊界路由器，它們之間采用內(nèi)部網(wǎng)關(guān)協(xié)議(interior gateway protocol,IGP)交換路由信息，一個(gè)邊界路由器可能會“隱藏”在另一邊界路由器的后面。圖1為未接入采集器網(wǎng)絡(luò)拓?fù)鋱D。圖1中，路由器n1至n7都是自治域中的邊界路由器，運(yùn)行BGP協(xié)議，路由器n6到其他自治域的路徑都要通過路由器n1，換句話說，對n6來說，n1屏蔽了大部分路由信息。這就決定了只從一個(gè)單獨(dú)的節(jié)點(diǎn)中提取的信息不足以反映整個(gè)網(wǎng)絡(luò)的拓?fù)洌覀冃枰⒁惶紫⒉杉瘷C(jī)制來最大可能地獲取更加全面的拓?fù)湫畔?。因此，我們在網(wǎng)絡(luò)中部署了一臺BGP信息采集器用來與各BGP路由器通信，抓取路由表。采集器與待測量網(wǎng)絡(luò)中盡可能多的節(jié)點(diǎn)相連，同樣運(yùn)行BGP協(xié)議，但不同的是采集器只接收來自其他BGP路由器的更新報(bào)文，而不會向他的鄰居廣播自身存儲的路由信息。這樣配置是為了保證在采集到盡可能多的路由表的前提下，不影響整個(gè)網(wǎng)絡(luò)的正常通信，否則，將有大量的正常數(shù)據(jù)流量被引導(dǎo)到采集器上。

我們在實(shí)驗(yàn)拓?fù)渲屑尤肓艘慌_采集器，其網(wǎng)絡(luò)拓?fù)淙鐖D2所示。由于實(shí)驗(yàn)網(wǎng)絡(luò)規(guī)模較小，我們將采集器與所有的邊界路由器連接，對每個(gè)邊界路由器而言，它們只是增加了一個(gè)鄰居，即后來部署的采集器，但由于采集器不廣播任何路由消息，其他邊界路由器只會定期廣播自己的可達(dá)網(wǎng)絡(luò)消息，并不會將流量引導(dǎo)到采集器上。同時(shí)，采集器又與普通邊界路由器一樣，從各鄰居路由器廣播的路由消息中推導(dǎo)出路徑信息，存儲在自身的路由表中。

一個(gè)典型的BGP路由表的結(jié)構(gòu)如表1所示，主要提取“AS路徑”這一屬性來推斷拓?fù)浣Y(jié)構(gòu)?！癆S路徑”是BGP路由表項(xiàng)中一項(xiàng)公認(rèn)的強(qiáng)制屬性，它表示到達(dá)目的前綴地址需要經(jīng)過的一系列AS號。以表1中這條表項(xiàng)為例，這是一個(gè)通往10.0.0.0/24網(wǎng)段的路徑，下一條地址是10.0.7.1，“AS路徑”屬性中包含了AS12，AS34，AS56，說明要到達(dá)目標(biāo)網(wǎng)絡(luò)，需要依次經(jīng)過12，34，56這3個(gè)自治域，由于是依次傳播的，顯而易見每2個(gè)自治域之間是連通的，即存在12—34，34—56這2條路徑。由此可見，通過提取“AS路徑”中的鄰接信息，是可以推斷出網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的。圖3表示了從“AS路徑”推斷拓?fù)涞乃惴鞒?。首先將拓?fù)涑跏蓟癁榭?，從采集器中的路由表中提取每一?xiàng)“AS路徑”屬性，將其中相鄰的2個(gè)AS號之間標(biāo)記為“連通”，重復(fù)此過程直至處理完所有“AS路徑”，得到初步推斷的結(jié)果。

圖1　未接入采集器網(wǎng)絡(luò)拓?fù)?　　Fig.1　Topology without acquisition

圖2　接入采集器后網(wǎng)絡(luò)拓?fù)洹　ig.2　Topology with acquisition

優(yōu)選路徑前綴地址下一跳度量值本地優(yōu)先級權(quán)重AS路徑*i10.0.0.0/2410.0.7.111000123456

2.2基于更新信息

互聯(lián)網(wǎng)是一個(gè)龐大且動(dòng)態(tài)的結(jié)構(gòu)，每一秒都會有成千上萬的節(jié)點(diǎn)加入和退出，如果再考慮網(wǎng)絡(luò)故障以及配置錯(cuò)誤等因素，僅僅靠靜態(tài)的路由表推斷出的拓?fù)浣Y(jié)構(gòu)一定是不準(zhǔn)確的，最多只能算是某一時(shí)刻的狀態(tài)。而BGP路由表也不能準(zhǔn)確地反映網(wǎng)絡(luò)中數(shù)據(jù)包的傳播路徑，因?yàn)槁酚杀頃x擇到一個(gè)特定前綴地址的最佳路徑，忽略其余的，但BGP更新消息卻可以保留多條路徑。所以，在通過采集器上的路由表推斷出拓?fù)浜?，還需要持續(xù)地接收BGP更新消息，從而獲得更加全面和完整的拓?fù)湫畔ⅰ?/p>

BGP更新消息是BGP 4種消息類型之一，也是最主要的一種，負(fù)責(zé)在自治域傳遞路由更新信息。它的結(jié)構(gòu)與BGP路由表的結(jié)構(gòu)非常類似，同樣，我們利用“AS路徑”這一屬性來推斷拓?fù)浣Y(jié)構(gòu)。一條BGP更新消息可能同時(shí)新增一條路徑和撤銷一條已有的路徑。對于新增的路徑，只需要簡單地將AS鄰接信息設(shè)為“連通”，并補(bǔ)充進(jìn)現(xiàn)有的拓?fù)渲?。但對于撤銷的路徑，不能草率地將相關(guān)的“連通”信息刪除，因?yàn)榭赡苤皇浅霈F(xiàn)了一條“更優(yōu)”的路徑，而非物理連接的斷開。針對上述情況，設(shè)計(jì)了一種判定自治域或鏈路是否“消失”的算法，流程如圖4所示，我們事先定義好一個(gè)閾值Δt，當(dāng)接收到撤銷報(bào)文時(shí)記錄當(dāng)前時(shí)刻，并且在超過這個(gè)閾值之后，如果該報(bào)文中撤銷的自治域號以及相關(guān)路徑都不在各路由器的路由表中出現(xiàn)，則認(rèn)為該自治域或域間連接信息不存在，將其對應(yīng)的“連通”關(guān)系從現(xiàn)有拓?fù)渲袆h除。根據(jù)網(wǎng)絡(luò)規(guī)模的差異，可以改變閾值Δt的大小，本文主要采用圖1和圖2中的小型實(shí)驗(yàn)網(wǎng)絡(luò)，Δt設(shè)置為3 min，在真實(shí)的互聯(lián)網(wǎng)當(dāng)中，全球的自治域已經(jīng)多達(dá)數(shù)十萬個(gè)，BGP路由表收斂時(shí)間長達(dá)幾十分鐘[14]，Δt可能被設(shè)置為數(shù)小時(shí)。

圖3　拓?fù)浒l(fā)現(xiàn)算法流程Fig.3　Process of topology discovery

圖4　BGP路由撤銷消息處理流程Fig.4　Process of withdraw message

BGP協(xié)議[4]規(guī)定，當(dāng)路由消息從一個(gè)自治域傳遞到另一個(gè)自治域時(shí)，需要在“AS路徑”的最前面加上最后一個(gè)新到達(dá)的自治域號，同一個(gè)自治域內(nèi)2個(gè)邊界路由器通過IGP協(xié)議傳遞路由信息時(shí)，不需要在“AS路徑”里添加多個(gè)相同的AS號，所以，通常情況下“AS路徑”中的AS號不會出現(xiàn)重復(fù)，但因?yàn)楸镜嘏渲玫仍蛞部赡軙霈F(xiàn)連續(xù)重復(fù)的AS號，這種情況下，我們把連續(xù)出現(xiàn)的AS合并為一個(gè)，然后再按照正常的算法步驟進(jìn)行計(jì)算。

2.3transit節(jié)點(diǎn)和stub節(jié)點(diǎn)的判定方法

我們把網(wǎng)絡(luò)中的自治域分成2種類型：transit和stub。在網(wǎng)絡(luò)拓?fù)鋱D中，stub節(jié)點(diǎn)只出現(xiàn)在一條路徑的兩端，它不向其他節(jié)點(diǎn)提供中轉(zhuǎn)服務(wù)，即網(wǎng)絡(luò)中的流量不能經(jīng)由它到達(dá)其他節(jié)點(diǎn)。除此之外的其他節(jié)點(diǎn)則為transit節(jié)點(diǎn)，因?yàn)樗鼈兇嬖谟诼窂降闹虚g，為其他節(jié)點(diǎn)提供中轉(zhuǎn)服務(wù)。由上述定義得出以下2點(diǎn)結(jié)論。

1)在“AS路徑”中，處在中間的節(jié)點(diǎn)一定是transit節(jié)點(diǎn)。設(shè)它為x，x的前一個(gè)節(jié)點(diǎn)為a，后一個(gè)節(jié)點(diǎn)為b，可知流量從a經(jīng)過x再到另一個(gè)自治域b，符合了transit節(jié)點(diǎn)的特征。

2)在“AS路徑”中，處在第一個(gè)和最后一個(gè)的節(jié)點(diǎn)不一定是stub節(jié)點(diǎn)，因?yàn)榇嬖谶@種情況：一個(gè)AS在某一條路由表項(xiàng)是端節(jié)點(diǎn)，但在另一條表項(xiàng)中成為了中間節(jié)點(diǎn)。

明確了上述2點(diǎn)之后，我們提出一種判定transit節(jié)點(diǎn)和stub節(jié)點(diǎn)的方法，如圖5所示。在采集器的路由表中，遍歷所有表項(xiàng)的“AS路徑”屬性，設(shè)所有出現(xiàn)過的AS為集合c，將每個(gè)“AS路徑”中第一個(gè)和最后一個(gè)刪除，將剩余的所有結(jié)點(diǎn)歸為transit節(jié)點(diǎn)，設(shè)為集合t，最后，c-t的部分歸為stub節(jié)點(diǎn)。區(qū)分transit和stub自治域可以使我們對拓?fù)浣Y(jié)構(gòu)有更加深入的了解，對網(wǎng)絡(luò)中核心區(qū)域和邊緣區(qū)域的劃分有很大的參考價(jià)值。

3　實(shí)驗(yàn)論證

3.1實(shí)驗(yàn)環(huán)境

為了驗(yàn)證方法的有效性，作為國家“863”大規(guī)模IPv6編址項(xiàng)目的一部分，使用通用開放研究仿真器(common open research emulator,CORE)[15]網(wǎng)絡(luò)仿真器接入CNGI-CERNET2和CNGI-中國電信兩大網(wǎng)絡(luò)，依托國防科技大學(xué)軟件定義組網(wǎng)方法SDTB進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)搭建了如圖1所示的實(shí)驗(yàn)網(wǎng)絡(luò)，包括n1-n7這7個(gè)邊界路由器，分別屬于AS1-AS6這6個(gè)自治域，自治域間的連接情況如圖5所示。

圖5　transit-stub判別算法流程Fig.5　Process of transit-stub discrimination

3.2部署采集器前后的比較

正如前文所述，在部署采集器之前，我們從單個(gè)BGP路由器上獲得的路由表不足以推斷出全面真實(shí)的拓?fù)浣Y(jié)構(gòu)，在圖1中，以邊界路由器n6為例，在運(yùn)行BGP協(xié)議之后，其上的BGP路由表如表2所示，可見，除了直連網(wǎng)段10.0.7.0/24之外，到達(dá)其余網(wǎng)段的路徑下一條地址均是10.0.7.1，即路由器n1與n6連接的接口地址。n1本質(zhì)上對n6屏蔽了到達(dá)其他自治域的路徑。使用該路由表中的信息運(yùn)行圖3中的拓?fù)浒l(fā)現(xiàn)算法后，生成的拓?fù)淙绫?所示，從表3中可以看出，僅從路由器n6推斷出的拓?fù)渲写嬖诖罅窟z漏。

表2　路由器n6上的路由表Tab.2　Routing table on router n6

表3　由路由器n6推斷出的拓?fù)銽ab.3　Topology inferred by router n6

√：實(shí)際存在且推斷正確×：實(shí)際存在但未推斷

由于單個(gè)路由表不足以作出有效的拓?fù)渫茢?，我們在網(wǎng)絡(luò)中部署一臺采集器，連接所有其他的BGP路由器，并通過配置一個(gè)prefix-list，限制采集器只接收來自鄰居的路由更新消息而不會廣播自身所記錄的路由信息。圖2中，網(wǎng)絡(luò)中央為新加入的采集器，在運(yùn)行BGP協(xié)議且收斂之后，提取出采集器上的BGP路由表，表4展示了部分內(nèi)容，僅使用表4中展示的部分內(nèi)容，我們就可以推斷出完整的網(wǎng)絡(luò)拓?fù)湫畔?，如?所示。

表4　采集器上部分路由表Tab.4　Partial routing table on the collector

表5　由采集器路由表推斷出的拓?fù)銽ab.5　Topology inferred by the collector

通過前后2個(gè)實(shí)驗(yàn)結(jié)果的比較，可以看出存在一些可能性，當(dāng)僅使用一臺路由器中的路由表信息來拓?fù)浣Y(jié)構(gòu)時(shí)，會發(fā)生拓?fù)湫畔⑦z漏。網(wǎng)絡(luò)中每一臺邊界路由器中都存儲了一份以自身視角生成的網(wǎng)絡(luò)結(jié)構(gòu)，在網(wǎng)絡(luò)中加入采集器后，它將各個(gè)路由器上的路由信息匯總起來，所以，采集器連接的路由器越多，它得到的拓?fù)湫畔⒕驮饺?。在真?shí)的互聯(lián)網(wǎng)當(dāng)中，絕大部分自治域都會在上游與互聯(lián)網(wǎng)服務(wù)供應(yīng)商(internet service provider,ISP)的網(wǎng)絡(luò)相連，理論上我們可以把采集器部署為與ISP網(wǎng)絡(luò)相連的節(jié)點(diǎn)，這樣可以獲得與該ISP相連所有自治域的BGP路由信息。

3.3BGP更新消息

本部分我們采用和上一部分同樣的實(shí)驗(yàn)網(wǎng)絡(luò)結(jié)構(gòu)，在整個(gè)網(wǎng)絡(luò)運(yùn)行BGP協(xié)議并達(dá)到穩(wěn)定后，將自治域AS6中的路由器n7與路由器n5和n4連接的2個(gè)接口關(guān)閉，以此來仿真網(wǎng)絡(luò)節(jié)點(diǎn)的故障。此時(shí)，AS5—AS6和AS4—AS6這2條連接已經(jīng)斷開，通過wireshark捕捉到采集器接收到一條來自路由器n7的“撤銷”消息，如圖6所示。由于此時(shí)的n7已經(jīng)不與其他任何自治域相連，所以，會向采集器發(fā)送一條“撤銷”消息，將之前廣播的所有經(jīng)過它所在自治域即AS6的路徑全部設(shè)為無效。記錄下此刻時(shí)間t，經(jīng)過Δt=3 min之后，運(yùn)行一次拓?fù)渫茢嗟乃惴?結(jié)果如表6所示，可以發(fā)現(xiàn)，AS5—AS6和AS4—AS6之間的連通關(guān)系已經(jīng)消失了。

圖6　“撤銷”消息Fig.6　Withdraw message

AS1AS2AS3AS4AS5AS6AS1AS2AS3AS4AS5AS6

3.4transit和stub節(jié)點(diǎn)的判定

我們在3.2節(jié)中的實(shí)驗(yàn)網(wǎng)絡(luò)基礎(chǔ)上增加一個(gè)AS7以及路由器n8，構(gòu)成的實(shí)驗(yàn)網(wǎng)絡(luò)如圖7所示。在整個(gè)網(wǎng)絡(luò)運(yùn)行BGP協(xié)議并達(dá)到穩(wěn)定之后，提取采集器上的路由表，并運(yùn)行上面介紹的transit-stub節(jié)點(diǎn)判定算法，節(jié)點(diǎn)全集C={1,2,3,4,5,6,7}，將所有路由表項(xiàng)的“AS路徑”中兩端的節(jié)點(diǎn)刪除之后，剩余的“AS路徑”如表7所示，根據(jù)表7中的數(shù)據(jù)可求得transit節(jié)點(diǎn)集t={1,2,3,4,5,6}，stub節(jié)點(diǎn)集為c-t={7}。從圖7的拓?fù)浣Y(jié)構(gòu)中也可以發(fā)現(xiàn)，AS7是一個(gè)末端自治域(stub AS)，除了和采集器之間的鏈路，有且只有一條與AS5相連的鏈路，這意味著沒有任何其他自治域可以經(jīng)過它到達(dá)另外一個(gè)自治域，也就是說它并不提供中轉(zhuǎn)的服務(wù)。在真實(shí)互聯(lián)網(wǎng)當(dāng)中，大部分的transit節(jié)點(diǎn)也會在某些“AS路徑”的端點(diǎn)出現(xiàn)，因?yàn)樗鼈冏陨硗瑫r(shí)也會產(chǎn)生某些IP地址前綴。從實(shí)驗(yàn)結(jié)果來看，該算法是可以準(zhǔn)確地識別出“AS路徑”中transit節(jié)點(diǎn)與stub節(jié)點(diǎn)的。

圖7　transit-stub判定實(shí)驗(yàn)網(wǎng)絡(luò)Fig.7　Experimental network of transit-stub discrimination

編號AS路徑1{5}2{3}3{5,6}4{2}5{5,4}6{4,3}7{1,5}8{2}

4　結(jié)束語

網(wǎng)絡(luò)拓?fù)鋵W(wǎng)絡(luò)研究有著重要的價(jià)值，自治域級的拓?fù)浣Y(jié)構(gòu)更是對了解互聯(lián)網(wǎng)的結(jié)構(gòu)有著重要意義。本文提出的利用BGP路由表和BGP更新消息推斷自治域級拓?fù)涞姆椒軌驕?zhǔn)確全面地測量出網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，同時(shí)還能提供一些網(wǎng)絡(luò)節(jié)點(diǎn)的輔助信息。但本文的實(shí)驗(yàn)是在小型的仿真網(wǎng)絡(luò)環(huán)境下進(jìn)行的，下一步需要在真實(shí)的大規(guī)模網(wǎng)絡(luò)中部署采集器，采集實(shí)驗(yàn)數(shù)據(jù)，并嘗試加入主動(dòng)探測的方法來提供方法的準(zhǔn)確性及高效性。

[1]CHEN Q, CHANG H, GOVINDAN R, et al. The origin of power laws in Internet topologies revisited[C]∥IEEE INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. Piscataway, NJ, USA: IEEE, 2002: 608-617.

[2]BATTISTA G D, PATRIGNANI M, PIZZONIA M. Computing the types of the relationships between autonomous systems[C]∥INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies. Piscataway, NJ, USA: IEEE, 2003: 156-165.

[3]MEDINA A, LAKHINA A, MATTA I, et al. BRITE: an approach to universal topology generation[C]∥Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems,2001，Proceedings.Piscataway,NJ,USA:IEEE,2001:346-353.

[4]HARES S, REKHTER Y, LI T. A Border Gateway Protocol 4 (BGP-4)[EB/OL].(2006-01-18)[2016-02-01]. https:∥tools.ietf.org/html/rfc4271.

[5]HUFFAKER B, PLUMMER D, MOORE D, et al. Topology discovery by active probing[C]∥2002 Symposium on Applications and the Internet (SAINT) Workshops. Piscataway,NJ,USA:IEEE,2002:90-96.

[6]CHANG H, JAMIN S, WILLINGER W. Inferring AS-level Internet topology from router-level path traces[C]∥Scalability and Traffic Control in IP Networks. Denver, CO: SPIE, 2001: 196-207.

[7]FAGGIANI A, GREGORI E, IMPROTA A, et al. A study on traceroute potentiality in revealing the Internet AS-level topology[C]∥Networking Conference. Piscataway, NJ, USA: IEEE, 2014: 1-9.

[8]WEI Z, CHEN M, JI L, et al. An AS Border Judgment Method Based on IP Path Information[C]∥IEEE GLOBECOM 2008-2008 IEEE Global Telecommunications Conference. Piscataway, NJ, USA: IEEE, 2008: 1-5.

[9]DONNET B,FRIEDMAN T,CROVELLA M.Improved Algorithms for Network Topology Discovery[C]∥DOVROLIS C.Passive and Active Network Measurement.Berlin Heidelberg,German:Springer,2005:149-162.

[10] ANDERSEN D G,FEAMSTER N,BAUER S,et al.Topology Inference from BGP Routing Dynamics[C]∥Proceedings of the 2Nd ACM SIGCOMM Workshop on Internet Measurement.New York,NY,USA:ACM,2002:243-248.

[11] University of Oregon Route Views Project[EB/OL]. [2016-01-20]. http:∥www.routeviews.org.

[12] RIPE RIS Raw Data[EB/OL]. [2016-01-05]. https:∥www.ripe.net.

[13] MOY J. Ospf version 2[EB/OL]. (1998-10-20)[2016-02-01]. https:∥tools.ietf.org/html/rfc2328.

[14] LABOVITZ C, AHUJA A, BOSE A, et al. Delayed Internet Routing Convergence[C]∥Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. New York, NY, USA: ACM, 2000: 175-187.

[15] AHRENHOLZ J. Comparison of CORE network emulation platforms[C]∥2010-MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE. Piscataway, NJ, USA: IEEE, 2010: 864-869.

胡一非(1989-),男,江蘇興化人,碩士研究生,主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)。E-mail:jsxhhyf@gmail.com。

程光(1973-),男,安徽黃山人,博士,教授，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)測量,網(wǎng)絡(luò)安全等。E-mail:gcheng@njnet.edu.cn。

(編輯：劉勇)

The National High Technology Research and Development Program of China(“863” Program)(2015AA015603)

A compound topology discovery method at As-level

HU Yifei1,2, CHENG Guang1,2

(1. School of Computer Science and Engineering, Southeast University, Nanjing 211189, P.R. China;2.Key Laboratory of Computer Network and Information Integration, Southeast University, Ministry of Education,Nanjing 211189, P.R. China)

With the development of network technology, traditional network seems powerless when facing new challenges. Future network cames out at this time led by software defined network(SDN) with many advantages, but topology measurement is as important as it was in traditional environment. In an AS-level topology, we can simply take every single AS as a node, and edges between two nodes means adjacency of ASes. Large numbers of different topology discovery algorithms have been shown recently in various researches. In this paper, a simple but efficient method utilizing high speed collector is deployed in the network to collect border gateway protocol(BGP) routing tables on BGP routers and BGP update messages among them to deduce network topological structure is proposed, and it could also differentiate transit-node and stub-node in the network. Experiments are conducted to prove this method could achieve expected effect which is precisely and completely inferring the topological structure at AS-level.

autonomous system; topology discovery; border gateway protocol(BGP)

10.3979/j.issn.1673-825X.2016.05.018

2016-02-16

2016-04-30通訊作者：程光gcheng@njnet.edu.cn

國家“863”計(jì)劃項(xiàng)目(2015AA015603)

TN92;TP393

A

1673-825X(2016)05-0729-08