IP級網絡拓撲測量技術的研究與實現

薛健等

摘要：對現有的常用的兩種網絡拓撲測量技術進行了分析研究，實現了基于traceroute技術的網絡拓撲測量系統并用其測量了中國網絡，通過與Iplane的測量結果對比評價了其可用性。首先討論了基于SNMP協議的拓撲測量方法，并指出其優缺點。隨后討論了基于traceroute技術的拓撲測量方法，描述了基于traceroute技術的拓撲測量系統的設計構架和關鍵技術。最終利用拓撲測量系統測量了中國網絡拓撲，然后將其測量結果同Iplane測量的中國網絡拓撲進行復雜網絡特征分析。通過特征對比發現，測量系統挖掘出的拓撲呈現出更顯著的非相稱性、更弱的聚集和更短的距離，證明了該系統的可用性。

關鍵詞：SNMP協議； traceroute技術； 拓撲測量； 復雜網絡

中圖分類號：TP393 文獻標識碼：A文章編號：2095-2163（2014）01-0094-04

0引言

伴隨著全球互聯網絡規模的不斷擴大以及計算機軟件和硬件技術的飛速發展，當今的互聯網絡已經變得愈加龐大和復雜，這一過程致使人們對網絡本身將缺乏準確的表述和認識，并在一定程度上制約了對當前網絡資源的有效利用，限制了網絡技術的發展。為了深入了解當前全球網絡，人們開始著手對網絡特征進行研究。其中，網絡拓撲的發現在整個網絡特征研究中即占有十分重要的地位。對網絡拓撲結構的深入研究與探討，便于對整個網絡進行宏觀管理，同時對國家及地區的網絡安全也起著至關重要的作用。

1IP級網絡拓撲測量的常用方法

IP級網絡拓撲測量是發現待測網絡元素的IP地址間的互聯情況。目前，IP級網絡拓撲的測量主要有兩種方式：基于SNMP協議[1]的測量方式和基于traceroute技術[2]的測量方式。

1.1基于SNMP協議的網絡拓撲測量方法

SNMP協議（Simple Network Management Protocol，簡單網絡管理協議）包含在IETF（Internet Engineering Task Force， 互聯網工程工作小組）定義的協議簇中，屬于一種TCP/IP體系下的應用層協議。該協議使得網絡管理者同代理之間傳遞管理指令和數據成為可能，已在很多的應用中被廣泛采用。

1.1.1SNMP的管理模型

SNMP的管理模型[3]如圖1所示。從體系結構上進行描述，主要包括三個關鍵元素。

（1）SNMP管理站

管理站通?？梢岳斫鉃槟硞€網絡中的一臺單機設備，網絡管理員可以通過管理站同系統進行信息交互。其工作方式類似于C/S體系結構（Client/Server，客戶端/服務器）下的客戶端。管理站可以接收網絡管理員或某種應用發出的操作請求，也可以接收來自系統代理的數據信息。

（2）SNMP管理代理

管理代理通常運行在某個共享網絡中支持SNMP協議的部件上，這是一種可以應答來自SNMP管理站發出的請求的軟件，其地位同C/S體系結構中的服務器極為相似。管理代理可以收到從SNMP管理站發出的SNMP請求，并根據需要對其進行響應，SNMP管理代理也可以通過異步發送的方式向管理站提供某些非請求數據。

（3）管理信息庫

MIB（Management Information Base，管理信息庫）是通過SNMP協議進行訪問的數據庫，所有支持SNMP協議的代理均保證能夠應答對MIB信息庫中的對象信息的查找請求；任何支持SNMP協議的網絡管理站應該確保自身欲對代理的請求信息都應包含在MIB數據庫的數據范圍內。

1.1.2算法描述

算法可以通過SNMP請求獲取目標網絡中各個路由器中的路由表數據并進行綜合分析，從而獲得目標網絡中路由器及子網之間的連接情況。

基于SNMP協議的拓撲測量算法過程如下[4]：

（1）任意選擇待測網絡中的某臺路由器作為初始化的起點路由器，將其壓入待發現路由隊列。

（2）從隊列中彈出隊首路由器作為當前路由器。發送SNMP請求，讀取當前路由器中的MIB數據庫，從中提取其路由表。

（3）遍歷MIB路由表。如果表中的記錄為直接連接，則將目的子網掩碼同目的IP地址進行與運算，從而獲得當前路由器與這個目的網絡的連接情況；如果記錄為間接連結且與當前路由器直接連接的下一跳路由器不在待發現路由器隊列中，則將下一跳路由器壓入待發現路由器隊列的隊尾，同時將其壓入已發現路由器隊列隊尾。

（4）若待發現隊列為空，則終止算法。否則，從待發現路由器隊列中彈出隊首路由器并將其作為當前路由器，返回第二步繼續執行。

1.1.3基于SNMP協議的網絡拓撲測量方法的優缺點

基于SNMP協議的方法的優點是算法的測量結果通常較為完整和精確，同時還具有易于實現，測量過程開銷較小的特點。而其缺點主要表現在其對帶測量的網絡要求支持SNMP協議，且普適性較弱。

1.2基于traceroute技術的網絡拓撲測量方法

traceroute方式通過測量源向目標節點發起traceroute測量以探測各個主機和中間路由器IP接口間的連接。基于traceroute技術的測量可歸類為基于ICMP協議的測量，而基于ICMP的測量方式具有限制少，適用性強的特點。但基于traceroute的網絡拓撲測量屬于主動測量，測量過程中需發送大量的ICMP數據包，這會增加網絡的負擔；同時實現起來相對基于SNMP的測量方式也更為復雜，程序的執行效率也比較低。即便如此，由于基于traceroute的測量方式在大規模網絡拓撲發現中具有更強的普適性，因此在現代網絡拓撲發現中得到廣泛的應用。

1.2.1網絡拓撲測量系統的整體設計

網絡拓撲測量系統旨在獲得并控制公開、可控的traceroute服務器向一個或多個目標IP同時發起traceroute測量，而將返回的結果整理成特定的形式后，再由后續的圖特征分析模塊對結果進行分析。網絡拓撲測量系統的整體設計如圖2所示。

1.2.2網絡拓撲發現系統的基本構成

整個拓撲測量系統共含有四個主要模塊，各個模塊的功能和關鍵技術概括如下：

（1）服務器采集模塊

全球公開的traceroute服務器Url列表往往由相關的組織機構或個人以網頁的形式對外發布，如traceroute.org上就有公開的約1 000個分布于全球各地的traceroute服務器Url。服務器采集模塊的功能就是從相應的traceroute服務器列表網頁中獲取全部有效的traceroute服務器Url，并將其存入數據庫中。同時，服務器采集模塊會定期檢測服務器列表中Url的有效性，并及時更新數據庫信息，以保證其時效性。

（2）測量數據采集模塊

測量數據采集模塊的功能是讀取目標IP地址列表，利用服務器采集模塊收集的traceroute服務器向所有目標IP發起traceroute測量，同時獲取服務器端返回的結果，再提交給數據整理模塊對結果進行分析整理。

（3）數據整理模塊

數據整理模塊利用Python的BeautifulSoup庫和正則表達式，首先在返回的網頁中定位traceroute結果所在的標簽，然后在該標簽中抽取出traceroute路徑中每跳的IP地址，形成一條由源點服務器到目標IP的完整的IP級路徑，并將其存入到與源服務器對應的文件中。通常網絡拓撲的測量結果由多個文件組成，每個文件描述某個源traceroute服務器到其測量的所有目標IP的traceroute路徑。

（4）拓撲分析模塊

拓撲分析模塊可以對最終獲得的拓撲圖進行顯示或復雜網絡特征提取。通常拓撲圖的顯示可以依靠現有的軟件，如Ciada[5]的Otter。拓撲圖的分析采用復雜網絡特征提取的方法來分析大規模網絡的真實特征，尋找其結構、動力學和功能的內在規律。2測量系統的測量結果分析

考慮利用網絡拓撲測量系統發現中國的IP級網絡拓撲，然后從華盛頓大學的Iplane服務測量的全球拓撲中提取中國網絡拓撲，并將其結果同測量系統發現的結果進行復雜網絡特征分析。通過特征對比表明了測量系統的可用性。

首先，從Iplane上獲取其測量的全球拓撲，將這個網絡拓撲命名為IPLTopo。然后，利用GeoIP從Iplane的目標IP集中篩選出所有位于中國的IP地址，形成一個中國目標IP集CNTarget。隨后，利用拓撲測量系統以CNTarget為目標進行測量，獲取系統測量的全球拓撲TmpTopo。最終，利用數據整理模塊從TmpTopo和IPLTopo中分別提取出中國的網絡拓撲。其中，Iplane測量的中國拓撲稱為IplaneTopo，系統測量的中國拓撲稱為MyTopo。MyTopo與IplaneTopo的統計特征如表1所示。網絡拓撲是一種無權無向圖，設鏈接數為m，節點數為n。

2.1平均節點度

平均節點度用來表示無向連通圖的疏密程度，通常用k來表示，其中k=2m/n。由表1可以看出IplaneTopo的k值更大，表明Iplane發現的拓撲圖更加密集。這是由于MyTopo的測量源點更為豐富，決定了其可發現網絡中的大部分低密度的節點，并使得所有節點中低密度節點的比例很高，由此導致其平均節點度偏低。而IplaneTopo相對較少的測量源點更多地卻只能發現介數[6]較高的高度節點，使得結果的平均節點度更高。

2.2節點度分布

當圖為非對稱時，A為負數，表示低度節點與高度節點互聯的情況出現得較為頻繁；反之若圖是對稱的，則A為正數。由圖4中的A值可以看出，MyTopo較IplaneTopo不相稱性更加顯著。這就表明網絡拓撲測量系統發現了一部分度數較高的節點同很多度數較低節點相連接的情況，相應部分網絡通常是用來給終端提供網絡接入的邊緣子網絡。薛健，等：IP級網絡拓撲測量技術的研究與實現

2.4聚集

在一個無向圖中，通常用一個節點的相鄰節點的鏈接數除以k（k-1）/2來計算度數為k的節點的局部聚集c。其中用c來表示c的均值，可以用該形式作為一種度量來描繪小世界[9]的現象。表示圖的傳遞性的T也可以作為另一種表述圖聚集性的單位，即用其表示當節點v1與節點v2，v3分別連接，則v2和v3兩節點也相連的概率。通過圖4可以看出，IplaneTopo的兩個聚集特征均強于MyTopo，這點同之前發現的IplaneTopo的k較大、高度節點比例較大的特征相吻合。

2.5距離分布

在無向圖中，通常表示任選圖中任意兩個節點且兩者最短距離為d的概率時，用P（d）來描述。由于P（d）的概率密度函數類似于高斯分布，因此可用均值d和方差σ來對其分布進行表述。d的最大值dmax用來表示圖的直徑。由圖4可以看出，MyTopo的三個值均比IplaneTopo的小，這是由于MyTopo的拓撲規模較IplaneTopo的更大，其中包括了更多的網絡節點以及鏈接，從而使得圖中任意兩點間包含更加豐富的路徑，且具更多的捷徑。

3結束語

本文分析了現有的兩種網絡拓撲測量技術—基于SNMP協議的網絡拓撲測量方法和基于traceroute技術的網絡拓撲測量方法。首先，描述SNMP方法的管理模型及算法實現，指出了其適用范圍較小，不適合大規模網絡拓撲測量的缺點；然后介紹了基于traceroute技術的網絡拓撲測量系統整體架構及各個模塊的主要功能。隨后，利用拓撲測量系統測量了中國網絡拓撲，并將其測量結果同Iplane測量的中國網絡拓撲進行復雜網絡特征對比。通過對比發現，測量系統挖掘出的拓撲更加完整精確，證明了該系統具有一定的代表性和可用性。

當然，系統的設計也存在著許多不足，主要有兩點。一是系統目前只能在一臺機器上采取串行的方式運行，每個測量周期時間均較長。可以考慮采取分布式測量的方式并發運行系統進行測量，其后再將各自的結果進行整合。如此則一個測量周期的時間可以大幅縮短。二是為了獲得更為全面的網絡拓撲信息，可以考慮將系統的測量結果同其它的拓撲發現項目的測量成果進行合并，如caida的skitter[10]、DIMES等。這就使得測量結果更加完整，節省了主動測量的開銷，同時又進一步縮短了測量周期。

參考文獻：

[1]胡延平，王連杰，劉武，等. 基于ICMP的網絡性能分析[J]. 計算機工程與設計，2003（4）：30-32.

[2]CHAN S H G. Traceroute-based topology inference without network coordinate estimation[C]//Proceedings of the Symposium on Information and Network Security of ICC 2008， 2008，5：300-391.

[3]楊安義，朱華清，王繼龍.一種改進的基于SNMP的網絡拓撲發現算法及實現[J]. 計算機應用， 2007（10）： 2412-2413， 2419.

[4]劉琳琳. 網絡拓撲發現技術的研究和實現[D].西安：西安電子科技大學，2006：25-35.

[5]BROIDO A， CLAFFY K. Internet topology： Connectivity of IP graphs. SPIE International symposium on Convergence of IT and Communication[C]//Society of Photo-Optical Instrumentation Engineers， Denver， CO.2001：172-187.

[6]GOH K I， KAHNG B， KIM D. Universal behavior of load distribution in scale-free networks[J]. Physical Review Letters， 2001，87（27）：278-701.

[7]FALOUTSOS M， FALOUTSOS P， FALOUTSOS C. On power-law relationships of the internet topology[J].SIGCOMM Computer Communication Review， 1999，29：140-259.

[8]NEWMAN M E J. Structure and function of complex networks[J]. SIAM Review. 2003，45（2）：167-256.

[9]WATTS D J， STROGATZ S H. Collective dynamics of 'small-world' networks[J].Nature， 1998，393：439-450.

[10]張君，趙海，康敏. Skitter與Ark探測架構下AS級Internet拓撲分析[J]. 計算機科學， 2010（11）：38-40.