基于布爾集線器的線速多播自路由交換結(jié)構(gòu)

塵福興，李揮，崔凱，張博

（1. 北京大學(xué) 深圳研究生院 深圳市云計(jì)算關(guān)鍵技術(shù)和應(yīng)用重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518055；2. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002）

1 引言

1984年，Huang和Knauer首次對ATM網(wǎng)絡(luò)中多播數(shù)據(jù)的交換問題予以關(guān)注，并設(shè)計(jì)出一種新型交換結(jié)構(gòu)來支持多播，提出了第一個(gè)多播交換結(jié)構(gòu)——Starlite[1]。自此，業(yè)界對高效的多播結(jié)構(gòu)進(jìn)行了持續(xù)的研究。其中，Saito提出了基于共享存儲式的交換結(jié)構(gòu)來實(shí)現(xiàn)多播的方法[2]。但是由于存儲器帶寬的限制使該結(jié)構(gòu)不能夠滿足大規(guī)模擴(kuò)展需求。Yeh提出了一種基于Knockout理論多播交換結(jié)構(gòu)，每個(gè)輸入端口采用完全連接的方式連接到輸出接口模塊[3]。Chao提出了基于該結(jié)構(gòu)的多播設(shè)計(jì)方案，但是由于文獻(xiàn)[3,4]結(jié)構(gòu)的級間采用總線式完全連接方式，所以該結(jié)構(gòu)存在線路器件驅(qū)動(dòng)能力的極限問題，使該類方案在大規(guī)模擴(kuò)展性能上存在瓶頸。

基于 banyan的多播交換結(jié)構(gòu)大多采用多播復(fù)制的方法，Lee提出了一種內(nèi)部無阻塞的復(fù)制網(wǎng)絡(luò)設(shè)計(jì)方案[5]，由于該方案累加和網(wǎng)絡(luò)及虛擬地址編碼器不適合大規(guī)模擴(kuò)展，會(huì)發(fā)生滿溢(overflow)的現(xiàn)象；多播地址轉(zhuǎn)換所需緩存開銷龐大，結(jié)構(gòu)過于復(fù)雜，難以滿足大規(guī)模擴(kuò)展的需求。文獻(xiàn)[6]提出了一種能夠?yàn)閺?fù)制網(wǎng)絡(luò)提供公平機(jī)制的方案，然而它進(jìn)一步增加了結(jié)構(gòu)復(fù)制絡(luò)的復(fù)雜性，使其難以應(yīng)用于大規(guī)模的交換結(jié)構(gòu)設(shè)計(jì)中。

文獻(xiàn)[7]提出了一種基于 Clos交換結(jié)構(gòu)多播調(diào)度算法，引入了一種路徑分配向量，但整個(gè)路徑?jīng)Q策時(shí)間復(fù)雜度較高，無法大規(guī)模擴(kuò)展。文獻(xiàn)[8]證明了對Clos網(wǎng)絡(luò)進(jìn)行多播路徑匹配是NP完全問題。

基于Crossbar多播交換結(jié)構(gòu)的研究則大都是關(guān)于多播調(diào)度算法。Hui和Ali分析了在隨機(jī)情況下扇出和非扇出交替類的多播調(diào)度算法的性能，這些研究都證明了由于信元頭阻塞（HOL blocking）會(huì)導(dǎo)致吞吐率大大降低[9,10]。Marsan在理論上證明了對于采用虛擬輸出隊(duì)列（VOQ）的大規(guī)模多播交換結(jié)構(gòu)，不存在一個(gè)有限的提速因子能使許可的多播流量達(dá)到100%的吞吐率[11]。Pan提出了一種將信元載荷與目的地址信息分開存儲的方案，但其要求的(N+1)(N為輸入/輸出的端口數(shù))倍于外部鏈路帶寬的加速比，本身就是大規(guī)模擴(kuò)展的瓶頸[12]。

從以上對多播交換結(jié)構(gòu)的研究中可以看出，現(xiàn)有的多播交換結(jié)構(gòu)都無法滿足大規(guī)模可擴(kuò)展、線速多播的要求，本文在分配格理論基礎(chǔ)上，通過將“統(tǒng)計(jì)線組”的技術(shù)應(yīng)用到分治網(wǎng)絡(luò)中，用合適的集線器來代替該網(wǎng)絡(luò)中節(jié)點(diǎn)，并從理論上對該結(jié)構(gòu)性能證明，從而得到具有低時(shí)延、無抖動(dòng)和無需排隊(duì)緩存優(yōu)勢以及滿足大規(guī)模可擴(kuò)展以及線速多播需求的線速多播交換結(jié)構(gòu)。該結(jié)構(gòu)在一定條件下能很好地解決多播交換結(jié)構(gòu)大規(guī)?？蓴U(kuò)展以及線速多播問題的同時(shí)，又能保證較好的服務(wù)質(zhì)量。

2 多級互聯(lián)完全分布式自路由模型和布爾多播交換單元

2.1 多級互聯(lián)分布式自路由模型

多級互連完全分布式自路由模型[13]以分治網(wǎng)絡(luò)(divide & conquer)[14]為基礎(chǔ)，而構(gòu)建的具有高度模塊化，最低的器件復(fù)雜度（N lb N）等優(yōu)點(diǎn)的多播交換結(jié)構(gòu)模型。以N=64[ id:(65):(654):(63)(52)(41): (65): (654): id ]的分治網(wǎng)絡(luò)為例，如圖1所示。其中，“:”表示一級2×2單元，而兩級間連線方式用一組位置換群元素表示，如(63)(52)(41)。

圖1 64×64的分治網(wǎng)絡(luò)

該類網(wǎng)絡(luò)的自路由特性由其“跡trace”和“導(dǎo)guide”[15]序列共同決定，給出了網(wǎng)絡(luò)的“跡 trace（TK）”和“導(dǎo)guide(RK)”序列及其自路由過程。對于一個(gè) N×N交換結(jié)構(gòu)，多級互聯(lián)網(wǎng)絡(luò)（MIN,multi-stage interconnection network）由于其分布式自路由特性，以及其理想的單元復(fù)雜度 Θ(NlbN)，因而適用于構(gòu)造大規(guī)模交換結(jié)構(gòu)。交換結(jié)構(gòu)的藝術(shù)就是由最基本的2×2元件通過各種拓?fù)浣Y(jié)構(gòu)以最低的代價(jià)構(gòu)造出符合性能指標(biāo)的大型交換系統(tǒng)。理想的結(jié)構(gòu)是其規(guī)?？梢匀我膺f歸擴(kuò)展，不存在任何瓶頸。因此基于該分布式自路由模型構(gòu)建多播交換結(jié)構(gòu)模型的理由和動(dòng)機(jī)是充分的、明顯的。構(gòu)建多播交換結(jié)構(gòu)的第一步應(yīng)該分析分布式自路由模型的基本交換單元及其原理。

圖1所示基本單元是由圖2(a)～圖2(c)狀態(tài)的自路由排序單元構(gòu)成，進(jìn)入該2×2基本自路由排序單元的數(shù)據(jù)分組排序交換過程可以使用帶內(nèi)信令來實(shí)現(xiàn)，例如，在數(shù)據(jù)分組的前面加上2位帶內(nèi)信令。第一位A1表示當(dāng)前時(shí)隙是否有數(shù)據(jù)分組，1表示存在有效數(shù)據(jù)分組，0表示不存在有效數(shù)據(jù)分組即為空分組；當(dāng)A1為1時(shí)第二位D1表示分組的輸出目標(biāo)端口地址才有意義，否則D1為無效位。故A1D1等于‘10’、‘11’、‘00’、‘01’時(shí)分別代表“輸出目標(biāo)端口為0的有效數(shù)據(jù)分組”，“輸出目標(biāo)端口為1的有效數(shù)據(jù)分組”，“空分組”，“空分組”。

自路由模型的基本2×2單元（如圖2(a)～圖2(c)）按如下規(guī)定的線性排序關(guān)系實(shí)現(xiàn)自路由：10＜00＜11，具體控制方式可參見表1。

圖2 2×2基本自路由排序單元處于BAR、CROSS、CONFLICT、BICAST的狀態(tài)

表1中，CONF(CONFLICT)表示沖突，由其他方式比如優(yōu)先級來決定哪個(gè)信號會(huì)被輸出。

表1 單播2×2基本自路由單元以兩位帶內(nèi)信令自路由的交換控制

自路由模型的基本單播2×2單元顯然不具備硬件電路拷貝的線速多播特性。為了達(dá)到線速多播交換的目的，需要將圖2中只有BAR和CROSS 2種單播路由方式的排序單元進(jìn)行重新定義，使其成為一種全新的滿足多播要求的排序交換單元，稱為多播交換單元（如圖2(d)、圖2(e)所示）?；窘粨Q單元在加入BICAST狀態(tài)后，需要滿足何種條件才能達(dá)到線速多播的要求，為了能夠方便描述和證明多播單元以及由其構(gòu)成的多播網(wǎng)絡(luò)特性，本文將從分配格的理論角度來說明。

2.2 布爾多播交換單元

在表1中定義輸入控制的基礎(chǔ)上，可以進(jìn)一步定義Ωroute={0-bound,1-bound,i dle}，即0?bound=10; 1?bound=11,idle=00。故 10＜00＜11 的線性排序等于如下規(guī)則的順序。

規(guī)則 1 0?bound＜idle＜1?bound

路由單元按照規(guī)則的序列排序即可將盡可能多的有效分組轉(zhuǎn)發(fā)到預(yù)定的輸出端口。當(dāng)出現(xiàn)2個(gè)0-bound分組或2個(gè)1-bound分組的輸出爭用時(shí)，BAR/CROSS狀態(tài)的選擇依賴于特定的應(yīng)用，如信號的優(yōu)先級。這樣的操作不影響信號自路由的最優(yōu)性。

當(dāng)排序單元應(yīng)用于多播時(shí)，必須定義新的帶內(nèi)信令和相應(yīng)的交換控制方式，例如表2所示。

表2 支持多播以線速扇出的2×2多播排序單元的信號控制

表2中，B表示BICAST多播分組（如圖2(d)、圖2(e)所示）；I表示IDLE空分組。

可見支持多播的自路由帶內(nèi)信令控制表必須擴(kuò)展為?bicast=?route∪{bicast}。

這個(gè)擴(kuò)展集合由規(guī)則1和規(guī)則2各自部分排序得到。多播單元對屬于集合?bicast的信號執(zhí)行排序，當(dāng)idle遇到bicast時(shí)交換控制遵循規(guī)則3。

規(guī)則 2 0?bound＜bicast＜1?bound

規(guī)則3 output-0端口輸出信號值0-bound，output-1端口輸出信號值1-bound，其后都跟隨著相同的負(fù)載。

這樣，分組的負(fù)載在通過多播單元時(shí)可以是BAR狀態(tài)、CROSS狀態(tài)或者BICAST狀態(tài)的硬件電路拷貝的線速多播方式。按這種方式，多播單元能將盡可能多的分組負(fù)載轉(zhuǎn)發(fā)到其預(yù)定目標(biāo)端口。

為了能夠方便分析多播單元的特性，排序規(guī)則1、2與交換規(guī)則3需要尋求一種可以同時(shí)滿足3種排序規(guī)則的理論，而分配格理論剛好能夠滿足需求。格是一個(gè)有二元操作數(shù)布爾和∨與布爾積∧，且遵守布爾交換律、布爾結(jié)合律、布爾冪等律、布爾吸收率的集合[15]。

常見的格是遵守布爾操作中并集和交集運(yùn)算的集合的一組子集。

規(guī)則4 a≤b?a∧b=a

根據(jù)規(guī)則4，每一個(gè)格都可以導(dǎo)出一個(gè)部分有序序列。如果一個(gè)部分有序集合（簡稱偏序集）中任意兩元素存在一個(gè)最大下界和一個(gè)最小上界，則稱這個(gè)偏序集為偏序格，用布爾和與布爾積表示這2個(gè)界限，偏序格邏輯上等同于格。圖3所示為2種格的舉例，其中圖3(a)是有3個(gè)變量的自由格，圖3(b)為分配格。

根據(jù)規(guī)則1和規(guī)則2，圖3(b)描述了?bicast的部分排序，很明顯偏序集?bicast具有偏序格的特性，因此被稱為格。至此多播單元運(yùn)行的3個(gè)規(guī)則1到規(guī)則3能夠被統(tǒng)一于以下布爾規(guī)則（規(guī)則5）。

規(guī)則5 輸出端口0的值為2個(gè)輸入的布爾積，輸出端口1的值為2個(gè)輸入的布爾和。

如果一個(gè)格滿足分配律

則此格為分配格。?bicast就是一個(gè)簡單的例子，如圖 3(b)所示。因此有時(shí)也把該多播單元稱為布爾單元。

圖3 2種格的舉例

本研究采用分配格來構(gòu)建多播排序和多播交換的自路由帶內(nèi)信號表。到目前為止，常用交換結(jié)構(gòu)信號表使用的都是線性有序集，尤其當(dāng)信號值為數(shù)字表示的時(shí)候更是如此。對所有帶內(nèi)信號進(jìn)行完全排序的要求不僅限制了結(jié)構(gòu)的應(yīng)用范圍，而且完全阻礙了多播操作。把2×2多播單元與2×2單播單元從分配格的角度來對比可以清楚地看出這一點(diǎn)。

2.3 多播集線器到布爾多播集線器一般化

定理1 （多播集線器定理[16]）以排序單元多級互聯(lián)網(wǎng)絡(luò)構(gòu)建的n-to-m的集線器（n個(gè)輸入，m個(gè)輸出的集線器）為參考，將其中的排序單元用多播單元替換。記信號表為?bicast，不妨設(shè)，輸入 V0個(gè) 0-bound，V1個(gè) 1-bound，以及VB個(gè)多播信號。可得到以下結(jié)論。

結(jié)論1 上面n?m個(gè)輸出端口最大可能產(chǎn)生共min｛n-m,V0+VB｝個(gè)0-bound和多播信號。

結(jié)論2 下面 m個(gè)輸出端口最大可能產(chǎn)生共min｛m,V1+VB｝個(gè)1-bound和多播信號。

2.2 節(jié)把基本交換排序單元統(tǒng)一到布爾單元并用布爾代數(shù)來描述，此處由基本單元多級互聯(lián)構(gòu)成的多播集線器同樣用布爾代數(shù)來描述。

定義1 令Vj(0≤j≤n)為n個(gè)變量 X0,X1,…,X(n-1)的合取范式。若1≤m＜n，當(dāng)

成立時(shí)，相應(yīng)的布爾交換器被稱為是n-to-m布爾集線器。

n×n布爾排序器在一定條件下等同于布爾集線器。如2×2布爾排序器和2-to-1布爾集線器，其實(shí)和布爾單元一樣。

推論1 當(dāng)Vj和σk應(yīng)用在任意分配格中的n元素而不是變量 X0,X1,…,X(n-1)的時(shí)候，式(1)、式(2)在定義1中仍是正確的。

在推論1中分配格的假設(shè)是關(guān)鍵，因?yàn)榉峙渎实膽?yīng)用在合取范式中的作用是非常重要。當(dāng)一個(gè)有序集合是分配格時(shí)，布爾集線器相對于普通集線器是一個(gè)高級版本。

定理2 （布爾集線器的0-1原理[16]）當(dāng)且僅當(dāng)輸入任意包含n?m個(gè)0和m個(gè)1的序列后，上面的n?m個(gè)端口輸出值為0，下面m個(gè)端口輸出值為1時(shí)，n×n布爾交換器就是n-to-m布爾集線器。

3 大規(guī)模擴(kuò)展線速多播交換結(jié)構(gòu)模型

為了構(gòu)建大規(guī)模擴(kuò)展多播交換結(jié)構(gòu)模型，本文把“統(tǒng)計(jì)線組”[15]技術(shù)應(yīng)用到2.1節(jié)的分治網(wǎng)絡(luò)中。將自路由分治網(wǎng)絡(luò)中的每一個(gè)2×2節(jié)點(diǎn)放大為2G×2G節(jié)點(diǎn)，并用 2G-to-G布爾多播集線器替換該節(jié)點(diǎn)，交換網(wǎng)絡(luò)中每一根連接線用一束共G根線替換，從而構(gòu)造了一個(gè)帶有統(tǒng)計(jì)復(fù)用特點(diǎn)的多播自路由結(jié)構(gòu)，每G根輸出線共享一個(gè)群組地址。由于通信波動(dòng)和突發(fā)性引發(fā)的分組丟失率隨 G值的增大呈指數(shù)級減小[13]，在可允許的輸入流量下，“統(tǒng)計(jì)線組”技術(shù)可以達(dá)到幾乎無阻塞交換。

在實(shí)際應(yīng)用中G表示為群組，將G根線組成的一束記為一個(gè)群組，這個(gè)值一般比較大，K表示群組數(shù)，N表示交換結(jié)構(gòu)的輸入/輸出的總線數(shù)N=KG。

如圖 4(a)所示為一個(gè) N=128，K=16，G=8的多播路由交換結(jié)構(gòu)。該結(jié)構(gòu)是通過將 16×16的banyan網(wǎng)絡(luò)中每一個(gè)2×2節(jié)點(diǎn)替換為2G-to-G的由布爾單元組成的布爾集線器來實(shí)現(xiàn)。這里G=8，在實(shí)際應(yīng)用中G本應(yīng)該為一個(gè)大的數(shù)，所以一個(gè)2n×2n banyan-type的G-line版本的網(wǎng)絡(luò)構(gòu)建成了一個(gè) N×N的幾乎無阻塞的多播交換器。根據(jù) fast knockout[17]集線器構(gòu)造算法或利用 bitonic circular再配合一級半清器（half-cleaner）[15]，可構(gòu)造G為任意大小的群組集線器，從而保證了交換結(jié)構(gòu)的大規(guī)?？蓴U(kuò)展性能。

圖4 布爾多播集線器交換結(jié)構(gòu)及內(nèi)部結(jié)構(gòu)

圖4(b)所示為圖4(a)中任一個(gè)2G-to-G的布爾多播集線器的內(nèi)部結(jié)構(gòu)圖。圖4(b)中的每一級（除了最后一級地址過濾器）中最小的單元即為2.2節(jié)的布爾多播交換單元。由圖4可以對本文提出線速多播交換的內(nèi)部結(jié)構(gòu)有一個(gè)更詳細(xì)的理解。

本文提出的線速多播交換模型所采用的完全自路由分治網(wǎng)絡(luò)結(jié)構(gòu)和布爾多播集線器都具有良好的大規(guī)?？蓴U(kuò)展性，交換結(jié)構(gòu)中每個(gè)最小的交換單元使用硬件電路拷貝的方式實(shí)現(xiàn)多播，從而保證了交換結(jié)構(gòu)的線速多播以及大規(guī)?？蓴U(kuò)展特性。此外，交換結(jié)構(gòu)模型中無排隊(duì)緩存，更不需要調(diào)度從而保證了多播時(shí)延不會(huì)高于某一個(gè)定值。

對于定理1，當(dāng)有一個(gè)適當(dāng)?shù)亩嗖バ盘柋?bicast為輸入時(shí)，多播集線器就能夠達(dá)到最優(yōu)的多播交換。而多播交換網(wǎng)絡(luò)則是由多播集線器遞歸構(gòu)造而成，當(dāng)用布爾單元代替集線器網(wǎng)絡(luò)中的排序單元時(shí)，對任意的一個(gè)格或分配格結(jié)構(gòu)的信號表，該定理是否也成立。由此深入考慮?bicast格結(jié)構(gòu)的支持多播集線器定理的本質(zhì)屬性，仔細(xì)觀察發(fā)現(xiàn)?bicast在結(jié)論1中分為上部理想{0,B}和下部理想{1,1}，在結(jié)論2中類似地分為{1,B}和{0,1}。

定理3 如果格 ?的非空子集 S滿足條件x∈S,y∈S?x∧y∈S,x∨y∈S，則S為子格；如果x∈S,y∈S?x∧y∈S，則子格S是一個(gè)上部理想；如果x∈S,y∈S?x∨y∈S，則子格S是一個(gè)下部理想。

定義2 如果2個(gè)格之間映射保持布爾運(yùn)算不變，則稱該映射為格同態(tài)。

如從格?到?2的格同態(tài)等同于格?劃分為一個(gè)上部理想和一個(gè)下部理想。

定理4 設(shè)μ是格?映射到?2的一個(gè)同態(tài)，那么格?上部理想為μ-1(0)和下部理想為μ-1(1)。若將格 ?劃分為上部理想 U和下部理想 L，對s∈U ,μ(s)=0和s∈L,μ(s)=1，則可以得到μ是格?到?2的同態(tài)。

定理5 對于由排序單元多級互聯(lián)網(wǎng)絡(luò)構(gòu)成的n-to-m集線器，用布爾單元替換多級互聯(lián)網(wǎng)絡(luò)中所有的排序單元，所得到一個(gè)n-to-m布爾集線器網(wǎng)絡(luò)便稱之為布爾集線器。

將任意的分配格?劃分為上部理想U(xiǎn)和下部理想L。從U中輸入u個(gè)值，0≤u≤m，從L中n-u個(gè)值進(jìn)入集線器網(wǎng)絡(luò)之后，有如下結(jié)論。

結(jié)論3 上部n?m個(gè)端口輸出min{n-m,u}屬于U的值。

結(jié)論4 下部m個(gè)端口輸出min{m,n-u}屬于L的值。

證明 根據(jù)定理5可知上述的單元為一個(gè)n-to-m布爾集線器。為了證明定理剩下的部分，令μ表示和s∈L,μ(s)=1中?到?2的同態(tài)。

用μ(s)替換每一個(gè)輸入信號 s。這就將 n個(gè)輸入信號值轉(zhuǎn)變?yōu)閡個(gè)0的和n?u個(gè)1的組合。從集線器網(wǎng)絡(luò)的性質(zhì)可知，上部n?m端口輸出為min{n-m,u}個(gè)0和下部n端口輸出個(gè)1。因?yàn)棣淌且粋€(gè)格同態(tài)，級間用同樣的信號替代。當(dāng)替代后集線器的一個(gè)輸出端口輸出值0或1時(shí)，則替代前其輸出值分別屬于μ-1(0)=U 或μ-1(1)=L。證畢。

將定理5應(yīng)用到Ω=Ωbicast，U={0,B}，L={I,1}，那么結(jié)論1和結(jié)論3變?yōu)橥耆嗤?。類似地，U={0,1}和L={B,1}結(jié)論2將和結(jié)論4一致。

定理6 針對大規(guī)?？蓴U(kuò)展多播結(jié)構(gòu)中的n-to-m集線器，將所有的排序單元用bicast單元來替換，則當(dāng)信號表是?bicast時(shí)，以下結(jié)論中有一項(xiàng)成立。

結(jié)論5 上面的n?m個(gè)端口輸出僅為0-bound信號。

結(jié)論6 下面的 m個(gè)端口輸出僅為1-bound信號。

結(jié)論7 沒有端口輸出為idle信號。結(jié)論8 沒有端口輸出為bicast信號。

證明 信號值 0-bound，1-bound，bicast和idle分別為0，1，B和I。bicast單元組成的多級互聯(lián)網(wǎng)絡(luò)的精確輸入組合為：V0個(gè) 0，V1個(gè) 1，VB個(gè)B，VI個(gè)I。由圖3(b)可看到該信號表滿足分配格的結(jié)構(gòu)，若將多級互聯(lián)網(wǎng)絡(luò)中的 bicast單元用布爾單元替換，則布爾集線器定理得以應(yīng)用，同時(shí)也保證了布爾集線器網(wǎng)絡(luò)構(gòu)成及式(1)、式(2)的應(yīng)用。證畢。

將信號表?bicast表示的格劃分為上部理想U(xiǎn)={0,B}和下部理想L={I,1}。可以得到由n元組構(gòu)成的對稱多項(xiàng)式σm+1的如下性質(zhì)。

性質(zhì)1 如果 V1+VI≥m+ 1，可得 σm+1的值不是1就是I，因?yàn)棣襪+1中的一些單項(xiàng)式只與n個(gè)變量中賦值為1和B的值的變量有關(guān)。

性質(zhì)2 如果 V1+VI≤m+ 1，可得 σm+1的值不是0就是B，因?yàn)棣襪+1中的一些單項(xiàng)式只與n個(gè)變量中賦值為0或B的值的變量有關(guān)。

另一種是，將理想的分為上部分U={1,B}和下部分L={0,I}。同理可得以下性質(zhì)結(jié)論。

性質(zhì)3 如果 V1+VB≥m+ 1，可得 σm+1的值是1或B。

性質(zhì)4 如果 V1+VB≤m + 1，可得 σm+1的值是0 或 I。

假設(shè)性質(zhì)2和性質(zhì)4成立，σm+1唯一可能的值就是0，再由式(1)可以得出結(jié)論4成立。

對稱地，假設(shè)性質(zhì)1和性質(zhì)3成立，σm+1唯一可能的值就是1，因此σm=1，再由式(2)可以得出結(jié)論6成立。

假設(shè)性質(zhì)2和性質(zhì)3成立，σm+1唯一可能的值就是B，因此σm≥σm+1=B。從式(1)可以得出，上部分n?m 個(gè)端口輸出不可能為I。從式(2)可以得出，下部分m個(gè)端口輸出也不可能為I。所以結(jié)論7可以成立。

由對稱的特性可得，在性質(zhì)1、性質(zhì)4假設(shè)下結(jié)論8也成立。

在定理6中，0-bound和bicast信號總數(shù)在多級互聯(lián)網(wǎng)絡(luò)被逐級保留，1-bound和 bicast信號總數(shù)亦然。同樣可以看出結(jié)論5到結(jié)論8的每一個(gè)聲明都暗示著結(jié)論1和結(jié)論2成立。因此定理6應(yīng)該可以說是布爾多播集線器原理的一個(gè)詳細(xì)版本。從定理6可以得出一個(gè)更通用的結(jié)論：布爾集線器理論不僅僅可以把盡可能多的信號路由到目的輸出群組，而且可以依據(jù)“優(yōu)先級”的不同而達(dá)到最佳路由。此處的“優(yōu)先級”要求集線器的信號表必須是分配格。這個(gè)定理適合通過各種可能的方式去劃分分配格的上部理想和下部理想。通過以下例子來說明。

圖5 優(yōu)先級多播信號表示例

設(shè)Ω={0+,0-,I,B,1-,1,1+}為在圖 5(a)中的分配格。?中元素的命名規(guī)則為：上標(biāo)‘+’為到達(dá)期望集線器的目的地址0或1的最高優(yōu)先級，‘?’表示最低優(yōu)先級。?中所有通過一個(gè)n-to-m布爾集線器的路由信號的優(yōu)先級涉及了所有可能的對 ?的劃分為上部理想U(xiǎn)集合和下部的理想L集合。這里可以組合

從定理5可以看出，在去往輸出群組0的元素中集合U中的每一個(gè)元素都比集合L中的元素的優(yōu)先級要高；同樣，信號路由到輸出群組1也是如此。應(yīng)用這個(gè)理論到上面所列出的5個(gè)劃分方法可以得到以下結(jié)論。

結(jié)論9 在有序子集{0+,0-,B,1-,1,1+}的信號中去往輸出群組 0的較小的元素被賦予較高優(yōu)先級，然而去往輸出群組1的信號被賦予較高的優(yōu)先級。布爾集線器的路由最佳性是和這個(gè)優(yōu)先級的策略相一致的。

結(jié)論10 類似的優(yōu)先級處理同樣可以應(yīng)用在有序子集{0+,0-,I ,1-,1,1+}中。

結(jié)論11 同時(shí)，B和I這2個(gè)信號在路由向任意輸出群組時(shí)被賦予同樣的優(yōu)先級，這就意味著B和I不能同時(shí)出現(xiàn)在彼此對立的輸出群組中。

如圖6(a)實(shí)例說明分配格?的信號通過一個(gè)8-to-4布爾集線器網(wǎng)絡(luò)的傳播過程，其中有上標(biāo)‘+’的信號是具有高優(yōu)先權(quán)處理的。0，1，B，I分別表示 0-bound，1-bound，bicast和 idle。圖中陰影部分單元表示發(fā)生多播的信號，在這里bicast和idle信號被0-bound和1-bound信號所替換。這樣輸出群組0得到盡可能多的0-bound和bicast信號，同時(shí)輸出群組 1得到盡可能的1-bound和bicast信號。此外，這個(gè)路由最優(yōu)是和結(jié)論9和結(jié)論11相一致的。

例如，圖6(b)例證了圖5(b)中非分配格Ω={0+,0-,I,B,1-,1,1+}中信號值通過同一個(gè)8-to-3布爾集線網(wǎng)絡(luò)的傳播過程，其理想的交換是得不到保障的。因?yàn)樵谶@個(gè)格中 B+∧I=0+和B+∨I=1+，一個(gè)高優(yōu)先級的bicast信號在一個(gè)布爾單元中遇到一個(gè)idle信號后輸出高優(yōu)先級0-bound和1-bound信號，從而導(dǎo)致輸出群組0丟失了一個(gè)有效信號，同時(shí)也只有一個(gè)有效信號出現(xiàn)在輸出群組0。這個(gè)次優(yōu)的路由結(jié)果反應(yīng)了在定義布爾交換，集線器或排序器中輸入信號需要滿足分配格的結(jié)構(gòu)才能達(dá)到最優(yōu)的多播交換。

圖6 信號通過布爾集線器網(wǎng)絡(luò)傳播過程

在實(shí)際應(yīng)用中非分配格有時(shí)會(huì)被用作信號表，因?yàn)楦邇?yōu)先級多播通信在整個(gè)通信量中占很小一部分，那么布爾集線器理論依舊能夠被統(tǒng)計(jì)應(yīng)用，這是一個(gè)特殊情況。

4 線速多播結(jié)構(gòu)阻塞率模型分析

從上述布爾多播單元 bicast的狀態(tài)可以看出，該多播交換結(jié)構(gòu)的特點(diǎn)是在交換網(wǎng)絡(luò)中線速扇出。當(dāng)扇出為1時(shí)即是單播，否則就是多播，所以該交換多播交換結(jié)構(gòu)支持單多播的混合輸入。分組的扇出率（多播扇出的個(gè)數(shù)）直接影響了其阻塞率。由于交換的規(guī)模是由其級數(shù)決定的，交換規(guī)模越大，多播分組扇出的可能性也就越大，交換的級數(shù)對阻塞率和扇出率也有直接的影響。

單播時(shí)自路由路徑 trace(guide)[15]信息表示為dφ(g)… dφ(2)dφ(1)1，其中，下角標(biāo)φ (1),φ(2),…,φ(g)表示級間置換信息[13]。多播分組頭信息序列為…Q110Q010Q100Q000Q01Q10Q00Q1Q01，多播分組頭信息的第一位1為多播有效位，此分組序列包含了該多播中所有單播的信息，從右向左依次排序，可以分解為多個(gè)單播分組的信息頭，并且都滿足單播的級間置換規(guī)則。

不妨設(shè)第 i(1≤i≤m)級布爾集線器內(nèi)單播分組控制信令為dφ(i)，多播分組控制信令為Qqi1，qi是二進(jìn)制數(shù)，其長度為i?1。每當(dāng)空分組I與多播分組B在同一個(gè)2×2的布爾單元相遇時(shí)，若該級滿足多播扇出控制要求，其兩端口的輸出控制信息則采用cut-through[15]的方法將多播信息頭進(jìn)行分割，否則多播頭信息不發(fā)生變化。

下面具體分析線速多播交換結(jié)構(gòu)在不同網(wǎng)絡(luò)負(fù)載下的分組阻塞率情況。假定各輸入群組所到達(dá)的分組滿足獨(dú)立同分布的要求，在某一時(shí)隙到達(dá)交換結(jié)構(gòu)網(wǎng)絡(luò)中第i級2G-to-G布爾集線器中某交換單元某輸入/輸出群組的分組數(shù)目表示為XIi/XOi(1≤i≤m )，其中，0≤XIi≤G,0≤XOi≤G 。

設(shè)交換結(jié)構(gòu)到達(dá)的業(yè)務(wù)數(shù)據(jù)總額為1，單播業(yè)務(wù)所占比例參數(shù)λ=P1，表示在單個(gè)時(shí)隙內(nèi)單播業(yè)務(wù)到達(dá)的概率為P1，多播業(yè)務(wù)所占比例參數(shù)為λ=P2，表示單個(gè)時(shí)隙里多播業(yè)務(wù)到達(dá)的概率 P2，用XI1s表示進(jìn)入交換結(jié)構(gòu)的第一級中某輸入群組的單播分組個(gè)數(shù)，則

其中，XI1m表示進(jìn)入交換結(jié)構(gòu)的第一級某輸入群組的多播分組個(gè)數(shù)。

P=P1+P2,x1=xs+xm，其中，xs表示單播分組個(gè)數(shù)，xm表示多播分組個(gè)數(shù)。如果xm≠0，表示存在多播分組，由于多播分組扇出的特點(diǎn)，那么在交換結(jié)構(gòu)中的某集線器最后輸出的分組個(gè)數(shù)在一定概率上要比輸入的分組多一些。假設(shè)每個(gè)多播分組在交換結(jié)構(gòu)的每一級都要求發(fā)生多播，即其帶內(nèi)多播控制信號全是由2k-1個(gè)B構(gòu)成，由于布爾集線器的輸入信號表為嚴(yán)格的分配格結(jié)構(gòu)，即當(dāng)單播與多播在集線器內(nèi)爭用同一個(gè)出口時(shí)，根據(jù)交換規(guī)則單播優(yōu)先級高而占用輸出端口，導(dǎo)致其多播會(huì)被誤路由，所以該多播只能以一定的概率扇出。XI1，YI1為交換結(jié)構(gòu)中第一級集線器的輸入，滿足獨(dú)立同分布要求。用AI1表示第一級布爾集線器輸入分組的總和。為了簡化表達(dá)式用DI(di)表示 DI=di時(shí)的概率P(DI=di)。

?a1≤2G,?I∧B=0,I∨B=1，使a1+x1m2+y1m2≤2G，其中，x1m=x1m1+x1m2，y1m=y1m1+y1m2，x1m1，y1m1為扇出為1的多播分組（即為單播分組），x1m2，y1m2為扇出2的多播分組。從而可得實(shí)際的輸出分組總和

其中，λ1m=1-λ1s，λ1m=1-，已知多播交換結(jié)構(gòu)的第i級集線器的輸出是第i+1級集線器的輸入，即滿足相同分布，由此可得集線器實(shí)際輸入的分組總數(shù)ai+1服從以下分布。

集線器實(shí)際輸出的分組總數(shù)ai′+1服從以下分布。

同樣可得出第i+1級布爾集線器的某輸出群組單多播分組總數(shù)的分布：

重復(fù)上述步驟可以推導(dǎo)出第i+1級布爾集線器輸出的單播分組個(gè)數(shù)XO(i+1)s分布，以及多播分組個(gè)數(shù)XO(i+1)m分布。通過的迭代的方法，可得第k級布爾集線器某輸出群組單多播分組個(gè)數(shù)的分布情況 XOks，XOkm。

單播阻塞率指平均輸入單播分組減去輸出單播分組數(shù)的平均值后再與平均輸入單播分組數(shù)的比，得式(13)。

多播的阻塞率要考慮扇出的因素，多播的輸出分組會(huì)遠(yuǎn)大于輸入分組，所以多播的阻塞率應(yīng)該為平均輸出多播分組數(shù)與理想最大輸出多播分組數(shù)的比，得式(14)。其中，(k+1)Gp2mod(G-Gp1)的含義為：因帶內(nèi)控制信令由全B組成，所以理想最大可扇出分組數(shù)可表示為(k+1)Gp2，但受到輸出端口數(shù)G的限制和單播輸入分組數(shù)Gp1的與多播分組爭用端口的影響，最大可輸出多播分組數(shù)表示為(k+1)Gp2mod(G-Gp1)。

5 仿真結(jié)果

本節(jié)采用C++編程實(shí)現(xiàn)在均勻分布業(yè)務(wù)源下對線速多播交換結(jié)構(gòu)的多播阻塞率和時(shí)延的仿真。阻塞率是指分組在經(jīng)過交換系統(tǒng)時(shí)沒能被成功交換到目的端口的概率。時(shí)延是指分組第一個(gè)比特進(jìn)入交換系統(tǒng)到分組第一個(gè)比特從交換系統(tǒng)輸出時(shí)所需要的時(shí)間。時(shí)延在交換系統(tǒng)中一般分為傳播時(shí)延和信號處理時(shí)延。仿真過程要求數(shù)據(jù)源滿足伯努利均勻分布，集線器的群組輸入業(yè)務(wù)要求服從二項(xiàng)分布，到達(dá)的業(yè)務(wù)強(qiáng)度用歸一化負(fù)載表示。

1)多播阻塞率仿真

負(fù)載強(qiáng)度對阻塞率有直接的影響，本節(jié)選取一個(gè)一個(gè)代表性的負(fù)載，不妨設(shè)單播業(yè)務(wù)所占負(fù)載的比例為P1=0.2，則可得多播業(yè)務(wù)所占負(fù)載的比例為0≤P2≤1-P1。在多播業(yè)務(wù)強(qiáng)度相對固定的情況下，通過改變交換網(wǎng)絡(luò)的級數(shù)參數(shù)K以及群組參數(shù)G的大小仿真多播阻塞率的情況。選取在K=4的條件下仿真并比較 G=8,16,32時(shí)多播的阻塞率情況。從圖7可以看出，隨著G增大其阻塞率而減小。因?yàn)閰?shù)K決定了交換結(jié)構(gòu)網(wǎng)絡(luò)的級數(shù)，當(dāng)K不變且單播業(yè)務(wù)負(fù)載強(qiáng)度相同時(shí)，則單播與多播在集線器中發(fā)生爭用的情況基本相同。然而若G變大，分組在布爾集線器內(nèi)部發(fā)生爭用的概率就變小，阻塞率也就越小。

圖7 G不同時(shí)的多播阻塞率

圖8的顯示的是群組G=32時(shí)，K=4、8、16時(shí)得到的多播阻塞率仿真結(jié)果。從圖中曲線可看出K變大其阻塞率也變大，然而在同一負(fù)載點(diǎn)上，K的不同，其阻塞率區(qū)別不明顯。這是因?yàn)橛捎诙嗖サ纳瘸鎏匦裕?dāng)交換結(jié)構(gòu)網(wǎng)絡(luò)級數(shù)不小于 4，歸一化負(fù)載P2≥0.2時(shí)，得到扇出的多播分組數(shù)接近G-0.2G=0.8G所以在最后的幾級布爾多播集線器中多播分組被扇出的概率會(huì)很小，所以在G=32歸一化負(fù)載下，雖然k不同，但其阻塞率差別并不明顯。

圖8 K不同時(shí)的多播阻塞率

2)多播分組時(shí)延仿真

多播分組在經(jīng)過交換結(jié)構(gòu)網(wǎng)絡(luò)的每一個(gè)布爾集線器中的每一個(gè)2×2布爾單元時(shí)，需要一定的時(shí)間完成對分組數(shù)據(jù)的處理，從而產(chǎn)生了時(shí)延。所以多播分組的時(shí)延主要由分組所經(jīng)過基本布爾單元個(gè)數(shù)決定，設(shè)分組在經(jīng)過任一個(gè)布爾單元時(shí)對數(shù)據(jù)處理的時(shí)間即時(shí)延為Δd。

多播交換結(jié)構(gòu)網(wǎng)絡(luò)的規(guī)模由k決定，每一個(gè)布爾集線器的規(guī)模則是G決定，交換結(jié)構(gòu)中布爾單元的個(gè)數(shù)則是由K和G共同決定。為了仿真多播時(shí)延數(shù)據(jù)，不妨先固定一個(gè)參數(shù)，設(shè)K=4，可以得到G=8,16,32的時(shí)延，如圖9所示。

從圖9中可看出G越小時(shí)延也越小。從圖中還可以看出 G不同時(shí)，各時(shí)延增長速度Tv的關(guān)系為Tv(G=32)＜Tv(G=16)＜Tv(G=8)，這是因?yàn)镚=32的阻塞率是最小的，所以分組丟失的概率較小，統(tǒng)計(jì)分組時(shí)延也就會(huì)最低。隨著負(fù)載的增大，當(dāng)負(fù)載大于 0.6時(shí)，時(shí)延增加的速度加快。

固定參數(shù)G=32時(shí)，得到K=4、8、12的時(shí)延仿真結(jié)果，如圖10所示，K越小其時(shí)延越小，K不同。從圖8可以得知，K不同，其阻塞率的變化不明顯，所以該時(shí)延曲線的變化也不明顯。該多播交換結(jié)構(gòu)采用的多級互聯(lián)的結(jié)構(gòu)，無論G，K參數(shù)如何變化，其時(shí)延也總會(huì)小于某一個(gè)定值。

圖9 K=4，G不同時(shí)的多播時(shí)延

圖10 G=32，K不同時(shí)的多播時(shí)延

6 結(jié)束語

本文提出的基于分配格的線速多播交換模型，具有低時(shí)延、無抖動(dòng)、可大規(guī)模擴(kuò)展優(yōu)點(diǎn)，當(dāng)多播業(yè)務(wù)負(fù)載強(qiáng)度控制在一定可允許的范圍內(nèi)時(shí)，其多播業(yè)務(wù)的阻塞率可以被接受，其多播時(shí)延總會(huì)小于某個(gè)定值，且該定值會(huì)在百納秒量級，所以該交換結(jié)構(gòu)能夠?yàn)榈竭_(dá)業(yè)務(wù)提供時(shí)延上限保障。該交換結(jié)構(gòu)模型可以解決某些網(wǎng)絡(luò)環(huán)境中對業(yè)務(wù)的特殊需求應(yīng)用的問題，如時(shí)延、阻塞率、線速多播等。

[1]HUANG A. Starlite: a wideband digital switch[A]. Proc Globecom'84[C]. Atlanta,GA,1984.1-5.

[2]SAITO H,YAMANAKA H,YAMADA H,et al. Multicast function and its LSI implementation in a shared multibuffer ATM switch[A].Networking for Global Communications,13th Proceedings IEEE[C].Toronto,Ont,1994.315-322.

[3]YEH Y S,HLUCHYJ M,ACAMPORA A. The knockout switch: a simple,modular architecture for high-performance packet switching[J].Selected Areas in Communications,1987,5(8):1274-1283.

[4]CHAO H J,CHOE B S,PARK J S,et al. Design and implementation of abacus switch: a scalable multicast ATM switch[J]. Selected Areas in Communications,1997,15(5):830-843.

[5]LEE T T. Nonblocking copy networks for multicast packet switching[J]. Selected Areas in Communications,1988,6(9): 1455-1467.

[6]CHAO H J,LIU B. High performance switches and routers[M].Wiley-IEEE Press,2007.

[7]MARCHOK D J,ROHRS C E,SCHAFER R M. Multicasting in a growable packet (ATM)switch[A]. INFOCOM'91. Proceedings. Tenth Annual Joint Conference of the IEEE Computer and Communications Societies Networking [C]. BalHarbour,FL,1991. 850-858.

[8]JASTRZEBSKI A,KUBALE M. Rearrangeability in multicast clos networks is np-complete[A]. Information Technology(ICJT)[C]. Gdansk,2010,183-186.

[9]HUI J Y,RENNER T.Queueing analysis for multicast packet switching[J]. IEEE Transaction Communications,1994,42(234): 723-731.

[10]ALI MK M,YANG S. Performance analysis of a random packet selection policy for multicast switching[J]. IEEE Transactions Communications,1996,44(3):388-398.

[11]MARSAN M A,BIANCO A,GIACCONE P,et al. Multicast traffic in input-queued switches: optimal scheduling and maximum throughput[J]. IEEE/ACM Transactions on Networking (TON),2003,11(3):465-477.

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

[13]HE W,LI H,WANG B,et al. Load-balanced multipath self-routing switching structure by concentrators[A]. IEEE International Conference on Communications,ICC’08[C]. Beijing,China,2008.5935-5939.

[14]LI H,LI S Y R. Layout complexity of bit-permuting exchange in multi-stage interconnection networks[M]. Boston: Kluwer Academic Publishers,2001.259-276.

[15]LI S Y R. Algebraic switching theory and broadband applications[M].Academic Press,2001.

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

[17]LI S Y R,LI H,KOO G M. Fast knockout algorithm for self-route concentration[J]. Computer Communications,1999,22(17):1574-1584.

[18]LI H,LI S Y R. On the Complexity of Concentrators and Multi-stage Interconnection Networks in Switching System[D]. Hong Kong: Chinese University of Hong Kong,2011.