基于優(yōu)先級(jí)的包插入隊(duì)列調(diào)度算法仿真研究

摘 要：提出一種高優(yōu)先級(jí)數(shù)據(jù)包插入到低優(yōu)先級(jí)數(shù)據(jù)包中發(fā)送的新型隊(duì)列調(diào)度算法，該算法不僅較大幅度地降低了高優(yōu)先級(jí)數(shù)據(jù)包的時(shí)延和時(shí)延抖動(dòng)，同時(shí)不會(huì)降低帶寬利用率，具有很強(qiáng)的實(shí)用性。通過OPNET建模驗(yàn)證了此種算法的有效性。

關(guān)鍵詞：時(shí)延抖動(dòng)；隊(duì)列調(diào)度；8 b/10 b編碼；包插入

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1004-373X(2008)02-107-03

Research and Simulation of Packet Inserting Scheduling Algorithm Based on Priority

LI Jian，TU Xiaodong

(Key Laboratory of Broadband Optical Fiber Transmission and Communication Networks，University of Electronic 

Science Technology of China，Chengdu，610054，China)

Abstract：A new queue scheduling algorithm based on priority，which inserts high priority packets into the low priority packet.The new algorithm can effectively reduce the time delay and delay jitter of high priority packets，but can′t decrease the bandwidth utilization ratio.Some simulation experiments are presented in this paper，which obviously verifies the validity of the new algorithm.

Keywords：delay jitter;queue scheduling;8 b/10 b encoding;packet insert

1 引 言

Internet的迅速發(fā)展，IP網(wǎng)絡(luò)開始支持各種時(shí)延和時(shí)延抖動(dòng)敏感的實(shí)時(shí)業(yè)務(wù)(如VOIP和IPTV)，而當(dāng)網(wǎng)絡(luò)上有突發(fā)性高的WWW或者FTP等非實(shí)時(shí)業(yè)務(wù)時(shí)，實(shí)時(shí)業(yè)務(wù)性能會(huì)受到很大影響。為了提供實(shí)時(shí)業(yè)務(wù)的QOS保證，各種減少時(shí)延和時(shí)延抖動(dòng)的隊(duì)列調(diào)度算法應(yīng)運(yùn)而生，目前出現(xiàn)的調(diào)度算法主要有基于循環(huán)調(diào)度(Round Robin)和基于GPS(Generalized Processor Sharing)兩大類［1］，但是這兩類算法都是基于數(shù)據(jù)包，包發(fā)送過程不可中斷。對于變長包發(fā)送，如果有一個(gè)比較長的低優(yōu)先級(jí)包(非實(shí)時(shí)業(yè)務(wù))已經(jīng)開始發(fā)送，同時(shí)收到一個(gè)急需發(fā)送的高優(yōu)先級(jí)包(實(shí)時(shí)業(yè)務(wù))，那么高優(yōu)先級(jí)包只好等待發(fā)送，這就增加了高優(yōu)先級(jí)數(shù)據(jù)包的延時(shí)；并且低優(yōu)先級(jí)的包長度越長，數(shù)目比例越高，系統(tǒng)的抖動(dòng)性能越差。針對上述問題提出一種新型的包插入隊(duì)列調(diào)度算法，并建立OPNET仿真模型。

2 插入式轉(zhuǎn)發(fā)調(diào)度算法簡析

ATM之所以能夠提供比較好的時(shí)延和時(shí)延抖動(dòng)性能，主要在于他的每一個(gè)調(diào)度周期都是一個(gè)長度小而固定的信元，而在變長包調(diào)度中長包發(fā)送的不可中斷性導(dǎo)致系統(tǒng)時(shí)延和抖動(dòng)性能的惡化，原因如下：一個(gè)1.5 kB字節(jié)的長的低優(yōu)先級(jí)數(shù)據(jù)包，在一個(gè)1 000 Mb/s的FE(以太光纖)接口處發(fā)送，需要獨(dú)占的時(shí)間段為：

而發(fā)送一個(gè)64 B的數(shù)據(jù)包只需要0.512 μs，如果該數(shù)據(jù)包為非常重要的高優(yōu)先級(jí)數(shù)據(jù)包，在低優(yōu)先級(jí)數(shù)據(jù)包剛發(fā)送時(shí)到達(dá)，那他得等待近12 μs的時(shí)間。傳統(tǒng)模式和插入模式的轉(zhuǎn)發(fā)過程如圖1所示。

圖1中A部分詮釋了采用最簡單的PQ(Priority Queuing)方法的傳統(tǒng)調(diào)度模式全過程：調(diào)度器在調(diào)度時(shí)間點(diǎn)S1啟動(dòng)對低優(yōu)先級(jí)包L1的發(fā)送，在調(diào)度時(shí)間點(diǎn)S2，發(fā)現(xiàn)高優(yōu)先級(jí)包H1等待發(fā)送，但無法發(fā)送，而必須等待L1發(fā)送完畢后才發(fā)送，這就造成相當(dāng)長的時(shí)延。同樣還有一些其他的調(diào)度算法，比如CQ，WFQ，CBWFQ，LLQ，IP RTP priority，都始終無法解決長包發(fā)送時(shí)對時(shí)延和抖動(dòng)的沖擊問題。這也是當(dāng)前的語[GK!7]音業(yè)務(wù)承載到IP上后，重負(fù)載下性能惡化的主要原因。

為解決上述問題，Cisco曾提出LFI［2］(Link Fragmentation and Interleaving )，采用長包分割發(fā)送的方式改善系統(tǒng)性能，但是映射和解映射過程卻帶來巨大的成本代價(jià)和高復(fù)雜度。為克服這些缺點(diǎn)，提出包插入的隊(duì)列調(diào)度方法：發(fā)送端需要傳輸緊急的高優(yōu)先級(jí)數(shù)據(jù)包時(shí)，將低優(yōu)先級(jí)數(shù)據(jù)包暫時(shí)掛起，然后將控制信號(hào)和所述高優(yōu)先級(jí)數(shù)據(jù)包發(fā)送到數(shù)據(jù)接收端；數(shù)據(jù)接收端根據(jù)控制信號(hào)提取實(shí)時(shí)業(yè)務(wù)包，并保證非實(shí)時(shí)業(yè)務(wù)包的完整接收。圖1的B部分描述仍采用最簡單的PQ(Priority Queuing)方法的包插入過程。這種算法的意義在于高優(yōu)先級(jí)的數(shù)據(jù)包本身在發(fā)送的過程中感覺不到低優(yōu)先級(jí)數(shù)據(jù)包子隊(duì)列的存在，只有他處于高優(yōu)先級(jí)數(shù)據(jù)包子隊(duì)列的頭部就可以發(fā)送，而不必等待低優(yōu)先級(jí)子隊(duì)列中的數(shù)據(jù)發(fā)送。

實(shí)現(xiàn)這種算法的關(guān)鍵在于包插入和恢復(fù)控制信息的創(chuàng)建和解析，下面將包插入算法和1000 BASE-X相結(jié)合，給出該算法的一種實(shí)現(xiàn)方式。

3 包插入和恢復(fù)控制信息

包插入和恢復(fù)控制信息等同于傳統(tǒng)意義的幀定界信息，不過這里的幀變?yōu)椴迦氲膶?shí)時(shí)業(yè)務(wù)數(shù)據(jù)包。傳統(tǒng)的幀定界方式有：字節(jié)計(jì)數(shù)法(如DDCMP(Digital Data Communications Message Protocol))、使用字符填充的首尾定界符法(如BISYNC(Binary Synchronous Communication))、使用比特填充的首尾標(biāo)志法(如HDLC)、違法編碼法(如mb/nb)等。

由于下一代分組傳送網(wǎng)架構(gòu)主要以太網(wǎng)包傳送(EOT)技術(shù)為主，并考慮易于識(shí)別、通用性好、資源耗費(fèi)小等因素，包插入調(diào)度模式的控制信息采用違法編碼法。這種方法利用以太網(wǎng)物理層編碼(mb/nb)的冗余控制碼作為標(biāo)識(shí)信息，簡單易實(shí)現(xiàn)，但由于各種規(guī)格的以太網(wǎng)物理層編碼方式并不相同，現(xiàn)只對1000BASE-X分析包插入模式的實(shí)現(xiàn)過程和仿真結(jié)果，其余規(guī)格的以太網(wǎng)基本類似。

千兆以太網(wǎng)1000BASE-X MAC層的PCS子層采用8b/10b編碼［3］，使用有序集K27.7和K29.7標(biāo)識(shí)數(shù)據(jù)包的開始和結(jié)束。參考上述方法，利用8 b/10 b編碼中冗余的特殊控制碼(K28.7和K28.0)，創(chuàng)建插入幀的開始和結(jié)束有序集，如表1所示。包插入隊(duì)列調(diào)度算法是點(diǎn)到點(diǎn)的調(diào)度方式，結(jié)合上述有序集，這個(gè)過程如下：發(fā)送端對業(yè)務(wù)流進(jìn)行分類，緩存于相應(yīng)的實(shí)時(shí)和非實(shí)時(shí)業(yè)務(wù)隊(duì)列，優(yōu)先發(fā)送實(shí)時(shí)業(yè)務(wù)數(shù)據(jù)包。當(dāng)在發(fā)送非實(shí)時(shí)業(yè)務(wù)數(shù)據(jù)包時(shí)有實(shí)時(shí)業(yè)務(wù)數(shù)據(jù)包需要發(fā)送，通過包插入控制信息(K28.7和K28.0)，在低優(yōu)先級(jí)的數(shù)據(jù)包中插入高優(yōu)先級(jí)數(shù)據(jù)包，過程如圖2所示。

接收端進(jìn)行8 b/10 b譯碼，并根據(jù)非插入包(不包含于某個(gè)包)和插入包的起始信息(分別為K27.7和K28.7)，將非插入包和插入包字節(jié)數(shù)據(jù)緩存到相應(yīng)的隊(duì)列，當(dāng)接收到相應(yīng)的包結(jié)束信息(分別為K29.7和K28.0)，讀出隊(duì)列中的數(shù)據(jù)信息，重新組裝成和發(fā)送端結(jié)構(gòu)一致的數(shù)據(jù)包。

CodeOrdered SetNumber of Code GroupsEncoding

The Ordered Set of inserting schedule model(noinsert-packet)

/S/Start-of-Packet1K27.7

/T/End-of-Packet1K29.7

The Ordered Set of inserting schedule model(insert-packet)

/Is/Insert packet/Is 1/ and /Is 2/

/Is 1/Start-of-insert-pk1K28.7

/Is 2/End-of-insert-pk1K28.0

4 OPNET仿真實(shí)現(xiàn)及結(jié)果分析

仿真采用的實(shí)時(shí)業(yè)務(wù)模型有VOIP和IPTV，非實(shí)時(shí)業(yè)務(wù)模型為WWW。VOIP和WWW業(yè)務(wù)均采用聚合的截尾pareto分布o(jì)n-off模型構(gòu)成自相似源［4］。IPTV業(yè)務(wù)模型采用基于單一場景且不區(qū)分I，P，B幀的gamma分布。

為比較全面的仿真現(xiàn)有網(wǎng)絡(luò)的業(yè)務(wù)負(fù)載情況，針對不同的業(yè)務(wù)和隊(duì)列數(shù)構(gòu)建不同的仿真場景，首先分析網(wǎng)絡(luò)只有WWW和IPTV業(yè)務(wù)且每種業(yè)務(wù)只有1個(gè)隊(duì)列的情況，OPNET仿真圖形如圖3所示，從圖中可以看出插入式調(diào)度模式的包時(shí)延小于非插入式調(diào)度模式，并且圖像的波動(dòng)性(時(shí)延抖動(dòng))插入模式比非插入模式小。

表2給出各種業(yè)務(wù)比重下仿真結(jié)果的時(shí)延統(tǒng)計(jì)值，結(jié)論如下：插入式調(diào)度模式的包平均時(shí)延小于非插入式調(diào)度模式，并且相同比重的VOIP業(yè)務(wù)隨網(wǎng)絡(luò)負(fù)載的增加性能改變更明顯；插入式調(diào)度模式具有比較穩(wěn)定的平均時(shí)延值，而非插入式模式的均值隨網(wǎng)絡(luò)負(fù)載等變化起伏比較大；插入調(diào)度模式的最大時(shí)延值遠(yuǎn)小于非插入調(diào)度模式，并且插入調(diào)度模式的最大時(shí)延值基本相同，這和平均時(shí)延值的穩(wěn)定性一樣，說明插入調(diào)度模式的時(shí)延抖動(dòng)更小 。

當(dāng)網(wǎng)絡(luò)中只有WWW和IPTV業(yè)務(wù)并每種業(yè)務(wù)只有一個(gè)隊(duì)列時(shí)，仿真結(jié)果統(tǒng)計(jì)值如表3所示。從表3可以看出：當(dāng)IPTV包長為1 526 B時(shí)，各參數(shù)值雖然插入模式比非插入模式都有相應(yīng)的減小，但是減小的幅度并沒有VOIP業(yè)務(wù)那么大，性能的提高也只是在幾個(gè)百分點(diǎn)之內(nèi)。當(dāng)減小IPTV的包長，可以看出時(shí)延特性等參數(shù)在插入模式下具有很大的提高，這說明當(dāng)實(shí)時(shí)業(yè)務(wù)包長遠(yuǎn)小于非實(shí)時(shí)業(yè)務(wù)包長，并實(shí)時(shí)業(yè)務(wù)比重小于非實(shí)時(shí)業(yè)務(wù)比重，插入模式下性能提升幅度比較大。

表4給出了網(wǎng)絡(luò)包含3種業(yè)務(wù)，并且實(shí)時(shí)業(yè)務(wù)對于1個(gè)和5個(gè)隊(duì)列的仿真結(jié)果統(tǒng)計(jì)值。同類實(shí)時(shí)業(yè)務(wù)多個(gè)隊(duì)列采用最簡單的輪循調(diào)度，VOIP數(shù)據(jù)包可以插入到[GK5!]IPTV數(shù)據(jù)包中發(fā)送。從表4中可以看出，采用插入式隊(duì)列調(diào)度的各種實(shí)時(shí)業(yè)務(wù)的時(shí)延和時(shí)延抖動(dòng)性能均得到了提高，特別是VOIP業(yè)務(wù)。

由于當(dāng)實(shí)時(shí)業(yè)務(wù)只有一個(gè)隊(duì)列時(shí)隊(duì)列相當(dāng)于FIFO，各路實(shí)時(shí)業(yè)務(wù)的公平性得不到保障，而當(dāng)實(shí)時(shí)業(yè)務(wù)有多個(gè)隊(duì)列時(shí)采用輪循調(diào)度可以保證公平性，所以當(dāng)VOIP數(shù)據(jù)包比較多的時(shí)候(業(yè)務(wù)比重比較大的時(shí)候20%)，多隊(duì)列模式的性能得到顯著提高。IPTV統(tǒng)計(jì)值比較多，所以統(tǒng)計(jì)結(jié)果可以很好的反映多隊(duì)列在時(shí)延方面的改善。WWW業(yè)務(wù)多隊(duì)列模式下，不管是平均時(shí)延，或者最大時(shí)延，還是時(shí)延抖動(dòng)都有提高。

從WWW的平均時(shí)延還可以看出，采用插入式調(diào)度只是輕微的增加WWW業(yè)務(wù)的平均時(shí)延。

5 結(jié) 語

結(jié)合1000BASE-X PCS子層中冗余特殊控制碼實(shí)現(xiàn)基于優(yōu)先級(jí)的插入式隊(duì)列調(diào)度算法，并給出OPNET仿真。從仿真結(jié)果可以看出：在實(shí)時(shí)業(yè)務(wù)比重較小且實(shí)時(shí)業(yè)務(wù)數(shù)據(jù)包包長比非實(shí)時(shí)業(yè)務(wù)數(shù)據(jù)包遠(yuǎn)小的情況下，實(shí)時(shí)業(yè)務(wù)時(shí)延和時(shí)延抖動(dòng)性能得到極大改善，并且非實(shí)時(shí)業(yè)務(wù)的時(shí)延性能并沒有受到多大影響。這種方法很適合于對時(shí)延很敏感的VOIP業(yè)務(wù)和其他包長比較小的實(shí)時(shí)業(yè)務(wù)。

參 考 文 獻(xiàn)

［1］王重鋼，隆克平.分組交換網(wǎng)絡(luò)中隊(duì)列調(diào)度算法的研究及其展望[J].電子學(xué)報(bào)，2001.

［2］Link Fragmentations and Interleaving for MLP Cisco，2003.

［3］1000BASE-X Physical Coding Sub layer (PCS) and Physical Medium Attachment (PMA) Tutorial.http://www.iol.unh.edu/services/testing/ge/training/.

［4］饒?jiān)迫A，徐重陽.自相似網(wǎng)絡(luò)通信量的分析與建模[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2002，30(5):9-11.



注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。