第2章_交換單元與交換網(wǎng)絡(luò)新

1、 第第2章章 交換網(wǎng)絡(luò)交換網(wǎng)絡(luò)2.1 交換單元交換單元2.1.1 交換單元的概念交換單元的概念2.1.2 交換單元連接特性的交換單元連接特性的數(shù)學(xué)描述及連接的表示形式數(shù)學(xué)描述及連接的表示形式2.1.3 交換單元常用的連接方式交換單元常用的連接方式2.1.4 交換單元性能指標(biāo)交換單元性能指標(biāo)2.1.5 開關(guān)陣列開關(guān)陣列2.1.6 空分（空間）交換單元空分（空間）交換單元2.1.7 時分交換單元時分交換單元2.1.8 共享總線型時分交換單元共享總線型時分交換單元2.2 交換網(wǎng)絡(luò)交換網(wǎng)絡(luò)2.2.1 交換網(wǎng)絡(luò)基本概念交換網(wǎng)絡(luò)基本概念2.2.2 CLOS網(wǎng)絡(luò)網(wǎng)絡(luò)2.2.3 TST網(wǎng)絡(luò)網(wǎng)絡(luò)2.2.4 DS

2、N網(wǎng)絡(luò)網(wǎng)絡(luò)2.2.5 BANYAN網(wǎng)絡(luò)網(wǎng)絡(luò)2.1 交換單元 交換單元是構(gòu)成交換網(wǎng)絡(luò)的最基本的交換單元是構(gòu)成交換網(wǎng)絡(luò)的最基本的部件，用若干個交換單元按照一定的拓?fù)洳考?，用若干個交換單元按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式就可以構(gòu)成交換網(wǎng)絡(luò)。結(jié)構(gòu)和控制方式就可以構(gòu)成交換網(wǎng)絡(luò)。 2.1.1 2.1.1 交換單元的概念交換單元的概念01M101N1控制端控制端狀態(tài)端狀態(tài)端入入線線出出線線M MN N的交換單元的交換單元u 定義定義構(gòu)成交換網(wǎng)絡(luò)的構(gòu)成交換網(wǎng)絡(luò)的最基本的部件。最基本的部件。u 功能功能在任意的入線和出在任意的入線和出線之間建立連接。線之間建立連接。交換單元的對外特性及示意圖交換單元的對外特性及示意

3、圖-描述內(nèi)部狀態(tài)描述內(nèi)部狀態(tài)完成控制功能完成控制功能1. 1. 交換單元交換單元N10M10入入線線出出線線（a）集中型（集中型（M N）M10N10出出線線入入線線（c）擴展型（擴展型（M N）M10N10入入線線出出線線（b）分配型（分配型（M=N）u 分類分類交換單元交換單元6 有向交換單元：有向交換單元：當(dāng)信息經(jīng)過交換單元時只能從當(dāng)信息經(jīng)過交換單元時只能從入線進(jìn)出線出，具有唯一確定的方向。入線進(jìn)出線出，具有唯一確定的方向。 無向交換單元：無向交換單元：交換單元的每條線即可入也可交換單元的每條線即可入也可出其入線數(shù)必等于出現(xiàn)數(shù)。出其入線數(shù)必等于出現(xiàn)數(shù)。按信息流向分類按信息流向分類 按信息

4、流向分類按信息流向分類交換單元（a）MN有向交換單元（入線進(jìn)出線出）有向交換單元（入線進(jìn)出線出）（b）N無向交換單元（無向交換單元（ M=N ）（c）N無向交換單元無向交換單元入入線線出出線線N100M1N10入入線線出出線線0M1N10入入線線出出線線8 按照交換單元的所有入線與所有出線之間是否按照交換單元的所有入線與所有出線之間是否共享單一的通路，可以把交換單元分為共享單一的通路，可以把交換單元分為時分交時分交換單元換單元與與空分交換單元空分交換單元。圖圖2.4 交換單元分類交換單元分類3：時分與空分：時分與空分交換單元信息交換的方式交換單元信息交換的方式在信息交換時，根在信息交換時，根據(jù)

5、信道的復(fù)用方式，據(jù)信道的復(fù)用方式，可分為：可分為：203021001223入入線線出出線線20130123（b）統(tǒng)計時分復(fù)用信號的交換統(tǒng)計時分復(fù)用信號的交換0123123入入線線出出線線（a）同步時分復(fù)用信號的交換同步時分復(fù)用信號的交換0 復(fù)用信號的交換示意圖復(fù)用信號的交換示意圖 只攜帶只攜帶用戶信息用戶信息不指定不指定出線地址出線地址不僅攜帶不僅攜帶用戶信息用戶信息 還有還有出線地址出線地址同步時分復(fù)用同步時分復(fù)用信號的交換信號的交換統(tǒng)計時分復(fù)用統(tǒng)計時分復(fù)用信號的交換信號的交換交換單元的基本功能交換單元的基本功能-建立連接和拆除連接建立連接和拆除連接用連接函數(shù)來描述交換單元的連接特性用連接函

6、數(shù)來描述交換單元的連接特性, , 一個連接函數(shù)對應(yīng)一種連接。一個連接函數(shù)對應(yīng)一種連接。1 1. . 連接與連接函數(shù)連接與連接函數(shù) （1 1）連接）連接 u 交換單元的入線和出線的連接交換單元的入線和出線的連接 點到點連接點到點連接一點到一點的連接。一點到一點的連接。 廣播功能廣播功能一點到多點的連接。一點到多點的連接。 連接與連接函數(shù)連接與連接函數(shù)（2 2）連接函數(shù)）連接函數(shù) 交換單元的基本特性是連接特性，它反映交換交換單元的基本特性是連接特性，它反映交換單元入線到出線的連接能力。單元入線到出線的連接能力。 對連接特性有效而正確的描述，就可以反映交對連接特性有效而正確的描述，就可以反映交換單元

7、的特性。換單元的特性。 每一個交換單元都可用一組連接函數(shù)來表示，每一個交換單元都可用一組連接函數(shù)來表示，一個連接函數(shù)對應(yīng)一種連接。一個連接函數(shù)對應(yīng)一種連接。f連接與連接函數(shù)連接與連接函數(shù) 如果用如果用 表示一個交換單元的入線編號，出線表示一個交換單元的入線編號，出線編號就可以用連接函數(shù)編號就可以用連接函數(shù) 來表示，來表示，0 M1，0 N1。 連接函數(shù)表示相互連接的入線編號和出線編號連接函數(shù)表示相互連接的入線編號和出線編號之間的一一對應(yīng)關(guān)系。之間的一一對應(yīng)關(guān)系。 連接函數(shù)實際上也反映了入線編號構(gòu)成的數(shù)組連接函數(shù)實際上也反映了入線編號構(gòu)成的數(shù)組和出線編號構(gòu)成的數(shù)組之間對應(yīng)的排列關(guān)系，因和出線編號

8、構(gòu)成的數(shù)組之間對應(yīng)的排列關(guān)系，因此，連接函數(shù)也稱為置換函數(shù)或排列函數(shù)。此，連接函數(shù)也稱為置換函數(shù)或排列函數(shù)。fx)(xfx)(xf連接與連接函數(shù)連接與連接函數(shù)f 函數(shù)表示形式函數(shù)表示形式 排列表示形式排列表示形式 圖形表示形式圖形表示形式常見的連接函數(shù)表示形式有三種：常見的連接函數(shù)表示形式有三種：2. 連接函數(shù)的表示形式15q 函數(shù)表示形式函數(shù)表示形式 x x表示入線編號（二進(jìn)制表示），表示入線編號（二進(jìn)制表示），f(x)f(x)表表示連接函數(shù)。示連接函數(shù)。q 排列表示形式排列表示形式 即輸入輸出對應(yīng)表示形式即輸入輸出對應(yīng)表示形式 t0，t1，t n-1 r0，r1，r n-1q 圖形表示形式

9、圖形表示形式1. 1. 直線連接（恒等置換）直線連接（恒等置換）對稱交換單元相同編號的入線與出線一一對稱交換單元相同編號的入線與出線一一對應(yīng)連接為直線連接。對應(yīng)連接為直線連接。01210121)(xxxxxxxxInnnn 2.1.3 2.1.3 交換單元常用的連接方式交換單元常用的連接方式 I(x 2 x 1 x 0) = x 2 x 1 x 0 0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7 0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7出出線線號號入入線線號號N=8N=8時的直線連接時的直線連接假設(shè)當(dāng)假設(shè)當(dāng)N=8N=8時時，交換單元常用的連接方式交換單元常

10、用的連接方式 交叉連接是實現(xiàn)二進(jìn)制地址編號中交叉連接是實現(xiàn)二進(jìn)制地址編號中第第0 0位位值位位值不同不同(0(0或或1)1)的入線與出線之間的連接。的入線與出線之間的連接。2. 2. 交叉連接交叉連接( (交叉置換交叉置換) ) 12101210()nnnnE xxx xxxx x交換單元常用的連接方式交換單元常用的連接方式 1 01 0()E xxxx0001010010111110假設(shè)當(dāng)N=8時，1 1，0 0，3 3，2 2，5 5，4 4，7 7，6 6 0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7 1 1，0 0，3 3，2 2，5 5，4 4，7 7，6 6或或出

11、出線線號號入入線線號號N=8N=8時的交叉連接時的交叉連接012012)(xxxxxxE0 01 12 23 34 45 56 67 71 10 03 32 25 54 47 76 6交換單元常用的連接方式交換單元常用的連接方式 均勻洗牌連接均勻洗牌連接3. . 均勻洗牌連接均勻洗牌連接( (均勻洗牌置換均勻洗牌置換) ) 具體實現(xiàn)方法是：將入線二進(jìn)制地址編號循環(huán)左移具體實現(xiàn)方法是：將入線二進(jìn)制地址編號循環(huán)左移1 1位作位作為出線地址編號。為出線地址編號。均勻洗牌連接均勻洗牌連接 均勻洗牌連接，將出線一個隔一個地從頭至尾地分成相等均勻洗牌連接，將出線一個隔一個地從頭至尾地分成相等的兩部分，將這

12、兩部分首尾相接，使之達(dá)到理想的一張隔一的兩部分，將這兩部分首尾相接，使之達(dá)到理想的一張隔一張的均勻洗牌效果。然后，按序?qū)⒊鼍€依次與入線連接。張的均勻洗牌效果。然后，按序?qū)⒊鼍€依次與入線連接。 (x 2 x 1 x 0) = x 1 x 0 x 2 當(dāng)當(dāng)N=8N=8時，時， 假設(shè)當(dāng)N=8時， 0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7 0 0，2 2，4 4，6 6，1 1，3 3，5 5，7 7出出線線號號入入線線號號N=8N=8時的均勻洗牌連接時的均勻洗牌連接均勻洗牌連接均勻洗牌連接子洗牌連接子洗牌連接-將全部入線及相應(yīng)出線分成若干將全部入線及相應(yīng)出線分成若干個子部分，每

13、一個子部分獨立完成均勻洗牌連接個子部分，每一個子部分獨立完成均勻洗牌連接。連接函數(shù)為連接函數(shù)為: : 子洗牌連接子洗牌連接假設(shè)當(dāng)N=8時， (x 2 x 1 x 0) = x 2 x 0 x 1 均勻均勻子子洗牌洗牌均勻均勻子子洗牌洗牌0,1,2,3,4,5,6,70,1,2,3,4,5,6,70,2,1,3,4,6,5,70,2,1,3,4,6,5,7出出線線號號入入線線號號N=8N=8時的均勻洗牌連接時的均勻洗牌連接逆逆均勻洗牌連接均勻洗牌連接 逆均勻洗牌連接逆均勻洗牌連接 逆勻洗牌連接是均勻洗牌連接的逆函數(shù)，兩者的逆勻洗牌連接是均勻洗牌連接的逆函數(shù)，兩者的入線和出線正好互換了位置入線和出

14、線正好互換了位置, ,即逆洗牌是將入線二即逆洗牌是將入線二進(jìn)制地址編號循環(huán)右移進(jìn)制地址編號循環(huán)右移1 1位作為出線地址編號。位作為出線地址編號。逆逆均勻洗牌連接均勻洗牌連接假設(shè)當(dāng)N=8時， (x 2 x 1 x 0) = x 0 x 2 x 1出出線線號號入入線線號號N=8N=8時的逆均勻洗牌連接時的逆均勻洗牌連接 蝶式連接變換實現(xiàn)時，其圖形形狀如蝴蝶，這種蝶式連接變換實現(xiàn)時，其圖形形狀如蝴蝶，這種連接是將入線二進(jìn)制地址編號的連接是將入線二進(jìn)制地址編號的互互換位置作為出線地址編號。換位置作為出線地址編號。4.4.蝶式連接蝶式連接( (蝶式置換蝶式置換) ) 蝶式連接蝶式連接( (蝶式置換蝶式置

15、換) ) 蝶式連接蝶式連接( (蝶式置換蝶式置換) ) (x 2 x 1 x 0) = x0 x 1x 2出出線線號號入入線線號號N=8N=8時的蝶式連接時的蝶式連接蝶式連接蝶式連接( (蝶式置換蝶式置換) ) 子蝶式連接子蝶式連接 子蝶式連接子蝶式連接-將全部入線及相應(yīng)出線分成將全部入線及相應(yīng)出線分成若干個子部分，每一個子部分獨立完成蝶式連接若干個子部分，每一個子部分獨立完成蝶式連接。子子蝶式連接蝶式連接 N=8N=8時的子蝶式連接時的子蝶式連接 (x 2 x 1 x 0) = x 2x0 x 1出出線線號號入入線線號號 N=8 N=8時的子蝶式連接時的子蝶式連接子子蝶式連接蝶式連接1.1.

16、接口接口 交換單元所有入線可以同時送入的總的信息量。交換單元所有入線可以同時送入的總的信息量。2.2.容量容量 用交換單元的性能指標(biāo)來用交換單元的性能指標(biāo)來描述其外部特性描述其外部特性可交換的信號形式可交換的信號形式（模擬信號模擬信號/ /數(shù)字信號數(shù)字信號） 、信號流向、信號流向。2.1.4 2.1.4 交換單元性能指標(biāo)交換單元性能指標(biāo)用交換單元的性能指標(biāo)來用交換單元的性能指標(biāo)來描述其外部特性描述其外部特性3.3.功能功能4.4.質(zhì)量質(zhì)量入線和出線之間建立連接并傳送信息。入線和出線之間建立連接并傳送信息。 交換速度、交換延時和其他損傷交換速度、交換延時和其他損傷。2.1.4 2.1.4 交換單

17、元性能指標(biāo)交換單元性能指標(biāo) 交換單元是如何完成交換的交換單元是如何完成交換的? ? 交換單元內(nèi)部是什么交換單元內(nèi)部是什么? ? 結(jié)構(gòu)如何結(jié)構(gòu)如何? ? 有何特性有何特性? ?交換單元的內(nèi)部交換單元的內(nèi)部) )( (空分交換單元空分交換單元前面討論了外部特性及其數(shù)學(xué)描述。前面討論了外部特性及其數(shù)學(xué)描述。我們將目光移到交換單元的內(nèi)部。我們將目光移到交換單元的內(nèi)部。最基本的的交換單元是開關(guān)陣列最基本的的交換單元是開關(guān)陣列即用各種各樣的開關(guān)構(gòu)成的交換單元即用各種各樣的開關(guān)構(gòu)成的交換單元。工作原理：控制開關(guān)的閉合就能建立任意入線和任意出線之間的連接。性能：取決于開關(guān)類型信號：模擬/數(shù)字/光波入線出線空分

18、交換單元 空分交換單元的特點（1）控制簡單，時延均勻。（2）交叉點數(shù)是入線數(shù)和出線數(shù)的乘積。適合構(gòu)成較小的交換單元。（3）容易實現(xiàn)多播和廣播。入線出線 開 關(guān) 陣 列（4）交換單元的性能依賴于所使用的開關(guān)。（5）開關(guān)具有控制端和狀態(tài)端。 開 關(guān) 陣 列繼電器：其構(gòu)成的交換單元是無向的，可交換模擬和數(shù)字信息，干擾和噪聲大、動作慢（ms級）、體積大（cm級）。實際的開關(guān)陣列 開 關(guān) 陣 列模擬電子開關(guān)：一般利用半導(dǎo)體材料制成。只能單向傳送，且衰耗和時延較大。實際的開關(guān)陣列數(shù)字電子開關(guān)：由簡單的邏輯門構(gòu)成，用于數(shù)字信號的交換，開關(guān)動作極快且無信號損失?？?間 接 線 器空間交換單元也稱為空間接線器（

19、Space Switch），簡稱S單元或S接線器，用來實現(xiàn)多個輸入復(fù)用線與多個輸出復(fù)用線之間的空間交換，而不改變其時隙位置。 完成不同時分復(fù)用線之間同一時隙的信息交換。交叉矩陣：由按時隙通斷的開關(guān)組成。交叉矩陣：由按時隙通斷的開關(guān)組成?？刂拼鎯ζ鳎簩徊娼狱c矩陣開關(guān)進(jìn)行控制?？刂拼鎯ζ鳎簩徊娼狱c矩陣開關(guān)進(jìn)行控制?；窘M成輸入線1輸入線2輸入線3輸入線n輸出線1輸出線n空 間 接 線 器工作方式空間交換單元的交叉點按時隙高速接通與斷開。如空間交換單元的交叉點按時隙高速接通與斷開。如一幀中有不同時隙的信碼要交換到同一條輸出線上，則一幀中有不同時隙的信碼要交換到同一條輸出線上，則在在CM控制下的交

20、叉接點在一幀內(nèi)就要開、關(guān)若干次?？刂葡碌慕徊娼狱c在一幀內(nèi)就要開、關(guān)若干次。即即:空間交換單元的交叉點是以時分方式工作的。空間交換單元的交叉點是以時分方式工作的。所以又所以又叫叫“時分復(fù)用的空間接線器時分復(fù)用的空間接線器”。空 間 接 線 器空 間 接 線 器S接線器的構(gòu)成：交叉點矩陣、控制存儲器交叉點矩陣：開關(guān)陣列控制存儲器（CM-Control Memory）：q S接線器所含CM數(shù)量等于入（出）線數(shù)q 每個CM所含有的存儲單元個數(shù)等于入（出）線上的復(fù)用時隙數(shù)q 每個存儲單元為n位bit,且滿足N2n,其中N為入（出）線上時隙數(shù) 空間交換單元的基本結(jié)構(gòu)輸入控制方式空 間 接 線 器1 2 3

21、1 2 31 2 3TS12 TS8TS12 TS808123TS8TS8輸入控制方式2TS12TS1231空間交換單元的控制方式CM輸入控制方式工作原理TS1012141531TS1412TS14TS11201100011 1 221CM 輸出控制方式輸出控制方式 1 2 31 2 3 3 2 1TS8TS12 TS808123TS8TS8輸出控制方式3TS12TS1221127TS12CM輸出控制方式工作原理TS1012141531TS14 1 2TS14TS11210010011 2 112MMS接線器01M-101M-1kkkkkk空 間 接 線 器 共享存儲器型交換單元 12 13N

22、存儲器2N輸入信號輸出信號2 13N 工作方式：輸入緩沖、輸出緩沖。 適用范圍：電路交換、分組交換。2.1.6 時分復(fù)用交換單元 話音存儲器話音存儲器（SMSM）: :暫存話音編碼信息。暫存話音編碼信息。SMSM單元單元數(shù)由輸入復(fù)用線上每幀的時隙數(shù)決定。數(shù)由輸入復(fù)用線上每幀的時隙數(shù)決定。 控制存儲器控制存儲器（CMCM）：存儲輸入或輸出話音信息）：存儲輸入或輸出話音信息的時隙地址。的時隙地址。CMCM單元數(shù)與單元數(shù)與SMSM單元數(shù)相同，每個存單元數(shù)相同，每個存儲單元存放儲單元存放SMSM的地址碼。的地址碼。完成同一條時分復(fù)用線上時隙之間的信息交換?；窘M成：時 間 接 線 器（1 1）順序?qū)懭?/p>

23、，控制讀出）順序?qū)懭?，控制讀出（2 2）控制寫入，順序讀出）控制寫入，順序讀出工作方式時 間 接 線 器時 間 接 線 器032731273032731RWWR時 間 接 線 器時 間 接 線 器0331273032731RWWR2727時 間 接 線 器Tkk時 間 接 線 器對于時間交換單元，不論采用哪種工作方式，每個輸入時隙的信息都將占用一個存儲單元，每個存儲單元都占有一定的空間位置，從這點看，時間交換單元雖是時隙交換，但卻是以“空間”位置的分配來實現(xiàn)交換的，所以，時間交換單元實質(zhì)上是按“空分”方式工作的。時 間 接 線 器 總線型交換單元總線入線控制入線控制入線控制總線控制邏輯12N線

24、入出線控制出線控制出線控制12N線出 工作原理 輸入緩沖，總線控制，輸出檢測，輸出緩沖。信息吞吐量 取決于總線帶寬，入線與出線的控制速率。 適用范圍：電路交換、分組交換。2.1.7 開 關(guān) 陣 列 數(shù)字交換單元2.1.7 開 關(guān) 陣 列.數(shù)字交換單元的工作原理STS18STS12端口RAM話路RAM數(shù)據(jù)RAM00031D3131P C12121818SRX4TX7典型的時分復(fù)用交換單元典型的時分復(fù)用交換單元 共享存儲器型交換單元共享存儲器型交換單元 總線型（共享媒體型）交換單元總線型（共享媒體型）交換單元時分復(fù)用交換單元實例時分復(fù)用交換單元實例 時間時間(T)接線器接線器(共享存儲器型共享存儲

25、器型)數(shù)字交換單元（數(shù)字交換單元（DSE）(總線型（共享媒體型）交換單總線型（共享媒體型）交換單元元) 空間接線器 時間接線器 數(shù)字交換單元交換單元小結(jié)交換單元小結(jié)交換單元及其數(shù)學(xué)描述交換單元及其數(shù)學(xué)描述開關(guān)陣列開關(guān)陣列時分復(fù)用交換單元時分復(fù)用交換單元2.3 交換網(wǎng)絡(luò)2.3 交換網(wǎng)絡(luò)2.2 交換網(wǎng)絡(luò)2.2.1 交換網(wǎng)絡(luò)的基本概念交換網(wǎng)絡(luò)的基本概念2.2.2 CLOS網(wǎng)絡(luò)網(wǎng)絡(luò)（ CLOS是人名 ）2.2.3 TST網(wǎng)絡(luò)網(wǎng)絡(luò)2.2.4 DSN網(wǎng)絡(luò)網(wǎng)絡(luò)2.2.5 BANYAN網(wǎng)絡(luò)網(wǎng)絡(luò)2.2.6 BENES網(wǎng)絡(luò)網(wǎng)絡(luò)交換網(wǎng)絡(luò)的定義：交換網(wǎng)絡(luò)的定義：將交換單元按一定的拓?fù)浣Y(jié)構(gòu)連接起來將交換單元按一定的拓?fù)?/p>

26、結(jié)構(gòu)連接起來交換網(wǎng)絡(luò)三要素：交換網(wǎng)絡(luò)三要素：交換單元，拓?fù)浣Y(jié)構(gòu)，控制方式。交換單元，拓?fù)浣Y(jié)構(gòu)，控制方式。交換交換單元單元交換交換單元單元交換交換單元單元交換交換單元單元控制單元控制單元交換網(wǎng)絡(luò)交換網(wǎng)絡(luò)入入線線出出線線2.2.1 交換網(wǎng)絡(luò)的基本概念交換網(wǎng)絡(luò)的基本概念圖2.39 交叉連接單元的工作狀態(tài)是具有兩條入線和兩條出線的電子開關(guān)元件。這種電子開關(guān)具有五種狀態(tài)。 交換網(wǎng)絡(luò)1. 單級交換網(wǎng)絡(luò)與多級交換網(wǎng)絡(luò)單級交換網(wǎng)絡(luò)與多級交換網(wǎng)絡(luò)圖2.29 單級交換網(wǎng)絡(luò) 單級交換網(wǎng)絡(luò)單級交換網(wǎng)絡(luò)交換交換單元單元入入線線出出線線(b) 同級多個交換網(wǎng)絡(luò)(a)單個交換網(wǎng)絡(luò)交換網(wǎng)絡(luò) 多級交換網(wǎng)絡(luò)多級交換網(wǎng)絡(luò)（入線到出

27、線的連接，經(jīng)過多個交換單元)第第1 1級是級是由由m m個個n nn n的的交換單交換單元構(gòu)成元構(gòu)成第第2 2級級是由是由n n個個m mm m的交換的交換單元構(gòu)單元構(gòu)成成為了防止網(wǎng)絡(luò)內(nèi)部阻塞2. 多級交換網(wǎng)絡(luò)與單級交換網(wǎng)重要的不同多級交換網(wǎng)絡(luò)與單級交換網(wǎng)重要的不同 多級交換網(wǎng)絡(luò)交換容量大，但存在內(nèi)部阻塞。 單級網(wǎng)絡(luò)不存在內(nèi)部阻塞，但交換容量受限。 交換網(wǎng)絡(luò)70交換網(wǎng)絡(luò)的阻塞是指從交換網(wǎng)絡(luò)不同輸入端來交換網(wǎng)絡(luò)的阻塞是指從交換網(wǎng)絡(luò)不同輸入端來的信息在交換網(wǎng)絡(luò)中交換時發(fā)生了對同一公共資源的信息在交換網(wǎng)絡(luò)中交換時發(fā)生了對同一公共資源爭搶的情況，這時在競爭資源中失敗的信息就會被爭搶的情況，這時在競爭資

28、源中失敗的信息就會被阻塞。阻塞。有兩種情況：有兩種情況：一種為內(nèi)部競爭，一種為出線競一種為內(nèi)部競爭，一種為出線競爭。爭。71n 內(nèi)部競爭：內(nèi)部競爭：同時要交換的兩路信息同搶交換單元內(nèi)同時要交換的兩路信息同搶交換單元內(nèi)部的通路資源；部的通路資源；n 出線競爭：出線競爭：不同入端來的信息同時爭搶交換網(wǎng)絡(luò)同不同入端來的信息同時爭搶交換網(wǎng)絡(luò)同一個輸出端口而發(fā)生的競爭。一個輸出端口而發(fā)生的競爭。n 內(nèi)部阻塞：內(nèi)部阻塞：因為內(nèi)部競爭而發(fā)生的阻塞稱為內(nèi)部阻因為內(nèi)部競爭而發(fā)生的阻塞稱為內(nèi)部阻塞塞n 有阻塞交換網(wǎng)絡(luò)有阻塞交換網(wǎng)絡(luò)：存在內(nèi)部阻塞的交換網(wǎng)絡(luò)。存在內(nèi)部阻塞的交換網(wǎng)絡(luò)。n 無阻塞交換網(wǎng)絡(luò)無阻塞交換網(wǎng)絡(luò)：

29、不存在內(nèi)部阻塞的交換網(wǎng)絡(luò)。不存在內(nèi)部阻塞的交換網(wǎng)絡(luò)。72p內(nèi)部阻塞：內(nèi)部阻塞：若出、入線空閑，但因交換若出、入線空閑，但因交換網(wǎng)絡(luò)級間鏈路被占用而無法網(wǎng)絡(luò)級間鏈路被占用而無法接通的現(xiàn)象，稱為多級交換接通的現(xiàn)象，稱為多級交換網(wǎng)絡(luò)的網(wǎng)絡(luò)的內(nèi)部阻塞。內(nèi)部阻塞。出線競爭出線競爭內(nèi)部競爭內(nèi)部競爭內(nèi)部競爭的有無與交換結(jié)構(gòu)的內(nèi)部拓?fù)浣Y(jié)構(gòu)、工作速內(nèi)部競爭的有無與交換結(jié)構(gòu)的內(nèi)部拓?fù)浣Y(jié)構(gòu)、工作速度等因素有關(guān)。度等因素有關(guān)。內(nèi)部競爭與出線競爭內(nèi)部競爭與出線競爭0nxn10n-1m-10mxm1n-110n-110n-110m-110m-110m-11第第1級級第第2級級多級網(wǎng)絡(luò)多級網(wǎng)絡(luò)( nm x nm )內(nèi)部阻塞

30、示意圖內(nèi)部阻塞示意圖n-1m-1 交換網(wǎng)絡(luò)交換網(wǎng)絡(luò)無阻塞無阻塞的概念的概念 嚴(yán)格無阻塞交換網(wǎng)絡(luò) 可重排無阻塞交換網(wǎng)絡(luò) 廣義無阻塞交換網(wǎng)絡(luò)無阻塞交無阻塞交 換網(wǎng)絡(luò)換網(wǎng)絡(luò) 嚴(yán)格無阻塞網(wǎng)絡(luò)只要連接的起點、終點是空閑的，不管網(wǎng)絡(luò)處于何種狀態(tài)，任何時刻都可以在交換網(wǎng)絡(luò)中建立連接。 可重排無阻塞網(wǎng)絡(luò) 只要連接的起點、終點是空閑的，不管網(wǎng)絡(luò)處于何種狀態(tài)，任何時刻都可以在一個交換網(wǎng)絡(luò)中直接或?qū)σ延械倪B接重選路由來建立一個連接。 廣義無阻塞網(wǎng)絡(luò) 一個給定的網(wǎng)絡(luò)存在阻塞的可能，但有可能有一種選路方法，可避免阻塞。目前很少見不討論。 交換網(wǎng)絡(luò)交換網(wǎng)絡(luò)無阻塞無阻塞的概念的概念 保證網(wǎng)絡(luò)上終端都能兩兩互通保證網(wǎng)絡(luò)上終端

31、都能兩兩互通 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)安排要合理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)安排要合理 - -防止網(wǎng)絡(luò)內(nèi)部阻塞防止網(wǎng)絡(luò)內(nèi)部阻塞 最后是網(wǎng)絡(luò)代價最后是網(wǎng)絡(luò)代價構(gòu)建大型交換網(wǎng)絡(luò)考慮的問題q 單級交換網(wǎng)絡(luò)是不存在內(nèi)部阻塞的，為什么實際使單級交換網(wǎng)絡(luò)是不存在內(nèi)部阻塞的，為什么實際使用的大多是多級交換網(wǎng)絡(luò)用的大多是多級交換網(wǎng)絡(luò)?q 因為交換網(wǎng)絡(luò)中交叉點越多，成本越高。一般在設(shè)因為交換網(wǎng)絡(luò)中交叉點越多，成本越高。一般在設(shè)計交換網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)時，盡量最小化交叉點數(shù)。計交換網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)時，盡量最小化交叉點數(shù)。q 容量相同的容量相同的多級多級交換網(wǎng)絡(luò)與交換網(wǎng)絡(luò)與單級單級交換網(wǎng)絡(luò)比較，交換網(wǎng)絡(luò)比較，交交叉點數(shù)大大減少。叉點數(shù)大大減少。交換

32、網(wǎng)絡(luò)交換網(wǎng)絡(luò) 交換網(wǎng)絡(luò)單級交換網(wǎng)絡(luò)單級交換網(wǎng)絡(luò) 交換單元入線出線單級網(wǎng)絡(luò)交叉接點數(shù)：單級網(wǎng)絡(luò)交叉接點數(shù)：1616 = 256。兩級網(wǎng)絡(luò)交叉接點數(shù)：兩級網(wǎng)絡(luò)交叉接點數(shù)：448=128。16161142143144141142143144141414141414141414入線出線1616例如：圖例如：圖2.27中的中的nm nm兩級交換網(wǎng)絡(luò)兩級交換網(wǎng)絡(luò)n n m m m n假設(shè)假設(shè)n=m=8則則n n m m m n = 如果用單級交換單元組成交換網(wǎng)絡(luò)n m n m= 單級交換單元組成交換網(wǎng)絡(luò)時輸入線數(shù)目輸出線數(shù)目交換單元數(shù)目* 構(gòu)建網(wǎng)絡(luò)交叉點數(shù)越少越好交換網(wǎng)絡(luò)的交叉點數(shù)目交換網(wǎng)絡(luò)的交叉點數(shù)目2

33、.2.2 CLOS網(wǎng)絡(luò)網(wǎng)絡(luò)CLOS就是一類交叉點數(shù)少的就是一類交叉點數(shù)少的NN的無阻塞的多級交換網(wǎng)絡(luò)的無阻塞的多級交換網(wǎng)絡(luò)CLOS網(wǎng)絡(luò)網(wǎng)絡(luò) CLOS是，按照某種連接方式連接起來，形成多級交換網(wǎng)絡(luò)。交叉點數(shù)隨入、出線數(shù)增加而增長較慢的。CLOS網(wǎng)絡(luò)網(wǎng)絡(luò)每一個交換單元都與下一級的各個交換單元有連接且僅有一條連，因此任每一個交換單元都與下一級的各個交換單元有連接且僅有一條連，因此任意一條入線與出線之間均存在一條通過中間級交換單元的路徑。意一條入線與出線之間均存在一條通過中間級交換單元的路徑。m、n、r是整數(shù)，決定了交換單元的容量，稱為網(wǎng)絡(luò)參數(shù)，并記為是整數(shù)，決定了交換單元的容量，稱為網(wǎng)絡(luò)參數(shù)，并記為

34、C(m，n，r)。 兩邊兩邊各有各有r個對個對稱的稱的mn矩形矩形交換交換單元單元中間是中間是m個個rr的方形交換單元的方形交換單元（1）組成組成CLOS網(wǎng)絡(luò)網(wǎng)絡(luò)（2） 三級三級對稱對稱CLOS網(wǎng)絡(luò)網(wǎng)絡(luò)C (m , n, r) 第一級每個交換單元出線數(shù)第三級每個交換單元入線數(shù)第二級交換單元數(shù)第一級每個交換單元入線數(shù)第三級每個交換單元出線數(shù)第一級和第三級交換單元數(shù)n1 = n2 = n r1 = r2 = r 嚴(yán)格無阻塞條件：嚴(yán)格無阻塞條件： m 2n1 可重排無阻塞條件：可重排無阻塞條件： m n 三級三級非對稱非對稱CLOS網(wǎng)絡(luò)網(wǎng)絡(luò)C (m , n1 , r1 , n2 , r2)： 嚴(yán)格無

35、阻塞條件：嚴(yán)格無阻塞條件： m n1 + n2 1 可重排無阻塞條件：可重排無阻塞條件： m max(n1 , n2 ) 三級三級CLOSCLOS網(wǎng)絡(luò)嚴(yán)格無阻塞條件網(wǎng)絡(luò)嚴(yán)格無阻塞條件m為CLOS網(wǎng)絡(luò)第 級所需要交換單元的個數(shù)，圖2.34 CLOS網(wǎng)絡(luò)的無阻塞條件假如我們要確立一條從的信息交換通路。最不利的情況是：第一級與 相連的交換單元中除去 之外所有剩余的均有信息要交換，那么第一級與 相連的交換單元中均處于忙狀態(tài)，并且所有的G G 三級三級CLOSCLOS網(wǎng)絡(luò)嚴(yán)格無阻塞條件的網(wǎng)絡(luò)嚴(yán)格無阻塞條件的分析分析 最后一級與 相連的交換單元除去 以外所有的條輸出線也均有信息要交換出來，個交換單元，而且

36、這些交換單元都要有一條出線連接到與 相連的交換單元上。 G G 三級三級CLOSCLOS網(wǎng)絡(luò)嚴(yán)格無阻塞條件的網(wǎng)絡(luò)嚴(yán)格無阻塞條件的分析分析第一級 第二級 第三級圖2.25 嚴(yán)格無阻塞的三級CLOS網(wǎng)絡(luò)那么在最壞情況下，總共需要個可供選擇的第2級交換單元，這時候為了確保鏈路無阻塞，完成a到b的信息交換，至少還應(yīng)該存在一條空閑鏈路，即中間級交換單元要有因此我們得出三級對三級對稱稱CLOSCLOS網(wǎng)絡(luò)網(wǎng)絡(luò)嚴(yán)格無阻塞條件： m 2n1 G G 三級三級CLOSCLOS網(wǎng)絡(luò)嚴(yán)格無阻塞條件的網(wǎng)絡(luò)嚴(yán)格無阻塞條件的分析分析第一級 第二級 第三級圖2.25 嚴(yán)格無阻塞的三級CLOS網(wǎng)絡(luò)891 13 34 42 2

37、1 13 34 42 2C1C1C2C21，2，3，44，2，1，3 可重排無阻塞網(wǎng)絡(luò)可重排無阻塞網(wǎng)絡(luò)1 13 34 42 21 13 34 42 2C1C1cc2cc2但滿足可重排無阻塞條件： m n2.2.3 TST 網(wǎng)絡(luò)網(wǎng)絡(luò) 第第1 1級級T T接線器：負(fù)責(zé)輸入母線的時隙交換。接線器：負(fù)責(zé)輸入母線的時隙交換。 第第2 2級級S S接線器：負(fù)責(zé)母線之間的空間交換交換。接線器：負(fù)責(zé)母線之間的空間交換交換。 第第3 3級級T T接線器：負(fù)責(zé)輸出母線的時隙交換。接線器：負(fù)責(zé)輸出母線的時隙交換。1. TST網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu) 由由T T接線器和接線器和 接線器連接接線器連接 而成的三級交換網(wǎng)絡(luò)。而成

38、的三級交換網(wǎng)絡(luò)。TSTTST網(wǎng)絡(luò)定義：網(wǎng)絡(luò)定義：TSTTST網(wǎng)絡(luò)模型是構(gòu)建大容量數(shù)字交換網(wǎng)絡(luò)的三級交換網(wǎng)絡(luò)網(wǎng)絡(luò)模型是構(gòu)建大容量數(shù)字交換網(wǎng)絡(luò)的三級交換網(wǎng)絡(luò)TST 網(wǎng)絡(luò)網(wǎng)絡(luò)TSTTST網(wǎng)絡(luò)的特點：網(wǎng)絡(luò)的特點： 每一條每一條PCMPCM線路連接到一個線路連接到一個T T接線器，有多少條接線器，有多少條輸入或輸出輸入或輸出PCMPCM線路，就有多少個線路，就有多少個T T接線器；接線器； S S級的出、入線數(shù)決定于兩側(cè)級的出、入線數(shù)決定于兩側(cè)T T接線器的數(shù)量，即接線器的數(shù)量，即等于輸入輸出線數(shù)。等于輸入輸出線數(shù)。T T接線器，接線器，S S接線器。接線器。兩側(cè)為兩側(cè)為T T接線器，中間為接線器，中間

39、為S S接線器，接線器，S S級級的出入線數(shù)決定于兩側(cè)的出入線數(shù)決定于兩側(cè)T T接線器的數(shù)量。接線器的數(shù)量。S S接線器接線器SMASMASMBSMB1 1輸入控制輸入控制輸入控制輸入控制輸出控制輸出控制2 2輸出控制輸出控制輸入控制輸入控制3 3輸出控制輸出控制輸入控制輸入控制輸出控制輸出控制4 4輸出控制輸出控制輸入控制輸入控制TST 網(wǎng)絡(luò)網(wǎng)絡(luò)TST交換網(wǎng)的組成1210.10 101210.TTS 如T=512 TS， TST網(wǎng)絡(luò)可實現(xiàn)512時隙之間的交換。TST 網(wǎng)絡(luò)網(wǎng)絡(luò) T-S-T交換網(wǎng)工作原理交換網(wǎng)工作原理 工作方式：兩側(cè)時間接線器工作方式必須相反。工作方式：兩側(cè)時間接線器工作方式必

40、須相反。 中間時隙的確定：反相法。中間時隙的確定：反相法。 如選定一個方向的時隙為如選定一個方向的時隙為X， 則另一個方向中間時隙為則另一個方向中間時隙為 +n/2。 雙向通路的建立雙向通路的建立 主叫主叫被叫：正向通路被叫：正向通路 被叫被叫主叫：反向通路主叫：反向通路T-S-T交換網(wǎng)工作原理 輸入線輸入線0、TS2的的A用戶用戶 輸出線輸出線2、TS20的用戶的用戶BTST交換過程舉例：正向通路：A B 中間時隙：7反向通路 B A 中間時隙：23AA20AAA20A0012310317317000313170CMC-2SMA-0CMA-0CMA-2CMB-2SMB-2TS20TS7TS2

41、3TS7TS2TSTAB031230SMB-02CMC-02BBB2003131230SMA-2TS202BB2B31231230CMB-0TS2TS230202A B2BBBB2BB200312312303123031023131CMC-0SMA-2CMA-2CMB-2CMB-0SMB-0TS2TS23TS7TS23TS20TSTAB0200CMA-0SMA-0AA2A0012310317TS7TS203170CMC-2AA20A0312070SMB-2TS2022230B ATS70731TS23TS23TS7020CMC-2CMC- 002331012310731020310233103

42、1023310310731TS2TS20TS20TS20222020SMA-0CMA-0CMA-2SMA-2SMB-0CMB-0SMB-2CMB-220TST交換過程示意圖2TTST T接線器，接線器，S S接線器。接線器。兩側(cè)為兩側(cè)為T T接線器，中間為接線器，中間為S S接線器，接線器，S S級的出入線數(shù)決定于兩側(cè)級的出入線數(shù)決定于兩側(cè)T T接線器的數(shù)量。接線器的數(shù)量。控制方式：控制方式：S接線器SMASMB1輸入控制輸入控制輸出控制2輸出控制輸入控制3輸出控制輸入控制輸出控制4輸出控制輸入控制TTS32條雙向時分復(fù)用線每條線上有32個時隙輸入側(cè)：話音存儲器用SMA0到SMA31表示； 控

43、制存儲器用CMA0到CMA31表示。輸出側(cè)：話音存儲器用SMB0到SMB31表示； 控制存儲器用CMB0到CMB3l表示 S接線器為3232矩陣，對應(yīng)連接到兩側(cè)的T接線器，并采用輸出控制方式，控制存儲器有32個，用CMC0到CMC31表示。 031 2. TST網(wǎng)絡(luò)工作原理網(wǎng)絡(luò)工作原理 以實現(xiàn)第以實現(xiàn)第0個個T接線器接線器(PCM0復(fù)用線復(fù)用線)的第的第2話路時隙與第話路時隙與第31個接線器個接線器(PCM31復(fù)用線復(fù)用線)的輸出時隙的輸出時隙31的交換為例，來說明的交換為例，來說明TST網(wǎng)絡(luò)的工作原理網(wǎng)絡(luò)的工作原理 102交換網(wǎng)絡(luò)一般交換網(wǎng)絡(luò)一般建立雙向通路建立雙向通路，為減少選路次數(shù)，簡化

44、控制，為減少選路次數(shù)，簡化控制，可使兩個方向的內(nèi)部時隙具有一定的對應(yīng)關(guān)系，通?？上嗖畎肟墒箖蓚€方向的內(nèi)部時隙具有一定的對應(yīng)關(guān)系，通?？上嗖畎霂?，俗稱幀，俗稱反相法反相法，即：，即：A到到B方向的內(nèi)部時隙數(shù)：方向的內(nèi)部時隙數(shù)：TSa=i，則則B到到A方向的內(nèi)部時隙數(shù)：方向的內(nèi)部時隙數(shù)：TSb= i + N/2 計算時以計算時以N為模，其中為模，其中N為幀的復(fù)用時隙數(shù)為幀的復(fù)用時隙數(shù)例如：例如：N=128， TSa=96，則，則 TSb=96+128/2 =32奇偶法奇偶法：當(dāng)一個方向選用偶數(shù)時隙：當(dāng)一個方向選用偶數(shù)時隙 2j（j0，1，2，N/21）時，另一個方向總是選用奇數(shù)時隙時，另一個方向總

45、是選用奇數(shù)時隙2j+1。關(guān)于TST網(wǎng)絡(luò)必須注意的幾個問題（2 2）一般情況下，）一般情況下，TSTTST網(wǎng)絡(luò)存在內(nèi)部阻塞但概率非網(wǎng)絡(luò)存在內(nèi)部阻塞但概率非常小，約為常小，約為1010-6 -6 。 （3 3）構(gòu)成）構(gòu)成TSTTST網(wǎng)絡(luò)的第網(wǎng)絡(luò)的第1 1級級T T接線器與第接線器與第3 3級級T T接線接線器一般采用不同的控制方式，但無論采用哪一種控器一般采用不同的控制方式，但無論采用哪一種控制方式，除了操作方式不同外，本質(zhì)是一樣的。制方式，除了操作方式不同外，本質(zhì)是一樣的。 T-S(n)-TT-S-T網(wǎng)絡(luò)：網(wǎng)絡(luò)：AXE10，F(xiàn)ETEX-150，E10B， 5ESS等等T-S-S-T網(wǎng)絡(luò)：網(wǎng)絡(luò)：N

46、EAX61T-S-S-S-T網(wǎng)絡(luò)：網(wǎng)絡(luò)：EWSDT-S-S-S-S-T網(wǎng)絡(luò)：網(wǎng)絡(luò)：4ESS (長途長途)S-T(n)-STSTTST網(wǎng)絡(luò)模型是構(gòu)建大容量數(shù)字交換網(wǎng)絡(luò)的三級交換網(wǎng)絡(luò)網(wǎng)絡(luò)模型是構(gòu)建大容量數(shù)字交換網(wǎng)絡(luò)的三級交換網(wǎng)絡(luò)交換機交換機2.2.4 DSN網(wǎng)絡(luò)DSNDSN網(wǎng)絡(luò)定義：網(wǎng)絡(luò)定義：由多個由多個DSEDSE（總線型交換單元，對同步時分復(fù)用總線型交換單元，對同步時分復(fù)用 信號進(jìn)行交換信號進(jìn)行交換, ,具有時隙交換功能）按照一具有時隙交換功能）按照一 定的定的連接方式構(gòu)成的大容量交換網(wǎng)絡(luò)連接方式構(gòu)成的大容量交換網(wǎng)絡(luò)DSNDSN網(wǎng)絡(luò)網(wǎng)絡(luò)特點：單側(cè)折疊式網(wǎng)絡(luò)結(jié)構(gòu)，所有出、入線處單側(cè)折疊式網(wǎng)絡(luò)結(jié)構(gòu)

47、，所有出、入線處于同一側(cè)，每個終端具有唯一地址。于同一側(cè)，每個終端具有唯一地址。DSNDSN網(wǎng)絡(luò)地址：網(wǎng)絡(luò)地址：ABCDABCDABCD終端模塊號終端模塊號 第第1級級DSE號號 第第2級級DSE號號 第第2、3級組號級組號4 bits2 bits3 bits4 bitsABCD4170第3級第4級平面0第2級0100001022007771023777終端模塊第1級平面1平面2平面3平面1平面2平面30123ABCD121212128910111110980370707815150151515151588070770089101121315組15組7 組891011047070150組0組A

48、BCD122410第第1級為入口級級為入口級選面級選面級其余其余3級為選組級級為選組級 首先由主叫所在的終端模塊的處理機產(chǎn)生選擇命令字包含主叫和被叫所在終端模塊的網(wǎng)絡(luò)地址ABCDABCD和ABCDABCD 選擇命令字由主叫模塊所連接的入口級相應(yīng)端口進(jìn)入，經(jīng)中相關(guān)級到達(dá)反射點 從反射點下傳給被叫所在的終端模塊。 選擇命令字每經(jīng)過一個DSE，由DSE按照命令字要求自動建立內(nèi)部通路。從主叫到反射點經(jīng)過的DSE，其內(nèi)部通路為指定選擇出端口。級間連接由連線規(guī)律和網(wǎng)絡(luò)地址決定。DSN網(wǎng)絡(luò)DSN網(wǎng)絡(luò) DSN是一種單側(cè)折疊式網(wǎng)絡(luò) DSN可自選路由 DSN的擴展性好 DSN采用逐級推進(jìn)的選試方式 能承受較大話務(wù)

49、量。DSN網(wǎng)絡(luò)定義：定義：由若干個由若干個2 x 2交換單元組成的多級交換網(wǎng)絡(luò)。交換單元組成的多級交換網(wǎng)絡(luò)。特點：特點：唯一路徑，自選路由，編號數(shù)字置換。唯一路徑，自選路由，編號數(shù)字置換。 優(yōu)點：優(yōu)點：簡單，模塊化，可擴展性好。簡單，模塊化，可擴展性好。缺點：缺點：內(nèi)部阻塞。內(nèi)部阻塞。2.2.5 BANYAN網(wǎng)絡(luò)網(wǎng)絡(luò)BANYAN網(wǎng)絡(luò)是一種網(wǎng)絡(luò)是一種，適用于適用于，即根據(jù)信號中攜帶的，即根據(jù)信號中攜帶的出線地址（唯一路徑）信息，自選路由，是進(jìn)（唯一路徑）信息，自選路由，是進(jìn)行行交換的好方法，適用于交換的好方法，適用于。BANYAN網(wǎng)絡(luò)的結(jié)構(gòu)網(wǎng)絡(luò)的結(jié)構(gòu)（1） 22交換單元（電子元器件） BANYA

50、N網(wǎng)絡(luò)的結(jié)構(gòu)網(wǎng)絡(luò)的結(jié)構(gòu)01232310第第2級級第第1級級唯一唯一路徑路徑0 1 2 30 1 2 30 2 1 30 2 1 3均勻洗牌連接均勻洗牌連接（2） 4個22交換單元構(gòu)成一個 44二級交換網(wǎng)絡(luò)4 44 4 BANYANBANYAN交換網(wǎng)絡(luò)交換網(wǎng)絡(luò)（3） 12個22交換單元構(gòu)成8 8三級BANYAN網(wǎng)絡(luò) （2個44的網(wǎng)絡(luò)再加上4個22交換單元構(gòu)成88的交換網(wǎng)絡(luò)）觀察圖我們可以把前面的8個22交換單元看成是兩個44的二級交換網(wǎng)絡(luò)，后面再加上一級4個22交換單元，構(gòu)成88的三級交換網(wǎng)絡(luò)。 這種將多個22交換單元分成若干級，并按照一定的級間連接方式構(gòu)成的多級交換網(wǎng)絡(luò)，就被稱為BANYAN網(wǎng)

51、絡(luò)。 蝶式連接子洗牌45230167452301670123456776543210第第1級級第第2級級第第3級級8 8三級三級BANYAN網(wǎng)絡(luò)網(wǎng)絡(luò)子洗牌子洗牌蝶式連接蝶式連接76543210第第1級級第第2級級第第3級級76543210蝶式連接蝶式連接子洗牌子洗牌子網(wǎng)子網(wǎng) 參照前面講述的44和88BANYAN網(wǎng)絡(luò)的實例，我們發(fā)現(xiàn)BANYAN網(wǎng)絡(luò)的結(jié)構(gòu)是很規(guī)則的，利用遞歸的方法可用較小的BANYAN網(wǎng)絡(luò)構(gòu)成較大的BANYAN網(wǎng)絡(luò)。 假設(shè)已有的BANYAN網(wǎng)絡(luò)，需構(gòu)成的BANYAN網(wǎng)絡(luò)，則可用 組，再加上一組交換單元構(gòu)成。 第一組的N N的N條出線分別與N個2 2交換單元的某一入線相連，第二組的

52、N N的N條出線分別與N個2 2交換單元的另一入線相連。步驟一：需要2個8 8的BANYAN網(wǎng)。 (16 162N 2NN8)步驟二：需要8個2 2的交換單元。步驟三：確定各級連接關(guān)系。第一個8*8的banyan網(wǎng)絡(luò)的8條輸出分別與這8個2*2交換單元的0號入線連接，而另一個8*8的banyan網(wǎng)絡(luò)的8條輸出分別與這8個2*2交換單元的1號入線連接舉例1：構(gòu)造的BANYAN網(wǎng)絡(luò)01012345678911109876542312131415151413121110161616 16 BANYAN BANYAN 交換網(wǎng)絡(luò)的構(gòu)成交換網(wǎng)絡(luò)的構(gòu)成0123456789101112131415012345

53、678910111213141516 16BANYAN交換網(wǎng)絡(luò)的構(gòu)成子網(wǎng)子網(wǎng)01234567891011121314150123456789101112131415用2 2交換單元構(gòu)成BANYAN網(wǎng)絡(luò)的具體形式可以有多種，如圖所示。 BANYAN網(wǎng)絡(luò)的構(gòu)成非常規(guī)則，由其結(jié)構(gòu)可以引出一些重要的特點。 兩個兩個88的的BANYAN網(wǎng)絡(luò)網(wǎng)絡(luò)擴展成擴展成1616的的BANYAN網(wǎng)絡(luò)網(wǎng)絡(luò)圖2.41 BANYAN網(wǎng)絡(luò)的擴展BANYAN網(wǎng)絡(luò)的任一入端到任一網(wǎng)絡(luò)的任一入端到任一端之間，具有端之間，具有1條且僅有一條通路。條且僅有一條通路。自選路由：不用外加控制命令，根據(jù)給定的出線地址，自選路由：不用外加控制命

54、令，根據(jù)給定的出線地址，對應(yīng)于出線地址的二進(jìn)制碼的選路標(biāo)簽來自動選路。對應(yīng)于出線地址的二進(jìn)制碼的選路標(biāo)簽來自動選路。 從網(wǎng)絡(luò)的任一輸入端口引出的一組通路形成了2分支樹，級數(shù)越多，分支越多，級數(shù)入線數(shù)，即。01234567012(010)3(011)4(100)5(101)678 x 8的3級BANYAN網(wǎng)絡(luò)10110(011)(010)(100)(101)信息的選路標(biāo)簽分別是信息的選路標(biāo)簽分別是 011，101，010，100對于統(tǒng)計復(fù)用信號，每個信元均攜帶有控制信息，包括路由對于統(tǒng)計復(fù)用信號，每個信元均攜帶有控制信息，包括路由信息，即出線地址，使用信息，即出線地址，使用BANYANBANYA

55、N網(wǎng)絡(luò)可以很方便的進(jìn)行交換。網(wǎng)絡(luò)可以很方便的進(jìn)行交換。 BANYAN網(wǎng)絡(luò)的入線和出線都編上號碼，并用一組數(shù)字的排列或稱置換來表示它的一種連接方式。 例如，對于44 BANYAN網(wǎng)絡(luò)，給定連接函數(shù)的排列為 ：0 1 2 3 3 0 2 1 1 10 03 32 21 10 03 32 21 10 03 32 21 10 03 32 2圖2.42 編號數(shù)字置換雖然任何一個交換單元及交換網(wǎng)絡(luò)都可以用置換（排列）來表示其連接方式，但對BANYAN網(wǎng)絡(luò)使用置換表示有特別的意義。這是因為，BANYAN網(wǎng)絡(luò)是按級由的，換句話說，在BANYAN網(wǎng)絡(luò)中，整個交換網(wǎng)絡(luò)連接方式的置換，是由各級及級間逐次置換構(gòu)成。例

56、如，圖中連接方式的實現(xiàn)，是各級及級間置換的疊加1 10 03 32 21 10 03 32 21 10 03 32 21 10 03 32 20 1 2 3 3 0 2 1 給定連接函數(shù)的排列為 ：自選路由自選路由5432106754321067010101010101010101010101入入 線線第第1級級第第2級級第第3級級信元信元信元信元出出線線信元信元信元信元0101101110100110111011011101101110信息信息信息信息信息信息信息信息地址地址地址地址地址地址正好到達(dá)正好到達(dá)(010)且且標(biāo)標(biāo)簽簽已已丟丟棄棄比比特特流流 簡單簡單 模塊化模塊化 可擴展性好可擴

57、展性好 信元交換時延小信元交換時延小3. BANYAN網(wǎng)絡(luò)的網(wǎng)絡(luò)的 內(nèi)部競爭（內(nèi)部阻塞）內(nèi)部競爭（內(nèi)部阻塞） 兩路信息同搶交換單元內(nèi)部的通路資源。兩路信息同搶交換單元內(nèi)部的通路資源。 出線競爭（出線阻塞）出線競爭（出線阻塞）不討論不討論 不同入端來的信息同時爭搶交換網(wǎng)絡(luò)同一個輸出端口不同入端來的信息同時爭搶交換網(wǎng)絡(luò)同一個輸出端口 造成出線阻塞。造成出線阻塞。BANYAN網(wǎng)絡(luò)網(wǎng)絡(luò)的是具有內(nèi)部競爭的有阻塞網(wǎng)絡(luò)。的是具有內(nèi)部競爭的有阻塞網(wǎng)絡(luò)。根據(jù)發(fā)生阻塞的22交換單元在網(wǎng)絡(luò)中的位置，阻塞會出現(xiàn) 出線阻塞采用輸入或輸出緩沖排隊的方法可以很好地解決。所以通常BANYAN網(wǎng)絡(luò)的內(nèi)部阻塞不包括出線阻塞。圖2

58、.43 BANYAN網(wǎng)絡(luò)的內(nèi)部競爭（造成阻塞）比特流 BANYAN網(wǎng)絡(luò)的網(wǎng)絡(luò)的 阻塞是入線向同一出線上發(fā)送信元產(chǎn)生的，最壞情況下阻塞的概率為50%。 適當(dāng)限制入線上的信息量或加大緩沖存儲器。 增加多級交換網(wǎng)絡(luò)的級數(shù)。 若要完全消除N N的網(wǎng)絡(luò)(其級數(shù)為Mlog2N)的BANYAN內(nèi)部阻塞，需要級。 增加BANYAN網(wǎng)的平面樹 構(gòu)成多通道交換網(wǎng)絡(luò)。 使用排序- BANYAN網(wǎng)絡(luò)。解決內(nèi)部阻塞的方法解決內(nèi)部阻塞的方法N = 2M， M為級數(shù)，為級數(shù)，8 = 23n 為了滿足BANYAN網(wǎng)絡(luò)的無阻塞條件，我們可以在BANYAN網(wǎng)絡(luò)前加入排序網(wǎng)絡(luò)batcher網(wǎng)絡(luò)，構(gòu)成BATCHER -BANYAN網(wǎng)

59、絡(luò)（B-B網(wǎng)絡(luò)）。n BATCHER排序網(wǎng)是由22的比較器構(gòu)成的。n 它是一個兩入線/兩出線的比較單元，分為向上排序器與向下排序器。n B-B網(wǎng)絡(luò)目前ATM交換機使用較多。xymin(x,y)max(x,y)向上排序器（升序排列）xmin(x,y)ymax(x,y)向下排序器（降序排列）圖2.47 batcher排序器（路由標(biāo)簽大的信息往箭頭方向送） 排序和交換在極為相似，這種功能上的相似性也導(dǎo)致了兩者在上的相似性。但工作原理還是有區(qū)別的。 排序網(wǎng)絡(luò)可對進(jìn)入該網(wǎng)絡(luò)的進(jìn)行排序，而不是地址； 交換是對進(jìn)行映射。 用比較器來構(gòu)成一種能自動排序數(shù)字的網(wǎng)絡(luò)，也稱比較器網(wǎng)絡(luò)。 顯然排序網(wǎng)絡(luò)是直接執(zhí)行排序算

60、法的硬件實現(xiàn)方法 。以前常用的軟件排序算法氣泡排序；快速排序堆排序；桶排序基排序；歸并排序等。求解排序問題的另一種方法是使用網(wǎng)絡(luò)的辦法，即88的Batcher-BANYAN網(wǎng)絡(luò)011111010100011010100111111100010011 batcher排序網(wǎng)絡(luò)是按遞增順序排序的。排序網(wǎng)絡(luò)是按遞增順序排序的。BATCHER排序網(wǎng)絡(luò)BANYAN網(wǎng)絡(luò)信息的選路標(biāo)簽分別是信息的選路標(biāo)簽分別是011，111，010，100升序排列BATCHER排序網(wǎng)絡(luò)圖2.49 對比Batcher-BANYAN網(wǎng)絡(luò)，BANYAN網(wǎng)絡(luò)出現(xiàn)內(nèi)部競爭0 1 4 6 入線3 7 2 4 出線假設(shè)假設(shè)則信息的選路標(biāo)簽