Clos網(wǎng)絡和Gamma網(wǎng)絡的連接特性研究（附：關于Kautz網(wǎng)絡均勻同態(tài)問題的初步探討）.pdf

1、上海交通大學碩士學位論文Clos網(wǎng)絡和Gamma網(wǎng)絡的連接特性研究（附：關于Kautz網(wǎng)絡均勻同態(tài)問題的初步探討）姓名：程亮申請學位級別：碩士專業(yè)：應用數(shù)學指導教師：李喬2003.1.1上海交通大學碩士學位論文CClos在1953年最早給出了數(shù)學理論證明，可以通過精巧的安排設計出不阻塞網(wǎng)絡來實現(xiàn)所有可能的連接請求，即嚴格不阻塞的3級交換網(wǎng)絡，它比使用專用線路的網(wǎng)絡可大大減少硬件的開銷。關于不阻塞交換網(wǎng)絡的數(shù)學理論，近年出版了專著TheM

2、athematicalTheoryofNonblockingSwitchingNetworksbyFrankKHwang(黃光明)》(WorldScientific，1998)[1]。本文在第一章介紹Clos網(wǎng)絡以及嚴格不阻塞、廣義不阻塞、可重排不阻塞的基本概念，并介紹3級Clos網(wǎng)絡嚴格不阻塞和可重排不阻塞的充要條件及其證明：在第二章中引申出4級Clos網(wǎng)絡的概念，并給出定義，同時證明4級Clos網(wǎng)絡嚴格不阻塞的充分必要條件與可重排不

3、阻塞的一個充分條件。第二章的內(nèi)容是我們得出的關于Clos網(wǎng)絡的結果，除了理論方面的意義，這些結果也為實際的網(wǎng)絡應用提供了一些選擇。曠＼／二Ga嗍a網(wǎng)絡的路由置換問題／Gamma網(wǎng)絡[9]是另～種重要的交換網(wǎng)絡，主要應用在多處理器系統(tǒng)中，用承處理器～處理器或處理器一存儲器之間的連接。|Ⅳ個輸入和Ⅳ個輸出的Gamma網(wǎng)絡由n1級組成，每一級上有Ⅳ個交換器，這里N=2“。除了第一級和最后一級，Gamma網(wǎng)絡每一級上的交換元件都是33的。Gam

4、ma網(wǎng)絡第一級(輸入級)上的元件是l3的，最后～級上的元件是31的。Gamma網(wǎng)絡的結構可以用有向圖G∽)來表示：把每個交換器看成頂點，把連接兩個交換器的線路看成是連接代表這兩個交換器的頂點的邊。G(n)=(y，E)可以形式的定義如下：V是n1個互不相交集合的并，V2VouVIu礦2uu。其中所=v：，v：，，v；一l，i=o，l，2，，N，Ⅳ=2”。G(”)的有向邊集E=EouEluE2uu厶。，，B是從巧到“】的(有向)邊集(i=O

5、，1，2，，n一1)。當i=O，1，2，，n一1時，r_，、、西2砂jx=哆，Y∈杉“，噶剛礦y噶剛∥t)；，=o，1，，Ⅳ一1，其中rood”(Ⅲ)表示整數(shù)m除以Ⅳ的余數(shù)。Gamma網(wǎng)絡一般不具有不阻塞性。1999年，EhabSElmalah和Chin—HungLam提出了Gamma網(wǎng)絡的下述路由置換問題[10]：對給定的NXN(N個輸入和Ⅳ個輸出)的Gamma網(wǎng)絡，當給定Ⅳ個輸入和Ⅳ個輸出之間的任意一個黃換丌時，是否有一個多項式時間

6、復雜度的算法來判定置換丌在Gamma網(wǎng)絡中能否實現(xiàn)(即是否有Ⅳ條邊不交路連接這些輸入和對應的輸出)這個問題至今仍末解決。本文將在第三章中介紹Gamma網(wǎng)絡的應用背景、基本概念和基本性質(zhì)。在第四章中先給出Gamma網(wǎng)絡路由置換問題的定義，接下來證明Ⅳ=4的Gamma網(wǎng)絡能實現(xiàn)所有可能的置換。在第四章接下來的章節(jié)里(從43開始)首先分析Gamma網(wǎng)絡的路由“階梯”圖，得到“階梯”圖的兩個重要性質(zhì)，由此得到基本性質(zhì)：NXN的Gamma網(wǎng)絡中最