基于可用性的ＱｏＳ選路研究
2009-01-01 00:00:00王宇李樂民
計算機應用研究 2009年5期
（電子科技大學 寬帶光纖傳輸與通信網技術重點實驗室 成都 610054）
摘 要：基于可用性的QoS選路(availabilitybasedQoS routing，AQR)是個復雜的問題。將AQR分為兩類，第一類AQR只需要搜索從源點到終點滿足QoS約束條件的工作路徑；第二類AQR問題除了搜索工作路徑，還需要搜索這個工作路徑的備份路徑。已有文獻對第一類AQR問題研究比較多；對于多約束的第二類AQR問題，則研究得比較少。指出了第二類問題雖然比較復雜，但可以借助于第一類問題的算法經過一些策略而得到解決；該思路可以有效利用已有文獻提出的關于第一類AQR的現成算法，從而解決第二類AQR問題。
關鍵詞：服務質量選路;可用性;基于可用性的服務質量選路
中圖分類號：TP393文獻標志碼：A
文章編號：1001-3695(2009)05-1844-03
QoS routing based on availability
WANG Yu，LI Lemin
(Key Laboratory of Broadband Optical Fiber Transmission Communication Networks University of Electronic Science Technology of China Chengdu 610054 China)
Abstract:AvailabilitybasedQoS routing (shortened as AQR) can be divided into two kinds. The first kind needs only search QoS satisfied working paths from the source nodes to the destination nodes. The second kind needs not only search working paths but also their backup paths. Few published works had studied on the second type of AQR with multiconstraints.This paper pointed out that the problem of the second type could be solved resorting to the solution of the first type with strategies.
Key words:QoS routing;availability;AQR
0 引言
Internet深入到了人們的工作、生活和學習之中，對工作和生活產生了深遠而重要的影響。傳統的Web應用有網上沖浪、電子郵件、FTP等，它們提供“盡力傳送(best effort BE)”的服務。但隨著Internet的發展，如IP電話、網絡會議、電子商務等業務的出現，要求網絡中實時地傳輸音頻和視頻數據，這使得BE服務不能滿足要求，于是就產生了服務質量(quality of service，QoS)的要求。
QoS指IP分組流通過一個或多個網絡時所表現出來的性能屬性，它主要為用戶業務提供端到端的服務質量保證，通常可以用一組可度量的業務參數來描述。這些參數即QoS參數，包括可用性、延遲、延遲抖動、帶寬等。許多文獻在QoS領域內做了富有成效的工作，提出了對于解決QoS問題有幫助的模型、協議和算法，包括集成服務(IntServ/RSVP)模型、區分服務(DiffServ)模型、多協議標簽交換(MPLS)、流量工程(traffic engineering)、QoS選路(QoSR)等。其中，QoS選路是個熱點并且是實現網絡支持QoS的關鍵技術之一。
QoS選路問題就是對網絡和業務的QoS性能進行優化，在盡量減少資源消耗的基礎上，合理分配網絡的流量負荷，減少阻塞概率，同時有利于系統接入更多的業務。 如果路由參數是兩個或多個加性、乘性QoS參數，則這類路由問題屬于NP完全問題，用傳統的窮舉算法不能滿意地解決問題，尤其是當網絡規模很大時[1]。
總的說來，QoS選路有兩種情況：a）只需所選目標路徑滿足若干QoS約束要求；b）所選目標路徑除了要滿足若干QoS約束要求，還有優化QoS約束的要求。前者為多約束路徑問題（multiconstraints path problem，MCP[2]）；后者為多約束優化路徑問題（multiconstraints optimal path problem，MCOP[3]）。對于MCP或MCOP，如果選路時考慮的QoS參數個數只有一個，則問題是可解的。
QoS參數有三種類型，即凹性參數、加性參數和乘性參數。凹性參數在有的文獻中也被稱為瓶頸性參數。帶寬是凹性參數；延遲、抖動、成本和跳數為加性參數；丟失率為乘性參數。
可用性[4~6]是一類比較特殊的QoS參數。可用性的含義就是在未來某一時刻，某設備或系統能提供服務的可能性。在QoS選路問題中，可用性的含義即是從源點到終點的連接在未來某一時刻仍然保持有效的可能性。對于一個選路問題，如果只考慮尋找從源點到終點的QoS工作路徑，并且可用性是其中的一個QoS約束參數，則該問題就是一般情況下的帶乘性參數的QoS選路問題。如果在選路時要提高連接的可用性而考慮保護，即尋找工作路徑的備份路徑，則該種情況將變得更復雜。
提高連接可用性的保護方法有兩種，即專有路徑保護(dedicated path protection DPP)和共享路徑保護(shared backup path protection SBPP)。在研究可用性時，文獻中通常的辦法是把這兩種方法獨立考慮。在一個網絡中，是可以同時存在DPP和SBPP兩種情況的。可以對工作路徑進行全路徑保護或部分鏈路保護。備份路徑可以與工作路徑共享部分鏈路，或與工作路徑的鏈路完全獨立。
現有文獻對可用性或者QoS選路都有各自豐富的研究；而對基于可用性的QoS選路問題研究的文獻就相對少些。由于可用性問題和QoS選路問題的復雜性，基于可用性的QoS選路問題也將更復雜。但是由于人們對一般的QoS選路問題研究較多，基于可用性的QoS選路是可以借鑒一般QoS選路方法的。
文獻[4]中，在進行可用性改進時，作者依靠的是源點到終點可用性最高的路徑。他們首先使用Kshortest算法找到源點到終點的路徑集；如果在路徑里的所有路徑皆不滿足可用性要求，他們綜合考慮了帶寬與可用性的組合，并使用Dijkstra算法求最短路徑法得到備份路徑。
1 問題描述
可以用圖G(V E)來表示所研究的網絡拓撲。其中，V是網絡中的節點集，E是邊集。設每個邊有k個QoS參數狀態，用k個權重關聯表示。
在研究QoS選路問題和可用性問題時，邊集E和點集V均可以具有QoS的權。此時，有以下兩種可能情況：
a)只考慮邊的QoS參數。已有的QoS選路算法，大多采用這樣的處理方式。
b)同時考慮邊和節點的QoS參數。此時，如果把節點的參數結合到鄰近邊的參數中去考慮，則此時網絡就可以只考慮邊的參數了。這樣，解決問題時就只需考慮邊參數，不考慮節點參數，問題也就簡化成了第一種情況。為了敘述方便，本文將這種簡化方法稱為N2W。當使用N2W思路后，網絡內只需要考慮邊參數狀態即可。但是，在某些情況下，這種方法會導致誤差。例如當源點或終點失效時，將不存在任何有效連接源點到終點的路徑；當考慮N2W方法時，卻仍然可能存在一條滿足QoS約束條件的路徑。所以，當考慮可用性問題時，如果節點的可用性值重要時，則不能使用N2W方法。
對于任意節點v，它的k個QoS參數狀態可以用k個權重關聯表示。在一個特定網絡拓撲中，所有鏈路和節點應該包含相同個數的QoS狀態參數。可以用一個通用的k狀態值{q0，q1，…，qk}表示某個網絡元素(可能是鏈路，也可能是節點)的QoS狀態值。
本文把基于可用性約束的QoS選路問題稱為availabilitybasedQoS routing（AQR）。當考慮備份路徑時，AQR將會更復雜。根據是否考慮備份路徑問題，AQR可以分為以下兩種類型：
a）第一類AQR問題。此類問題的要求是在網絡中搜索一條路徑，該路徑滿足各QoS約束條件，而可用性只是其中的一個乘性QoS約束參數。該類問題就是一般的QoS選路問題。
b）第二類AQR問題。此類問題的目的是在網絡中搜索一條從源點到終點的工作路徑w和若干與該工作路徑部分獨立或完全獨立的備份路徑b。此時得到的從源點到終點的連接（由工作路徑與備份路徑組成）應滿足各QoS約束條件。
2 AQR算法
解決第一類AQR問題的算法思路是：尋找一條從源點到終點滿足QoS約束條件的路徑。如果搜索成功，則算法選路成功；如果搜索失敗，則算法選路失敗。通用的最短路徑算法可以解決此類問題。比如當只考慮最大可用性路徑問題時，可以用Dijkstra算法求解。還有很多QoS啟發式算法可以求解該類問題，如解決MCP和MCOP問題的文獻[2，3]就可以解決第一類AQR問題。
對第二類問題的特殊情況已有了研究。文獻[4]就研究了WDM網狀網內搜索共享保護路徑的情況。它首先用K最短路徑方法搜索K(K大寫)條最大可用性的路徑；如果這K條路徑的可用性不能滿足要求，則搜索各路徑對應的備份鏈路/路徑，以求新得到的連接中能有滿足可用性要求的連接。
本文重點討論第二類AQR問題。尋找保護路徑的原因是因為工作路徑不能滿足業務的QoS約束要求。這樣就出現一個問題：什么時候需要選路算法尋找保護路徑？情況1:在已知工作路徑的情況下，再尋找一條從源點到終點的備份路徑，使從源點到終點的連接的QoS參數滿足QoS約束條件。情況2:已知從源點到終點的QoS約束條件，尋找一條工作路徑。如果搜索到的工作路徑滿足QoS約束條件，則QoS選路成功；否則，將需要再搜索一條從源點到終點的備份路徑，所得連接應滿足QoS約束條件。
在情況2時，得到的結果有兩種可能：
第一種可能，從源點到終點的工作鏈路已經能滿足所有的QoS約束條件，則從源點到終點連接的各QoS狀態即為工作路徑的QoS狀態。假設該主工作路徑p共包含n個鏈路和節點，且各鏈路或節點的某類型QoS參數的權值為{q0，q1，…，qn}。用q表示從源點到終點的連接對于該類型QoS參數的狀態值，用q(p)表示從源點到終點的工作路徑p上該類型QoS參數的狀態值，則該QoS參數可能的三種情況及其對應q(p)和q值。
該參數為凹性，則
q=q(p)=min{q0，q1，…，qn}(1)
該參數為加性，則
q=q(p)=q0+q1+…+qn(2)
該參數為乘性，則
q=q(p)=q0×q1×…×qn(3)
第二種可能，QoS從源點到終點的工作路徑上的某些類型的QoS參數不滿足約束條件，需要搜索一條從源點到終點的備份路徑。帶有保護路徑的連接的可能情況很復雜。在文獻[5]中討論了可用性的M:N保護的可能情況。
對于第二類AQR問題，除了可用性，還可能會涉及到各種類型的QoS參數。不管是屬于M:N保護還是SBPP或者DPP保護類型，從源點到終點的連接上任何一個元素都有下列屬性: a)節點或鏈路；b)在主工作鏈路上，或在備份路徑上。
對于除可用性外的其他QoS參數，工作鏈路和備份鏈路上該類型的QoS參數值可以用式(1)~(3)得到。假設工作路徑上某類型的QoS參數狀態為q(w)，備份路徑上該類型的QoS參數狀態為q(b)，則源點到終點連接該類型參數的狀態值q為
q=q(w)#q(b)(4)
運算“#”表示取大或取小，究竟是取大還是取小，根據特定QoS參數而定。比如連接的帶寬，應該是工作路徑和備份路徑上帶寬的最小值。所以式(4)取最小值。對于延遲，QoS約束一般是上限要求，式(4)應該取最大值。相應地，抖動、成本和跳數在式(4)都應該取最大值。
第一類AQR算法已經有很多求解算法，在求解第二類AQR問題時，可以借助第一類AQR問題的算法，使復雜問題簡單化。
下面是一個求解第二類AQR問題思路的步驟，從中可以看出由AQR第一類算法求解第二類AQR問題時，需要一些策略或技巧。
a）已知網絡G(V E)。
b）由第一類AQR算法得到一條工作路徑p。
c)按照某種策略，得到網絡拓撲G1。
d）在G1內，仍然由AQR第一類算法得到與p不同的備份路徑b。
從以上步驟可以看出，在求解第二類算法時，主要是把握好求解G1的策略，從而得到需要的合適的備份路徑。
在第二類AQR問題中，因為要涉及到可用性，則問題會更特殊。例如，要找從源點到終點具有最大可用性的工作路徑和備份路徑，一個直接的想法就是：先找到從源點到終點的最大可用性路徑，然后再在剩下所有鏈路中搜索另一條與工作路徑獨立的最大可用性的備份路徑。但該方法得到的工作路徑和備份路徑所得到的連接不一定會得到最大可用性。
圖1就是一個特殊的例子。在圖1中，各鏈路上的數值為該鏈路的可用性，并且假設節點1為源點，節點7為終點。在整個拓撲中，節點1~7的最可用路徑為1—2—3—7，假設它為工作路徑，其可用性為0.994012；在剩下的鏈路中最可靠路徑是1—5—4—7 則其為備份路徑，其可用性為0.993016。在這種情況下，從節點1~7的連接的可用性為0.994012+(1-0.994012)×0.993016=0.999958。
假如工作路徑為1—2—6—7，此時該路徑的可用性為0.993514；假如備份路徑為1—5—4—3—7，它的可用性為0.993913。此時從節點1~7的連接的可用性為0.993514+(1-0.993514) ×0.993913=0.999961。可以看出，此時所得連接的可用性反而比上段所求可用性的值要大。
為了避免上面所舉例子導致的失誤，可以對AQR第二類問題求解步驟中進行改進，也就是可以生成k個路徑對，即k個{w，b}的集合，各對中的w不相同，選擇其中最滿足QoS約束的一對即可。這樣可以得到AQR第二類問題求解步驟，其即為改進的AQR第二類問題的求解思路。在解決策略中，i為循環次數，循環上限為k。注意，在下述的AQR第二類問題求解步驟b)中，一般情況下，最多有k個{w，b}對。當得到的{w，b}對至少存在一個時，則第二類問題就有解。
以下給出AQR第二類問題求解的一個應用例子：
a)已知網絡G(V，E)，i=0。
b）i=i+1。當i>k時，在最多k個{wj，bj}(0≤j≤k)中選擇一個最優組合；當i≤k時執行c)。
c）按策略1得到Gi(G1=G)。
d）由第一類AQR算法在Gi中得到一條工作路徑pi。
e）按照策略2得到網絡拓撲G′i。
f）在G′i內，仍然由AQR第一類算法得到與pi不同的備份路徑bi。
文獻[3]中的算法ATCMCOP為一個效果不錯的第一類AQR算法。可以先由ATCMCOP求解出w，此時取k為w的鏈路跳數。策略1即為在G中依次去掉w中的一條鏈路，剩下的網絡拓撲即為Gi。很明顯，對于不同的i，所得到的Gi是不相同的。策略2則要根據具體要求制定。如果需要備份鏈路與工作鏈路獨立，則策略2可以制定為：在Gi中去掉pi所在的所有鏈路所形成的新的網絡拓撲，即為G′i。
上面第一類算法本文選擇的是ATCMCOP，實際上，可以選擇其他任何性能好的第一類AQR算法。
3 仿真
在仿真時，QoS參數主要考慮可用性。數據包的QoS可用性約束在區間[0.9 1]均勻分布。鏈路的可用性在區間[0.98 1]上均勻分布。
本文將對兩種算法進行比較。第一個算法即使用改進的AQR算法求解第二類問題，并且使用到的第一類算法為ATCMCOP，稱該算法為AQRATCMCOP（AAM）。第二個算法為Mello等人在文獻[6]中提出的算法，不妨稱之為Mello算法。對于網絡路由時遇到的每個第二類AQR問題，分別用AAM和Mello算法進行選路，并用兩個不同的變量GA和GM表示二個算法選路成功的次數。如果AAM選路成功，則GA=GA+1； 如果Mello算法選路成功，則GM=GM+1。
設一條長為L的路徑上的各鏈路可用性為Ai，則該路徑p的可用性為Ap=Li=1Ai。即只要該路徑上所有的鏈路可用時，路徑p可用。此時，計算式子兩邊取對數，可以把可用性轉換為加性參數來處理。當有備份路徑時，可用性的計算方法請見文獻[6]。此時連接的可用性表達式涉及到工作路徑和備份路徑，不能直接取對數轉為加性參數。不過，對于任意一個鏈路的可用性(availability)都應該遠大于不可用性(unavailability)，所以在使用AAM算法時，仍然可以用上面的式子取對數后轉為加性參數來處理，只是在選到路徑后，需要驗證所找到的路徑是否滿足要求，此時驗證所用的計算表達式則用文獻[6]中的計算式子。
仿真使用的網絡拓撲結構為torus 8×8結構，如圖2所示。在該規則網絡結構里，任何節點都與四個其他節點連接。
仿真結果見表1。 在表1中，左列為網絡中的網絡負載變化情況，右列為對應的AAM與Mello算法對于網絡中的AQR問題選路成功次數比值。從結果看出，兩者的效果差不多。
4 結束語
對于AQR問題，已有較多文獻對第一類問題進行了研究，各種算法各有所長。在現有對第二類AQR問題相對較少的研究中，一般都只考慮了可用性一個元素。本文給出了一個通用的第二類AQR算法模型。
