一種復合的自治域級拓撲發現方法

胡一非，程　光

(1. 東南大學 計算機科學與工程學院，江蘇 南京 211189；2. 東南大學 計算機網絡和信息集成教育部重點實驗室，江蘇 南京 211189)

?

一種復合的自治域級拓撲發現方法

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

(1. 東南大學 計算機科學與工程學院，江蘇 南京 211189；2. 東南大學 計算機網絡和信息集成教育部重點實驗室，江蘇 南京 211189)

隨著網絡技術的發展，面對新的挑戰，傳統網絡逐漸力不從心，軟件定義網絡(software-defined network,SDN)領銜的未來網絡應運而生，隨之而來的是各類網絡測量技術紛紛針對未來網絡發生演變，但拓撲結構測量在傳統網絡環境下的作用仍然不可忽視。在自治域級的網絡拓撲中，每個自治域都可以簡化為一個點,而用兩點之間的連線表示自治域間的鄰接關系。近年來有許多相關的研究展示了不同的拓撲發現算法。提出了一種簡單高效的方法來推斷自治域級的拓撲,利用在網絡中部署高速采集器采集邊界網關協議(border gateway protocol,BGP)路由器上的路由表以及BGP協議的更新信息來推斷網絡拓撲結構，并判定自治域的相關屬性。實驗證明了該方法能夠達到預期效果，全面、準確地推斷網絡在自治域級的拓撲結構。

自治域；拓撲發現；邊界網關協議(BGP)

0　引　言

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

自治域級的拓撲結構可以通過BGP的路由信息來推斷。BGP路由表中的每一項都包含了一個“AS路徑”的屬性，記錄了到達一個特定IP地址前綴所經過的AS號，通過求出多個BGP路由表中的“AS路徑”的并集，我們可以對網絡的拓撲做一個大致的推斷；另外，由于網絡波動，鏈路故障及配置錯誤等原因觸發的BGP更新報文也包含了“AS路徑”這一屬性，因此，可以用來作為通過BGP路由表推斷出拓撲的一種補充。本文依托國防科技大學面向廣域網實驗床的軟件定義組網方法-軟件定義實驗床(software difined testbed,SDTB)，提出了一種通過采集BGP路由表和BGP路由更新信息來推斷自治域級拓撲的方法，并為二維路由實驗和 IPv6 大規模編址實驗提供了支撐，相比其他方法，可以用最小的代價得到最完整的拓撲信息，另外，還提供了一系列相關的輔助拓撲信息，比如時間戳，結點類型等，方便用戶決策。

1　相關工作

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

2　拓撲發現算法

2.1基于BGP路由表

BGP協議與開放式最短路徑優先(open shortest path first,OSPF)[13]等鏈路狀態協議不同，它并不維護一個全局的視圖，每個運行BGP協議的邊界路由器選擇它認為最好的路徑并廣播給它的鄰居，導致的結果就是每一個不同的路由器都有可能存儲著不同的路徑信息；另外，同一個自治域中可能會存在多個邊界路由器，它們之間采用內部網關協議(interior gateway protocol,IGP)交換路由信息，一個邊界路由器可能會“隱藏”在另一邊界路由器的后面。圖1為未接入采集器網絡拓撲圖。圖1中，路由器n1至n7都是自治域中的邊界路由器，運行BGP協議，路由器n6到其他自治域的路徑都要通過路由器n1，換句話說，對n6來說，n1屏蔽了大部分路由信息。這就決定了只從一個單獨的節點中提取的信息不足以反映整個網絡的拓撲，我們需要建立一套消息采集機制來最大可能地獲取更加全面的拓撲信息。因此，我們在網絡中部署了一臺BGP信息采集器用來與各BGP路由器通信，抓取路由表。采集器與待測量網絡中盡可能多的節點相連，同樣運行BGP協議，但不同的是采集器只接收來自其他BGP路由器的更新報文，而不會向他的鄰居廣播自身存儲的路由信息。這樣配置是為了保證在采集到盡可能多的路由表的前提下，不影響整個網絡的正常通信，否則，將有大量的正常數據流量被引導到采集器上。

我們在實驗拓撲中加入了一臺采集器，其網絡拓撲如圖2所示。由于實驗網絡規模較小，我們將采集器與所有的邊界路由器連接，對每個邊界路由器而言，它們只是增加了一個鄰居，即后來部署的采集器，但由于采集器不廣播任何路由消息，其他邊界路由器只會定期廣播自己的可達網絡消息，并不會將流量引導到采集器上。同時，采集器又與普通邊界路由器一樣，從各鄰居路由器廣播的路由消息中推導出路徑信息，存儲在自身的路由表中。

一個典型的BGP路由表的結構如表1所示，主要提取“AS路徑”這一屬性來推斷拓撲結構?！癆S路徑”是BGP路由表項中一項公認的強制屬性，它表示到達目的前綴地址需要經過的一系列AS號。以表1中這條表項為例，這是一個通往10.0.0.0/24網段的路徑，下一條地址是10.0.7.1，“AS路徑”屬性中包含了AS12，AS34，AS56，說明要到達目標網絡，需要依次經過12，34，56這3個自治域，由于是依次傳播的，顯而易見每2個自治域之間是連通的，即存在12—34，34—56這2條路徑。由此可見，通過提取“AS路徑”中的鄰接信息，是可以推斷出網絡拓撲結構的。圖3表示了從“AS路徑”推斷拓撲的算法流程。首先將拓撲初始化為空，從采集器中的路由表中提取每一項“AS路徑”屬性，將其中相鄰的2個AS號之間標記為“連通”，重復此過程直至處理完所有“AS路徑”，得到初步推斷的結果。

圖1　未接入采集器網絡拓撲 　　Fig.1　Topology without acquisition

圖2　接入采集器后網絡拓撲　　Fig.2　Topology with acquisition

優選路徑前綴地址下一跳度量值本地優先級權重AS路徑*i10.0.0.0/2410.0.7.111000123456

2.2基于更新信息

互聯網是一個龐大且動態的結構，每一秒都會有成千上萬的節點加入和退出，如果再考慮網絡故障以及配置錯誤等因素，僅僅靠靜態的路由表推斷出的拓撲結構一定是不準確的，最多只能算是某一時刻的狀態。而BGP路由表也不能準確地反映網絡中數據包的傳播路徑，因為路由表會選擇到一個特定前綴地址的最佳路徑，忽略其余的，但BGP更新消息卻可以保留多條路徑。所以，在通過采集器上的路由表推斷出拓撲后，還需要持續地接收BGP更新消息，從而獲得更加全面和完整的拓撲信息。

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

圖3　拓撲發現算法流程Fig.3　Process of topology discovery

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

BGP協議[4]規定，當路由消息從一個自治域傳遞到另一個自治域時，需要在“AS路徑”的最前面加上最后一個新到達的自治域號，同一個自治域內2個邊界路由器通過IGP協議傳遞路由信息時，不需要在“AS路徑”里添加多個相同的AS號，所以，通常情況下“AS路徑”中的AS號不會出現重復，但因為本地配置等原因也可能會出現連續重復的AS號，這種情況下，我們把連續出現的AS合并為一個，然后再按照正常的算法步驟進行計算。

2.3transit節點和stub節點的判定方法

我們把網絡中的自治域分成2種類型：transit和stub。在網絡拓撲圖中，stub節點只出現在一條路徑的兩端，它不向其他節點提供中轉服務，即網絡中的流量不能經由它到達其他節點。除此之外的其他節點則為transit節點，因為它們存在于路徑的中間，為其他節點提供中轉服務。由上述定義得出以下2點結論。

1)在“AS路徑”中，處在中間的節點一定是transit節點。設它為x，x的前一個節點為a，后一個節點為b，可知流量從a經過x再到另一個自治域b，符合了transit節點的特征。

2)在“AS路徑”中，處在第一個和最后一個的節點不一定是stub節點，因為存在這種情況：一個AS在某一條路由表項是端節點，但在另一條表項中成為了中間節點。

明確了上述2點之后，我們提出一種判定transit節點和stub節點的方法，如圖5所示。在采集器的路由表中，遍歷所有表項的“AS路徑”屬性，設所有出現過的AS為集合c，將每個“AS路徑”中第一個和最后一個刪除，將剩余的所有結點歸為transit節點，設為集合t，最后，c-t的部分歸為stub節點。區分transit和stub自治域可以使我們對拓撲結構有更加深入的了解，對網絡中核心區域和邊緣區域的劃分有很大的參考價值。

3　實驗論證

3.1實驗環境

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

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

3.2部署采集器前后的比較

正如前文所述，在部署采集器之前，我們從單個BGP路由器上獲得的路由表不足以推斷出全面真實的拓撲結構，在圖1中，以邊界路由器n6為例，在運行BGP協議之后，其上的BGP路由表如表2所示，可見，除了直連網段10.0.7.0/24之外，到達其余網段的路徑下一條地址均是10.0.7.1，即路由器n1與n6連接的接口地址。n1本質上對n6屏蔽了到達其他自治域的路徑。使用該路由表中的信息運行圖3中的拓撲發現算法后，生成的拓撲如表3所示，從表3中可以看出，僅從路由器n6推斷出的拓撲中存在大量遺漏。

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

表3　由路由器n6推斷出的拓撲Tab.3　Topology inferred by router n6

√：實際存在且推斷正確×：實際存在但未推斷

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

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

表5　由采集器路由表推斷出的拓撲Tab.5　Topology inferred by the collector

通過前后2個實驗結果的比較，可以看出存在一些可能性，當僅使用一臺路由器中的路由表信息來拓撲結構時，會發生拓撲信息遺漏。網絡中每一臺邊界路由器中都存儲了一份以自身視角生成的網絡結構，在網絡中加入采集器后，它將各個路由器上的路由信息匯總起來，所以，采集器連接的路由器越多，它得到的拓撲信息就越全面。在真實的互聯網當中，絕大部分自治域都會在上游與互聯網服務供應商(internet service provider,ISP)的網絡相連，理論上我們可以把采集器部署為與ISP網絡相連的節點，這樣可以獲得與該ISP相連所有自治域的BGP路由信息。

3.3BGP更新消息

本部分我們采用和上一部分同樣的實驗網絡結構，在整個網絡運行BGP協議并達到穩定后，將自治域AS6中的路由器n7與路由器n5和n4連接的2個接口關閉，以此來仿真網絡節點的故障。此時，AS5—AS6和AS4—AS6這2條連接已經斷開，通過wireshark捕捉到采集器接收到一條來自路由器n7的“撤銷”消息，如圖6所示。由于此時的n7已經不與其他任何自治域相連，所以，會向采集器發送一條“撤銷”消息，將之前廣播的所有經過它所在自治域即AS6的路徑全部設為無效。記錄下此刻時間t，經過Δt=3 min之后，運行一次拓撲推斷的算法,結果如表6所示，可以發現，AS5—AS6和AS4—AS6之間的連通關系已經消失了。

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

AS1AS2AS3AS4AS5AS6AS1AS2AS3AS4AS5AS6

3.4transit和stub節點的判定

我們在3.2節中的實驗網絡基礎上增加一個AS7以及路由器n8，構成的實驗網絡如圖7所示。在整個網絡運行BGP協議并達到穩定之后，提取采集器上的路由表，并運行上面介紹的transit-stub節點判定算法，節點全集C={1,2,3,4,5,6,7}，將所有路由表項的“AS路徑”中兩端的節點刪除之后，剩余的“AS路徑”如表7所示，根據表7中的數據可求得transit節點集t={1,2,3,4,5,6}，stub節點集為c-t={7}。從圖7的拓撲結構中也可以發現，AS7是一個末端自治域(stub AS)，除了和采集器之間的鏈路，有且只有一條與AS5相連的鏈路，這意味著沒有任何其他自治域可以經過它到達另外一個自治域，也就是說它并不提供中轉的服務。在真實互聯網當中，大部分的transit節點也會在某些“AS路徑”的端點出現，因為它們自身同時也會產生某些IP地址前綴。從實驗結果來看，該算法是可以準確地識別出“AS路徑”中transit節點與stub節點的。

圖7　transit-stub判定實驗網絡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　結束語

網絡拓撲對網絡研究有著重要的價值，自治域級的拓撲結構更是對了解互聯網的結構有著重要意義。本文提出的利用BGP路由表和BGP更新消息推斷自治域級拓撲的方法能夠準確全面地測量出網絡拓撲結構，同時還能提供一些網絡節點的輔助信息。但本文的實驗是在小型的仿真網絡環境下進行的，下一步需要在真實的大規模網絡中部署采集器，采集實驗數據，并嘗試加入主動探測的方法來提供方法的準確性及高效性。

[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-),男,江蘇興化人,碩士研究生,主要研究方向為計算機網絡。E-mail:jsxhhyf@gmail.com。

程光(1973-),男,安徽黃山人,博士,教授，主要研究方向為計算機網絡測量,網絡安全等。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”計劃項目(2015AA015603)

TN92;TP393

A

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