多層信息網絡故障定位綜述

齊小剛，牛紅曼，劉興成，王曉琳，劉立芳

（1. 西安電子科技大學 數學與統計學院，陜西 西安 710126; 2. 西安電子科技大學 計算機學院，陜西 西安710071）

近年來，通信網絡的規模和復雜性呈現急劇增長勢頭，這給網絡管理系統(NMS)運行帶來了嚴重挑戰，其核心問題是故障管理。故障在大規模通信網絡中是不可避免的，因此實時地檢測和定位故障對于網絡的可靠運行至關重要，而故障管理系統的功能就是檢測、定位網絡中的故障以及啟動故障恢復機制來防止網絡性能的退化[1-2]。

故障管理過程包括2個部分：故障診斷和故障恢復。故障診斷分為3個步驟：故障探測、故障定位以及故障測試。故障探測是通過觀測網絡癥狀來確定網絡部件是否發生故障的過程。故障定位是使用一組觀測到的癥狀來推斷網絡中故障出現的精確位置。故障測試是通過檢查推斷出的部件來驗證該部件是否發生故障的過程。故障診斷是故障管理的重要組成部分。故障診斷的目標是及時精確地定位網絡故障，故障恢復是故障部件被識別后恢復正常的過程。在故障診斷的3個步驟中，由于故障定位的復雜性，故障定位是最具挑戰性的。

有別于傳統觀念中需要大量人工干預，逐一排除故障的方法，目前較多文獻研究的目的是以極少的人工干預以及網絡負載實現快速精確的故障定位，主要定位節點故障和鏈路故障。當前該領域面臨的挑戰如下：

1)精確的網絡模型

網絡的類型以及所建立的網絡模型決定了模型中使用的信息可能是靜態或動態的，而動態信息的存在使得該問題更具有挑戰性，因為當網絡運行時更多的信息將被納入模型之中。此外，片面、不完全、不準確的信息可能會延誤診斷過程或影響診斷的準確性。

2)計算復雜性

概率推理固有的高時空復雜度，使面向大型、復雜通信網絡的故障定位計算變得更為棘手，而且這些計算需要反復執行，以便持續監測網絡。

3)故障定位技術

分布式的技術有助于減少故障檢測的時間和解決集中式管理節點的瓶頸，然而這會增加網絡的控制開銷。此外，改變網絡管理系統的監控目標可能需要在節點上完成一定數量的手工配置，而這種配置過程進一步使得分布式的定位方案變得更為復雜。

4)新型網絡中的故障定位

軟件定義網絡(software defined network，SDN)是一種新型的網絡體系結構，通過將網絡控制與網絡轉發解耦合構建開放可編程的網絡體系結構。SDN控制器配置問題可以映射為在傳統的網絡中放置一個集中式網絡管理系統NMS的問題[3]。雖然集中控制可以幫助提供更好的診斷和監測能力，然而SDN環境也給網絡管理系統帶來了一些新的故障類型。

5)高動態環境下的網絡管理

由SDN和網絡功能虛擬化 (network function virtualization，NFV)部件構成的高動態環境基礎設施的頻繁變化給網絡管理系統帶來了新的挑戰。其中一些挑戰與以下因素有關：①SDN配置更改的規模和頻繁程度[4]；②業務和用戶需求依賴的NFV部件動態添加和刪除[5]；③所跟蹤的資源波動情況；④所監控資源利用率等。另一個挑戰性的問題是，跟蹤所有頻繁變化的網絡服務，并在此基礎上進行管理決策。

6)網絡環境的復雜性

隨著新的網絡環境部署，在很長一段時間內，已有的或遺存的網絡環境仍然會與新技術共存。在過渡時期內，網絡管理方案應該能夠管理網絡的復雜性。此外，基于網絡的服務通常會穿越已有的與新的網絡中物理的和虛擬的網絡部件。因此，信息網絡的共存需要從端到端的角度實現網管系統的無縫管理。

本文對多層信息網絡故障定位過程中采用的探測信息獲取策略，和基于資源映射關系的網絡故障定位模型進行了分析和總結，綜述了多層網絡故障定位方法。主要創新點與貢獻如下：

1)對多層網絡故障探測信息獲取策略進行了分類與總結，討論了不同探測信息獲取策略的優缺點以及面臨的挑戰。

2)討論和總結了現有的基于資源映射關系的網絡故障定位模型，并對其優缺點進行分析。

3)從故障定位模型、探測信息獲取方式、故障定位計算、網絡異構性、運行效率與成本多個方面綜述了多層網絡故障定位方法。

4)討論了多層網絡故障定位研究的不足和面臨的挑戰，并對未來更進一步的研究指出可能的方向。

1 多層網絡故障的定義

1.1 故障的定義

故障是指網絡發生問題的根源所對應的網絡事件。網絡中一個設備的故障有可能導致其他設備的故障。故障可能發生在硬件設備(如路由器、鏈路等)或者軟件(如路由表、網絡服務等)上。在網絡中癥狀是故障的外在表現形式。癥狀可以以不同的方式被觀測到，如網絡告警、人為觀測，或者使用主動監測機制。在網絡設備上可以放置監測代理，當網絡設備觀測到任何異常時，網絡設備上的監測代理會以告警的方式向網絡產生通告。告警表示網絡部件觀測到該部件不能正常運行，如丟包、連接失敗或者鏈路故障。這些告警被看作網絡可能發生故障的癥狀。使用這些告警診斷網絡中的故障涉及的挑戰是實際的故障可能出現在網絡的任何位置。

用圖1來解釋1個故障情形。客戶嘗試使用安全外殼協議(SSH)來連接到遠程服務器(服務器2)。在端路由器上有多個入口到服務器2上，在它的轉發表上有不同的轉發端口，在轉發表上總是選擇第一個入口。如圖1所示，關于目的地服務器2的SSH請求被錯誤地轉發到服務器1上，服務器1把相應的SSH請求丟棄，并產生告警。客戶沒有接收到SSH請求的應答，最終超時，產生告警(即連接失敗)報告給網絡管理員。這個例子表明故障部件可以引起遠程位置的服務中斷。本文把網絡中的客戶機、服務器和路由器等網絡設備抽象為節點，把連接相鄰節點的路徑設備抽象為鏈路，并把節點和鏈路統稱為網絡部件。本文研究的故障類型為節點故障和鏈路故障，并稱由故障的節點或鏈路產生的告警為癥狀。

圖 1 故障及癥狀/警告舉例Fig. 1 Examples of failures and symptoms/alarms

.2 多層網絡故障的定義

本文把覆蓋網(Overlay網絡)、虛擬網等通過底層網絡資源的抽象和隔離而虛擬出來的網絡稱為虛擬層網絡。把底層網絡和由它虛擬出來的虛擬層網絡稱為多層網絡。

本文把多層網絡表示為無向圖 G=(V,E)，其中： V 是節點集，包括底層節點 VSN和虛擬層節點VVN； E 是鏈路集，包括底層鏈路 ESN和虛擬層鏈路EVN。稱虛擬層節點和虛擬層鏈路為虛擬部件，底層節點和底層鏈路為底層部件。

多層網絡故障包括底層部件故障和虛擬層部件故障。其中，底層故障部件包括底層故障節點和底層故障鏈路。虛擬層故障部件包括虛擬層故障節點和虛擬層故障鏈路。

本文稱在虛擬層網絡中由虛擬層節點和虛擬層鏈路連接而成的端到端的虛擬層最短路徑為多層網絡服務。

多層網絡中的癥狀可能由故障的節點、鏈路或服務異常產生。服務的狀態反映了它所通過的虛擬層部件的狀態。多層網絡中節點或鏈路故障產生的告警和觀察到的端到端服務異常狀態稱為負面癥狀，觀察到的端到端服務正常狀態稱為正面癥狀。

在多層網絡中虛擬層部件和底層部件存在映射關系，包括節點映射和鏈路映射。節點映射表示一個虛擬層節點映射到底層網絡中的一個底層節點上。圖2是多層網絡中虛擬層網絡映射到底層網絡的一個例子，圖中overlay網絡中的虛擬節點A映射到底層節點 N1上。鏈路映射表示一條虛擬層鏈路映射到底層網絡中的一條路徑上，即一條虛擬層鏈路可能跨越多個底層鏈路。如圖2所示多層網絡中的虛擬層鏈路 (D,C)映射到底層路徑 N4→ N9→ N3上。

圖 2 多層網絡中虛擬層網絡映射到底層網絡的例子Fig. 2 Mapping between virtual layer network and substrate network in multilayer networks

在多層網絡中，互聯網服務提供者(ISP)被分為兩類：基礎設施提供者(InP)和服務提供者(SP)。服務提供者為用戶提供定制的端到端服務。InP把底層網絡資源租給SP，通過這種方式提高了底層網絡資源的利用率，但是由于多層網絡賦予底層網絡新的功能，多層網絡故障增加了傳統網絡的故障形式，給故障診斷帶來挑戰，具體分析如下。

1)底層網絡信息不可獲得性和信息的不完全性與不準確性。底層網絡通常不愿與虛擬層網絡共享詳細的網絡信息，例如：底層網絡的癥狀，虛擬層網絡和底層網絡的映射關系，底層網絡的先驗概率等，這對于故障診斷是十分關鍵的。此外，完全地監控所有底層網絡和虛擬層網絡是不可行的，故障診斷必須依賴于不準確和不完全的信息，這就導致了故障診斷的不確定性。

2)動態癥狀-故障因果關系。虛擬節點和鏈路與底層節點映射的靈活性和動態性使得虛擬層網絡和底層網絡的因果關系變得不可預測。在多層網絡中作為故障診斷基礎的癥狀-故障因果關系是動態和不可預測的。

3)多層故障。多層網絡服務性能的下降可能由于虛擬層或底層網絡的部件故障引起的。由于底層網絡部件和虛擬層網絡部件存在映射關系，底層網絡部件故障會導致對應的虛擬層網絡部件故障。虛擬層網絡部件和底層網絡部件的映射關系使得多層網絡故障定位變得更加復雜。因此，本文把虛擬層故障分為獨立虛擬層故障和相關虛擬層故障。在虛擬層網絡中由于軟件錯誤引起的故障稱為獨立虛擬層故障。相關虛擬層故障是由底層部件的故障而引起的虛擬層故障，如果底層故障部件恢復正常了，相關虛擬層故障也就不存在了。

2 多層網絡探測信息獲取策略

2.1 被動監測策略

被動監測策略通過在網絡設備上放置監測代理來監測網絡。網絡中的任意部件的故障將會由監測代理產生告警，接著告警被NMS作為負面癥狀來分析網絡中故障部件的精確位置。由于NMS被動地等待監測代理發送告警，所以這種方法是被動性的。與傳統網絡相比，多層網絡不僅具有底層網絡還有抽象的虛擬層網絡，因此多層網絡的被動監測可逐層進行，即分別在底層網絡和虛擬層網絡采用被動監測策略建立模型，以此來定位出底層網絡故障部件和虛擬層網絡故障部件。

噪聲的干擾會造成被動監測癥狀的丟失，或虛假癥狀的存在，因此多層網絡的被動監測策略面臨著如何獲得和保持準確信息的挑戰[1,6-7]，因為故障定位的準確性直接取決于所建模型中信息的準確性。

2.2 主動探測策略

主動探測策略與被動監測不同，通過在多個網絡節點上配置探測站并沿著探測路徑發送數據包(探測包)來測量探測站節點之間(端到端)的連通性以獲取探測路徑通過的網絡部件的二進制狀態信息[8]。探測路徑兩端的探測站節點為探測包的發送端和接收端。如果在探測路徑發送端發送的探測包可以被接收端接收，則表明該探測路徑是連通的，測試結果表示為“1”，即該探測路徑通過的節點都是正常的；反之，該探測路徑是不連通的，測試結果表示為“0”，即該探測路徑上至少存在一個故障節點。與被動監測相比，主動探測中探測包的使用有助于NMS對于大量的網絡故障事件反應更快、更精確，這與傳統的被動接收告警的方法有著極大不同。由于探測站配置和探測路徑選擇的過程可以控制，所以主動探測是靈活的。

主動探測包括2種：預計劃探測策略和適應性探測策略。預計劃探測策略首次由Brodie等[9]提出，Brodie等解決的是單節點故障定位問題，通過使用依賴矩陣來解釋探測選擇問題，依賴矩陣D是 r×n矩 陣，其中，r是網絡中探測路徑的數量，n 是網絡中節點的數量。如果探測 Pi經 過節點 Nj，矩陣元素 D(i,j)=1， 否則 D(i,j)=0。預計劃探測策略需要解決的問題是：如何在給定的網絡拓撲中構建合適的探測路徑，使得網絡中的每條節點發生故障時能夠返回不同的測試結果。考慮花費問題，盡量少地部署探測站和構造探測路徑也是此類問題的考慮方向。然而，Brodie等使用的預計劃探測策略存在一些限制：只假設單個節點發生故障，未考慮測試結果丟失、虛假測試結果以及動態的探測路徑等的影響。隨后，Tapolcai等[10-13]采用預計劃探測策略針對全光網絡中的單鏈路和多鏈路故障提出多種故障定位方法。然而，這些方法只適用于小型網絡。Xuan等[11]采用預計劃探測策略提出的算法解決了大型網絡中多個鏈路故障定位問題。由于多層網絡具有多層故障，且底層部件的故障會導致虛擬層部件的故障，多層網絡的預計劃探測策略可逐層進行，即分別在底層網絡和虛擬層網絡采用預計劃探測策略建立模型。首先，在底層網絡中采用預計劃探測策略定位出底層故障部件。其次，對底層故障部件進行故障恢復，則相關虛擬故障部件也被恢復。最后，在虛擬層網絡中采用預計劃探測策略來定位出獨立虛擬層故障。適應性探測策略的使用在文獻[9]中定義，由Natu等[6,13-14]進行了深入探究和論述，并在此基礎上提出了基于確定性模型以及非確定性模型的適應性探測算法。在這種探測策略中，不是發送探測包來定位所有可能的故障，而是首先發送少量探測包來監測所有的網絡部件的狀態。這些探測包可以監測是否有故障發生，但不能夠定位故障的確切位置。基于探測結果，首先識別出可能的故障區域，其次發送額外的探測包來精確定位故障的位置。適應性探測的主要目標是通過發送最少數目的探測包來精確地定位故障部件的位置。同樣地，多層網絡的適應性探測策略可逐層進行。主動探測策略本質上是通過測試端到端路徑上的部件狀態，與被動監測策略相比對故障響應更快，更靈活性，因此多層網絡采用主動探測策略定位故障效率更高。主動探測策略具有明顯的優勢，但是在實際的使用過程中，網絡需要發送大量的管理所需的流量，由于并不是所有的故障同時發生，所以大量的流量是浪費的。此外，發送較多數目的探測會產生延遲，很難得到最優的探測路徑集合以及收集到精確的測試結果。上述缺點將導致故障定位率降低以及故障定位時間增加，因此綜合考慮探測效率、探測代價的主動探測策略成為進一步亟待解決的問題。

2.3 主被動結合探測策略

主被動結合探測策略同時使用被動監測策略和主動探測策略，彌補了單一一種探測策略的不足。Tang等[15]采用主被動結合探測策略提出了主動集成故障推理(AIR)框架。如圖3所示，主動集成故障推理過程包括3個功能模塊：故障推理、保真度評價和行動選擇。

3 多層網絡故障定位模型

圖 3 主動集成故障推理流程Fig. 3 Flow chart of AIR framework

故障推理模塊把被動觀察到的癥狀作為輸入返回故障假設集 Φ作為輸出。故障假設集 Φ包括一列假設 h1,h2,···,hp，其中每一個假設包括可以解釋所有觀察到的癥狀的故障集。然后把 Φ發送到保真度評價模塊來檢驗任意的假設 hi∈Φ是否具有高保真度，如果具有高保真度，那么故障推理過程終止。否則，有助于解釋具有最高保真度hi的一列未觀察到的癥狀 SN被發送到行動選擇模塊來確定哪個癥狀已經發生。因此，保真度評價值 hi相應地調整。執行的行動返回測試結果，測試結果是已存的癥狀集 SV和不存在的癥狀集SU。基于行動返回的結果，對應的保真度值可能被增加或減少。如果新計算的保真度滿足條件，那么推理過程終止，否則 SO、SU作為故障推理模塊的新輸入來生成一個新的假設。這個過程一直重復直到找到具有高保真度的假設。

多層網絡具有多層故障，且底層部件的故障會導致虛擬層部件的故障，因此多層網絡的主被動結合探測策略可逐層進行，即分別在底層網絡和虛擬層網絡采用主被動結合探測策略來定位出底層網絡故障部件和獨立虛擬層故障部件。行動選擇的使用減少了由于噪聲存在引起的癥狀丟失或虛假癥狀存在的可能性，主被動結合探測策略最小化探測的使用而且提高了多層網絡故障定位的準確率。

2.4 終端用戶觀察策略

大多數多層網絡探測信息獲取策略要么需要網絡監測代理被動搜集到的大量告警信息，要么使用探測來主動監控網絡。然而，被動監控需要大量關于底層網絡部件后驗或先驗故障概率信息，這在實際實踐中限制了其有效性。采用主動探測策略監控網絡會產生額外的流量消耗，這會給多層網絡帶來負擔。因此，越來越多的研究者采用基于終端用戶觀察的探測信息獲取策略[16-20]。終端用戶觀察不需要知道多層網絡的先驗或后驗故障概率信息，僅僅使用終端用戶觀察到的服務負面癥狀找出可能發生的故障部件。

雖然多層網絡的終端用戶觀察策略不需要網絡監測代理被動搜集到的大量信息，或者使用探測來主動監控網絡，但是由于并不是所有的終端用戶都愿意共享服務狀態信息，且可能存在惡意的終端用戶共享錯誤的服務狀態信息，因此不充足的終端用戶觀察和惡意終端用戶會降低故障定位的精度。如何處理不充足的終端用戶觀察和識別出惡意的終端用戶是該策略進一步的研究方向。

表1是各種探測信息獲取策略在探測信息獲取方式，是否增加網路流量及花費，優缺點和面臨的挑戰等方面對現有的多種探測信息獲取策略進行的比較分析。

3.1 依賴矩陣模型

多層網絡依賴矩陣模型描述了采用主動探測策略時底層網絡和虛擬層網絡中探測路徑與其通過的網絡部件狀態(節點或鏈路)之間關系。根據網絡部件狀態是否為二進制狀態(正常“0”，或故障“1”)，可以將多層網絡的依賴矩陣模型分為二進制依賴矩陣模型[21-23]和非二進制依賴矩陣模型[24-27]。二進制依賴矩陣模型假設多層網絡部件和探測路徑只有正常和故障2種狀態，且假設探測路徑狀態是正常的當且僅當這條路徑上的所有部件都是正常狀態。非二進制依賴矩陣模型不僅可以定位出多層網絡故障部件而且可以判定多層網絡節點、鏈路的擁塞程度或鏈路延遲。

表 1 各種探測信息獲取策略的比較Table 1 Comparison of various detection information acquisition techniques

3.2 基于圖論的故障傳播模型

多層網絡基于圖論的故障傳播模型(fault propagation model，FPM)描述了采用被動監測策略時所有可能發生在底層網絡和虛擬層網絡故障和癥狀之間的關系。該模型需要具備底層網絡和虛擬層網絡部件故障狀態和告警與其他部件的故障。

建立狀態和告警之間相互關聯的先驗知識。為了建立這樣的模型，需要很好地了解每一層網絡部件間的依賴關系。故障定位算法的高效性和精確性依賴于先驗知識的精確性。FPM的常見模型有依賴圖模型或貝葉斯網絡模型。依賴圖模型是有向圖，其中節點表示事件，邊表示事件間的關系。每一條有向邊通過條件概率來標記，其表達的意思是：由于起始節點的故障導致了終點節點的故障。依賴圖的每個節點既可以表示網絡節點的故障，也可以表示網絡鏈路的故障。關于使用依賴圖模型的故障診斷方法的一些工作見文獻[6, 28-29]。貝葉斯網絡模型又稱信任網絡模型，是一個有向無環圖，其中，節點表示網絡鏈路狀態或端到端路徑狀態，有向邊表示端到端路徑或經由這些路徑的鏈路之間的依賴關系，其影響的大小用條件概率表示。每個節點是多值的隨機變量，其表達的意思是每個路徑或鏈路可能有多種故障類型，如延遲、大量的包丟失、完全不連通等。這種情形在故障傳播模型中可以被表示為每條路徑和鏈路在貝葉斯網絡模型中對應于多個路徑和鏈路節點，其中每個節點表示不同的故障類型。FPM也可以建模為二部圖模型。盡管在真實網絡中故障和癥狀間的關系通常比二部圖表示的關系更為復雜，但許多故障定位方法仍然使用二分FPM[4,6,9]，原因如下：1)執行具有復雜表示形式的故障定位模型是困難的；2)詳細模型通常可以通過一系列的圖規約操作降為二分模型；3)模型建立需要對網絡有深厚知識的積累，而癥狀-故障映射關系可以通過外在的觀測來獲得。因此，在許多真實的問題中使用二分的癥狀-故障模型是可行的。

為了減少由于使用大規模貝葉斯網絡模型計算復雜度，Bennacer等[30]提出了混合模型，結合了貝葉斯網絡模型(BN)和基于實例的推理機制(case based reasoing，CBR)的使用。這個模型的基本思想是，通過使用CBR減少基于BN相關的故障診斷方法的內在復雜性來簡化和優化故障診斷過程。在診斷過程中，BN結構的子集通過CBR來識別，在子集中只推理觀測到變化的節點。CBR的使用有助于利用先前學到的情況來解決目前的以及未來的問題。隨著時間的推移，CBR的知識庫不斷更新，有助于提高診斷的效率。通過使用混合模型加速了故障診斷過程以及減少了與推理相關的計算復雜度。

使用基于圖論的故障傳播模型的故障定位方法面臨著如何獲得和保持準確信息的挑戰[6,14]，因為故障定位的準確性直接取決于模型中信息的準確性。一些研究人員[31-33]利用建立非確定性故障傳播模型將信息的動態相關性納入模型中。Rish等[34]和Steiner等[31]建立動態貝葉斯網絡模型來表示網絡部件狀態隨時間的變化情況。動態BN網絡模型通過引入時間片的概念和時間片之間的轉移概率 P(Xt|Xt-1)對靜態BN網絡模型進行擴展， Xt=(xt1,xt2,···,xnt)表示節點在時間片t的狀態向量。然而，“動態”表示動態的系統，而不是隨時間變化的系統，DBN模型是非時變的，DBN模型具有馬爾科夫特性，即給定當前的狀態，網絡將來的狀態與它過去的狀態是獨立的。時間片內的依賴關系用靜態貝葉斯模型來描述。DBN模型是一個平穩過程，即轉移概率和時間片內依賴關系不隨時間的變化而變化。布 P(Xt-1) 以及在時間片t 的 觀測值 Yt，可以應用標準的BN模型推斷算法來計算 P(Xt|Xt-1,Yt)，其中

一旦給定動態的BN模型，基于先驗概率分Yt是在時間t觀測到的癥狀集。由于DBN模型的時間復雜度很高，文獻[35]提出了高效的近似算法來解決這個問題。為了減少控制開銷，應用網絡分區策略。目前的分區策略包括基于分簇的策略和基于圖分割的策略，這些策略的使用有助于減少通信開銷和控制開銷。Li等[36]通過使用分簇策略建立動態貝葉斯網絡模型來減少故障推理的時間復雜度，即使用DBN模型來表示大型IP網絡的狀態，將故障節點劃分為獨立的分簇來減少診斷時間。由于故障節點間的條件具有獨立性，對故障節點進行分簇是可行的。然而分簇的使用降低了故障診斷的準確性。

3.3 癥狀-故障-行動模型

癥狀-故障-行動模型(SFA模型)是一個5元組(S,F,A,E1,E2)， 其中故障集 F 、癥狀集S、行動集A是3個互相獨立的頂點集。

如圖4所示，癥狀-故障-行動模型表示的關系：對于每個行動，與之聯系起來的是行動頂點ai∈A；對于每個癥狀，與之聯系起來的是癥狀頂點 si∈S；對于每個故障，與之聯系起來的是故障頂點 fi∈F ；對于每個故障fi，與之關聯的邊的權重等于 p(si|fi)， 表示癥狀 si由它造成。對于每個行動ai，與之關聯的邊的權重等于行動花費，表示行動驗證癥狀存在的可能性。故障-癥狀-行動模型采用 了主被動結合探測策略，彌補了單一探測的不足。

圖 4 癥狀-故障-行動模型Fig. 4 Flow chart of AIR framework

4 多層網絡故障診斷與定位方法

4.1 O-AIR

與文獻[15]的AIR類似，Overlay網絡故障集成推理(O-AIR)[37]采用主被動結合探測策略。該方法假定網絡監測代理駐留在每個覆蓋網絡節點上，監測代理監控鏈路并收集關于網絡部件故障概率的信息和傳統觀察對應覆蓋網癥狀的概率，收集的探測信息用來構造集中式的基于查詢的信息系統稱為覆蓋網絡配置(overlay network profile，ONP)。進而將相關端到端癥狀和故障用于建立overlay故障-癥狀模型。然而，觀察到的癥狀可能不足以識別網絡中的所有故障，因此需要采用主動探測策略執行一組監測行動來確定發生故障的根源，在此基礎上建立overlay網絡癥狀-故障-行動(O-SFA)模型來定位出所有的故障部件。

O-AIR包括3個功能模塊：癥狀挖掘、故障推理和行動選擇。基于ONP，癥狀挖掘模塊使用觀察到的overlay癥狀來動態地創建O-SFA模型。故障推理模塊把O-SFA作為輸入，返回故障假設h作 為輸出。故障假設 h包括一組能解釋所有觀察到的癥狀的部件。選擇對應的overlay行動來驗證假設。如果 h中的所有故障都得到驗證，那么overlay故障診斷過程終止并進行故障匯報。反之，基于行動結果，通過除去不能解釋的overlay癥狀和不相關的部件并且增加新的癥狀及與之相關的部件來更新之前創建的O-SFA。該過程一直重復直到找到可驗證的假設。

圖5是對應于圖1中overlay網絡中的overlay鏈路和overlay路徑。圖5中的overlay網絡有2條overlay路徑：在overlay節點 D 和 E之間的路徑 PDE和在overlay節點 A 和 B 之間的路徑 PAB。overlay路徑 PDE包含2條overlay鏈路 lDC和 lCE；類似地，overlay路徑 PAB包 含2條overlay鏈路 lAC和lCB。 NDC、NCE、NAC、NCB表示底層網絡部件。圖6表示的是對應于圖5的overlay網絡的O-SFA模型。O-SFA模型中， Oi表示每一條overlay路徑對應的癥狀， Sj表示每條overlay鏈路對應的路徑，Fk表示overlay或其對應的underlay節點的故障，al表示驗證癥狀的行動節點。

圖 5 overlay網絡中的overlay鏈路和overlay路徑Fig. 5 overlay network showing overlay paths and links

圖 6 overlay網絡的O-SFA模型Fig. 6 Symptom-fault-action model for overlay network

可以看出，上述模型具有很強的優越性，但在實際應用中還需要進一步改進和完善：1)定位模型框架中不僅使用網絡監測代理被動收集的大量信息，同時還需借助使用探測包主動監測網絡狀態以克服現有方法的局限性；2)被動監測需要大量有關底層網絡部件后驗或先驗故障概率的網絡知識，這在實際中限制了該方法的有效性，同時探測帶來的額外流量也增加了基礎網絡負擔；3)模型的假設較強，需要增加對于關聯故障或多故障情形的適應能力。

4.2 多層監控方法

在overlay網絡中，通過測量所有的overlay節點對之間的路徑來監控所有overlay網絡鏈路是十分笨重且花費巨大代價的。Demirci等[38]提出了多層監控方法，監控部分底層網絡的鏈路和部分overlay鏈路的狀態來最小化監控overlay網絡的總花費。通過適當地組合底層鏈路和overlay鏈路可以推出整個overlay網絡鏈路的狀態。

虛擬網絡的被動故障診斷方法使用代表底層網絡、虛擬網絡故障和癥狀關系的網絡模型。相應的故障診斷問題可以闡述為概率推理問題，在給定觀測癥狀的情況下識別在底層網絡中的故障。然而，這些方法忽略了在虛擬層獨立存在的故障。Yan等[39]建立了分層模型，提供了虛擬網絡環境中可能發生的3種故障。在底層發生的故障被稱為底層故障(SF)，它可能導致對應虛擬節點和鏈路的故障，稱之為相關虛擬故障(CVF)。由于虛擬層軟件錯誤發生的故障稱為獨立虛擬故障(IVF)。當底層故障得到修復時，對應的相關虛擬故障也會自動被修復。為此，Yan等在文獻[39]中描述了基于癥狀-故障關系和所觀測的癥狀來定位出所有虛擬故障的方法，基于CVF和SF的映射關系定位底層故障SF，提出了過濾算法來區分CVF和IVF。文獻[15]假設選擇算法從過濾過的故障中推出可以解釋觀察到的癥狀的故障假設集合，然而他們卻忽略了CVF和IVF交集非空的可能，導致故障定位不完全，診斷率不高。

劉娜等[40]提出一種針對網絡虛擬化環境下虛擬網和底層網的分層模型。采用多層監控方法，通過虛擬網信任評估算法來提高故障診斷的準確率降低誤報率。張順利[41]提出了網絡虛擬化環境下的服務故障傳播模型。為了提高診斷算法的性能，提出了基于癥狀內在相關性的多層虛擬網服務故障診斷算法，該算法能夠很好地解決底層網絡信息對服務提供商可見性造成的虛擬網服務故障難以定位的問題，可以有效地降低診斷算法的誤報率，減少診斷算法的診斷時間。

由于底層網絡信息對服務提供商不可見性造成虛擬網服務故障難以定位，又由于每個底層網絡上同時承載的虛擬網絡數量較多，導致癥狀集中包含的癥狀和故障集中包含的故障較多，因此多層監控方法的故障診斷性能較低。

4.3 基于終端用戶觀察策略的方法

終端用戶觀察策略不需要知道虛擬網絡的全部知識，僅僅使用終端用戶觀察到的負面癥狀找出可能發生的故障部件。Tang等[18]提出了overlay故障診斷框架DigOver。這里終端用戶觀察到的負面癥狀對應于一條overlay路徑上的所有部件的集合。使用負面癥狀作為證據構造可能發生的故障部件集合，即故障假設集。使用Dempster-Shafer理論評價故障假設集中的每個故障進而使用評價的不確定性來量化部件故障發生的可能性。Dempster-Shafer理論的使用使得其與其他基于貝葉斯理論的概率故障診斷方法不同。在貝葉斯推理中需要主動監控或網絡監測代理搜集的大量信息。然而DigOver不需要這樣的先驗信息，僅僅需要網絡拓撲信息。盡管DigOver具有較高的準確性，但是評價故障可能性的時間花費過長，特別是當負面癥狀集中于少量的故障部件時。為此，Wang等[19]提出了一個故障診斷方法DiaEO，DiaEO將終端用戶觀察到的負面癥狀進行篩選，把負面癥狀矩陣篩選成多個子矩陣，并在每個子矩陣上分析癥狀來減少推理時間。Gillani等[20]提出另外一種基于終端用戶觀察的故障診斷方法。終端用戶之間通過匯報他們觀察到的數據包丟失和路由信息共享服務異常信息(即負面癥狀)。文獻[23]的貢獻在于創建一個基于約束的模型探測器來準確定位大規模網絡的數據包丟失，且這個過程不需要任何主動探測或網絡監測代理。這個模型利用終端用戶負面癥狀之間的相關性(歸因于共享的癥狀和路徑片段)和觀察到的網絡數據包丟失特性，使用可滿足性模理論(satisfiability modulo theories，SMT)對約束進行編碼。高級SMT解答器如Z3和Yices可以解決數千的約束條件和數百萬的變量[42]。這種方法對于大量癥狀和網絡部件具有擴展性。文中的模型探測器可以識別滿足終端用戶觀察和網絡數據包丟失的網絡部件根源的最小集。然而，由于不充足的終端用戶觀察，該故障診斷系統具有低精確度風險。此外，一些終端用戶可能是惡意的，并向其他終端用戶分享虛假觀察。選擇性請求合適的終端用戶發送網絡探測信息來解決不充足的觀察。這些探測僅僅瞄準可能發生故障部件的很小的子集。同時，已有的文獻證明了需要發送的探測僅僅消耗極少的流量，進而通過識別并把它們匯報的虛假觀察從系統中除去來解決惡意終端用戶問題。

雖然終端用戶觀察不需要網絡監測代理被動搜集到的大量信息，或者使用探測來主動監控網絡，但是不充足的終端用戶觀察和惡意終端用戶會降低故障診斷系統的精度。

4.4 高效的overlay網絡配置

Demirci等[43]提出了高效的節點配置來加快故障診斷速度并最優化overlay監控。一個新術語診斷能力被定義為overlay網絡使用最小的花費來精確診斷可能發生的故障的特性。診斷能力很大程度上依賴于底層網絡拓撲。此外，overlay節點的配置也對overlay的診斷能力起重大作用。圖7是3個節點的overlay網絡在底層網絡上的不同配置的例子。對于overlay ABC，底層節點X的故障可以在路徑AB上被觀察到。然而，由于2個底層鏈路和1個底層節點都可能是故障的根源，因此故障部件集合不能被降低為1個部件。另一方面，對于overlay配置ABC′可以在3個端到端路徑上觀察到故障節點X，且故障節點可以被唯一地定位。通常情況下診斷能力和底層部件的壓力(對于底層節點，壓力是映射到其上的overlay節點數；對于底層鏈路，其壓力是通過它的overlay鏈路數)之間存在權衡，即較高的診斷能力通常會以底層網絡的壓力為代價。overlay配置方法基于以下思想。

1)增加共享1個底層鏈路的平均overlay路徑數：端到端路徑共享1個底層部件越多，可以觀察到該部件發生故障的癥狀數越多，這有助于定位故障。

2)限制一個部件上的最大壓力：底層節點或鏈路由過多overlay節點或鏈路共享將會帶來擁塞或資源耗盡的風險。

3)限制幾乎完全重疊的overlay路徑數：兩個完全重疊的端到端路徑會觀察到同一個癥狀，不會比與之重合的單個overlay路徑提供更多有價值的信息。

圖 7 overlay網絡的2種可能的配置Fig. 7 Sample topology with two possible placements of an overlay network

綜合這3種思想，配置算法的目標是最大化配置質量即度量q。算法始于overlay到底層網絡的隨機配置，通過作一些較小的調整來逐漸提高q。這個方法利用了overlay設計的靈活性來最大化overlay網絡的診斷能力。

4.5 動態貝葉斯模型

為了保證在網絡虛擬化環境下診斷算法的性能，克服強動態性特點帶來的問題，Rahman等[44]綜合考慮動態環境對網絡模型、網絡狀態、故障先驗概率等方面的影響，采用動態貝葉斯網絡模型對網絡虛擬化環境下的故障診斷問題進行建模，提出動態環境下的虛擬網故障診斷算法。算法的主要過程包括時間信息處理、噪聲處理、故障定位、計算后驗概率和執行更新。算法的步驟如下。

1)時間信息處理。假設時間片1的模型為FFDDMMF2(D(FMFi1,ti,,(2S F,Sii,,t1i,,,2P S,PFi,i1F,t,,i,P2P,FFPii,,1Ft,,Si,P2i,,tS)Fi。i,,21),S，i,1最)，終時合間成片的2期的望模模型型為為

2)噪聲處理。去除噪聲共分為2個步驟：先根據癥狀與故障之間的關系，過濾掉虛假故障；再根據癥狀之間的關系，過濾掉被動癥狀。

3)診斷算法。通過分析觀測到的癥狀So，t，找出

故障

一

的

系

集

列合可)能，

通

解過釋計當算前假癥設狀集的合假的設信集度合

B

H(H

it(it,一So

組

,t)，輸出信度最大的一個或者多個假設的集合作為最終定位結果。

4)計算后驗概率和執行更新。為了提高動態環境下的故障診斷算法性能，在每個時間片診斷結束后，修正每個時間窗口內的先驗故障概率。對于每一個故障節點，使用貝葉斯公式計算其后驗概率，利用后驗概率和傳播概率，更新當前節點故障的概率，將本次計算結果作為下一個時間片的先驗概率，然后進入下一個時間片繼續處理。

使用動態貝葉斯模型的故障診斷方法面臨的挑戰如下。

1)故障探測中考慮時間信息處理的動態貝葉斯模型計算復雜度高。使用基于時間信息處理的動態貝葉斯模型在時間片內是靜態貝葉斯網絡模型。這種方法可以處理各種不同的動態系統，但是靜態貝葉斯網絡模型本身的復雜度會增加動態貝葉斯網絡模型的計算復雜度。

2)故障診斷精度不高的問題。在DBN模型中，可以拆分故障節點為獨立的簇來減少診斷時間和進行推斷。然而簇的使用降低了故障診斷的精度。

3)網絡虛擬化的動態性特點容易造成網絡模型知識不準確、網絡信息傳輸時噪聲增大等問題，給故障診斷帶來挑戰。

可以看出，現有工作在研究面向高動態網絡的故障管理與定位方面充分考慮了狀態的遷移、故障節點間的條件獨立性、網絡的規模和時間復雜度等方面。然而，過于復雜的定位技術在實際的網絡管理和故障定位中并不具備通用性，并且已有方法均基于探測到的故障信息和事先收集的癥狀-故障關系以及假定網絡狀態或故障節點之間是獨立的，而這些與實際信息網絡的狀態累積(如擁塞導致的故障)和網絡互聯(如網絡中存在的數據流)的本質有些是不相符的。因此，重新考察與驗證狀態或節點之間的獨立性，建立面向實際網絡的通用故障定位技術，提高故障定位算法的運行速度和準確性，將成為本研究領域的核心問題。

5 開放性研究問題和未來研究方向

綜合上述分析，現有故障定位技術相關研究的不足和亟待進一步研究解決的問題如下。

1)現有的故障定位模型對于資源映射特性的考慮有待完善，研究虛擬網絡的故障定位模型還非常有限。已有的研究工作仍然缺乏對信息獲取和模型建立過程的研究。由于信息獲取的復雜性以及與之相關的諸多問題，建立精確的網絡模型被認為是一個獨立的過程，而且大多數的研究方案假設上述模型是事先存在的。隨著新的網絡環境部署，在很長一段時間內，已有的或遺存的網絡環境仍然會與新技術共存，網絡管理方案應該能夠管理網絡的異構性。此外，基于網絡的服務通常會穿越已有的或新的網絡、物理的或虛擬的網絡部件，因此異構網絡部件的共存需要從端到端的角度實現網管系統的無縫管理。

2)網絡的動態性、探測效率、探測代價、網絡開銷等約束關系難以權衡，研究高動態網絡特性的故障探測信息獲取技術仍然是一個空白區域。使用探測來診斷網絡需要在網絡中的一個或多個位置上放置探測站，接著選擇探測瞄準不同的網絡節點和鏈路。探測站需要探測編碼的安裝、操作、維護，探測包的發送需要額外的網絡流量花費以及收集、存儲和分析測試結果，探測站和探測路徑的部署增加了網絡管理的花費。未來的可行方法是優化探測站的選擇和探測路徑數量的設定并最小化監測花費，提出綜合考慮探測效率、探測代價的探測信息獲取技術。為了適應基礎設施的頻繁變化，有必要建立基于預測思想的下一代網絡管理系統。該系統不僅具有檢測和定位的功能，還應當從最近的網絡部件狀態信息中捕捉和預防故障的發生，提供更好的網絡穩定性和服務交付，以及網絡管理(如資源提供、監控、分析與通知等)一體化解決方案。

3)現有的故障定位中的獨立性假設較強，設計面向不同定位需求的通用故障定位算法仍然充滿挑戰。近年來，雖然已經出現了多種近似的解決方案，但權衡網絡故障診斷準確性和網絡控制開銷仍然是一個挑戰性的問題。目前為止，還沒有直接的證據證明網絡狀態前后之間或故障節點之間的獨立性假設的合理性，更沒有建立面向實際網絡的通用故障定位技術。同時針對不同的業務需求，需要進一步降低概率推理近似算法的復雜度，提高故障定位算法的運行速度和準確性仍舊充滿挑戰。

因此，針對上述問題未來可研究面向虛擬異構信息網絡的故障診斷方法。從故障定位模型、信息獲取方式、故障定位計算、網絡異構性、運行效率與成本等方面入手，設計一個面向異構多層信息網絡的故障探測與定位體系。需要充分考慮信息獲取的復雜性、網絡新老技術的共存性和故障定位模型的真實性，建立面向虛擬網絡的故障定位新模型；將優化探測站的選擇和探測路徑數量的設定，研究綜合考慮探測效率、探測代價、網絡開銷等約束的高動態虛擬網絡故障探測信息獲取新技術；此外，研究并驗證狀態或節點之間的關系，設計面向不同業務需求的通用故障定位算法，進一步提高故障定位算法的運行速度和準確性。在上述體系結構下，可以致力于基于預測思想的下一代網絡管理系統，該系統不僅具有故障監測和定位的功能，還應當從最近的網絡部件狀態信息中捕捉和預防故障的發生。

6 結束語

本文總結和研究了多層信息網絡的定位問題，從故障定位模型、信息獲取方式、故障定位計算、網絡異構性、運行效率與成本等方面入手，充分研究了多層網絡故障定位方法，分析了各種方法的優缺點。最后，對現有故障定位方法相關研究的不足和亟待進一步研究解決的問題進行了總結，并指出了未來的研究方向。