3交換網(wǎng)絡(luò)完整版本

交換網(wǎng)絡(luò)1ATM交換的基本原理akkablccmxxzyxyssQueueQueueQueue數(shù)據(jù)信頭翻譯表O1O2OqI1I2In輸入鏈路VCC輸出鏈路VCCI1xO1kyOqmzO2l::InxO1ayO2bsOqc信元頭輸入輸出信元數(shù)據(jù)信元頭信元頭翻譯信元被交換的同時(shí)，輸入信頭的值被翻譯成輸出信元頭的值。2交換的基本功能是在任意的入線和出線之間建立連接。在交換系統(tǒng)中完成這一基本功能的部件就是交換網(wǎng)絡(luò)，它是交換系統(tǒng)的核心。交換網(wǎng)絡(luò)是由若干個(gè)交換單元按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的。

交換單元是構(gòu)成交換網(wǎng)絡(luò)的最基本的部件。交換網(wǎng)絡(luò)有：空分、時(shí)分?jǐn)?shù)字、模擬1、交換網(wǎng)絡(luò)的構(gòu)成和分類32.1交換單元的基本概念入線出線控制端狀態(tài)端…………MXN的交換單元0011M-1N-14入線出線0011442323同步時(shí)分復(fù)用信號(hào)的交換兩種信號(hào)的交換5入線出線001221異步時(shí)分復(fù)用信號(hào)的交換0210001222兩種信號(hào)的交換6基本交換模塊基本交換模塊的容量規(guī)模：從2x2到16x16信息速率：從155Mbit/s、622Mbit/s到2.5Gbit/s基本交換模塊的容量（規(guī)模和信息速率）決定于：采用的技術(shù)工藝、設(shè)計(jì)的集成化程度基本交換模塊的基本功能——排隊(duì)功能基本交換模塊是一個(gè)統(tǒng)計(jì)復(fù)用器在基本交換模塊內(nèi)部會(huì)出現(xiàn)競爭多個(gè)信元需要同時(shí)使用相同資源（如內(nèi)部線路、出線等）在出現(xiàn)競爭時(shí)，需要對(duì)沖突的信元進(jìn)行緩沖（排隊(duì)）若交換模塊是內(nèi)部完全無阻塞的，則不需要內(nèi)部緩沖為了解決對(duì)相同出線的競爭，必須在基本模塊內(nèi)提供排隊(duì)功能7排隊(duì)策略信元排隊(duì)和緩沖是基本交換模塊的基本功能根據(jù)交換單元的結(jié)構(gòu)和所需的信息速率，需要在交換單元的入線、出線或單元內(nèi)部設(shè)計(jì)信元的緩沖隊(duì)列交換單元中可采用三種排隊(duì)策略（根據(jù)緩沖器在交換單元中的物理位置劃分）：輸入排隊(duì)輸出排隊(duì)中央排隊(duì)8輸入排隊(duì)基本思想在交換單元的輸入端解決可能的競爭問題。實(shí)現(xiàn)方式為每一條入線配置一個(gè)緩沖隊(duì)列，信元在隊(duì)列中排隊(duì)在一個(gè)信元周期內(nèi)，如果出現(xiàn)多個(gè)入線上的信元競爭同一的出線時(shí)，則由一個(gè)仲裁邏輯來決定哪些入線隊(duì)列中的信元是允許通行的，而其他隊(duì)列中的信元需要等待經(jīng)過仲裁后的信元不會(huì)再出現(xiàn)競爭9輸入排隊(duì)模型傳輸交換媒體仲裁邏輯12N12N出線入線輸入隊(duì)列每條入線一個(gè)緩沖隊(duì)列信元在入線排隊(duì)交換傳輸媒體是一個(gè)無阻塞的傳輸網(wǎng)絡(luò)仲裁邏輯決定可以得到服務(wù)的入線仲裁策略輪流服務(wù)、具有優(yōu)先級(jí)（固定優(yōu)先級(jí)或隊(duì)列長度優(yōu)先等）10輸入排隊(duì)的缺點(diǎn)在入線處的隊(duì)列將需要更多的緩沖容量存在隊(duì)頭阻塞（HOL）在一個(gè)信元周期內(nèi)，任一條出線都只能為一個(gè)信元提供輸出服務(wù)，而選擇該出線的其他信元必須在輸入隊(duì)列中等待若一條入線上的隊(duì)列的排頭信元因競爭失敗而阻塞，該隊(duì)列中的所有后續(xù)信元也被迫阻塞，即使該隊(duì)列中的后續(xù)信元所選擇的出線當(dāng)前是空閑的。一個(gè)信元周期內(nèi)，通過交換傳輸媒體傳輸?shù)男旁獢?shù)P不超過交換單元的入線總數(shù)N，即PN。在輸入排隊(duì)模型中，仲裁邏輯是必須的用于確定可以得到服務(wù)的入線1112輸出排隊(duì)基本思想來自入線的信元可以自由通過交換傳輸媒體傳送（交換）到所需的出線上，在出線上設(shè)置緩沖隊(duì)列解決多信元對(duì)出線的競爭。實(shí)現(xiàn)方法在一個(gè)信元周期內(nèi)，所有信元都可無需仲裁地從入線到達(dá)所需的出線每條出線配置一個(gè)隊(duì)列，以便緩沖同時(shí)到達(dá)的競爭該出線的多個(gè)信元一個(gè)信元周期內(nèi)，一條出線只能為一個(gè)信元服務(wù)，未服務(wù)的信元將暫存在該出線的輸出隊(duì)列中13輸出排隊(duì)模型傳輸交換媒體12N12N出線入線輸出隊(duì)列交換傳輸媒體無阻塞的傳輸網(wǎng)絡(luò)，信元通過傳輸媒體時(shí)無需仲裁邏輯每出線配置一個(gè)緩沖隊(duì)列信元在出線處排隊(duì)，采用FIFO原則，保證信元的順序14輸出排隊(duì)的優(yōu)缺點(diǎn)設(shè)置在出線上的隊(duì)列所需的緩沖空間較小去往同一條出線的多個(gè)信元可以在同一個(gè)信元周期內(nèi)交換到出線上，不存在隊(duì)頭阻塞不需要仲裁邏輯為保證沒有信元丟失，在傳輸交換媒體中信元的傳輸交換的速率必須N倍于入線的速率輸出排隊(duì)策略對(duì)緩沖器的訪問速度要求很高在一個(gè)信元周期內(nèi)需要對(duì)隊(duì)列緩沖器進(jìn)行N次信元寫操作和一次信元讀操作。15基本思想為了減少整個(gè)交換單元所需的總緩沖容量，在基本交換單元中設(shè)置一個(gè)共享的隊(duì)列緩沖器，被所有的入線和出線所公用。實(shí)現(xiàn)方法在基本交換單元的中央設(shè)置一個(gè)隊(duì)列緩沖器，被所有的入線和出線所共享來自所有入線上的全部信元都直接存入中央隊(duì)列各出線從中央隊(duì)列中查找目的地為其自身的信元，依照先進(jìn)先出的原則取出并發(fā)送中央排隊(duì)16中央排隊(duì)模型交換傳輸媒體I12N12N出線入線中央隊(duì)列傳輸交換媒體II共享的中央隊(duì)列被入線和出線所公用交換傳輸媒體分為兩部分輸入信元通過交換傳輸媒體I進(jìn)入中央隊(duì)列排隊(duì)；再通過輸入信元通過交換傳輸媒體II輸出到出線。信元通過傳輸媒體時(shí)無需仲裁邏輯。17下圖是一個(gè)交叉點(diǎn)緩沖方式（CrosspointBuffer），即緩沖器設(shè)置在交叉點(diǎn)中，用在基于crossbar交換網(wǎng)絡(luò)中。交叉點(diǎn)緩沖方式不存在HOL阻塞現(xiàn)象，其緩沖性能類似于輸出緩沖方式，但不存在加速因子，即對(duì)內(nèi)部處理速度和存儲(chǔ)器存儲(chǔ)速率沒有加速要求，但這種方式需要較多數(shù)量的存儲(chǔ)器。交叉點(diǎn)緩沖18中央排隊(duì)的優(yōu)缺點(diǎn)中央隊(duì)列被所有入線和出線共享，提高了緩沖器的利用率，因此大大減少隊(duì)列緩沖器的總?cè)萘拷粨Q單元的控制管理復(fù)雜出線必須能夠通過某種查找機(jī)制，從中央隊(duì)列中找出準(zhǔn)備輸出到出線的信元必須保證中央緩沖器中的各邏輯隊(duì)列具有先進(jìn)先出的順序由于對(duì)中央緩沖器的信元讀寫是完全隨機(jī)的，因此需要一套復(fù)雜的存儲(chǔ)器管理系統(tǒng)19三種排隊(duì)策略的性能分析衡量排隊(duì)策略性能的參數(shù)信元丟失率信元的排隊(duì)時(shí)延所需隊(duì)列緩沖器的容量（實(shí)現(xiàn)參數(shù)）研究性能的方法在交換單元的輸入線上，給定一種特定的業(yè)務(wù)類型和業(yè)務(wù)量負(fù)荷，來研究不同排隊(duì)策略的性能。進(jìn)行排隊(duì)策略的性能的手段直觀的分析建立數(shù)學(xué)模型計(jì)算機(jī)仿真的20該圖表示了一個(gè)帶緩沖型banyan交換網(wǎng)絡(luò)（BufferedBanyan），它是在交換單元（SE）內(nèi)部設(shè)置緩沖。緩沖型banyan緩沖方式與交叉點(diǎn)緩沖方式不同，緩沖型banyan的緩沖器主要是用來存儲(chǔ)在內(nèi)部競爭中失敗的信元，減少信元丟失率。當(dāng)然緩沖器即使在交換單元（SE）內(nèi)部，也會(huì)有不同的配置方式（輸入方式，輸出方式，輸入輸出方式），圖中就是一個(gè)由采用輸入緩沖方式的SE構(gòu)成的緩沖型banyan交換網(wǎng)絡(luò)。

緩沖型banyan交換網(wǎng)絡(luò)（輸入緩沖方式）21郵局中的輸入排隊(duì)模型一個(gè)郵局中有兩個(gè)服務(wù)窗口郵局大門相當(dāng)于一條入線兩個(gè)服務(wù)窗口相當(dāng)于兩條出線到達(dá)郵局的顧客都郵局門口排在一個(gè)隊(duì)列中相當(dāng)于輸入隊(duì)列隊(duì)列按照先進(jìn)先出原則服務(wù)隊(duì)頭的顧客被阻塞（等待）會(huì)導(dǎo)致隊(duì)中的其他顧客也得不到服務(wù)

郵票

寄信

寄信

郵票

郵票郵票窗口郵寄窗口22郵局中的輸出排隊(duì)模型到達(dá)的顧客都直接進(jìn)入郵局，并根據(jù)自己的目的選擇排在一個(gè)服務(wù)窗口的隊(duì)列中顧客的選擇相當(dāng)于交換過程窗口隊(duì)列相當(dāng)于輸出隊(duì)列服務(wù)窗口的利用率得到提高顧客排隊(duì)的等待時(shí)間減少了各服務(wù)窗口的隊(duì)列相互獨(dú)立，在一個(gè)隊(duì)列中等待的顧客不會(huì)影響其他服務(wù)隊(duì)列中的顧客。

郵票

郵票

郵票郵票窗口郵寄窗口

寄信

寄信

寄信23郵局中的中央排隊(duì)模型輸出排隊(duì)要求每個(gè)服務(wù)窗口隊(duì)列有足夠的隊(duì)列座位相當(dāng)于最壞情況下的隊(duì)列長度為減少郵局中的座位總數(shù),所有服務(wù)窗口共享一個(gè)隊(duì)列相當(dāng)于在中央排隊(duì)可以減少總的隊(duì)列緩沖容量智能服務(wù)員在服務(wù)窗口空閑時(shí)，從隊(duì)列中找出下一個(gè)需要被服務(wù)的顧客服務(wù)員的功能對(duì)應(yīng)于一個(gè)復(fù)雜的控制邏輯

郵票

寄信

寄信

郵票

郵票郵票窗口郵寄窗口

寄信

服務(wù)員24三種排隊(duì)策略的直觀分析平均等待時(shí)間對(duì)相同的外部業(yè)務(wù)負(fù)荷，輸入排隊(duì)的平均等待時(shí)間比其他兩種排隊(duì)策略更長隊(duì)列緩沖器需求輸入排隊(duì)需要最大中央排隊(duì)需要最少信元丟失率在隊(duì)列緩沖容量相同的情況下，輸入排隊(duì)信元丟失率明顯高于輸出排隊(duì)和中央排隊(duì)25三種策略的實(shí)現(xiàn)參數(shù)的比較263、交換網(wǎng)絡(luò)交換網(wǎng)絡(luò)是由若干個(gè)交換單元按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)。交換網(wǎng)絡(luò)的三個(gè)基本要素是：交換單元、不同交換單元間的拓?fù)溥B接和控制方式。27交換網(wǎng)絡(luò)的一般結(jié)構(gòu)……控制單元出線入線……交換單元交換單元交換單元交換單元交換網(wǎng)絡(luò)28單級(jí)交換網(wǎng)絡(luò)和多級(jí)交換網(wǎng)絡(luò)交換網(wǎng)絡(luò)按拓?fù)溥B接方式可分為：單級(jí)交換網(wǎng)絡(luò)多級(jí)交換網(wǎng)絡(luò)出線0N-1入線0M-1單級(jí)交換網(wǎng)絡(luò)交換單元29混合式互換網(wǎng)絡(luò)0123456701234567輸入端口輸出端口反饋回路30多級(jí)交換網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可用三個(gè)參數(shù)來說明：每個(gè)交換單元的容量交換單元的級(jí)數(shù)交換單元間的連接通路（鏈路）多級(jí)交換網(wǎng)絡(luò)31多級(jí)交換網(wǎng)絡(luò)(nmxnm兩級(jí)交換網(wǎng)絡(luò))……………O1n-1O1n-1…O1n-1O1m-1O1m-1O1m-1……………………OO11m-1n-11級(jí)2級(jí)32多級(jí)互連網(wǎng)的內(nèi)部競爭在網(wǎng)絡(luò)邊緣，信元會(huì)因競爭輸出線而發(fā)生丟失MIN內(nèi)部對(duì)內(nèi)部資源的競爭也會(huì)造成信元丟失，即內(nèi)部阻塞內(nèi)部鏈路競爭出線競爭33多級(jí)交換網(wǎng)絡(luò)的內(nèi)部阻塞

若出、入線空閑，但因交換網(wǎng)絡(luò)級(jí)間鏈路被占用而無法接通的現(xiàn)象，稱為多級(jí)交換網(wǎng)絡(luò)的內(nèi)部阻塞。嚴(yán)格無阻塞網(wǎng)絡(luò)：不管網(wǎng)絡(luò)處于何種狀態(tài)，任何時(shí)刻都可以在交換網(wǎng)絡(luò)中建立一個(gè)連接，只要這個(gè)連接的起點(diǎn)、終點(diǎn)是空閑的，而不會(huì)影響網(wǎng)絡(luò)中已建立起來的連接。34可重排無阻塞網(wǎng)絡(luò)：不管網(wǎng)絡(luò)處于何種狀態(tài)，任何時(shí)刻都可以在交換網(wǎng)絡(luò)中直接或?qū)σ延械倪B接重選路由來建立一個(gè)連接，只要這個(gè)連接的起點(diǎn)、終點(diǎn)是空閑的，而不會(huì)影響網(wǎng)絡(luò)中已建立起來的連接。廣義無阻塞網(wǎng)絡(luò)：指一個(gè)給定的網(wǎng)絡(luò)存在著固有的阻塞可能，但又可能存在著一種精巧的選路方法，使得所有的阻塞均可避免，而不必重新安排網(wǎng)絡(luò)中已建立起來的連接。多級(jí)交換網(wǎng)絡(luò)的內(nèi)部阻塞3513421342C1C1cc2cc2可重排無阻塞網(wǎng)絡(luò)36采用反壓機(jī)制的無阻塞MIN各交換單元的輸入具有緩沖器，存儲(chǔ)競爭失敗的信元內(nèi)部控制機(jī)制監(jiān)視緩沖器的充滿程度，當(dāng)緩沖器快充滿時(shí)，向上游交換單元發(fā)送反壓控制，防止隊(duì)列溢出內(nèi)部鏈路速率需高于外部，保證在入線處無信元丟失輸出控制器輸入控制器緩沖器第K-1級(jí)第K級(jí)反壓控制交換單元交換單元37ATM交換機(jī)構(gòu)和交換系統(tǒng)38ATM交換系統(tǒng)舉例ATM交換系統(tǒng)是由話路子系統(tǒng)和控制子系統(tǒng)組成，其中話路子系統(tǒng)由輸入和輸出側(cè)接口以及交換網(wǎng)絡(luò)組成，該ATM交換系統(tǒng)的交換網(wǎng)絡(luò)采用了Sunshine交換結(jié)構(gòu)，如圖所示。一個(gè)ATM交換系統(tǒng)實(shí)例393.1CLOS網(wǎng)絡(luò)為了減少交叉點(diǎn)總數(shù)而同時(shí)具有嚴(yán)格的無阻塞特性，CLOSC.很早就提出一種多級(jí)結(jié)構(gòu)，推出了嚴(yán)格無阻塞的條件，這就是著名的CLOS網(wǎng)絡(luò)?！?n…1n1n1n……1…1m

1r11rmmmm11111111rrrr3級(jí)CLOS網(wǎng)絡(luò)40在最壞情況下，中間級(jí)會(huì)有（n-1）X2個(gè)交換單元被占用，因此中間級(jí)至少要有（n-1）X2+1=2n-1個(gè)交換單元，即m≥2n-1時(shí)，可確保無阻塞（嚴(yán)格無阻塞）。CLOS網(wǎng)絡(luò)413.3BANYAN網(wǎng)絡(luò)Banyan網(wǎng)絡(luò)的基本結(jié)構(gòu)Banyan網(wǎng)絡(luò)的基本特性BATCHER-BANYAN網(wǎng)絡(luò)基于banyan的多通路結(jié)構(gòu)Benes網(wǎng)絡(luò)42banyan網(wǎng)絡(luò)可分為一些子類，L級(jí)banyan是其中的一類，其特征是只有相鄰級(jí)之間才有鏈路相連，即任何輸入到任何輸出之間的通路都經(jīng)過L級(jí)。L級(jí)banyan網(wǎng)絡(luò)又可分為規(guī)則banyan和不規(guī)則banyan。規(guī)則banyan是指構(gòu)成banyan網(wǎng)絡(luò)的各個(gè)交換單元都是等同的，而不規(guī)則banyan則不然。如果規(guī)則banyan中的各個(gè)交換單元不僅是等同的，而且每個(gè)交換單元的入線數(shù)等于出線數(shù)，則稱此規(guī)則banyan為矩形banyan。1、Banyan網(wǎng)絡(luò)的基本結(jié)構(gòu)43通常將由2X2的交換單元構(gòu)成的單通路網(wǎng)絡(luò)稱為banyan網(wǎng)絡(luò)。banyan網(wǎng)絡(luò)是基于樹型的拓?fù)浣Y(jié)構(gòu)，但每一個(gè)交換單元卻是基于crossbar的結(jié)構(gòu)。2X2的交換單元也具有bar和cross兩種狀態(tài)。1、Banyan網(wǎng)絡(luò)的基本結(jié)構(gòu)4401234567012345678x8的3級(jí)banyan網(wǎng)絡(luò)45樹型結(jié)構(gòu)特性：從banyan的任一輸入端口引出的一組通路形成了2分支樹，級(jí)數(shù)越多，分支越多，級(jí)數(shù)k=㏒2N，N=總?cè)刖€數(shù)/出線數(shù)，即2k=N。單通路特性：

banyan的任一入端到任一出端之間，具有1條且僅有一條通路。自選路由特性：自選路由，即是給定出線地址，不用外加控制命令，就可選到出線?？梢允褂脤?duì)應(yīng)于出端號(hào)的二進(jìn)制碼的選路標(biāo)簽來自動(dòng)選路。2、Banyan網(wǎng)絡(luò)的基本特性4601234567012(010)3(011)4(100)5(101)678x8的3級(jí)banyan網(wǎng)絡(luò)10110(011)(010)(100)(101)Banyan網(wǎng)絡(luò)的自選路由特性47全部8條通往出線3上的路徑，每條路徑上三個(gè)交換單元的出線號(hào)碼都分別是0、1、1，組合起來的二進(jìn)制數(shù)字011正是BANYAN網(wǎng)絡(luò)的出線號(hào)碼3。

48可擴(kuò)展性：

banyan的構(gòu)成具有一定的規(guī)律，可以采用有規(guī)則的擴(kuò)展方法將較小容量的banyan擴(kuò)展成較大規(guī)模。已有NXN的BANYAN網(wǎng)絡(luò)，需構(gòu)成2NX2N的BANYAN網(wǎng)絡(luò)，則可用2組NXN，再加上一組N個(gè)2X2交換單元構(gòu)成。第一組的NXN的N條出線分別與N個(gè)2X2交換單元的某一入線相連，第二組的NXN的N條出線分別與N個(gè)2X2交換單元的另一入線相連。內(nèi)部竟?fàn)幮裕?/p>

banyan是具有內(nèi)部競爭的有阻塞網(wǎng)絡(luò)。2、Banyan網(wǎng)絡(luò)的基本特性4916X16BANYAN交換網(wǎng)絡(luò)的構(gòu)成Banyan網(wǎng)絡(luò)的可擴(kuò)展性5016X16BANYAN交換網(wǎng)絡(luò)的構(gòu)成Banyan網(wǎng)絡(luò)的可擴(kuò)展性511）內(nèi)部阻塞是在2X2交換單元的兩條入線要向同一個(gè)出線上發(fā)送信元時(shí)產(chǎn)生的，最壞情況下概率為50%，若減少入線上的信息量，就可減少阻塞的概率，故可通過適當(dāng)限制入線上的信息量或加大緩沖存儲(chǔ)器來減少內(nèi)部阻塞。2）可以通過增加多級(jí)交換網(wǎng)絡(luò)的級(jí)數(shù)來消除內(nèi)部阻塞。已有證明，若要完全消除NXN的banyan網(wǎng)絡(luò)的內(nèi)部阻塞，至少需要2㏒2N-1級(jí)。3）可以增加banyan網(wǎng)的平面樹，構(gòu)成多通道交換網(wǎng)絡(luò)。4）使用排序-banyan網(wǎng)絡(luò)。解決內(nèi)部阻塞的方法5201234567012(010)3(011)4(100)5(101)678x8的3級(jí)banyan網(wǎng)絡(luò)10110(011)(010)(100)(101)Banyan網(wǎng)絡(luò)的自選路由特性53

該網(wǎng)絡(luò)也簡稱為B-B網(wǎng)，是由BATCHER排序網(wǎng)和BANYAN網(wǎng)組成，它成功地避免了BANYAN網(wǎng)絡(luò)的內(nèi)部阻塞，這是目前ATM交換機(jī)使用較多的一種網(wǎng)絡(luò)。BATCHER排序網(wǎng)是由2X2的比較器（BATCHER比較器）構(gòu)成的。xymin(x,y)max(x,y)xymin(x,y)max(x,y)3、BATCHER-BANYAN網(wǎng)絡(luò)54BatcherSortingNetwork

BatcherSortingNetwork

由2×2的排序單元構(gòu)成，這種排序單元比較兩條入線上信元的目的地址。每一級(jí)的排序操作由箭頭指示，箭頭總是指向地址大的入線經(jīng)排序后應(yīng)去往的出線。如果在兩條入線上僅出現(xiàn)單個(gè)信元，它將作為小地址處理，因而被送到非箭頭所指的出線上。

整個(gè)BatcherSortingNetwork由一系列的”升/降序器”組成，這些排序器接受上升和下降序列并輸出一個(gè)排列好的（單調(diào)）序列。在8*8B-B拓樸結(jié)構(gòu)圖中第一級(jí)上的兩組、每組含兩個(gè)相反方向排序器的輸出分別被二、三級(jí)上的兩個(gè)4線排序單元合并及排序（兩單元的排序方式正好相反），然后送到第四、五、六級(jí)上的8線排序器再進(jìn)行排序。最后在BatcherSortingNetwork的輸出所有的信元都被排好序，但此時(shí)的信元還沒有到達(dá)最終的目的地。

55010101010101010101010101混洗交換Batcher網(wǎng)Banyan網(wǎng)01001001001101101111111111156為了減少或消除banyan的內(nèi)部阻塞，提高吞吐率，除了構(gòu)成B-B網(wǎng)絡(luò)之外，還可以構(gòu)成基于banyan的的各種多通路網(wǎng)絡(luò)。（1）增長型banyan

增長型banyan就是前面加上分配級(jí)，以擴(kuò)大每個(gè)入端的選擇范圍，從而形成多通路網(wǎng)絡(luò)。每增加1級(jí)，每個(gè)入端與每個(gè)出端之間的通路數(shù)就增加1倍。前置分配級(jí)還可以使業(yè)務(wù)流均衡地進(jìn)入banyan的入端，減少banyan對(duì)流入的業(yè)務(wù)流模型的敏感性。4、基于BANYAN的多通路結(jié)構(gòu)570123456701234567增長型banyan增長型BANYAN58（2）擴(kuò)展型banyan

考察banyan中的交換單元，對(duì)應(yīng)于每個(gè)交換單元輸出地址有1條鏈路，如果使每個(gè)輸出地址有d條鏈路，也就是可以任意選擇d條中的1條，就稱為擴(kuò)展型banyan。在擴(kuò)展型banyan網(wǎng)中，2×2的交換單元變成了2d×2d的交換單元。但輸出地址并非2d個(gè)，而仍然是2個(gè)，只要用1個(gè)比特來區(qū)別。于是在任何時(shí)刻，最多可有d個(gè)信息單元傳送到交換單元的每個(gè)輸出；如果對(duì)應(yīng)于同一輸出地址同時(shí)有多于d個(gè)的信元到達(dá)，只能傳送其中的d個(gè)。4、基于BANYAN的多通路結(jié)構(gòu)590123456701234567擴(kuò)展型banyan擴(kuò)展型BANYAN60（3）膨脹型banyan

膨脹型banyan是膨脹度d在各級(jí)可以變化的擴(kuò)展型banyan。（4）復(fù)份型banyan

復(fù)份型banyan是將若干個(gè)相同的banyan并接在一起，形成多平面的網(wǎng)絡(luò)結(jié)構(gòu)。從復(fù)份型banyan的每個(gè)輸入端進(jìn)入的信息單元，可以隨機(jī)地選擇某個(gè)平面，也可以按負(fù)荷均分原則分配到各個(gè)平面，還可以廣播到所有的平面。

4、基于BANYAN的多通路結(jié)構(gòu)610123456701234567膨脹型banyand=2d=3d=4膨脹型BANYAN62Banyan1Banyan2Banyanr…………………………12n12n復(fù)份型banyan復(fù)份型BANYAN63

benes網(wǎng)絡(luò)是著名的多通路網(wǎng)絡(luò)，具有再配置無阻塞的特點(diǎn)?？梢钥闯?，Benes網(wǎng)絡(luò)實(shí)際上相當(dāng)于兩個(gè)banyan（banyan與反轉(zhuǎn)banyan）的背對(duì)背相連，并將中間相鄰兩級(jí)合并為1級(jí)。由于每個(gè)banyan有l(wèi)og2

N級(jí)，因此Benes網(wǎng)絡(luò)共有2log2

N-1級(jí)。

benes網(wǎng)絡(luò)的構(gòu)成也有一定的規(guī)律。使用2X2交換單元的NXNbenes網(wǎng)絡(luò)的構(gòu)成方法為：兩側(cè)各有N/2個(gè)2X2交換單元，中間為兩個(gè)N/2XN/2的子網(wǎng)絡(luò)，每個(gè)交換單元以一條鏈路連到每個(gè)子網(wǎng)絡(luò)；再將中間子網(wǎng)絡(luò)按上述方法繼續(xù)分解，直到中間子網(wǎng)絡(luò)就是2X2交換單元為止。4、BENES網(wǎng)絡(luò)6401234567012345678X8benes網(wǎng)絡(luò)8X8BENES網(wǎng)絡(luò)650123456701234567benes網(wǎng)絡(luò)構(gòu)成方法N/2XN/2N/2XN/2BENES網(wǎng)絡(luò)構(gòu)成方法66多級(jí)互連網(wǎng)的路由標(biāo)簽信元在MIN中從入線到出線所走過的路由可以用一串?dāng)?shù)字來表示，即稱為路由標(biāo)簽01234567891011121314150123456789101112131415001000100110011067交換網(wǎng)絡(luò)（MIN）中的路由MIN需要解決的關(guān)鍵性問題——路由選擇可以根據(jù)兩個(gè)標(biāo)準(zhǔn)來劃分MIN中的選路方法根據(jù)路由信息安放的位置根據(jù)完成選路決策的時(shí)間根據(jù)路由信息安放的位置基于信元：信元自尋路（self-routing）方式基于網(wǎng)絡(luò)：路由表控制（routingtablecontrolled）方式根據(jù)完成選路決策的時(shí)間基于連接：內(nèi)部面向連接，路由在連接建立時(shí)確定基于信元：每個(gè)信元逐個(gè)進(jìn)行路由選擇68自尋路方式的路由選擇