陳永勝

摘要：隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)信息量及信息類型越來越多，傳統(tǒng)網(wǎng)絡(luò)Best Effort服務(wù)機制受到了互聯(lián)網(wǎng)日益增加的信息類型及信息量的沖擊越來越大，QoS算法已經(jīng)成為人們研究的重點與熱點。介紹了路由算法，對QoS及QoS路由進行了闡述，重點對計算機網(wǎng)絡(luò)基于QoS路由算法進行了探討，并對計算機網(wǎng)絡(luò)QoS路由算法的發(fā)展進行了展望。

關(guān)鍵詞：網(wǎng)絡(luò)；QoS；路由算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）10-2202-02

隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)信息量及信息類型越來越多。尤其是到了二十世紀的九十年代，傳統(tǒng)網(wǎng)絡(luò)Best Effort服務(wù)機制受到了互聯(lián)網(wǎng)日益增加的信息類型及信息量的沖擊越來越大，因此，不同的實時多媒體應(yīng)用程序使得傳統(tǒng)的協(xié)議模式對于網(wǎng)絡(luò)用戶的需求不能滿足。在此背景下，網(wǎng)絡(luò)服務(wù)質(zhì)量算法，即Quality of Service，簡稱QoS算法已經(jīng)成為人們研究的重點與熱點。

1 路由算法概述

路由指的是將信息自源通過網(wǎng)絡(luò)向目的地進行傳送。路由技術(shù)包括了最優(yōu)路徑的確定以及信息單元即數(shù)據(jù)包的傳送兩項基本活動。相對而言，進行數(shù)據(jù)包的傳輸與交換較為直接和簡單，但是確定路由較為復(fù)雜。因此，確定路由算法必須充分考慮以下因素：①確定路由算法需要考慮最優(yōu)化。路由算法的確定應(yīng)該選擇最佳路徑能力；②確定路由算法需要考慮簡潔性。路由算法的確定需要簡潔，也就是通過盡可能少的開銷及軟件，實現(xiàn)最大的功能；③確定路由算法需要考慮堅固性。當路由算法處在不可預(yù)料的環(huán)境或者是非正常的環(huán)境時，包括出于負載較高的環(huán)境，操作失誤，硬件出現(xiàn)故障等情況時，要求算法能夠正常的工作。因此在網(wǎng)絡(luò)的連接點上分布路由器，因此，當路由器發(fā)生故障時期后果非常的嚴重，所以，路由算法必須可以經(jīng)受時間的考驗，能夠在不同網(wǎng)絡(luò)環(huán)境中可靠穩(wěn)定工作；④確定路由算法需要考慮快速收斂。對于最佳路徑的判斷全部的路由器都可以達到一致這就是收斂。如果因為網(wǎng)絡(luò)事件造成了路由不可用或者可用，那么路由器就會進行信息的更新。因為進行路由信息更新時，涉及到整個的網(wǎng)絡(luò)，所以必須對最佳路徑進行重新的計算，直至出現(xiàn)全部路由器一致的最佳路徑。當收斂速度慢時，就會出現(xiàn)網(wǎng)絡(luò)中斷甚至造成路徑循環(huán)；⑤確定路由算法需要考慮靈活性。利用算法應(yīng)該準確快速的滿足不同的網(wǎng)絡(luò)環(huán)境。比如，當某網(wǎng)段出現(xiàn)故障，那么路由算法應(yīng)該及時發(fā)現(xiàn)算法，同時能夠提供給使用該網(wǎng)段的全部路由最佳的另外的路徑。

2 QoS及QoS路由概述

2.1 QoS概述

隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，交互式電視會議，遠程教育，協(xié)同文檔編輯等已經(jīng)廣泛的出現(xiàn)在人們的生活中。這些應(yīng)用具有實時性，無一不涉及到網(wǎng)絡(luò)服務(wù)質(zhì)量QoS問題。QoS可以實現(xiàn)對數(shù)據(jù)包的科學(xué)合理的排隊，優(yōu)化含有內(nèi)容標識的數(shù)據(jù)表，同時對于特定數(shù)據(jù)表進行更高優(yōu)先級的賦值，使得優(yōu)先級高的數(shù)據(jù)包首先進行傳輸，提高了數(shù)據(jù)表傳輸?shù)乃俣?。QoS是IP數(shù)據(jù)流基于網(wǎng)絡(luò)性能，具有包括延遲，業(yè)務(wù)可用性，丟包率，可變延遲以及吞吐量等度量指標。對于不同的應(yīng)用要求，QoS也不同，比如有些應(yīng)用要求傳輸速率，有些應(yīng)用要求吞吐量等。

當前Internet越來越普及，已經(jīng)滲入到人們生活的各個方面，人們對網(wǎng)絡(luò)性能，服務(wù)以及安全性等各方面的期望也越來越高。然而當前互聯(lián)網(wǎng)中的Best Effort服務(wù)仍然是一種主要的服務(wù)類別，在網(wǎng)絡(luò)中全部分組都被同等的對待，而任意一個擁塞的鏈路都會造成分組傳輸時間的增加，從而使得性能下降，數(shù)據(jù)出現(xiàn)抖動，甚至是出現(xiàn)數(shù)據(jù)包的丟失，因此服務(wù)質(zhì)量得不到保障。基于此，隨著QoS技術(shù)的不斷發(fā)展，高效的QoS的重要性日益凸顯，被越來越多的應(yīng)用到計算機網(wǎng)絡(luò)路由算法中。

2.2 QoS路由概述

2.2.1 QoS路由網(wǎng)絡(luò)模型

對QoS網(wǎng)絡(luò)的拓撲結(jié)構(gòu)以及資源的容量進行抽象，得到加權(quán)圖N（V，E），V表示了節(jié)點集，也就是網(wǎng)絡(luò)內(nèi)的交換的設(shè)備；E是雙向鏈路集，也就是傳輸?shù)穆肪€。對于任何一個網(wǎng)絡(luò)節(jié)點（u，v），當存在從u→v的鏈路，那么必定會存在從v→u的鏈路，基于鏈路的對稱性可以得到，網(wǎng)絡(luò)被分成了對稱網(wǎng)絡(luò)以及非對稱網(wǎng)絡(luò)。基于以上的描述，事實上網(wǎng)絡(luò)包括了兩種要素，即節(jié)點與鏈路。

2.2.2 QoS路由的度量

QoS路由算法的可實現(xiàn)性是由算法的復(fù)雜程度決定的。而QoS度量參數(shù)的選擇對算法的復(fù)雜程度有著直接的影響，同時，路由選擇算法的性能是由網(wǎng)絡(luò)支持的度量參數(shù)體現(xiàn)的。支持度量參數(shù)越多，表明越能夠有效的接入業(yè)務(wù)服務(wù)質(zhì)量。然而同時增加了路由選擇算法，降低了業(yè)務(wù)接入率。QoS應(yīng)用業(yè)務(wù)對于網(wǎng)絡(luò)服務(wù)提出包括帶寬，丟包率，延時，延時抖動等可度量的參數(shù)。在計算機網(wǎng)絡(luò)上進行數(shù)據(jù)業(yè)務(wù)的傳輸時，需要滿足度量的要求。QoS能夠利用約束集對度量進行描述。

3 計算機網(wǎng)絡(luò)基于QoS路由算法的分析

3.1 不同路由策略特征

基于網(wǎng)絡(luò)狀態(tài)信息的維護形式以及路徑搜索的形式進行分類，路由策略被分成了源路由，層次路由以及分布式路由。源路由內(nèi)的任何一個節(jié)點都對全局信息的完整起到維護作用，維護網(wǎng)絡(luò)拓撲結(jié)構(gòu)以及任何一個鏈路狀態(tài)信息，根據(jù)全局的信息在源節(jié)點進行最優(yōu)路徑的計算；對于層次路由而言，其解決的主要問題是可擴展性問題，將網(wǎng)絡(luò)內(nèi)的一部分節(jié)點進行聚合構(gòu)成邏輯節(jié)點，之后，將這些邏輯節(jié)點進行聚合成上一層次的邏輯節(jié)點，進而能夠獲得樹結(jié)構(gòu)，從最上層邏輯節(jié)點開始進行路由計算；對于分布式路由機制來說，任何一個節(jié)點都不需要對全局的信息進行維護，通常只是清楚相鄰節(jié)點信息，利用各個節(jié)點間的分布式的計算獲得路徑，在節(jié)點間實現(xiàn)信息控制，通過對每一個節(jié)點的保存在狀態(tài)信息的綜合使用對路徑進行搜索，大多是分布式路由算法都要求鏈路狀態(tài)協(xié)議或者是距離矢量協(xié)議，在任何一個節(jié)點通過距離矢量的形式對路由的相關(guān)信息進行維護與計算，基于上述距離矢量，路由過程進行一跳一跳的實現(xiàn)。

3.2 源路由

因為進行源路由的計算能夠在同一個節(jié)點實現(xiàn)，因此，對于分布式計算中存在的死鎖檢測，分布計算終止檢測等問題得到了有效的避免，同時確保了計算的路徑不會出現(xiàn)回環(huán)。源路由存在以下不足：①會聚的信息量比較大。因為對于任何一個節(jié)點來說，都要對整個網(wǎng)絡(luò)的狀態(tài)信息起到維護的作用，因此，網(wǎng)絡(luò)會聚信息量比價大，使得網(wǎng)絡(luò)的整體的效率變低；②網(wǎng)絡(luò)狀態(tài)的準確性不高。因為網(wǎng)絡(luò)的大量的狀態(tài)信息都會向每一個節(jié)點會聚，而進行信息的會聚無疑需要時間，從而使得網(wǎng)絡(luò)的實時情況不能得到很好的體現(xiàn)；③源點計算量過大。當節(jié)點在接收到會聚的網(wǎng)絡(luò)的信息以后，對最短路徑算法進行啟動，基于整體網(wǎng)絡(luò)拓撲信息對本節(jié)點到網(wǎng)絡(luò)的全部的節(jié)點的最短的路徑進行計算，進而生成路由表。對于任何一個節(jié)點來說，都需要進行計算，因此，計算量過大；④可擴展性存在問題。因為對于任何一個路由器來說，其存儲量是有限的，基于此，隨著網(wǎng)絡(luò)規(guī)模的增加，支持源路由路由器網(wǎng)絡(luò)信息維護量源路由大，就大規(guī)模的網(wǎng)絡(luò)而言，路由器的存儲空間不能滿足源路由策略需要。

3.3 分層路由

分層路由通常被進行大規(guī)模網(wǎng)絡(luò)路由計算中存在的可擴展性問題的解決。分層路由計算一般需要源路由策略與分布式路由策略相結(jié)合，這是由于任何一個節(jié)點僅維護聚合以后的部分網(wǎng)絡(luò)的狀態(tài)的信息。通常而言，對于同一層內(nèi)能夠?qū)⒁延械脑绰酚刹呗赃M行利用，分布于不同的邏輯層的計算結(jié)果進行結(jié)合從而獲取最優(yōu)路徑。因此，實際上分成路由具有源路由以及分布式路由的優(yōu)勢。不過兩種策略相結(jié)合的機制也存在一定的不足。①增強了狀態(tài)信息的不精確性。將一部分的節(jié)點的狀態(tài)進行會聚成為一個節(jié)點，通過一條邏輯鏈路信息對多條路徑或者鏈路的綜合信息進行表示，這樣無疑使得網(wǎng)絡(luò)節(jié)點中狀態(tài)信息維護的不準確性增加；②對于多個的QoS參數(shù)節(jié)點不容易聚合成一個節(jié)點。就QoS路由來說，不同QoS參數(shù)需要不同的鏈路或者節(jié)點的聚合的形式，然而這些形式有時候會出現(xiàn)相互驀地，基于此，要進行多個節(jié)點聚合為一個邏輯節(jié)點，而同時又要求聚合多個QoS參數(shù)，這是不容易實現(xiàn)的。介紹一個典型的層次路由算法。B Awerbuch等人對ATM網(wǎng)絡(luò)內(nèi)不同層次算法進行了對比，通過模擬實驗發(fā)現(xiàn)層次算法性能優(yōu)于非層次算法性能，就同一網(wǎng)絡(luò)結(jié)構(gòu)不同層次算法的性能表現(xiàn)及原因進行了分析，同時提出了改進的算法。

3.4分布式路由

對于分布式路由，進行路徑的計算是分布于路徑的節(jié)點間，因此，對于路徑的要求需要滿足響應(yīng)快，計算量小的特點。因為，其節(jié)點不需要對全局信息進行保存，所以具有良好的可擴展性。其存在的不足包括：①由于會聚信息的類型比較多，因此管理不易；②對于某些NP路由問題以及NPC問題，特別是對于QoS路由問題不易設(shè)計啟發(fā)式路由算法；③當狀態(tài)信息不準確時容易發(fā)生回環(huán)的問題，因為節(jié)點維持的信息進行其他路徑的選擇，因此，回環(huán)問題的容易造成路由失敗。

4 計算機網(wǎng)絡(luò)QoS路由算法的展望

傳統(tǒng)計算機互聯(lián)網(wǎng)路由理論將網(wǎng)絡(luò)的權(quán)值看做為不隨著時間變化，是靜態(tài)的，這無疑和實際不相符。事實上，為了對計算機互聯(lián)網(wǎng)的運行的情況進行準確的描述，需要把鏈路權(quán)值當做是隨時間變化的參數(shù)。當前，在理論上已經(jīng)證明，傳統(tǒng)最短路徑算理論基礎(chǔ)，在依賴時間的網(wǎng)絡(luò)中被證明是不正確的。目前，已經(jīng)提出了基于時間變化的網(wǎng)絡(luò)模型，理論基礎(chǔ)，并且在混合型時間網(wǎng)絡(luò)分布式路由協(xié)議中得到了應(yīng)用。

計算機網(wǎng)絡(luò)不但存在時間的依賴性，同時計算機網(wǎng)絡(luò)的鏈路權(quán)值，拓撲結(jié)構(gòu)以及用戶的產(chǎn)生都具有非常大的隨機性，基于此，隨機網(wǎng)絡(luò)模型以及理論能夠?qū)τ嬎銠C網(wǎng)絡(luò)狀態(tài)進行更好的描述。對于最短路徑算法方面，特別是隨機網(wǎng)絡(luò)的最短路徑算法的選擇方面，已經(jīng)有較為深入的研究，與此相關(guān)的算法以及計算機網(wǎng)絡(luò)路由協(xié)議的移植的研究也有了非常大的進步?；陔S機時間依賴模型以及理論描述對于計算機網(wǎng)絡(luò)時間的隨機性構(gòu)建路由算法模型，是未來對于計算機網(wǎng)絡(luò)QoS路由算法的發(fā)展趨勢。

5 結(jié)束語

Internet網(wǎng)絡(luò)的迅猛發(fā)展，其多媒體應(yīng)用及實時應(yīng)用業(yè)務(wù)發(fā)展迅猛，這就要求互聯(lián)網(wǎng)能夠滿足高效的服務(wù)質(zhì)量支持，然而傳統(tǒng)的Best Effort網(wǎng)絡(luò)機制并不能滿足QoS通信的要求，因此，計算機網(wǎng)絡(luò)中基于服務(wù)質(zhì)量的QoS路由算法已經(jīng)成為網(wǎng)絡(luò)研究的重點與熱點。對于QoS路由算法的研究對于網(wǎng)絡(luò)理論及應(yīng)用發(fā)展都具有非常重要的意義。

參考文獻：

[1] 朱慧玲，杭大明.QoS路由：問題與解決方法綜述[J].電子學(xué)報，2008，13（1）：110-116.

[2] 崔勇，吳建平，徐恪.基于模擬退火的服務(wù)質(zhì)量路由算法[J].軟件學(xué)報，2003，14（5）：877-884.

[3] 何小燕，費翔，羅軍舟.Internet中一種基于遺傳算法的QoS路由選擇策略[J].計算機學(xué)報，2010（11）：1171-1178.

[4] 王征應(yīng)，石冰心.基于啟發(fā)式遺傳算法的QoS組播路由問題求解[J].計算機學(xué)報，2001，24（1）：55-61.

[5] B Awerbueh.The Effect of Network Hierarchy Structure on Performance of ATM PNNI Hierarchical Routing[J].Computer Communication，2000，23（10）：980-986.