多層信息網(wǎng)絡(luò)故障定位綜述

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

（1. 西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 西安 710126; 2. 西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安710071）

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

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

有別于傳統(tǒng)觀念中需要大量人工干預(yù)，逐一排除故障的方法，目前較多文獻(xiàn)研究的目的是以極少的人工干預(yù)以及網(wǎng)絡(luò)負(fù)載實(shí)現(xiàn)快速精確的故障定位，主要定位節(jié)點(diǎn)故障和鏈路故障。當(dāng)前該領(lǐng)域面臨的挑戰(zhàn)如下：

1)精確的網(wǎng)絡(luò)模型

網(wǎng)絡(luò)的類型以及所建立的網(wǎng)絡(luò)模型決定了模型中使用的信息可能是靜態(tài)或動態(tài)的，而動態(tài)信息的存在使得該問題更具有挑戰(zhàn)性，因?yàn)楫?dāng)網(wǎng)絡(luò)運(yùn)行時(shí)更多的信息將被納入模型之中。此外，片面、不完全、不準(zhǔn)確的信息可能會延誤診斷過程或影響診斷的準(zhǔn)確性。

2)計(jì)算復(fù)雜性

概率推理固有的高時(shí)空復(fù)雜度，使面向大型、復(fù)雜通信網(wǎng)絡(luò)的故障定位計(jì)算變得更為棘手，而且這些計(jì)算需要反復(fù)執(zhí)行，以便持續(xù)監(jiān)測網(wǎng)絡(luò)。

3)故障定位技術(shù)

分布式的技術(shù)有助于減少故障檢測的時(shí)間和解決集中式管理節(jié)點(diǎn)的瓶頸，然而這會增加網(wǎng)絡(luò)的控制開銷。此外，改變網(wǎng)絡(luò)管理系統(tǒng)的監(jiān)控目標(biāo)可能需要在節(jié)點(diǎn)上完成一定數(shù)量的手工配置，而這種配置過程進(jìn)一步使得分布式的定位方案變得更為復(fù)雜。

4)新型網(wǎng)絡(luò)中的故障定位

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

5)高動態(tài)環(huán)境下的網(wǎng)絡(luò)管理

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

6)網(wǎng)絡(luò)環(huán)境的復(fù)雜性

隨著新的網(wǎng)絡(luò)環(huán)境部署，在很長一段時(shí)間內(nèi)，已有的或遺存的網(wǎng)絡(luò)環(huán)境仍然會與新技術(shù)共存。在過渡時(shí)期內(nèi)，網(wǎng)絡(luò)管理方案應(yīng)該能夠管理網(wǎng)絡(luò)的復(fù)雜性。此外，基于網(wǎng)絡(luò)的服務(wù)通常會穿越已有的與新的網(wǎng)絡(luò)中物理的和虛擬的網(wǎng)絡(luò)部件。因此，信息網(wǎng)絡(luò)的共存需要從端到端的角度實(shí)現(xiàn)網(wǎng)管系統(tǒng)的無縫管理。

本文對多層信息網(wǎng)絡(luò)故障定位過程中采用的探測信息獲取策略，和基于資源映射關(guān)系的網(wǎng)絡(luò)故障定位模型進(jìn)行了分析和總結(jié)，綜述了多層網(wǎng)絡(luò)故障定位方法。主要創(chuàng)新點(diǎn)與貢獻(xiàn)如下：

1)對多層網(wǎng)絡(luò)故障探測信息獲取策略進(jìn)行了分類與總結(jié)，討論了不同探測信息獲取策略的優(yōu)缺點(diǎn)以及面臨的挑戰(zhàn)。

2)討論和總結(jié)了現(xiàn)有的基于資源映射關(guān)系的網(wǎng)絡(luò)故障定位模型，并對其優(yōu)缺點(diǎn)進(jìn)行分析。

3)從故障定位模型、探測信息獲取方式、故障定位計(jì)算、網(wǎng)絡(luò)異構(gòu)性、運(yùn)行效率與成本多個(gè)方面綜述了多層網(wǎng)絡(luò)故障定位方法。

4)討論了多層網(wǎng)絡(luò)故障定位研究的不足和面臨的挑戰(zhàn)，并對未來更進(jìn)一步的研究指出可能的方向。

1 多層網(wǎng)絡(luò)故障的定義

1.1 故障的定義

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

用圖1來解釋1個(gè)故障情形?？蛻魢L試使用安全外殼協(xié)議(SSH)來連接到遠(yuǎn)程服務(wù)器(服務(wù)器2)。在端路由器上有多個(gè)入口到服務(wù)器2上，在它的轉(zhuǎn)發(fā)表上有不同的轉(zhuǎn)發(fā)端口，在轉(zhuǎn)發(fā)表上總是選擇第一個(gè)入口。如圖1所示，關(guān)于目的地服務(wù)器2的SSH請求被錯(cuò)誤地轉(zhuǎn)發(fā)到服務(wù)器1上，服務(wù)器1把相應(yīng)的SSH請求丟棄，并產(chǎn)生告警。客戶沒有接收到SSH請求的應(yīng)答，最終超時(shí)，產(chǎn)生告警(即連接失敗)報(bào)告給網(wǎng)絡(luò)管理員。這個(gè)例子表明故障部件可以引起遠(yuǎn)程位置的服務(wù)中斷。本文把網(wǎng)絡(luò)中的客戶機(jī)、服務(wù)器和路由器等網(wǎng)絡(luò)設(shè)備抽象為節(jié)點(diǎn)，把連接相鄰節(jié)點(diǎn)的路徑設(shè)備抽象為鏈路，并把節(jié)點(diǎn)和鏈路統(tǒng)稱為網(wǎng)絡(luò)部件。本文研究的故障類型為節(jié)點(diǎn)故障和鏈路故障，并稱由故障的節(jié)點(diǎn)或鏈路產(chǎn)生的告警為癥狀。

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

.2 多層網(wǎng)絡(luò)故障的定義

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

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

多層網(wǎng)絡(luò)故障包括底層部件故障和虛擬層部件故障。其中，底層故障部件包括底層故障節(jié)點(diǎn)和底層故障鏈路。虛擬層故障部件包括虛擬層故障節(jié)點(diǎn)和虛擬層故障鏈路。

本文稱在虛擬層網(wǎng)絡(luò)中由虛擬層節(jié)點(diǎn)和虛擬層鏈路連接而成的端到端的虛擬層最短路徑為多層網(wǎng)絡(luò)服務(wù)。

多層網(wǎng)絡(luò)中的癥狀可能由故障的節(jié)點(diǎn)、鏈路或服務(wù)異常產(chǎn)生。服務(wù)的狀態(tài)反映了它所通過的虛擬層部件的狀態(tài)。多層網(wǎng)絡(luò)中節(jié)點(diǎn)或鏈路故障產(chǎn)生的告警和觀察到的端到端服務(wù)異常狀態(tài)稱為負(fù)面癥狀，觀察到的端到端服務(wù)正常狀態(tài)稱為正面癥狀。

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

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

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

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

2)動態(tài)癥狀-故障因果關(guān)系。虛擬節(jié)點(diǎn)和鏈路與底層節(jié)點(diǎn)映射的靈活性和動態(tài)性使得虛擬層網(wǎng)絡(luò)和底層網(wǎng)絡(luò)的因果關(guān)系變得不可預(yù)測。在多層網(wǎng)絡(luò)中作為故障診斷基礎(chǔ)的癥狀-故障因果關(guān)系是動態(tài)和不可預(yù)測的。

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

2 多層網(wǎng)絡(luò)探測信息獲取策略

2.1 被動監(jiān)測策略

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

噪聲的干擾會造成被動監(jiān)測癥狀的丟失，或虛假癥狀的存在，因此多層網(wǎng)絡(luò)的被動監(jiān)測策略面臨著如何獲得和保持準(zhǔn)確信息的挑戰(zhàn)[1,6-7]，因?yàn)楣收隙ㄎ坏臏?zhǔn)確性直接取決于所建模型中信息的準(zhǔn)確性。

2.2 主動探測策略

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

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

2.3 主被動結(jié)合探測策略

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

3 多層網(wǎng)絡(luò)故障定位模型

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

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

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

2.4 終端用戶觀察策略

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

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

表1是各種探測信息獲取策略在探測信息獲取方式，是否增加網(wǎng)路流量及花費(fèi)，優(yōu)缺點(diǎn)和面臨的挑戰(zhàn)等方面對現(xiàn)有的多種探測信息獲取策略進(jìn)行的比較分析。

3.1 依賴矩陣模型

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

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

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

多層網(wǎng)絡(luò)基于圖論的故障傳播模型(fault propagation model，F(xiàn)PM)描述了采用被動監(jiān)測策略時(shí)所有可能發(fā)生在底層網(wǎng)絡(luò)和虛擬層網(wǎng)絡(luò)故障和癥狀之間的關(guān)系。該模型需要具備底層網(wǎng)絡(luò)和虛擬層網(wǎng)絡(luò)部件故障狀態(tài)和告警與其他部件的故障。

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

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

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

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

3.3 癥狀-故障-行動模型

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

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

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

4 多層網(wǎng)絡(luò)故障診斷與定位方法

4.1 O-AIR

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

O-AIR包括3個(gè)功能模塊：癥狀挖掘、故障推理和行動選擇?；贠NP，癥狀挖掘模塊使用觀察到的overlay癥狀來動態(tài)地創(chuàng)建O-SFA模型。故障推理模塊把O-SFA作為輸入，返回故障假設(shè)h作 為輸出。故障假設(shè) h包括一組能解釋所有觀察到的癥狀的部件。選擇對應(yīng)的overlay行動來驗(yàn)證假設(shè)。如果 h中的所有故障都得到驗(yàn)證，那么overlay故障診斷過程終止并進(jìn)行故障匯報(bào)。反之，基于行動結(jié)果，通過除去不能解釋的overlay癥狀和不相關(guān)的部件并且增加新的癥狀及與之相關(guān)的部件來更新之前創(chuàng)建的O-SFA。該過程一直重復(fù)直到找到可驗(yàn)證的假設(shè)。

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

圖 5 overlay網(wǎng)絡(luò)中的overlay鏈路和overlay路徑Fig. 5 overlay network showing overlay paths and links

圖 6 overlay網(wǎng)絡(luò)的O-SFA模型Fig. 6 Symptom-fault-action model for overlay network

可以看出，上述模型具有很強(qiáng)的優(yōu)越性，但在實(shí)際應(yīng)用中還需要進(jìn)一步改進(jìn)和完善：1)定位模型框架中不僅使用網(wǎng)絡(luò)監(jiān)測代理被動收集的大量信息，同時(shí)還需借助使用探測包主動監(jiān)測網(wǎng)絡(luò)狀態(tài)以克服現(xiàn)有方法的局限性；2)被動監(jiān)測需要大量有關(guān)底層網(wǎng)絡(luò)部件后驗(yàn)或先驗(yàn)故障概率的網(wǎng)絡(luò)知識，這在實(shí)際中限制了該方法的有效性，同時(shí)探測帶來的額外流量也增加了基礎(chǔ)網(wǎng)絡(luò)負(fù)擔(dān)；3)模型的假設(shè)較強(qiáng)，需要增加對于關(guān)聯(lián)故障或多故障情形的適應(yīng)能力。

4.2 多層監(jiān)控方法

在overlay網(wǎng)絡(luò)中，通過測量所有的overlay節(jié)點(diǎn)對之間的路徑來監(jiān)控所有overlay網(wǎng)絡(luò)鏈路是十分笨重且花費(fèi)巨大代價(jià)的。Demirci等[38]提出了多層監(jiān)控方法，監(jiān)控部分底層網(wǎng)絡(luò)的鏈路和部分overlay鏈路的狀態(tài)來最小化監(jiān)控overlay網(wǎng)絡(luò)的總花費(fèi)。通過適當(dāng)?shù)亟M合底層鏈路和overlay鏈路可以推出整個(gè)overlay網(wǎng)絡(luò)鏈路的狀態(tài)。

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

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

由于底層網(wǎng)絡(luò)信息對服務(wù)提供商不可見性造成虛擬網(wǎng)服務(wù)故障難以定位，又由于每個(gè)底層網(wǎng)絡(luò)上同時(shí)承載的虛擬網(wǎng)絡(luò)數(shù)量較多，導(dǎo)致癥狀集中包含的癥狀和故障集中包含的故障較多，因此多層監(jiān)控方法的故障診斷性能較低。

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

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

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

4.4 高效的overlay網(wǎng)絡(luò)配置

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

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

2)限制一個(gè)部件上的最大壓力：底層節(jié)點(diǎn)或鏈路由過多overlay節(jié)點(diǎn)或鏈路共享將會帶來擁塞或資源耗盡的風(fēng)險(xiǎn)。

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

圖 7 overlay網(wǎng)絡(luò)的2種可能的配置Fig. 7 Sample topology with two possible placements of an overlay network

綜合這3種思想，配置算法的目標(biāo)是最大化配置質(zhì)量即度量q。算法始于overlay到底層網(wǎng)絡(luò)的隨機(jī)配置，通過作一些較小的調(diào)整來逐漸提高q。這個(gè)方法利用了overlay設(shè)計(jì)的靈活性來最大化overlay網(wǎng)絡(luò)的診斷能力。

4.5 動態(tài)貝葉斯模型

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

1)時(shí)間信息處理。假設(shè)時(shí)間片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最)，終時(shí)合間成片的2期的望模模型型為為

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

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

故障

一

的

系

集

列合可)能，

通

解過釋計(jì)當(dāng)算前假癥設(shè)狀集的合假的設(shè)信集度合

B

H(H

it(it,一So

組

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

4)計(jì)算后驗(yàn)概率和執(zhí)行更新。為了提高動態(tài)環(huán)境下的故障診斷算法性能，在每個(gè)時(shí)間片診斷結(jié)束后，修正每個(gè)時(shí)間窗口內(nèi)的先驗(yàn)故障概率。對于每一個(gè)故障節(jié)點(diǎn)，使用貝葉斯公式計(jì)算其后驗(yàn)概率，利用后驗(yàn)概率和傳播概率，更新當(dāng)前節(jié)點(diǎn)故障的概率，將本次計(jì)算結(jié)果作為下一個(gè)時(shí)間片的先驗(yàn)概率，然后進(jìn)入下一個(gè)時(shí)間片繼續(xù)處理。

使用動態(tài)貝葉斯模型的故障診斷方法面臨的挑戰(zhàn)如下。

1)故障探測中考慮時(shí)間信息處理的動態(tài)貝葉斯模型計(jì)算復(fù)雜度高。使用基于時(shí)間信息處理的動態(tài)貝葉斯模型在時(shí)間片內(nèi)是靜態(tài)貝葉斯網(wǎng)絡(luò)模型。這種方法可以處理各種不同的動態(tài)系統(tǒng)，但是靜態(tài)貝葉斯網(wǎng)絡(luò)模型本身的復(fù)雜度會增加動態(tài)貝葉斯網(wǎng)絡(luò)模型的計(jì)算復(fù)雜度。

2)故障診斷精度不高的問題。在DBN模型中，可以拆分故障節(jié)點(diǎn)為獨(dú)立的簇來減少診斷時(shí)間和進(jìn)行推斷。然而簇的使用降低了故障診斷的精度。

3)網(wǎng)絡(luò)虛擬化的動態(tài)性特點(diǎn)容易造成網(wǎng)絡(luò)模型知識不準(zhǔn)確、網(wǎng)絡(luò)信息傳輸時(shí)噪聲增大等問題，給故障診斷帶來挑戰(zhàn)。

可以看出，現(xiàn)有工作在研究面向高動態(tài)網(wǎng)絡(luò)的故障管理與定位方面充分考慮了狀態(tài)的遷移、故障節(jié)點(diǎn)間的條件獨(dú)立性、網(wǎng)絡(luò)的規(guī)模和時(shí)間復(fù)雜度等方面。然而，過于復(fù)雜的定位技術(shù)在實(shí)際的網(wǎng)絡(luò)管理和故障定位中并不具備通用性，并且已有方法均基于探測到的故障信息和事先收集的癥狀-故障關(guān)系以及假定網(wǎng)絡(luò)狀態(tài)或故障節(jié)點(diǎn)之間是獨(dú)立的，而這些與實(shí)際信息網(wǎng)絡(luò)的狀態(tài)累積(如擁塞導(dǎo)致的故障)和網(wǎng)絡(luò)互聯(lián)(如網(wǎng)絡(luò)中存在的數(shù)據(jù)流)的本質(zhì)有些是不相符的。因此，重新考察與驗(yàn)證狀態(tài)或節(jié)點(diǎn)之間的獨(dú)立性，建立面向?qū)嶋H網(wǎng)絡(luò)的通用故障定位技術(shù)，提高故障定位算法的運(yùn)行速度和準(zhǔn)確性，將成為本研究領(lǐng)域的核心問題。

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

綜合上述分析，現(xiàn)有故障定位技術(shù)相關(guān)研究的不足和亟待進(jìn)一步研究解決的問題如下。

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

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

3)現(xiàn)有的故障定位中的獨(dú)立性假設(shè)較強(qiáng)，設(shè)計(jì)面向不同定位需求的通用故障定位算法仍然充滿挑戰(zhàn)。近年來，雖然已經(jīng)出現(xiàn)了多種近似的解決方案，但權(quán)衡網(wǎng)絡(luò)故障診斷準(zhǔn)確性和網(wǎng)絡(luò)控制開銷仍然是一個(gè)挑戰(zhàn)性的問題。目前為止，還沒有直接的證據(jù)證明網(wǎng)絡(luò)狀態(tài)前后之間或故障節(jié)點(diǎn)之間的獨(dú)立性假設(shè)的合理性，更沒有建立面向?qū)嶋H網(wǎng)絡(luò)的通用故障定位技術(shù)。同時(shí)針對不同的業(yè)務(wù)需求，需要進(jìn)一步降低概率推理近似算法的復(fù)雜度，提高故障定位算法的運(yùn)行速度和準(zhǔn)確性仍舊充滿挑戰(zhàn)。

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

6 結(jié)束語

本文總結(jié)和研究了多層信息網(wǎng)絡(luò)的定位問題，從故障定位模型、信息獲取方式、故障定位計(jì)算、網(wǎng)絡(luò)異構(gòu)性、運(yùn)行效率與成本等方面入手，充分研究了多層網(wǎng)絡(luò)故障定位方法，分析了各種方法的優(yōu)缺點(diǎn)。最后，對現(xiàn)有故障定位方法相關(guān)研究的不足和亟待進(jìn)一步研究解決的問題進(jìn)行了總結(jié)，并指出了未來的研究方向。