多約束QoS路由技術的研究

摘要:隨著Internet網絡實時多媒體業務應用快速發展，要求通訊網絡提供高效的服務質量(QoS)，QoS路由成為解決QoS問題的一項關鍵技術。該文介紹了滿足QoS路徑選擇算法的基本概念，設計基礎，著重描述了在基于跳數及時延多約束QoS最短路徑算法的設計。

關鍵詞:QoS;路由技術;跳數;時延

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)33-9164-02

Reserch of Multi-constrained QoS-based Routing Technology

JIANG Wei-xing

(Zhenjiang College，Zhenjiang 212003，China)

Abstract: With the rapid development of real-time multimedia business applications on the Internet network，communication networks to provide efficient quality of service (QoS) is required，QoS routing problem is a key solution to the QoS problem. This article describes the basic concepts and design basis of the QoS routing algorithm and focus on the design of Multi-constrained QoS shortest path algorithm based on the number of hops and delay.

Key words: QoS; routing technology; hops; delay

隨著網絡多媒體技術的飛速發展，Internet上實時多媒體應用層出不窮，如IP電話、視頻會議、視頻點播(VOD)、遠程教育等多媒體實時業務以及電子商務在Internet上傳送，Internet已逐步從單一的數據傳送網向數據、語音、圖像等多媒體信息的綜合傳輸網演化。這些不同多媒體應用要求通訊網絡提供高效的服務質量(QoS)。衡量服務質量包括主要參數如下:① 時延:一個信息包在兩個參考點之間傳輸的時間間隔;② 時延抖動:相同路徑上信息包的時延變化;③ 吞吐量:經過一個網絡或網絡設備的信息包的速率，可以用峰值速率或平均速率表示;④ 丟包率:一個網絡丟棄信息包的最大概率。IP網絡中的服務質量問題主要與IP網絡的傳輸方式有關。IP網絡采用“盡力而為(best-effort)”的傳輸方式，僅為數據傳輸找到一條通道，而對傳輸的結果不做任何保證。這樣的傳輸方式會帶來很多服務質量問題，例如:① 因為傳輸中可能會丟失或拋棄信息，所以無法保證傳輸內容的完整性;② 由于對資源實行共享和動態分配，因此不能保證傳輸的速率或帶寬;③ 不能保證能及時響應用戶。

從某種意義上說，這是IP網絡分布式的、開放的環境帶來的負面影響。未來IP網絡上會有多種業務開展，其中多媒體業務要求非常高的傳輸質量，實時業務要求非常高的響應時間和傳輸時延控制，這是目前的網絡傳輸環境無法達到的。為滿足對QoS不同的需要，提高IP網絡對服務質量的支持能力，有以下幾種QoS技術:資源預留協議(RSVP)、差分服務(DiffServ)、多協議標記交換(MPLS)、虛擬專用網以及流量工程(Traffic Engineering)等技術。這些網絡技術的研究主要通過兩個途徑提高QoS，一個是節點控制;另一個是整網或局部網絡控制。節點控制在單節點或單鏈路完成，主要控制業務對單節點共享資源的占用，包括共享的鏈路、緩存區、處理器資源;節點控制主要的策略包括:業務流整形、業務調度、節點緩沖區管理。整網或局部網絡控制通常通過對路由與信令的控制達到對業務流或業務在網絡中傳輸的直接控制，因路由直接關系到網絡性能，所以QoS路由成為解決QoS問題的一項關鍵技術。

1 QoS路由選擇技術

QoS路由的概念用來刻畫服務提供者與用戶之間用數量或質量來定義的性能約定。一次連接的服務質量由一系列約束條件給出，如帶寬約束，時延約束，抖動約束等。QoS路由的主要目標是為接入的業務選擇滿足其服務質量要求的傳輸路徑，同時保證網絡資源的有效利用。一般路由選擇過程由兩個部分組成:一是為到達業務選擇路徑并發送數據包的過程，本文稱之為尋路過程;一是節點間路由信息的交互過程。

與傳統的盡力而為的路由過程相比，QoS尋路過程涉及三個方面的問題:一是依據哪些度量參數作為尋路標準，這里簡稱為度量參數選擇問題;另一個是在尋路標準設定后，如何找到滿足業務需求的路徑，并保證數據經由選定路徑傳輸到目的節點，我們稱之為尋路問題;路由信息交互過程中，由于鏈路傳輸延時的存在，每個節點獲得的其他節點的狀態信息總是具有一定的不準確性，這些不準確性將在一定程度上影響QoS路由算法的有效性，因此，路由信息不準確的問題，也是QoS路由中的一個主要問題。度量參數選擇問題、尋路問題和路由信息不準確問題是首要解決的基本問題，也是QoS路由中的研究重點。

解決QoS路由問題就是找到一條滿足一個或多個QoS條件的路徑。網絡服務被要求提供的QoS，對于給定路徑相對于其成分鏈路而言一般表現如下3類性質。

1) 可加性:總QoS等于構成這條路徑的所有鏈路QoS值之和(如跳數，時延等);

2) 可乘性:總QoS等于構成這條路徑的所有鏈路QoS值之積(如誤差率，丟包率等);

3) 最小最大性:總QoS等于構成這條路徑的所有鏈路QoS值中的最小者(如流量，帶寬等)，或者總QoS等于構成這條路徑的所有鏈路QoS值中的最大者(如帶寬利用率等)。

因此對于最小性QoS，進行路徑選擇之前不滿足QoS的鏈路將不作為路徑選擇對象;對于乘法性QoS，可以將各鏈路的QoS值進行對數變化，轉換為加法性QoS，保證在進行路徑選擇時只包括加法性QoS，以便于處理。

2 多約束條件下QoS路由模型

由于要同時滿足這些性質各異的QoS是比較復雜的，Dijkstra算法只能根據單一條件來計算最短路徑，在大規模的網絡中則需要設置多個約束條件，使得計算的復雜度控制在多項式的時間內完成，首先根據某些條件簡化網絡，然后再根據某一條件計算最短路徑。

為了便于處理，進行路徑選擇之前將不滿足QoS約束的鏈路不作為路徑選擇對象，同時，對于最大最小QoS一般可以采用加權方法(或倒數)進行變換。對于乘法性QoS，將各鏈路的QoS，將各鏈路的QoS值進行對數變換，轉換為加法性QoS。所以，在進行路徑選擇時只包括加法性QoS。這樣就可以將QoS路由問題經過變換可以轉化為多目標決策問題。

假設一個QoS多個約束條件為x1，x2，…，xn，分別對應業務類型，帶寬，時延，鏈路長度，跳數，端口吞吐能力，端口緩沖能力等，則目標函數f1(x)，f2(x)，…，fp(x)分別代表路徑p上的端到端的可利用帶寬函數，傳輸時延函數，時延抖動函數等約束條件函數。在對瓶頸帶寬和時延抖動等分別進行最大最小化處理、加權處理和對數處理后，可以得到QoS路由的一般形式:

，k(k為v0到vn路徑的個數) x∈X }，

若路徑p滿足上述條件就是QoS請求的可行路徑。下面設計一個多約束QoS的路由算法。

3 算法設計

3.1 問題描述

為了研究算法，將網絡中的交換節點、鏈路、鏈路屬性抽象為圖，其網絡模型可以表示為G(V，E);其中V是頂點的集合，包括n個頂點，其中v∈V為圖的一個節點;E是邊的集合，包括m條邊，e元素為一條鏈路。在每條鏈路e關聯上一組相互無關的權值(w1(e)，w2(e) ，...，wk(e))，稱為鏈路的QoS的度量，簡寫為w (e)，其中wi(e)為路徑約束類型權值度量。

定義1: 源節點s和目的節點d之間路徑P跳數為，e為路徑P上的鏈路。

定義2:對于圖G中，每一鏈路e∈E均對應兩個正實數加權值cost(e)，delay(e)。cost(e)定義了鏈路e的代價，其值與該鏈路的資源使用情況有關。delay(e)定義了鏈路e的信息傳輸時延，該時延包括排隊時延、傳輸時延和交換時延等。路由問題可描述為在圖G中尋找一條包括源節點s到接受節點d的路徑P，應滿足以下條件:

(1)

約束條件:其中△為時延上限(或稱時延約束)，該參量定義了實時業務的傳送延時要求，用于平衡代價與延時的路由選擇策略，鏈路選擇函數如下:

f(eij)=c(eij)

P(i)+D(i，j) <△

否則 f(eij)=∞

其中P(i)是路徑從源節點s到目標節點i的時延，c(eij)、D(i，j)分別為鏈路eij的代價及時延。

3.2 算法實現機理

一般地說，最優算法無法在多項式時間內完成。采用啟發式算法降低算法難度，但在性能上逼近理論算法。下面的算法就是啟發式算法。根據上面的定義，該算法有幾個輸入變量:首先是配置鏈路特性(跳數，時延);其次是與這些特性相關的資源狀況;第三是網絡的拓撲信息。其中網絡的資源和拓撲信息可以通過IGP來獲得。根據鏈路特性傳輸時延識別重點鏈路，采用為鏈路賦權值的方法，根據鏈路的時延情況，時延長的鏈路賦較大的權值，時延小的賦較小權值。為了防止所選路徑過長而消耗過多的網絡資源，引入跳數限制，令H表示路徑的最大跳數限制。在權值的基礎上，綜合考慮時延保證和跳數，提出一種時延、跳數受限的最小權值路由算法。主要計算步驟如下:

1) 排除掉那些鏈路信息不全的鏈路，然后進行鏈路所屬的資源類的檢查，檢查之后，如果發現有無效的資源所屬關系的鏈路，就把這些鏈路排除掉;

2) 根據刪減后的拓撲計算最短距離的路徑。在滿足上述條件下，路徑P的權值最小，P就是就是從源節點s到接受點v的路徑。

3.3 算法實現

根據上面多約束條件QoS路由模型構造思想，具體條件應滿足上面定義1和定義2，通過改進Prim算法來求解問題。Prim算法用于求最小生成樹，Prim算法的基本思想為:在圖G中，算法從U={S}(S為源點)，U為其生成樹的頂點集合，T=Φ開始，重復執行下列操作:在所有u∈U，v∈{V-U}的邊(u，v)∈E中找一條權值最小的邊(u0，v0)并入集合T，T是G上MST中邊的集合，同時u0并入U，直到U=V為止。

改進算法的基本思想是:首先，用Dijkstra第k最短路徑算法，計算從源節點到目的節點以時延和跳數為優化準則的路徑，選擇跳數Hop(p)小于H的路徑，將所求的路徑中最小的時延與Δ比較，若該值比Δ大則表明限制條件太苛刻，可令Δ等于該路徑的時延。然后以cost最小為首要優化目標，用Prim算法求出圖G的MST樹。用Prim算法每生成一條邊eij時，就計算由S到該邊的跳數Hop(p)和累計時延，若Hop(p)

4 結束語

在基于多約束的路由選擇算法中，尋找一條同時滿足兩個或兩個以上度量約束的路徑，是一個NP完全問題。該問題目前在數學上還沒有統一確定的解決方法，這也意味著還沒有標準的基于約束的路由算法。因此在路徑選擇算法，約束條件選擇上具有相當的靈活性，隨著今后光傳輸技術的發展，需要考慮的約束條件一定會隨之而發生變化，我們應該根據不同的網絡結構和性能需求來選擇不同的參數，從而更好地適應未來智能光網絡發展，這些有待跟蹤研究。

參考文獻:

[1] 吳中平.IP網絡的QoS路由算法的研究[D].天津:天津大學計算機科學與技術學院，2007，1.

[2] 包學才.一種多約束服務質量路由算法[J].微電子學與計算機，2008，10.

[3] 崔新友.IP over DWDM 網絡多業務傳送的路由算法[J].清華大學學報，2008，48(1).

[4] 賈艷萍，孟相如.基于MPLS流量工程的多路徑約束負載均衡方法[J].計算機應用，2008，27(3).

[5] 吳功宜，吳英.計算機網絡教師用書[M].清華大學出版社，2004，8.