伴隨著全球互聯(lián)網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大以及計(jì)算機(jī)軟件和硬件技術(shù)的飛速發(fā)展，當(dāng)今的互聯(lián)網(wǎng)絡(luò)已經(jīng)變得愈加龐大和復(fù)雜，這一過(guò)程致使人們對(duì)網(wǎng)絡(luò)本身將缺乏準(zhǔn)確的表述和認(rèn)識(shí)，并在一定程度上制約了對(duì)當(dāng)前網(wǎng)絡(luò)資源的有效利用，限制了網(wǎng)絡(luò)技術(shù)的發(fā)展。為了深入了解當(dāng)前全球網(wǎng)絡(luò)，人們開(kāi)始著手對(duì)網(wǎng)絡(luò)特征進(jìn)行研究。其中，網(wǎng)絡(luò)拓?fù)涞陌l(fā)現(xiàn)在整個(gè)網(wǎng)絡(luò)特征研究中即占有十分重要的地位。對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的深入研究與探討，便于對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行宏觀管理，同時(shí)對(duì)國(guó)家及地區(qū)的網(wǎng)絡(luò)安全也起著至關(guān)重要的作用。

　　摘要：對(duì)現(xiàn)有的常用的兩種網(wǎng)絡(luò)拓?fù)錅y(cè)量技術(shù)進(jìn)行了分析研究，實(shí)現(xiàn)了基于traceroute技術(shù)的網(wǎng)絡(luò)拓?fù)錅y(cè)量系統(tǒng)并用其測(cè)量了中國(guó)網(wǎng)絡(luò)，通過(guò)與Iplane的測(cè)量結(jié)果對(duì)比評(píng)價(jià)了其可用性。首先討論了基于SNMP協(xié)議的拓?fù)錅y(cè)量方法，并指出其優(yōu)缺點(diǎn)。隨后討論了基于traceroute技術(shù)的拓?fù)錅y(cè)量方法，描述了基于traceroute技術(shù)的拓?fù)錅y(cè)量系統(tǒng)的設(shè)計(jì)構(gòu)架和關(guān)鍵技術(shù)。最終利用拓?fù)錅y(cè)量系統(tǒng)測(cè)量了中國(guó)網(wǎng)絡(luò)拓?fù)�，然后將其測(cè)量結(jié)果同Iplane測(cè)量的中國(guó)網(wǎng)絡(luò)拓?fù)溥M(jìn)行復(fù)雜網(wǎng)絡(luò)特征分析。通過(guò)特征對(duì)比發(fā)現(xiàn)，測(cè)量系統(tǒng)挖掘出的拓?fù)涑尸F(xiàn)出更顯著的非相稱(chēng)性、更弱的聚集和更短的距離，證明了該系統(tǒng)的可用性。

　　關(guān)鍵詞：SNMP協(xié)議,traceroute技術(shù),拓?fù)錅y(cè)量,復(fù)雜網(wǎng)絡(luò)

　　0引言

　　1IP級(jí)網(wǎng)絡(luò)拓?fù)錅y(cè)量的常用方法

　　IP級(jí)網(wǎng)絡(luò)拓?fù)錅y(cè)量是發(fā)現(xiàn)待測(cè)網(wǎng)絡(luò)元素的IP地址間的互聯(lián)情況。目前，IP級(jí)網(wǎng)絡(luò)拓?fù)涞臏y(cè)量主要有兩種方式：基于SNMP協(xié)議[1]的測(cè)量方式和基于traceroute技術(shù)[2]的測(cè)量方式。

　　1.1基于SNMP協(xié)議的網(wǎng)絡(luò)拓?fù)錅y(cè)量方法

　　SNMP協(xié)議（SimpleNetworkManagementProtocol，簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議）包含在IETF（InternetEngineeringTaskForce，互聯(lián)網(wǎng)工程工作小組）定義的協(xié)議簇中，屬于一種TCP/IP體系下的應(yīng)用層協(xié)議。該協(xié)議使得網(wǎng)絡(luò)管理者同代理之間傳遞管理指令和數(shù)據(jù)成為可能，已在很多的應(yīng)用中被廣泛采用。

　　1.1.1SNMP的管理模型

　　SNMP的管理模型[3]如圖1所示。從體系結(jié)構(gòu)上進(jìn)行描述，主要包括三個(gè)關(guān)鍵元素。

　�。�1）SNMP管理站

　　管理站通�？梢岳斫鉃槟硞�(gè)網(wǎng)絡(luò)中的一臺(tái)單機(jī)設(shè)備，網(wǎng)絡(luò)管理員可以通過(guò)管理站同系統(tǒng)進(jìn)行信息交互。其工作方式類(lèi)似于C/S體系結(jié)構(gòu)（Client/Server，客戶(hù)端/服務(wù)器）下的客戶(hù)端。管理站可以接收網(wǎng)絡(luò)管理員或某種應(yīng)用發(fā)出的操作請(qǐng)求，也可以接收來(lái)自系統(tǒng)代理的數(shù)據(jù)信息。

　　（2）SNMP管理代理

　　管理代理通常運(yùn)行在某個(gè)共享網(wǎng)絡(luò)中支持SNMP協(xié)議的部件上，這是一種可以應(yīng)答來(lái)自SNMP管理站發(fā)出的請(qǐng)求的軟件，其地位同C/S體系結(jié)構(gòu)中的服務(wù)器極為相似。管理代理可以收到從SNMP管理站發(fā)出的SNMP請(qǐng)求，并根據(jù)需要對(duì)其進(jìn)行響應(yīng)，SNMP管理代理也可以通過(guò)異步發(fā)送的方式向管理站提供某些非請(qǐng)求數(shù)據(jù)。

　�。�3）管理信息庫(kù)

　　MIB（ManagementInformationBase，管理信息庫(kù)）是通過(guò)SNMP協(xié)議進(jìn)行訪問(wèn)的數(shù)據(jù)庫(kù)，所有支持SNMP協(xié)議的代理均保證能夠應(yīng)答對(duì)MIB信息庫(kù)中的對(duì)象信息的查找請(qǐng)求；任何支持SNMP協(xié)議的網(wǎng)絡(luò)管理站應(yīng)該確保自身欲對(duì)代理的請(qǐng)求信息都應(yīng)包含在MIB數(shù)據(jù)庫(kù)的數(shù)據(jù)范圍內(nèi)。

　　1.1.2算法描述

　　算法可以通過(guò)SNMP請(qǐng)求獲取目標(biāo)網(wǎng)絡(luò)中各個(gè)路由器中的路由表數(shù)據(jù)并進(jìn)行綜合分析，從而獲得目標(biāo)網(wǎng)絡(luò)中路由器及子網(wǎng)之間的連接情況。

　　基于SNMP協(xié)議的拓?fù)錅y(cè)量算法過(guò)程如下[4]：

　　（1）任意選擇待測(cè)網(wǎng)絡(luò)中的某臺(tái)路由器作為初始化的起點(diǎn)路由器，將其壓入待發(fā)現(xiàn)路由隊(duì)列。

　�。�2）從隊(duì)列中彈出隊(duì)首路由器作為當(dāng)前路由器。發(fā)送SNMP請(qǐng)求，讀取當(dāng)前路由器中的MIB數(shù)據(jù)庫(kù)，從中提取其路由表。

　　（3）遍歷MIB路由表。如果表中的記錄為直接連接，則將目的子網(wǎng)掩碼同目的IP地址進(jìn)行與運(yùn)算，從而獲得當(dāng)前路由器與這個(gè)目的網(wǎng)絡(luò)的連接情況；如果記錄為間接連結(jié)且與當(dāng)前路由器直接連接的下一跳路由器不在待發(fā)現(xiàn)路由器隊(duì)列中，則將下一跳路由器壓入待發(fā)現(xiàn)路由器隊(duì)列的隊(duì)尾，同時(shí)將其壓入已發(fā)現(xiàn)路由器隊(duì)列隊(duì)尾。

　�。�4）若待發(fā)現(xiàn)隊(duì)列為空，則終止算法。否則，從待發(fā)現(xiàn)路由器隊(duì)列中彈出隊(duì)首路由器并將其作為當(dāng)前路由器，返回第二步繼續(xù)執(zhí)行。

　　1.1.3基于SNMP協(xié)議的網(wǎng)絡(luò)拓?fù)錅y(cè)量方法的優(yōu)缺點(diǎn)

　　基于SNMP協(xié)議的方法的優(yōu)點(diǎn)是算法的測(cè)量結(jié)果通常較為完整和精確，同時(shí)還具有易于實(shí)現(xiàn)，測(cè)量過(guò)程開(kāi)銷(xiāo)較小的特點(diǎn)。而其缺點(diǎn)主要表現(xiàn)在其對(duì)帶測(cè)量的網(wǎng)絡(luò)要求支持SNMP協(xié)議，且普適性較弱。

　　1.2基于traceroute技術(shù)的網(wǎng)絡(luò)拓?fù)錅y(cè)量方法

　　traceroute方式通過(guò)測(cè)量源向目標(biāo)節(jié)點(diǎn)發(fā)起traceroute測(cè)量以探測(cè)各個(gè)主機(jī)和中間路由器IP接口間的連接�；�于traceroute技術(shù)的測(cè)量可歸類(lèi)為基于ICMP協(xié)議的測(cè)量，而基于ICMP的測(cè)量方式具有限制少，適用性強(qiáng)的特點(diǎn)。但基于traceroute的網(wǎng)絡(luò)拓?fù)錅y(cè)量屬于主動(dòng)測(cè)量，測(cè)量過(guò)程中需發(fā)送大量的ICMP數(shù)據(jù)包，這會(huì)增加網(wǎng)絡(luò)的負(fù)擔(dān)；同時(shí)實(shí)現(xiàn)起來(lái)相對(duì)基于SNMP的測(cè)量方式也更為復(fù)雜，程序的執(zhí)行效率也比較低。即便如此，由于基于traceroute的測(cè)量方式在大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)中具有更強(qiáng)的普適性，因此在現(xiàn)代網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)中得到廣泛的應(yīng)用。

　　1.2.1網(wǎng)絡(luò)拓?fù)錅y(cè)量系統(tǒng)的整體設(shè)計(jì)

　　網(wǎng)絡(luò)拓?fù)錅y(cè)量系統(tǒng)旨在獲得并控制公開(kāi)、可控的traceroute服務(wù)器向一個(gè)或多個(gè)目標(biāo)IP同時(shí)發(fā)起traceroute測(cè)量，而將返回的結(jié)果整理成特定的形式后，再由后續(xù)的圖特征分析模塊對(duì)結(jié)果進(jìn)行分析。網(wǎng)絡(luò)拓?fù)錅y(cè)量系統(tǒng)的整體設(shè)計(jì)如圖2所示。1.2.2網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)系統(tǒng)的基本構(gòu)成

　　整個(gè)拓?fù)錅y(cè)量系統(tǒng)共含有四個(gè)主要模塊，各個(gè)模塊的功能和關(guān)鍵技術(shù)概括如下：

　　（1）服務(wù)器采集模塊

　　全球公開(kāi)的traceroute服務(wù)器Url列表往往由相關(guān)的組織機(jī)構(gòu)或個(gè)人以網(wǎng)頁(yè)的形式對(duì)外發(fā)布，如traceroute.org上就有公開(kāi)的約1000個(gè)分布于全球各地的traceroute服務(wù)器Url。服務(wù)器采集模塊的功能就是從相應(yīng)的traceroute服務(wù)器列表網(wǎng)頁(yè)中獲取全部有效的traceroute服務(wù)器Url，并將其存入數(shù)據(jù)庫(kù)中。同時(shí)，服務(wù)器采集模塊會(huì)定期檢測(cè)服務(wù)器列表中Url的有效性，并及時(shí)更新數(shù)據(jù)庫(kù)信息，以保證其時(shí)效性。

　�。�2）測(cè)量數(shù)據(jù)采集模塊

　　測(cè)量數(shù)據(jù)采集模塊的功能是讀取目標(biāo)IP地址列表，利用服務(wù)器采集模塊收集的traceroute服務(wù)器向所有目標(biāo)IP發(fā)起traceroute測(cè)量，同時(shí)獲取服務(wù)器端返回的結(jié)果，再提交給數(shù)據(jù)整理模塊對(duì)結(jié)果進(jìn)行分析整理。

　�。�3）數(shù)據(jù)整理模塊

　　數(shù)據(jù)整理模塊利用Python的BeautifulSoup庫(kù)和正則表達(dá)式，首先在返回的網(wǎng)頁(yè)中定位traceroute結(jié)果所在的標(biāo)簽，然后在該標(biāo)簽中抽取出traceroute路徑中每跳的IP地址，形成一條由源點(diǎn)服務(wù)器到目標(biāo)IP的完整的IP級(jí)路徑，并將其存入到與源服務(wù)器對(duì)應(yīng)的文件中。通常網(wǎng)絡(luò)拓?fù)涞臏y(cè)量結(jié)果由多個(gè)文件組成，每個(gè)文件描述某個(gè)源traceroute服務(wù)器到其測(cè)量的所有目標(biāo)IP的traceroute路徑。

　�。�4）拓?fù)浞治瞿�塊

　　拓?fù)浞治瞿�塊可以對(duì)最終獲得的拓?fù)鋱D進(jìn)行顯示或復(fù)雜網(wǎng)絡(luò)特征提取。通常拓?fù)鋱D的顯示可以依靠現(xiàn)有的軟件，如Ciada[5]的Otter。拓?fù)鋱D的分析采用復(fù)雜網(wǎng)絡(luò)特征提取的方法來(lái)分析大規(guī)模網(wǎng)絡(luò)的真實(shí)特征，尋找其結(jié)構(gòu)、動(dòng)力學(xué)和功能的內(nèi)在規(guī)律。2測(cè)量系統(tǒng)的測(cè)量結(jié)果分析

　　考慮利用網(wǎng)絡(luò)拓?fù)錅y(cè)量系統(tǒng)發(fā)現(xiàn)中國(guó)的IP級(jí)網(wǎng)絡(luò)拓?fù)�，然后從華盛頓大學(xué)的Iplane服務(wù)測(cè)量的全球拓?fù)渲刑崛≈袊?guó)網(wǎng)絡(luò)拓?fù)洌�并將其結(jié)果同測(cè)量系統(tǒng)發(fā)現(xiàn)的結(jié)果進(jìn)行復(fù)雜網(wǎng)絡(luò)特征分析。通過(guò)特征對(duì)比表明了測(cè)量系統(tǒng)的可用性。

　　首先，從Iplane上獲取其測(cè)量的全球拓?fù)洌瑢⑦@個(gè)網(wǎng)絡(luò)拓?fù)涿�名為IPLTopo。然后，利用GeoIP從Iplane的目標(biāo)IP集中篩選出所有位于中國(guó)的IP地址，形成一個(gè)中國(guó)目標(biāo)IP集CNTarget。隨后，利用拓?fù)錅y(cè)量系統(tǒng)以CNTarget為目標(biāo)進(jìn)行測(cè)量，獲取系統(tǒng)測(cè)量的全球拓?fù)銽mpTopo。最終，利用數(shù)據(jù)整理模塊從TmpTopo和IPLTopo中分別提取出中國(guó)的網(wǎng)絡(luò)拓?fù)�。其中，Iplane測(cè)量的中國(guó)拓?fù)浞Q(chēng)為IplaneTopo，系統(tǒng)測(cè)量的中國(guó)拓?fù)浞Q(chēng)為MyTopo。MyTopo與IplaneTopo的統(tǒng)計(jì)特征如表1所示。網(wǎng)絡(luò)拓?fù)涫且环N無(wú)權(quán)無(wú)向圖，設(shè)鏈接數(shù)為m，節(jié)點(diǎn)數(shù)為n。

　　2.1平均節(jié)點(diǎn)度

　　平均節(jié)點(diǎn)度用來(lái)表示無(wú)向連通圖的疏密程度，通常用k來(lái)表示，其中k=2m/n。由表1可以看出IplaneTopo的k值更大，表明Iplane發(fā)現(xiàn)的拓?fù)鋱D更加密集。這是由于MyTopo的測(cè)量源點(diǎn)更為豐富，決定了其可發(fā)現(xiàn)網(wǎng)絡(luò)中的大部分低密度的節(jié)點(diǎn)，并使得所有節(jié)點(diǎn)中低密度節(jié)點(diǎn)的比例很高，由此導(dǎo)致其平均節(jié)點(diǎn)度偏低。而IplaneTopo相對(duì)較少的測(cè)量源點(diǎn)更多地卻只能發(fā)現(xiàn)介數(shù)[6]較高的高度節(jié)點(diǎn)，使得結(jié)果的平均節(jié)點(diǎn)度更高。

　　2.2節(jié)點(diǎn)度分布

　　當(dāng)圖為非對(duì)稱(chēng)時(shí)，A為負(fù)數(shù)，表示低度節(jié)點(diǎn)與高度節(jié)點(diǎn)互聯(lián)的情況出現(xiàn)得較為頻繁；反之若圖是對(duì)稱(chēng)的，則A為正數(shù)。由圖4中的A值可以看出，MyTopo較IplaneTopo不相稱(chēng)性更加顯著。這就表明網(wǎng)絡(luò)拓?fù)錅y(cè)量系統(tǒng)發(fā)現(xiàn)了一部分度數(shù)較高的節(jié)點(diǎn)同很多度數(shù)較低節(jié)點(diǎn)相連接的情況，相應(yīng)部分網(wǎng)絡(luò)通常是用來(lái)給終端提供網(wǎng)絡(luò)接入的邊緣子網(wǎng)絡(luò)。薛健，等：IP級(jí)網(wǎng)絡(luò)拓?fù)錅y(cè)量技術(shù)的研究與實(shí)現(xiàn)

　　2.4聚集

　　在一個(gè)無(wú)向圖中，通常用一個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的鏈接數(shù)除以k（k-1）/2來(lái)計(jì)算度數(shù)為k的節(jié)點(diǎn)的局部聚集c。其中用c來(lái)表示c的均值，可以用該形式作為一種度量來(lái)描繪小世界[9]的現(xiàn)象。表示圖的傳遞性的T也可以作為另一種表述圖聚集性的單位，即用其表示當(dāng)節(jié)點(diǎn)v1與節(jié)點(diǎn)v2，v3分別連接，則v2和v3兩節(jié)點(diǎn)也相連的概率。通過(guò)圖4可以看出，IplaneTopo的兩個(gè)聚集特征均強(qiáng)于MyTopo，這點(diǎn)同之前發(fā)現(xiàn)的IplaneTopo的k較大、高度節(jié)點(diǎn)比例較大的特征相吻合。

　　2.5距離分布

　　在無(wú)向圖中，通常表示任選圖中任意兩個(gè)節(jié)點(diǎn)且兩者最短距離為d的概率時(shí)，用P（d）來(lái)描述。由于P（d）的概率密度函數(shù)類(lèi)似于高斯分布，因此可用均值d和方差σ來(lái)對(duì)其分布進(jìn)行表述。d的最大值dmax用來(lái)表示圖的直徑。由圖4可以看出，MyTopo的三個(gè)值均比IplaneTopo的小，這是由于MyTopo的拓?fù)湟?guī)模較IplaneTopo的更大，其中包括了更多的網(wǎng)絡(luò)節(jié)點(diǎn)以及鏈接，從而使得圖中任意兩點(diǎn)間包含更加豐富的路徑，且具更多的捷徑。

　　3結(jié)束語(yǔ)

　　本文分析了現(xiàn)有的兩種網(wǎng)絡(luò)拓?fù)錅y(cè)量技術(shù)—基于SNMP協(xié)議的網(wǎng)絡(luò)拓?fù)錅y(cè)量方法和基于traceroute技術(shù)的網(wǎng)絡(luò)拓?fù)錅y(cè)量方法。首先，描述SNMP方法的管理模型及算法實(shí)現(xiàn)，指出了其適用范圍較小，不適合大規(guī)模網(wǎng)絡(luò)拓?fù)錅y(cè)量的缺點(diǎn)；然后介紹了基于traceroute技術(shù)的網(wǎng)絡(luò)拓?fù)錅y(cè)量系統(tǒng)整體架構(gòu)及各個(gè)模塊的主要功能。隨后，利用拓?fù)錅y(cè)量系統(tǒng)測(cè)量了中國(guó)網(wǎng)絡(luò)拓?fù)�，并將其測(cè)量結(jié)果同Iplane測(cè)量的中國(guó)網(wǎng)絡(luò)拓?fù)溥M(jìn)行復(fù)雜網(wǎng)絡(luò)特征對(duì)比。通過(guò)對(duì)比發(fā)現(xiàn)，測(cè)量系統(tǒng)挖掘出的拓?fù)涓�加完整精確，證明了該系統(tǒng)具有一定的代表性和可用性。

　　當(dāng)然，系統(tǒng)的設(shè)計(jì)也存在著許多不足，主要有兩點(diǎn)。一是系統(tǒng)目前只能在一臺(tái)機(jī)器上采取串行的方式運(yùn)行，每個(gè)測(cè)量周期時(shí)間均較長(zhǎng)。可以考慮采取分布式測(cè)量的方式并發(fā)運(yùn)行系統(tǒng)進(jìn)行測(cè)量，其后再將各自的結(jié)果進(jìn)行整合。如此則一個(gè)測(cè)量周期的時(shí)間可以大幅縮短。二是為了獲得更為全面的網(wǎng)絡(luò)拓?fù)湫畔ⅲ�可以考慮將系統(tǒng)的測(cè)量結(jié)果同其它的拓?fù)浒l(fā)現(xiàn)項(xiàng)目的測(cè)量成果進(jìn)行合并，如caida的skitter[10]、DIMES等。這就使得測(cè)量結(jié)果更加完整，節(jié)省了主動(dòng)測(cè)量的開(kāi)銷(xiāo)，同時(shí)又進(jìn)一步縮短了測(cè)量周期。參考文獻(xiàn)：

　　[1]胡延平，王連杰，劉武，等.基于ICMP的網(wǎng)絡(luò)性能分析[J].計(jì)算機(jī)工程與設(shè)計(jì)，2003（4）：30-32.

　　[2]CHANSHG.Traceroute-basedtopologyinferencewithoutnetworkcoordinateestimation[C]//ProceedingsoftheSymposiumonInformationandNetworkSecurityofICC2008，2008，5：300-391.

　　[3]楊安義，朱華清，王繼龍.一種改進(jìn)的基于SNMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法及實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2007（10）：2412-2413，2419.

　　[4]劉琳琳.網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)的研究和實(shí)現(xiàn)[D].西安：西安電子科技大學(xué)，2006：25-35.

---

轉(zhuǎn)載請(qǐng)注明來(lái)自：http://www.jinnzone.com/jisuanjiwangluolw/34221.html