現(xiàn)代交換_chapter2(三)

1、三、交換單元的內(nèi)部結(jié)構(gòu)及工作原理三、交換單元的內(nèi)部結(jié)構(gòu)及工作原理3.4 總線型交換單元總線型交換單元 結(jié)構(gòu)如圖結(jié)構(gòu)如圖2.21所示。包括所示。包括入線入線控制部件、控制部件、出線控制部件和總線三部分。出線控制部件和總線三部分。 總線按時(shí)隙輪流分配給各個(gè)入線控制部件總線按時(shí)隙輪流分配給各個(gè)入線控制部件和出線控制部件使用，分配到的輸入部件將輸和出線控制部件使用，分配到的輸入部件將輸入信號(hào)送到總線上入信號(hào)送到總線上。四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò) T型交換單元功能型交換單元功能S型交換單元功能（不能單獨(dú)使用）型交換單元功能（不能單獨(dú)使用）交換單元容量增加有限交換單元容量增加有限四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò) 交

2、換網(wǎng)絡(luò)：交換網(wǎng)絡(luò)：由若干個(gè)交換單元按照一定的由若干個(gè)交換單元按照一定的拓?fù)浣Y(jié)構(gòu)構(gòu)成的網(wǎng)絡(luò)。拓?fù)浣Y(jié)構(gòu)構(gòu)成的網(wǎng)絡(luò)。 三大要素：三大要素：交換單元、交換單元間的拓?fù)浣粨Q單元、交換單元間的拓?fù)溥B接、控制方式連接、控制方式四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)(1)單級(jí)交換網(wǎng)絡(luò)單級(jí)交換網(wǎng)絡(luò): 一個(gè)交換單元組成，直接實(shí)現(xiàn)入線一個(gè)交換單元組成，直接實(shí)現(xiàn)入線到出線的連接到出線的連接(2) 多級(jí)交換網(wǎng)絡(luò)多級(jí)交換網(wǎng)絡(luò)第第1級(jí)的每個(gè)交換單元與第級(jí)的每個(gè)交換單元與第2級(jí)級(jí)的交換單元之間僅有一條鏈路的交換單元之間僅有一條鏈路四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò) 內(nèi)部阻塞：內(nèi)部阻塞： 出、入線空閑，但因交換網(wǎng)絡(luò)級(jí)間鏈路被出、入線空閑，但因交換網(wǎng)絡(luò)

3、級(jí)間鏈路被占用而無法接通的現(xiàn)象稱多級(jí)交換網(wǎng)絡(luò)的占用而無法接通的現(xiàn)象稱多級(jí)交換網(wǎng)絡(luò)的內(nèi)部?jī)?nèi)部阻塞阻塞。 若用計(jì)算機(jī)的術(shù)語，阻塞也可稱為沖突，若用計(jì)算機(jī)的術(shù)語，阻塞也可稱為沖突，即不同入線上的信息試圖時(shí)占用同一條鏈路。即不同入線上的信息試圖時(shí)占用同一條鏈路。四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò) 無阻塞交換網(wǎng)絡(luò)無阻塞交換網(wǎng)絡(luò) 交換網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)的交換網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)的目標(biāo)是滿足一定的連接能力的要求下，盡目標(biāo)是滿足一定的連接能力的要求下，盡量最小化交叉點(diǎn)數(shù)。量最小化交叉點(diǎn)數(shù)。 三種無阻塞網(wǎng)絡(luò)三種無阻塞網(wǎng)絡(luò)嚴(yán)格無阻塞網(wǎng)絡(luò)嚴(yán)格無阻塞網(wǎng)絡(luò)可重排無阻塞網(wǎng)絡(luò)可重排無阻塞網(wǎng)絡(luò)廣義無阻塞網(wǎng)絡(luò)廣義無阻塞網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò) 嚴(yán)

4、格無阻塞網(wǎng)絡(luò)：嚴(yán)格無阻塞網(wǎng)絡(luò)： 不管網(wǎng)絡(luò)處于何種狀態(tài)，任何時(shí)刻都可不管網(wǎng)絡(luò)處于何種狀態(tài)，任何時(shí)刻都可以在交換網(wǎng)絡(luò)中建立一個(gè)連接，只要這個(gè)連以在交換網(wǎng)絡(luò)中建立一個(gè)連接，只要這個(gè)連接的起點(diǎn)、終點(diǎn)是空閑的，而不會(huì)影響網(wǎng)絡(luò)接的起點(diǎn)、終點(diǎn)是空閑的，而不會(huì)影響網(wǎng)絡(luò)中已建立起來的連接。中已建立起來的連接。理想網(wǎng)絡(luò)理想網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò) 可重排無阻塞網(wǎng)絡(luò)可重排無阻塞網(wǎng)絡(luò) 不管網(wǎng)絡(luò)處于何種狀態(tài)，任何時(shí)刻都可不管網(wǎng)絡(luò)處于何種狀態(tài)，任何時(shí)刻都可以在一個(gè)交換網(wǎng)絡(luò)中直接或?qū)σ延械倪B接重以在一個(gè)交換網(wǎng)絡(luò)中直接或?qū)σ延械倪B接重選路由來建立一個(gè)連接，只要這個(gè)連接的起選路由來建立一個(gè)連接，只要這個(gè)連接的起點(diǎn)和終點(diǎn)是空

5、閑的。點(diǎn)和終點(diǎn)是空閑的。四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò) 廣義無阻塞網(wǎng)絡(luò)廣義無阻塞網(wǎng)絡(luò) 一個(gè)給定的網(wǎng)絡(luò)存在著固有的阻塞的一個(gè)給定的網(wǎng)絡(luò)存在著固有的阻塞的可能，但有可能存在著一種精巧的選路方可能，但有可能存在著一種精巧的選路方法，使得所有的阻塞均可避免，而不必重法，使得所有的阻塞均可避免，而不必重新安排網(wǎng)絡(luò)中已建立起來的連接。新安排網(wǎng)絡(luò)中已建立起來的連接。四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò) CLOS網(wǎng)絡(luò)網(wǎng)絡(luò): CLOS首次構(gòu)造了如圖首次構(gòu)造了如圖2.28所示的所示的NN的的無阻塞交換網(wǎng)絡(luò)無阻塞交換網(wǎng)絡(luò) (僅適用于奇數(shù)級(jí)網(wǎng)絡(luò)僅適用于奇數(shù)級(jí)網(wǎng)絡(luò))。 采用足夠多的級(jí)數(shù)，對(duì)于較大的采用足夠多的級(jí)數(shù)，對(duì)于較大的N，能夠設(shè)，

6、能夠設(shè)計(jì)出一種無阻塞網(wǎng)絡(luò)，其交叉點(diǎn)數(shù)增長(zhǎng)的速度計(jì)出一種無阻塞網(wǎng)絡(luò)，其交叉點(diǎn)數(shù)增長(zhǎng)的速度小于小于N1（0 1）也就是說，使用）也就是說，使用CLOS網(wǎng)絡(luò)，既可以減少交叉點(diǎn)數(shù)，又可以做到無阻網(wǎng)絡(luò)，既可以減少交叉點(diǎn)數(shù)，又可以做到無阻塞。塞。四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)CLOS網(wǎng)絡(luò)的結(jié)構(gòu)：網(wǎng)絡(luò)的結(jié)構(gòu)：兩邊各有兩邊各有r個(gè)對(duì)稱的個(gè)對(duì)稱的mn矩形交換單元，中間矩形交換單元，中間是是m個(gè)個(gè)r r的方形交換單元。的方形交換單元。每一個(gè)交換單元都與下一級(jí)的各個(gè)交換單元有每一個(gè)交換單元都與下一級(jí)的各個(gè)交換單元有連接且僅有一條連接。連接且僅有一條連接。任意一條入線與出線之間均存在一條通過中間任意一條入線與出線之間均存在

7、一條通過中間級(jí)交換單元的路徑。級(jí)交換單元的路徑。四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)三級(jí)三級(jí)CLOSCLOS網(wǎng)絡(luò)網(wǎng)絡(luò)C(m,n,r) C(m,n,r) 無阻塞條件無阻塞條件: :如果如果m 2n-1，則此網(wǎng)絡(luò)是嚴(yán)格無阻塞的，則此網(wǎng)絡(luò)是嚴(yán)格無阻塞的;如果如果m n，則此網(wǎng)絡(luò)是可重排無阻塞的。，則此網(wǎng)絡(luò)是可重排無阻塞的。四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)TST網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)：兩側(cè)是結(jié)構(gòu)：兩側(cè)是T型接線器，中間是型接線器，中間是S型接線器型接線器負(fù)責(zé)輸入復(fù)用線上時(shí)隙交換負(fù)責(zé)輸入復(fù)用線上時(shí)隙交換負(fù)責(zé)復(fù)用線之間的空間變換負(fù)責(zé)復(fù)用線之間的空間變換負(fù)責(zé)輸出復(fù)用線上時(shí)隙交換負(fù)責(zé)輸出復(fù)用線上時(shí)隙交換四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)工作原理工作

8、原理 每側(cè)有每側(cè)有32個(gè)個(gè)T接線器，接線器，T接線器的接線器的容量為容量為512，輸入側(cè)，輸入側(cè)T接線器采用接線器采用輸出輸出控制控制方式方式; S接線器采用接線器采用輸出控制輸出控制方式方式; 輸出側(cè)輸出側(cè)T接線器則采用接線器則采用輸入控制輸入控制方式。方式。四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)工作原理工作原理 A用戶用戶 HW0TS2 B用戶用戶 HW31TS511雙向路由，空閑時(shí)隙采用反向內(nèi)時(shí)隙法。雙向路由，空閑時(shí)隙采用反向內(nèi)時(shí)隙法。首先選擇內(nèi)時(shí)隙首先選擇內(nèi)時(shí)隙7;對(duì)應(yīng)反向內(nèi)時(shí)隙為對(duì)應(yīng)反向內(nèi)時(shí)隙為7+512/2=263四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)STS網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)：兩側(cè)是結(jié)構(gòu)：兩側(cè)是S型接線器，中間是型

9、接線器，中間是T型接線器型接線器負(fù)責(zé)輸入復(fù)用線之間空間交換負(fù)責(zé)輸入復(fù)用線之間空間交換負(fù)責(zé)內(nèi)部時(shí)隙交換負(fù)責(zé)內(nèi)部時(shí)隙交換負(fù)責(zé)輸出復(fù)用線之間空間交換負(fù)責(zé)輸出復(fù)用線之間空間交換四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)工作原理工作原理 A用戶用戶 HW1TS5 B用戶用戶 HW2TS16四、交換網(wǎng)絡(luò)四、交換網(wǎng)絡(luò)BanyanBanyan網(wǎng)絡(luò)網(wǎng)絡(luò) 1. 結(jié)構(gòu)結(jié)構(gòu) 空分交換網(wǎng)絡(luò)，由若干個(gè)空分交換網(wǎng)絡(luò)，由若干個(gè)2x2交換單元組成的多交換單元組成的多級(jí)交換網(wǎng)絡(luò)。級(jí)交換網(wǎng)絡(luò)。 一個(gè)交叉連接單元有兩種狀態(tài)：平行連接和交一個(gè)交叉連接單元有兩種狀態(tài)：平行連接和交叉連接。叉連接。 44的多級(jí)互連網(wǎng)絡(luò)的多級(jí)互連網(wǎng)絡(luò) 4 個(gè)交叉連接單元連接起

10、來，得一個(gè)個(gè)交叉連接單元連接起來，得一個(gè)44的多的多級(jí)互連網(wǎng)絡(luò)。每個(gè)入端到出端都有一條且僅有一級(jí)互連網(wǎng)絡(luò)。每個(gè)入端到出端都有一條且僅有一條路徑，如圖所示。條路徑，如圖所示。 88的多級(jí)互連網(wǎng)絡(luò)如圖所示?？烧J(rèn)為是由的多級(jí)互連網(wǎng)絡(luò)如圖所示?？烧J(rèn)為是由前面前面4個(gè)個(gè)22加后面加后面2個(gè)個(gè)44交叉連接單元組成交叉連接單元組成的混合級(jí)構(gòu)成。的混合級(jí)構(gòu)成。88多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)2. Banyan網(wǎng)絡(luò)的性質(zhì)網(wǎng)絡(luò)的性質(zhì)（ 1）惟一路徑性質(zhì)）惟一路徑性質(zhì) Banyan網(wǎng)絡(luò)中的每條入線和每條出線之間都網(wǎng)絡(luò)中的每條入線和每條出線之間都只有一條路徑，稱之為惟一路徑性質(zhì)。只有一條路徑，稱之為惟一路徑性質(zhì)。（2）自

11、選路由性質(zhì)）自選路由性質(zhì) Banyan網(wǎng)絡(luò)的入端數(shù)和出端數(shù)相等。若設(shè)其為網(wǎng)絡(luò)的入端數(shù)和出端數(shù)相等。若設(shè)其為N，則，則必有必有N2M。既可以把。既可以把N個(gè)入端和個(gè)入端和N個(gè)出端順序分別編號(hào)為個(gè)出端順序分別編號(hào)為M位二進(jìn)制數(shù)字來區(qū)別位二進(jìn)制數(shù)字來區(qū)別N個(gè)入端和出端。個(gè)入端和出端。一個(gè)一個(gè)N NN N的的BanyanBanyan網(wǎng)絡(luò)共有網(wǎng)絡(luò)共有M M級(jí)，由入端級(jí)，由入端 i i 到出端到出端 j j 的的連接，每級(jí)交叉連接單元的出口號(hào)組成一個(gè)連接，每級(jí)交叉連接單元的出口號(hào)組成一個(gè)M M位二進(jìn)制數(shù)就表位二進(jìn)制數(shù)就表示出口號(hào)。示出口號(hào)。01出端出端5（101）的路徑）的路徑如果把出線的編號(hào)如果把出線的

12、編號(hào)(或者叫作地址或者叫作地址)以二進(jìn)制數(shù)字的形式以二進(jìn)制數(shù)字的形式送到交換單元，則每一級(jí)上的送到交換單元，則每一級(jí)上的22交叉連接單元就只需要根交叉連接單元就只需要根據(jù)這個(gè)地址中的某一位就可以判別應(yīng)將其送往哪一個(gè)出端上。據(jù)這個(gè)地址中的某一位就可以判別應(yīng)將其送往哪一個(gè)出端上。輸出沖突輸出沖突內(nèi)部爭(zhēng)用，會(huì)內(nèi)部爭(zhēng)用，會(huì)引起內(nèi)部阻塞引起內(nèi)部阻塞（3）內(nèi)部阻塞性質(zhì)）內(nèi)部阻塞性質(zhì) Banyan網(wǎng)絡(luò)不僅有內(nèi)部阻塞，而且這種內(nèi)部阻塞隨著網(wǎng)絡(luò)不僅有內(nèi)部阻塞，而且這種內(nèi)部阻塞隨著陣列級(jí)數(shù)的增加而增加。因此，陣列級(jí)數(shù)的增加而增加。因此，Banyan網(wǎng)絡(luò)不可能做得很網(wǎng)絡(luò)不可能做得很大。大。（1 1）增加多級(jí)開關(guān)陣列

13、的級(jí)數(shù)。把一個(gè)）增加多級(jí)開關(guān)陣列的級(jí)數(shù)。把一個(gè)M M級(jí)級(jí)BanyanBanyan網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò)對(duì)折疊加，使其級(jí)數(shù)增加到折疊加，使其級(jí)數(shù)增加到2M2M1 1，得到的網(wǎng)絡(luò)是無阻塞的，得到的網(wǎng)絡(luò)是無阻塞的. .由由3 3級(jí)增加到級(jí)增加到5 5級(jí)，消除內(nèi)部阻塞。級(jí)，消除內(nèi)部阻塞。 內(nèi)部阻塞是一個(gè)必須要解決的問題，近年來許多人進(jìn)內(nèi)部阻塞是一個(gè)必須要解決的問題，近年來許多人進(jìn)行這方面的研究，提出了若干方案。行這方面的研究，提出了若干方案。011對(duì)折疊對(duì)折疊加為加為1101111011011010010對(duì)折疊對(duì)折疊加為加為01010（2）排序）排序Banyan網(wǎng)絡(luò)，即通過在網(wǎng)絡(luò)，即通過在Banyan網(wǎng)絡(luò)前面添加

14、網(wǎng)絡(luò)前面添加一個(gè)排序網(wǎng)絡(luò)使其成為一個(gè)無阻塞網(wǎng)絡(luò)?？梢宰C明，一個(gè)排序網(wǎng)絡(luò)使其成為一個(gè)無阻塞網(wǎng)絡(luò)?？梢宰C明， Banyan網(wǎng)絡(luò)在滿足某些特定條件下可以進(jìn)行無阻塞連接，網(wǎng)絡(luò)在滿足某些特定條件下可以進(jìn)行無阻塞連接，例如例如互換網(wǎng)絡(luò)?；Q網(wǎng)絡(luò)。 洗牌洗牌互換網(wǎng)絡(luò)的無阻塞性質(zhì)互換網(wǎng)絡(luò)的無阻塞性質(zhì) 若有兩個(gè)連接若有兩個(gè)連接ab，cd，其中入端號(hào)和出，其中入端號(hào)和出端號(hào)滿足：端號(hào)滿足：ca，bd，dbca，則兩連接，則兩連接的路徑完全不重疊。的路徑完全不重疊。 在在BanyanBanyan網(wǎng)絡(luò)前附加一個(gè)排序網(wǎng)絡(luò)組成排序輸網(wǎng)絡(luò)前附加一個(gè)排序網(wǎng)絡(luò)組成排序輸入的二進(jìn)制序列可理解為不同信元中的虛通路標(biāo)識(shí)入的二進(jìn)制序列可理解為不同信元中的虛通路標(biāo)識(shí)符符(VCI)(VCI)。排序規(guī)則排序規(guī)則為：為：(1)(1)在每級(jí)，如果兩個(gè)在每級(jí)，如果兩個(gè)VCIVCI標(biāo)識(shí)符到達(dá)同一個(gè)交換單元，則較標(biāo)識(shí)符到達(dá)同一個(gè)交換單