基于Crossbar的可重構網絡輸入排隊分域調度研究

張博，汪斌強，王珊珊，衛紅權，李揮

(1. 國家數字交換系統工程技術研究中心, 河南 鄭州 450002;2. 北京大學深圳研究生院 深圳市云計算關鍵技術和應用重點實驗室，廣東 深圳 518055)

1 引言

互聯網基于資源統計復用、“盡力而為”服務模式的特點，輔以Overlay、CDN等技術拓展了其所承載的業務范圍，一定程度上滿足了規模化的音視頻業務、安全業務等承載要求，但并未從根本上解決互聯網面臨的安全、多播、QoS等問題。其根本原因在于一方面網絡是剛性的，網絡的設計與構建依據特定業務需求進行，改造只能依靠升級和擴展，無法實現功能重構；其二節點是封閉的，節點的升級和擴展只能由原提供商實施，無法實現開放。從而導致了互聯網的僵化問題。針對上述問題，擺脫傳統網絡技術體系束縛，提出了一種面向服務提供的柔性網絡技術體系。

面向服務提供的柔性網絡技術體系對現有和未來可能出現的用戶業務進行科學聚類[1]，業務的聚類方法有多種，因應用環境不同而異，當前主要是通過業務對服務質量的要求進行聚類。還可以按照功能特征進行聚類，例如互聯網上的業務可以分為視頻、語音、交互式命令等。還可以按照通信方式的數量進行分類，將業務分為點到點業務、點到多點業務和多點到多點業務等[2]。

在柔性網絡技術體系中，基礎設施提供商建設、管理和維護物理網絡基礎設施，為可重構服務承載網(RSCN, reconfigurable service carrying network)提供網絡資源。服務提供商在網絡級，根據業務需求考慮異質和同質、成本和收益[3]和負載流量均衡[4]等因素實現RSCN優化構建。在節點級，通過重構將節點資源分割為某個RSCN獨享，支持網絡級承載網之間的獨立運行。當某一業務取消時，該RSCN可立即拆除，將網絡資源應用到新的RSCN構建中。

網絡基礎設施包括可重構路由交換平臺、智能光節點和相關鏈路等，其中可重構路由交換平臺是網絡基礎設施的核心。可重構路由交換平臺中的交換結構作為業務時延、時延抖動、分組丟失率等特性主要的影響組件，具有更加重要的作用，可以通過對交換資源分割，使各RSCN獨享交換資源，來滿足業務對QoS的需求。如圖1所示，R為可重構路由交換平臺，S為對應的交換資源(包括緩存、調度、交換結構等)，綜合管理接收用戶需求，生成RSCN構建命令，下發給各個可重構路由交換平臺，其中包括對交換結構的分割參數，可重構路由交換平臺接收命令，通過重構，將交換資源分割給各個承載網，完成不同承載網之間交換資源的隔離。其中，為承載網1對應交換結構，為承載網2對應交換結構，為承載網3對應交換結構，其他為未使用的交換資源。

圖1 可重構路由交換平臺交換結構空分示意

本文在面向服務提供的柔性網絡技術體系下，基于RSCN的構建，針對可重構路由交換平臺中Crossbar交換資源，以8× 8Crossbar的分域為例引出了輸入排隊Crossbar交換結構調度問題，提出了一種分域承載組調度算法，該算法在單個承載組內進行輪詢調度，域內進行最長隊列優先調度，推導了組內和域內的調度過程。并在交換性能仿真平臺SPES中進行了復雜度和時延特性的仿真，仿真結果表明：分域調度算法的調度復雜度小于不分域調度算法的調度復雜度，相對于傳統典型的調度算法，分域承載組調度算法具有更優的時延特性。

2 交換結構分域原理

2.1 面向RSCN的交換結構需求

RSCN與虛擬網構建不同之處在于：網絡環境和實現技術不同，虛擬網構建通過設備虛擬化的形式，選擇和設置虛擬節點，連接虛擬節點間的虛擬鏈路，而RSCN構建基于可重構路由交換設備的柔性網絡，通過設備的重構形式支持。構建拓撲不同，虛擬網拓撲和實際物理網絡拓撲是分離的，而RSCN拓撲與實際物理網絡拓撲是對應的。

在RSCN的構建中，網絡資源可抽象表示為G( V, E)，其中，V表示物理節點的集合，E表示物理鏈路的集合，?e∈E，c( e)表示鏈路e所能夠承載的最大帶寬。對于RSCN構建需求，可抽象表示為{Gv( Vv,Ev),D}，其中，Gv( Vv,Ev)表示RSCN的拓撲，Vv表示RSCN邏輯節點的集合，Ev表示RSCN邏輯鏈路的集合，D={dev|ev∈Ev}為邏輯鏈路ev的帶寬需求dev的集合。RSCN構建問題可描述為將邏輯鏈路映射到物理路徑，記作path( s, t)=Mlink(ev)，其中，s=Mnode(sv)，t=Mnode(tv)，path( s, t)表示s至t所經過的物理鏈路，Mlink(·)表示邏輯鏈路到物理路徑的映射關系，Mnode(·)表示邏輯節點到物理節點的映射關系。RSCN構建是求解在G( V, E)中構建一個子圖G′( V′, E′)，該子圖滿足：

且?e∈E′，鏈路e上的帶寬為

設f( e)表示鏈路e單位流量的帶寬所需的費用，對RSCN構建的設計目標是構建子圖G′( V′, E′)的費用最小化，如式(3)所示。

假設節點v'i∈V'的需求為{x11(e), x12(e),…,x1N(e);x21(e),…,x2N(e);…;xi1(e),…,xiN(e );…}，可轉換為如圖2所示的需求。

圖2 節點構建需求

其中，{RSCNki,Cki}表示k號服務承載在第i個端口的帶寬需求為Cij。在可重構路由交換平臺中，SE(switching element)為交換組件，FE(forwarding element)為轉發組件，LE(link element)為接口組件，其具體的實現方式見文獻[5]。在SE中，采用Crossbar交換結構的IQ調度。

2.2 Crossbar結構分域

對于輸入端口i，考慮到雙向傳輸的需求，則第k個承載網在輸入端口i的帶寬需求Input( Cki)等于第k個承載網在輸出端口i的帶寬需求Output( Cki)。定義承載網輸入矩陣為表示承載網在各輸入端口的分布，其生成過程如算法1。

算法1 R生成過程

由M'=RTR得交叉開關匹配矩陣M為

定義1 第n個調度域用SDn表示，滿足SDn( Ir)數據分組不到達SDn'(Or)，且SDn'(Ir)數據分組不到達SDn( Or)，其中，SDn( Ir/Or)為第n個調度域的任意輸入/輸出端口。

對于一個N×N的Crossbar交換結構，為了更清晰的說明分域原理，選擇N=8，如圖3(a)所示。Crossbar交換結構內部無阻塞，如果無出端口競爭，可實現輸入8個端口到輸出8個端口的數據交換。假設該結構被平均分割給3個調度域，即每個調度域需要該交換結構端口數量為2、3和3。共有種分法。假設其中調度域1需求的輸入端口為{1,4}，輸出端口為{1,4}，調度域2需求的輸入端口為{3,5,8}，輸出端口為{3,5,8}，調度域3需求的輸入端口為{2,6,7}，輸出端口為{2,6,7}，如圖3(b)所示，將每個交叉開關當作交換資源，平均分割成3個承載網調度域，其交換資源利用率為，因為有42個交叉開關在該分割周期內不再被控制，對該42個交叉開關進行關閉來實現分域調度。

假設N×N的Crossbar交換結構分割成n個端口數不等的承載網調度域，即n個承載網調度域，可用(N1, N2,…,Nn)來表示其占有的輸入總端口數，滿足N1+N2+…+Nn=N，則第i(1≤i≤n≤N)個調度域占用輸入端口數為Ni。其Crossbar交換資源利用率為

圖3 8×8交換結構分域示意

對于Crossbar交換資源利用率nλ來說，當n=1時，λmax=1，為傳統的無分域交換；當n=N時，，為N個點到點交換；當1＜n＜N時，，為分域交換。對于分域交換,當n=M0時，假設，共有種分域方式。通過分割成n個Ni×Ni, i=1,2,…,n 的調度域，減少單個調度域輸入輸出端口數，將集中式的N×N調度復雜度轉換為Ni×Ni調度復雜度。

3 分域承載組調度算法

3.1 輸入排隊調度

在分組交換路由技術的發展上，交叉（crossbar）矩陣在N較小時是一類實現無阻塞的理想交換結構，它的調度過程是先由調度器對活躍輸入端口進行無輸出端口爭用的配對，決定所有活躍輸入端口下一個時隙的輸出端口，而在下一個時隙進行傳輸。僅靠交換結構本身還無法實現無阻塞交換，必須與相應的緩存方式與調度算法相結合。輸出排隊（OQ）[6]調度，能夠為業務提供100%吞吐量、速率及時延方面的QoS保證，但需要交換結構的加速比達到N，當N較大時是很難實現的。

比較而言，輸入隊列（IQ）調度，只需交換單元和存儲單元工作在線速，采用虛擬輸出排隊（VOQ）機制解決隊頭阻塞問題。但輸入排隊交換結構的調度算法需要全局考慮交換結構所有輸入端口和輸出端口的帶寬使用，因此必須采用集中式的調度機制，其本質是一個雙向圖的匹配求解問題。集中式的調度機制使得在輸入排隊交換結構實現服務質量保障十分復雜。已提出的如最大權重匹配調度算法已經證明可以提供100%的吞吐量，然而其復雜度為O( N3logN)[7]，很難具有現實意義。文獻[8]致力于對最大權重匹配算法進行簡化，但是其復雜度降低有限，依然無法在高速環境下應用。另一種思路通過利用輸入排隊交換結構雙向圖匹配特征，采用隨機化思想[9]求解最大匹配的逼近匹配關系。但它僅從吞吐量單個方面優化調度性能，缺乏其他相關的服務質量保障措施。

雖然研究人員提出種種其他解決方案試圖降低MWM（maximum weight matching）和MSM（maximum size matching）的實現復雜度[10,11]，然而不加速條件下，這種復雜度降低是以犧牲IQ交換結構性能為代價的。通過對基于Crossbar輸入緩存調度的研究不難發現，影響緩存調度的一個關鍵因素是交換結構的輸入輸出端口數，如表1所示。

表1 輸入排隊調度算法復雜度與N的關系

為在復雜度和性能之間進行折中，研究人員逐步著眼于將基于時間戳和輪詢的調度算法進行結合。GRR(group round robin)[12]引入一種流分組策略將大量流聚類為“流組”，并采用基于時間戳的WF2Q（worst-case fair weighted fair queuing)算法[13]作為組間調度算法，DRR(deficit round-robin)算法[14]作為組內調度算法，提高算法的公平性和降低復雜度。在組數較小的常量假設下，GRR能基于現有算法獲得O(1)時間復雜度。當流速動態改變時，基于時間戳的調度策略無法提供恒定的GPS(generalized processor sharing)[15]相對時延。

FRR(fair round-robin)[16]組間采用基于時間戳的調度策略，組內采用輪詢的調度策略，能為流組i提供端到端時延上限。不足之處在于其“攤還”復雜度，在傳輸前FRR算法需要將組內分組組裝較大的“幀”，所以分組會經歷O( K)的組裝時延。

輪詢調度算法RR/GPFQ(round-robin/goup packet fair queuing)[17]將基于分組的GPS算法進行改進以支持流速率的動態調整，降低了算法復雜度，并獲得嚴格的時延上限，且能夠提供時延和公平性特性。RR/GPFQ算法的時延和公平性上限僅取決于給定組內或組群的流狀態，而不是分組數目N。

針對以上輸入調度和分層調度的不足之處，本文針對可重構服務承載網構建的特殊性，采用分層調度的思想，將調度過程分為2層，如圖4所示，第1層將單個RSCN對應一個調度組，進行承載組內調度(CGS, carrying group scheduling)；第2層進行組間的域調度(DS, domain scheduling)。

圖4 承載組調度示意

其中，隊列VOQkij緩存第k個承載網到達輸入端口i、去往輸出端口j的業務流fkij、N'為本調度域所包含的輸入端口數。具體而言，首先根據P個承載網劃分為P個承載組在每個承載組內采用改進的輪詢機制決定組內數據分組的調度順序。而后，DS采用基于最長隊列優先的調度機制決定各調度順序。

3.2 承載組內調度

針對本文承載組內調度借鑒文獻[18]中SRR調度算法，對LDRRWA進一步改進，采用平滑的DRR調度策略(SDRR, smoothed DRR)。

在單個承載網內，用rkij標識fkij的帶寬需求，用表示調度權重，如式(6)所示。

SDRR算法以“幀”組織一次輪詢調度過程，具體如算法2。行1)將承載組共享份額計數器CG_deficit清“0”。行2)～16)對至少輸出一個分組的流組成的鏈表acitve_list進行輪詢輸出，非空的流fijk將轉移到鏈表acitve_list′中，以進行第2輪分組的共享份額輪詢調度。如行17)～23)所示，該共享份額過程借用CG_deficit中份額來滿足部分不能支持本輪分組輸出的調度份額需求，出現負份額，在下一輪調度過程中，上次沒有借用到份額的流優先借用。

算法2 SDRR調度過程

3.3 域調度

域調度采用最長隊列優先(LQF, longest queue first)的調度方法，記為DSLQF。如圖3(a)所示，對于一個8× 8的無分割交換結構，二分圖匹配下的8× 8匹配矩陣表示為M(n)，其中，元素mij( n)表示第n時隙內輸入端口Ii( i=1,2,…,8)到輸出端口Oi( i=1,2,…,8)的交叉開關的狀態。

DS1可以表示為

DS2可以表示為

DS3可以表示為

二分圖匹配下的8× 8匹配矩陣為

其中，⊙為Hadamard積[19]。

其中，mkij(n)表示第n時隙內第k( k=1,2,3)個SD輸入端口Ii( i=1,2,…,8)到輸出端口Oi( i=1,2,…,8)的交叉開關的狀態。

對于基于隊長的調度算法，相應變化的有隊長矩陣、狀態矩陣和到達矩陣。其匹配矩陣由8× 8變為了N×N，假設其分割為W個SD，分別為

則其匹配矩陣為

無分割隊長矩陣L( n)表示為

其中，元素lij(n)表示第n時隙內輸入端口Ii( i=1,2,…,N)到輸出端口Oj(j=1,2,…,N)的VOQij隊列隊長，行向量-L→i(n)是輸入端口Ii的隊長向量，列向量(n)是輸出端口Oj的隊長向量。

有分割隊長矩陣L'( n)表示為

無分割到達矩陣A(n)表示為

其中，元素aij(n)表示第n時隙內輸入端口Ii( i=1,2,…,N)到 輸 出 端 口Oi( i=1,2,…,N)的VOQij隊列到達過程，行向量(n)是輸入端口Ii的到達向量。在容許流量模型下，需滿足條件

有分割到達矩陣A'(n)表示為

在容許流量模型下，需滿足條件

交換結構隊長矩陣迭代過程[20]為

無分割狀態矩陣Q(n)為

其中，元素mij( n)表示第n時隙內輸入端口Ii( i=1,2,…,N)到輸出端 口Oj(j=1,2,…,N)的VOQij隊列中信元的有無。

其狀態矩陣Q(n)迭代過程為

有分割狀態矩陣Q'(n)為

DS調度過程描述為

步驟1 調度器獲得交換結構分割參數Ck=同時令n=1,P=1,L'(0)=M'(0)=A'(0)=Q'(0)=[0]。

步驟2 在時隙n中有信元到達，狀態矩陣Q'( n)發生變化，qkij向其調度器發出請求，輸入端口Ii形成到達行向量(n)。

圖5 步驟4中無分割仲裁和有分割仲裁的比較

步驟4 優先級指針P指向輸出端口Op所對應的隊長矩陣列向量(n)中同一SD中權重最大（隊列最長）的元素eP，eP決定了M'(n)中第P列非0元素的位置。

步驟5 如果P=P+1modN≠1，重復步驟4；如果P=P+1modN=1，執行下一步。

步驟6 將{eP,P=1,2,…,N}送入M'(n)，n=n+1，轉向步驟2。

步驟4中無分割仲裁和有分割仲裁的比較如圖5所示，圖5(b)中以3個SD為例表示，可見步驟4中，對于無分割交換結構，其單次進行N個權值的仲裁，分割交換結構單次進行Nk個權值的仲裁，減小了仲裁復雜度。

4 仿真實驗

本文采用基于Crossbar交換性能仿真平臺SPES(switching performance evaluation system)[21]設計并實現了基于交換結構分域的輸入排隊調度算法。

在原來仿真平臺基礎上，增加了網絡承載控制系統，該系統配置或隨機生成調度域分割參數，并將參數傳遞給輸入端子系統、輸出端子系統和調度子系統，以決定其調度過程所對應的SD和Crossbar匹配點，其仿真結構如圖6所示。

1) 相對運算復雜度仿真

該仿真中假設平均分成3個SD，滿足不同SD端口數之差不大于1。圖7給出了傳統矩陣模型的LQF與域調度的DSLQF算法的相對運算復雜度比較曲線圖，相對運算復雜度是對調度算法中算術加法次數進行的相對比較結果。當交換結構端口數N依次從4增加到20時，相對運算復雜度曲線呈類指數迅速增加，傳統的LQF算法的相對運算復雜度大于DSLQF算法的相對運算復雜度。

相對運算復雜度的減小主要由交換結構SD的個數決定，如果SD分割個數增加，則其運算效率還會提高，但倍數低于SD個數。對于同一個Crossbar交換結構，DSLQF算法的相對運算復雜度隨SD個數增加而減小，但非線性關系。圖8為16× 16 Crossbar結構相對運算復雜度與SD個數關系圖，其SD對應端口數分割原則為：不同SD端口數之差不大于1。

圖6 加入分割參數的輸入排隊仿真平臺

圖7 SM-LQF與LQF相對運算復雜度比較

圖8 相對運算復雜度與SD個數關系

2) 不同負載時延仿真

時延仿真采用16×16的交換結構，cell長度為64byte，仿真業務選取了貝努利業務源和ON-OFF突發業務源，其中突發業務的突發長度為20，目的端口分布分別采用均勻分布和 Diagonal分布，Diagonal分布的表達式為

圖9(a)給出在貝努利均勻業務源條件下，各調度算法在歸一化負載強度區間[0 .6,1]的平均時延對比曲線，用 T(*)表示*調度算法的時延。可見，輸出排隊 FQ的T(FQ)最小， T(SDRR-DSLQF)次之，輸入排隊LQF的T(LQF)最大，分層調度算法的時延均小于非分層調度。LQF、DRR-LQF、SDRR-LQF和SDRRDSLQF 4種調度算法的時延比較，T(LQF)＞ T(DRR-LQF)表明分層調度的時延特性優于非分層調度，因為分層調度將調度過程分為組內調度和組間調度 2個部分，將輸入調度中整體集中式的復雜度變為局部調度復雜度之和，減小仲裁端口數，減小了算法復雜度。 T(DRR-LQF)＞T(SDRR-LQF)表明SDRR比DRR調度算法時延小，原因是SDRR的輪詢過程采用份額借用機制，使得單個時隙內更多信元被調度。

圖9 貝努利業務源時延對比

T(SDRR-LQF)＞T(SDRR-DSLQF)表明分域的調度比不分域調度時延小，原因是分域調度仲裁復雜度小。

圖 9(b)給出在貝努利 Diagonal業務源條件下，各調度算法在歸一化負載強度區間[0.6,1]的平均時延對比曲線。與圖 9(a)比較可見，非均勻業務源條件下的時延比均勻業務源條件下的時延大，非均勻業務源對輸出排隊FQ的T(FQ)影響最小，對輸入排隊LQF和iSLIP的時延影響最大，非均勻業務源輸入與均勻業務源輸入下的時延大小關系不變。

圖 10(a)給出在 ON-OFF突發均勻業務源條件下，各調度算法在歸一化負載強度區間[0 .6,1]的平均時延對比曲線。與圖9(a)比較可見，ON-OFF突發業務源輸入下的時延約為貝努利業務源輸入下時延的10倍，ON-OFF突發業務源對各算法時延的影響相同，ON-OFF突發業務源輸入與貝努利業務源輸入下各算法時延大小關系不變。

圖10 ON-OFF突發業務源時延對比

圖10(b)給出在ON-OFF突發Diagonal業務源條件下，各調度算法在歸一化負載強度區間[ ]0.6,1的平均時延對比曲線。與圖10(a)比較可見，非均勻突發業務源輸入下的時延大于均勻突發業務源輸入下的時延，在非均勻突發業務源條件下，輸入排隊LQF和iSLIP的時延增長迅速，非均勻突發業務源輸入下的時延與均勻突發業務源輸入下的時延大小關系不變。

對以上仿真結果分析得出如下結論：

1) 對于N×N的Crossbar交換結構，SD個數越大，相對運算復雜度越小，當個數為N時，每個SD只有一個端口，無需仲裁就可調度，可實現調度延遲為0。

2) 在 4種業務源輸入條件下，ON-OFF突發Diagonal業務源輸入下的時延最大。

3) 任何一種業務源輸入下，輸出排隊FQ調度算法的時延都是最小，且在均勻和非均勻業務源條件下保持穩定，可見輸出排隊雖然需要內部加速，但能為業務提供好的時延QoS保證。

4) 任何一種業務源輸入下，分層調度的時延總小于非分層調度的時延，主要原因是分層調度將調度過程分為組內調度和組間調度2個部分，將輸入調度中整體集中式的復雜度變為局部調度復雜度之和，減小仲裁端口數，減小了算法復雜度。

當然從理論上分析，該算法也存在一些不足:

1) Crossbar交換結構分域承載組調度的前提是在可重構網絡技術體系下構建 RSCN的需求，RSCN對輸入輸出端口的約束性條件形成了自封閉的調度域，域內包括幾個 RSCN的業務，且每個RSCN業務不全部使用域內輸入輸出端口。如果沒有這個前提，則該分域調度就會出現輸入到輸出交換路徑的不可達問題。

2) 分域承載組調度中的域分割參數是由網絡級可重構綜合管理系統下達，當單個網絡節點接收到該分割參數后，需要停機進行先分割再啟動后調度的過程，增加了宕機時延。

3) 分域承載組調度算法的設計需具有可重構性，即需要根據分割參數進行調度的變化，當N很大時，重構過程需確定大量關閉的Crossbar交叉節點，會提高一定的復雜度。

5 結束語

在目前對通信節點功能和性能要求越來越高的發展模式下，可以通過構建RSCN實現網絡級的優化，通過分割節點資源，尤其是節點內的交換資源，來滿足不同RSCN業務的區分服務。交換結構的分割帶來了調度算法的分割，業務特性需求（時延、抖動和分組丟失率等）的不同，對調度算法也有不同的要求，可采用單個調度域中部署不同調度算法來滿足要求，這樣就可以為特定的業務實現獨立的調度，采用交換資源獨享將QoS等級劃分。

[1] 張偉, 吳春明, 姜明. 網絡業務聚類研究[J]. 解放軍信息工程大學學報, 2009, 10(1):53-56.ZHANG W, WU C M, JIANG M. Study of network services aggregation[J]. Journal of Information Engineering University, 2009, 10(1):53-56.

[2] 龔雙瑾, 劉多, 張雪麗等.下一代網關鍵技術及發展[M]. 北京: 國防工業出版社, 2006.GONG S J, LIU D, ZHANG X L, et al. Key Technology and Development of Next Generation Network[M]. Beijing: National Defense Industry Press, 2006.

[3] CAPONE A, ELIAS J, MARTIGNON F. Routing and resource optimization in service overlay networks[J]. Elsevier Computer Networks,2009, 53(2):180-190.

[4] YU M, YI Y, REXFORD J. Rethinking virtual network embedding:substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communications Review, 2008, 38(2):17-29.

[5] ZHUGE B, YU C, LIU K P. Research on internal flow control mechanism of ForCES routers[J]. Information Technology Journal 2011 Asian Network for Scientific Information, 2011, 10(3):626-638.

[6] KESIDIS G, MCKEOWN N. Output-buffer ATM packet switching for integrated-services communicateon networks[A]. Proceedings of IEEE ICC’97[C]. Montreal, Canada, 1997. 342-350.

[7] MEKKITTIKUL A, MCKEOWN N. A practical scheduling algorithm for achieving 100% throughput in input-queued switches[A]. INFOCOM‘98[C]. San Francisco, CA, 1998. 792-799.

[8] MEKKITTIKUL A. Scheduling Non-uniform Traffic in High Speed Packet Switches and Routers[D]. Stanford University, 1998. 17-20.

[9] GIACCONE P, PRABHAKAR B, SHAH D. Towards simple highperformance schedulers for high-aggregate bandwidth switches[A].IEEE INFOCOM2002[C]. New York, USA, 2002. 120-127.

[10] LEE Y, LOU J Y, LUO J Z. An efficient packet scheduling algorithm with deadline guarantees for input-queued switches[J]. Journal IEEE/ACM Transitions on Networking, 2007, 15(1): 212-225.

[11] LEONARDI E, MELLIA M, NERI F. Design and implementation of a fast VOQ scheduler for a switch sabric[J]. IJCSNS International Journal of Computer Science and Network Security, 2008, 8(9):32-36.

[12] CAPRITA B, NIEH J, CHAN W C. Group round robin: improving the fairness and complexity of packet scheduling[A]. Proc of the ACM/IEEE ANCS[C]. Princeton, New Jersey, USA, 2005. 29-40.

[13] BENNETT J C R, ZHANG H. WF2Q: worst-case fair weighted fair queuing[A]. Proc of the IEEE INFOCOM[C]. New York, USA, 1996.120-128.

[14] SHREEDHAR M, VARGHESE G. Efficient fair queuing using deficit round robin[J]. IEEE/ACM Transactions on Networking, 1996, 4(3):375-385.

[15] PAREKH A K, GALLAGER R G. A generalized processor sharing approach to flow control in integrated services networks: the single-node case[J]. IEEE/ACM Transactions on Networking, 1993, 1(3):344-357.

[16] YUAN X, DUAN Z. FRR: a proportional and worst-case fair round robin scheduler[J]. IEEE Transactions on Computers, 2009, 58(3):365-379.

[17] COMER D, MARTYNOV M. Design and analysis of hybrid packet schedulers[A]. Proc of the IEEE INFOCOM 2008[C]. Phoenix, AZ,2008. 1570-1578.

[18] GUO C X. Improved smoothed round robin schedulers for high-speed packet networks[A]. Proc of the IEEE INFOCOM[C]. Phoenix, AZ,2008. 1579-1587.

[19] 張賢達. 矩陣分析與應用[M]. 北京: 清華大學出版社, 2004. 101-106.ZHANG X D. Matrix Analysis and Application[M]. Beijing: Tsinghua University Press, 2004. 101-106.

[20] 馬祥杰, 毛軍鵬, 蘭巨龍. 輸入排隊Crossbar架構下的矩陣模型及MM-LQF調度策略[J]. 電子學報, 2008, 36(1):9-16.MA X J, MAO J P, LAN J L. Matrix model for input-queued crossbar fabric and MM-LQF scheduling scheme[J]. Journal of Electronics,2008, 36(1):9-16.

[21] HU H C, YI P, GUO Y F. Design and implementation of high performance simulation platform for switching and scheduling[J]. Journal of Software, 2008, 19(4):1036-1050.