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

摘 要：隨著網絡的不斷發(fā)展，其拓撲結構變得越來越復雜，其獲取也變得越來越困難，該文介紹分析了網絡拓撲技術的發(fā)展現(xiàn)狀，分析了現(xiàn)有網絡拓撲技術的不足，并且提出了基于STP、SNMP和ICMP三種常見協(xié)議的網絡拓撲發(fā)現(xiàn)算法。

關鍵詞：網絡拓撲發(fā)現(xiàn) STP SNMP ICMP

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

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

1 網絡拓撲發(fā)現(xiàn)算法研究

在網絡拓撲發(fā)現(xiàn)技術方面，美國康奈爾大學的CNRG網絡研究組、CAIDA組織的Skitter [1]和貝爾實驗室在這方面都有了深入的研究，他們設計的算法及其技術都已經具有較好的應用，并且已經進行了商用。

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

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

2 基于STP協(xié)議的網絡拓撲發(fā)現(xiàn)算法

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

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

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

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

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

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

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

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

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

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

詳細描述如下：

（1）對網絡中所有的設備進行訪問，對交換機進行識別并且存入臨時鏈表A中。

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

（3）對網絡拓撲生成樹進行廣度優(yōu)先遍歷。根據STP協(xié)議可以得到交換區(qū)域的根網橋，而后將根網橋加入到FIFO（先進先出隊列）的等待進一步檢測的隊列B中。

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

（5）重復4，直到隊列B為空。

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

（7）若在臨時鏈表A中仍不為空，則說明存在網絡中存在啞交換機，如果臨時鏈表A為空，則跳轉至10。

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

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

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

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

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

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

（1）能夠對啞設備存在的情況進行處理。

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

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

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

（3）能夠對網絡拓撲結構的變化進行及時反映。

在運行STP協(xié)議的網絡中，如果網絡物理拓撲發(fā)生變化，算法會立即被觸發(fā)，進而對整個網絡的拓撲結構進行重新的繪制，所以在STP發(fā)現(xiàn)算法得出的物理拓撲始終是最新最完整的。但在其他算法中，對網絡拓撲結構的繪制必須通過報文之間的交流來進行，如果存在兩臺或者幾臺設備由于某種原因很久沒有發(fā)生通信，則會導致此設備不會被發(fā)現(xiàn)，網絡拓撲結構繪制不完整。

（4）能夠對多個子網的復雜環(huán)境網絡拓撲結構進行有效的發(fā)現(xiàn)。

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

3 基于ICMP協(xié)議的網絡拓撲發(fā)現(xiàn)算法

在ICMP協(xié)議中有Ping命令和Traceroute命令，這兩種命令可以幫助我們獲得網絡的拓撲結構。

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

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

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

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

假定子網掩碼的長度是masklen；

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

ping這些廣播地址；

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

}

（2）通過一組地址來判定該組地址所屬子網。

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

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

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

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

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

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

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

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

通過上述方式我們可以構造出包含節(jié)點R1，R2，R3，…，Rn和連接關系（源主機，R1），（R1，R2），（R2，R3），…，（Rn，目標設備）拓撲結構來。由于基本所有的路由器都會向源節(jié)點發(fā)送TTL-Expired ICMP消息，所以一般情況下，通過Traceroute命令得出來的網絡拓撲結構是比較準確的。

通過ICMP中的Ping和Traceroute命令的特性可以實現(xiàn)對網絡拓撲結構的發(fā)現(xiàn)。

算法的主要步驟如下：

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

（2）然后每次從A中取出一個IP地址a通過步驟3進行判定，直到地址集A中沒有IP地址可以取，繪制網絡拓撲圖。

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

算法流程如圖4所示。

4 基于SNMP協(xié)議的網絡拓撲發(fā)現(xiàn)算法

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

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

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

（3）因為要對網絡中所有設備進行檢測，在網絡規(guī)模比較大時可能導致算法執(zhí)行時間較長，同時由于實際網絡中情況比較復雜，存在網絡時延等情況，可能導致發(fā)現(xiàn)的網絡拓撲結構不準確。

（4）在路由表中本身存在大量的冗余信息，可能導致網絡拓撲結構的不準確。

（5）根據該算法進行拓撲發(fā)現(xiàn)需要網絡中所有的設備都支持SNMP協(xié)議。

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

本節(jié)在現(xiàn)有基于SNMP算法的基礎上研究了一種基于SNMP的網絡拓撲發(fā)現(xiàn)改進算法，經過實際網絡管理系統(tǒng)的驗證，能夠有效發(fā)現(xiàn)管控網絡的三級拓撲結構，即：骨干網路由、二級子網和三級子網拓撲結構。

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

詳細描述如下：

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

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

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

（4）判斷路由器之間的連接關系：如果ipRouteType為4，下一跳ipNextHopIpAddress地址有效，表明另一個路由器與Rx直接相連。根據ipNextHopIpAddress地址信息訪問另一個路由器的ipAddressTable，判斷AllRouters隊列中是否己經存在該路由器信息，如不存在則把該路由器編號加入隊列AllRouters和AccessRouters中。很容易確定Rx的Y端口與另一個路由器Ru的V端口直接連接。因此把元素（Rx，Y，Ru，V）無重復地放入隊列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不為空，轉到（2），如果為空，程序中止。

算法運行結束以后，AllRouters包含了所有活動的路由器，子網隊列Subnets包含了所有活動的子網，隊列R-links-S和隊列R-links-R的信息表示路由器與子網、路由器與路由器之間連接關系，最終可以準確而完整地把拓撲結構繪制出來。

5 結語

該文分析了網絡拓撲技術的重要性，介紹了現(xiàn)有各類網絡拓撲發(fā)現(xiàn)算法，并重點針對其不足進行了分析，根據現(xiàn)有網絡拓撲發(fā)現(xiàn)算法的不足，根據實際，選取STP、SNMP和ICMP三個常用協(xié)議做為基礎，提出了基于這三種常見協(xié)議的網絡拓撲發(fā)現(xiàn)算法，同時提出了一種基于SNMP協(xié)議的拓撲發(fā)現(xiàn)改進算法，更好的解決了網絡拓撲發(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] 鄭海，張國清.物理網絡拓撲發(fā)現(xiàn)算法的研究[J].計算機研究與發(fā)展，2002， 39（3）：264-268.

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

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

[5] 陳艷秋，宋銀瀕，刁成嘉.利用端口流量分析解決物理網絡拓撲發(fā)現(xiàn)問題[J].計算機工程與應用，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的網絡拓撲發(fā)現(xiàn)與拓撲生成樹的繪制[J].網絡安全技術與應用，2007（3）：23-27.

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

[11] 石玫.網絡拓撲自主發(fā)現(xiàn)[D].中國人民解放軍信息工程大學，2007.

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

[13] 王婕，歐陽松.網絡拓撲自動發(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不為空，轉到（2），如果為空，程序中止。

算法運行結束以后，AllRouters包含了所有活動的路由器，子網隊列Subnets包含了所有活動的子網，隊列R-links-S和隊列R-links-R的信息表示路由器與子網、路由器與路由器之間連接關系，最終可以準確而完整地把拓撲結構繪制出來。

5 結語

該文分析了網絡拓撲技術的重要性，介紹了現(xiàn)有各類網絡拓撲發(fā)現(xiàn)算法，并重點針對其不足進行了分析，根據現(xiàn)有網絡拓撲發(fā)現(xiàn)算法的不足，根據實際，選取STP、SNMP和ICMP三個常用協(xié)議做為基礎，提出了基于這三種常見協(xié)議的網絡拓撲發(fā)現(xiàn)算法，同時提出了一種基于SNMP協(xié)議的拓撲發(fā)現(xiàn)改進算法，更好的解決了網絡拓撲發(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] 鄭海，張國清.物理網絡拓撲發(fā)現(xiàn)算法的研究[J].計算機研究與發(fā)展，2002， 39（3）：264-268.

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

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

[5] 陳艷秋，宋銀瀕，刁成嘉.利用端口流量分析解決物理網絡拓撲發(fā)現(xiàn)問題[J].計算機工程與應用，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的網絡拓撲發(fā)現(xiàn)與拓撲生成樹的繪制[J].網絡安全技術與應用，2007（3）：23-27.

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

[11] 石玫.網絡拓撲自主發(fā)現(xiàn)[D].中國人民解放軍信息工程大學，2007.

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

[13] 王婕，歐陽松.網絡拓撲自動發(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不為空，轉到（2），如果為空，程序中止。

算法運行結束以后，AllRouters包含了所有活動的路由器，子網隊列Subnets包含了所有活動的子網，隊列R-links-S和隊列R-links-R的信息表示路由器與子網、路由器與路由器之間連接關系，最終可以準確而完整地把拓撲結構繪制出來。

5 結語

該文分析了網絡拓撲技術的重要性，介紹了現(xiàn)有各類網絡拓撲發(fā)現(xiàn)算法，并重點針對其不足進行了分析，根據現(xiàn)有網絡拓撲發(fā)現(xiàn)算法的不足，根據實際，選取STP、SNMP和ICMP三個常用協(xié)議做為基礎，提出了基于這三種常見協(xié)議的網絡拓撲發(fā)現(xiàn)算法，同時提出了一種基于SNMP協(xié)議的拓撲發(fā)現(xiàn)改進算法，更好的解決了網絡拓撲發(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] 鄭海，張國清.物理網絡拓撲發(fā)現(xiàn)算法的研究[J].計算機研究與發(fā)展，2002， 39（3）：264-268.

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

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

[5] 陳艷秋，宋銀瀕，刁成嘉.利用端口流量分析解決物理網絡拓撲發(fā)現(xiàn)問題[J].計算機工程與應用，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的網絡拓撲發(fā)現(xiàn)與拓撲生成樹的繪制[J].網絡安全技術與應用，2007（3）：23-27.

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

[11] 石玫.網絡拓撲自主發(fā)現(xiàn)[D].中國人民解放軍信息工程大學，2007.

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

[13] 王婕，歐陽松.網絡拓撲自動發(fā)現(xiàn)算法的研究[J].計算機測量與控制，2005， 13（9）：978-980.endprint