摘  要： 區(qū)分服務(wù)（DiffServ）體系是未來IP QoS研究的主要發(fā)展方向，在區(qū)分服務(wù)的體系下，隊(duì)列調(diào)度是實(shí)現(xiàn)IP QoS的核心技術(shù)。在深入研究區(qū)分服務(wù)體系下的基本分組調(diào)度算法優(yōu)缺點(diǎn)的基礎(chǔ)上，提出一種改進(jìn)算法，以隊(duì)列分組的延遲特性，保證實(shí)時(shí)業(yè)務(wù)的實(shí)時(shí)特性。對改進(jìn)算法進(jìn)行了仿真，在多約束下，對性能進(jìn)行了評價(jià)。
關(guān)鍵詞： 服務(wù)質(zhì)量；區(qū)分服務(wù)；調(diào)度算法；實(shí)時(shí)特性

　隨著Internet網(wǎng)絡(luò)的迅猛發(fā)展，促使了各種基于Internet應(yīng)用的數(shù)量呈指數(shù)級增長，業(yè)務(wù)種類同時(shí)也發(fā)生了很大的變化，已經(jīng)從單一數(shù)據(jù)向集成數(shù)據(jù)、視頻語音、圖像等多種業(yè)務(wù)轉(zhuǎn)變，例如：語音（VoIP）、VoD（Video on Demand）以及視頻會(huì)議等。這些新應(yīng)用對網(wǎng)絡(luò)的帶寬、延遲、抖動(dòng)等都有一定的要求，而傳統(tǒng)的盡力而為網(wǎng)絡(luò)不能較好地滿足這些新業(yè)務(wù)在帶寬和時(shí)延等方面的具體需求?；诖耍疚奶岢鍪褂肣oS技術(shù)來保證網(wǎng)絡(luò)的傳輸質(zhì)量。QoS 技術(shù)并沒有擴(kuò)充網(wǎng)絡(luò)的帶寬，只是根據(jù)業(yè)務(wù)的需求以及網(wǎng)絡(luò)狀況來管理帶寬，實(shí)現(xiàn)帶寬的優(yōu)化。IETF在1997年9月制定了有關(guān)QoS 定義和服務(wù)的一系列RFC 標(biāo)準(zhǔn)，并提出了區(qū)分服務(wù)（DiffServ）[1]模型的解決方案。在此模型中，它將IP服務(wù)類型（ToS）字段改名為DS，并用它承載IP包服務(wù)所要求的信息，是嚴(yán)格意義上的第三層技術(shù)。區(qū)分業(yè)務(wù)主要通過兩個(gè)機(jī)制來完成：DS標(biāo)記和一個(gè)包轉(zhuǎn)發(fā)處理庫集合的每跳行為PHB（Per-Hop-Behavior）。通過對一個(gè)包DS字段的不同標(biāo)記以及基于DS字段的處理，就能夠產(chǎn)生一些不同的服務(wù)級別。IP包頭中的DSCP（區(qū)分服務(wù)標(biāo)記字段）是DS區(qū)域的邊緣節(jié)點(diǎn)和核心節(jié)點(diǎn)之間傳遞流匯聚信息的媒介，是連接邊界的傳輸分類和調(diào)節(jié)機(jī)制與內(nèi)部PHB的橋梁。
　網(wǎng)絡(luò)QoS控制的實(shí)質(zhì)在于資源的管理，即控制緩沖隊(duì)列、鏈路帶寬等網(wǎng)絡(luò)資源的分配與使用。隊(duì)列管理在網(wǎng)絡(luò)傳輸控制中發(fā)揮著相當(dāng)大的作用，是網(wǎng)絡(luò)QoS控制的核心技術(shù)之一，也是實(shí)現(xiàn)網(wǎng)絡(luò)擁塞控制的重要手段，是當(dāng)前QoS研究的熱點(diǎn)。本文采取DWRR_PQ的調(diào)度算法可以為EF業(yè)務(wù)提供低延遲、低抖動(dòng)及對帶寬的要求的服務(wù)，將EF業(yè)務(wù)和其他業(yè)務(wù)進(jìn)行很好的隔離，避免BE業(yè)務(wù)可能出現(xiàn)的“饑餓”現(xiàn)象。
1 基于DiffServ的隊(duì)列調(diào)度策略
　目前最常使用的隊(duì)列調(diào)度算法有PQ、WRR、DWRR等。PQ算法的高優(yōu)先級隊(duì)列的分組總是優(yōu)先得到調(diào)度，低優(yōu)先級隊(duì)列的分組只能在高優(yōu)先級隊(duì)列分組被調(diào)度結(jié)束之后才會(huì)得到服務(wù)，否則是得不到服務(wù)的。所以該算法能夠給優(yōu)先級高的業(yè)務(wù)數(shù)據(jù)報(bào)文提供低延遲和低抖動(dòng)網(wǎng)絡(luò)性能，而低優(yōu)先級的報(bào)文可能出現(xiàn)“饑餓”現(xiàn)象。WRR算法：對于所有的業(yè)務(wù)流在排隊(duì)等待調(diào)度的隊(duì)列WRR是根據(jù)每個(gè)隊(duì)列配置的權(quán)值與所有的業(yè)務(wù)流在排隊(duì)等待調(diào)度的隊(duì)列的權(quán)值總和的比來平等地分配帶寬的，克服了PQ調(diào)度算法的低優(yōu)先級隊(duì)列可能出現(xiàn)長期的“饑餓”現(xiàn)象。同時(shí)WRR還可以提供類似公平隊(duì)列算法的公平性、實(shí)現(xiàn)過程比較簡單和算法的復(fù)雜度只有O（1），且適用在高速網(wǎng)絡(luò)下。但是由于該算法輪詢服務(wù)的特征，從而不能保證EF業(yè)務(wù)的低延遲、低抖動(dòng)的性能，不能支持包長度的變化，一旦調(diào)度長度不一樣的數(shù)據(jù)包就會(huì)導(dǎo)致分組長的隊(duì)列會(huì)得到更多的帶寬資源，出現(xiàn)不公平的現(xiàn)象。DWRR算法：是基于WRR的一種算法，它分配給每一個(gè)隊(duì)列的權(quán)值不是分組的個(gè)數(shù)，而是分組的比特?cái)?shù)，當(dāng)前輪詢剩下的比特?cái)?shù)會(huì)留到下一次的輪詢中去。基本的調(diào)度過程與WRR算法是一樣的，但是它提供的帶寬分配細(xì)度會(huì)更加公平，而它的復(fù)雜度與WRR一樣。DWRR與WRR有同樣的缺點(diǎn)，即對于在同一個(gè)隊(duì)列的報(bào)文沒有優(yōu)先級的區(qū)分，對于這種“微公平”性沒有很好的保證，并且對EF業(yè)務(wù)的低延時(shí)和低抖動(dòng)也沒有很好的保證[2]。
　本文的調(diào)度算法主要由流量調(diào)節(jié)器和DWRR_PQ分組調(diào)度器兩部分組成。為了避免EF業(yè)務(wù)流量霸占過多的帶寬資源，采用了令牌桶算法作為流量調(diào)節(jié)器來控制EF業(yè)務(wù)的流量。同時(shí)為了滿足EF業(yè)務(wù)的低延時(shí)抖動(dòng)的性能還是采用了優(yōu)先級算法，能夠?yàn)樽罡邇?yōu)先級的EF業(yè)務(wù)提供最佳的服務(wù)。但是由PQ算法的缺點(diǎn)可以看出，這樣做有可能會(huì)使低優(yōu)先級的業(yè)務(wù)長時(shí)間得不到服務(wù)，處于“饑餓”的狀態(tài)[3]。因此，分組調(diào)度器的算法是通過將DWRR算法和優(yōu)先級算法相結(jié)合來實(shí)現(xiàn)的，區(qū)分服務(wù)模型是將大量的復(fù)雜性工作放在邊緣路由器中來完成以達(dá)到伸縮性強(qiáng)的特點(diǎn)。邊緣路由器雖然會(huì)降低流量的容量但是并不會(huì)減少流的數(shù)目，同時(shí)使服務(wù)基于匯聚流，從而使核心路由器的工作僅限于簡單的業(yè)務(wù)判斷并轉(zhuǎn)發(fā)匯聚數(shù)據(jù)流。所以該調(diào)度策略適用于邊緣路由器的隊(duì)列調(diào)度，而核心路由器的調(diào)度策略就是該調(diào)度策略的簡化，即不會(huì)包括令牌桶的流量調(diào)節(jié)器[4]。當(dāng)分組到達(dá)區(qū)分服務(wù)域時(shí)，邊緣路由器首先會(huì)對該分組進(jìn)行分類和調(diào)度。如果該分組被標(biāo)記為EF業(yè)務(wù)，那么它就必須經(jīng)過流量控制的令牌桶過濾，若令牌桶中有令牌則符合流量要求，就會(huì)通過PQ調(diào)度，被送到高優(yōu)先級隊(duì)列進(jìn)行轉(zhuǎn)發(fā)；否則該分組就會(huì)被降級處理重新標(biāo)記，并且同時(shí)轉(zhuǎn)到其他隊(duì)列中去接受DWRR算法的調(diào)度。如果到達(dá)的分組數(shù)據(jù)包被標(biāo)記為其他的非EF業(yè)務(wù)，那么它首先就要接受DWRR算法的調(diào)度，被DWRR調(diào)度后再會(huì)被發(fā)送到PQ算法中的優(yōu)先級或低優(yōu)先級隊(duì)列中進(jìn)行排隊(duì)調(diào)度等待優(yōu)先級調(diào)度器的調(diào)度。在上述算法原理分析中，最高優(yōu)先級的EF業(yè)務(wù)分組總是優(yōu)先得到服務(wù)，但是由于它的流量會(huì)受到令牌桶算法的控制，并不會(huì)占用整個(gè)帶寬的資源，因此低優(yōu)先級業(yè)務(wù)的隊(duì)列并不會(huì)出現(xiàn)“饑餓”狀態(tài)。本文調(diào)度算法提高了網(wǎng)絡(luò)的性能，滿足了QoS對EF業(yè)務(wù)在低延時(shí)、低抖動(dòng)和公平性及對低優(yōu)先級的業(yè)務(wù)的資源分配不合理現(xiàn)象[5]的要求。
DWRR-PQ算法調(diào)度原理如圖1所示。

2.1 調(diào)度算法對EF業(yè)務(wù)吞吐量的仿真
　利用網(wǎng)絡(luò)仿真軟件OPNET實(shí)現(xiàn)了該算法。由圖3可知，DWRR_PQ調(diào)度算法對EF業(yè)務(wù)的吞吐量與PQ算法非常接近，一般都是在500 packets處上下波動(dòng)，波動(dòng)范圍較小。而在WRR算法下的EF業(yè)務(wù)吞吐量波動(dòng)較大，范圍在494 paeket~502 paeket之間。DWRR_PQ算法對EF業(yè)務(wù)的吞吐量的支持率比WRR要好。

2.2 調(diào)度算法對EF業(yè)務(wù)延遲抖動(dòng)的仿真
　在網(wǎng)絡(luò)中傳輸EF業(yè)務(wù)時(shí)要求其具有低延遲和低抖動(dòng)的性能。由圖4所示可以看出，PQ調(diào)度和DWRR_PQ調(diào)度的端到端延遲都是在11.6 ms上下波動(dòng)，而WRR的延遲比較高，在17 ms~18 ms之間波動(dòng)。由這些數(shù)據(jù)可知，PQ和DWRR_PQ算法端到端的延遲比WRR算法低7 ms~8 ms左右，性能有很大的提高。同時(shí)由圖4還可以看出三種調(diào)度算法下EF業(yè)務(wù)通信量的延遲抖動(dòng)的情況。PQ算法和DWRR_PQ算法下，EF業(yè)務(wù)通信量的延遲變化范圍一般是在0.1 ms左右，而WRR算法的延遲的變化大約在0.2 ms?？梢奃WRR_PQ算法對EF業(yè)務(wù)的隊(duì)列延遲和抖動(dòng)有很好的保證。

2.3 調(diào)度算法對BE業(yè)務(wù)支持的仿真
　由圖5可知，PQ調(diào)度算法沒有數(shù)據(jù)（只有DWRR_PQ算法和WRR算法有數(shù)據(jù)），這是由PQ算法的特點(diǎn)決定的，當(dāng)有BE業(yè)務(wù)流時(shí)，PQ調(diào)度器會(huì)將該業(yè)務(wù)分配給最低的優(yōu)先級，再有高優(yōu)先級時(shí)不會(huì)對低優(yōu)先級的業(yè)務(wù)進(jìn)行調(diào)度，使低優(yōu)先級的業(yè)務(wù)處于“饑餓”狀態(tài)，采集不到BE的數(shù)據(jù)，從而使PQ算法的接收方不會(huì)接收到BE的數(shù)據(jù)。同時(shí)從圖中還可以看出，WRR算法對BE通信量的支持比DWRR_PQ方案還要好。

　經(jīng)過對仿真結(jié)果的分析，就EF業(yè)務(wù)隊(duì)列的吞吐量、延遲和延遲抖動(dòng)而言，DWRR_PQ算法的調(diào)度性能都要好于WRR算法；與PQ機(jī)制相比，DWRR_PQ降低了BE業(yè)務(wù)有可能處于“饑餓”狀態(tài)的問題。
　本文提出了一種基于區(qū)分服務(wù)（DiffServ）的擁塞管理的隊(duì)列調(diào)度策略，滿足了區(qū)分服務(wù)業(yè)務(wù)的EF業(yè)務(wù)流對網(wǎng)絡(luò)的性能要求。仿真結(jié)果顯示了本算法實(shí)現(xiàn)了為EF業(yè)務(wù)提供低延遲、低抖動(dòng)及對帶寬要求的服務(wù)，將EF業(yè)務(wù)和其他業(yè)務(wù)進(jìn)行很好的隔離，避免了BE業(yè)務(wù)可能出現(xiàn)的“饑餓”現(xiàn)象，說明了本文提出的調(diào)度策略對區(qū)分服務(wù)體系的隊(duì)列調(diào)度有較好的支持。
參考文獻(xiàn)
[1] 林闖．計(jì)算機(jī)網(wǎng)絡(luò)的服務(wù)質(zhì)量（QoS）[M]．北京：科學(xué)出版社，2004．
[2] PITSILLIDES A， IAMBERT J. Adaptive congestion control in ATM based networks： Quality of service and high utilixation[J]. Computer， Communication， 1997（20）：1239-1258.
[3] PETERSON L L， DAVIE B S. Computer networks： a system approach（second wdition）[M]. 北京： 機(jī)械工業(yè)出版社， 2002.
[4] GUFFENS V， BASTIN G. Fluid flow network modeling for hop-by-hop feedback control of a multicast stream[C]. Benelux Meeting， 2003.
[5] GOYAL P， VIN H M， CHEN H. Start-time fair queuing： a scheduling algorithm for integrated services[J]. IEEE/ACM Transactions on Networking， 1997，5（5）：690-704.