一種動(dòng)態(tài)權(quán)值輸入緩存Crossbar多播調(diào)度算法

楊 帆，徐展琦，李丹武，祝劍鋒，馬 濤，丁 喆

(西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071)

?

一種動(dòng)態(tài)權(quán)值輸入緩存Crossbar多播調(diào)度算法

楊 帆，徐展琦，李丹武，祝劍鋒，馬 濤，丁 喆

(西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071)

針對(duì)輸入緩存Crossbar結(jié)構(gòu)，提出一種權(quán)值動(dòng)態(tài)計(jì)算的多播調(diào)度算法．該算法使用地址拷貝的方法將多播信元按照目的端口區(qū)分存儲(chǔ)，以達(dá)到減少隊(duì)頭阻塞的目的．在調(diào)度多播信元時(shí)，與現(xiàn)有調(diào)度算法每次迭代時(shí)多播信元的權(quán)值都保持固定不同，新算法在每輪迭代中根據(jù)多播信元的扇出分割情況動(dòng)態(tài)地為信元計(jì)算權(quán)值，以確保為扇出分割小的信元提供更多優(yōu)先輸出機(jī)會(huì)．減少多播信元的扇出分割，可以有效地防止路由器在多播業(yè)務(wù)量大時(shí)的輸入端口擁塞．為了驗(yàn)證新算法的性能，提出一種只存在少數(shù)最佳匹配的多播業(yè)務(wù)模式．仿真結(jié)果表明，新算法在這種苛刻的業(yè)務(wù)模式以及其他常見的業(yè)務(wù)模式下都有很好的吞吐率．

多播交換;調(diào)度;扇出分割;隊(duì)頭阻塞;吞吐率

隨著互聯(lián)網(wǎng)的高速發(fā)展，目前多播業(yè)務(wù)的應(yīng)用越來越多，因此在路由器中能夠支持多播交換變得越來越重要．由于路由器輸入端口的速率越來越高，高速路由器需要采用輸入緩存的交換方式[1-2]．在輸入緩存的交換方式中進(jìn)行多播交換，主要存在兩大困難:隊(duì)頭阻塞無法完全消除;多播調(diào)度困難．

在輸入緩存交換方式中，隊(duì)頭阻塞對(duì)于交換吞吐率的影響嚴(yán)重．對(duì)于單播業(yè)務(wù)，隊(duì)頭阻塞會(huì)使交換吞吐率只有58.6%；對(duì)于多播業(yè)務(wù)，隊(duì)頭阻塞的影響雖然沒有理論結(jié)論，但是由于多播交換確保吞吐率更困難，因此隊(duì)頭阻塞對(duì)交換吞吐率的影響會(huì)更為突出，從筆者的仿真中可以看出隊(duì)頭阻塞的不利影響．在進(jìn)行多播交換時(shí)，要完全克服隊(duì)頭阻塞，對(duì)于N個(gè)輸出端口的Crossbar而言，需要 2N-1 個(gè)隊(duì)列[3]．當(dāng)N比較大時(shí)，需要的隊(duì)列數(shù)量太多，難以實(shí)現(xiàn)．因此在輸入緩存的交換方式中，完全克服多播交換的隊(duì)頭阻塞非常困難．現(xiàn)有的研究中采取的方法都是盡量緩解隊(duì)頭阻塞，主要方法分為兩類: 第1類是文獻(xiàn)[4]中采用的用k個(gè)隊(duì)列來存儲(chǔ)多播分組的方法．在這種方法中，k的取值是關(guān)鍵，k值大，難以實(shí)現(xiàn)；k值小，對(duì)克服隊(duì)頭阻塞的幫助又不大．第2類是文獻(xiàn)[5]中提出的將所有多播分組存儲(chǔ)于一個(gè)隊(duì)列中，允許隊(duì)頭的前m個(gè)多播分組參與調(diào)度，但是m值大，調(diào)度算法復(fù)雜度高；m值小，效果不明顯．因此筆者提出一種新的基于地址拷貝的多播隊(duì)列組織結(jié)構(gòu)，該結(jié)構(gòu)可以有效地支持多播，并減少隊(duì)頭阻塞的影響．

對(duì)于輸入緩存Crossbar中的多播交換，第2個(gè)困難在于多播調(diào)度．如果采取集中式的調(diào)度算法，實(shí)現(xiàn)復(fù)雜度高，不適合于高速實(shí)時(shí)環(huán)境．通常都采用啟發(fā)式分布調(diào)度算法[6]．但是，啟發(fā)式分布調(diào)度算法各個(gè)輸入/輸出端口之間獨(dú)立地進(jìn)行分組調(diào)度，相互之間缺乏配合，要排除絕大多數(shù)非最優(yōu)匹配而找出少數(shù)的最優(yōu)匹配，不是件容易的事．在多播交換中，扇出分割容易導(dǎo)致輸入端口擁塞．所謂扇出分割，是指一個(gè)多播分組如果不能夠一次從它的所有輸出端口都輸出的話，那么需要分多次向其各個(gè)輸出端發(fā)送．當(dāng)輸入端口的多播業(yè)務(wù)量比較大時(shí)，采用扇出分割將導(dǎo)致輸入端口擁塞．例如，假設(shè)一個(gè)多播分組需要k次發(fā)送才能從輸入端口向所有輸出端口發(fā)送完畢，在此期間，它必須留在輸入緩存內(nèi)，而輸入端口在這段時(shí)間中有可能會(huì)新到達(dá)k個(gè)分組，那么當(dāng)該多播分組發(fā)送完畢后，輸入緩存中會(huì)新積壓 k-1 個(gè)分組．因此，扇出分割如果頻繁發(fā)生，則會(huì)使存儲(chǔ)器中分組的隊(duì)長(zhǎng)越來越長(zhǎng)，最終導(dǎo)致存儲(chǔ)器溢出．為此，筆者提出了一種權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度——?jiǎng)討B(tài)權(quán)值的多播調(diào)度(Multicast Scheduling with Dynamic Weight，MSDW)算法，可以有效地減少多播分組的扇出分割．為了驗(yàn)證所提算法的性能，筆者還提出了一種苛刻的多播業(yè)務(wù)模式．在這種業(yè)務(wù)模式中，輸入端口輸入多個(gè)多播業(yè)務(wù)流，這些業(yè)務(wù)流輸出沖突非常嚴(yán)重，只存在少數(shù)的無扇出分割匹配．權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法除了在常見的業(yè)務(wù)模式下吞吐率高外，在這種很苛刻的業(yè)務(wù)模式下，也仍然能夠獲得很高的吞吐率．

1 基于地址拷貝的多播隊(duì)列組織結(jié)構(gòu)

筆者提出一種有助于緩解隊(duì)頭阻塞的多播隊(duì)列組織結(jié)構(gòu)．對(duì)于N個(gè)輸入端口與N個(gè)輸出端口的Crossbar而言，每個(gè)輸入端口的緩存中包含有以下幾種隊(duì)列: 1個(gè)信元隊(duì)列，N個(gè)多播地址隊(duì)列，N個(gè)單播地址隊(duì)，N個(gè)多播暫存地址隊(duì)列以及m個(gè)獨(dú)立隊(duì)列．其中，對(duì)應(yīng)每個(gè)輸出端口分別有1個(gè)多播地址隊(duì)列、1個(gè)單播地址隊(duì)列及1個(gè)多播暫存地址隊(duì)列．

為了實(shí)現(xiàn)高速交換，目前在高速路由器內(nèi)部，往往把變長(zhǎng)的分組切割成定長(zhǎng)的信元進(jìn)行交換，交換完畢后再把信元組裝成分組．文中交換、調(diào)度、隊(duì)列存儲(chǔ)都使用固定長(zhǎng)度的信元．信元從輸入端口發(fā)送到輸出端口的時(shí)間稱為一個(gè)時(shí)隙．一個(gè)輸入端口的信元(包括單播和多播信元)都被存儲(chǔ)于一個(gè)信元隊(duì)列中．其中，單播信元的地址指針按照信元的目的端口存儲(chǔ)于相應(yīng)的單播地址隊(duì)列中；多播信元的地址指針被拷貝多份，存儲(chǔ)于其各個(gè)目的端口的多播地址隊(duì)列中．采用地址拷貝，等效于采用信元拷貝，但是更節(jié)省存儲(chǔ)空間．在交換過程中，一個(gè)多播地址隊(duì)列i中存儲(chǔ)的隊(duì)頭指針指向的信元一旦獲準(zhǔn)向輸出i輸出，如果它還有剩余的其他輸出端口待輸出，則該指針將轉(zhuǎn)入多播暫存地址隊(duì)列i中，在該隊(duì)列內(nèi)等待向其他輸出端口輸出，防止繼續(xù)逗留在多播地址隊(duì)列i內(nèi)，給隊(duì)列中其他去往輸出端口i信元造成隊(duì)頭阻塞．

另外，為了減輕隊(duì)頭阻塞，在每個(gè)輸入端口還設(shè)置了m個(gè)獨(dú)立隊(duì)列．當(dāng)信元隊(duì)列的隊(duì)長(zhǎng)超出了設(shè)定的門限時(shí)，如果一個(gè)多播流業(yè)務(wù)量大，就將該多播流的信元存儲(chǔ)在獨(dú)立隊(duì)列中，不和其他多播流混存，從而有助于減少其他多播流的信元對(duì)業(yè)務(wù)量大的多播流信元的阻塞．

2 權(quán)值動(dòng)態(tài)計(jì)算的多播調(diào)度算法

由于扇出分割把一個(gè)多播信元分多次輸出，延長(zhǎng)信元緩存被釋放的時(shí)間，容易導(dǎo)致輸入緩存的溢出，因此在多播交換中應(yīng)該盡量讓一個(gè)多播信元能夠一次向其所有輸出端口發(fā)送成功．筆者提出的多播調(diào)度算法就是為了達(dá)到這個(gè)目的的．為了做到這一點(diǎn)，使用調(diào)度算法和以往的啟發(fā)式調(diào)度算法不同．在以往的啟發(fā)式調(diào)度算法中，在一個(gè)信元的調(diào)度過程中其權(quán)值是不變化的，而在筆者提出的算法中，一個(gè)信元的一次調(diào)度過程中權(quán)值會(huì)變化．在筆者提出的算法中，一次調(diào)度分為兩個(gè)步驟：第1步為試探匹配；第2步為再匹配．在試探匹配當(dāng)中，信元i的權(quán)值為

其中，k1，k2是加權(quán)系數(shù)，Ti是信元i的等待時(shí)間，Pi為當(dāng)前時(shí)隙信元i所在輸入端口的優(yōu)先級(jí)．

定理1 令Tmin=min{Ti|Ti≠0}，如果k1>1且使得k2Pi

受篇幅所限，略去定理1的證明．當(dāng)信元調(diào)度時(shí)，輸出端口優(yōu)先選擇權(quán)值大的信元．根據(jù)定理1，信元的權(quán)值主要由其等待時(shí)間決定，等待時(shí)間長(zhǎng)的信元會(huì)優(yōu)先得到輸出的機(jī)會(huì)，確保交換時(shí)延．引入Pi是為了使任何兩個(gè)參與調(diào)度的信元的權(quán)值都不同，避免由權(quán)值相同而引起的扇出分割．例如，多播信元1與多播信元2權(quán)值相同，而且有共同的輸出端口，即輸出3、4、5，如果輸出3選擇信元1，輸出4與5選擇信元2，那么這兩個(gè)多播信元都不能向所有端口發(fā)送，引起扇出分割，信元的權(quán)值不同則不會(huì)引起該問題．

對(duì)于式(1)中輸入端口優(yōu)先級(jí)的設(shè)置，筆者提出雙向移位的優(yōu)先級(jí)設(shè)置方法．假設(shè)路由器有N個(gè)輸入端口，則輸入端口的優(yōu)先級(jí)取為 0～ N-1 的N個(gè)整數(shù)．令Pi(j)表示端口i在時(shí)隙j時(shí)的優(yōu)先級(jí)，l= j modN，m= (i- l) modN:

根據(jù)式(2)，由于Pi≤N，所以只要k2的值較小，很容易使定理1中k2Pi

定理2 雙向移位的優(yōu)先級(jí)設(shè)置方法，當(dāng)輸入端口數(shù)量N為偶數(shù)時(shí)，設(shè)i和k為任意的兩個(gè)輸入端口，則在所有時(shí)隙當(dāng)中，端口i在一半時(shí)隙中優(yōu)先級(jí)大于端口k，而在另一半時(shí)隙當(dāng)中端口k的優(yōu)先級(jí)大于端口i．

受篇幅所限，定理2的證明略去．定理2說明了筆者提出的雙向移位優(yōu)先級(jí)設(shè)置的方法可以保證輸入端口的優(yōu)先級(jí)具有良好的公平性．

試探匹配分為3步:

(1) 請(qǐng)求．輸入端口所有隊(duì)列的隊(duì)頭指針指向的信元以及獨(dú)立隊(duì)列的隊(duì)頭信元按照式(1)計(jì)算權(quán)值，然后向其所有的待輸出端口發(fā)送請(qǐng)求．如果一個(gè)輸入端口中有兩個(gè)隊(duì)頭指針指向的是同一個(gè)多播信元，那么只有一個(gè)隊(duì)頭指針發(fā)送請(qǐng)求，請(qǐng)求中包含有該信元的權(quán)值．

(2) 認(rèn)可．一個(gè)輸出端口會(huì)收到多個(gè)信元的請(qǐng)求，它從中選擇權(quán)值最大的信元對(duì)其進(jìn)行認(rèn)可．

(3) 確認(rèn)．如果一個(gè)輸入端口有多個(gè)信元收到不同輸出端的認(rèn)可，那么這個(gè)輸入端口選擇權(quán)值最大的信元的輸出端口進(jìn)行確認(rèn)．

試探匹配的上述3步構(gòu)成一次迭代，試探匹配階段只進(jìn)行一次迭代．當(dāng)該階段結(jié)束后，權(quán)值很大的信元的輸入端口會(huì)向其所有輸出端口發(fā)送確認(rèn)，這些信元會(huì)獲得從其所有輸出端口全部輸出的機(jī)會(huì)，稱這類信元為無扇出信元．其他信元如何輸出取決于再匹配階段的調(diào)度結(jié)果．如果一個(gè)多播信元的輸出端口當(dāng)中包含有無扇出信元的一些輸出端口，則由于該多播信元在與無扇出信元競(jìng)爭(zhēng)輸出端口時(shí)失敗，因此它一定會(huì)進(jìn)行扇出分割，稱這類多播信元為必扇出信元．這種必扇出的多播信元可能會(huì)對(duì)別的多播信元帶來不利影響．例如，有3個(gè)多播信元，信元1的輸出端口為{輸出1，輸出2，輸出3}，權(quán)值為9; 信元2的輸出端口為{輸出3，輸出4}，權(quán)值為8;信元3的輸出端口為{輸出4，輸出5，輸出6}，權(quán)值為7．信元1為無扇出信元，信元2為必扇出信元．由于信元2的權(quán)值大于信元3，因此在輸出端口4，信元2與信元3的競(jìng)爭(zhēng)中信元2會(huì)獲勝．所以必扇出信元會(huì)引起其他信元的扇出分割，這是應(yīng)該防止的．事實(shí)上，由于必扇出信元在以后的時(shí)隙中還要輸出，與其讓必扇出信元在本次調(diào)度中輸出，不如讓它把本次輸出的機(jī)會(huì)讓給其他信元，減少其他信元的扇出分割．在上面的例子中，應(yīng)該設(shè)法讓信元3具有比信元2大的權(quán)值，這樣信元3可以在輸出4的競(jìng)爭(zhēng)中獲勝，也無扇出分割．為了做到這一點(diǎn)，需要在迭代過程中重新計(jì)算多播信元的權(quán)值．所以，筆者提出的算法在試探匹配之后的再匹配階段的權(quán)值和試探匹配階段的權(quán)值具有不同的形式．

在再匹配階段，信元i的權(quán)值為

其中，Bi=cniFi，cni為信元i的輸出與無扇出信元的輸出相互重疊的數(shù)目．如果 cni> 0，則信元i是必扇出信元．Fi為信元i的輸出端口總數(shù)，Bi稱為信元i的拒阻率．信元i在再匹配的第1次迭代中的拒阻率由試探匹配的結(jié)果決定，再匹配其他迭代中的拒阻率由前面迭代的結(jié)果共同決定．在式(3)中， k3?k2，k3? k1，因此再匹配階段信元i的權(quán)值主要由拒阻率來決定．拒阻率越大，信元的權(quán)值越小．即必扇出的信元與無扇出信元的重疊端口數(shù)量越多，它的權(quán)值就越小，它就會(huì)越讓位于其他信元輸出．雖然必扇出信元在調(diào)度中會(huì)讓其他信元優(yōu)先輸出，但是它的等待時(shí)間卻會(huì)因此而增加，根據(jù)式(1)與式(3)，它在以后的調(diào)度過程中權(quán)值將增加，會(huì)獲得更為優(yōu)先的輸出機(jī)會(huì)，不會(huì)出現(xiàn)必扇出信元總得不到輸出機(jī)會(huì)的不公平現(xiàn)象．再匹配階段的迭代步驟和上文中試探匹配的步驟相同，再匹配階段進(jìn)行數(shù)次迭代．當(dāng)再匹配結(jié)束后，輸入端口與其發(fā)送了確認(rèn)的輸出端口之間形成匹配，它們之間可以進(jìn)行信元的發(fā)送．筆者提出算法的核心思想，就是通過必扇出信元把輸出的機(jī)會(huì)讓給其他信元，實(shí)現(xiàn)減少扇出分割的目標(biāo)．

3 計(jì)算機(jī)仿真分析

使用OPNET軟件對(duì)權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法進(jìn)行了計(jì)算機(jī)仿真．在仿真中，除了使用傳統(tǒng)的伯努利流量模型及on-off流量模型外，還提出一種輸出端口沖突嚴(yán)重的固定流量模型，以此來檢驗(yàn)各種多播交換方法的好壞．

固定復(fù)合流模型: 在每個(gè)輸入端口中，到達(dá)多個(gè)去往固定輸出端口集合的多播流，可以描述為

,

稱矩陣F為復(fù)合流矩陣，矩陣中的元素fi，j代表著輸入端口i注入的第j個(gè)多播業(yè)務(wù)流．業(yè)務(wù)流fi，j的信元到達(dá)服從on-off模型，在on期內(nèi)有信元連續(xù)到達(dá)，off期內(nèi)無信元到達(dá)．在矩陣F中，同一列中的多播流沒有相同的輸出端口，而任意兩個(gè)不屬于同一列的多播流都包含有共同的輸出端口．例如，對(duì)于一個(gè)有3個(gè)輸入端口、每個(gè)輸入端口注入5個(gè)多播業(yè)務(wù)的復(fù)合流，F(xiàn)矩陣為

筆者所做的仿真比較了另外兩種多播調(diào)度算法FIFOMS[7]與MQ-SCPX[8]與筆者提出算法的性能．其中FIFOMS與筆者提出的算法一樣，采用的是輸入緩存的Crossbar結(jié)構(gòu)，而MQ-SCPX采用的是交叉節(jié)點(diǎn)帶緩存的Crossbar結(jié)構(gòu)．以下仿真了不同算法下的信元交換時(shí)延．多播信元的交換時(shí)延定義為一個(gè)多播信元從其最后一個(gè)輸出端口輸出的時(shí)刻減去該多播信元從輸入端口輸入的時(shí)刻．仿真采用 16×16 的Crossbar，每次仿真100萬個(gè)交換時(shí)隙．權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法分為兩種，MSDW1與MSDW2的調(diào)度機(jī)制完全相同，只是缺少多播暫存地址隊(duì)列．之所以要分為兩個(gè)算法，是要比較多播隊(duì)頭阻塞對(duì)交換性能的影響．

圖1 伯努利源下b=02時(shí)各算法的信元時(shí)延圖2 on?off源下各算法的信元時(shí)延

在圖1中給出了伯努利源下(b=0.2，b代表著一個(gè)多播信元去往一個(gè)輸出端口的概率)各個(gè)算法的時(shí)延(時(shí)延的單位是前文所說的交換時(shí)隙)．可以看出，伯努利源下各個(gè)算法的性能差別不大，性能都比較好，這是因?yàn)椴粗忻總€(gè)信元的輸出端口都是隨機(jī)產(chǎn)生的，因此形成不了持續(xù)地、比較強(qiáng)烈地輸出沖突．圖2中給出了on-off源下各個(gè)算法的時(shí)延．由于在一個(gè)on狀態(tài)期間的信元具有相同的輸出端口，所以不同輸入端口的信元如果有輸出沖突的話，輸出沖突會(huì)比伯努利源持續(xù)的時(shí)間更長(zhǎng)一些，更劇烈一些．仿真中設(shè)置的on期的平均長(zhǎng)度為32個(gè)信元時(shí)隙，不同on狀態(tài)期間多播信元的輸出端口隨機(jī)產(chǎn)生．可以看出，MSDW2算法的性能最好，而MSDW1雖然調(diào)度機(jī)制與MSDW2相同，但是由于它沒有多播暫存地址隊(duì)列，所以它的隊(duì)頭阻塞相對(duì)嚴(yán)重，導(dǎo)致性能不佳．因此可以看出克服隊(duì)頭阻塞對(duì)于提高多播交換性能的意義．

圖3中給出了使用式(4)中固定復(fù)合流的情況下，各個(gè)算法的時(shí)延．在圖3的仿真中，式(4)的5列業(yè)務(wù)中，每一列業(yè)務(wù)的流量比例都相同，各占總流量的20%．從圖3中可以看出，在固定復(fù)合流的模式下權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法比其他兩種算法具有明顯的優(yōu)勢(shì)．FIFOMS與MQ-SCPX分別在負(fù)載為0.55與0.65左右的時(shí)候，信元的時(shí)延迅速增長(zhǎng)，而權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法在負(fù)載接近1時(shí)，時(shí)延才有了顯著增加．

圖3 固定復(fù)合流下各算法的信元時(shí)延圖4 伯努利源下迭代次數(shù)對(duì)信元時(shí)延的影響

圖5 固定復(fù)合流下迭代次數(shù)對(duì)信元時(shí)延的影響圖6 有無扇出分割參數(shù)對(duì)信元時(shí)延的影響

筆者還仿真了迭代次數(shù)與算法性能的關(guān)系．從圖4中可以看出，在伯努利源的情況下，基本上只需要迭代3次就可以取得比較好的性能．而在固定復(fù)合流的情況下，如圖5所示，基本上進(jìn)行2次迭代就可以達(dá)到比較好的性能．因?yàn)樵诓聪滦旁妮敵龆丝谌慷际请S機(jī)的，而在復(fù)合流的情況下，信元的輸出端口全部都是固定的，因此在伯努利源下需要相對(duì)多一些的迭代次數(shù)．由于權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法需要的迭代次數(shù)較少，因此權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法具有較低的實(shí)現(xiàn)復(fù)雜度．圖6中給出了在權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法的信元權(quán)值的計(jì)算中，有無扇出分割參數(shù)對(duì)交換性能的影響，仿真中使用的是式(4)的固定復(fù)合流．其中一條曲線為再匹配階段多播信元權(quán)值按照式(3)計(jì)算，而另一條曲線信元的權(quán)值始終按照式(1)計(jì)算．從圖6可以看出，如果在多播調(diào)度中只考慮等待時(shí)間，那么交換性能差，不能獲得高吞吐率，這充分說明了扇出分割因素在多播調(diào)度中的重要作用．

4 小 結(jié)

在多播交換中，過多的扇出分割將導(dǎo)致低吞吐率，而多播隊(duì)頭阻塞也會(huì)對(duì)吞吐率產(chǎn)生不利的影響．筆者提出了一種能夠減少多播扇出分割的輸入緩存Crossbar的多播調(diào)度算法權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度以及能夠減少隊(duì)頭阻塞的多播交換隊(duì)列組織結(jié)構(gòu)．對(duì)所提出的算法與結(jié)構(gòu)在多種業(yè)務(wù)模式下進(jìn)行了仿真，為了檢驗(yàn)多播交換算法的性能，還提出了一種輸出端口沖突嚴(yán)重的固定復(fù)合流模型．仿真結(jié)果表明，權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法在多種業(yè)務(wù)模式下均能取得良好的性能，而且算法的迭代次數(shù)少，實(shí)現(xiàn)復(fù)雜度較低．這說明權(quán)值動(dòng)態(tài)計(jì)算的調(diào)度算法是一種適合于在輸入緩存Crossbar中應(yīng)用的良好的多播調(diào)度算法．

[1] HE C Z, YEUNG K L. Ultra-large Feedback-based Switch Implementation for Data Center Networks[C]//IEEE International Conference on Communications. Piscataway: IEEE, 2015: 5485-5490.

[2]CHRYSOS N, MINKENBER C, RUDQUIST M, et al. High-radix Switches Made of Bufferless Clos Networks[C]//2015 IEEE 21st International Symposium on High Performance Computer Architecture. Piscataway: IEEE, 2015: 402-414.

[3]LIU K, YAN J, LU J, et al. Predictive Unicast and Multicast Scheduling in Onboard Buffered Crossbar Switches[J]. IEEE Communications Letters, 2016, 20(3): 498-501.

[4]Di C, MHAMDI L. Scheduling Multicast Traffic in Partially Buffered Crossbar Switches[C]//International Symposium on Computers and Communications. Piscataway: IEEE, 2013: 777-782.

[5]YU H, RUEPP S, BERGER M S, et al. Integration of Look-ahead Multicast and Unicast Scheduling for Input-queued Cell Switches[C]//2012 IEEE 13th International Conference on High Performance Switching and Routing. Piscataway: IEEE, 2012: 59-64.

[6]JIANG Y B, QIU Z L, GAO Y, et al. Multicast Support in Input Queued Switches with Low Matching Overhead[J]. IEEE Communications Letters, 2012, 16(12): 2083-2086.

[7]PAN D, YANG Y Y. FIFO-based Multicast Scheduling Algorithm for Virtual Output Queued Packet Switches[J]. IEEE Transactions on Computers, 2005, 54(10): 1283-1297.

[8]WANG W F, LEE F C, LU G L. A Shared-memory Design for Crosspoint Buffered Switches under Mixed Uni-and Multicast Traffic[C]//24th IEEE International Conference on Advanced Information Networking and Applications Workshops. Piscataway: IEEE Computer Society, 2010: 133-138.

(編輯：郭 華)

Multicast scheduling algorithm with a dynamic weight for the input buffered Crossbar

YANGFan，XUZhanqi，LIDanwu，ZHUJianfeng，MATao，DINGZhe

(State Key Lab. of Integrated Service Networks, Xidian Univ., Xi’an 710071, China)

A multicast scheduling algorithm with a dynamic weight is proposed for the input buffered crossbar. The address of the multicast cell is copied and saved according to its destination ports to decrease the effect of head of line blocking. When a multicast cell is scheduled, its weight is computed in each iteration according to its fanout splitting dynamically to give more chances for the low fanout splitting cells to export. This scheme can decrease the fanout splitting of multicast cells. The input port congestion under a heavy multicast traffic load can be effectively avoided if multicast fannout splitting is decreased. To verify the performance of the proposed scheduling algorithm, a multicast traffic mode with few perfect matchings is proposed. Simulation results show that the new scheduling algorithm has a good throughput under this rigorous traffic mode and other traditional traffic modes.

multicast switching; scheduling; fanout splitting; head of line blocking; throughput

2014-10-24

時(shí)間：2016-04-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(61572391)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(K5051301023)

楊 帆(1973-)，男，副教授，E-mail: fany@xidian.edu.cn．

http://www.cnki.net/kcms/detail/61.1076.tn.20160401.1622.028.html

10.3969/j.issn.1001-2400.2016.06.014

TN915

A

1001-2400(2016)06-0080-06