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

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

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

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

5、撲結構都是一樣的，則稱此網絡為對稱網絡。線性陣列一種一維的線性網絡，其中N個結點用N-1個鏈路連成一行。內部結點度為2，端結點度為1，直徑為N-1，等分寬度b=1。環用一條附加鏈路將線性陣列的兩個端點連接起來而構成的。可以單向工作，也可以雙向工作。它是對稱的，結點度是常數2。雙向環的直徑為N/2，單向環的直徑是N。帶弦環在環的基礎上，給每個結點增加一條或兩條鏈路。增加的鏈路愈多，結點度愈高，網絡直徑就愈小。全連接網絡一種環網。其中任何兩個結點之間都有鏈路相連。循環移數網絡通過在環上每個結點到所有與其距離為2的整數冪的結點之間都增加一條附加鏈而構成的。這就是說，如果j-i=2 r，r=0,1,2,n-1，網絡規模N=2n，則結點i與結點j連接。這種循環移數網絡的結點度為d=2n-1，直徑D=n/2。超立方體一種二元n立方體結構。一般說來，一個n立方體由N=