[發(fā)明專利]基于拓?fù)錁涞幕厮菔铰酚杉?jí)網(wǎng)絡(luò)拓?fù)錂z測(cè)方法

無效

• 申請(qǐng)?zhí)枺?/td>: 200810056013.5
• 申請(qǐng)日: 2008-01-11
• 公開（公告）號(hào): CN101217428A
• 公開（公告）日: 2008-07-09
• 發(fā)明（設(shè)計(jì)）人: 何涇沙;李波;石恒華
• 申請(qǐng)（專利權(quán)）人: 北京工業(yè)大學(xué)
• 主分類號(hào): H04L12/26
• 分類號(hào): H04L12/26;H04L12/24;H04L12/56
• 代理公司: 北京思海天達(dá)知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 劉萍

技術(shù)領(lǐng)域

本發(fā)明涉及一種大規(guī)模網(wǎng)絡(luò)的快速拓?fù)錂z測(cè)方法，能有效地提高大規(guī)模網(wǎng)絡(luò)拓?fù)錂z測(cè)的效率和減少所需的檢測(cè)時(shí)間，屬于網(wǎng)絡(luò)拓?fù)錂z測(cè)領(lǐng)域。

背景技術(shù)

目前，常見的路由級(jí)網(wǎng)絡(luò)拓?fù)錂z測(cè)方法都是基于網(wǎng)絡(luò)數(shù)據(jù)包的生存時(shí)間(TTL)限制進(jìn)行的，基本原理，是首先從檢測(cè)點(diǎn)發(fā)送TTL字段為1的數(shù)據(jù)包到目的地址，從檢測(cè)點(diǎn)到目的地址的網(wǎng)絡(luò)路徑中第一個(gè)路由器接收到此數(shù)據(jù)包后，向檢測(cè)源發(fā)回一個(gè)ICMP“超時(shí)”數(shù)據(jù)包，此數(shù)據(jù)包中包含該路由器的接口IP地址，然后檢測(cè)源發(fā)送TTL字段為2的數(shù)據(jù)包到目的地址，網(wǎng)絡(luò)路徑中第二個(gè)路由器接收到此數(shù)據(jù)包后向檢測(cè)源發(fā)回ICMP“超時(shí)”數(shù)據(jù)包，從而得到第二個(gè)路由器的接口IP地址，循環(huán)往復(fù)從而得到從檢測(cè)源到目的地址的整條路徑中的所有路由器接口IP。通過檢測(cè)大量檢測(cè)源和目的地址對(duì)，就可以得到整個(gè)網(wǎng)絡(luò)中路由器的接口IP信息，進(jìn)一步處理即可得到整個(gè)網(wǎng)絡(luò)的路由級(jí)拓?fù)洹Ｓ捎谛枰獙?duì)網(wǎng)絡(luò)中每條路徑進(jìn)行檢測(cè)，因此網(wǎng)絡(luò)中不同路徑的交叉部分會(huì)被反復(fù)檢測(cè)到，特別是在大規(guī)模的網(wǎng)絡(luò)拓?fù)錂z測(cè)中這種冗余度是非常高的。為了降低冗余度、提高檢測(cè)效率和降低拓?fù)錂z測(cè)時(shí)間，出現(xiàn)了一些改進(jìn)型的方法，它們根據(jù)不同的算法將第一個(gè)檢測(cè)數(shù)據(jù)包的TTL值設(shè)置為大于1的某個(gè)值，從而在一定的概率范圍內(nèi)降低檢測(cè)的冗余度，但是這種概率是不確定的，在網(wǎng)絡(luò)拓?fù)錂z測(cè)過程中，在整個(gè)拓?fù)涞哪承┚植繖z測(cè)中這種改進(jìn)能有效地降低冗余度，而其它一些則只能有較少的冗余度降低。

發(fā)明內(nèi)容

為了克服現(xiàn)有路由級(jí)拓?fù)錂z測(cè)方法中初始TTL值設(shè)置的不確定性，進(jìn)一步降低撲檢測(cè)的冗余度和提高檢測(cè)效率，本發(fā)明利用目的地址集合中對(duì)檢測(cè)做出響應(yīng)的目的地址，取得其返回的數(shù)據(jù)包并分析出目的地址與檢測(cè)源的距離，從而確定初始檢測(cè)數(shù)據(jù)包的TTL值，在取得部分網(wǎng)絡(luò)拓?fù)湫畔⒑筮M(jìn)行分析，從而指導(dǎo)后續(xù)檢測(cè)工作的繼續(xù)進(jìn)行。

本發(fā)明解決其技術(shù)問題所采用的技術(shù)方案是：1)以255作為網(wǎng)絡(luò)數(shù)據(jù)包的生存時(shí)間TTL針對(duì)所有的目的地址進(jìn)行一次探測(cè)；還可以64或者128作為網(wǎng)絡(luò)數(shù)據(jù)包的生存時(shí)間TTL；

2)當(dāng)某個(gè)目的地址有響應(yīng)時(shí)，取得該響應(yīng)數(shù)據(jù)包的TTL字段值；

3)目前各種操作系統(tǒng)默認(rèn)將響應(yīng)數(shù)據(jù)包的TTL值設(shè)置為16、32、64、128或255，上述取得的響應(yīng)數(shù)據(jù)包的TTL與這五個(gè)值中稍大于它的值之差的絕對(duì)值為目的地址和檢測(cè)源的路徑長(zhǎng)度N；

4)利用拓?fù)鋱D的樹狀特性，從目的地址開始回溯網(wǎng)絡(luò)拓?fù)洌词褂肨TL＝N-1、TTL＝N-2、TTL＝N-3直至TTL＝1的數(shù)據(jù)包檢測(cè)目的地址，并記錄下得到的路由器接口地址；當(dāng)探測(cè)到某個(gè)已經(jīng)發(fā)現(xiàn)的路由器接口時(shí)，對(duì)此目的地址的探測(cè)過程中止，繼續(xù)探測(cè)下一個(gè)目的地址；

當(dāng)目的地址集中沒有對(duì)檢測(cè)做出響應(yīng)的地址會(huì)被忽略，拓?fù)錂z測(cè)過程以下一個(gè)目的地址為檢測(cè)地址繼續(xù)進(jìn)行；

5)完成對(duì)全部目的地址集的一次掃描之后，得到整個(gè)實(shí)際網(wǎng)絡(luò)拓?fù)涞囊徊糠郑藭r(shí)分析得到的拓?fù)鋱D，找出拓?fù)鋱D中出度乘以路徑長(zhǎng)度值最大的拓?fù)涔?jié)點(diǎn)作為最優(yōu)節(jié)點(diǎn)；

6)以上述最優(yōu)節(jié)點(diǎn)的路徑長(zhǎng)度為初始檢測(cè)數(shù)據(jù)包的TTL值來回溯檢測(cè)目的地址集中沒有響應(yīng)的地址，并記錄得到拓?fù)洌瓿烧麄€(gè)拓?fù)錂z測(cè)過程。

本發(fā)明的有益效果是，可以有效地降低網(wǎng)絡(luò)拓?fù)錂z測(cè)的冗余度，減少拓?fù)錂z測(cè)時(shí)間和提高拓?fù)浒l(fā)現(xiàn)效率，同時(shí)操作和實(shí)施起來比較方便。

附圖說明

圖1是原始的拓?fù)錂z測(cè)算法圖。

圖2是改進(jìn)后的拓?fù)錂z測(cè)算法圖

圖3是回溯式拓?fù)錂z測(cè)算法圖

圖4是回溯式拓?fù)錂z測(cè)算法首輪探測(cè)后發(fā)現(xiàn)的網(wǎng)絡(luò)拓?fù)?/p>

其中R1、R2、R3、R4、R5、R6、R7、R8、R9代表路由器1-9

D(Destination)1、D2、D3、D4、D5代表目的地址1-5

M(Monitor)代表檢測(cè)源

具體實(shí)施方式

在圖3所示實(shí)施例中，目的地址集合為D1、D2、D3、D4和D5，M為檢測(cè)源，R1、R2、R3、R4、R5、R6、R7、R8和R9為網(wǎng)絡(luò)拓?fù)渲械?個(gè)路由器。

1)以255作為網(wǎng)絡(luò)數(shù)據(jù)包的生存時(shí)間TTL針對(duì)目的地址集里的5個(gè)目的地址進(jìn)行一次探測(cè)。

2)當(dāng)某個(gè)目的地址有響應(yīng)時(shí)，取得響應(yīng)數(shù)據(jù)包的TTL字段值。其中D1、D2和D4對(duì)探測(cè)做出響應(yīng)，返回相應(yīng)的響應(yīng)數(shù)據(jù)包。從三個(gè)響應(yīng)數(shù)據(jù)包得到各自的TTL值，分別為TTL1＝251，TTL2＝124，TTL4＝60。