一種基于圖的網絡拓撲概率故障定位方法

摘要：準確的網絡拓撲故障定位能夠提高網絡管理的效率。在研究IP網絡拓撲發現的基礎上，提出了一種基于無向圖的網絡拓撲概率故障定位方法，能夠有效地排除網絡故障、提高網絡性能并增強網絡的可靠性。

關鍵詞：拓撲發現； 無向圖； 拓撲故障定位

中圖法分類號：TP393文獻標識碼：A

文章編號：1001－3695(2007)01－0133－03

作為網絡管理的重要組成部分，拓撲管理可以反映網絡設備的配置、布局和節點狀態。網絡主機或數據鏈路的失效會導致網絡拓撲故障，但由于網絡龐大，故障源的具體位置很難確定，因此準確地進行拓撲故障定位是拓撲管理的關鍵。通過拓撲故障定位，能夠及時發現失效的主機或鏈路，提高網絡性能、增強網絡可靠性。

實現拓撲故障定位的基礎是拓撲發現，本文在研究IP網絡拓撲發現的基礎上，使用基于無向圖的方法對網絡拓撲故障定位進行了研究。

1拓撲發現方法研究

實現IP網絡的拓撲管理，也就是對IP網絡進行拓撲發現與監控。IP網絡拓撲發現有以下常用的方法[1]：①利用SNMP獲取MIB中的拓撲信息；②利用ICMP Ping/Ping Broadcast命令判斷目的設備的存在性；③利用ICMP Traceroute命令獲得路由器間的連接關系；④利用DNS命令發現域內主機和路由器的相關拓撲信息；⑤利用ARP獲取同一以太網網段內所有活動主機的拓撲信息；⑥利用BGP，OSPF，RIP等路由協議獲取路由信息，從而快速獲得路由器間的連接關系以及子網拓撲信息。

使用ICMP Echo/Reply能夠迅速發現網絡中的IP節點，簡單有效且具有通用性。SNMP功能強大、發現速度快，目前主要的網絡設備都支持SNMP。SNMP的標準MIB II(RFC 1213)中包含了對管理網絡非常有用的信息，具有通用性。因此本文采用ICMP與SNMP相結合的方法來實現IP網絡拓撲發現，具有快速、通用的優點，能滿足網管系統的實時性要求。其具體方法是：使用SNMP獲取MIB中與拓撲發現相關的關鍵信息，據此構造出網絡主拓撲，再使用ICMP發現子網中的終端設備，實現子拓撲的構建，從而完成整個IP網絡的拓撲發現。

在標準MIB II(RFC 1213)中，與拓撲發現相關的關鍵信息主要包括sys組、if組和ip組變量[2]。本文主要用到if組和ip組。根據ip組中的iPForwarding變量可判斷該設備是否為路由器；根據if組的設備網絡接口表可判斷此接口所連接的子網類型；根據ip組的IP地址表可判斷與路由器相連的子網地址；根據ip組的IP路由表可找到與該路由器非直接連接的下一跳路由器IP地址。

拓撲發現算法的流程如下：

(1)從被管IP地址段中取出一個IP地址，使用SNMP獲取其iPForwarding值，如果為1，則設備具有前向轉發IP數據包的功能，為路由器。如果找到了一個路由器，轉步驟(2)；如果不存在路由器，則算法結束。

(2)使用SNMP查詢該路由器IP地址表(iPAddrTable)，取得表中所有IP地址(ipAdEntAddr)和相應的子網掩碼(iPAdEntNetMask)。將ipAdEntAddr和相應的iPAdEntNetMask進行與操作，確定該路由器所連接的所有子網地址，如果子網都不在管理范圍內，算法結束；否則，從接口表(ifTable)獲得變量ifType，確定子網的網絡類型。

(3)獲得子網信息后，查詢該路由器路由表(ipRouteTable)，獲得非直接連接路由器的下一跳IP地址(ipRoute￣NextHop)，即路由類型(ipRouteType)的值為4(indirect)。如果無這樣的路由器，算法結束；否則，轉步驟(2)。針對上述算法所確定的所有子網，使用ICMP發現網內的所有活動IP節點。在此基礎上對該拓撲進行周期監控，發現網絡拓撲變化和不可達情況，但不能確定故障的具體位置。因此拓撲故障定位是下一步需要研究的問題。

2拓撲故障定位方法研究

通信網絡中故障定位的技術很多，包括專家系統、依賴圖、碼書、信任網絡、因果關系圖或根據實際情況建模[4，5]。根據定位方式，故障定位技術又可以分為被動方式[6]和主動探測方式[7，8]。本文使用圖論模型進行網絡建模，并在此基礎上進行了故障定位研究。

在網絡拓撲穩定的情況下，當某臺主機或者路由器(以下簡稱為主機)出現了不可達的情況(假設網絡中路由算法在網絡連通情況下都能夠發現正確路由)，可能是主機出現了故障或與該主機相連的所有鏈路出現了故障。區分這兩種情況，準確地進行拓撲故障定位是一個重要難題，為解決該問題，本文使用了基于無向圖的概率方法進行網絡拓撲故障的定位。

2．1網絡與無向圖

在網絡研究中可以將網絡抽象為無向圖，簡稱圖[3]。一個圖G定義為一個有序對(V，E)，記為G=(V，E)。其中：①V是一個非空集合，稱為頂點集或者點集，其元素稱為頂點或者點，用n表示頂點數；②E是由V中的點組成的無序點對構成的可重集合（同一點對在E中可出現多次），稱為邊集，其元素稱為邊，用m表示邊數。邊記為uv，也可記為e，即e=uv，并稱u(或v)與e關聯；連接兩個相同頂點邊的條數稱為邊的重數，重數大于1的邊稱為重邊；頂點重合為一點的邊稱為環；沒有環也無重邊的圖稱為簡單圖。

假設網絡中主機、鏈路的故障發生相互獨立，并且同一個設備的故障發生情況也是獨立的，主機、鏈路的故障時間間隔概率分布是已知的。圖1中，以Fvi表示網絡中頂點vi的故障時間間隔分布函數，以Fej表示網絡中邊ej的故障時間間隔分布函數。在下面的討論中，t表示當前時刻，tvi與tej表示vi與ej上次發生故障的時刻。

2．2基于無向圖的概率故障定位

下面對網絡中的各種不可達情況進行分析，并在此基礎上進行概率故障定位。

2．3故障定位的實例分析

下面以圖1為例，說明故障模型的化簡方法。

3結束語

本文在IP網絡拓撲發現的基礎上研究了一種基于無向圖的網絡拓撲概率故障定位方法，該拓撲故障定位方法已在實際的IP城域網中得到使用，能夠有效地排除網絡故障，提高了網絡性能。

參考文獻：

［1］Lin Hwachun， Lai Shouchuan， Chen Pingwen. Automatic Topology Discovery of IP Networks[J]. IEICE Trans. Inf.Syst， 2000.

［2］RFC 1213， Management Information Base for Network Management of TCP/IPbased Internets： MIBII［S］.

［3］張先迪，李正良. 圖論及其應用[M]. 北京：高等教育出版社，2005.

［4］Malgorzata Steinder， Adarshpal S Sethi. A Survey of Fault Localization Techniques in Computer Networks［J］. Science of Computer Programming，20-04，53（2）：165194.

［5］Malgorzata Steinder， Adarshpal S Sethi. Probabilistic Fault Localization in Communication Systems Using Belief Networks［J］. IEEE/ACM Transactions on Networking，20-04，12(5)：809822.

［6］S Kliger，S Yemini，Y Yemini，et al. A Coding Approach to Event Correlation[C]. Proceedings of the 4th International Symposium on Intelligent Network Management，1995.

［7］I Rish，M Brodie，N Odintsova，et al.Realtime Problem Determination in Distributed Systems Using Active Probing［C］. IEEE/IFIP (NOMS)， 20-04.

［8］M Brodie，I Rish，S Ma.Optimizing Probe Selection for Fault Localization[C]. IEEE/IFIP (DSOM)， 2001.

作者簡介：

唐勇，男，云南云縣人，博士研究生，主要研究方向為無線網絡、網絡計算與網絡管理；張欣，女，碩士研究生，主要研究方向為無線網絡、多媒體通信與寬帶通信網；周明天，男，教授，博導，主要研究方向為網絡計算、分布式計算與信息安全。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文