張博，汪斌強(qiáng)，朱圣平

（國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002)

1 引言

目前，互聯(lián)網(wǎng)開始進(jìn)入下一代網(wǎng)絡(luò)新時(shí)期，據(jù)2010年Arbor公司與美國密西根大學(xué)的一份持續(xù)2年的聯(lián)合研究報(bào)告[1]，多媒體音視頻的應(yīng)用服務(wù)成為了當(dāng)今互聯(lián)網(wǎng)的發(fā)展主流。中國互聯(lián)網(wǎng)絡(luò)信息中心(CNNIC)2011年7月中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[2]表明：網(wǎng)絡(luò)視頻繼續(xù)保持平穩(wěn)增長，2011年6月中國網(wǎng)絡(luò)視頻用戶達(dá)3.01億，作為與線下電視最為相近的互聯(lián)網(wǎng)服務(wù)，網(wǎng)絡(luò)視頻服務(wù)是使用最多的服務(wù)之一。視頻流有典型的特性，其數(shù)據(jù)內(nèi)容趨向于單點(diǎn)發(fā)送，多點(diǎn)接收，即多播。如今流行的基于視頻應(yīng)用的 IPTV、視頻會(huì)議、交互式仿真、多方游戲等應(yīng)用的流量都具有多播特性。

多播交換結(jié)構(gòu)研究開始于 1984年，Huang和Knauer首次對(duì)ATM網(wǎng)絡(luò)中多播數(shù)據(jù)的交換問題予以關(guān)注，并設(shè)計(jì)一種新型交換結(jié)構(gòu)來支持多播，由此提出了第一個(gè)多播交換結(jié)構(gòu)——Starlite[3]。1988年，Deering[4]提出了將多播功能結(jié)合到數(shù)據(jù)網(wǎng) IP層的多播結(jié)構(gòu)。1992年，多播實(shí)驗(yàn)網(wǎng)——Mbone建立[5]。目前，較完整的多播協(xié)議體系已經(jīng)形成，IP多播的研究工作逐漸集中于流量控制和擁塞控制研究，無線多播研究和大規(guī)模高效多播研究。

對(duì)于大規(guī)模高效多播研究，基于banyan的多播交換結(jié)構(gòu)大多采用多播復(fù)制的方法，Tony Lee[6]提出了一種內(nèi)部無阻塞的復(fù)制網(wǎng)絡(luò)設(shè)計(jì)方案，但結(jié)構(gòu)過于復(fù)雜。文獻(xiàn)[7]對(duì)該結(jié)構(gòu)進(jìn)行改進(jìn)，但輸入分組復(fù)制要求的總和超出輸出端口的數(shù)量時(shí)，滿溢的現(xiàn)象便會(huì)發(fā)生。Yeh等人[8]提出了一種基于Knockout理論多播交換結(jié)構(gòu)，每個(gè)輸入端口采用完全連接的方式連接到所有的輸出接口模塊。但該方案的大規(guī)模擴(kuò)展性能存在瓶頸?；贑los結(jié)構(gòu)的多播交換，文獻(xiàn)[9]引入了一種路徑分配向量，但整個(gè)路徑?jīng)Q策時(shí)間復(fù)雜度為O(K)，無法大規(guī)模擴(kuò)展。2010年的文獻(xiàn)[10]證明了對(duì)Clos網(wǎng)絡(luò)進(jìn)行多播路徑匹配是NP完全問題?；贑rossbar多播交換結(jié)構(gòu)是當(dāng)前的主流類型，Pan等人[11]提出了一種將信元載荷與目的地址信息分開存儲(chǔ)的方案，但交換結(jié)構(gòu)的加速比高。文獻(xiàn)[12]針對(duì)IPTV提出了一種扇出無關(guān)的多播交換結(jié)構(gòu)，但該結(jié)構(gòu)要求到達(dá)過程滿足強(qiáng)大數(shù)定律，且多播輸出阻塞率高?；贑rossbar緩存單多播聯(lián)合調(diào)度算法[13]采用了分級(jí)和層次化的調(diào)度機(jī)制，但該調(diào)度機(jī)制仍然存在O(N( 2N- 1 ))隊(duì)列復(fù)雜度瓶頸。

以上分析中多播結(jié)構(gòu)和調(diào)度機(jī)制固有的瓶頸使其不具備大規(guī)模擴(kuò)展能力，可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)理論體系[14]對(duì)多播問題的原因進(jìn)行了分析。從多播研究的整體看，終端基本是以軟件方式實(shí)現(xiàn)各種應(yīng)用層，通常不存在瓶頸，而路由交換節(jié)點(diǎn)的實(shí)現(xiàn)是多播性能的關(guān)鍵。路由交換節(jié)點(diǎn)的多播實(shí)現(xiàn)方式可以分為多次單播軟件調(diào)度方式和硬件電路線速扇出拷貝方式。目前路由交換節(jié)點(diǎn)上多播多數(shù)采用多次單播的軟多播[15]，即在路由前對(duì)多播分組先進(jìn)行復(fù)制而后各自在源端口隊(duì)列排隊(duì)，但軟多播實(shí)時(shí)性差，不能保證服務(wù)質(zhì)量。

在可重構(gòu)基礎(chǔ)網(wǎng)絡(luò)中，有效彌合多播業(yè)務(wù)特性和網(wǎng)絡(luò)服務(wù)能力的一個(gè)途徑是將多播業(yè)務(wù)特征需求與網(wǎng)絡(luò)承載服務(wù)二者抽象成一種特定的“業(yè)務(wù)—服務(wù)”映射模型，多播服務(wù)根據(jù)多播業(yè)務(wù)需求，構(gòu)建節(jié)點(diǎn)和鏈路資源獨(dú)享的可重構(gòu)多播服務(wù)承載網(wǎng)，這就要求交換層面必須采用完全分布式的控制機(jī)制，才能將節(jié)點(diǎn)交換資源有效分割給多播業(yè)務(wù)。因此，可重構(gòu)基礎(chǔ)網(wǎng)絡(luò)多播交換機(jī)制采用硬件電路線速扇出的多播拷貝方式和自路由尋路方式。其分布式自路由尋路方式有效地解決了緩存調(diào)度的瓶頸問題；其線速扇出與網(wǎng)絡(luò)負(fù)載相適應(yīng)，避免了輸出競爭等待；其等級(jí)數(shù)的交換路徑，時(shí)延抖動(dòng)小，避免了時(shí)延抖動(dòng)大造成的多播性能下降問題。

基于此，本文提出了部分扇出多播交換阻塞率模型，該模型具有完全分布式自路由，無需端口匹配，無內(nèi)部緩存，無緩存時(shí)延的特點(diǎn)。當(dāng)構(gòu)建純多播服務(wù)承載網(wǎng)或單多播混合服務(wù)承載網(wǎng)時(shí)，可采用關(guān)閉部分22×布爾單元和級(jí)間比特置換的重構(gòu)操作實(shí)現(xiàn)其交換資源的邏輯隔離，由于其分布式的特點(diǎn)，多播服務(wù)承載網(wǎng)之間無相關(guān)性，大大簡化了多個(gè)可重構(gòu)服務(wù)承載網(wǎng)構(gòu)建的控制復(fù)雜度，增強(qiáng)了多播交換結(jié)構(gòu)的可擴(kuò)展性。

2 逐級(jí)部分扇出交換結(jié)構(gòu)

定義1[16]并播單元：0-1并播單元輸入定義在字母表{0 -bound, 1 -bound,idle,bicast} ，即定義在{10,11,00,bicast}域中，規(guī)定10 ＜ 00 =bicast＜00，bicast為一個(gè)輸入端的輸入信號(hào)同時(shí)輸出到Output-0和 Output-1，在判決選路時(shí)，使用表 1的規(guī)則。當(dāng)bicast與空為輸入時(shí)，則輸出端口同時(shí)輸出該信號(hào)。

表1 基于{10,bicast,11}域的輸入控制

定義2[16]布爾單元：0-1并播單元可以看成22×的布爾單元，其交換規(guī)則為：輸入為含有2個(gè)元u和v的偏序集，輸出相當(dāng)于對(duì)輸入偏序集中的元求上確界和下確界，由格理論知u∧v為下確界，u∨v為上確界。

其中，u∨v=uorv，u∧v=uandv，如圖1所示，滿足：當(dāng)u≤v時(shí)，則u∧v=u,u∨v=v,當(dāng)u≥v時(shí)，則u∧v=v,u∨v=u。

圖1 布爾單元

0,1,I,B分別代表0 -bound, 1 -bound,idle,bicast輸 入 ， 則 有 表 達(dá) 式0 ∧ 1 = 0 ,0 ∨ 1= 1 ，I∧B= 0 ,I∨B=1。

定義3 布爾群組集線器：采用布爾單元組成的banyan類網(wǎng)絡(luò)或擴(kuò)展banyan類網(wǎng)絡(luò)為布爾群組集線器，對(duì)于2G- t o-G的布爾群組集線器滿足：該集線器將2G個(gè)輸入信號(hào)中最大的G個(gè)信號(hào)傳輸?shù)骄哂凶畲筝敵龅刂罚ㄝ敵龆丝趶纳贤碌牡刂肪幮驗(yàn)槎M(jìn)制表示的0→2G-1）的G個(gè)輸出端口，并將其余信號(hào)傳輸?shù)阶钚≥敵龅刂返腉個(gè)輸出端口。

2G- t o-G布爾群組集線器構(gòu)建方法可參見文獻(xiàn)[17]，以雙調(diào)循環(huán)排序器為例，其基本排序原理如圖2所示，采用點(diǎn)線式表示雙調(diào)循環(huán)排序器網(wǎng)絡(luò)，設(shè)a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p∈P，P為線性序集，根據(jù)布爾多項(xiàng)式比較方式可以得到排序序列A1≤A2≤ … ≤A16，其中，A1=a∧b∧ …∧p，A16=a∨b∨ … ∨p。如果P是{0,1}，則a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p中任意輸入為 1通過該網(wǎng)絡(luò)都可以到達(dá)輸出端的8個(gè)高地址，其余的到達(dá)8個(gè)低地址，假設(shè)該輸入中有6個(gè)輸入變量為1，即a= 1 ,f= 1 ,g= 1 ,k= 1 ,m= 1 ,o=1，經(jīng)該集線器，得到A11=A12=A13=A14=A15=A16=1.

對(duì)于一個(gè)N×N的單播交換結(jié)構(gòu)，其輸入信元目的地址可能組合為NN。而對(duì)于N×N多播交換結(jié)構(gòu)，由于每一個(gè)輸入信元的目的地址可能是部分或全部輸出端口的組合，則整個(gè)交換結(jié)構(gòu)其輸入信元目的地址的組合多達(dá)(2N- 1 )N。當(dāng)N大時(shí)，大規(guī)模多播交換結(jié)構(gòu)的調(diào)度配對(duì)具有很高的復(fù)雜性，因此在大規(guī)模（如萬端口交換結(jié)構(gòu)）的情況下，要求交換結(jié)構(gòu)在數(shù)據(jù)傳輸控制過程中不能采用集中式方式，而要分布式配對(duì)，以減小復(fù)雜度，因此采用自路由的方式來實(shí)現(xiàn)多播數(shù)據(jù)傳輸。由于一個(gè)多播信元有2N- 1種目的地址的組合，其信元分組自路由的編碼開銷的最少二進(jìn)制位為O(lb(2N- 1 )) ≈O(l b 2N) =O(N)，當(dāng)交換結(jié)構(gòu)的規(guī)模變大時(shí)，如N= 1 024，則每個(gè)多播信元自路由目的地址最小的編碼代價(jià)為1 024bit=128byte，巨大的編碼開銷使得帶寬的利用率變低，信元傳輸?shù)臅r(shí)延增大，故在信元傳輸過程中必須采用分級(jí)控制。

參考多路徑自路由模型[1]建立基于布爾群組集線器的 banyan類交換網(wǎng)絡(luò)，設(shè)N= 2n,N=KG,K= 2k,G=2g，先構(gòu)造一個(gè)K×Kbanyan類網(wǎng)絡(luò)，這里采用分治banyan類（divide-and-conquer）網(wǎng)絡(luò)。然后將網(wǎng)絡(luò)中的2×2交換單元用2G-to-G布爾群組集線器代替。取K= 24，G= 23，可得圖3所示的交換結(jié)構(gòu)。該交換結(jié)構(gòu)逐級(jí)進(jìn)行自路由選路，先將分組交換到某個(gè)輸出群組，而后進(jìn)行時(shí)分輸出。該交換結(jié)構(gòu)的多播分組在每個(gè)布爾群組集線器中部分扇出。

圖2 雙調(diào)循環(huán)排序器點(diǎn)線式結(jié)構(gòu)

圖3 128×128布爾群組集線器banyan類交換網(wǎng)絡(luò)

3 部分扇出多播交換阻塞率模型

3.1 部分扇出自路由機(jī)制

如圖4所示，交換結(jié)構(gòu)的自路由分組格式分為帶內(nèi)控制信息和有效載荷2部分，帶內(nèi)控制信息進(jìn)行選路控制。自路由方式有2種，一種為每經(jīng)過一級(jí)，該級(jí)的有效位被處理后決定輸出，所以對(duì)于第j,1≤j≤m級(jí)，1gj為該級(jí)的有效選路信息，由此可實(shí)現(xiàn)該控制分組的正確尋路。另一種為每經(jīng)過一級(jí)，其有效位在下一級(jí)依然保留被再利用，控制信號(hào)在每一級(jí)均為 1gjgj+1…gm。在集線器互聯(lián)的banyan類網(wǎng)絡(luò)中選擇前者，在布爾群組集線器中選擇后者。

圖4 自路由分組格式

以8-to-3布爾群組集線器為例，由圖5(a)和圖5(b)對(duì)比不難看出，由于輸出信息中仍然含有B控制信息，因此多播交換網(wǎng)絡(luò)采用部分扇出的方式。當(dāng)有單播加入時(shí)，即將圖5(a)中的2個(gè)I控制位，變?yōu)?,1控制位，則圖5(b)中輸出信息中含有2個(gè)B的控制信息，多于圖5(a)中輸出的B控制信息數(shù)，即有一個(gè)B沒有與I進(jìn)入過同一個(gè)布爾單元，所以其多播性能會(huì)下降。假設(shè)輸入信息中無I信息，那么該多播信息就無法扇出。

圖5 8-to-3布爾集線器點(diǎn)線表示

結(jié)論：布爾群組集線器，具有部分扇出單播搶占優(yōu)先的多播能力。對(duì)于2n×2n

布爾多播交換結(jié)構(gòu)，根據(jù)信息熵理論，其輸出地址的任意子集帶內(nèi)控制信息都不能低于2nbit，但可以采用2 1n- 的0,1,,I B四狀態(tài)帶內(nèi)控制信息來滿足二進(jìn)制比特的帶內(nèi)控制。帶內(nèi)控制信息必須包括每一級(jí)的控制信息，這里采用四狀態(tài)的分割編碼(cut-through coding)法[17]。其帶內(nèi)控制信息為

自右向左進(jìn)行帶內(nèi)控制，前邊的位決定后邊控制位的分割。對(duì)于第一級(jí)輸入，當(dāng)Q=B，控制信息從 0端口輸出，控制信息從 1端口輸出，同時(shí)有效載荷扇出。當(dāng)Q= 0 ，控制信息從0端口輸出，且1端口控制信息無效。當(dāng)Q= 1，控制信息從1端口輸出，且0端口控制信息無效。對(duì)于第二級(jí)輸入，當(dāng)Q0=B時(shí)，控制信息從0端口輸出，控制信息從1端口輸出，同時(shí)有效載荷扇出。每一級(jí)依次類推，可將分組傳輸?shù)阶罱K的目的地址。以 23×23banyan網(wǎng)絡(luò)為例。由圖6(a)可見其2個(gè)帶內(nèi)控制信號(hào)共含有4個(gè)B，在無單播與其競爭的情況下，扇出到6個(gè)目的端口。當(dāng)某一2n× 2n布爾多播交換網(wǎng)絡(luò)輸入只有一個(gè)帶內(nèi)控制信號(hào)為(2n-1)bitB時(shí)，可扇出到2n- 1個(gè)目的地址。由圖6(b)可見，當(dāng)給網(wǎng)路加入2條單播數(shù)據(jù)分組，單播數(shù)據(jù)分組也會(huì)與該交換網(wǎng)絡(luò)中的多播產(chǎn)生競爭，而使多播扇出很少的分組。

圖6 banyan類網(wǎng)絡(luò)多播自路由

結(jié)論：布爾多播banyan類交換結(jié)構(gòu)，具有部分扇出單播搶占優(yōu)先的多播能力。

3.2 多播交換阻塞率模型

單多播混合輸入的交換網(wǎng)絡(luò)，先確定單播與多播爭用的布爾群組集線器中多播扇出的情況，扇出個(gè)數(shù)不同其阻塞率不同。由于布爾群組集線器具有部分扇出特性，因此隨著級(jí)數(shù)的增加，其分組流的個(gè)數(shù)不斷增大，因此其阻塞率不斷增大。

第i(1 ≤i≤m)級(jí)布爾群組集線器內(nèi)，單播控制信息不變?yōu)椋嗖タ刂菩畔?，其中，iq為二進(jìn)制數(shù)，長度為 1i-，每次當(dāng)B與I在同一個(gè)22×布爾單元時(shí)，其后邊的控制信息采用2.2節(jié)方法進(jìn)行碼分割。

下面分析該結(jié)構(gòu)在不同負(fù)載下的阻塞率。假定到達(dá)同一輸出群組內(nèi)的分組相互獨(dú)立，設(shè)隨機(jī)變量代表在某一時(shí)隙，到達(dá)第i級(jí)2 toGG- - 布爾群組集線器復(fù)用交換單元某輸入/輸出群組的分組數(shù)目，

XI1為第一級(jí)交換單元某輸入群組的分組數(shù)目，假設(shè)單播和多播業(yè)務(wù)都服從貝努利均勻分布，設(shè)單播業(yè)務(wù)源到達(dá)強(qiáng)度的參數(shù)λ=p1，則單播業(yè)務(wù)源在單個(gè)時(shí)隙里以概率p1到達(dá)，設(shè)多播業(yè)務(wù)源到達(dá)強(qiáng)度的參數(shù)λ=p2，則多播業(yè)務(wù)源在單個(gè)時(shí)隙里以概率p2到達(dá)，滿足條件p1+p2≤ 1，則第一級(jí)某一輸入群組到達(dá)單播分組個(gè)數(shù)XI1s為

第一級(jí)某一輸入群組到達(dá)多播分組個(gè)數(shù)1mIX為

其中，p=p1+p2，x1=xs+xm，xs表示單播個(gè)數(shù)，xm表示多播個(gè)數(shù)。對(duì)于布爾群組集線器到達(dá)分組并不是最后的輸出分組個(gè)數(shù)，為更多的扇出多播分組，假設(shè)每個(gè)多播分組帶內(nèi)控制信號(hào)由2k-1個(gè)B構(gòu)成(全B構(gòu)成)，單個(gè)布爾集線器中單播的優(yōu)勢(shì)導(dǎo)致其多播以一定概率扇出，因?yàn)榧€器中只有1bit有效位，所以每一個(gè)多播分組只能扇出1個(gè)或2個(gè)分組。對(duì)于第一級(jí)集線器有輸入XI1，YI1獨(dú)立同分布，假設(shè)AI1表示第一級(jí)某2G- t o-G布爾群組集線器輸入分組數(shù)總和，為簡化表示，采用DI（di）表示DI=di的概率P（DI=di） 。

?a1≤ 2G， ?I∧B= 0 ,I∨B=1， 使 得a1+x1m2+y1m2≤ 2G，其中，x1m=x1m1+x1m2,y1m=y1m1+y1m2，x1m1,y1m1為無扇出的多播分組，x1m2,y1m2為扇出2個(gè)分組的多播分組。實(shí)際輸出的分組的總數(shù)a'1為

當(dāng)a'1＜2G時(shí)多播全被扇出，當(dāng)a'1=2G時(shí)，存在部分多播無扇出的情況。當(dāng)有z'1＜G的分組到達(dá)某輸出群組，則至少有z'1≤a'1＜ 2G分組到達(dá)該集線器的輸入，無路徑錯(cuò)誤選擇，當(dāng)有z'1=G的分組到達(dá)某輸出群組，則有a'1=G,a'1=G+1,… ,a'1= 2G個(gè)分組競爭該輸出群組，則會(huì)發(fā)生某些分組路徑錯(cuò)誤選擇，導(dǎo)致阻塞。則第一級(jí)布爾集線器某輸出群組單多播混合分組個(gè)數(shù)z'1分布為

則第一級(jí)布爾群組集線器輸出單播分組概率分布XO1s（x'1s） 為

其中：

第一級(jí)集線器輸出多播分組概率XO1m（x'1m）為

其中，λ1m=1-λ1sλ'1m=1 -λ'1s，已知第i級(jí)的輸出為第i+ 1 級(jí)輸入，即XOis,XOim,XOi與XI(i+1)s,XI(i+1)m,XIi+1符合相同分布，實(shí)際輸入分組總數(shù)ai+1服從以下分布：

實(shí)際輸出的分組總數(shù)1'ia+服從以下分布：

第 1i+級(jí)布爾集線器某輸出群組單多播混合分組個(gè)數(shù)1'iz+分布為

從而推導(dǎo)出第 1i+級(jí)布爾群組集線器輸出單播分組個(gè)數(shù)1sOX分布和多播分組個(gè)數(shù)1mOX分布。迭代可得第k級(jí)的布爾集線器某輸出群組單多播混合分組個(gè)數(shù)kOX分布，單播分組個(gè)數(shù)ksOX分布，多播分組個(gè)數(shù)kmOX。

單播阻塞率指平均輸出單播分組數(shù)與平均輸入單播分組數(shù)的比，得式(1)。

多播阻塞率指平均輸出多播分組數(shù)與最大輸出多播分組數(shù)的比，得式(2)。

其中，(k+ 1)Gp2mod(G-Gp1)含義為：全B的帶內(nèi)控制信息，理想最大可扇出 (k+ 1 )Gp2個(gè)分組，但受到輸出端口數(shù)G和單播輸入分組數(shù)Gp1的影響，最大輸出 (k+ 1)Gp2mod(G-Gp1)個(gè)多播分組。

多播扇出率指輸出多播分組個(gè)數(shù)與輸入多播分組個(gè)數(shù)的比，得式(3)。

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

本節(jié)采用 MATLAB軟件對(duì)布爾群組集線器自路由交換網(wǎng)絡(luò)在均勻分布業(yè)務(wù)源下的單播阻塞率、多播阻塞率和扇出率進(jìn)行仿真。對(duì)于Bernoulli均勻分布業(yè)務(wù)源，群組業(yè)務(wù)到達(dá)服從二項(xiàng)分布，業(yè)務(wù)強(qiáng)度采用歸一化負(fù)載強(qiáng)度表示，對(duì)于任意輸入群組i，滿足用ijλ表示到達(dá)輸入群組i去往輸出群組j的速率。

1) 單播阻塞率仿真

設(shè)定多播負(fù)載強(qiáng)度p2= 0 .2，單播負(fù)載強(qiáng)度0 ≤p1≤1-p2。對(duì)于N×N的交換網(wǎng)絡(luò),N=KG,K= 2k,G= 2g，在k= 6 的條件下比較G=8,16,32時(shí)的單播阻塞率，如圖7(a)所示，G越大其阻塞率越小。在G= 1 6的條件下比較k= 4 ,6,8時(shí)的阻塞率，如圖7(b)所示，k越大其阻塞率越大。該2種條件下，當(dāng)歸一化負(fù)載強(qiáng)度＞0.6時(shí)，其阻塞率大于等于 1 0-2，會(huì)造成單播分組的大量錯(cuò)傳。

圖7 單播阻塞率

原因分析：k決定交換網(wǎng)絡(luò)的級(jí)數(shù)，在k不變的情況下，多播負(fù)載強(qiáng)度20.2p= ，不同的G時(shí)，由于級(jí)數(shù)相同，其多播分組扇出個(gè)數(shù)對(duì)單播的影響基本相同。但G越大，其xG≤的概率越大，從而減少了xG＞時(shí)分組在布爾群組集線器中的內(nèi)部阻塞概率。當(dāng)G一定時(shí)，k越大，交換結(jié)構(gòu)的級(jí)數(shù)越大，由于多播的扇出特性，隨著級(jí)數(shù)的增加，其多播扇出數(shù)就會(huì)增加，增加了分組的個(gè)數(shù)，加大了內(nèi)部阻塞率。而且每一級(jí)由于布爾群組集線器中分組對(duì)輸出群組的均勻選擇，存在一定的路徑錯(cuò)傳概率，同樣加大了單播阻塞率。

2) 多播阻塞率仿真

設(shè)定單播負(fù)載強(qiáng)度p1= 0 .2，多播負(fù)載強(qiáng)度滿足0 ≤p2≤1 -p1。在k= 6 的條件下比較G=8,16,32時(shí)的多播阻塞率，如圖8(a)所示，G越大其阻塞率越小。在G= 1 6的條件下比較k= 4 ,6,8時(shí)的多播阻塞率，如圖8(b)所示，k越大其阻塞率越大，但k不同時(shí)，其阻塞率區(qū)別不明顯。2種條件下，多播阻塞率小于等于 1 0-2。

圖8 多播阻塞率

原因分析：k決定交換網(wǎng)絡(luò)的級(jí)數(shù)，在k不變的情況下，單播負(fù)載強(qiáng)度p1= 0 .2，不同的G時(shí)，由于級(jí)數(shù)相同，單播負(fù)載強(qiáng)度相同，其單播分組對(duì)多播的影響基本相同。但G越大，其x≤G的概率越大，從而減少了x＞G時(shí)分組在布爾集線器中的內(nèi)部阻塞概率。當(dāng)G一定時(shí)，k越大，交換結(jié)構(gòu)的級(jí)數(shù)越大，但由于多播的扇出特性，當(dāng)級(jí)數(shù)大于等于4時(shí)，負(fù)載p2≥ 0 .2時(shí)，其4次扇出的多播分組個(gè)數(shù)就接近G- 0 .2G= 0 .8G，后幾級(jí)的多播扇出會(huì)很小，而對(duì)于式(2)，需要做模 (G-Gp1)運(yùn)算，所以k= 4 ,6,8時(shí)，其阻塞率區(qū)別不明顯。

3) 多播扇出率仿真

設(shè)定單播負(fù)載強(qiáng)度p1= 0 .2，多播負(fù)載強(qiáng)度0 ≤p2≤ 1 -p1，在k= 6 的條件下，比較G=8,16,32時(shí)的多播扇出率，如圖9(a)所示，歸一化負(fù)載強(qiáng)度為0.1時(shí)，多播扇出率接近7，G越大其扇出率越大，多播歸一化負(fù)載強(qiáng)度接近0.8時(shí)，其扇出率都趨近于1，但G不同時(shí)，其多播扇出率區(qū)別不明顯。在G=16的條件下，比較k= 4 ,6,8時(shí)的多播扇出率，如圖9(b)所示，k越大其多播扇出率越大。

圖9 多播扇出率

原因分析：k決定交換網(wǎng)絡(luò)的級(jí)數(shù)，在k不變的情況下，單播負(fù)載強(qiáng)度10.2p= ，不同的G時(shí)，由于級(jí)數(shù)相同，單播負(fù)載強(qiáng)度相同，其單播分組對(duì)多播的影響基本相同。G不同，但多播分組的輸入分組個(gè)數(shù)和輸出分組個(gè)數(shù)同等比例增加，所以扇出率變化不明顯。當(dāng)G變大時(shí)，xG≤的概率變大，從而減少了xG＞的概率，減少了分組在布爾集線器中的內(nèi)部阻塞概率，使式(3)分子變大，所以扇出率變大。當(dāng)G一定時(shí)，k越大，交換結(jié)構(gòu)的級(jí)數(shù)越大，由于多播的扇出特性，當(dāng)級(jí)數(shù)變大時(shí)，多播就會(huì)有更多的扇出分組， 8k= 比 6k= 時(shí)多了兩級(jí)扇出， 6k= 比 4k= 時(shí)多了兩級(jí)扇出，所以隨著k的變大，其扇出率明顯變大。當(dāng)多播負(fù)載非常小時(shí)，其多播可以完全扇出，其扇出率正比于k+ 1，所以當(dāng)歸一化負(fù)載強(qiáng)度為0.1時(shí)，k= 8 ,6,4時(shí)，多播扇出率分別接近于9,7,5。

4) 多播時(shí)延仿真

時(shí)延分為分組平均時(shí)延Da和分組最大時(shí)延Dm。若交換系統(tǒng)在一定時(shí)間內(nèi)交換的分組數(shù)為n，di代表第i,1≤i≤n個(gè)分組的時(shí)延，那么Da和Dm描述為

分組的時(shí)延主要由分組經(jīng)過2×2布爾單元個(gè)數(shù)決定，假設(shè)分組每經(jīng)過一個(gè)2×2布爾單元的時(shí)延為Δd，一般在ns級(jí)。

在k= 6 的條件下比較G= 8 ,16,32時(shí)的時(shí)延，如圖 10(a)所示，G越小時(shí)延越小。在負(fù)載強(qiáng)度小于等于 0.5時(shí)，其時(shí)延增長速度Tv的關(guān)系為Tv(G=32)＜Tv(G=16)＜Tv(G=8)，在負(fù)載強(qiáng)度＞0.5時(shí)，其時(shí)延增長速度Tv的關(guān)系為Tv(G=32)＞Tv(G=16)＞Tv(G=8)。在G= 1 6的條件下比較k= 8 ,6,4時(shí)的時(shí)延，如圖10(b)所示，k越小其時(shí)延越小。且負(fù)載強(qiáng)度在(0,0.8]范圍內(nèi)時(shí)，k不同，時(shí)延增長速度Tv變化不明顯。

圖10 多播時(shí)延

原因分析：在阻塞率相同的情況下，時(shí)延主要受2×2布爾單元級(jí)數(shù)的影響，該級(jí)數(shù)由集線器中2×2布爾單元的級(jí)數(shù)和banyan類網(wǎng)絡(luò)級(jí)數(shù)相乘得到。G不變，G越大，集線器中2×2布爾單元的級(jí)數(shù)越大，2×2布爾單元的總級(jí)數(shù)越大，所以時(shí)延變大。對(duì)于圖10(a)，當(dāng)負(fù)載強(qiáng)度小于等于0.5時(shí)，由于G= 3 2的阻塞率遠(yuǎn)遠(yuǎn)小于G= 1 6,G= 8 ，因此Tv(G=32)最小。當(dāng)負(fù)載強(qiáng)度大于 0.5時(shí)，由于G= 3 2的阻塞率與G=16,G=8在相同的數(shù)量級(jí)，但G=32時(shí)2×2排序器級(jí)數(shù)最大，所以Tv(G=32)最大。G不變，k越大，2×2交換單元的總級(jí)數(shù)越大，時(shí)延越大，而由圖8(b)可知，k不同時(shí)，其阻塞率變化不明顯，因此在圖10(b)中時(shí)延增長速度Tv無明顯變化。不論何種G,k參數(shù)的交換結(jié)構(gòu)，其時(shí)延總小于某個(gè)定值。例如：當(dāng)G= 3 2,k=6時(shí)，時(shí)延 小 于等于Dmax，約等于1 8 7.5Δt，當(dāng)G=16,k= 8 時(shí)，時(shí)延 小 于等于Dmax，約等于1 8 0Δt。

不同的業(yè)務(wù)對(duì)帶寬、丟失率、時(shí)延、抖動(dòng)等QoS需求是不同的，如電子郵件對(duì)實(shí)時(shí)性要求低，但對(duì)丟失率要求高，丟失后必須重傳；實(shí)時(shí)流媒體業(yè)務(wù)對(duì)實(shí)時(shí)性要求高，一定丟失率下不影響服務(wù)質(zhì)量。該單多播混合輸入部分扇出多播交換模型，當(dāng)單播負(fù)載強(qiáng)度控制在一定范圍內(nèi)時(shí)，如p1≤ 0 .2時(shí)，其多播阻塞率小于等于 1 0-2，所以該交換結(jié)構(gòu)可以滿足某些網(wǎng)絡(luò)場(chǎng)景的應(yīng)用，其多播時(shí)延總小于某個(gè)定值，且該定值在百納秒量級(jí)，所以該交換結(jié)構(gòu)能夠?yàn)榈竭_(dá)業(yè)務(wù)提供時(shí)延上限保障。

5 結(jié)束語

本文的阻塞率模型是部分扇出多播模型，由于單播搶占或阻塞，在單個(gè)交換節(jié)點(diǎn)扇出率小的多播分組可在下一個(gè)交換節(jié)點(diǎn)中再次進(jìn)行部分扇出。本文假設(shè)多播的帶內(nèi)控制信息為全B，即對(duì)所有輸出端口均有扇出，該假設(shè)忽略了多播對(duì)輸出端口集的限制，下一步工作，基于可控多播輸出端口集進(jìn)行多播扇出模型的建立，該模型需要考慮每一級(jí)是否扇出的問題。

[1] LABOVITZ C, IEKEL-JOHNSON S, MCPHERSO D. Internet inter-domain traffic[A]. Proc of the ACM SIGCOMM[C]. New Delhi,India, 2010, 75-86.

[2] 中國互聯(lián)網(wǎng)絡(luò)信息中心. 中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[EB/OL].http://www.cnnic.net.cn/dtygg/dtgg/201201/t20120116_23667.html,2011.China Internet Network Information Center. Statistical report of China Internet network development status[EB/OL].http://www.cnnic.net.cn/dtygg/dtgg/201201/t20120116_23667.html, 2011.

[3] HUANG A, KNAUER S. Starlite: a wideband digital switch[A]. Proc of Globecom[C]. Atlanta, GA, 1984. 121-125.

[4] DEERING S, CHERITON D. Multicast routing in datagram internetworks and extended LANs[J]. ACM Transactions on Computer Systems, 1990, 8(2):85-110.

[5] ERIKSSON H. Mbone: the multicast backbone[J]. Communication of the ACM, 1994, 37(8):54-55.

[6] LEE T T. Non-blocking copy networks for multicast packet switching[J]. IEEE Journal on Selected Areas in Communications, 1988, 6(9):1445-1467.

[7] GUO M H, CHANG R S. Multicast ATM switches based on input cells scheduling[A]. Proc of APCC[C]. Sydney, Australia, 1997. 1629-1632.

[8] YEH Y S, HLUCHYTJ M G, ACAMPORA A. The knockout switch:asimple, modular architecture for high-performance packet switching[J].IEEE Journal on Selected Areas in Communications, 1987, 5(8): 1274-1283.

[9] YANG Y, MASSON G M. Broadcast ring sandwich networks[J].IEEE Trans Computers, 1995, 44(10):1169-1180.

[10] JASTRZEBSKI A, KUBALE M. Rearrangeability in multicast clos networks is np-complete[A]. 2010 2nd International Conference on Information Technology (ICIT)[C]. 2010. 183-186.

[11] PAN D, YANG Y. FIFO-based multicast scheduling algorithm for virtual output queued packet switches[J]. IEEE Transactions on Computers, 2005, 54(10):1283-1297.

[12] 胡曦明. 有效支持IPTV業(yè)務(wù)的扇出無關(guān)交換結(jié)構(gòu)[D]. 鄭州: 信息工程大學(xué), 2007. 29-49.HU X M. Fanout-free Switch Fabric to Support IPTV Business[D].Zhengzhou: Infromation Engeering University, 2007. 29-49.

[13] HU H C, LIN P, GUO Y F. Integrated uni- and multicast traffic scheduling in buffered crossbar switches[A]. 3rd Intentional Conference on Communications and Networking in China (ChinaCOM’08)[C].Hangzhou, China, 2008. 66-72.

[14] 蘭巨龍. 可重構(gòu)信息通信基礎(chǔ)網(wǎng)絡(luò)體系研究[R]. 國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（973計(jì)劃）項(xiàng)目計(jì)劃任務(wù)書, 2011.LAN J L. Research on Foundition Network System of Reconfigurable Information Communication[R]. Planning Task Document of National Basic Research Program of China(973 Program), 2011.

[15] 劉瑩, 徐恪. Internet 多播體系結(jié)構(gòu)[M]. 北京：科學(xué)出版社, 2008.LIU Y, XU K. Internet Multicast Archithecture[M].Beijing: Science Press, 2008.

[16] LI S Y R. Unified algebraic theory of sorting, routing, multicasting,and concentration networks[J]. IEEE Transactions on Communications,2010, 58(1):247-256.

[17] LI S Y R. Algebraic Switching Theory and Broadband Applications[M]. San Diego, CA, USA: Academic Press, 2001. 281-321.

[18] 李揮, 何偉, 伊鵬. 排序集線器多級(jí)互連交換結(jié)構(gòu)的多路徑自路由模型[J]. 電子學(xué)報(bào), 2008, 36(1):1-8.LI H, HE W, YI P,et al. Modeling multi-path self-routing switching structure from multistage interconnection of sorting concentrators[J].Acta Electronica Sinica, 2008, 36(1):1-8.