網絡拓撲發現算法的研究

宋翠

摘 要：本文主要針對目前比較常用的網絡拓撲發現算法，進行了較深入的理論分析和研究。分析了拓撲發現在網絡管理中的重要性，并總結出各算法的優缺點，并提出可以根據應用的實際環境，將多種拓撲發現算法融合，揚長避短，從而達到更佳的發現效果。

關鍵詞：網絡管理；SNMP；拓撲發現

一、基于SNMP協議的拓撲發現算法

該方法是通過標準的SNMP協議來實現的，由一個指定的或默認的路由器開始，通過讀取該路由器的IP路由表，獲取到下一跳路由器的IP地址信息。依據此法，采用廣度優先遍歷或深度優先遍歷對整個網絡內的路由器進行遍歷，可依次向下發現網絡中的路由器。將目的IP地址和子網掩碼進行“與”運算，從而得到網絡地址，再通過路由類型的判斷，來確定所連接的子網類型，從而確定網絡中各設備的互連情況，構建整個網絡的拓撲圖。因此，該算法簡單易行，發現網絡設備的效率高，網絡與系統開銷小。

其不足是：要求待發現的網絡內的設備必須支持SNMP協議，否則無法發現。同時，出于對網絡安全方面的考慮，在訪問管理信息庫時需要密碼，即共同體的值，若是不知道該值，就無法訪問網絡設備，也就無法獲得網絡連接的信息。

二、基于ICMP協議的拓撲發現算法

首先給定一個IP地址范圍，對該范圍內的所有IP發起ping命令，將ping通的活動IP地址記錄到IP地址表中。然后從該表中提取一個IP地址，對該地址進行TraceRoute操作，將途經的路由器記錄到路由器隊列中。重復上述操作，直至指定范圍內的所有IP地址都操作完畢為止。接下來再對IP地址表中的每個IP地址發送子網掩碼請求，從應答的報文中獲取該IP地址所對應的子網掩碼，確定其網絡地址，并加入子網隊列。將所得結果進行分析對照，合并歸屬于同一路由器的不同地址，從而得到網絡的拓撲結構。此算法理論簡單，操作方便，適用性較強，不僅能發現拓撲，又能檢測網絡設備和主機的存活性。

它的不足是：ping命令只能測試源與目的地之間的連通性，而途中經歷了哪些設備卻無法確定。使用TraceRoute命令，盡管能探測出途中經過的路由器，但此命令卻不能直觀地反映網絡設備間的連接關系。由于給定的IP地址是個范圍，不夠準確，里面可能含有不存在的地址，在對每個IP都進行ping和TraceRoute操作時，就增加了系統開銷，浪費了帶寬，因此該方法效率不高。此外，如果防火墻處于開啟狀態，ICMP包則是無法通過，也就無法準確發現網絡的拓撲結構。

三、基于RIP協議的拓撲發現算法

RIP協議是小型網絡中常用的距離矢量路由協議，以跳數作為路徑的度量標準，最大跳數為15跳，16跳則認為網絡不可達。RIP協議分為RIPv1和RIPv2，其中RIPv2支持VLSM及CIDR技術。在發送路由更新時，將整張路由表發送給直連鄰居。接收到鄰居的路由更新時，同自己路的由表進行對照，將表中不存在的路由添加進來，對于表中已存在的路由比較一下哪個更優，則采用哪個。啟用RIPv2的路由器在網絡拓撲沒發生變化時，默認每隔30秒鐘就發送一次更新，即周期性更新；當拓撲發生變化時，則立即發送更新即觸發更新。若路由條目在180秒內無更新收到，則該路由被標記為無效，若在240秒內還沒收到更新，則從將該路由條目從路由表中刪除。因此可以通過RIP協議與路由器交互，獲取相應路由表信息，分析并從中提取出網絡拓撲結構。

該算法的優點是速度快、性能高且發現結構較準確。但對此協議數據單元的解析難度較大，同時要求被檢測網絡內的路由器都得使用RIP協議。此外，由于RIP最大跳數為15跳，這就決定了它搜索的范圍較小，因此這種算法的實用性也變得越來越小。

四、基于OSPF協議的拓撲發現算法

OSPF開放最短路徑優先協議，是最為典型的鏈路狀態路由協議，其通用性高，功能強。OSPF作為一種內部網關協議，用于在同一AS自治域系統中的路由器之間交換路由信息。其原理是，運行OSPF協議的每臺路由器都知道自己直連的網絡，向網絡中直連鄰居發送Hello數據包，確認鄰居是否存在。然后將所創建鏈路狀態數據包LSP泛洪到其所有的鄰居，鄰居則將收到的LSP存放到數據庫中。每臺路由器都依據自己數據庫中的信息去構建一個完整的最短路徑優先樹SPF樹，并根據SPF算法計算通向所有目的網絡的最佳路徑，將其添加到路由表中。當網絡結構發生變化時，立即發送鏈路狀態通告LSA，運行路由算法，重新計算路由。因此，網絡內的每臺路由器都擁有一致的網絡拓撲結構，所不同的是每個路由器的拓撲結構都是以自己為根節點的樹結構。

基于OSPF協議的發現算法就是獲取網絡內的一臺路由器的LSA數據庫，并實時獲取LSA同步網絡拓撲的信息，其優點是效率高、速度快、準確。由于OSPF協議較復雜，實現難度較大，并且要求網絡內的路由器都得啟用OSPF協議。此外，它采用的SPF算法非常復雜，對硬件設備的要求也較高，計算路由時開銷大。

綜上所述，當前網絡拓撲發現的算法有很多，各有優缺點及適用范圍。在實際應用中，可基于上述拓撲發現算法，并結合實際研究、應用的環境，將兩種或多種拓撲發現算法融為一體，揚長避短，從而演化出一種更為優化、更為適用的網拓撲發現算法。