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

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

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

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

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

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

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