張博，汪斌強，朱圣平

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

1 引言

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

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

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

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

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

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

2 逐級部分扇出交換結構

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

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

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

其中，u∨v=uorv，u∧v=uandv，如圖1所示，滿足：當u≤v時，則u∧v=u,u∨v=v,當u≥v時，則u∧v=v,u∨v=u。

圖1 布爾單元

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

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

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

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

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

圖2 雙調(diào)循環(huán)排序器點線式結構

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

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

3.1 部分扇出自路由機制

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

圖4 自路由分組格式

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

圖5 8-to-3布爾集線器點線表示

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

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

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

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

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

3.2 多播交換阻塞率模型

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

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

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

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

第一級某一輸入群組到達多播分組個數(shù)1mIX為

其中，p=p1+p2，x1=xs+xm，xs表示單播個數(shù)，xm表示多播個數(shù)。對于布爾群組集線器到達分組并不是最后的輸出分組個數(shù)，為更多的扇出多播分組，假設每個多播分組帶內(nèi)控制信號由2k-1個B構成(全B構成)，單個布爾集線器中單播的優(yōu)勢導致其多播以一定概率扇出，因為集線器中只有1bit有效位，所以每一個多播分組只能扇出1個或2個分組。對于第一級集線器有輸入XI1，YI1獨立同分布，假設AI1表示第一級某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個分組的多播分組。實際輸出的分組的總數(shù)a'1為

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

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

其中：

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

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

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

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

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

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

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

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

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

4 仿真實驗

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

1) 單播阻塞率仿真

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

圖7 單播阻塞率

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

2) 多播阻塞率仿真

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

圖8 多播阻塞率

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

3) 多播扇出率仿真

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

圖9 多播扇出率

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

4) 多播時延仿真

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

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

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

圖10 多播時延

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

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

5 結束語

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

[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)絡信息中心. 中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告[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è)務的扇出無關交換結構[D]. 鄭州: 信息工程大學, 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] 蘭巨龍. 可重構信息通信基礎網(wǎng)絡體系研究[R]. 國家重點基礎研究發(fā)展計劃（973計劃）項目計劃任務書, 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 多播體系結構[M]. 北京：科學出版社, 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]. 電子學報, 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.