梁佳誠(chéng)，熊慶旭，蕭翰

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

10.3969/j.issn.1003-3114.2018.01.10

梁佳誠(chéng)，熊慶旭，蕭翰.一種星載CICQ交換機(jī)單組播分組調(diào)度算法[J].無(wú)線電通信技術(shù),2018,44(1):48-54.

[LIANG Jiacheng，XIONG Qingxu，XIAO Han.A Packet Scheduling Algorithm for Unicast and Multicast Traffic in CICQ Switch under GEO Channel Environment [J].Radio Communications Technology,2018,44(1):48-54.]

一種星載CICQ交換機(jī)單組播分組調(diào)度算法

梁佳誠(chéng)，熊慶旭，蕭 翰

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

以緩解聯(lián)合輸入交叉隊(duì)列(CICQ)交換機(jī)分組調(diào)度中的組播HOL Blocking問(wèn)題為目標(biāo)，同時(shí)對(duì)因GEO信道問(wèn)題傳輸失敗而需要重傳的分組進(jìn)行補(bǔ)償，提出一種新的單組播混合調(diào)度算法，即緩解組播頭分組阻塞算法RMHB。該算法在交換機(jī)盡量工作于Work-Conserving的前提下，盡量緩解組播隊(duì)列頭分組對(duì)次分組的阻塞，在單組播分組裁決中，將分組在信道中重傳的次數(shù)作為考慮的首要因素。目前尚未見(jiàn)到CICQ結(jié)構(gòu)中在考慮GEO衛(wèi)星信道狀態(tài)的情況下，進(jìn)行單組播混合業(yè)務(wù)分組調(diào)度的方法。

星載交換；調(diào)度算法；單組播；CICQ；頭分組阻塞

TN911.5

A

1003-3114(2018)01-48-7

2017-09-12

國(guó)家自然科學(xué)基金項(xiàng)目(61271196)

APacketSchedulingAlgorithmforUnicastandMulticastTrafficinCICQSwitchunderGEOChannelEnvironment

LIANG Jiacheng,XIONG Qingxu,XIAO Han

(School of Electronic and Information Engineering,Beijing University of Aeronautics and Astronautics,Beijing 100083,China)

Aiming at relieving the problem of multicast HOL blocking in CICQ switches，and simultaneously compensating the packets that need to be retransmitted due to the failure of GEO channel transmission,a new relief multicast traffic HOL blocking scheduling algorithm called RMHB is proposed,which accommodates mixed unicast and multicast traffic.This algorithm relieves the blocking of sub-packets by header packets under the premise that the switch operates as far as possible in Work-Conserving state.In the choice of unicast and multicast packet,the times of retransmissions of the packets in the channel is taken as the primary factor.Up to now,there is no research about scheduling algorithm considering GEO satellite channel environment in CICQ switches that accommodates mixed unicast and multicast traffic.

on-board switching; scheduling algorithm; unicast and multicast; CICQ; HOL blocking

0 引言

隨著衛(wèi)星通信技術(shù)發(fā)展及應(yīng)用需求的增長(zhǎng)，基于分組交換的衛(wèi)星通信網(wǎng)絡(luò)得到了越來(lái)越多的關(guān)注。為提高衛(wèi)星網(wǎng)絡(luò)性能，星上交換技術(shù)是研究的重點(diǎn)內(nèi)容之一。不同于地面網(wǎng)絡(luò)，GEO衛(wèi)星網(wǎng)絡(luò)業(yè)務(wù)中組播占有較高的比例，單組播混合業(yè)務(wù)分組調(diào)度的星上交換技術(shù)是衛(wèi)星網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。

傳統(tǒng)的交換機(jī)采用輸出排隊(duì)(Output Queuing,OQ)的交換結(jié)構(gòu)，其N(輸入/輸出端口數(shù)目)倍加速比的需求使其不適用于高速大容量交換環(huán)境[1]。輸入排隊(duì)(Input Queuing,IQ)交換結(jié)構(gòu)無(wú)需加速比，可擴(kuò)展性強(qiáng)，是未來(lái)高速交換機(jī)研究的主要方向。IQ結(jié)構(gòu)中虛擬輸出排隊(duì)(Virtual Output Queuing,VOQ)結(jié)構(gòu)的輸入輸出競(jìng)爭(zhēng)緊密耦合的集中式調(diào)度特性使得控制過(guò)程較為復(fù)雜[2]。而CICQ (Combined Input and Crossbar Queued)結(jié)構(gòu)通過(guò)在交換矩陣的每個(gè)交叉節(jié)點(diǎn)配置一定容量的緩存，很大程度解耦了輸入輸出競(jìng)爭(zhēng)的裁決，使得調(diào)度算法復(fù)雜度降低，故而更適用于星載環(huán)境。

對(duì)于輸入端口設(shè)置多個(gè)組播緩存隊(duì)列的CICQ結(jié)構(gòu)，其調(diào)度步驟分：CA(Cell Assignment) -IS(Input Schedule)-OS (Output Schedule)三步。

CA策略已有一些研究，如文獻(xiàn)[3]中提到的Vector算法及文獻(xiàn)[4]中提到的Modulo算法，這些CA算法各有利弊。目前已有CA研究中，幾乎都未將CA與IS綜合考慮，使之更加滿足后續(xù)IS調(diào)度的需求，在整體上提升性能。

對(duì)于IS-OS調(diào)度，多數(shù)都是基于簡(jiǎn)單的輪詢(Round-Robin,RR)算法[4-6]，如文獻(xiàn)[4]中提出的MURS(Multicast and Unicast Round Robin Scheduling)算法。也有一部分研究提出在IS-OS調(diào)度中采用基于權(quán)重的調(diào)度與競(jìng)爭(zhēng)裁決策略[7-9]，如文獻(xiàn)[9]中提出的LCMS(Low-Cost Multicast Scheduling )算法。文獻(xiàn)[10]中首次以使得CICQ交換機(jī)盡量工作于Work-Conserving狀態(tài)為目標(biāo)，提出了MUCB (Multicast and Unicast Crossbuffer Balance)算法，與最新的主流算法相比，該算法的性能具有明顯的優(yōu)勢(shì)。

以上調(diào)度算法研究均是以地面有線環(huán)境為條件。CICQ結(jié)構(gòu)中，只有部分單播調(diào)度研究是以星載環(huán)境為條件，但也主要是考慮對(duì)到達(dá)星載交換機(jī)輸入端口的業(yè)務(wù)分析建模[11-12]，而具體調(diào)度算法仍然與地面有線環(huán)境相似。

然而，GEO衛(wèi)星網(wǎng)絡(luò)中組播業(yè)務(wù)比例較高，且網(wǎng)絡(luò)環(huán)境復(fù)雜。在CICQ交換機(jī)調(diào)度中，交換機(jī)輸出端口對(duì)應(yīng)的輸出信道的狀態(tài)是隨機(jī)變化的。因此，有必要研究CICQ結(jié)構(gòu)中考慮衛(wèi)星網(wǎng)絡(luò)信道特點(diǎn)的單組播混合業(yè)務(wù)分組調(diào)度算法。

本文通過(guò)分析組播HOL Blocking問(wèn)題，結(jié)合CICQ結(jié)構(gòu)特點(diǎn)，在盡量保證CICQ交換機(jī)運(yùn)行于Work-Conserving狀態(tài)的前提下，以緩解組播隊(duì)列頭分組對(duì)次分組阻塞為目標(biāo)，同時(shí)在調(diào)度算法的單組播分組權(quán)重比較中，將分組由于在GEO衛(wèi)星信道中傳輸出錯(cuò)而導(dǎo)致需要重傳的次數(shù)作為比較中需要考慮的首要因素，以達(dá)到盡量對(duì)因受信道影響較為嚴(yán)重的分組進(jìn)行補(bǔ)償?shù)哪康?。就此提出了一種GEO衛(wèi)星信道環(huán)境下的單組播混合調(diào)度算法，即緩解組播HOL Blocking(Relief Multicast HOL Blocking，RMHB)算法。

1 單組播調(diào)度問(wèn)題分析

圖1為本文采用的星載CICQ結(jié)構(gòu)示意圖。對(duì)于每個(gè)輸入端口，單播分組到達(dá)后按照其去向進(jìn)入對(duì)應(yīng)VOQ隊(duì)列，組播分組到達(dá)后，按照CA算法選擇MVOQ(Multicast Virtual Output Queuing)隊(duì)列入隊(duì)。同時(shí)，每個(gè)輸入端口為單播分組配置N個(gè)重傳隊(duì)列RTVOQ(ReTransmission Virtual Output Queue)及為組播分組配置k個(gè)重傳隊(duì)列RTMVOQ (ReTransmission Multicast Virtual Output Queue)，重傳隊(duì)列的標(biāo)號(hào)與原理想信道下CICQ結(jié)構(gòu)中的VOQ隊(duì)列標(biāo)號(hào)及MVOQ隊(duì)列標(biāo)號(hào)一致。RTVOQ隊(duì)列與RTMVOQ隊(duì)列分別用來(lái)暫存由輸出端口調(diào)度離開(kāi)的單播和組播分組。

圖1 星載CICQ結(jié)構(gòu)示意圖

對(duì)于4×4交換機(jī)，不妨設(shè)每個(gè)輸入端口有4個(gè)組播隊(duì)列。圖2中矩陣DHi表示輸入端口i的4個(gè)組播隊(duì)列的頭分組去向，如DHi(1,2)=1表示輸入端口i的組播隊(duì)列1的頭分組去向包含輸出端口2；矩陣DSi表示輸入端口i的4個(gè)組播隊(duì)列的次分組去向，如Dsi(1,2)=1表示輸入端口i的組播隊(duì)列1的次分組去向包含輸出端口2；矩陣X表示交叉緩存狀態(tài)，如X(2,1)=1表示交叉緩存(2,1)不為空。以下分析將均以圖2為例，這里假設(shè)DHi與DSi均對(duì)應(yīng)輸入端口1的狀態(tài)為：

1.1 CA算法

當(dāng)?shù)竭_(dá)組播分組的去向包含輸出端口2時(shí)，應(yīng)使該分組進(jìn)入輸入端口1的最短虛擬組播隊(duì)列。因?yàn)榈?列交叉緩存只有一個(gè)分組，當(dāng)前時(shí)隙輸出調(diào)度后，第2列交叉緩存可能為空。若下一時(shí)隙輸入調(diào)度時(shí)交換機(jī)所有輸入端口中均無(wú)頭分組去往輸出端口2，而該到達(dá)分組去向包含輸出端口2，但由于其不是頭分組而無(wú)法被調(diào)度，即由于HOL Blocking使得交換機(jī)無(wú)法運(yùn)行于Work-Conserving狀態(tài)。所以，為避免這種情形，應(yīng)使得該到達(dá)組播分組進(jìn)入最短隊(duì)列，從而盡快成為頭分組。

若當(dāng)前時(shí)隙輸入調(diào)度后，交叉緩存可能無(wú)法接納輸入端口1的頭分組，而到達(dá)分組的去向包含輸出端口3時(shí)，也應(yīng)使該分組進(jìn)入輸入端口1的最短虛擬組播隊(duì)列。因?yàn)檩斎攵丝?的頭分組去向中不包含輸出端口3，該到達(dá)分組去向包含輸出端口3，而輸入端口1在本時(shí)隙輸入調(diào)度后可能無(wú)法在下一時(shí)隙繼續(xù)傳輸分組，若不盡快使得該到達(dá)分組成為頭分組，可能造成輸入端口1的傳輸機(jī)會(huì)浪費(fèi)。

1.2 輸入調(diào)度

由CICQ結(jié)構(gòu)中Work-Conserving含義可知，只要輸入調(diào)度后每列交叉緩存中分組數(shù)目至少為1，交換機(jī)本時(shí)隙便工作于Work-Conserving狀態(tài)。故輸入調(diào)度中，先考慮在盡量保證每列交叉緩存至少有一個(gè)分組后，之后對(duì)未傳輸過(guò)分組的輸入端口以緩解HOL Blocking為目標(biāo)進(jìn)行調(diào)度。

在輸入端口1選擇組播隊(duì)列傳輸時(shí)，應(yīng)優(yōu)先選擇組播隊(duì)列1。因?yàn)橛删仃嘪的狀態(tài)可知，輸出端口1和輸出端口2對(duì)應(yīng)列交叉緩存的非空數(shù)目均小于2。這意味該時(shí)隙輸出調(diào)度后，第1列和第2列交叉緩存可能為空，進(jìn)而使得后續(xù)時(shí)隙交換機(jī)可能無(wú)法運(yùn)行于Work-Conserving狀態(tài)。而組播隊(duì)列1的次分組去向包含輸出端口1和輸出端口2，而對(duì)于其他組播隊(duì)列，其次分組去向與輸出端口1和輸出端口2最多的交集中至多有一個(gè)元素。這意味組播隊(duì)列1的次分組更有利于交換機(jī)后續(xù)時(shí)隙工作于Work-Conserving狀態(tài)，所以應(yīng)優(yōu)先傳輸組播隊(duì)列1的頭分組，從而使得組播隊(duì)列1的次分組可盡快成為頭分組。

1.3 輸出調(diào)度

由輸入調(diào)度分析可知，輸入端口1需要傳輸其組播隊(duì)列1的頭分組到交叉緩存。但是，由于該頭分組去向包含輸出端口4，而X(1,4)=1,使得其頭分組不能盡快被完全調(diào)度到交叉緩存。因此，輸出端口4在進(jìn)行輸出調(diào)度時(shí)，應(yīng)優(yōu)先選擇X(1,4)對(duì)應(yīng)的交叉緩存分組。

1.4 重傳策略

不同于地面有線或者無(wú)線網(wǎng)絡(luò)中的信道，GEO網(wǎng)絡(luò)中的信道傳輸時(shí)延巨大，對(duì)于GEO星載交換機(jī)而言，其在每個(gè)時(shí)隙調(diào)度時(shí)是無(wú)法準(zhǔn)確獲知本時(shí)隙經(jīng)調(diào)度離開(kāi)交換機(jī)的分組是否會(huì)在信道中傳輸出錯(cuò)，而交換機(jī)中不允許丟失分組。故而，星載交換機(jī)中，針對(duì)可能因信道狀態(tài)惡化導(dǎo)致分組傳輸失敗的情形，需要有一定的重傳策略對(duì)其進(jìn)行處理。

不同于單播調(diào)度中的重傳策略，單組播混合業(yè)務(wù)調(diào)度中的重傳策略面臨更復(fù)雜的問(wèn)題。單播分組的去向只有一個(gè)，在CICQ交換機(jī)中，每個(gè)VOQ隊(duì)列中的單播分組去向也都一致，因此在調(diào)度過(guò)程中，隊(duì)列前面的分組一定比隊(duì)列后面的分組早獲得其是否在信道中傳輸成功的信息。因此，單播調(diào)度的重傳策略可以借鑒滑動(dòng)窗口的方案來(lái)實(shí)現(xiàn)。組播則不同，一個(gè)組播分組的去向有多個(gè)，各個(gè)去向?qū)?yīng)的輸出端口信道狀態(tài)可能不一致，扇出拆分后，各個(gè)去向在信道中傳輸?shù)钠鹗紩r(shí)間點(diǎn)也不一致，從而使得該組播分組重傳時(shí)間點(diǎn)也比較難確定。而且，同一個(gè)組播隊(duì)列中，隊(duì)列前后分組去向經(jīng)常不一致，而CICQ結(jié)構(gòu)中的分布式調(diào)度使得調(diào)度中組播隊(duì)列前面的分組未必會(huì)比后面分組提前調(diào)度離開(kāi)交換機(jī)。因此，窗口機(jī)制對(duì)于組播重傳策略的借鑒意義不是很大。

基于此，本文采用配置重傳隊(duì)列的方式解決單組播分組的重傳問(wèn)題。

輸入調(diào)度時(shí)，先從每個(gè)重傳隊(duì)列隊(duì)頭開(kāi)始，根據(jù)當(dāng)前時(shí)隙與重傳隊(duì)列中分組離開(kāi)時(shí)間的時(shí)間差是否大于等于星地往返時(shí)延及地面反饋的是否傳輸成功的信息，找出需要重傳的分組，然后將其送往該重傳隊(duì)列對(duì)應(yīng)的單播或組播虛擬輸出隊(duì)列的隊(duì)頭之前，使其參與輸入競(jìng)爭(zhēng)。

輸出調(diào)度時(shí)，則根據(jù)其所有去向是否都已從各自對(duì)應(yīng)的輸出端口離開(kāi)來(lái)決定其是否需要復(fù)制一份送往對(duì)應(yīng)輸入端口的重傳隊(duì)列隊(duì)尾，并 v標(biāo)記離開(kāi)交換機(jī)時(shí)間，這樣，可保證重傳隊(duì)列中后面的分組一定不會(huì)早于前面分組獲得地面反饋的是否傳輸成功的信息，從而不需要遍歷整個(gè)重傳隊(duì)列來(lái)找出需要重傳的分組。

1.5 補(bǔ)償方案

GEO衛(wèi)星信道狀態(tài)的變化會(huì)使得已從輸出端口調(diào)度離開(kāi)的單播或組播分組需要重傳，部分分組甚至可能需要多次重傳，這些需要重傳的分組會(huì)造成交換機(jī)中分組累積，進(jìn)而使得調(diào)度的性能惡化，應(yīng)當(dāng)采用必要的補(bǔ)償方案使得重傳盡快離開(kāi)交換機(jī)，本文提出的補(bǔ)償思路是：

① 輸入調(diào)度中，在輸入端口按照權(quán)重選擇單組播分組進(jìn)入交叉緩存，權(quán)重比較時(shí)，優(yōu)先比較分組重傳次數(shù)，即重傳次數(shù)多的分組一定權(quán)重更高。對(duì)于重傳次數(shù)相同的分組，在按照其他方式比較權(quán)重。

② 對(duì)于因信道狀態(tài)變化導(dǎo)致傳輸失敗的分組，其在交換機(jī)中的滯留的時(shí)間將至少增加星地往返的傳輸時(shí)間。因此，在計(jì)算單組播分組權(quán)重中，將分組在交換機(jī)中等待時(shí)間作為乘法因子之一，可對(duì)傳輸失敗需要重傳分組進(jìn)行一定程度的補(bǔ)償。

2 RMHB算法

根據(jù)第2節(jié)中示例的分析，本節(jié)將詳細(xì)介紹RMHB算法。

為敘述的方便，下面給出相關(guān)符號(hào)含義：

O：輸出端口的集合，且按端口號(hào)升序排列；

I：輸入端口的集合，且按端口號(hào)升序排列；

Ad：到達(dá)分組的去向向量，若到達(dá)分組的去向包含輸出端口j，則Ad[j]=1，否則，Ad[j]=0；

Pi：輸入端口i的頭分組(包括單播)去向向量，Pi[j]=1，表示頭分組去向包含輸出端口j,Pi[j]=0,表示不包含；

Vij：輸入端口i中去往輸出端口j的隊(duì)列；

Mik：輸入端口i的第k個(gè)組播隊(duì)列；

Xij：輸入端口i和輸出端口j對(duì)應(yīng)交叉節(jié)點(diǎn)緩存；

Bj：輸出端口j的列方向交叉緩存中分組數(shù)目；

Mi：輸入端口i的所有虛擬組播隊(duì)列；

Uj：對(duì)于輸出端口j滿足以下條件的所有輸入端口的集合：Xij為空，同時(shí)Vij不為空或Mi中所有非空頭分組中有去往輸出端口j；

Tj：Uj與I的交集，且按端口號(hào)升序排列；

Di：輸入端口i所有非空頭分組目的端口種類數(shù)；

w：組播權(quán)重因子；

Aik：Mik頭分組到達(dá)時(shí)扇出；

Cik：Mik頭分組當(dāng)前扇出；

Xj：輸出端口j對(duì)應(yīng)的列方向交叉緩存的集合;

F：若F=0，表示組播按照Vector算法入隊(duì)，若F=1,表示組播不按照Vector算法入隊(duì)；

Sik：次分組對(duì)Work-Conserving匹配數(shù)，即Sik等于該次分組一類去向端口的總數(shù)，這類去向端口連接的交叉緩存中不為空的數(shù)目小于等于1。

RMHB算法包含3個(gè)運(yùn)行階段，具體運(yùn)行過(guò)程為：

第一階段：入隊(duì)

對(duì)于每個(gè)輸入端口i，單播分組去向?yàn)閖則去往Vij，組播分組按照以下步驟入隊(duì)：

③ 若存在j，使得：Ad[j]=1,同時(shí)Bj≤1，則F=1，跳到第⑥步；

④ 若輸入調(diào)度后該輸入端口仍可有分組傳輸?shù)浇徊婢彺?，則跳到第⑥步；

⑤ 若存在j，使得：Ad[j]=1,同時(shí)Pi[j]=0，Xij為空，則F=1；

以上步驟中提到的Vector算法是一種已有的組播入隊(duì)方案，其算法過(guò)程為：從N維向量空間定義k個(gè)特征向量v1,v2,…,vk分別對(duì)應(yīng)k個(gè)組播隊(duì)列，每個(gè)特征向量的每個(gè)元素的值為0或1，且每?jī)蓚€(gè)特征向量相互正交；對(duì)于到達(dá)的組播分組，按照其去向定義去向向量Da；若到該分組去向包含輸出端口j，則Da[j]=1,否則Da[j]=0。在v1,v2,…,vk中找出與Da距離最短的特征向量，則到達(dá)分組進(jìn)入該特征向量對(duì)應(yīng)的組播隊(duì)列。

第二階段：輸入調(diào)度

① 設(shè)當(dāng)前時(shí)隙為n2，每個(gè)輸入端口分別從隊(duì)列頭開(kāi)始檢查該輸入端口中的N個(gè)單播重傳隊(duì)列及k個(gè)組播重傳隊(duì)列中的分組，直到找到符合n2-n1

② 對(duì)重傳隊(duì)列中的頭分組和第①步中找到的分組之間的所有分組(包含隊(duì)列頭分組但不包含找到的分組)進(jìn)行相應(yīng)處理。對(duì)于單播分組，若傳輸成功，則將其剔除；若傳輸失敗，則保留，且將該分組的重傳次數(shù)加1。對(duì)于組播分組，若所有去向均傳輸成功，則將其剔除；否則，剔除傳輸成功的去向，保留傳輸失敗的去向，保留該組播分組，其重傳次數(shù)加1；

③ 將剔除后所有剩余的分組分別送往該重傳隊(duì)列對(duì)應(yīng)的單播或組播虛擬輸出隊(duì)列的隊(duì)頭之前；

④ 令O包含全部輸出端口，I包含全部輸入端口；

⑤ 若O為空，該時(shí)隙結(jié)束輸入調(diào)度；

⑥ 從O集合的第一個(gè)元素開(kāi)始，選擇Bj最小的輸出端口j，若Bj>0,則跳到第步；

⑦ 若Tj為空，從O中剔除端口j，回到第⑤步；

⑧ 從Tj集合的第一個(gè)元素開(kāi)始，選擇Di最小的輸入端口i；

⑩ 從I中剔除端口i，更新U、T、Bj狀態(tài)，回到第6步；

第三階段：輸出調(diào)度

① 對(duì)于每個(gè)輸出端口j，找出所有滿足如下條件的組播隊(duì)列：該組播隊(duì)列頭分組去向包含輸出端口j，同時(shí)Xij非空，其中i為該組播隊(duì)列所在的輸入端口編號(hào)；

② 在第①步選出的組播隊(duì)列中找出max{Sik}；

③ 若max{Sik}>0，該輸出端口j傳輸Xij中的分組，

同時(shí)，若該分組為單播分組，則將該單播分組復(fù)制一份送往對(duì)應(yīng)的輸入端口的單播重傳隊(duì)列隊(duì)尾，并將其從輸出端口離開(kāi)的時(shí)隙記為n1。若該分組為組播分組，判斷其所有去向是否都已從各自對(duì)應(yīng)的輸出端口離開(kāi)：若是，則將該組播分組復(fù)制一份到組播重傳隊(duì)列的隊(duì)尾，入隊(duì)重傳隊(duì)列的標(biāo)號(hào)與該組播分組原來(lái)所在虛擬組播隊(duì)列標(biāo)號(hào)一致，并將其從輸出端口離開(kāi)的時(shí)隙記為n1；否則，則標(biāo)記該組播分組對(duì)應(yīng)的去向已從對(duì)應(yīng)的輸出端口被調(diào)度離開(kāi)。若max{Sik}=0，則執(zhí)行第④步；

3 仿真結(jié)果

單組播混合調(diào)度中，輸入輸出負(fù)載間關(guān)系為：

μ=λ(fu+|φ|fm)，

(1)

式中，μ為輸出負(fù)載，λ為輸入負(fù)載，fu為單播業(yè)務(wù)比例，|φ|為組播平均扇出，fm為組播業(yè)務(wù)比例。這里給出的仿真結(jié)果中，fm=0.8，負(fù)載均為輸出負(fù)載。

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

(2)

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

仿真中，GEO衛(wèi)星信道模型采用常用的雨衰(Additive White Gaussian Noise,AWGN)信道，該信道適用于GEO衛(wèi)星與地面靜止基站通信，AWGN信道模型具體建模方式參見(jiàn)文獻(xiàn)[13]。這里以雷雨天氣為條件對(duì)選取相應(yīng)的參數(shù)。假設(shè)信噪比為30 dB。仿真得到雷雨天氣下AWGN信道的信道容量為0.6。對(duì)于交換機(jī)而言，其輸出負(fù)載為0.6時(shí)即達(dá)到滿載，因此，仿真中輸出負(fù)載最大設(shè)為0.6。

仿真時(shí)間為100萬(wàn)個(gè)時(shí)隙。交換機(jī)端口數(shù)為16×16，ON-OFF業(yè)務(wù)的平均突發(fā)長(zhǎng)度為16個(gè)時(shí)隙，每個(gè)輸入端口設(shè)有8個(gè)虛擬組播隊(duì)列。

由于尚未見(jiàn)到在CICQ結(jié)構(gòu)單組播混合調(diào)度中考慮GEO信道環(huán)境的研究。為對(duì)比分析，這里選取在OQ結(jié)構(gòu)FIFO算法中只加入對(duì)應(yīng)的重傳機(jī)制，即OQ結(jié)構(gòu)調(diào)度中，對(duì)于每個(gè)輸出端口，直接將FIFO隊(duì)列中的分組在信道中傳輸，對(duì)于反饋到需要重傳的分組，將其直接置于原FIFO隊(duì)頭進(jìn)行重傳。本節(jié)將給出RMHB算法與OQ中FIFO算法的性能對(duì)比。

表1給出了4種業(yè)務(wù)到達(dá)時(shí)，不同負(fù)載條件下RMHB算法與OQ中FIFO算法的通過(guò)率仿真結(jié)果，圖2～圖5分別給出了4種業(yè)務(wù)到達(dá)時(shí)，不同負(fù)載下RMHB算法與OQ中FIFO算法的時(shí)延性能對(duì)比。

可以看出，總體來(lái)說(shuō)，在AWGN信道條件下，對(duì)于4種到達(dá)業(yè)務(wù)，與OQ結(jié)構(gòu)中FIFO算法相比，RMHB算法性能較弱。但是，在非均勻ON-OFF業(yè)務(wù)下，RMHB算法與OQ中FIFO算法極為接近。

表1 通過(guò)率仿真結(jié)果

業(yè)務(wù)類型負(fù)載傳播類型單播組播單組播混合RMHB算法OQ中FIFO算法RMHB算法OQ中FIFO算法RMHB算法OQ中FIFO算法均勻Bernoulli0．30．999410．999660．990980．997790．992660．998170．60．997750．990000．806490．959390．844920．96554均勻ON?OFF0．30．999380．999990．994250．998110．995270．998480．60．998160．991010．811830．955770．849160．96283非均勻Bernoulli0．30．999110．998390．998040．997110．998260．997360．60．997920．938490．773050．912300．818090．91754非均勻ON?OFF0．30．999040．998380．998770．997480．998830．997660．60．997630．941010．851250．914340．880620．91969

圖2 均勻Bernoulli業(yè)務(wù)總體平均時(shí)延

圖3 均勻ON-OFF業(yè)務(wù)總體平均時(shí)延

圖4 非均勻Bernoulli業(yè)務(wù)總體平均時(shí)延

圖5 非均勻ON-OFF業(yè)務(wù)總體平均時(shí)延

相較于OQ中FIFO算法，RMHB算法性能較弱的主要原因在于其組播通過(guò)率較差，雖然單播通過(guò)率較OQ中FIFO算法稍好，但仍不足以彌補(bǔ)其相較于OQ中FIFO算法組播性能落后的缺陷。而RMHB算法組播性能較差的原因在于：對(duì)于組播分組而言，當(dāng)部分扇出對(duì)應(yīng)的信道狀態(tài)變差，而交換機(jī)又調(diào)度該組播分組的這些扇出在信道中傳輸時(shí)，分組傳輸過(guò)程中出現(xiàn)錯(cuò)誤，此時(shí)需要對(duì)該組播分組傳錯(cuò)的扇出進(jìn)行重傳。重傳時(shí)，由于該組播分組的其他扇出對(duì)應(yīng)信道狀態(tài)可能良好，從而這些在信道中傳輸成功，使得重傳時(shí)該重傳分組的去向減少。而該重傳分組進(jìn)入組播隊(duì)列頭分組時(shí)，由于其去向較少，對(duì)其后續(xù)去向較多的組播分組又造成了阻塞，最終加重了組播的HOL Blocking問(wèn)題。

4 結(jié)束語(yǔ)

首先分析了在CICQ結(jié)構(gòu)中單組播混合調(diào)度時(shí)，如何在盡量保證Work-Conserving的前提下，通過(guò)在組播入隊(duì)、輸入調(diào)度以及輸出調(diào)度算法中，盡量緩解組播的HOL Blocking問(wèn)題。同時(shí)，在調(diào)度算法中，考慮針對(duì)GEO衛(wèi)星信道環(huán)境的重傳策略及補(bǔ)償機(jī)制，提出一種適用于GEO星載環(huán)境環(huán)境的CICQ結(jié)構(gòu)中單組播混合調(diào)度算法，即RMHB算法。之后，以GEO衛(wèi)星信道中的常見(jiàn)的AWGN信道模型為條件，給出了RMHB算法與OQ中FIFO算法的仿真對(duì)比，并對(duì)仿真進(jìn)行了分析。

本文是對(duì)單組播混合調(diào)度算法中考慮GEO信道進(jìn)行了初步探索，為今后進(jìn)一步探索適用于星載環(huán)境的單組播混合調(diào)度算法提供基礎(chǔ)和借鑒。

[1] 熊慶旭.輸入排隊(duì)結(jié)構(gòu)交換機(jī)分組調(diào)度研究[J].通信學(xué)報(bào),2005,26(6):118-129.

[2] Nabeshima M.Performance Evaluation of a Combined Input-and Crosspoint-queued Switch[J].IEICE Transactions on Communications,2000,83(3): 737-741.

[3] 陳庶樵,扈紅超,郭云飛,等.一種支持單組播的 MCICQ 交換結(jié)構(gòu)及其性能仿真[J].系統(tǒng)仿真學(xué)報(bào),2009 (13): 4003-4008.

[4] Mhamdi L,Vassiliadis S.Integrating Uni-and Multicast Scheduling in Buffered Crossbar Switches[C]∥High Performance Switching and Routing,2006 Workshop on.IEEE.Piscataway,NJ:IEEE Press,2006:190-196.

[5] Mhamdi L,Hamdi M.Scheduling Multicast Traffic in Internally Buffered Crossbar Switches[C]∥ 2004 IEEE International Conference on Communications,.Piscataway,NJ:IEEE Press,2004,2: 1103-1107.

[6] DONG Z Q,ROJAS-CESSA R.Packet Switching and Replication of Multicast Traffic by Crosspoint Buffered Packet switches[C]∥ 2007 IEEE Workshop on High Performance Switching and Routing,HPSR.Piscataway,NJ:IEEE Press,2007: 160-165.

[7] SUN S T,HE S M,ZHENG Y F,et al.Multicast Scheduling in Buffered Crossbar Switches with Multiple input Queues[C]∥ 2005 Workshop on High Performance Switching and Routing,HPSR 2005.Piscataway,NJ:IEEE Press,2005: 73-77.

[8] 董林林.基于 CICQ 結(jié)構(gòu)的多播交換技術(shù)研究[D].西安：西安電子科技大學(xué),2013.

[9] YI P,LI H,YU J,et al.Scheduling Multicast and Unicast Traffic in Buffered Crossbar Switches[C]∥ IET International Conference on Wireless Mobile and Multimedia Networks Proceedings,ICWMMN 2006.Stevenage ：IET,2006: 1-4.

[10] 梁佳誠(chéng)，熊慶旭，閆付龍，等.基于Work-Conserving的CICQ結(jié)構(gòu)中單組播分組調(diào)度算法[J].北京航空航天大學(xué)學(xué)報(bào),2017,43(1): 144-151.

[11] 曾媛,龔文斌,劉會(huì)杰,等.適合星載交換機(jī)的調(diào)度算法[J].計(jì)算機(jī)工程,2009,35(3): 158-160.

[12] Xu L,Luo F,Luo Z.High Performance Packet Switches for Broadband Satellite Networks[C]∥ International Conference on Space Information Technology.International Society for Optics and Photonics,2005: 598510-598514.

[13] 王愛(ài)華,羅偉雄.Ka頻段衛(wèi)星通信信道建模及系統(tǒng)性能仿真[J].通信學(xué)報(bào),2001,22(9): 61-69.

梁佳誠(chéng)(1991—)，男，碩士研究生，主要研究方向：星載交換；

熊慶旭(1965—)，男，博士，教授，主要研究方向：通信網(wǎng)絡(luò)、高性能交換技術(shù)、語(yǔ)義通信、無(wú)線傳感器網(wǎng)絡(luò)；

蕭翰(1990—)，男，博士研究生，主要研究方向：星載交換。