徐永華，陳清華

(1.金陵科技學(xué)院 信息技術(shù)學(xué)院，江蘇 南京211169;2.江蘇省信息分析工程實驗室，江蘇 南京211169;3.南京理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 南京210094)

0 引 言

近年來，流媒體傳輸在網(wǎng)絡(luò)傳輸領(lǐng)域中占據(jù)了越來越重要的地位，如何根據(jù)流媒體的性質(zhì)或改進交換機的調(diào)度策略［1-2］是提高網(wǎng)絡(luò)服務(wù)質(zhì)量的有效途徑。目 前，VOQ［3］交 換 機 使 用 的 調(diào) 度 算 法 有PIM［4］(Parallel Iterative Matching)、RRM［5］(Round-Robin Matching)和iSLIP 算法［6-7］，其中，iSLIP 算法因為其實現(xiàn)簡單和并行性得到了廣泛的應(yīng)用，但為保證網(wǎng)絡(luò)的服務(wù)質(zhì)量(QOS)［8］同時也保證吞吐量。學(xué)者們提出了基于輸入排隊［9］的支持優(yōu)先級機制的交換機調(diào)度算法，即Prioritized iSLIP(P-iSLIP)算法［10］，進行基于優(yōu)先級的調(diào)度，這樣才能使重要性高的分組得到更好的服務(wù)，但該算法是各個輸入隊列按照嚴格優(yōu)先級來執(zhí)行的，在實際的傳輸過程中將會導(dǎo)致普通數(shù)據(jù)隊列的丟失及對增強層造成很大的延時和延時抖動，不能更好地滿足網(wǎng)絡(luò)的服務(wù)質(zhì)量保證及網(wǎng)絡(luò)吞吐量。

因此，本文提出改進支持嚴格優(yōu)先級的交換機調(diào)度算法，采用動態(tài)優(yōu)先級算法實現(xiàn)，其中設(shè)計了一個動態(tài)的線性優(yōu)先級計算函數(shù)，該函數(shù)的輸入?yún)?shù)是每個隊列的優(yōu)先級和在每一隊列中待發(fā)送的數(shù)據(jù)包數(shù)，傳輸?shù)膬?yōu)先級隨之動態(tài)改變。該算法使交換機能夠更好地支持MPEG-4 流的傳輸，提高MPEG-4 流傳輸?shù)姆?wù)質(zhì)量。

1 虛擬輸出排隊VOQ 的交換機邏輯結(jié)構(gòu)

基于VOQ 的系統(tǒng)結(jié)構(gòu)如圖1 所示，它主要由輸入端口、輸出端口、交換結(jié)構(gòu)和調(diào)度器［11-12］組成。假設(shè)輸入和輸出端口的數(shù)量都是N 且數(shù)據(jù)傳輸速率相同。輸入端口采用VOQ，共有N ×N =N2個隊列。分組在進入交換結(jié)構(gòu)前已被分成定長信元，時間被分成等長的時間片。

圖1 VOQ 交換機的系統(tǒng)結(jié)構(gòu)

輸入端i 的信元到達是一個離散的隨機過程，用Ai(t)表示，1≤i≤N，表示在一個時間片t 內(nèi)最多有一個信元到達一個輸入端口。到達的信元根據(jù)目的端口存放相應(yīng)地輸入FIFO 隊列Q(i，j)中，隊列Q(i，j)的占用率用Li，j(t)表示。各隊列的信元到達過程用Ai，j(t)表示，平均到達率為λi，j。到達過程的集合記為

2 基于VOQ 的輸入排隊匹配調(diào)度算法

2.1 基于嚴格優(yōu)先級的iSLIP 算法

在MPEG-4 中將層次劃分為基本層、增強層1 ～4，由此得出VOQ 隊列為基本層、增強層分組和普通數(shù)據(jù)分組的6 組，各自的重要性不同，在支持L 個優(yōu)先級的P-iSLIP 算法中，每一個輸入端口對每個單獨的優(yōu)先權(quán)等級和輸出都保持一個單獨的FIFO 隊列，在每個VOQ 中設(shè)置P 個子隊列，P 個子隊列表示為Ql(i，j)，其中i 表示輸入端口;j 表示輸出端口，l 表示優(yōu)先級，則1≤i，j≤N，1≤l≤P，這樣每個輸入端口保持了FIFO 隊列數(shù)為P ×N 個。該算法在每個信元時間內(nèi)規(guī)定了嚴格的優(yōu)先權(quán)。

Ql(i，j)只有在Qm( i，j )，l ＜m≤P 的所有隊列被服務(wù)完成之后才能接受服務(wù)，算法在迭代收斂時或迭代次數(shù)達到n 次后停止。其中，迭代收斂是指在新一輪的迭代中沒有匹配出任何新連接。每次迭代的3 個步驟分別為請求、授權(quán)、接受。

在P-iSLIP 算法中，各個優(yōu)先級隊列是按照嚴格優(yōu)先級來執(zhí)行的，即高優(yōu)先級的隊列中有分組的話，低優(yōu)先級隊列不會被發(fā)送，在實際的傳輸過程中將會導(dǎo)致:①普通數(shù)據(jù)隊列丟失，當基本層和增強層待傳輸?shù)臄?shù)據(jù)量增加時，普通數(shù)據(jù)包的阻塞將加大，一旦普通數(shù)據(jù)包的隊列達到滿的情況下，就會丟失;②MPEG-4 增強層數(shù)據(jù)包丟失，因為將MPEG-4 流分成基本層和增強層時，由于MPEG-4 增強層是不能單獨解碼的，必須和其對應(yīng)的基本層一起解碼，如果在MPEG-4 基本層隊列和增強層隊列中依然采用嚴格優(yōu)先級策略的話，對于MPEG-4 增強層將造成很大的延時和延時抖動，很可能當MPEG-4 增強層傳送到解碼器時，與其對應(yīng)的基本層幀已經(jīng)解碼播出了。這樣MPEG-4 增強層就錯過其播發(fā)時間，導(dǎo)致的結(jié)果是雖然MPEG-4 增強層傳輸?shù)搅私K端，但對于視頻質(zhì)量并沒有幫助，相當于MPEG-4 增強層數(shù)據(jù)包丟失了。因此，在考慮盡量滿足MPEG-4 基本層的傳輸下，適當考慮提高增強層和普通數(shù)據(jù)包的優(yōu)先級，使得數(shù)據(jù)傳輸更加完整。因此，提出了在面向MPEG-4 流的匹配調(diào)度算法設(shè)計中，綜合考慮實際發(fā)送數(shù)據(jù)隊列的情況，改進面向MPEG-4流的調(diào)度算法，使之更加適合數(shù)據(jù)傳輸。

2.2 動態(tài)優(yōu)先級的iSLIP(DP-iSLIP)算法

首先將數(shù)據(jù)隊列分為3 組，如表1 所示。

表1 數(shù)據(jù)隊列分組

因此，每個輸入端口的每一個VOQ 設(shè)置6 個子隊列，分別是MPEG-4 基本層隊列、MPEG-4 增強層1 隊列、MPEG-4 增強層2 隊列、MPEG-4 增強層3 隊列、MPEG-4 增強層4 隊列和普通的Best Effort 隊列。

基于嚴格的優(yōu)先級考慮是對于每一組設(shè)置一個固定的優(yōu)先級，不考慮系統(tǒng)的狀態(tài)和隊列中的數(shù)據(jù)多少。本文提出采用一種動態(tài)考慮優(yōu)先級的辦法，即在整個數(shù)據(jù)傳輸?shù)倪^程中，優(yōu)先級動態(tài)改變，設(shè)計一個動態(tài)的線性優(yōu)先級計算函數(shù)F(i)，該函數(shù)的輸入?yún)?shù)是每個隊列的優(yōu)先級和在每一隊列中的待發(fā)送的數(shù)據(jù)包數(shù)，該函數(shù)定義為

式中:l(p)是對列p 的優(yōu)先級，0≤l(p)≤1，本文實驗仿真中定義為{0.7，0.4，0.2};r(p)是隊列中的待發(fā)送的數(shù)據(jù)比，即待發(fā)送的數(shù)據(jù)包數(shù)/隊列的長度;w(p)是一個權(quán)重因子，在此，定義為{0.6，0.7，0.8}。公式中體現(xiàn)出如果一個數(shù)據(jù)包具有較高的l(p)，同時隊列中的數(shù)據(jù)也較多則具有較高的優(yōu)先級，會被首先考慮發(fā)送。設(shè)置MPEG-4 的基本層隊列的優(yōu)先級l(p)最高，普通數(shù)據(jù)隊列的l(p)最低，而r(p)的值取決于目前隊列的狀態(tài)和隊列可利用的長度。如圖3 所示，經(jīng)過優(yōu)先級函數(shù)計算后具有最高取值的隊列優(yōu)先被發(fā)送。但是，當一個隊列中待發(fā)送的數(shù)據(jù)較多，即r(p)接近于1 時，首先考慮發(fā)送該隊列中的數(shù)據(jù)，以免數(shù)據(jù)被丟失。然而，如果沒有一個隊列中待發(fā)送的數(shù)據(jù)處于占滿隊列的情況，l(i)是發(fā)送數(shù)據(jù)優(yōu)先級的決定因素，也就是隊列優(yōu)先級較高的先被發(fā)送。如果f(p)＞1，則取整。

圖3 動態(tài)優(yōu)先級結(jié)構(gòu)模型

因為該算法中要支持6 個優(yōu)先級隊列，所以，每個輸出端口需要6 個授權(quán)指針gjp(j)，1≤j≤6;每個輸入端口也需要6 個接受指針aip(i)，1≤i≤6。

改進后的算法同樣分為3 個步驟:

(1) 請求。如果任意一個輸入端口i 有分組需要發(fā)送，那么在輸入端口i 的所有非空VOQ 中，每個VOQ 選出發(fā)送配額Ck不為0 的，且根據(jù)測算出具有最高優(yōu)先級的分組，判斷如果是增強層組，則固定優(yōu)先級考慮輪轉(zhuǎn)該組的所有隊列，并為相應(yīng)隊列發(fā)送請求;否則不是增強層組，發(fā)送最高優(yōu)先級的分組隊列，在請求中包含該隊列的優(yōu)先級fij(p)信息。如果MPEG-4基本層組隊列和增強層組中所有隊列均為空，則發(fā)送普通隊列的請求。

(2) 授權(quán)。輸出端口j 接收到請求之后，它需要找到這些請求當中具有最高優(yōu)先級的所有請求f(j)=max fij。然后輸出端口就在滿足優(yōu)先級為f(j)的輸入端口中選擇一個輸入端口。輸出仲裁器需要對每一個優(yōu)先級等級保持一個指針gjp。在所有具有最高優(yōu)先級為f(j)的輸入選擇過程中，仲裁器使用指針gjp(j)并且選擇使用與經(jīng)典SLIP 算法相同的輪轉(zhuǎn)方案。輸出端口要告訴每個輸入端口它的請求是否被授權(quán)了。當且僅當在第3 步中輸入端口i 接受輸出端口j 時，指針gjp(j)在授權(quán)的輸入端口位置之后模N+1。

(3) 接受。假如輸入端口i 接收到輸出端口來的授權(quán)，輸入端口i 將確定最高級別的授權(quán)，即確定f'(i)=max fij。輸入端口在具有優(yōu)先級為fij=f'(i)的輸出端口中選擇一個。輸入仲裁器對每個優(yōu)先級保持一個單獨的指針aip。在所有具有最高優(yōu)先級為f'(i)的輸出端口中進行選擇時，仲裁器就使用指針a'ip(i)按照經(jīng)典SLIP 算法一樣的輪轉(zhuǎn)方案來進行選擇。每個輸入端口應(yīng)該對每個輸出端口的授權(quán)是否被接受做出指示。指針a'ip(i)在被接受的輸出端口之后模N +1。輸出端口i 在完成匹配后將該端口的VOQij中建立匹配的隊列的發(fā)送配額Ck－1。

圖4 給出了一個算法實例。圖中為一個4 ×4 的交換結(jié)構(gòu)。在圖4(a)中，設(shè)VOQ11的基本層和增強層隊列都不空，且Ck＞0，所以VOQ11的基本層隊列發(fā)送請求，請求優(yōu)先級為f1，即requset(f1);設(shè)VOQ12中，基本層隊列不空，但基本層隊列的Ck=0，無法發(fā)送請求，所以增強層發(fā)送請求requset(f2);而VOQ32中基本層和增強層都為空，則普通隊列發(fā)送請求requset(f3)。由于輸出端口1 收到的2 個請求的優(yōu)先級相同，需要查看授權(quán)指針gjp(j)來確定授權(quán)哪個輸入端口的請求，而gjp(j)所指的輸入端口為1，所以輸出端口1 授權(quán)輸入端口1 的請求;輸出端口2 收到的2 個請求優(yōu)先級不同，授權(quán)優(yōu)先級高的請求。在圖4(b)中，可以看到授權(quán)的結(jié)果。如圖4(c)所示，輸入端口1 收到了2 個授權(quán)，但優(yōu)先級不同，所以輸入端口1 接受優(yōu)先級高的授權(quán)，在接受之后，相應(yīng)的授權(quán)和接受指針都進行更新，這樣就完成了一次迭代。多重迭代執(zhí)行算法的步驟(1)～(3)，每次迭代都在以前迭代建立匹配的基礎(chǔ)上增加匹配的數(shù)目。如果在迭代過程中，當某一VOQ 的子隊列中的MPEG-4 基本層和增強層隊列的發(fā)送配額Ck=0，則將它們的發(fā)送配額Ck各自設(shè)為初始時的發(fā)送配額。通過上述的改進，使得MPEG-4 基本層和增強層有選擇的發(fā)送，首先保證基本層分組的發(fā)送，同時也盡力發(fā)送增強層分組。

圖4 算法實例

3 實驗結(jié)果

該發(fā)生器的開發(fā)采用VC + + 6.0、Matlab 6.5 的開發(fā)環(huán)境，Windows XP 操作系統(tǒng)。仿真的交換結(jié)構(gòu)采用8 ×8 的crossbar［13-14］交換結(jié)構(gòu)，并且所有鏈路具有相同的信元傳輸速率，流量模型采用ON/OFF 模型［15-16］。設(shè)定輸入端口速率為1 Gb/s，交換結(jié)構(gòu)采用VOQ 存儲組織方式，改進后的算法采用4 次迭代，信元長度為64 Byte，延遲時間的單位為時隙(slot)，即傳輸一個信元用的時間。

3.1 性能評價指標

(1) 包丟失率。設(shè)Npli表示第i 時間間隙丟失的包數(shù);Npai表示第i 時間間隙到達的包數(shù);t 為某個時間片，則包丟失率:

(2) 平均延遲。設(shè)Tpdi表示第i 時間間隙包的延遲時間;Tpai表示第i 時間間隙包的到達時間;t 為某個時間片，則平均延遲Ad:

3.2 發(fā)送配額對延遲的影響

由于在改進的算法中為MPEG-4 基本層隊列和4個MPEG-4 增強子層隊列分別設(shè)置了發(fā)送配額Ck。設(shè)MPEG-4 基本層隊列、MPEG-4 增強層1 隊列、MPEG-4 增強層2 隊列、MPEG-4 增強層3 隊列和MPEG-4 增強層4 隊列的發(fā)送配額分別為C1，C2，…，C5，令rate = C1∶C2∶C3∶C4∶C5，則rate 值表示MPEG-4 基本層和4 個增強子層隊列的發(fā)送比，假設(shè)rate=2 ∶1 ∶1 ∶1 ∶1，給出增強層的4 個隊列同一個發(fā)送配額，而每發(fā)送2 個MPEG-4 基本層隊列就發(fā)送1個MPEG-4 增強層組中每一個隊列，其中增強層的隊列是輪轉(zhuǎn)發(fā)送。

如表2 所示，在80%的負載下，不同的流量和不同的rate 值，MPEG-4 基本層和MPEG-4 增強層1 隊列、2 隊列、3 隊列和4 隊列的平均延遲大小。rate 值從3 增大到10。

表2 配額對延遲的影響

從表2 中可以看出，基本層的延遲同比增強層的較少，說明首先保證基本層傳輸，此外，當rate 從3 增大到6 時，MPEG-4 基本層分組的延遲明顯減小;rate從6 增大到10 時MPEG-4 基本層的延時略有減小，趨于穩(wěn)定;rate 從3 增大到7 時，MPEG-4 增強層的延時緩慢增大;當rate 從7 ～10 時，MPEG-4 增強層分組平均延時增大較快。

通過上述分析，可以得到這樣的結(jié)論:rate 值為7左右時，改進的算法能夠獲得較好的性能，既能使MPEG-4 基本層的分組平均延遲減少到最低，又能保證MPEG-4 增強層的分組平均延遲不至于過大。故本文將MPEG-4 基本層分組和MPEG-4 增強層分組的Ck值比例設(shè)為7 ∶1。

3.3 P-iSLIP 算法和DP-iSLIP 算法的分析比較

普通數(shù)據(jù)隊列的延遲比較如圖5 所示。由圖可以看出，普通數(shù)據(jù)隊列在負載為10% ～50%時，兩種算法下的延遲基本一樣，當負載大于50%時，動態(tài)優(yōu)先級下的平均延遲較小，隨著負載的加重，平均延遲變化比較平穩(wěn)。

普通數(shù)據(jù)隊列的包丟失率如圖6 所示，由圖可以看出，當負載大于50%時，隨著負載的加重，兩種算法下的包丟失率變化都比較快，其中P-iSLIP 算法下的包丟失率較大;動態(tài)優(yōu)先級下的包丟失率較小。

增強層1 隊列的延遲比較和丟包率如圖7、8 所示。由圖可以看出，與普通隊列的基本相似，但是在60% ～70%和80% ～90%之間兩種算法有很大的區(qū)別。

圖5 普通數(shù)據(jù)隊列的延遲

圖6 普通數(shù)據(jù)隊列的包丟失率

圖7 增強層1 隊列的延遲

圖8 增強層1 隊列的包丟失率

圖9 基本層隊列的延遲

圖10 基本層隊列的包丟失率

基本層隊列的延遲和包丟失率比較如圖9、10 所示。由圖可以看出，基本層隊列在負載為10% ～50%時，兩種算法下的延遲基本一樣，當負載大于50%時，動態(tài)優(yōu)先級下的平均延遲較小，在負載為50% ～60%之間隨著負載的加重，平均延遲變化較快，但是丟包率有著明顯的改善，較為平穩(wěn)。

縱觀以上結(jié)果可以看出，動態(tài)優(yōu)先級算法具有較低的平均延遲和包丟失率，對于MPEG-4 基本層隊列、增強層1 隊列以及普通數(shù)據(jù)隊列具有很好的分類調(diào)度作用，當負載為90%時，MPEG-4 基本層隊列的延遲為18 個時隙，增強層1 隊列的延遲為340 個時隙，普通數(shù)據(jù)隊列的延遲為2 400 個時隙;MPEG-4 基本層隊列的包丟失率為0.019，增強層1 隊列的包丟失率為0.21，普通數(shù)據(jù)隊列的包丟失率為0.96，說明首先保證了基本層的通過，而且縱向比較各圖，犧牲了較小的基本層的延遲和丟包率，換得了其他各層數(shù)據(jù)的延遲和丟包率的大幅度減少，即以較小的代價換得了更多的數(shù)據(jù)通過。綜上所述，DP-iSLIP 算法在有限的空間下，盡量考慮了滿足MPEG-4 基本層的傳輸下，適當考慮提高增強層和普通數(shù)據(jù)包的優(yōu)先級，使得數(shù)據(jù)傳輸更加完整。

4 結(jié) 語

本文改進了面向MPEG-4 分級編碼流的交換機調(diào)度算法，實驗首先對算法中rate 參數(shù)取值進行了討論，然后在普通數(shù)據(jù)隊列、基本層隊列、增強層1 數(shù)據(jù)隊列中分別采用嚴格優(yōu)先級的P-iSLIP 算法和DP-iSLIP 算法完成了不同負載情況下的延遲和丟包率比較。說明在有限的資源下，首先保證基本層數(shù)據(jù)隊列的通過，其次是增強層1 隊列，最后是普通數(shù)據(jù)隊列，對于普通數(shù)據(jù)隊列和增強層的隊列都在原有的P-iSLIP 算法基礎(chǔ)上有了較大的提高，當然是以犧牲了較少的基本層的數(shù)據(jù)傳輸為代價的。仿真結(jié)果表明，本文提出的面向MPEG-4 流的交換機調(diào)度算法能夠保證MPEG-4 基本層的優(yōu)先發(fā)送，保證其延時性能，保證其具有較少的丟包率，同時也能將考慮到MPEG-4 增強層和普通數(shù)據(jù)得到一定的服務(wù)，能夠為MPEG-4 流的傳輸提供更好的質(zhì)量保證。

［1］ 王 暉，沙基昌，孫 曉，等. MPEG-4FGS 視頻流量模型的仿真應(yīng)用研究［J］.計算機仿真，2006，23(12):

［2］ 劉國柱，王洪林.MPEG-4 實時視頻傳輸?shù)膿砣刂扑惴ǖ母倪M［J］.微型機與應(yīng)用，2010，18(5):39-44.

［3］ 徐曉飛，吳建民，龔 誠.VOQ 交換機的輸出隊列調(diào)度算法［J］.哈爾濱工業(yè)大學(xué)學(xué)報，2009，41(7):120-123.

［4］ McKeown N. Scheduling cells in an input-queued switch［J］.Electronics Letters，1993，29(25):2174-2175.

［5］ Anderson T E，Owicki S S，Saxe J B，et al. High speed switch scheduling for local area networks［J］. ACM Transactions on Computer Systems，1993，11(4):319-352.

［6］ Nick McKeown. The iSLIP scheduling algorithm for input-queued switches［J］. IEEE/ACM Transactions on Networking，1999，7(2):188-201.

［7］ 李 秋，戚宇林，楊 凱.輸入排隊iSLIP 算法的改進與比較［J］.華北電力大學(xué)學(xué)報(自然科學(xué)版)，2009，36(2):106-109.

［8］ Ch Bouras，Gkamas A. Multimedia transmission with adaptive QoS based on real-time protocols ［J］. International Journal of Communication Systems，2003，16(3):225-248.

［9］ 張重洋，申金媛，劉潤杰，等.基于輸入排隊的高速交換調(diào)度算法研究［J］.智能系統(tǒng)學(xué)報，2008，3(3):265-269.

［10］ Nick McKeown. Scheduling algorithms for input-queued cell switches［D］.Berkeley:Univ California，1995.

［11］ 王俊芳，張思東.通用高速分組交換調(diào)度算法［J］.電子科技大學(xué)學(xué)報，2010，39(1):69-73.

［12］ 申 寧，李 俊，倪 宏. 一種優(yōu)化指針策略的輸入排隊調(diào)度算法［J］.計算機系統(tǒng)應(yīng)用，2010，19(12):94-99.

［13］ 馬祥杰，蘭巨龍，毛軍鵬，等.輸入排隊Crossbar 架構(gòu)下的流量模型［J］.電子學(xué)報，2009，37(1):170-174.

［14］ 高志江，曾華燊，夏 羽.基于CICQ 交換結(jié)構(gòu)的低復(fù)雜度調(diào)度算法［J］.四川大學(xué)學(xué)報(工程科學(xué)版)，2011，43(5):163-167.

［15］ TAQQU M，LECY J. Dependence in probability and statistics:A survey of recent results［C］//Volume 11 of Progress in Probability and Statistics. Birkhauser，Boston，1986:73-89.

［16］ 饒云華，曹 陽，楊 艷，等. 基于Pareto 分布的IP 骨干節(jié)點輸入通信量模型［J］.計算機科學(xué)，2006，33(3):27-28.