【正文】 網(wǎng)絡(luò)的可擴(kuò)展性 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 78 1）內(nèi)部阻塞是在 2X2交換單元的兩條入線要向同一個出線上發(fā)送信元時產(chǎn)生的，最壞情況下概率為 50%，若減少入線上的信息量，就可減少阻塞的概率，故可通過適當(dāng)限制入線上的信息量或加大緩沖存儲器來減少內(nèi)部阻塞。 2）可以通過增加多級交換網(wǎng)絡(luò)的級數(shù)來消除內(nèi)部阻塞。已有證明，若要完全消除 N X N的 banyan網(wǎng)絡(luò)的內(nèi)部阻塞，至少需要 2㏒ 2N1級。 3）可以增加 banyan網(wǎng)的平面樹，構(gòu)成多通道交換網(wǎng)絡(luò)。 4） 使用排序 banyan網(wǎng)絡(luò)。 解決內(nèi)部阻塞的方法 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 79 該網(wǎng)絡(luò)也簡稱為 BB網(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)成的。 x y min(x,y) max(x,y) x y min(x,y) max(x,y) BATCHERBANYAN網(wǎng)絡(luò) 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 80 BATCHERBANYAN網(wǎng)絡(luò) 011 111 010 100 011 010 100 111 111 100 010 011 BATCHERBANYAN網(wǎng)絡(luò) 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 81 為了減少或消除 banyan的內(nèi)部阻塞，提高吞吐率，除了構(gòu)成 BB網(wǎng)絡(luò)之外，還可以構(gòu)成基于 banyan的的各種多通路網(wǎng)絡(luò)。 （ 1） 增長型 banyan 增長型 banyan就是前面加上分配級，以擴(kuò)大每個入端的選擇范圍，從而形成多通路網(wǎng)絡(luò)。每增加 1級，每個入端與每個出端之間的通路數(shù)就增加 1倍 。 前置分配級還可以使業(yè)務(wù)流均衡地進(jìn)入 banyan的入端，減少 banyan對流入的業(yè)務(wù)流模型的敏感性。 基于 BANYAN的多通路結(jié)構(gòu) 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 82 01 23 45 67 01 2 3 4 5 67 增長型 banyan 增長型 BANYAN 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 83 （ 2） 擴(kuò)展型 banyan 考察 banyan中的交換單元，對應(yīng)于每個交換單元輸出地址有 1條鏈路，如果使每個輸出地址有 d條鏈路，也就是可以任意選擇 d條中的 1條，就稱為擴(kuò)展型 banyan。 在擴(kuò)展型 banyan網(wǎng)中 ， 2 2的交換單元變成了2d 2d的交換單元 。 但輸出地址并非 2d個 ， 而仍然是 2個 ，只要用 1個比特來區(qū)別 。 于是在任何時刻 ， 最多可有 d個信息單元傳送到交換單元的每個輸出；如果對應(yīng)于同一輸出地址同時有多于 d個的信元到達(dá) ， 只能傳送其中的 d個 。 基于 BANYAN的多通路結(jié)構(gòu) 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 84 01 2 3 4 5 67 01 23 45 67 擴(kuò)展型 banyan 擴(kuò)展型 BANYAN 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 85 （ 3） 膨脹型 banyan 膨脹型 banyan是膨脹度 d在各級可以變化的擴(kuò)展型banyan。 （ 4） 復(fù)份型 banyan 復(fù)份型 banyan是將若干個相同的 banyan并接在一起 ，形成多平面的網(wǎng)絡(luò)結(jié)構(gòu) 。 從復(fù)份型 banyan的每個輸入端進(jìn)入的信息單元 ， 可以隨機(jī)地選擇某個平面 ， 也可以按負(fù)荷均分原則分配到各個平面 ， 還可以廣播到所有的平面 。 基于 BANYAN的多通路結(jié)構(gòu) 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 86 01 2 3 4 5 67 01 23 45 67 膨脹型 banyan d=2 d=3 d=4 膨脹型 BANYAN 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 87 Banyan 1 Banyan 2 Banyan r … … … … … … … … … … 1 2 n 1 2 n 復(fù)份型 banyan 復(fù)份型 BANYAN 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 88 benes網(wǎng)絡(luò)是著名的多通路網(wǎng)絡(luò) ， 具有再配置無阻塞的特點(diǎn) 。 可以看出 ， Benes網(wǎng)絡(luò)實(shí)際上相當(dāng)于兩個 banyan（ banyan與反轉(zhuǎn) banyan） 的背對背相連 ， 并將中間相鄰兩級合并為 1級 。 由于每個 banyan有 log2 N級 ， 因此Benes網(wǎng)絡(luò)共有 2log2 N1級 。 benes網(wǎng)絡(luò)的構(gòu)成也有一定的規(guī)律 。 使用 2X2交換單元的 N X N benes網(wǎng)絡(luò)的構(gòu)成方法為：兩側(cè)各有 N/2個 2X2交換單元 ， 中間為兩個 N/2 X N/2的子網(wǎng)絡(luò) ， 每個交換單元以一條鏈路連到每個子網(wǎng)絡(luò)；再將中間子網(wǎng)絡(luò)按上述方法繼續(xù)分解 ， 直到中間子網(wǎng)絡(luò)就是 2X2交換單元為止 。 BENES網(wǎng)絡(luò) 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 89 01 23 45 67 01 2 3 4 5 67 8 X 8 benes網(wǎng)絡(luò) 8 X8 BENES 網(wǎng)絡(luò) 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 90 01 23 45 67 01 2 3 4 5 67 benes網(wǎng)絡(luò)構(gòu)成方法 N/2 X N/2 N/2 X N/2 BENES 網(wǎng)絡(luò)構(gòu)成方法 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 91 作業(yè)（ 1） 有一個 TST交換網(wǎng)絡(luò)，有 8條輸入母線和 8條輸出目線，每條母線為一幀 256個 TS， 其第一級 T接線器為輸入控制方式， S接線器為輸出控制方式，第二級 T接線器為輸出控制方式，請畫圖表示該網(wǎng)絡(luò)將 HW6TS8交換到 HW2TS23的過程（內(nèi)部選定的空閑時隙為 TS15 ），并標(biāo)出各級 SM和 CM的容量及相關(guān)單元內(nèi)容，給出 CP的時間 。 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 92 作業(yè)（ 2） 構(gòu)造 16*16的交換單元：采用基本開關(guān)陣列時，需要 多少個開關(guān)？采用 K=4的繩路開關(guān)陣列時，需要多少個開關(guān)？采用可重排無阻塞網(wǎng)絡(luò)時，需多少個 2*2交叉單元？采用 BANYAN網(wǎng)絡(luò)時，需多少個 2*2交叉單元？采用共享存貯器結(jié)構(gòu)時，至少需 多少個存儲單元。 構(gòu)造 256*256的三級嚴(yán)格無阻塞 CLOS網(wǎng)絡(luò)。要求：入口級選擇 8入線的交換單元，出口級選擇 8出線的交換單元。畫出該網(wǎng)絡(luò)連接示意圖（標(biāo)出各級交換單元的個數(shù)，入出線）。 北京郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 卞佳麗 93 本章小結(jié) 描述交換單元連接特性的方法 交換單元的外部特性描述的描述指標(biāo) 三種典型的交換單元的結(jié)構(gòu)、特性及工作原理 無阻塞網(wǎng)絡(luò)的概念，構(gòu)成無阻塞網(wǎng)絡(luò)的方法 TST、 CLOS、 BANYAN網(wǎng)絡(luò)的結(jié)構(gòu)及特性