張博，汪斌強，王珊珊，衛(wèi)紅權(quán)，李揮

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

1 引言

互聯(lián)網(wǎng)基于資源統(tǒng)計復(fù)用、“盡力而為”服務(wù)模式的特點，輔以O(shè)verlay、CDN等技術(shù)拓展了其所承載的業(yè)務(wù)范圍，一定程度上滿足了規(guī)?；囊粢曨l業(yè)務(wù)、安全業(yè)務(wù)等承載要求，但并未從根本上解決互聯(lián)網(wǎng)面臨的安全、多播、QoS等問題。其根本原因在于一方面網(wǎng)絡(luò)是剛性的，網(wǎng)絡(luò)的設(shè)計與構(gòu)建依據(jù)特定業(yè)務(wù)需求進行，改造只能依靠升級和擴展，無法實現(xiàn)功能重構(gòu)；其二節(jié)點是封閉的，節(jié)點的升級和擴展只能由原提供商實施，無法實現(xiàn)開放。從而導(dǎo)致了互聯(lián)網(wǎng)的僵化問題。針對上述問題，擺脫傳統(tǒng)網(wǎng)絡(luò)技術(shù)體系束縛，提出了一種面向服務(wù)提供的柔性網(wǎng)絡(luò)技術(shù)體系。

面向服務(wù)提供的柔性網(wǎng)絡(luò)技術(shù)體系對現(xiàn)有和未來可能出現(xiàn)的用戶業(yè)務(wù)進行科學(xué)聚類[1]，業(yè)務(wù)的聚類方法有多種，因應(yīng)用環(huán)境不同而異，當(dāng)前主要是通過業(yè)務(wù)對服務(wù)質(zhì)量的要求進行聚類。還可以按照功能特征進行聚類，例如互聯(lián)網(wǎng)上的業(yè)務(wù)可以分為視頻、語音、交互式命令等。還可以按照通信方式的數(shù)量進行分類，將業(yè)務(wù)分為點到點業(yè)務(wù)、點到多點業(yè)務(wù)和多點到多點業(yè)務(wù)等[2]。

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

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

圖1 可重構(gòu)路由交換平臺交換結(jié)構(gòu)空分示意

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

2 交換結(jié)構(gòu)分域原理

2.1 面向RSCN的交換結(jié)構(gòu)需求

RSCN與虛擬網(wǎng)構(gòu)建不同之處在于：網(wǎng)絡(luò)環(huán)境和實現(xiàn)技術(shù)不同，虛擬網(wǎng)構(gòu)建通過設(shè)備虛擬化的形式，選擇和設(shè)置虛擬節(jié)點，連接虛擬節(jié)點間的虛擬鏈路，而RSCN構(gòu)建基于可重構(gòu)路由交換設(shè)備的柔性網(wǎng)絡(luò)，通過設(shè)備的重構(gòu)形式支持。構(gòu)建拓?fù)洳煌摂M網(wǎng)拓?fù)浜蛯嶋H物理網(wǎng)絡(luò)拓?fù)涫欠蛛x的，而RSCN拓?fù)渑c實際物理網(wǎng)絡(luò)拓?fù)涫菍?yīng)的。

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

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

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

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

圖2 節(jié)點構(gòu)建需求

其中，{RSCNki,Cki}表示k號服務(wù)承載在第i個端口的帶寬需求為Cij。在可重構(gòu)路由交換平臺中，SE(switching element)為交換組件，F(xiàn)E(forwarding element)為轉(zhuǎn)發(fā)組件，LE(link element)為接口組件，其具體的實現(xiàn)方式見文獻[5]。在SE中，采用Crossbar交換結(jié)構(gòu)的IQ調(diào)度。

2.2 Crossbar結(jié)構(gòu)分域

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

算法1 R生成過程

由M'=RTR得交叉開關(guān)匹配矩陣M為

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

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

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

圖3 8×8交換結(jié)構(gòu)分域示意

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

3 分域承載組調(diào)度算法

3.1 輸入排隊調(diào)度

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

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

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

表1 輸入排隊調(diào)度算法復(fù)雜度與N的關(guān)系

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

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

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

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

圖4 承載組調(diào)度示意

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

3.2 承載組內(nèi)調(diào)度

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

在單個承載網(wǎng)內(nèi)，用rkij標(biāo)識fkij的帶寬需求，用表示調(diào)度權(quán)重，如式(6)所示。

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

算法2 SDRR調(diào)度過程

3.3 域調(diào)度

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

DS1可以表示為

DS2可以表示為

DS3可以表示為

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

其中，⊙為Hadamard積[19]。

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

對于基于隊長的調(diào)度算法，相應(yīng)變化的有隊長矩陣、狀態(tài)矩陣和到達矩陣。其匹配矩陣由8× 8變?yōu)榱薔×N，假設(shè)其分割為W個SD，分別為

則其匹配矩陣為

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

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

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

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

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

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

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

交換結(jié)構(gòu)隊長矩陣迭代過程[20]為

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

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

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

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

DS調(diào)度過程描述為

步驟1 調(diào)度器獲得交換結(jié)構(gòu)分割參數(shù)Ck=同時令n=1,P=1,L'(0)=M'(0)=A'(0)=Q'(0)=[0]。

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

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

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

步驟5 如果P=P+1modN≠1，重復(fù)步驟4；如果P=P+1modN=1，執(zhí)行下一步。

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

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

4 仿真實驗

本文采用基于Crossbar交換性能仿真平臺SPES(switching performance evaluation system)[21]設(shè)計并實現(xiàn)了基于交換結(jié)構(gòu)分域的輸入排隊調(diào)度算法。

在原來仿真平臺基礎(chǔ)上，增加了網(wǎng)絡(luò)承載控制系統(tǒng)，該系統(tǒng)配置或隨機生成調(diào)度域分割參數(shù)，并將參數(shù)傳遞給輸入端子系統(tǒng)、輸出端子系統(tǒng)和調(diào)度子系統(tǒng)，以決定其調(diào)度過程所對應(yīng)的SD和Crossbar匹配點，其仿真結(jié)構(gòu)如圖6所示。

1) 相對運算復(fù)雜度仿真

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

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

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

圖7 SM-LQF與LQF相對運算復(fù)雜度比較

圖8 相對運算復(fù)雜度與SD個數(shù)關(guān)系

2) 不同負(fù)載時延仿真

時延仿真采用16×16的交換結(jié)構(gòu)，cell長度為64byte，仿真業(yè)務(wù)選取了貝努利業(yè)務(wù)源和ON-OFF突發(fā)業(yè)務(wù)源，其中突發(fā)業(yè)務(wù)的突發(fā)長度為20，目的端口分布分別采用均勻分布和 Diagonal分布，Diagonal分布的表達式為

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

圖9 貝努利業(yè)務(wù)源時延對比

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

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

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

圖10 ON-OFF突發(fā)業(yè)務(wù)源時延對比

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

對以上仿真結(jié)果分析得出如下結(jié)論：

1) 對于N×N的Crossbar交換結(jié)構(gòu)，SD個數(shù)越大，相對運算復(fù)雜度越小，當(dāng)個數(shù)為N時，每個SD只有一個端口，無需仲裁就可調(diào)度，可實現(xiàn)調(diào)度延遲為0。

2) 在 4種業(yè)務(wù)源輸入條件下，ON-OFF突發(fā)Diagonal業(yè)務(wù)源輸入下的時延最大。

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

4) 任何一種業(yè)務(wù)源輸入下，分層調(diào)度的時延總小于非分層調(diào)度的時延，主要原因是分層調(diào)度將調(diào)度過程分為組內(nèi)調(diào)度和組間調(diào)度2個部分，將輸入調(diào)度中整體集中式的復(fù)雜度變?yōu)榫植空{(diào)度復(fù)雜度之和，減小仲裁端口數(shù)，減小了算法復(fù)雜度。

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

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

2) 分域承載組調(diào)度中的域分割參數(shù)是由網(wǎng)絡(luò)級可重構(gòu)綜合管理系統(tǒng)下達，當(dāng)單個網(wǎng)絡(luò)節(jié)點接收到該分割參數(shù)后，需要停機進行先分割再啟動后調(diào)度的過程，增加了宕機時延。

3) 分域承載組調(diào)度算法的設(shè)計需具有可重構(gòu)性，即需要根據(jù)分割參數(shù)進行調(diào)度的變化，當(dāng)N很大時，重構(gòu)過程需確定大量關(guān)閉的Crossbar交叉節(jié)點，會提高一定的復(fù)雜度。

5 結(jié)束語

在目前對通信節(jié)點功能和性能要求越來越高的發(fā)展模式下，可以通過構(gòu)建RSCN實現(xiàn)網(wǎng)絡(luò)級的優(yōu)化，通過分割節(jié)點資源，尤其是節(jié)點內(nèi)的交換資源，來滿足不同RSCN業(yè)務(wù)的區(qū)分服務(wù)。交換結(jié)構(gòu)的分割帶來了調(diào)度算法的分割，業(yè)務(wù)特性需求（時延、抖動和分組丟失率等）的不同，對調(diào)度算法也有不同的要求，可采用單個調(diào)度域中部署不同調(diào)度算法來滿足要求，這樣就可以為特定的業(yè)務(wù)實現(xiàn)獨立的調(diào)度，采用交換資源獨享將QoS等級劃分。

[1] 張偉, 吳春明, 姜明. 網(wǎng)絡(luò)業(yè)務(wù)聚類研究[J]. 解放軍信息工程大學(xué)學(xué)報, 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] 龔雙瑾, 劉多, 張雪麗等.下一代網(wǎng)關(guān)鍵技術(shù)及發(fā)展[M]. 北京: 國防工業(yè)出版社, 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] 張賢達. 矩陣分析與應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2004. 101-106.ZHANG X D. Matrix Analysis and Application[M]. Beijing: Tsinghua University Press, 2004. 101-106.

[20] 馬祥杰, 毛軍鵬, 蘭巨龍. 輸入排隊Crossbar架構(gòu)下的矩陣模型及MM-LQF調(diào)度策略[J]. 電子學(xué)報, 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.