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

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

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

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

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

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