動態(tài)優(yōu)先調度算法在ip分組中的應用

1調度算法設計目前，qos保證機制在研究服務系統(tǒng)（differv）中的重要論述側重于qos系統(tǒng)的主要交換機設備中。核心交換機的研究重點是第三層交換與路由相結合的方法。由于核心交換機的體系結構大多趨于采用Crossbar交換開關為核心的分布式結構，因此，調度算法也就成為核心交換機中的一個重要研究內容。調度算法的主要目的是為了解決IP分組轉發(fā)時的公平性和延遲性。DiffServ體系的路由節(jié)點緩存區(qū)由4種不同級別的獨立緩存隊列構成，它是一種支持優(yōu)先級的緩存隊列，與此相對應的調度算法是優(yōu)先級調度算法。優(yōu)先級調度算法分為兩種：第一種是靜態(tài)調度算法；第二種是動態(tài)調度算法。靜態(tài)優(yōu)先級調度算法實際上是一種單播調度算法。其中，iSLIP算法是目前較為成功的一種單播調度算法。該算法通過RR指針保證了多個端口之間IP分組轉發(fā)時的公平性。該文將在iSLIP算法的基礎上討論動態(tài)優(yōu)先級調度算法對不同優(yōu)先級的IP分組轉發(fā)時的公平性和延遲性。2采用預約帶寬業(yè)務DiffServ體系定義了四種聚集業(yè)務類型：即：（1）迅速型業(yè)務（PHB-EF）。它是一種“三低一保證”的業(yè)務，“三低一保證”是指低延遲、低抖動、低丟失率和帶寬保證等四項指標。它的DSCP值（DSCP是DS標記域中的具體值）是“101110”，該業(yè)務是一種類似于高速的專線服務；（2）確保型業(yè)務（PHB-AF）。它是一種“預約帶寬”的業(yè)務，在網絡擁塞的情況下仍能保證該類業(yè)務流擁有一定量的預約帶寬。它的DSCP值是“100XXX、011XXX、010XXX、001XXX”；(3）選擇型業(yè)務（PHB-CS）。它是一種按“分級服務”的業(yè)務，它的DSCP定義值類型是“XXX000”，它在DiffServ域中是按原IntServ/RSVP定義的不同級別進行轉發(fā)處理；（4）缺省型業(yè)務（PHB-BE）。它是一種“盡力而為”的業(yè)務，它的DSCP值是“000000”，任何一種路由器都支持缺省型業(yè)務流。按照這四種聚集業(yè)務的定義，DiffServ體系在所有的路由設備中構建了4種緩沖隊列，以致于把進入DiffServ體系的所有信息流劃分歸類為4種聚集流，分別緩存到不同的隊列中，并進行維護和管理。如圖1所示。Queue1表示為第1種迅速型EF聚集流；Queue2表示為第2種確保型AF聚集流；Queue3表示為第3種選擇型CS聚集流；Queue4表示為第4種缺省型BE聚集流。見圖1所示。顯然，這種隊列為嚴格的優(yōu)先級提供了實現QoS的基礎。3優(yōu)先順序算法的描述3.1基于ilisp的ip分配算法靜態(tài)優(yōu)先級調度算法是指IP分組的優(yōu)先級別在傳輸之前便根據某種要求已確定，而且該優(yōu)先級別在整個傳輸過程中保持不變。該算法實現簡單，可為最高級別的聚集流提供QoS保證。iSLIP算法便是一種靜態(tài)優(yōu)先級調度算法。iSLIP算法的目的是為了公平、有效、快速地匹配一個輸入隊列從輸入端口到輸出端口。它是一種迭代算法。每次迭代由三個步驟組成：分別為請求、準許和接受。采用RR選擇指針進行匹配來保證多個端口之間IP分組轉發(fā)時的公平性。iSLIP算法的優(yōu)點是多個端口之間IP分組轉發(fā)的公平性好，容易擴展，對N個端口的交換開關只需lbN次迭代，易于硬件實現。但是，iLISP算法每次迭代請求都是為最高級別的IP分組由輸入端口向輸出端口發(fā)出的一個信息。包括準許和接受都是針對最高級別IP分組的。所以，在DiffServ體系中，其他幾種低級別聚集流有可能一直得不到處理，這是因為只有在高一級的聚集流隊列為空時，才能服務給定較低一級的優(yōu)先級隊列，尤其在高優(yōu)先級聚集流不斷進入緩存隊列的情況下，就會導致低級別的聚集流無限期地等待。顯然這種iSLIP調度算法對4種不同優(yōu)先級聚集流的轉發(fā)是不公平的。3.2動態(tài)和靜態(tài)調度算法動態(tài)優(yōu)先級調度算法是指IP分組的優(yōu)先級別在傳輸中根據某種要求隨著時間而變化，而且隨著時間的增大，優(yōu)先級別也隨之提高。這樣，等待時間較長的IP分組，總會因其優(yōu)先級別不斷提高而被調度轉發(fā)，該算法實現也相對簡單，它在為最高級別的聚集流提供轉發(fā)的同時，而且還能為其他幾種低級別聚集流提供了QoS保證，顯然它是一種較好的調度算法。這種調度算法的思想為不同優(yōu)先級別的IP分組轉發(fā)提供了公平性保證。這里規(guī)定，靜態(tài)與動態(tài)優(yōu)先級調度算法均設定相同的緩存區(qū)最大利用率。兩者區(qū)別僅限于優(yōu)先級別隊列在轉發(fā)傳輸過程中優(yōu)先級別的不變和可變。4核心局域網節(jié)點個數n在靜態(tài)優(yōu)先級調度算法中，由以上討論可知，最高級別聚集流的QoS是有保證的。在動態(tài)優(yōu)先級調度算法中，由于在最高級別聚集流隊列中加入了較低級的IP分組，這樣是否會影響到最高級別IP分組的按時轉發(fā)，為此作以下延遲門限分析：現以端到端的傳輸延遲不大于0.025s為準。由于局域網（校園網內）路過的節(jié)點數很有限，所以，端到端的傳輸延遲主要取決于廣域網中核心交換機的節(jié)點個數，現推算端到端之間經過的最大節(jié)點個數n，因為全球骨干網的路由節(jié)點數已超過十萬臺，但是任一對端到端之間的路由節(jié)點數遠遠沒有那么多，由最新資料統(tǒng)計，全球共有224個國家和地區(qū)。因此得到每個國家平均含有約446臺骨干網的路由節(jié)點。以我國為例進一步推算，有32個省直轄市，每個省平均含有約14臺骨干網的路由節(jié)點。設省內骨干網邊緣節(jié)點到省內骨干網中心節(jié)點之間平均有可能經過的最大節(jié)點數是7臺（按兩條路計算），而國家級骨干網邊緣節(jié)點到國家級骨干網中心節(jié)點之間平均有可能經過的最大節(jié)點數是8臺（按4條路計算）。全球骨干網則是224個國家和地區(qū)的路由節(jié)點之間的連接，所以任意兩個國家之間有可能經過的路由最大節(jié)點數是112臺（按2條路計算）。因此n=7+8+112+8+7=142。在全球骨干網中，一般使用IGRP（專有路由協(xié)議），它的最大跳數是255。顯然，142滿足條件?？紤]到園區(qū)網、校園網的情況，取一個保守值200，由此得t=0.025s/n=0.025s/200=125000ns?，F以此延遲門限標準作為IP分組的轉發(fā)延遲門限討論。5動態(tài)分級調度算法按照動態(tài)優(yōu)先級調度算法的思想，較低級IP分組隨著時間的增大，其優(yōu)先級別也隨之提高。設Q1i(t）、Q2i(t）、Q3i(t）、Q4i(t）分別代表4種不同級別的聚集流。Q1i(t）為最高級別聚集流，Q4i(t）為最低級別聚集流，上標i表示分組順序號。以Qj(t）表示t時刻第j個隊列的IP分組個數；以B表示整個緩存區(qū)的IP分組個數大??；以B/4表示每個隊列所能容納的IP分組個數；用Lj(t）表示代表t時刻第j個隊列的IP分組個數的上限，用△t表示傳輸一個IP分組所需時間。當一個分組在t時刻到達緩存區(qū)入口時，首先記錄這個IP分組到達的時間，以保證緩存區(qū)每個分組都有唯一的時間，并按照優(yōu)先級別把該分組歸入不同的優(yōu)先級隊列（設為第j列），然后計算t時刻第j隊列的IP分組個數Qj(t），即，根據RED-DT算法可知，RED-DT算法總是預留出一小部分緩存空間，留作更好地處理信息流的突發(fā)性。它的緩存區(qū)利用率為ρ=βB/（1+βK）。從ρ的表達式可得，當K=4時，設定β=1，那么，整個緩存區(qū)的最大利用率為ρ=80%。這個最大利用率是IP分組丟棄的門限。因此晉升門限應小于丟棄門限。又因為緩存區(qū)容量一般大于100個IP分組，所以，選取（B/4）×70%作為晉升門限是合理的。以此晉升門限為準，對每個進入緩存區(qū)的IP分組，均要對某一種緩存隊列中每個IP分組的等待時間進行計算以及Qj(t）計算和Qj(t）/（B/4）判斷，所以，只要網絡不產生嚴重擁塞，就不會出現因IP分組丟棄而得不到晉升的情況。按照上述的選取，動態(tài)優(yōu)先級調度算法晉升門限為：若Qj(t）/（B/4）>Lj(t），則取Fj(t）=MAXtime{Qj1(t）,Qj2(t），…，Qjn(t）}；作以下計算：其中，DS是IP分組頭中的優(yōu)先級字段，通過這樣的方法可使較低級的IP分組向上晉升一級優(yōu)先級別。這樣，由于分組流不斷進入緩存隊列，因此，在某較低級的隊列中可能存在著低級隊列和高級隊列之分，這時，如果該低級的隊列中個數超出丟棄的門限，則丟棄沒有晉升的分組，而晉升過的分組受到保護。這種晉升分組方法保證了不同級別聚集流的公平性。具體的不同優(yōu)先級隊列轉發(fā)步驟如下：(1）從t時刻開始，對最高優(yōu)先級隊列進行轉發(fā)，當轉發(fā)完時刻或到t+（B/4）×70%×△t時刻暫停；(2）從轉發(fā)完時刻或t+（B/4）×70%×△t時刻開始，對所有小于t時刻得3種較低級別隊列均晉升優(yōu)先級別一個檔次，然后選擇晉升中最高優(yōu)先級隊列進行轉發(fā)，當轉發(fā)完時刻或到[t+（B/4）×70%×△t]×2時刻暫停；(3）重新賦值t=[t+（B/4）×70%×△t]×2或轉發(fā)完時刻，從時刻開始，回到最高優(yōu)先級隊列再進行轉發(fā)，當轉發(fā)完時刻或到t+（B/4）×70%×△t時刻暫停；(4）從轉發(fā)完時刻或t+（B/4）×70%×△t時刻開始，對所有小于t時刻的3種較低級別隊列均晉升優(yōu)先級別一個檔次，然后選擇晉升中等待時間最長的最高優(yōu)先級隊列進行轉發(fā)，當轉發(fā)完時刻或到[t+（B/4）×70%×△t]×2時刻暫停；(5）重復（3）和（4），直到結束為止。現以1000個字節(jié)長度的IP分組為例，取廣域網骨干網帶寬為2.5Gb/s，這時，每個時鐘數按每秒鐘2.5Gb/s計算，得每個時鐘周期為0.4ns。以現行的接口數據線64位為準，每個總線周期能傳送8個字節(jié)，每個總線周期為4個時鐘周期，所以解出帶寬為2.5Gb/s時，1.6ns傳送8個字節(jié)，也就是1ns傳輸5個字節(jié)。這種條件下，轉發(fā)一個分組需要200ns，由此得出在一個延遲門限內可轉發(fā)625個IP分組。按照上述的具體轉發(fā)步驟可描述為：Queue1→Queue2→Queue1→Queue3→Queue1→Queue4→Queue1→Queue2→……，如此進行下去，直到轉發(fā)完625個分組。6動態(tài)分級調度算法實驗分析這里用MATLAB做了一個仿真實驗。這個實驗是假設網絡沒有發(fā)生擁塞環(huán)境下的仿真，主要目的是只觀察4種優(yōu)先級別分組的轉發(fā)個數情況。并設緩存區(qū)容量可容納100個IP分組，最大利用率為ρ=80%晉升門限是70%，并以1000個字節(jié)長度的IP分組為例。仿真實驗首先隨機地發(fā)送了625個IP分組，討論在一個可允許的延遲門限內（125000ns）,4種優(yōu)先級別分組的轉發(fā)延遲情況。先做靜態(tài)優(yōu)先級調度算法的仿真實驗，結果見圖2所示。后做動態(tài)優(yōu)先級調度算法的仿真實驗，結果見圖3所示。由圖2中可看出，因IP分組優(yōu)先級別不同而轉發(fā)延遲不同。優(yōu)先級別最高的分組（優(yōu)先級1）在一個延遲門限內可發(fā)送570個左右IP分組，優(yōu)先級2可轉發(fā)60個左右IP分組；優(yōu)先級3和優(yōu)先級4的IP分組在這段時間內一直沒有被轉發(fā)。這個結果表明，靜態(tài)優(yōu)先級調度算法只能為優(yōu)先級別最高的分組提供QOS保證。其他3種均不能得到保證，所以公平性較差。從圖3中可看出，優(yōu)先級別最高的分組在一個延遲門限內可發(fā)送370個左右IP分組，同時還能可轉發(fā)120多個優(yōu)先級2的IP分組；轉發(fā)80多個優(yōu)先級3的IP分組；轉發(fā)60多個優(yōu)先級4的IP分組。這個結果表明，動態(tài)優(yōu)先級調度算法為優(yōu)先級別最高的分組提供QOS保證的同時，也能為其他3種優(yōu)先級別的分組提供相應保證。即保證了4種優(yōu)先級別的分組在一個延遲門限內都能得到相應的轉發(fā)，所以公平性較好。7動態(tài)層級調度算法在DiffServ體系的4種獨立緩存隊列中，通過引入動態(tài)優(yōu)先級調度算法可以改變過去靜態(tài)優(yōu)先級調度算法無法解決的4種優(yōu)先級別IP分組轉發(fā)時的公平性問題。解決公平性問題的具體方法是依據緩存隊列容量的70%來確定晉