基于反饋機制的自愈算法

趙季紅 ，曲樺，陳文東

(1. 西安交通大學(xué) 電子與信息工程學(xué)院，陜西 西安 710049;

2. 西安郵電學(xué)院 通信與信息工程學(xué)院，陜西 西安 710061)

1 引言

隨著通信網(wǎng)絡(luò)寬帶化進程的逐步深入，業(yè)務(wù)類型的日漸豐富，網(wǎng)絡(luò)的生存性問題成為研究的熱點。故障恢復(fù)是網(wǎng)絡(luò)生存性研究的重要組成部分[1,2]，而自愈作為一種智能化的故障恢復(fù)技術(shù)，其研究也成為了一種趨勢。

自愈通常是指網(wǎng)絡(luò)在發(fā)生故障的情況下，不需要人工干預(yù)，能很快地、自發(fā)地恢復(fù)受影響的業(yè)務(wù)[3]。這就要求網(wǎng)絡(luò)設(shè)備具備更強的計算和存儲能力。自愈的基本原理是在節(jié)點檢測到故障之后，立即通知源節(jié)點重新選擇一條路徑，即在邊緣節(jié)點之間建立另外一條能夠滿足業(yè)務(wù)傳輸需求的路徑，將受影響的流量切換到這條備份路徑上去，從而保證業(yè)務(wù)的連續(xù)傳輸。

自愈的研究現(xiàn)狀主要集中于2個方面：故障檢測和故障恢復(fù)。故障檢測旨在感知并且定位網(wǎng)絡(luò)故障[4]。當(dāng)網(wǎng)絡(luò)中檢測到故障之后，故障恢復(fù)機制開始運作。故障恢復(fù)旨在將故障路徑上的流量切換到另一條可承載這些流量的健康路徑上，減少由于故障對業(yè)務(wù)傳輸所造成的影響。

目前故障檢測主要有 RSVP軟狀態(tài)、RSVP HELLO、LSP PING/Traceroute[5]以及 BFD[6]等技術(shù)。這幾種技術(shù)所花費的檢測時間較長，意味著在故障發(fā)生到故障被檢測期間，將有大量的數(shù)據(jù)丟失。故障恢復(fù)的研究主要集中于2種機制：保護交換和重路由。保護交換的前提是為可能的故障路徑提前找到一條備份路徑。當(dāng)故障發(fā)生后，將流量切換到備份路徑上保證業(yè)務(wù)的傳輸。這種機制的主要問題是備份路徑會占用大量的網(wǎng)絡(luò)資源，造成資源的利用率偏低[7]。重路由主要有2個思路，靜態(tài)路由和在線路由。靜態(tài)路由將網(wǎng)絡(luò)在很長一段時間的平均流量作為網(wǎng)絡(luò)的當(dāng)前流量信息，在這個基礎(chǔ)上計算路由。這種方法簡單卻精度較差。目前，靜態(tài)路由主要有最寬最短路徑（WSP）算法[8]、最大可預(yù)留帶寬（MRB）算法[9]。在線路由則基于當(dāng)前網(wǎng)絡(luò)的狀態(tài)信息，計算并選擇最小可能出現(xiàn)擁塞的路徑傳輸業(yè)務(wù)，網(wǎng)絡(luò)狀態(tài)信息更新的即時性和準確性很大程度上決定了算法的性能。目前，在線路由主要包括最小沖突路由算法（MIRA）[10]、動態(tài)在線路由算法（DORA）[11]、最小沖突優(yōu)化算法（LIOA）[12]等。重路由對于新路徑的建立依賴于故障信息、網(wǎng)絡(luò)路由的策略、預(yù)定義設(shè)置以及網(wǎng)絡(luò)當(dāng)前的狀態(tài)信息，利用這些信息的路由算法，其收斂時間得不到保證，導(dǎo)致故障恢復(fù)時間不能滿足業(yè)務(wù)的QoS傳輸。

根據(jù)上述分析，自愈技術(shù)的研究仍有許多問題亟待解決。第一，自愈以故障檢測為前提，對故障檢測結(jié)果的依賴程度過高。首先，自愈算法的觸發(fā)是在故障檢測之后進行的，當(dāng)網(wǎng)絡(luò)發(fā)生故障后，只有該故障被感知并且被定位之后才能觸發(fā)自愈算法，因此自愈算法需要等待故障檢測所需的時間。其次，如果故障未被成功檢測，那么自愈算法就不能被觸發(fā)，從而導(dǎo)致故障恢復(fù)失敗。第二，自愈進行重路由計算的時間過長，其收斂的時間很難符合業(yè)務(wù)傳輸質(zhì)量的要求。而且基于QoS約束重路由計算需要隨時掌握當(dāng)前網(wǎng)絡(luò)狀態(tài)信息，這些信息的收集往往通過泛洪的方式，會造成一定的資源浪費。

針對上述問題，本文提出了一種基于反饋機制的自愈算法。該算法通過引入Q學(xué)習(xí)的反饋機制，可以感知網(wǎng)絡(luò)當(dāng)前的狀態(tài)信息，也可以感知到路徑發(fā)生故障或者擁塞的情況，這樣大大降低了自愈對于故障檢測的依賴程度，不必對故障進行精確地定位，只需要模糊的感知故障或擁塞，自愈就可以啟動。另一方面，該算法可以通過業(yè)務(wù)的傳輸收集路徑的信息（時延、帶寬等），通過對這些信息的學(xué)習(xí)，可以獲得學(xué)習(xí)“經(jīng)驗”并作為重路由選擇的依據(jù)，避免了繁雜的重路由計算過程，降低了重路由所需的時間。同時，該算法引入了多 QoS參數(shù)約束評價函數(shù)的路由計算以及Boltzmann-Gibbs分布的路徑選擇策略，使算法具備了區(qū)分業(yè)務(wù)能力以及網(wǎng)絡(luò)資源優(yōu)化能力。

本文首先介紹了算法設(shè)計中的幾個基本概念，然后詳細介紹了算法應(yīng)用于網(wǎng)絡(luò)中的網(wǎng)絡(luò)模型、算法的數(shù)學(xué)模型以及算法實現(xiàn)的具體流程和步驟。最后，用 MATLAB對該算法進行了仿真，并對算法的性能進行了討論。

2 算法設(shè)計中的基本概念

2.1 反饋機制

本文的研究旨在通過引入機器學(xué)習(xí)理論改善目前傳統(tǒng)自愈機制缺乏對于網(wǎng)絡(luò)環(huán)境的學(xué)習(xí)能力的狀況，提高自愈機制的智能性。機器學(xué)習(xí)理論中的學(xué)習(xí)策略很多，比如類比學(xué)習(xí)、歸納學(xué)習(xí)、支持向量機和強化學(xué)習(xí)等，其中強化學(xué)習(xí)源于心理學(xué)中的“試錯法”，通過不斷與環(huán)境交互來改善策略最終找到適合環(huán)境的最優(yōu)策略，這種與環(huán)境交互的思想可以應(yīng)用到網(wǎng)絡(luò)中實現(xiàn)對網(wǎng)絡(luò)環(huán)境的學(xué)習(xí)。

本文中提出的算法通過引入強化學(xué)習(xí)理論中的Q學(xué)習(xí)[13]反饋機制來感知網(wǎng)絡(luò)當(dāng)前狀態(tài)的變化，一定程度上緩解了傳統(tǒng)自愈機制對于故障檢測技術(shù)依賴程度過高的問題。同時，利用反饋機制可以降低在線路由計算中由于泛洪流量對網(wǎng)絡(luò)資源的浪費。反饋機制原理如圖1所示。

圖1 基于Q學(xué)習(xí)的反饋機制

圖1 中，當(dāng)每個業(yè)務(wù)傳輸結(jié)束的時候，目的節(jié)點Egress會將該業(yè)務(wù)傳輸路徑的狀態(tài)信息反饋給源節(jié)點Ingress。Ingress通過這個反饋回來的狀態(tài)信息感知該路徑的承載能力。反饋回來的狀態(tài)信息本質(zhì)上是業(yè)務(wù)傳輸完成后學(xué)習(xí)到的“經(jīng)驗”。這樣就可以避免每次重路由時重新計算新的路徑，而是直接利用先前的“經(jīng)驗”自適應(yīng)地選擇合適的備份路徑，從路由重計算到路由重查表，可以大大節(jié)省不必要的計算負擔(dān)。

考慮到可以人為定義反映網(wǎng)絡(luò)狀態(tài)信息的評價函數(shù)，那么可以把其定義為一個數(shù)值。這樣反饋流量占用的帶寬和傳輸產(chǎn)生的時延可以忽略不記。因此，這種反饋機制較傳統(tǒng)的泛洪廣播網(wǎng)絡(luò)狀態(tài)信息的方式更加簡單，而且能夠有效減少網(wǎng)絡(luò)中不必要的泛洪流量。

綜上所述，通過反饋機制，Ingress節(jié)點依靠感知當(dāng)前網(wǎng)絡(luò)狀態(tài)并且積累學(xué)習(xí)“經(jīng)驗”來選擇路徑，在很大程度上降低自愈機制對故障檢測的依賴程度，同時提高了網(wǎng)絡(luò)資源利用率。

2.2 業(yè)務(wù)分類

網(wǎng)絡(luò)中的有些業(yè)務(wù)對實時性的要求較高，必須滿足其實時傳輸，才能保證業(yè)務(wù)的服務(wù)質(zhì)量（QoS）；而有些業(yè)務(wù)對網(wǎng)絡(luò)的吞吐量和分組丟失率的要求較高，只有足夠大的吞吐量和足夠低的分組丟失率才能保證業(yè)務(wù)的服務(wù)質(zhì)量；還有一些業(yè)務(wù)對網(wǎng)絡(luò)的要求不高，采用傳統(tǒng)“盡力而為”服務(wù)即可，這類業(yè)務(wù)應(yīng)該盡量少地占用網(wǎng)絡(luò)資源。

為了合理地利用有限的網(wǎng)絡(luò)資源，本文提出的算法的路由策略會依據(jù)不同業(yè)務(wù)類型選擇適合其傳輸需求的最優(yōu)路徑。在本文中，將業(yè)務(wù)分成3種類型：EF業(yè)務(wù)、AF業(yè)務(wù)和BE業(yè)務(wù)。EF業(yè)務(wù)為加速轉(zhuǎn)發(fā)業(yè)務(wù)，AF業(yè)務(wù)為確保轉(zhuǎn)發(fā)業(yè)務(wù)，BE業(yè)務(wù)為盡力而為轉(zhuǎn)發(fā)業(yè)務(wù)。3種業(yè)務(wù)對于QoS參數(shù)的要求參見表1。

表1 不同業(yè)務(wù)類型對QoS參數(shù)的要求

2.3 多QoS約束評價函數(shù)

一些自愈技術(shù)在尋找備份路徑進行故障恢復(fù)的時候只考慮單一因素的約束，這樣帶來的問題是選擇的路徑不一定能夠充分地滿足業(yè)務(wù)傳輸?shù)腝oS需求，因為保證業(yè)務(wù)QoS傳輸需要考慮的參數(shù)很多，只滿足其中一個不一定能達到傳輸?shù)囊?。因此，本文提出的算法引入多QoS參數(shù)的約束，這樣反饋的評價函數(shù)所包含的網(wǎng)絡(luò)狀態(tài)信息會更加全面。

本文中，選取3種常用的QoS參數(shù)作為約束集合：吞吐量（TH）、端到端時延（delay）和分組丟失率（P）。這些參數(shù)都體現(xiàn)的是路徑端到端的性能，綜合考慮這些約束因素選擇出來的路徑就會融入這些約束信息，使路徑的選擇更加科學(xué)和可靠，更能滿足業(yè)務(wù)的QoS傳輸需求。很明顯，EF、AF業(yè)務(wù)的優(yōu)先級和重要性要遠遠高于BE業(yè)務(wù)，因此希望 BE業(yè)務(wù)盡量少地占用網(wǎng)絡(luò)中的節(jié)點和鏈路資源。使用U表示路徑對網(wǎng)絡(luò)節(jié)點和鏈路資源的利用率，U=Npath/ Nall，其中，Npath表示一條路徑使用的節(jié)點數(shù)，Nall表示網(wǎng)絡(luò)中節(jié)點個數(shù)總和。那么，約束集合C={TH, delay, P, U}。

評價函數(shù)為約束集合C的函數(shù)，即f(C)。評價函數(shù)的大小就體現(xiàn)了網(wǎng)絡(luò)中路徑的端到端的承載能力的好壞。其值越大，說明該路徑當(dāng)前的承載能力越強。

2.4 資源優(yōu)化

靜態(tài)路由算法通常會使業(yè)務(wù)集中于一條基于某種準則的“最優(yōu)”路徑。當(dāng)網(wǎng)絡(luò)中負載較大時，會產(chǎn)生路徑擁塞，這就需要全局服務(wù)器對流量進行控制來解決這一問題。在本文中，源節(jié)點 Ingress可以得到評價函數(shù)提供的信息，因此可以感知到網(wǎng)絡(luò)當(dāng)前各條路徑的負載情況，從而避免選擇負載較大的路徑進行業(yè)務(wù)的傳輸。但網(wǎng)絡(luò)中的負載情況是隨著時間變化而變化的，這就需要算法對網(wǎng)絡(luò)狀態(tài)信息的動態(tài)感知。本文中，源節(jié)點具有動態(tài)感知網(wǎng)絡(luò)狀態(tài)信息的能力，從而能夠依據(jù)路徑選擇策略自適應(yīng)地選擇路徑，使網(wǎng)絡(luò)負載均衡，實現(xiàn)網(wǎng)絡(luò)資源的優(yōu)化。

3 基于反饋機制的自愈算法

基于反饋機制的自愈算法以強化學(xué)習(xí)中的 Q學(xué)習(xí)算法作為理論基礎(chǔ)，應(yīng)用于網(wǎng)絡(luò)中以增強自愈機制的學(xué)習(xí)能力，提高自愈機制對于網(wǎng)絡(luò)環(huán)境的感知力，實現(xiàn)網(wǎng)絡(luò)的智能化控制。

3.1 數(shù)學(xué)模型

本文中反饋機制的實現(xiàn)是基于強化學(xué)習(xí)理論中的Q學(xué)習(xí)算法。Q學(xué)習(xí)就是要在系統(tǒng)動力學(xué)特性未知的情況下估計最優(yōu)策略的Q值，詳見文獻[13]。在線Q學(xué)習(xí)方法的實現(xiàn)是按遞歸公式(3)進行的：在每個時間步 t，觀察當(dāng)前狀態(tài) St，選擇和執(zhí)行動作At，再觀察后續(xù)狀態(tài) St+1并接受立即回報Rt，然后根據(jù)式(3)來調(diào)整Q值。

式(1)中，α為學(xué)習(xí)率，它控制著學(xué)習(xí)的速度，α越大則收斂越快。但是過大的α可能導(dǎo)致不收斂。Watkins證明了α在滿足一定條件時，如果任一個二元組(St,At)能用方程(1)進行無窮多次迭代，則當(dāng) t趨于無窮時，Qt(St,At)以概率1收斂到關(guān)于最優(yōu)策略的Q*(St,At)[13]。

根據(jù)多 QoS參數(shù)約束的需要，定義立即回報Reward為多 QoS約束的評價函數(shù)以滿足業(yè)務(wù)的QoS需求。從上文可知，Reward是約束集C的函數(shù)。令 R={R1, R2, … , Rm}表示每個行動對應(yīng)的Reward的集合。定義

式(2)中ω1、ω2、ω3和ω4為權(quán)系數(shù)。調(diào)整權(quán)系數(shù)的大小可以體現(xiàn)出不同類型業(yè)務(wù)（EF業(yè)務(wù)、AF業(yè)務(wù)和BE業(yè)務(wù)）的需求。

Q學(xué)習(xí)算法中， Agent面臨的一個問題是如果選擇下一個動作，通常需要考慮2方面的因素。其一是Agent必須對狀態(tài)動作空間做充分的探索從而能夠找出最優(yōu)或近最優(yōu)的策略。另一方面是利用通過學(xué)習(xí)已獲得的經(jīng)驗進行動作選擇，從而使學(xué)習(xí)的成本降低?？梢圆捎眠B續(xù)可微且近似貪婪的Boltzmann-Gibbs分布[14]作為動作選取策略，動作Ak被選取的概率為

式(3)中，Tt(＞0)為溫度參數(shù)，控制行為選取的隨機程度。為了提高學(xué)習(xí)的速度，利用模擬退火技術(shù)在學(xué)習(xí)過程中按式(4)進行動態(tài)調(diào)整溫度值，即在學(xué)習(xí)的初期選擇較大的溫度，以保證動作選取的隨機性較大，增加搜索能力，然后在學(xué)習(xí)的過程中逐漸降低溫度，保證以前的學(xué)習(xí)效果不被破壞[14]。

式(4)中, β 為退火因子，并且 0＜β ＜1。

3.2 網(wǎng)絡(luò)模型

本文提出的基于反饋機制的自愈算法可以應(yīng)用在任何Mesh網(wǎng)絡(luò)中。本文將以MPLS網(wǎng)絡(luò)作為應(yīng)用場景對算法的實現(xiàn)進行詳細地研究。

將MPLS網(wǎng)絡(luò)的拓撲抽象為G(V,E)，V代表網(wǎng)絡(luò)中的節(jié)點（路由器），E代表網(wǎng)絡(luò)中的鏈路。令S={S1, S2,… , Sn}表示MPLS網(wǎng)絡(luò)環(huán)境中的邊緣節(jié)點的集合（邊緣路由器LER或者自治域范圍內(nèi)的邊緣標(biāo)簽交換路由器LSR），Si∈V。假設(shè)S1為業(yè)務(wù)傳輸源節(jié)點，那么選擇S1作為Q學(xué)習(xí)Agent，潛在的目的節(jié)點集合S’={S2, … , Sn}即作為Q學(xué)習(xí)中的環(huán)境狀態(tài)集，顯然S’為有限集。源節(jié)點與目的節(jié)點之間所有可能的傳輸路徑集合為 A={A1, A2, … ,Am}，A即為Q學(xué)習(xí)Agent可以采取的行動集合，即是MPLS網(wǎng)絡(luò)的標(biāo)簽交換路徑（LSP）。Agent每采取一次行動，即每選擇一條路徑，都會產(chǎn)生一個與這次行動相對應(yīng)的回報 Reward（式（2））反饋給源節(jié)點，然后根據(jù)式(1)更新此次業(yè)務(wù)傳輸之后對應(yīng)路徑的Qt(Si,Aj) 值，Si表示業(yè)務(wù)傳輸?shù)哪康墓?jié)點；Aj表示業(yè)務(wù)到達Si的傳輸路徑。網(wǎng)絡(luò)模型如圖2所示。

圖2 Q學(xué)習(xí)在MPLS網(wǎng)絡(luò)中的應(yīng)用模型

Qt(Si,Aj)值大小決定了選擇路徑 Aj到目標(biāo)節(jié)點 Si的“傾向”。將所有 Q值建立起來的矩陣Qt(Si,Aj)（i∈[1,n]，j∈[1,m]） 定義為 Q 表格，表示業(yè)務(wù)的路由信息。S1節(jié)點中儲存的Q表格如表2所示。

表2 Q表格

當(dāng)業(yè)務(wù)傳輸結(jié)束并反饋Reward更新Q表格信息之后，就可以以式(3)作為路徑選取策略來選擇新業(yè)務(wù)的傳輸路徑，更新后的 Q表格融入了反饋信息，因此具備網(wǎng)絡(luò)狀態(tài)的感知能力，同樣也具備了故障的感知能力。

3.3 算法流程

算法的實現(xiàn)流程如圖3所示。

具體實現(xiàn)步驟如下。

step1 當(dāng)業(yè)務(wù)從源節(jié)點接入后，判斷業(yè)務(wù)的類型。

step2 源節(jié)點根據(jù)業(yè)務(wù)的類型查詢相應(yīng)的路徑優(yōu)先級表格（EF業(yè)務(wù)Q表格、AF業(yè)務(wù)Q表格和BE業(yè)務(wù)Q表格）。

step3 依據(jù)基于Boltzmann-Gibbs分布的路徑選擇策略（式(3)）得到業(yè)務(wù)的傳輸路徑Ai。

step4 在業(yè)務(wù)傳輸過程中經(jīng)過鏈路時，記錄鏈路的吞吐量和時延信息。

step5 在業(yè)務(wù)到達目的節(jié)點后，將所得到的路徑信息進行整合，計算出路徑吞吐量、路徑時延以及業(yè)務(wù)數(shù)據(jù)的分組丟失率，根據(jù)式(2)計算得到此次業(yè)務(wù)傳輸?shù)腞eward，并反饋給源節(jié)點。

圖3 算法的實現(xiàn)流程

step6 利用 Q 學(xué)習(xí)算法（式（1））得到更新后的Q值，從而對路徑的優(yōu)先級信息進行更新。新業(yè)務(wù)到來時便查詢更新后的相應(yīng)業(yè)務(wù)的Q表格，重復(fù)如上的步驟找到傳輸路徑。

在本文中，業(yè)務(wù)的傳輸需要考慮2種情況，一種是業(yè)務(wù)傳輸成功的情況，一種是業(yè)務(wù)傳輸失敗的情況。在第1種情況下，對算法收斂速度的要求不能過高，因為過快地收斂可能導(dǎo)致較大的擾動，學(xué)習(xí)的精確性不能得到很好地保證。在第2種情況下，業(yè)務(wù)傳輸失敗很可能是由于鏈路或者節(jié)點出現(xiàn)故障造成的，對于這種情況，希望算法能對其進行較快地學(xué)習(xí)，因此希望收斂速度快。這2種情況可以通過使用不同的學(xué)習(xí)率α實現(xiàn)。算法可用下面的偽代碼表示。

算法1 基于反饋機制的自愈算法

對于任意源節(jié)點Si∈S；

初始化 Qi(Sj,Ak)，其中，Sj為目的節(jié)點，Ak為選擇的路徑，在所有 Ak中，取最少跳數(shù)路徑的Qi(Sj,Ak)為1，其余值為0；

根據(jù)式(3)的隨機分布選擇路徑，假設(shè)選擇路徑Am；

根據(jù)式(2)，計算相應(yīng)的Reward函數(shù)；

如果業(yè)務(wù)傳輸成功，依據(jù)下式更新Q表格：

如果業(yè)務(wù)傳輸失敗，依據(jù)下式更新Q表格：

4 仿真與性能分析

本節(jié)將對算法進行仿真并依據(jù)仿真結(jié)果分析算法各方面的性能。需要特別說明的是本文提出的算法改變了傳統(tǒng)的自愈機制的以故障檢測為前提的故障恢復(fù)模式，而是利用Q學(xué)習(xí)反饋機制的故障感知能力先于定位故障提前響應(yīng)故障，因此缺少同類的自愈機制進行比較。在仿真中，將采用無反饋的靜態(tài)自愈機制說明基于反饋的自愈機制對于網(wǎng)絡(luò)環(huán)境的學(xué)習(xí)能力的改善。

4.1 網(wǎng)絡(luò)參數(shù)設(shè)置

仿真中的網(wǎng)絡(luò)拓撲如圖 4所示。其中，LSR1為源節(jié)點，同時也是Q學(xué)習(xí)Agent。LSR15為目的節(jié)點，Reward將從這個節(jié)點反饋到LSR1以更新Q表格。

圖4 網(wǎng)絡(luò)拓撲（LSR12為故障場景中的故障節(jié)點）

LSR1和LSR15之間有22條可用傳輸路徑，路徑信息參見表 3。其中，對路徑的約束參數(shù)包括路徑吞吐量（Mbit/s）、路徑時延（ms）和路徑節(jié)點數(shù)。在仿真中，路徑的分組丟失率與路徑剩余帶寬之間呈指數(shù)關(guān)系。

表3 仿真參數(shù)設(shè)置

表3中，靜態(tài)路徑選擇指的是靜態(tài)路由算法中3種業(yè)務(wù)可以選擇的路徑。EF業(yè)務(wù)選擇的路徑為1、2、4、5、12、20、21和 22；AF業(yè)務(wù)選擇的路徑為 1、3、7、10、11、17、20、21和 22；BE 業(yè)務(wù)可以選擇所有路徑。靜態(tài)算法沒有引入反饋機制，作為與本文提出算法的對比算法。

在仿真中，設(shè)置LSR12為可能發(fā)生故障的節(jié)點。從表3中可以看出，如果LSR12發(fā)生故障，受影響的路徑有1、5、9、13、18和19。仿真中還加入了鏈路擁塞的情況，為了便于觀察，設(shè)置路徑22為可能發(fā)生擁塞的路徑。因此，仿真中包括3種場景，分別為無故障場景、LSR12故障場景和路徑22擁塞場景。

在仿真中，需要在網(wǎng)絡(luò)負載大小變化條件下討論算法性能，因此，對網(wǎng)絡(luò)負載定義如下 10個等級，如表4所示。等級越高，表明網(wǎng)絡(luò)負載越大。

表4 負載級別定義

4.2 性能分析

4.2.1 故障感知

本文中提出的算法通過業(yè)務(wù)傳輸之后評價函數(shù)的反饋機制感知網(wǎng)絡(luò)當(dāng)前的狀態(tài)信息。因此，該算法具備故障感知的能力。令

φ 越小說明算法感知故障的能力越強；反之，算法感知故障的能力就越弱。仿真結(jié)果如圖5所示。圖5(b)反映了本文提出的算法對故障感知的性能，圖5(a)反映了沒有加入反饋機制的靜態(tài)路由算法對故障感知的性能。從仿真結(jié)果可以看出，基于反饋機制的算法在故障感知性能上表現(xiàn)出了一定的優(yōu)勢。

圖5 故障感知性能

4.2.2 故障恢復(fù)

在本文算法的自愈機制中，如果EF業(yè)務(wù)或者AF業(yè)務(wù)傳輸失敗時，即選擇了故障路徑時，源節(jié)點會重新選擇路徑傳輸業(yè)務(wù)。如果重新選擇的路徑不能滿足業(yè)務(wù)傳輸?shù)腝oS或者仍然選擇了故障路徑，則認為業(yè)務(wù)恢復(fù)失敗，即沒有找到合適的備份路徑保證業(yè)務(wù)的傳輸；如果重新選擇的路徑可以滿足業(yè)務(wù)的 QoS，并且不是故障路徑，則認為業(yè)務(wù)恢復(fù)成功，即找到了一條合適的備份路徑保證業(yè)務(wù)的傳輸。因此，業(yè)務(wù)恢復(fù)失敗率可以表示為

仿真結(jié)果如圖6所示。

圖6 故障恢復(fù)性能

4.2.3 區(qū)分業(yè)務(wù)

圖7從業(yè)務(wù)平均時延、路徑平均剩余帶寬和業(yè)務(wù)平均分組丟失率 3個方面說明了算法對于 EF、AF和BE業(yè)務(wù)的區(qū)分能力。

從圖 7(a)中可以明顯看出，EF業(yè)務(wù)的平均時延最小，AF業(yè)務(wù)次之，BE業(yè)務(wù)最大。這說明，算法對于EF業(yè)務(wù)，更傾向于選擇時延小的路徑保證業(yè)務(wù)的實時傳輸，而AF業(yè)務(wù)和BE業(yè)務(wù)的時延保證則相對較差。從圖 7(b)中可以明顯看出，AF業(yè)務(wù)選擇路徑的平均剩余帶寬最大，EF業(yè)務(wù)次之，BE業(yè)務(wù)最小。算法對于AF業(yè)務(wù)，更傾向于選擇吞吐量大的路徑保證業(yè)務(wù)的傳輸，而對EF業(yè)務(wù)和BE業(yè)務(wù)，則這方面的保證相對較差。從圖7(c)中可以明顯看出，AF業(yè)務(wù)的平均分組丟失率最小，EF業(yè)務(wù)次之，BE業(yè)務(wù)最大。這說明，算法對于AF業(yè)務(wù)和EF業(yè)務(wù)，更傾向于選擇分組丟失率小的路徑保證業(yè)務(wù)的傳輸，而對BE業(yè)務(wù)的分組丟失率保證相對較差。

圖7 區(qū)分業(yè)務(wù)性能

圖7 的結(jié)果說明算法對EF、AF和BE 3種業(yè)務(wù)進行了區(qū)分服務(wù)，在有限的網(wǎng)絡(luò)資源條件下，滿足了EF業(yè)務(wù)和AF業(yè)務(wù)的傳輸需求。

4.2.4 網(wǎng)絡(luò)資源優(yōu)化

本文提出的算法通過反饋機制可以感知路徑的剩余帶寬，在源節(jié)點選擇路徑時，會根據(jù)剩余帶寬情況動態(tài)進行路徑的分配。因此，網(wǎng)絡(luò)中流量會比較均衡。而靜態(tài)路由算法由于沒有引入反饋機制，缺少對路徑剩余帶寬的感知能力，因此在選路時，不會考慮到網(wǎng)絡(luò)的負載情況，只根據(jù)靜態(tài)路由表進行路由。因此，各路徑的負載情況不一定會均衡，網(wǎng)絡(luò)資源利用率偏低。將圖8(a)和圖8(b)進行比較，可以明顯看出，基于反饋機制的自愈算法可以使網(wǎng)絡(luò)中各路徑的負載均衡化，具有網(wǎng)絡(luò)資源優(yōu)化的能力，在圖中顯示的效果是路徑剩余帶寬平面比較平滑，而靜態(tài)路由算法中的路徑剩余帶寬平面就顯得凹凸不平。

圖8 資源優(yōu)化性能

4.2.5 學(xué)習(xí)率α1、α2對算法性能的影響

在本文中，α1為業(yè)務(wù)傳輸成功時的學(xué)習(xí)率，α2為業(yè)務(wù)傳輸失敗時的學(xué)習(xí)率。學(xué)習(xí)率越大，則算法收斂速度越快，但抖動也越大，而且如果學(xué)習(xí)率過大，還有可能導(dǎo)致算法不收斂。分別選取AF業(yè)務(wù)在故障路徑17和擁塞路徑22上的Q值變化曲線說明學(xué)習(xí)率對算法性能的影響，如圖 9所示。

圖9 學(xué)習(xí)率α1、α2對算法性能的影響

在仿真進行到1/4時，故障發(fā)生，路徑17中斷，所以此時影響算法收斂速度的學(xué)習(xí)率為α2；當(dāng)仿真進行到3/4時，故障結(jié)束，路徑17恢復(fù)，所以影響算法收斂速度的學(xué)習(xí)率變?yōu)棣?。從圖9(a)中可以看出，在故障發(fā)生時，當(dāng)學(xué)習(xí)率較大時，收斂速度較快，但有一定的抖動。從圖9(b)中可以看出，在擁塞發(fā)生的時候，較大的α1對應(yīng)曲線的收斂速度較快，但抖動較大。

5 結(jié)束語

本文提出了一種基于反饋機制的自愈算法。利用Q學(xué)習(xí)的反饋機制，降低了傳統(tǒng)自愈機制對故障檢測的依賴程度，在一定程度上提高了算法對于故障感知的靈敏度，從而提高了故障恢復(fù)率。算法利用多QoS約束的評價函數(shù)，對于不同類型業(yè)務(wù)查詢不同的Q表格從而使其具備區(qū)分業(yè)務(wù)的能力，同時，通過對網(wǎng)絡(luò)狀態(tài)信息的反饋以及基于Boltzmann-Gibbs分布的路徑選擇策略也在一定程度提高了網(wǎng)絡(luò)資源的利用率，達到了網(wǎng)絡(luò)資源優(yōu)化的目的。

[1] IETF RFC 3469. Framework for Multi-Protocol Label Switching(MPLS)-based Recovery[S]. 2003.

[2] JORGE L, GOMES T. Survey of recovery schemes in MPLS networks[A]. 2006 International Conference on Dependability of Computer Systems[C]. Szklarska Poreba, Poland, 2006.

[3] YIJUN X, MASON L G. Restoration strategies and spare capacity requirements in self-healing ATM networks[J]. IEEE/ACM Transactions on Networking, 1999, 7(1): 98-110.

[4] CAVENDISH D, OHTA H, RAKOTORANTO H. Operation, administration, and maintenance in MPLS Networks[A]. IEEE Communications Magazine[C]. 2004. 91-99.

[5] IETF RFC 4379. Detecting Multi-protocol Label Switched (MPLS)Data Plane Failures[S]. 2006.

[6] IETF DRAFT. Bidirectional Fowarding Detection[S]. 2007.

[7] IETF RFC 3469. Framework for Multi-Protocol Label Switching(MPLS)-based Recovery[S]. 2003.

[8] GRERIN R, WILLIAMS D, ORDA A. QoS routing mechanisms and OSPF extensions[A]. 1997 Global Telecommunications Conference[C].Phoenix, 1997.

[9] KE Y, COPELAND G A. Scalability of routing advertisement for QoS routing in an IP network with guaranteed QoS[A]. 2000 Global Telecommunications Conference[C]. San Francisco, 2000.

[10] KODIALAM M, LAKSHMAN T. Minimum interference routing with applications to MPLS traffic engineering[A]. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies[C].Tel Aviv, 2000.

[11] SZETO W, BOUTABA R, IRAQI Y, Dynamic online routing algorithm for MPLS traffic engineering[A]. The 9th International Conference on Advanced Communication Technology[C]. Gangwon-Do,Korea, 2007.

[12] BAGULA B, BOTHA M, KRZESINSKI A. Online traffic engineering:the least interference optimization algorithm[A]. 2004 IEEE International Conference on Communications[C]. Paris, France, 2004.

[13] KAELBLING L P, LITTMAN M L, MOORE A W. Reinforcement learning: a survey[J]. Journal of Artificial Intelligence Research, 1996,4(1): 237-285.

[14] SUTTON R S, BARTO A G. Reinforcement Learning: An Introduction[M]. The MIT Press, Cambridge, MA, 1998.