焦彥平++李唱++陳東寧

摘 要：隨著網(wǎng)絡(luò)的不斷發(fā)展，其拓?fù)浣Y(jié)構(gòu)變得越來越復(fù)雜，其獲取也變得越來越困難，該文介紹分析了網(wǎng)絡(luò)拓?fù)浼夹g(shù)的發(fā)展現(xiàn)狀，分析了現(xiàn)有網(wǎng)絡(luò)拓?fù)浼夹g(shù)的不足，并且提出了基于STP、SNMP和ICMP三種常見協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法。

關(guān)鍵詞：網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn) STP SNMP ICMP

中圖分類號：TP393 文獻標(biāo)識碼：A 文章編號：1674-098X（2014）07（b）-0046-05

隨著網(wǎng)絡(luò)的不斷發(fā)展與普及，網(wǎng)絡(luò)的規(guī)模變得越來越大，網(wǎng)絡(luò)的結(jié)構(gòu)變得越來越復(fù)雜，對網(wǎng)絡(luò)進行有效的管理和控制是保證網(wǎng)絡(luò)處在正常高效運轉(zhuǎn)的關(guān)鍵。但對網(wǎng)絡(luò)進行有效的管理首先要獲得網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，而網(wǎng)絡(luò)的結(jié)構(gòu)復(fù)雜、節(jié)點數(shù)目繁多，靠人工統(tǒng)計往往是行不通的，而目前的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)又存在著一定的不足，所以研究更加有效的手段來得到網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)具有重大的意義。

1 網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法研究

在網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)方面，美國康奈爾大學(xué)的CNRG網(wǎng)絡(luò)研究組、CAIDA組織的Skitter [1]和貝爾實驗室在這方面都有了深入的研究，他們設(shè)計的算法及其技術(shù)都已經(jīng)具有較好的應(yīng)用，并且已經(jīng)進行了商用。

在物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法中，由于交換機轉(zhuǎn)發(fā)數(shù)據(jù)具有透明性的特點，這就給物理層的拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)帶來了很大的困難。針對物理網(wǎng)絡(luò)中的拓?fù)浒l(fā)現(xiàn)問題，中科院計算所的鄭海提出了能依賴不完整的交換機AFT來發(fā)現(xiàn)物理網(wǎng)絡(luò)拓?fù)涞乃惴╗2]，隨后他們在此基礎(chǔ)上進一步解決了子網(wǎng)中存在Hub的判定情況[3]，但存在的不足在于它們都不能準(zhǔn)確判定鏈路是否為冗余鏈路。文獻[4]和[5]給出了基于端口流量的拓?fù)浒l(fā)現(xiàn)算法，通過對端口流量數(shù)據(jù)的分析進而實現(xiàn)了網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)，但是該方法的實際數(shù)據(jù)無法準(zhǔn)確獲得，并且獲得的數(shù)據(jù)可能存在很大的誤差，不具有實際的應(yīng)用性。文獻[6]和[7]中利用交換機地址轉(zhuǎn)發(fā)表的數(shù)據(jù)構(gòu)建了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，是一種數(shù)據(jù)鏈路層的拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)方法，但是這種方法無法對啞交換機（不能通過SNMP協(xié)議訪問的交換機）進行有效的發(fā)現(xiàn)。文獻[8]和[9]同樣給出了一種基于生成樹協(xié)議（Spanning Tree Protocol，STP）的數(shù)據(jù)鏈路層網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，這種算法具有分析得到啞交換機的連接關(guān)系的能力，但是其缺點是無法發(fā)現(xiàn)交換機與主機的關(guān)系，并且要求交換機支持STP協(xié)議才能有效。

IETF于2000年推出物理拓?fù)銶IB （Management Information Base）[10]，它IP網(wǎng)絡(luò)的相關(guān)對象如圖1所示。IETF試圖去解決網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)的問題，但是IETF并沒有具體給出如何獲取MIB的具體方法，只能通過一些通用的協(xié)議來獲取MIB。

2 基于STP協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法

生成樹協(xié)議（Spanning Tree Protocol，STP）的主要功能有兩個：一是創(chuàng)建以某臺交換機為跟的網(wǎng)絡(luò)拓?fù)渖蓸?，同時能夠避免環(huán)路的產(chǎn)生。二是在網(wǎng)絡(luò)拓?fù)浒l(fā)生改變時，能夠達到收斂保護的目的。算法能夠?qū)崿F(xiàn)的基礎(chǔ)在于網(wǎng)絡(luò)中每臺交換機都在Bridge MIB中保存了其交換域生成樹的一部分，利用SNMP協(xié)議來獲取MIB中的這些信息，再根據(jù)STP協(xié)議的特征，通過比較就可以得到整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。根據(jù)STP協(xié)議我們可以推導(dǎo)出以下八條結(jié)論[11-12]，這幾條結(jié)論可以幫助我們判斷各個端口的關(guān)系。

結(jié)論一：設(shè)交換機的根接口指定網(wǎng)橋為，指定接口為，由于能運行生成樹協(xié)議的必須是交換機，所以必為交換機，且、通過接口、直連或通過集線器互連（設(shè)備級直連）。

結(jié)論二：處于轉(zhuǎn)發(fā)狀態(tài)的接口為所在網(wǎng)段內(nèi)的其他網(wǎng)橋傳播信息，所以必須存在連接。若無連接，它不會參與生成樹算法，也就不可能有轉(zhuǎn)發(fā)狀態(tài)。

結(jié)論三：阻塞接口若無連接存在，則生成樹協(xié)議不會令其阻塞，它一定是進行冗余備份的線路。所以若阻塞接口的指定網(wǎng)橋非本交換機，其上一定有連接存在。

結(jié)論四：對于設(shè)備級直連交換機、的兩接口、，若，則、通過集線器連接，反之，接口、直連。其中表示交換機通過接口收到數(shù)據(jù)包的源MAC地址集，表示交換機通過接口收到數(shù)據(jù)包的源MAC地址集。

結(jié)論五：假設(shè)交換機接口的地址轉(zhuǎn)發(fā)表中僅包含主機設(shè)備，若主機數(shù)目為1，則該接口與主機直連；若主機數(shù)目大于l，則該接口通過集線器連接主機群。

結(jié)論六：若交換機接口的地址轉(zhuǎn)發(fā)表中無其他交換機的地址信息但包含路由器地址，則該接口與路由器直連。若交換機接口的地址轉(zhuǎn)發(fā)表中無其他交換機和路由器的地址信息，則它與轉(zhuǎn)發(fā)表中的主機設(shè)各級直連，通過結(jié)論五進行連接確認(rèn)。

結(jié)論七：若的非根端口的指派網(wǎng)橋為（），且端口的狀態(tài)是阻塞的，且的非根端口的指派端口與的指派端口相等，那么與直連，且該鏈路是備份鏈路。

結(jié)論八：滿足規(guī)則1的2個端口與，不妨假定是根端口，是非根端口，若存在其他端口（）與滿足規(guī)則1，那么、與之間必定存在集線器或啞交換機等不支持SNMP 的設(shè)備。

利用上述的八條結(jié)論，可以得出基于STP協(xié)議的拓?fù)浒l(fā)現(xiàn)算法：根據(jù)結(jié)論一，當(dāng)發(fā)現(xiàn)未知的網(wǎng)橋時，它一定是啞交換機。以根交換機為源地址Ping啞交換機，利用結(jié)論二查找拓?fù)浣Y(jié)構(gòu)生成樹的內(nèi)容，如果其中包含啞交換機的MAC地址，則認(rèn)為它們之間存在直接相連的關(guān)系。其中偽造根交換機為源地址的Ping數(shù)據(jù)包是為了滿足生成樹轉(zhuǎn)發(fā)下行接口的完備性。STP發(fā)現(xiàn)算法利用網(wǎng)絡(luò)OSI第二層連接信息生成網(wǎng)絡(luò)拓?fù)鋱D，按廣度優(yōu)先遍歷、先主干后備份的順序進行，算法流程如圖2所示。

詳細描述如下：

（1）對網(wǎng)絡(luò)中所有的設(shè)備進行訪問，對交換機進行識別并且存入臨時鏈表A中。

（2）將鏈表A中的所有交換機IP逐個取出來，并通過SNMP協(xié)議訪問同時記錄根網(wǎng)橋MAC地址、本機的根接口、處于轉(zhuǎn)發(fā)和阻塞接口的指定網(wǎng)橋MAC及其指定接口。endprint

（3）對網(wǎng)絡(luò)拓?fù)渖蓸溥M行廣度優(yōu)先遍歷。根據(jù)STP協(xié)議可以得到交換區(qū)域的根網(wǎng)橋，而后將根網(wǎng)橋加入到FIFO（先進先出隊列）的等待進一步檢測的隊列B中。

（4）從隊列B中取出一個交換機放入鏈表C中。在臨時鏈表A中找出根接口的指定交換機為的交換機信息逐一添入待檢測隊列B中。由結(jié)論一、三可知它們屬于設(shè)備級直連，并從臨時鏈表A中去除該交換機信息。

（5）重復(fù)4，直到隊列B為空。

（6）判斷添加交換機連接：查詢鏈表C中每個交換機接口的指定網(wǎng)橋和指定接口，若存在相同的交換機，則說明它們與指定的網(wǎng)橋是相互連接的，但它們是通過集線器等連接設(shè)備相連的，否則為設(shè)備直連，修改指定網(wǎng)橋的指定接口類型。

（7）若在臨時鏈表A中仍不為空，則說明存在網(wǎng)絡(luò)中存在啞交換機，如果臨時鏈表A為空，則跳轉(zhuǎn)至10。

（8）在臨時鏈表A中對每個交換機根接口的指定網(wǎng)橋進行查詢，若該網(wǎng)橋不存在于臨時鏈表A中，根據(jù)結(jié)論一，將該網(wǎng)橋加入待檢測隊列B中。并重復(fù)進行4、5、6步驟。

（9）處理啞交換機連接：在鏈表C中逆序查找除啞交換機自身所在分枝以外其他分枝的交換機接口轉(zhuǎn)發(fā)狀態(tài)，若其狀態(tài)轉(zhuǎn)發(fā)無連接并且其轉(zhuǎn)發(fā)地址中包含該啞交換機的MAC地址，則對該接口與啞交換機之間的連接信息進行添加。

（10）處理冗余連接：判斷每個交換機的阻塞接口查詢它的指定網(wǎng)橋，將連接填入對應(yīng)的接口信息區(qū)。

（11）向全網(wǎng)主機發(fā)送廣播Ping包，對于處在設(shè)備直連狀態(tài)的兩臺交換機，對直連兩接口的地址轉(zhuǎn)發(fā)表進行訪問，并且根據(jù)結(jié)論四改寫其接口信息。

（12）根據(jù)結(jié)論六對主機之間的連接和路由器之間連接進行添加。

STP拓?fù)浒l(fā)現(xiàn)算法具有以下四個方面的優(yōu)點：

（1）能夠?qū)≡O(shè)備存在的情況進行處理。

在STP發(fā)現(xiàn)算法中，根據(jù)結(jié)論六利用交換機接口的指定網(wǎng)橋來發(fā)現(xiàn)啞交換機，并且利用了結(jié)論一和結(jié)論四處理接口連接集線器的情況。

（2）能夠發(fā)現(xiàn)并對冗余連接進行處理。

在生成樹算法中，它以阻塞某些接口來實現(xiàn)無環(huán)路轉(zhuǎn)發(fā)。在STP發(fā)現(xiàn)算法中，通過查找比較接口狀態(tài)，將那些處于阻塞狀態(tài)的接口取出，為其與指定網(wǎng)橋添加連接，便能發(fā)現(xiàn)冗余連接。

（3）能夠?qū)W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化進行及時反映。

在運行STP協(xié)議的網(wǎng)絡(luò)中，如果網(wǎng)絡(luò)物理拓?fù)浒l(fā)生變化，算法會立即被觸發(fā)，進而對整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進行重新的繪制，所以在STP發(fā)現(xiàn)算法得出的物理拓?fù)涫冀K是最新最完整的。但在其他算法中，對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的繪制必須通過報文之間的交流來進行，如果存在兩臺或者幾臺設(shè)備由于某種原因很久沒有發(fā)生通信，則會導(dǎo)致此設(shè)備不會被發(fā)現(xiàn)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)繪制不完整。

（4）能夠?qū)Χ鄠€子網(wǎng)的復(fù)雜環(huán)境網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進行有效的發(fā)現(xiàn)。

不同子網(wǎng)間的交換機即使直接相連，它們也是通過各自的網(wǎng)關(guān)交換信息，但它們必定都遵循生成STP協(xié)議以構(gòu)造無環(huán)路交換域，所以利用STP發(fā)現(xiàn)算法可以發(fā)現(xiàn)這些相對比較復(fù)雜連接。

3 基于ICMP協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法

在ICMP協(xié)議中有Ping命令和Traceroute命令，這兩種命令可以幫助我們獲得網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

Ping命令往往用來檢測一個節(jié)點是不是處在運行的狀態(tài)或者是檢測兩個節(jié)點之間的時延（RTT）。Ping向所要檢測的目的地址發(fā)送ICMP echo請求包，等待接收ICMP echo響應(yīng)包，按照成功的次數(shù)及一些其他數(shù)據(jù)對網(wǎng)絡(luò)的時延等一些性能進行評估。一般情況下Ping只關(guān)心網(wǎng)絡(luò)上的源節(jié)點和目的節(jié)點，而不考慮網(wǎng)絡(luò)的其他細節(jié)，同時也可以利用Ping的廣播得到整個網(wǎng)絡(luò)的主機狀態(tài)。在文獻[13]中給出了Ping的三類規(guī)則，利用這三類規(guī)則可以對某個IP地址所歸屬的網(wǎng)絡(luò)或者是IP的有效性進行判斷，具體如下：

（1）通過Ping的廣播來判定IP地址所屬子網(wǎng)。

遞減猜測子網(wǎng)掩碼的長度，對每個猜測的子網(wǎng)掩碼構(gòu)造廣播地址，進行Ping操作，如果主機對構(gòu)造的廣播地址有回應(yīng)則說明猜測的子網(wǎng)掩碼是正確。給定一個IP地址，可利用本規(guī)則猜測該地址所屬的子網(wǎng)掩碼：

for（masklen=31； i> 7 ； i--） {

假定子網(wǎng)掩碼的長度是masklen；

為IP地址和masklen構(gòu)造主機號為全0和全1的直接廣播地址；

ping這些廣播地址；

如果多于兩個主機對這兩個ping都做出了響應(yīng)，則返回masklen，否則繼續(xù)；

}

（2）通過一組地址來判定該組地址所屬子網(wǎng)。

已知地址集A中的IP地址同屬于一個子網(wǎng)，對地址集A進行異或操作，找出第一個不為0的位，則該位及其后的各位都只能是主機號，而不可能是子網(wǎng)號。從而判斷出子網(wǎng)掩碼的長度（可能比實際子網(wǎng)掩碼的位數(shù)長），而子網(wǎng)地址則可通過猜測得到的子網(wǎng)掩碼做按位與運算得出。求取子網(wǎng)掩碼的偽代碼如下：

（3）判定在某個域中的有效IP地址。

已知一個子網(wǎng)空間的地址集B，推測已知的子網(wǎng)地址空間中有效的IP地址，其算法描述如下：

for（每個ping測試成功的地址）{

把此地址的后續(xù)N個地址加入到臨時集合中；

if（地址以1，63，129或者193結(jié)尾） {

可能有其他的主機在這個空間中，把N個具有相同前綴的隨機地址加入到臨時集合中；

Traceroute命令可以發(fā)現(xiàn)源節(jié)點和目的節(jié)點之間的路由器。其原理是通過Traceroute命令向目的節(jié)點發(fā)送端口為65535的UDP報文，它們之間的路由器在轉(zhuǎn)發(fā)該數(shù)據(jù)包之間會將其TTL值減1，如果當(dāng)TTL值變?yōu)榱?，則該路由器向源節(jié)點發(fā)送TTL-Expired ICMP的消息。Traceroute命令就是通過這個特性，將發(fā)送包的TTL值不斷的增大，這樣會使源節(jié)點到目的節(jié)點間這條路經(jīng)上所有的路由器均會向源節(jié)點發(fā)送TTL-Expired ICMP包，這樣就將此路徑上的所有路由器進行發(fā)現(xiàn)。如圖3所示，對一個目標(biāo)設(shè)備發(fā)送的第一個數(shù)據(jù)包中TTL值為1，所以此報文在遇到兩個節(jié)點之間第一個路由器R1時，就會向源節(jié)點發(fā)送TTL-Expired ICMP包，這樣路由器R1就被發(fā)現(xiàn)了，R1就成了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的一部分。之后就將發(fā)送報文的TTL值不斷增加1，一直加到發(fā)送的報文被目的節(jié)點所接收，就可以得到之間所有路由器節(jié)點。endprint

通過上述方式我們可以構(gòu)造出包含節(jié)點R1，R2，R3，…，Rn和連接關(guān)系（源主機，R1），（R1，R2），（R2，R3），…，（Rn，目標(biāo)設(shè)備）拓?fù)浣Y(jié)構(gòu)來。由于基本所有的路由器都會向源節(jié)點發(fā)送TTL-Expired ICMP消息，所以一般情況下，通過Traceroute命令得出來的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是比較準(zhǔn)確的。

通過ICMP中的Ping和Traceroute命令的特性可以實現(xiàn)對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的發(fā)現(xiàn)。

算法的主要步驟如下：

（1）首先在域內(nèi)隨機選取形式為（* .1）的地址同時將它們存在臨時地址集A。

（2）然后每次從A中取出一個IP地址a通過步驟3進行判定，直到地址集A中沒有IP地址可以取，繪制網(wǎng)絡(luò)拓?fù)鋱D。

（3）首先利用Ping命令判斷該地址是否為有效地址，如果有效則將該地址存入地址集B中并且根據(jù)規(guī)則3將更多的地址加入地址集A中。而后有效地址a進一步執(zhí)行Traceroute命令，會得到與其相連接的所有路由器的信息，然后利用規(guī)則2猜測地址a所屬的子網(wǎng)地址。

算法流程如圖4所示。

4 基于SNMP協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法

在一般的基于SNMP協(xié)議的拓?fù)浒l(fā)現(xiàn)方法中，網(wǎng)絡(luò)中的每個設(shè)備都有路由表，路由表中的信息包含了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的信息，路由表包括路由目的網(wǎng)絡(luò)地址、網(wǎng)絡(luò)的子網(wǎng)掩碼、該路由的下一站IP地址、對應(yīng)的端口索引和路由協(xié)議類型等信息。由于路由表中下一跳的節(jié)點一定是具有路由功能的節(jié)點，所以就可以在設(shè)定路由器開始，依次讀取每臺路由器的路由表，這樣就可以逐個發(fā)現(xiàn)每臺具有路由功能的節(jié)點，進而得出具有路由功能節(jié)點的拓?fù)浣Y(jié)構(gòu)。再根據(jù)路由表的本地接口的索引標(biāo)識項，找到接口表中所對應(yīng)的本地接口索引，由接口表的接口類型就可以判斷其所在子網(wǎng)的類型，最終構(gòu)建出整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖。這種方法的拓?fù)浒l(fā)現(xiàn)過程和算法的優(yōu)點在于其過程簡單，運行速度快，發(fā)現(xiàn)效率高，對資源消耗比較小，因此，得到了大家的廣泛應(yīng)用。但是，該方法的不足也很明顯，主要表現(xiàn)在以下五個方面：

（1）由于只是根據(jù)IP地址來發(fā)現(xiàn)設(shè)備，這樣就無法發(fā)現(xiàn)網(wǎng)絡(luò)中沒有配置IP的網(wǎng)絡(luò)設(shè)備。

（2）由于目前一個路由器往往具有不止一個IP地址，而此基于路由表的發(fā)現(xiàn)方法算法實際上就是基于IP地址的，所以一個具有多個IP地址的路由器會導(dǎo)致一臺設(shè)備被算法當(dāng)成了多臺設(shè)備，與實際情況不符合。

（3）因為要對網(wǎng)絡(luò)中所有設(shè)備進行檢測，在網(wǎng)絡(luò)規(guī)模比較大時可能導(dǎo)致算法執(zhí)行時間較長，同時由于實際網(wǎng)絡(luò)中情況比較復(fù)雜，存在網(wǎng)絡(luò)時延等情況，可能導(dǎo)致發(fā)現(xiàn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不準(zhǔn)確。

（4）在路由表中本身存在大量的冗余信息，可能導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不準(zhǔn)確。

（5）根據(jù)該算法進行拓?fù)浒l(fā)現(xiàn)需要網(wǎng)絡(luò)中所有的設(shè)備都支持SNMP協(xié)議。

因此，該方法一般用于骨干網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的發(fā)現(xiàn)，主要對網(wǎng)絡(luò)的路由節(jié)點進行發(fā)現(xiàn)，對網(wǎng)絡(luò)的整體情況進行繪制?？梢?，無論是基于STP的拓?fù)浒l(fā)現(xiàn)算法還是本節(jié)的拓?fù)浒l(fā)現(xiàn)算法都各有優(yōu)缺點和局限性，在實際的應(yīng)用中要根據(jù)具體的情況發(fā)揮出算法的功能。

本節(jié)在現(xiàn)有基于SNMP算法的基礎(chǔ)上研究了一種基于SNMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)改進算法，經(jīng)過實際網(wǎng)絡(luò)管理系統(tǒng)的驗證，能夠有效發(fā)現(xiàn)管控網(wǎng)絡(luò)的三級拓?fù)浣Y(jié)構(gòu)，即：骨干網(wǎng)路由、二級子網(wǎng)和三級子網(wǎng)拓?fù)浣Y(jié)構(gòu)。

這種算法的基本思想是在網(wǎng)絡(luò)中路由器之間的鏈路是由其兩端路由器的端口互聯(lián)構(gòu)成的，根據(jù)TCP/IP的編址原理，鏈路兩端路由器端口的IP地址必然處于同一個子網(wǎng)中。因此，通過一個子網(wǎng)中已知的IP地址和這個IP地址的子網(wǎng)掩碼即可計算出該子網(wǎng)中所有其他的IP地址。根據(jù)這種思路，從某個節(jié)點開始，訪問其MIB庫，得到該節(jié)點所有接口的IP地址和子網(wǎng)掩碼，該節(jié)點稱為種子節(jié)點。通過計算得到與每一接口在同一個子網(wǎng)內(nèi)的其他IP地址。判斷這些IP地址是否屬于路由器信息，如果是則將此路由器信息記錄到待檢測路由設(shè)備鏈表，作為下一層發(fā)現(xiàn)的種子節(jié)點。并同時記錄兩個路由器問的鏈路信息到拓?fù)湫畔㈡湵怼Ｖ貜?fù)以上步驟直到?jīng)]有種子節(jié)點或者達到指定的發(fā)現(xiàn)層數(shù)，即可完成相應(yīng)的拓?fù)浒l(fā)現(xiàn)過程。算法流程如圖5所示。

詳細描述如下：

（1）根據(jù)網(wǎng)絡(luò)管理系統(tǒng)的IP掩碼，使用路由跟蹤的方法獲取網(wǎng)管終端所在的默認(rèn)路由器網(wǎng)關(guān)地址。訪問該路由器獲取ipAdderssTable地址表信息，將其編號加入AllRouters隊列（元素包括路由器名、接口號、接口IP、接口號和接口IP等，其中接口號與接口IP的多少依據(jù)各個不同路由器而不同）和AccessRouters隊列（待訪問路由器，結(jié)構(gòu)跟AllRouters類似）。

（2）從AccessRoutes取出一個元素設(shè)為當(dāng)前處理的路由器Rx，依次訪問Rx的路由表ipRouteTable表項，將目標(biāo)子網(wǎng)信息編號無重復(fù)地放入子網(wǎng)隊列Subnets（元素包括子網(wǎng)號，子網(wǎng)地址，掩碼等）。

（3）判斷路由器與子網(wǎng)連接關(guān)系：依次對Rx的ipRouteTable表項檢查，如果ipRouteType項不為4，表示相應(yīng)子網(wǎng)與Rx直接相連，下一跳地址ipNextHopIpAddress項為空。根據(jù)Rx的ipAddressTable信息確定Y端口與該子網(wǎng)Z相連接，將連接關(guān)系組（Rx，Y，Z）無重復(fù)地放入R-1inks-S隊列（路由器接口與子網(wǎng)相連的接配對的二元組）。

（4）判斷路由器之間的連接關(guān)系：如果ipRouteType為4，下一跳ipNextHopIpAddress地址有效，表明另一個路由器與Rx直接相連。根據(jù)ipNextHopIpAddress地址信息訪問另一個路由器的ipAddressTable，判斷AllRouters隊列中是否己經(jīng)存在該路由器信息，如不存在則把該路由器編號加入隊列AllRouters和AccessRouters中。很容易確定Rx的Y端口與另一個路由器Ru的V端口直接連接。因此把元素（Rx，Y，Ru，V）無重復(fù)地放入隊列R-links-R（路由器接口與路由器接口相連的二元組）中。endprint

（5）把隊列R-links-R進行去冗處理。因為在以上的算法實現(xiàn)中，有可能存相同的連接信息加入到隊列中。例如：R1的2端口與R4的3端口直接相連，在算法實現(xiàn)過程中，可能同時在隊列中加入了（R1，2，R4，3）和（R4，3，R1，2）的元素組，雖然它們在形式上不一樣，但他們表示同一個連接信息。

（6）把Rx的元素組從AccessRouters中刪除，如果AccessRouters不為空，轉(zhuǎn)到（2），如果為空，程序中止。

算法運行結(jié)束以后，AllRouters包含了所有活動的路由器，子網(wǎng)隊列Subnets包含了所有活動的子網(wǎng)，隊列R-links-S和隊列R-links-R的信息表示路由器與子網(wǎng)、路由器與路由器之間連接關(guān)系，最終可以準(zhǔn)確而完整地把拓?fù)浣Y(jié)構(gòu)繪制出來。

5 結(jié)語

該文分析了網(wǎng)絡(luò)拓?fù)浼夹g(shù)的重要性，介紹了現(xiàn)有各類網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，并重點針對其不足進行了分析，根據(jù)現(xiàn)有網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的不足，根據(jù)實際，選取STP、SNMP和ICMP三個常用協(xié)議做為基礎(chǔ)，提出了基于這三種常見協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，同時提出了一種基于SNMP協(xié)議的拓?fù)浒l(fā)現(xiàn)改進算法，更好的解決了網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)比較難以有效解決的問題。

參考文獻

[1] K.C.Claffy D.McRobb.Measurement and Visualization of Internet Connectivity and Performance[EB/OL]. http：//www.caida.org/Tools/Skitter， 2001.

[2] 鄭海，張國清.物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的研究[J].計算機研究與發(fā)展，2002， 39（3）：264-268.

[3] 張國強，張國清，李仰耀.物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的研究和系統(tǒng)實現(xiàn)[J].小型微型計算機系統(tǒng)，2006，27（1）：12-16.

[4] 邱林，張建忠，吳功宜.基于端口流量的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法研究[J].計算機工程與應(yīng)用，2002，38（22）：171-172.

[5] 陳艷秋，宋銀瀕，刁成嘉.利用端口流量分析解決物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)問題[J].計算機工程與應(yīng)用，2007，43（5）：150-152.

[6] Gobjuka.H， Breitbart.Y.Ethernet Topology Discovery for Networks with Incomplete Information[J]. IEEE INFOCOM，2007（8）：631-638.

[7] Uzair.U，Ahmad.HF，AIi.A，Suguri.H.An Efficient Algorithm for Ethernet Topology Discovery inLarge Multi-subnet Networks[J]. IEEE INFOCOM， 2007（4）：1-7.

[8] Farkas J，de Oliveira V.G， Salvador M.R， dos Santos G.C. Automatic Discovery of Physical Topology in Ethernet Networks [J].IEEE INFOCOM，2008，3：848-854.

[9] 曲朝陽，胡緒超.基于SNMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)與拓?fù)渖蓸涞睦L制[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2007（3）：23-27.

[10] J Case，M Fedor，M Schoffstall.Simple Network Management Protocal [S].RFC1157，1999.

[11] 石玫.網(wǎng)絡(luò)拓?fù)渥灾靼l(fā)現(xiàn)[D].中國人民解放軍信息工程大學(xué)，2007.

[12] 張占國，劉淑芬，包鐵，等.基于STP協(xié)議的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法[J].計算機工程，2008，34（6）：98-100.

[13] 王婕，歐陽松.網(wǎng)絡(luò)拓?fù)渥詣影l(fā)現(xiàn)算法的研究[J].計算機測量與控制，2005， 13（9）：978-980.endprint

（5）把隊列R-links-R進行去冗處理。因為在以上的算法實現(xiàn)中，有可能存相同的連接信息加入到隊列中。例如：R1的2端口與R4的3端口直接相連，在算法實現(xiàn)過程中，可能同時在隊列中加入了（R1，2，R4，3）和（R4，3，R1，2）的元素組，雖然它們在形式上不一樣，但他們表示同一個連接信息。

（6）把Rx的元素組從AccessRouters中刪除，如果AccessRouters不為空，轉(zhuǎn)到（2），如果為空，程序中止。

算法運行結(jié)束以后，AllRouters包含了所有活動的路由器，子網(wǎng)隊列Subnets包含了所有活動的子網(wǎng)，隊列R-links-S和隊列R-links-R的信息表示路由器與子網(wǎng)、路由器與路由器之間連接關(guān)系，最終可以準(zhǔn)確而完整地把拓?fù)浣Y(jié)構(gòu)繪制出來。

5 結(jié)語

該文分析了網(wǎng)絡(luò)拓?fù)浼夹g(shù)的重要性，介紹了現(xiàn)有各類網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，并重點針對其不足進行了分析，根據(jù)現(xiàn)有網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的不足，根據(jù)實際，選取STP、SNMP和ICMP三個常用協(xié)議做為基礎(chǔ)，提出了基于這三種常見協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，同時提出了一種基于SNMP協(xié)議的拓?fù)浒l(fā)現(xiàn)改進算法，更好的解決了網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)比較難以有效解決的問題。

參考文獻

[1] K.C.Claffy D.McRobb.Measurement and Visualization of Internet Connectivity and Performance[EB/OL]. http：//www.caida.org/Tools/Skitter， 2001.

[2] 鄭海，張國清.物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的研究[J].計算機研究與發(fā)展，2002， 39（3）：264-268.

[3] 張國強，張國清，李仰耀.物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的研究和系統(tǒng)實現(xiàn)[J].小型微型計算機系統(tǒng)，2006，27（1）：12-16.

[4] 邱林，張建忠，吳功宜.基于端口流量的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法研究[J].計算機工程與應(yīng)用，2002，38（22）：171-172.

[5] 陳艷秋，宋銀瀕，刁成嘉.利用端口流量分析解決物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)問題[J].計算機工程與應(yīng)用，2007，43（5）：150-152.

[6] Gobjuka.H， Breitbart.Y.Ethernet Topology Discovery for Networks with Incomplete Information[J]. IEEE INFOCOM，2007（8）：631-638.

[7] Uzair.U，Ahmad.HF，AIi.A，Suguri.H.An Efficient Algorithm for Ethernet Topology Discovery inLarge Multi-subnet Networks[J]. IEEE INFOCOM， 2007（4）：1-7.

[8] Farkas J，de Oliveira V.G， Salvador M.R， dos Santos G.C. Automatic Discovery of Physical Topology in Ethernet Networks [J].IEEE INFOCOM，2008，3：848-854.

[9] 曲朝陽，胡緒超.基于SNMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)與拓?fù)渖蓸涞睦L制[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2007（3）：23-27.

[10] J Case，M Fedor，M Schoffstall.Simple Network Management Protocal [S].RFC1157，1999.

[11] 石玫.網(wǎng)絡(luò)拓?fù)渥灾靼l(fā)現(xiàn)[D].中國人民解放軍信息工程大學(xué)，2007.

[12] 張占國，劉淑芬，包鐵，等.基于STP協(xié)議的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法[J].計算機工程，2008，34（6）：98-100.

[13] 王婕，歐陽松.網(wǎng)絡(luò)拓?fù)渥詣影l(fā)現(xiàn)算法的研究[J].計算機測量與控制，2005， 13（9）：978-980.endprint

（5）把隊列R-links-R進行去冗處理。因為在以上的算法實現(xiàn)中，有可能存相同的連接信息加入到隊列中。例如：R1的2端口與R4的3端口直接相連，在算法實現(xiàn)過程中，可能同時在隊列中加入了（R1，2，R4，3）和（R4，3，R1，2）的元素組，雖然它們在形式上不一樣，但他們表示同一個連接信息。

（6）把Rx的元素組從AccessRouters中刪除，如果AccessRouters不為空，轉(zhuǎn)到（2），如果為空，程序中止。

算法運行結(jié)束以后，AllRouters包含了所有活動的路由器，子網(wǎng)隊列Subnets包含了所有活動的子網(wǎng)，隊列R-links-S和隊列R-links-R的信息表示路由器與子網(wǎng)、路由器與路由器之間連接關(guān)系，最終可以準(zhǔn)確而完整地把拓?fù)浣Y(jié)構(gòu)繪制出來。

5 結(jié)語

該文分析了網(wǎng)絡(luò)拓?fù)浼夹g(shù)的重要性，介紹了現(xiàn)有各類網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，并重點針對其不足進行了分析，根據(jù)現(xiàn)有網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的不足，根據(jù)實際，選取STP、SNMP和ICMP三個常用協(xié)議做為基礎(chǔ)，提出了基于這三種常見協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法，同時提出了一種基于SNMP協(xié)議的拓?fù)浒l(fā)現(xiàn)改進算法，更好的解決了網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)比較難以有效解決的問題。

參考文獻

[1] K.C.Claffy D.McRobb.Measurement and Visualization of Internet Connectivity and Performance[EB/OL]. http：//www.caida.org/Tools/Skitter， 2001.

[2] 鄭海，張國清.物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的研究[J].計算機研究與發(fā)展，2002， 39（3）：264-268.

[3] 張國強，張國清，李仰耀.物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的研究和系統(tǒng)實現(xiàn)[J].小型微型計算機系統(tǒng)，2006，27（1）：12-16.

[4] 邱林，張建忠，吳功宜.基于端口流量的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法研究[J].計算機工程與應(yīng)用，2002，38（22）：171-172.

[5] 陳艷秋，宋銀瀕，刁成嘉.利用端口流量分析解決物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)問題[J].計算機工程與應(yīng)用，2007，43（5）：150-152.

[6] Gobjuka.H， Breitbart.Y.Ethernet Topology Discovery for Networks with Incomplete Information[J]. IEEE INFOCOM，2007（8）：631-638.

[7] Uzair.U，Ahmad.HF，AIi.A，Suguri.H.An Efficient Algorithm for Ethernet Topology Discovery inLarge Multi-subnet Networks[J]. IEEE INFOCOM， 2007（4）：1-7.

[8] Farkas J，de Oliveira V.G， Salvador M.R， dos Santos G.C. Automatic Discovery of Physical Topology in Ethernet Networks [J].IEEE INFOCOM，2008，3：848-854.

[9] 曲朝陽，胡緒超.基于SNMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)與拓?fù)渖蓸涞睦L制[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2007（3）：23-27.

[10] J Case，M Fedor，M Schoffstall.Simple Network Management Protocal [S].RFC1157，1999.

[11] 石玫.網(wǎng)絡(luò)拓?fù)渥灾靼l(fā)現(xiàn)[D].中國人民解放軍信息工程大學(xué)，2007.

[12] 張占國，劉淑芬，包鐵，等.基于STP協(xié)議的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法[J].計算機工程，2008，34（6）：98-100.

[13] 王婕，歐陽松.網(wǎng)絡(luò)拓?fù)渥詣影l(fā)現(xiàn)算法的研究[J].計算機測量與控制，2005， 13（9）：978-980.endprint