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

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

1 引言

互聯(lián)網(wǎng)基于資源統(tǒng)計(jì)復(fù)用、“盡力而為”服務(wù)模式的特點(diǎn)，輔以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è)計(jì)與構(gòu)建依據(jù)特定業(yè)務(wù)需求進(jìn)行，改造只能依靠升級(jí)和擴(kuò)展，無法實(shí)現(xiàn)功能重構(gòu)；其二節(jié)點(diǎn)是封閉的，節(jié)點(diǎn)的升級(jí)和擴(kuò)展只能由原提供商實(shí)施，無法實(shí)現(xiàn)開放。從而導(dǎo)致了互聯(lián)網(wǎng)的僵化問題。針對(duì)上述問題，擺脫傳統(tǒng)網(wǎng)絡(luò)技術(shù)體系束縛，提出了一種面向服務(wù)提供的柔性網(wǎng)絡(luò)技術(shù)體系。

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

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

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

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

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

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

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

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

在RSCN的構(gòu)建中，網(wǎng)絡(luò)資源可抽象表示為G( V, E)，其中，V表示物理節(jié)點(diǎn)的集合，E表示物理鏈路的集合，?e∈E，c( e)表示鏈路e所能夠承載的最大帶寬。對(duì)于RSCN構(gòu)建需求，可抽象表示為{Gv( Vv,Ev),D}，其中，Gv( Vv,Ev)表示RSCN的拓?fù)?，Vv表示RSCN邏輯節(jié)點(diǎn)的集合，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é)點(diǎn)到物理節(jié)點(diǎn)的映射關(guān)系。RSCN構(gòu)建是求解在G( V, E)中構(gòu)建一個(gè)子圖G′( V′, E′)，該子圖滿足：

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

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

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

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

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

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

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

算法1 R生成過程

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

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

對(duì)于一個(gè)N×N的Crossbar交換結(jié)構(gòu)，為了更清晰的說明分域原理，選擇N=8，如圖3(a)所示。Crossbar交換結(jié)構(gòu)內(nèi)部無阻塞，如果無出端口競(jìng)爭(zhēng)，可實(shí)現(xiàn)輸入8個(gè)端口到輸出8個(gè)端口的數(shù)據(jù)交換。假設(shè)該結(jié)構(gòu)被平均分割給3個(gè)調(diào)度域，即每個(gè)調(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)所示，將每個(gè)交叉開關(guān)當(dāng)作交換資源，平均分割成3個(gè)承載網(wǎng)調(diào)度域，其交換資源利用率為，因?yàn)橛?2個(gè)交叉開關(guān)在該分割周期內(nèi)不再被控制，對(duì)該42個(gè)交叉開關(guān)進(jìn)行關(guān)閉來實(shí)現(xiàn)分域調(diào)度。

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

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

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

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

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

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

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

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

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

為在復(fù)雜度和性能之間進(jìn)行折中，研究人員逐步著眼于將基于時(shí)間戳和輪詢的調(diào)度算法進(jìn)行結(jié)合。GRR(group round robin)[12]引入一種流分組策略將大量流聚類為“流組”，并采用基于時(shí)間戳的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)時(shí)間復(fù)雜度。當(dāng)流速動(dòng)態(tài)改變時(shí)，基于時(shí)間戳的調(diào)度策略無法提供恒定的GPS(generalized processor sharing)[15]相對(duì)時(shí)延。

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

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

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

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

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

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

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

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

SDRR算法以“幀”組織一次輪詢調(diào)度過程，具體如算法2。行1)將承載組共享份額計(jì)數(shù)器CG_deficit清“0”。行2)～16)對(duì)至少輸出一個(gè)分組的流組成的鏈表acitve_list進(jìn)行輪詢輸出，非空的流fijk將轉(zhuǎn)移到鏈表acitve_list′中，以進(jìn)行第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)度采用最長(zhǎng)隊(duì)列優(yōu)先(LQF, longest queue first)的調(diào)度方法，記為DSLQF。如圖3(a)所示，對(duì)于一個(gè)8× 8的無分割交換結(jié)構(gòu)，二分圖匹配下的8× 8匹配矩陣表示為M(n)，其中，元素mij( n)表示第n時(shí)隙內(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時(shí)隙內(nèi)第k( k=1,2,3)個(gè)SD輸入端口Ii( i=1,2,…,8)到輸出端口Oi( i=1,2,…,8)的交叉開關(guān)的狀態(tài)。

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

則其匹配矩陣為

無分割隊(duì)長(zhǎng)矩陣L( n)表示為

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

有分割隊(duì)長(zhǎng)矩陣L'( n)表示為

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟4 優(yōu)先級(jí)指針P指向輸出端口Op所對(duì)應(yīng)的隊(duì)長(zhǎng)矩陣列向量(n)中同一SD中權(quán)重最大（隊(duì)列最長(zhǎng)）的元素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個(gè)SD為例表示，可見步驟4中，對(duì)于無分割交換結(jié)構(gòu)，其單次進(jìn)行N個(gè)權(quán)值的仲裁，分割交換結(jié)構(gòu)單次進(jìn)行Nk個(gè)權(quán)值的仲裁，減小了仲裁復(fù)雜度。

4 仿真實(shí)驗(yàn)

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

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

1) 相對(duì)運(yùn)算復(fù)雜度仿真

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4) 任何一種業(yè)務(wù)源輸入下，分層調(diào)度的時(shí)延總小于非分層調(diào)度的時(shí)延，主要原因是分層調(diào)度將調(diào)度過程分為組內(nèi)調(diào)度和組間調(diào)度2個(gè)部分，將輸入調(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對(duì)輸入輸出端口的約束性條件形成了自封閉的調(diào)度域，域內(nèi)包括幾個(gè) RSCN的業(yè)務(wù)，且每個(gè)RSCN業(yè)務(wù)不全部使用域內(nèi)輸入輸出端口。如果沒有這個(gè)前提，則該分域調(diào)度就會(huì)出現(xiàn)輸入到輸出交換路徑的不可達(dá)問題。

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

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

5 結(jié)束語

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

[1] 張偉, 吳春明, 姜明. 網(wǎng)絡(luò)業(yè)務(wù)聚類研究[J]. 解放軍信息工程大學(xué)學(xué)報(bào), 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]. 北京: 國(guó)防工業(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] 張賢達(dá). 矩陣分析與應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2004. 101-106.ZHANG X D. Matrix Analysis and Application[M]. Beijing: Tsinghua University Press, 2004. 101-106.

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