基于緩解HoL堵塞的單組播混合調(diào)度算法

袁龍， 熊慶旭， 蕭翰

(北京航空航天大學(xué) 電子信息工程學(xué)院, 北京 100083)

隨著網(wǎng)絡(luò)應(yīng)用的發(fā)展，網(wǎng)絡(luò)所承載的業(yè)務(wù)類型從單一類型逐漸向多元化發(fā)展，交換機(jī)不僅需要支持純單播業(yè)務(wù)或純組播業(yè)務(wù)分組轉(zhuǎn)發(fā)，還需要有效調(diào)度單組播混合業(yè)務(wù)。

輸出排隊(duì)(Output Queued,OQ)結(jié)構(gòu)的通過(guò)率為100%，可提供QoS確保功能，但存在N倍加速比，不易于擴(kuò)展[1]。輸入排隊(duì)(Input Queued,IQ)結(jié)構(gòu)加速比為1，可擴(kuò)展性強(qiáng)，但需采用虛擬輸出排隊(duì)(Virtual Output Queuing,VOQ)[2]結(jié)構(gòu)克服頭分組(Head of Line,HoL)堵塞[3]問(wèn)題。對(duì)于單播業(yè)務(wù)只需在每個(gè)輸入端口配置N個(gè)虛擬隊(duì)列，但組播業(yè)務(wù)分組扇出類型多達(dá)2N-1種，則需要在每個(gè)輸入端口放置2N-1個(gè)隊(duì)列[4]，難以在大規(guī)模交換機(jī)中實(shí)用化。目前的研究通常配置k(1

隨著集成電路技術(shù)的發(fā)展，聯(lián)合輸入交叉排隊(duì)(Combined Input and Crossbar Queued，CICQ)被普遍認(rèn)為最值得期待的高性能分組交換結(jié)構(gòu),但 CICQ結(jié)構(gòu)單組播混合業(yè)務(wù)調(diào)度算法研究不多。早期主要以單播調(diào)度或組播調(diào)度為主，在單播調(diào)度中[5-7]，文獻(xiàn)[7]提出的交叉緩存隊(duì)列均衡(Crossbuffer Queue Balance,CQB)算法從定量的角度出發(fā)，以交換機(jī)實(shí)現(xiàn)work-conserving狀態(tài)為追求目標(biāo)，使交換機(jī)的性能得到顯著提升。在組播調(diào)度中，Mhamdi和Hamdi提出了組播交叉結(jié)點(diǎn)輪詢(Multicast Cross-Points Round Robin,MXRR)算法[8]，由于輸入端口中僅采用單FIFO(First In First Out)隊(duì)列，存在嚴(yán)重的HoL堵塞問(wèn)題。文獻(xiàn)[9]提出了輪詢(Round Robin,RR)、最小扇出優(yōu)先(Minimum Residue First,MRF)、最大服務(wù)優(yōu)先(Maximum Service First,MSF)以及最大服務(wù)率優(yōu)先(Maximum Ratio of Service First,MRSF)等調(diào)度算法，并在輸入端口采用多個(gè)組播隊(duì)列，從結(jié)構(gòu)上緩解了組播HoL堵塞，提高了交換機(jī)的通過(guò)率降低了平均分組時(shí)延。為了滿足單播組播混合業(yè)務(wù)調(diào)度的需求，Mhamdi和Vassiliadis提出了單組播輪詢調(diào)度(Multicast and Unicast Round robin Scheduling,MURS)算法[10]，采用不同的優(yōu)先級(jí)輪詢調(diào)度單組播業(yè)務(wù)。雖然算法復(fù)雜度低，但整體性能欠佳。Yi等提出的低代價(jià)組播調(diào)度(Low-Cost Multicast Scheduling,LCMS)算法[11]，考慮了單組播業(yè)務(wù)之間的差異性，基于權(quán)重裁決單組播之間的競(jìng)爭(zhēng)，算法的性能有一定提升，但輸入端口僅采用一個(gè)組播隊(duì)列，導(dǎo)致了較嚴(yán)重的HoL堵塞。梁佳誠(chéng)等提出的均衡交叉節(jié)點(diǎn)緩存單組播調(diào)度(Multicast and Unicast Crossbuffer Balance,MUCB)算法[12]，與以往基于輪詢或者基于權(quán)重的調(diào)度算法不同，而是采用了均衡交叉節(jié)點(diǎn)緩存占用的思路，使交換機(jī)最大程度地逼近work-conserving狀態(tài)。雖然MUCB算法使交換機(jī)的性能有了較好的改善，但沒(méi)有采取有效機(jī)制以緩解HoL堵塞。

為了緩解組播HoL堵塞問(wèn)題，通常在輸入端口配置k個(gè)組播隊(duì)列。因此，新到達(dá)分組需要按照一定的入隊(duì)策略選擇合適的隊(duì)列入隊(duì)。在已有研究中，多數(shù)基于三大準(zhǔn)則[9]提出相應(yīng)的入隊(duì)策略，主要分為2類：

1) 靜態(tài)入隊(duì)策略，如文獻(xiàn)[13]提出Module入隊(duì)策略，利用分組扇出數(shù)取余的方法選擇隊(duì)列，即：i=Fmodk；實(shí)現(xiàn)簡(jiǎn)單，但扇出數(shù)目相同卻不相關(guān)的分組會(huì)進(jìn)入同一緩存隊(duì)列，且對(duì)于小扇出分組均衡性差。文獻(xiàn)[14]提出加權(quán)取模(Weighted Module,WM)入隊(duì)策略改善了Module中小扇出組播均衡效果差的問(wèn)題。文獻(xiàn)[15]提出特征向量法(vector)選擇分組扇出與隊(duì)列特征向量距離最小的隊(duì)列入隊(duì)，增加了頭分組扇出差異性，但負(fù)載均衡的效果一般。

2) 動(dòng)態(tài)入隊(duì)策略，如文獻(xiàn)[9]提出的面向分組輪詢分配(Cell oriented Round-Robin Assignment,CRRA)、面向突發(fā)輪詢分配(Burst oriented Round-Robin Assignment,BRRA)、面向最短隊(duì)列分組優(yōu)先(Cell oriented Shortest Queue First,CSQF)和面向最短突發(fā)隊(duì)列優(yōu)先(Burst oriented Shortest Queue First,BSQF)等入隊(duì)策略，存在分組失序問(wèn)題。

本文通過(guò)研究HoL堵塞與work-conserving之間的關(guān)系，基于CICQ結(jié)構(gòu)提出一種新的單組播混合調(diào)度算法, 即單組播低HoL堵塞(Multicast and Unicast with Low HoL Blocking,MULHB)算法，其基本思想就是以緩解HoL堵塞為目標(biāo)，使交換機(jī)逼近work-conserving狀態(tài)。同時(shí)，為了進(jìn)一步緩解HoL堵塞，本文提出一種新的組播分組入隊(duì)策略, 即動(dòng)態(tài)組播分組入隊(duì)(Dynamic Muticast Queuing,DMQ) 策略，使新到達(dá)分組根據(jù)緩存隊(duì)列的狀態(tài)可以動(dòng)態(tài)選擇合適的隊(duì)列入隊(duì)。

本文首先對(duì)CICQ結(jié)構(gòu)單組播混合調(diào)度中的主要問(wèn)題進(jìn)行了分析；然后，具體說(shuō)明了DMQ策略以及MULHB算法；最后，給出了本文提出算法的仿真結(jié)果，并和當(dāng)前主流的單組播混合調(diào)度算法進(jìn)行比較和分析。

1 問(wèn)題分析

本文討論的CICQ交換結(jié)構(gòu)如圖1所示。每個(gè)輸入端口分別配置N個(gè)單播隊(duì)列和k(1

CICQ結(jié)構(gòu)work-conserving狀態(tài)是指，任一時(shí)隙中若交換機(jī)中存在去往某個(gè)輸出端口的分組，則該時(shí)隙必有分組離開(kāi)該輸出端口。由于輸入端口中組播隊(duì)列的數(shù)目受到限制，因此，在調(diào)度過(guò)程中，屬于同一組播隊(duì)列的分組扇出去向不完全一致。此時(shí)，若組播隊(duì)列的后續(xù)分組中存在使交換機(jī)滿足work-conserving狀態(tài)的扇出去向，而頭分組中不存在，則發(fā)生了由HoL堵塞引起的非work-conserving問(wèn)題。由于考慮整個(gè)組播隊(duì)列中全部后續(xù)分組的扇出過(guò)于復(fù)雜，本文算法中僅考慮頭分組對(duì)次分組的堵塞造成的影響。

為了盡量解決由HoL堵塞引起的非work-conserving狀態(tài)，在每一時(shí)隙中，分組入隊(duì)后、輸入調(diào)度前，應(yīng)使所有輸入端口中存在若干不屬于同一端口的頭分組的扇出去向可以完全覆蓋所有傳輸需求但對(duì)應(yīng)節(jié)點(diǎn)緩存列為空的輸出端口。為了達(dá)到上述條件，首先，可以通過(guò)入隊(duì)策略動(dòng)態(tài)調(diào)整新到達(dá)分組在隊(duì)列排隊(duì)狀態(tài)。已有實(shí)用的靜態(tài)入隊(duì)策略由于選擇隊(duì)列的方式固定，分組入隊(duì)后，相同扇出類型的分組不能根據(jù)調(diào)度的需求重新選擇合適的隊(duì)列入隊(duì)。同時(shí)，仿真統(tǒng)計(jì)發(fā)現(xiàn)在調(diào)度過(guò)程中，輸入端口內(nèi)的緩存隊(duì)列出現(xiàn)大量為空的狀態(tài)。因此，入隊(duì)策略應(yīng)當(dāng)使新到達(dá)分組根據(jù)當(dāng)前緩存隊(duì)列的狀態(tài)動(dòng)態(tài)選擇合適的隊(duì)列入隊(duì)，尤其存在可選的空隊(duì)列時(shí)，應(yīng)充分選擇空隊(duì)列入隊(duì)，使輸入端口中頭分組的扇出差異性增大。其次，為了使交換機(jī)達(dá)到高通過(guò)率及低時(shí)延的目標(biāo)，應(yīng)盡可能使交換機(jī)處于work-conserving狀態(tài)。從文獻(xiàn)[7]中給出交換機(jī)實(shí)現(xiàn)work-conserving的條件可知，在輸入調(diào)度之后，所有的有傳輸需求的輸出端口對(duì)應(yīng)節(jié)點(diǎn)緩存列均不為空，從而使得輸出端口總有分組離開(kāi)。在此基礎(chǔ)上，輸入調(diào)度后，應(yīng)使有助于交換機(jī)逼近work-conserving狀態(tài)的次分組盡快成為頭分組。最后，輸出調(diào)度應(yīng)盡快調(diào)度節(jié)點(diǎn)緩存中可能導(dǎo)致發(fā)生HoL堵塞的分組離開(kāi)交換機(jī)。

圖1 CICQ交換結(jié)構(gòu)Fig.1 CICQ switch architecture

此外，在輸入端口中采用的緩存配置方式對(duì)單播和組播分組進(jìn)行隔離處理。由于2種業(yè)務(wù)之間存在一定的差異性，當(dāng)輸入調(diào)度在選擇分組進(jìn)入節(jié)點(diǎn)緩存內(nèi)時(shí)，需要采用一定的裁決機(jī)制解決單、組播分組之間的競(jìng)爭(zhēng)問(wèn)題，以避免“餓死”現(xiàn)象發(fā)生。

2 DMQ-MULHB調(diào)度算法

由第1節(jié)分析可知，為使交換機(jī)避免發(fā)生由HoL堵塞引起的非work-conserving狀態(tài)，本文采用新的入隊(duì)策略控制分組入隊(duì)，同時(shí)結(jié)合相應(yīng)的輸入輸出調(diào)度算法使交換機(jī)盡可能在分組入隊(duì)后、輸入調(diào)度前，所有輸入端口中存在若干不屬于同一端口的頭分組的扇出去向可以完全覆蓋有傳輸需求但對(duì)應(yīng)節(jié)點(diǎn)緩存列為空的輸出端口。本節(jié)將從入隊(duì)策略、輸入調(diào)度和輸出調(diào)度等環(huán)節(jié)詳細(xì)分析DMQ-MULHB調(diào)度算法的設(shè)計(jì)。

2.1 入隊(duì)策略

當(dāng)輸入端口i有組播分組到達(dá)時(shí)，選擇入隊(duì)隊(duì)列的具體步驟如下：

1) 分組到達(dá)時(shí)，若H[p]≠0,選擇隊(duì)列號(hào)等于F[p]值的隊(duì)列入隊(duì)，入隊(duì)結(jié)束；否則進(jìn)入步驟2)。

2) 若存在空隊(duì)列，選擇分組扇出與隊(duì)列特征向量差異最小的隊(duì)列，進(jìn)入步驟5)；否則進(jìn)入步驟3)。

3) 若存在隊(duì)長(zhǎng)為1的隊(duì)列，選擇分組與頭分組扇出差異最小的隊(duì)列，進(jìn)入步驟5)；否則進(jìn)入步驟4)。

4) 選擇分組與隊(duì)尾分組扇出差異最小的隊(duì)列；若存在多個(gè)，則選擇最短隊(duì)列。

5)F[p]更新為所選隊(duì)列序號(hào)，H[p]加1，選擇F[p]對(duì)應(yīng)隊(duì)列入隊(duì)，入隊(duì)結(jié)束。當(dāng)索引值為p的頭分組在輸入端口完全扇出時(shí)，H[p]減1。

由上述步驟可知，首先，步驟1)限定了新到達(dá)分組重新選擇隊(duì)列入隊(duì)的條件，只有當(dāng)該輸入端口中相同扇出類型的分組緩存數(shù)目為零時(shí)，才能重新選擇隊(duì)列入隊(duì)，該機(jī)制避免發(fā)生亂序；其次，步驟2)允許可重新選擇隊(duì)列的新到達(dá)組播分組進(jìn)入空隊(duì)列增加端口中頭分組扇出差異，使隊(duì)列頭分組獲得更多調(diào)度機(jī)會(huì)，以緩解了HoL堵塞，使交換機(jī)盡量逼近work-conserving狀態(tài)。最后，步驟3)～步驟5)對(duì)于緩存分組具有均衡作用，同時(shí)盡量減少相鄰分組間的扇出差異，當(dāng)前一分組成為頭分組時(shí)，可以緩解頭分組對(duì)次分組造成的HoL堵塞。

2.2 MULHB調(diào)度算法

本文提出MULHB算法，在輸入調(diào)度過(guò)程中，首先，找出有傳輸需求且對(duì)應(yīng)節(jié)點(diǎn)緩存列為空的輸出端口；其次，找出扇出去向包含上述輸出端口且頭分組扇出去向類型數(shù)最少的輸入端口；再次，從上述輸入端口中找出滿足工作保持狀態(tài)的頭分組；最后，從中優(yōu)先選擇可以完全扇出且對(duì)應(yīng)次分組有助于交換機(jī)逼近work-conserving狀態(tài)的頭分組進(jìn)行傳輸。在輸入調(diào)度中盡量使交換機(jī)既在當(dāng)前時(shí)隙實(shí)現(xiàn)work-conserving狀態(tài)，又使輸入端口中頭分組扇出在后續(xù)時(shí)隙盡可能覆蓋所有有傳輸需求的輸出端口，從而避免交換機(jī)發(fā)生由HoL堵塞引起的非work-conserving狀態(tài)。另外，在裁決單、組播分組之間的競(jìng)爭(zhēng)時(shí)，組播分組的權(quán)重以頭、次分組扇出、節(jié)點(diǎn)緩存狀態(tài)以及頭分組等待時(shí)間作為權(quán)重因子，單播分組的權(quán)重以等待時(shí)間作為權(quán)重因子?；跈?quán)重比較完成，避免“餓死”現(xiàn)象發(fā)生。在輸出調(diào)度過(guò)程中，輸出調(diào)度優(yōu)先選擇其次分組有助于交換機(jī)在后續(xù)時(shí)隙逼近work-conserving狀態(tài)的頭分組對(duì)應(yīng)的節(jié)點(diǎn)緩存中的分組進(jìn)行輸出。

輸入調(diào)度算法：

1) 初始化集合O包含所有輸出端口，集合I包含所有輸入端口。

2) 若集合O為空，則結(jié)束該時(shí)隙輸入調(diào)度。

3) 從集合O的第1個(gè)元素開(kāi)始，找出max{yj}對(duì)應(yīng)輸出端口j，若max{yj}=0，進(jìn)入步驟11)。

4) 若集合J為空，從集合O中剔除輸出端口j，回到步驟2)。

5) 從J的第1個(gè)元素開(kāi)始，選擇其中min{Di}對(duì)應(yīng)輸入端口i；找出輸入端口i中存在扇出去向包含輸出端口j且可完全扇出的組播頭分組，進(jìn)入下一步；否則，進(jìn)入步驟8)。

6) 若步驟5)找出的頭分組中存在次分組滿足Sik>0，則選擇max{Sik}對(duì)應(yīng)的組播隊(duì)列，進(jìn)入步驟9)；否則，進(jìn)入步驟7)。

10) 從集合I中剔除輸入端口i，更新U、J、Y，回到步驟3)。

11) 若集合I為空，該時(shí)隙輸入調(diào)度結(jié)束。

12) 從集合I的第1個(gè)元素開(kāi)始，若Mi中存在可完全扇出的頭分組，進(jìn)入步驟13)，否則，進(jìn)入步驟15)。

13) 若Mi中存在次分組滿足Sik>0，則選擇max{Sik}對(duì)應(yīng)的組播隊(duì)列，進(jìn)入步驟16)；否則，進(jìn)入步驟14)。

輸出調(diào)度算法：

1) 初始化集合O包含全部輸出端口，集合I包含全部輸入端口。

2)若集合O為空，則結(jié)束該時(shí)隙輸出調(diào)度。

3) 從O的第1個(gè)元素開(kāi)始，從輸入端口中找出所有包含輸出端口j扇出去向且狀態(tài)不為空的Xij對(duì)應(yīng)的隊(duì)列；若存在，進(jìn)入下一步；否則進(jìn)入步驟7)。

4) 若步驟3)中找出的隊(duì)列中存在次分組滿足Sik>0，則選擇max{Sik}對(duì)應(yīng)的組播隊(duì)列；否則，進(jìn)入步驟6)。

6) 輸出Xij中分組，從集合O中剔除輸出端口j，回到步驟2)。

3 仿真及對(duì)比分析

本節(jié)將基于CICQ交換結(jié)構(gòu)對(duì)DMQ-MULHB算法進(jìn)行仿真并對(duì)其性能進(jìn)行評(píng)估。仿真采用Bernoulli和ON-OFF兩種業(yè)務(wù)作為業(yè)務(wù)源模型。交換結(jié)構(gòu)的端口規(guī)模為16×16，仿真時(shí)間為100萬(wàn)個(gè)時(shí)隙，每個(gè)輸入端口設(shè)有8個(gè)組播隊(duì)列。其中ON-OFF業(yè)務(wù)的平均突發(fā)長(zhǎng)度為16。為了方便對(duì)性能進(jìn)行分析，同時(shí)給出了最大扇出優(yōu)先和最大服務(wù)比率優(yōu)先(Maxfanout First and Maximum Ratio of Service First,MF-MRSF)算法、MUCB算法以及OQ調(diào)度的仿真結(jié)果進(jìn)行對(duì)比，其中MF-MRSF算法、MUCB算法均采用Module入隊(duì)策略。

3.1 流量模型

在本次仿真中，假設(shè)單播業(yè)務(wù)占比f(wàn)u，組播業(yè)務(wù)占比f(wàn)m，組播分組平均扇出為|φ|，輸入負(fù)載為λ，輸出負(fù)載為μ，仿真結(jié)果中的負(fù)載均為輸出負(fù)載，在單組播混合調(diào)度中，輸入與輸出負(fù)載之間的關(guān)系滿足μ=λ(fu+|φ|fm)。

仿真中的非均勻業(yè)務(wù)為弱對(duì)角業(yè)務(wù)，對(duì)于輸入端口i，其到達(dá)分組去向分布為

其中：uij為輸入端口i的分組到達(dá)時(shí)，去往輸出端口j的概率；ui為輸入負(fù)載；ω為非均勻因子，仿真中將ω設(shè)為0.5。

3.2 均勻業(yè)務(wù)

低負(fù)載情況下，不同算法的性能差異性相對(duì)較小，本文給出高負(fù)載情況下的通過(guò)率及平均時(shí)延對(duì)比。

表1、表2給出了均勻業(yè)務(wù)下，fm=0.8時(shí)，各算法在歸一化負(fù)載為0.90、0.95、0.99的通過(guò)率?？梢钥闯觯煌?fù)載下，MULHB算法的通過(guò)率高于MF-MRSF及MUCB算法。

圖2給出了均勻業(yè)務(wù)下平均時(shí)延的對(duì)比結(jié)果。從圖中可以看出，MULHB算法的時(shí)延性能優(yōu)于MF-MRSF及MUCB算法。

表1 均勻Bernoulli業(yè)務(wù)通過(guò)率Table 1 Throughput under uniform Bernoulli traffic

表2 均勻ON-OFF業(yè)務(wù)通過(guò)率Table 2 Throughput under uniform ON-OFF traffic

3.3 非均勻業(yè)務(wù)

表3、表4給出了非均勻業(yè)務(wù)下，fm=0.8時(shí)，不同算法的通過(guò)率。MULHB算法的通過(guò)率要高于MF-MRSF及MUCB算法。

圖3給出了非均勻業(yè)務(wù)下平均時(shí)延的對(duì)比結(jié)果。從圖中可以看出，MULHB算法的時(shí)延性能顯著優(yōu)于MF-MRSF及MUCB算法，并且接近OQ調(diào)度。

通過(guò)仿真結(jié)果對(duì)比可以看出，無(wú)論是在均勻業(yè)務(wù)下還是非均勻業(yè)務(wù)下，DMQ-MULHB算法的性能相對(duì)于MUCB算法、MF-MRSF算法，都有了明顯的提升。尤其在非均勻業(yè)務(wù)下，DMQ-MULHB算法的性能接近OQ調(diào)度。

圖2 均勻Bernoulli和ON-OFF業(yè)務(wù)平均時(shí)延Fig.2 Average delay under uniform Bernoulli and ON-OFF traffic

表3 非均勻Bernoulli業(yè)務(wù)通過(guò)率Table 3 Throughput under non-uniform Bernoulli traffic

表4 非均勻ON-OFF業(yè)務(wù)通過(guò)率Table 4 Throughput under non-uniform ON-OFF traffic

圖3 非均勻Bernoulli和ON-OFF業(yè)務(wù)平均時(shí)延Fig.3 Average delay under non-uniform Bernoulli amd ON-OFF traffic

4 結(jié) 論

1) 本文基于CICQ交換結(jié)構(gòu)分析了單組播混合調(diào)度中HoL堵塞、節(jié)點(diǎn)緩存狀態(tài)以及使交換機(jī)逼近work-conserving狀態(tài)之間的關(guān)系。

2) 與已有研究中基于輪詢機(jī)制或者基于最大權(quán)重匹配的調(diào)度算法不同，本文以緩解HoL堵塞問(wèn)題為目標(biāo)，盡量使交換機(jī)逼近work-conserving狀態(tài)。

在上述分析的基礎(chǔ)之上，本文提出了DMQ入隊(duì)策略以及MULHB算法，通過(guò)仿真與現(xiàn)有性能較好的MUCB算法以及MF-MRSF算法進(jìn)行對(duì)比，在均勻業(yè)務(wù)下，DMQ-MULHB算法的性能更好。尤其在非均勻業(yè)務(wù)下，DMQ-MULHB算法性能的表現(xiàn)有了顯著的提升，并且接近OQ調(diào)度。