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

關鍵詞：時延抖動；隊列調度；8 b/10 b編碼；包插入

中圖分類號：TP393 文獻標識碼：A 文章編號：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網絡開始支持各種時延和時延抖動敏感的實時業(yè)務(如VOIP和IPTV)，而當網絡上有突發(fā)性高的WWW或者FTP等非實時業(yè)務時，實時業(yè)務性能會受到很大影響。為了提供實時業(yè)務的QOS保證，各種減少時延和時延抖動的隊列調度算法應運而生，目前出現的調度算法主要有基于循環(huán)調度(Round Robin)和基于GPS(Generalized Processor Sharing)兩大類［1］，但是這兩類算法都是基于數據包，包發(fā)送過程不可中斷。對于變長包發(fā)送，如果有一個比較長的低優(yōu)先級包(非實時業(yè)務)已經開始發(fā)送，同時收到一個急需發(fā)送的高優(yōu)先級包(實時業(yè)務)，那么高優(yōu)先級包只好等待發(fā)送，這就增加了高優(yōu)先級數據包的延時；并且低優(yōu)先級的包長度越長，數目比例越高，系統(tǒng)的抖動性能越差。針對上述問題提出一種新型的包插入隊列調度算法，并建立OPNET仿真模型。

2 插入式轉發(fā)調度算法簡析

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

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

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

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

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

3 包插入和恢復控制信息

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

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

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

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

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仿真實現及結果分析

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

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

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

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

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

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

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

5 結 語

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

參 考 文 獻

［1］王重鋼，隆克平.分組交換網絡中隊列調度算法的研究及其展望[J].電子學報，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］饒云華，徐重陽.自相似網絡通信量的分析與建模[J].華中科技大學學報:自然科學版，2002，30(5):9-11.



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