第7章互連網(wǎng)絡(luò)

1、第7章 互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)一種由開(kāi)關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用來(lái)實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)中結(jié)點(diǎn)之間的相互連接。這些結(jié)點(diǎn)可以是處理器、存儲(chǔ)模塊或其他設(shè)備。線(xiàn)路交換源結(jié)點(diǎn)和目的結(jié)點(diǎn)之間的物理通路在整個(gè)數(shù)據(jù)傳送期間一直保持連接。分組交換把信息分割成許多組（又稱(chēng)為包），將它們分別送入互連網(wǎng)絡(luò)。這些數(shù)據(jù)包可以通過(guò)不同的路徑傳送，到目的結(jié)點(diǎn)后再拼合出原來(lái)的數(shù)據(jù)。在分組交換中，結(jié)點(diǎn)之間不存在固定連接的物理通路。集中控制方式集中控制方式中，有一個(gè)全局的控制器接收所有的通信請(qǐng)求，并由它設(shè)置互連網(wǎng)絡(luò)的開(kāi)關(guān)連接。分散控制方式分散控制方式中，不存在全局的控制器，通信請(qǐng)求的處理和開(kāi)關(guān)的設(shè)置由互連網(wǎng)絡(luò)分散地進(jìn)行。

2、靜態(tài)拓?fù)浣Y(jié)構(gòu)在各結(jié)點(diǎn)之間有專(zhuān)用的連接通路，且在運(yùn)行過(guò)程中不能改變。動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)根據(jù)需要設(shè)置互連網(wǎng)絡(luò)中的開(kāi)關(guān)，從而對(duì)結(jié)點(diǎn)之間的連接通路進(jìn)行重新組合，實(shí)現(xiàn)所要求的通信模式?；ミB函數(shù)用變量x表示輸入（設(shè)x=0，1，N1），用函數(shù)f(x)表示輸出，通過(guò)數(shù)學(xué)表達(dá)式建立輸入端與輸出端的一一對(duì)應(yīng)關(guān)系。即在互連函數(shù)f的作用下，輸入端x連接到輸出端f(x)。也稱(chēng)為置換函數(shù)或排列函數(shù)。循環(huán)互連函數(shù)f(x)有時(shí)可以采用循環(huán)表示，即：（x0 x1 x2 xj-1）。它表示f(x0)=x1，f(x1)=x2，f(xj-1)=x0j稱(chēng)為該循環(huán)的長(zhǎng)度。交換函數(shù)實(shí)現(xiàn)二進(jìn)制地址編碼中第k位互反的輸入端與輸出端之間的連接。其表達(dá)

3、式為均勻洗牌函數(shù)將輸入端分成數(shù)目相等的兩半，前一半和后一半按類(lèi)似均勻混洗撲克牌的方式交叉地連接到輸出端（輸出端相當(dāng)于混洗的結(jié)果）。其函數(shù)關(guān)系可表示為 即把輸入端的二進(jìn)制編號(hào)循環(huán)左移一位。逆均勻洗牌函數(shù)將輸入端的二進(jìn)制編號(hào)循環(huán)右移一位而得到所連接的輸出端編號(hào)。其互連函數(shù)為逆均勻洗牌是均勻洗牌的逆函數(shù)。蝶式互連函數(shù)把輸入端的二進(jìn)制編號(hào)的最高位與最低位互換位置，便得到了輸出端的編號(hào)。定義為反位序函數(shù)將輸入端二進(jìn)制編號(hào)的位序顛倒過(guò)來(lái)求得相應(yīng)輸出端的編號(hào)。其互連函數(shù)為PM2I函數(shù)一種移數(shù)函數(shù)，它是將各輸入端都循環(huán)移動(dòng)一定的位置連到輸出端。其函數(shù)為PM2+i (x) x2i mod NPM2-i(x) x

4、2i mod N 其中，0xN1，0in1，nlog2N，N為結(jié)點(diǎn)數(shù)。網(wǎng)絡(luò)規(guī)模一般說(shuō)來(lái)，網(wǎng)絡(luò)用圖來(lái)表示。這種圖由用有向邊或無(wú)向邊連接的有限個(gè)結(jié)點(diǎn)構(gòu)成。其結(jié)點(diǎn)數(shù)稱(chēng)為網(wǎng)絡(luò)規(guī)模。結(jié)點(diǎn)度與結(jié)點(diǎn)相連接的邊的數(shù)目。入度在單向通道的情況下，進(jìn)入結(jié)點(diǎn)的通道數(shù)。出度在單向通道的情況下，從結(jié)點(diǎn)出來(lái)的通道數(shù)。距離對(duì)于網(wǎng)絡(luò)中的任意兩個(gè)結(jié)點(diǎn)，從一個(gè)結(jié)點(diǎn)出發(fā)到另一個(gè)結(jié)點(diǎn)終止所需要跨越的邊數(shù)的最小值。網(wǎng)絡(luò)直徑網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)間最短路徑長(zhǎng)度的最大值。等分寬度在將某一網(wǎng)絡(luò)切成相等兩半的各種切法中，沿切口的最小通道邊數(shù)。結(jié)點(diǎn)之間的線(xiàn)長(zhǎng)兩個(gè)結(jié)點(diǎn)之間連線(xiàn)的長(zhǎng)度，用米、千米等表示。對(duì)稱(chēng)網(wǎng)絡(luò)對(duì)于一個(gè)網(wǎng)絡(luò)，如果從其中的任何一個(gè)結(jié)點(diǎn)看，拓

5、撲結(jié)構(gòu)都是一樣的，則稱(chēng)此網(wǎng)絡(luò)為對(duì)稱(chēng)網(wǎng)絡(luò)。線(xiàn)性陣列一種一維的線(xiàn)性網(wǎng)絡(luò)，其中N個(gè)結(jié)點(diǎn)用N-1個(gè)鏈路連成一行。內(nèi)部結(jié)點(diǎn)度為2，端結(jié)點(diǎn)度為1，直徑為N-1，等分寬度b=1。環(huán)用一條附加鏈路將線(xiàn)性陣列的兩個(gè)端點(diǎn)連接起來(lái)而構(gòu)成的?？梢詥蜗蚬ぷ鳎部梢噪p向工作。它是對(duì)稱(chēng)的，結(jié)點(diǎn)度是常數(shù)2。雙向環(huán)的直徑為N/2，單向環(huán)的直徑是N。帶弦環(huán)在環(huán)的基礎(chǔ)上，給每個(gè)結(jié)點(diǎn)增加一條或兩條鏈路。增加的鏈路愈多，結(jié)點(diǎn)度愈高，網(wǎng)絡(luò)直徑就愈小。全連接網(wǎng)絡(luò)一種環(huán)網(wǎng)。其中任何兩個(gè)結(jié)點(diǎn)之間都有鏈路相連。循環(huán)移數(shù)網(wǎng)絡(luò)通過(guò)在環(huán)上每個(gè)結(jié)點(diǎn)到所有與其距離為2的整數(shù)冪的結(jié)點(diǎn)之間都增加一條附加鏈而構(gòu)成的。這就是說(shuō)，如果j-i=2 r，r=0,1,2,n-1，網(wǎng)絡(luò)規(guī)模N=2n，則結(jié)點(diǎn)i與結(jié)點(diǎn)j連接。這種循環(huán)移數(shù)網(wǎng)絡(luò)的結(jié)點(diǎn)度為d=2n-1，直徑D=n/2。超立方體一種二元n立方體結(jié)構(gòu)。一般說(shuō)來(lái)，一個(gè)n立方體由N=