網(wǎng)絡(luò)拓?fù)淇焖侔l(fā)現(xiàn)方法分析范文

本站小編為你精心準(zhǔn)備了網(wǎng)絡(luò)拓?fù)淇焖侔l(fā)現(xiàn)方法分析參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

網(wǎng)絡(luò)拓?fù)?/a>結(jié)構(gòu)研究對(duì)自治域協(xié)議安全分析、網(wǎng)絡(luò)提供商（ISP）優(yōu)化網(wǎng)絡(luò)性能和網(wǎng)絡(luò)安全管理意義重大。網(wǎng)絡(luò)拓?fù)?a href="http://www.ruiyinglinkage.com/txcb/wltplw/683631.html" target="_blank">發(fā)現(xiàn)根據(jù)路由等網(wǎng)絡(luò)元素存儲(chǔ)的轉(zhuǎn)發(fā)路徑信息或網(wǎng)絡(luò)主動(dòng)測(cè)量獲取的逐跳路徑信息，對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行獲取和分析。網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法分為基于路由轉(zhuǎn)發(fā)表、基于簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議（SNMP）和管理信息庫(kù)（MIB）信息以及基于因特網(wǎng)控制報(bào)文協(xié)議（ICMP）3種路徑探測(cè)分析方法?；诼酚赊D(zhuǎn)發(fā)表的方法利用邊界網(wǎng)關(guān)協(xié)議（BGP）和開(kāi)放式最短路徑優(yōu)先協(xié)議（OSPF）等路由協(xié)議，對(duì)自治域間和自治域內(nèi)進(jìn)行網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)。該方法優(yōu)點(diǎn)是速度快以及網(wǎng)絡(luò)負(fù)載小，缺點(diǎn)是發(fā)現(xiàn)范圍有限，范圍僅取決于獲取路由轉(zhuǎn)發(fā)表的網(wǎng)絡(luò)范圍；基于SNMP和MIB信息的方法是通過(guò)SNMP訪問(wèn)路由器、交換機(jī)或網(wǎng)橋中的MIB庫(kù)，通過(guò)MIB庫(kù)中的IP路由表、接口表及其他信息分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。該方法優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、速度快且準(zhǔn)確率高，缺點(diǎn)是MIB庫(kù)的訪問(wèn)權(quán)限難以獲取，無(wú)法對(duì)整個(gè)互聯(lián)網(wǎng)進(jìn)行網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)。基于ICMP的路徑探測(cè)分析方法一般使用回送請(qǐng)求和回送應(yīng)答，通過(guò)存活時(shí)間（TTL）設(shè)置，對(duì)互聯(lián)網(wǎng)拓?fù)渎窂竭M(jìn)行發(fā)現(xiàn)，通常包含地址集構(gòu)造探測(cè)、存活主機(jī)探測(cè)、路徑和時(shí)延信息探測(cè)以及拓?fù)浣Y(jié)構(gòu)生成與顯示4個(gè)階段。該方法優(yōu)點(diǎn)是探測(cè)地址可靈活選擇以及不依賴路由器或交換機(jī)的訪問(wèn)權(quán)限，缺點(diǎn)是網(wǎng)絡(luò)負(fù)載大且速度慢。上述3種網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法各有優(yōu)缺點(diǎn)。由于互聯(lián)網(wǎng)地址規(guī)模龐大、自治域間和自治域內(nèi)路由協(xié)議不同以及眾多網(wǎng)絡(luò)元素訪問(wèn)權(quán)限獲取難度大，因此對(duì)互聯(lián)網(wǎng)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)主要采用基于ICMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法。隨著互聯(lián)網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究的不斷深入，發(fā)現(xiàn)了互聯(lián)網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的各種特性，如冪率特性、魯棒且脆弱性和聚集特性［4］等，以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不同度量指標(biāo)（節(jié)點(diǎn)度分布、聚集系數(shù)、介數(shù)、核數(shù)和平均路徑長(zhǎng)度）等其他特性。利用上述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性可優(yōu)化拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)方法，提高拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)效率，降低正常網(wǎng)絡(luò)流量的擾動(dòng)。鑒于ICMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法存在注入網(wǎng)絡(luò)數(shù)據(jù)量大和時(shí)效不高等問(wèn)題，將互聯(lián)網(wǎng)結(jié)構(gòu)特性與網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法結(jié)合，提出了一種基于路徑前綴匹配和雙向探測(cè)的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法，從而降低了注入網(wǎng)絡(luò)的流量負(fù)載，有效提高了網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)的時(shí)間效率。

1路徑探測(cè)

Traceroute是最早利用ICMP進(jìn)行報(bào)文傳輸路徑探測(cè)的工具，由VanJacobson在1989年開(kāi)發(fā)［5］。其原理是發(fā)送報(bào)文TTL遞增的用戶數(shù)據(jù)報(bào)協(xié)議（UDP）報(bào)文，在探測(cè)報(bào)文從源端到目的端的傳送路徑中每經(jīng)過(guò)一個(gè)路由其報(bào)文TTL值自動(dòng)減1，當(dāng)報(bào)文TTL值為0時(shí)，路由器向源端返回報(bào)文TTL超時(shí)的報(bào)文，當(dāng)?shù)竭_(dá)目的端時(shí)，由于UDP端口選擇較大（＞1024）的目的端口，將返回端口不可達(dá)報(bào)文。因此設(shè)置首個(gè)探測(cè)報(bào)文TTL值為1，后續(xù)探測(cè)報(bào)文TTL值逐次加1，可根據(jù)返回的TTL超時(shí)報(bào)文和目的端返回的端口不可達(dá)報(bào)文中IP地址，獲取源端到目的端的網(wǎng)絡(luò)路徑信息。

Skitter是由加利福尼亞大學(xué)互聯(lián)網(wǎng)應(yīng)用數(shù)據(jù)分析中心（CAIDA）開(kāi)發(fā)的分布式網(wǎng)絡(luò)測(cè)量工具，在美國(guó)、英國(guó)、加拿大和法國(guó)等國(guó)家分別部署了24個(gè)測(cè)量點(diǎn)。基于傳輸控制協(xié)議（TCP）報(bào)文實(shí)現(xiàn)Traceroute，使用常用端口可確保報(bào)文到達(dá)目的端時(shí)通過(guò)防火墻的過(guò)濾規(guī)則。24個(gè)測(cè)量點(diǎn)共用由971080個(gè)IPv4地址構(gòu)成的目標(biāo)地址集，每3d完成一次對(duì)地址集的路徑及報(bào)文往返時(shí)間（RTT）的測(cè)量循環(huán)。Mercator與Skitter類似，采用分布式測(cè)量方法對(duì)大規(guī)模網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和鏈路時(shí)延進(jìn)行測(cè)量。主要區(qū)別：Mercator采用啟發(fā)式地址集隨機(jī)生成機(jī)制，可自適應(yīng)構(gòu)造探測(cè)地址集，而不依賴于解析BGP路由表和域名解析服務(wù)（DNS）數(shù)據(jù)庫(kù)等手段。Mercator通過(guò)改進(jìn)Traceroute實(shí)現(xiàn)2個(gè)目標(biāo)：1）任意位置部署；2）無(wú)需額外輸入，僅依賴有限TTL值探測(cè)報(bào)文，但Mercator啟發(fā)式地址生成機(jī)制可能產(chǎn)生較大的探測(cè)流量。Rocketfuel針對(duì)ISP網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行發(fā)現(xiàn)和構(gòu)造，采用直接探測(cè)機(jī)制和路由器接口聚合機(jī)制以提高拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)和構(gòu)造效率。直接探測(cè)機(jī)制利用BGP路由表對(duì)經(jīng)過(guò)ISP的探測(cè)路徑進(jìn)行篩選，減少了探測(cè)地址和路徑數(shù)量。路由器接口聚合機(jī)制可根據(jù)探測(cè)路徑中路由接口特征，識(shí)別相同路由器的不同接口并聚合為唯一的路由器地址，從而提高拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)的準(zhǔn)確性和效率。以上方法分別針對(duì)基于ICMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)的不同方面，解決了分布式網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)、啟發(fā)式地址集構(gòu)造和路由器接口聚合等問(wèn)題。對(duì)于每個(gè)測(cè)量點(diǎn)，注入網(wǎng)絡(luò)數(shù)據(jù)量大和時(shí)間效率低仍是影響互聯(lián)網(wǎng)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)的重點(diǎn)問(wèn)題。本文根據(jù)互聯(lián)網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)，改進(jìn)了互聯(lián)網(wǎng)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法，從而降低了探測(cè)數(shù)據(jù)流量并提高了時(shí)間效率。

2雙向探測(cè)

基于ICMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法普遍采用TTL單向增長(zhǎng)Traceroute方法，對(duì)測(cè)量點(diǎn)到目標(biāo)網(wǎng)絡(luò)設(shè)備的網(wǎng)絡(luò)路徑進(jìn)行測(cè)量，如圖1所示。其中，TTL－x為探測(cè)端TTL為x的探測(cè)報(bào)文；ICMP－TE為路由丟棄TTL超時(shí)報(bào)文時(shí)的響應(yīng)報(bào)文；ICMP－DU為目標(biāo)網(wǎng)絡(luò)地址的目標(biāo)端口不可達(dá)響應(yīng)報(bào)文。探測(cè)端向目標(biāo)網(wǎng)絡(luò)設(shè)備發(fā)送TTL由1開(kāi)始，以1為步長(zhǎng)遞增的TCP，UDP或ICMP報(bào)文。當(dāng)TTL＝i的探測(cè)報(bào)文發(fā)送后，等待接收路由器Ri的超時(shí)返回報(bào)文或目標(biāo)網(wǎng)絡(luò)設(shè)備的端口不可達(dá)報(bào)文，并記錄路徑第i跳的路由接口地址以及報(bào)文RTT或目標(biāo)網(wǎng)絡(luò)設(shè)備報(bào)文往返時(shí)間。若接收時(shí)間超時(shí)，則對(duì)TTL＝i路由地址重新探測(cè)。連續(xù)3次探測(cè)失敗后，則認(rèn)為該路由為匿名路由，設(shè)置該路由接口地址為NULL并對(duì)TTL＝i＋1的路由地址繼續(xù)進(jìn)行探測(cè)。若連續(xù)3個(gè)路由均無(wú)法探測(cè)成功，則認(rèn)為該目標(biāo)網(wǎng)絡(luò)設(shè)備無(wú)法到達(dá)，放棄該網(wǎng)絡(luò)設(shè)備的路徑探測(cè)。按照目前Traceroute方法對(duì)多個(gè)IP地址進(jìn)行測(cè)量時(shí)，由于互聯(lián)網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)的聚集特點(diǎn)，路徑中大量路由節(jié)點(diǎn)將會(huì)重復(fù)探測(cè)。圖2給出了網(wǎng)絡(luò)聚集結(jié)構(gòu)特點(diǎn)，當(dāng)從探測(cè)點(diǎn)s1到目標(biāo)網(wǎng)絡(luò)設(shè)備d1，d2和d3進(jìn)行測(cè)量時(shí)，路由器R1將會(huì)在每次測(cè)量中進(jìn)行探測(cè)。由于互聯(lián)網(wǎng)網(wǎng)絡(luò)規(guī)模龐大，對(duì)整個(gè)互聯(lián)網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的發(fā)現(xiàn)和測(cè)量的工作量將是巨大的和重復(fù)的，故增加了探測(cè)數(shù)據(jù)流量和時(shí)間代價(jià)。針對(duì)互聯(lián)網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特點(diǎn)以及網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法重復(fù)探測(cè)率高的問(wèn)題，提出了雙向探測(cè)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)方法。

3前綴匹配哈希表與TTL切割線

在雙向探測(cè)Traceroute方法TTL遞減過(guò)程中，需要每次對(duì)返回的超時(shí)報(bào)文地址進(jìn)行查表，其結(jié)果決定是否繼續(xù)遞減探測(cè)。前綴匹配表的結(jié)構(gòu)對(duì)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)發(fā)送的探測(cè)流量和時(shí)間效率產(chǎn)生較大影響，應(yīng)從查詢速度和表的大小2方面考慮，使用哈希表能較好地滿足以上2項(xiàng)要求。探測(cè)端負(fù)責(zé)維護(hù)1個(gè)哈希表組，分別以每個(gè)TTL值建立1個(gè)哈希表，第i個(gè)哈希表為從探測(cè)端出發(fā)第i跳的常見(jiàn)路由地址及其前i－1跳的路徑信息。隨著TTL的增加，路由器地址將以指數(shù)級(jí)增加。為了控制哈希表規(guī)模，當(dāng)TTL＝i的路由地址在哈希表查詢失敗時(shí)，該地址和路徑前綴信息不插入哈希表，而插入待哈希列表。利用定期掃描待哈希列表對(duì)哈希表進(jìn)行更新，從而確保命中率以及哈希表規(guī)?？煽?。根據(jù)文獻(xiàn)，互聯(lián)網(wǎng)作為小世界網(wǎng)絡(luò)，其節(jié)點(diǎn)平均距離是19個(gè)連接，因此取中間值10作為初始TTL切割線，分別建立TTL＝1～TTL＝10的10個(gè)哈希表。探測(cè)過(guò)程中不斷掃描待哈希列表對(duì)哈希表更新，對(duì)10個(gè)哈希表的命中率進(jìn)行分析，將命中率最高的TTL值作為分割線，對(duì)小于分割線的TTL段和大于分割線的TTL段進(jìn)行遞減和遞增探測(cè)。

4試驗(yàn)驗(yàn)證

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)方法的評(píng)價(jià)標(biāo)準(zhǔn)分為完備性、時(shí)間效率、網(wǎng)絡(luò)負(fù)載和準(zhǔn)確性4方面。其中，完備性指拓?fù)浒l(fā)現(xiàn)可能獲取的網(wǎng)絡(luò)覆蓋范圍是否對(duì)所有網(wǎng)絡(luò)設(shè)備進(jìn)行發(fā)現(xiàn)；時(shí)間效率從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)所需時(shí)間衡量方法優(yōu)劣性；網(wǎng)絡(luò)負(fù)載指網(wǎng)絡(luò)探測(cè)過(guò)程中對(duì)網(wǎng)絡(luò)流量的影響大小；準(zhǔn)確性針對(duì)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)結(jié)果與真實(shí)網(wǎng)絡(luò)的誤差進(jìn)行分析。為了對(duì)基于ICMP的雙向網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法的網(wǎng)絡(luò)負(fù)載、時(shí)間效率和準(zhǔn)確性進(jìn)行分析，本文對(duì)中國(guó)教育網(wǎng)的所有網(wǎng)段利用ICMPping進(jìn)行掃描獲取探測(cè)地址集，共獲得活躍的主機(jī)地址10713個(gè)，針對(duì)該地址集分別使用傳統(tǒng)Traceroute和雙向探測(cè)Traceroute方法進(jìn)行試驗(yàn)對(duì)比。傳統(tǒng)Traceroute方法以TTL＝1遞增探測(cè)，雙向探測(cè)Traceroute方法以TTL＝10為初始值，哈希表大小設(shè)為100，目標(biāo)地址集為中國(guó)教育網(wǎng)內(nèi)活躍的主機(jī)中隨機(jī)抽取不同規(guī)模的10個(gè)地址集，其探測(cè)結(jié)果從完備性、時(shí)間效率、網(wǎng)絡(luò)負(fù)載和準(zhǔn)確4方面對(duì)比。1）完備性雙向探測(cè)Traceroute方法僅針對(duì)探測(cè)過(guò)程進(jìn)行改進(jìn)，未涉及改進(jìn)探測(cè)地址集的生成技術(shù)。因此，從完備性角度，該方法與傳統(tǒng)Traceroute方法相同。2）時(shí)間效率從探測(cè)地址集隨機(jī)抽取1000，2000，…，10000個(gè)地址建立不同規(guī)模的探測(cè)地址集10個(gè)，探測(cè)地址集完成探測(cè)所需時(shí)間如圖4所示。由圖4可見(jiàn)，雙向探測(cè)與傳統(tǒng)Traceroute方法相比，降低了探測(cè)時(shí)間，且在一定規(guī)模的探測(cè)地址集內(nèi)，隨地址集規(guī)模的增大，降低探測(cè)時(shí)間的程度也隨之增加。3）網(wǎng)絡(luò)負(fù)載網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)探測(cè)所需流量是網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)的一個(gè)重要因素，探測(cè)過(guò)程應(yīng)盡可能降低正常網(wǎng)絡(luò)業(yè)務(wù)流量的干擾。利用上述10個(gè)探測(cè)地址集，對(duì)探測(cè)過(guò)程中的發(fā)包數(shù)進(jìn)行統(tǒng)計(jì)，如圖5所示。由圖5可見(jiàn)，雙向探測(cè)方法注入網(wǎng)絡(luò)的數(shù)據(jù)流量較傳統(tǒng)Traceroute方法較少，故降低了對(duì)正常網(wǎng)絡(luò)業(yè)務(wù)數(shù)據(jù)流量的影響。4）準(zhǔn)確性由于難以獲取實(shí)際網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，本文僅對(duì)雙向探測(cè)和傳統(tǒng)Traceroute方法的準(zhǔn)確性進(jìn)行對(duì)比，以獲取目標(biāo)網(wǎng)絡(luò)地址完全路徑的比例為參考標(biāo)準(zhǔn)，在一定程度上可反映網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法的準(zhǔn)確性。利用上述10個(gè)探測(cè)地址集，其中最后一跳能夠到達(dá)目標(biāo)網(wǎng)絡(luò)設(shè)備IP地址的數(shù)量比例如表1所示。由表1可見(jiàn)，在地址集中目標(biāo)網(wǎng)絡(luò)設(shè)備的探測(cè)結(jié)果中，獲取完全路徑的目標(biāo)網(wǎng)絡(luò)設(shè)備約為59％。因?qū)χ袊?guó)教育網(wǎng)全部網(wǎng)段ping掃描需持續(xù)約30h，而教育網(wǎng)中活躍主機(jī)的IP地址在一定時(shí)間范圍內(nèi)會(huì)發(fā)生變化，因此不能獲得地址集中所有IP地址的網(wǎng)絡(luò)路徑。從準(zhǔn)確性角度，雙向探測(cè)方法與傳統(tǒng)Traceroute方法差別不大，均能獲得活躍主機(jī)的網(wǎng)絡(luò)路徑信息。

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

目前，基于ICMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法是互聯(lián)網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)的主要方法，利用ICMP對(duì)互聯(lián)網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)的各項(xiàng)目和工具均存在注入網(wǎng)絡(luò)數(shù)據(jù)流量大和時(shí)間效率低的問(wèn)題。本文使用TTL雙向探測(cè)和前綴匹配哈希表對(duì)傳統(tǒng)TTL單向遞增的Traceroute方法進(jìn)行改進(jìn)，對(duì)中國(guó)教育網(wǎng)中活躍主機(jī)進(jìn)行了掃描和探測(cè)。試驗(yàn)表明，雙向探測(cè)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)方法能夠減少正常網(wǎng)絡(luò)業(yè)務(wù)數(shù)據(jù)流量的擾動(dòng)，并減少互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)所需時(shí)間。

作者：王志釗 陸余良 楊國(guó)正 單位：合肥電子工程學(xué)院網(wǎng)絡(luò)系