李 富，程子敬，李 周，王 瑞

（北京衛(wèi)星信息工程研究所 北京 100086）

為了提高網(wǎng)絡可靠性，交換機連接為環(huán)型拓撲或網(wǎng)狀拓撲，但會形成二層環(huán)路，IEEE STP生成樹協(xié)議[1]通過有選擇性地阻塞網(wǎng)絡冗余鏈路來達到消除網(wǎng)絡二層環(huán)路的目的。但STP導致負載分配不均和瓶頸，尤其在接近根交換機的位置。同時在沒有經(jīng)過優(yōu)化的拓撲結構中，可能會存在較大傳輸時延。所以，良好的網(wǎng)絡拓撲設計是避免網(wǎng)絡時延影響的第一步。

網(wǎng)絡拓撲設計問題作為一個復雜的組合優(yōu)化問題，同樣可歸結為一個NP-hard問題。文獻[2]提出可靠性和成本平衡的拓撲設計方法，但沒有考慮交換機的容量限制。文獻[3]采用遺傳算法來優(yōu)化子網(wǎng)劃分，平衡各個子網(wǎng)的通信負荷。文獻[4]研究了TS（Tabu Search）算法來優(yōu)化交換式網(wǎng)絡。文獻[5]中利用模擬退火（SA）算法作為找到最佳網(wǎng)絡拓撲結構的技術。

文中根據(jù)終端節(jié)點之間的業(yè)務優(yōu)先級及其靜態(tài)流量要求，提出了一種網(wǎng)絡拓撲選擇算法，確定交換機的生成樹拓撲以及終端節(jié)點和交換機的連接關系。該方法對拓撲進行評分，在所有可能的拓撲結構中找到最好的拓撲結構，確定交換機之間的樹型拓撲和終端節(jié)點的分布位置。在網(wǎng)絡拓撲評估中考慮兩條準則：交換機負載均衡，和流量最短路徑選擇。定義兩個系數(shù)α，β分別對應上述準則，根據(jù)目標確定每個準則的權重。算法獨立于上層應用，可以用來保證高優(yōu)先級的業(yè)務流量經(jīng)過最短路徑，同時避免網(wǎng)絡資源的利用不足。同時考慮到可靠性，可以將最好的拓撲進行結合，構造交換機之間的冗余網(wǎng)絡拓撲。

1 網(wǎng)絡模型

將網(wǎng)絡建模為無向圖 G（V，E），其中 V=｛v1，v2，…，vN，…vN+M｝，代表頂點集合，其中頂點{v1，v2，…，vN}對應網(wǎng)絡的終端節(jié)點，{vN+1…vN+M｝對應交換機。 E=｛e1，e2，…，eN，…eN+M-1，｝代表邊集合，其中{e1，e2…eN}對應終端節(jié)點和交換機之間的鏈路，{eN+1，eN+2…eN+M-1}代表交換機之間的鏈路。網(wǎng)絡的節(jié)點和鏈路不發(fā)生故障。

交換機頂點{vN+1…vN+M｝和交換機之間的鏈路{e1，e2，…eM-1}，組成的G的子圖G1，G1的鄰接矩陣Tc=[Tij]有M行和M列，其中

Tc為對稱矩陣。由于生成樹中，邊的數(shù)目為頂點數(shù)目減1，所以Tc中對角線以上非零元素為M-1。

節(jié)點 v1，v2， …，vN和 vN+1， …，vN+M存在著以下連接關系，vi=f（vj）（j=1，2，…，N；i=N+1，N+2，…，N+M），一個終端節(jié)點只能接到一個交換機上。交換機和終端節(jié)點的連接矩陣A=[Aij]有 1 行和 N 列，其中 Aij=vi（i=N+1，N+2，…N+M，j=1，…N），代表第j個終端節(jié)點連接到第i個交換機上。

子圖G1的鄰接矩陣Tc，及交換機和終端節(jié)點的連接矩陣A可確定唯一的網(wǎng)絡拓撲。

2 基于業(yè)務優(yōu)先級和負載均衡的拓撲設計

假設 Ci（i=1，2，…，N）表示第 i個節(jié)點（交換機）的交換能力，以 Gbps 為單位。 Dij（i，j=1，2，...，M，i≠j）表示終端節(jié)點 i和j的流量需求，也就是說，節(jié)點之間的平均用戶流量，Mbps為單位。Pij（i，j=1，2，...，M，i≠j）表示終端節(jié)點 i和 j的流量的優(yōu)先級要求，Pij的取值規(guī)則如下：

Pij值越大，表明從節(jié)點i到節(jié)點j的業(yè)務流量在優(yōu)先級考慮中所占的權重越大。

此外，α，β（0≤α，β≤1，α+β=1）是用戶定義的歸一化參數(shù)，分別代表每條準則的重要性：交換機負載均衡（SLB），和流量最短路徑（SPS）。例如，如果主要考慮交換機負載均衡，令 α=1，β=0，但如果同等考慮 SLB 和 SPS，令 α=β=0.5。

對于每種拓撲結構，在分配流量要求后，可以定義Si（i=1，2，...，N）為第 i個交換機的流量負載，以 Gbps為單位。

其中，path（m，n）表示流量 Dmn經(jīng)過的路徑，交換機負載為經(jīng)過此節(jié)點所有流量之和。

其中，

在SPS標準，其目標是找到一個最低L.的拓撲結構，這樣可以保證高優(yōu)先級的業(yè)務流量沿最短路徑傳輸。

其中 pathcost（i，j）表示業(yè)務流量從節(jié)點 i到節(jié)點 j的交換機數(shù)目。

對于一個具有N個節(jié)點的網(wǎng)絡，算法的輸入?yún)?shù)是流量矩陣 D=Dij，i，j=1，...，N，i≠j，客戶業(yè)務優(yōu)先級矩陣 P=Pij（i，j=1，2，...，M，i≠j），和 α，β（0≤α，β≤1，α+β=1）。

算法如下：

1）M個交換節(jié)點全連接情況下，找到交換節(jié)點的生成樹，并確定其鄰接矩陣 Tc=[Tij]，i，j=1，...，M。

2）根據(jù)Tc，客戶業(yè)務優(yōu)先級矩陣 P，和流量矩陣 D，計算客戶業(yè)務流量的平均路徑長度L，和交換機的負載Si（I=1，2，...，N）。

3）基于SLB和SPS標準，為每種拓撲指定3個參數(shù)Sc1，Sc2

歸一化這些參數(shù)，分別用Sc1，Sc2代表，

4）為SLB和SPS，分別指定系數(shù)α，β，并基于用戶的目標找到最好的樹形拓撲結構。要做到這一點，在第3步中獲得的每個歸一化參數(shù)乘以其相應的系數(shù)，并求和，

這樣可以為所有可能的拓撲結構分級。此處，不考慮所有終端節(jié)點連接到同一臺交換機的情況。選擇得分最高的拓撲，作為最優(yōu)拓撲，確定交換機節(jié)點之間的鄰接矩陣Tc，及交換機和終端節(jié)點的連接矩陣A。

3 計 算

對于N個交換節(jié)點，M個終端節(jié)點的網(wǎng)絡圖G而言，圖G1代表交換節(jié)點的全連接圖，設A是圖G1的關聯(lián)矩陣，G1的生成樹的數(shù)目 t（G1）=det（AAT）[6]。 對于終端節(jié)點 vj（j=1，2，...，M），f（vj）有 N 種取值，則圖 G 的可能拓撲有 t（G）*MN種。當N和M值較大時，拓撲數(shù)量將非常巨大。因此采用遺傳算法進行全局搜索。遺傳算法進行拓撲選擇的主要步驟如下。

1）編碼 劃分為M+1個子區(qū)間，第一個子區(qū)間為交換機的鄰接矩陣，由鄰接矩陣的對角線以上元素組成，其中非零元素個數(shù)為N-1，編碼長度為N*（N-1）/2，隨后為交換機和終端節(jié)點的連接矩陣A，劃分為M個區(qū)間，每個子區(qū)間的取值范圍為 [1，N]，即每臺終端設備可能連接到N臺交換機中的一臺，每個子區(qū)間采用二進制編碼，編碼長度m，使得2m-1≤N-1≤2m-1。一種編碼組合稱之為一條染色體。染色體長度為L=N*（N-1）/2+M*m。

2）初始化種群 設置種群數(shù)目為20，采用隨機初始化的方式，產(chǎn)生20個編碼長度為L的合格染色體。區(qū)間1的編碼要求任意兩點間是連通的，可通過Floyd算法[7]進行驗證。染色體的區(qū)間2到區(qū)間M+1的編碼要求至少有兩個區(qū)間的編碼不相同，即排除所有終端節(jié)點連接到一臺交換機的情況。

3）解碼并鑒別 將染色體解碼并采用線性鑒別模型進行鑒別，轉(zhuǎn)換為真實值。

4）計算適應度 適應度等于目標函數(shù)值Final_score。

5）選擇、交叉、變異 選擇方法采用“輪盤賭”選擇法。交叉概率設定為0.8，采用單點交叉算子，鄰接矩陣作為一個整體其內(nèi)部不進行交叉，隨機交叉位置須在染色體第一個子區(qū)間之后，采用精英主義策略，保留最優(yōu)解。變異概率前2/3繁殖代數(shù)設定為0.4，后1/3繁殖代數(shù)設定為0.1，如果第一個子區(qū)間內(nèi)的基因發(fā)生變異，代表交換機的鄰接矩陣發(fā)生變異，產(chǎn)生一個新的鄰接矩陣。

6）重復 3），4），5）操作至繁殖到 60 代。

7）根據(jù)交換機節(jié)點的鄰接矩陣和交換機和終端節(jié)點的連接矩陣A，確定網(wǎng)絡拓撲。

4 仿真結果

通過MATLAB實現(xiàn)拓撲選擇算法。其輸入?yún)?shù)為一個具有M個終端節(jié)點的網(wǎng)絡流量需求矩陣 D，元素為 Dij，i，j=1，2，...，M，（Dii=0）， 終端節(jié)點間流量優(yōu)先級矩陣 Pij和 α，β（0≤α，β≤1，α+β=1）。 輸出為分級的拓撲。

利用圖1對算法進行說明

圖1 網(wǎng)絡節(jié)點Fig.1 Network element

圖1中有3臺交換機，形成全連接拓撲，交換機的交換容量[C1，C2，C3]=[2Gbps，1.5Gbps，3Gbps]，6 臺終端節(jié)點設備，拓撲選擇算法將確定交換機的生成樹拓撲，并且將6臺終端節(jié)點設備分配到3臺交換機上。給出客戶業(yè)務優(yōu)先級矩陣和終端節(jié)點間的流量需求矩陣：

終端節(jié)點間的流量矩陣為

業(yè)務流量優(yōu)先級矩陣

如果搜索交換機負載均衡最好的拓撲（SLB），則令α=1，β=0，得分最高的Tc及A如下：

交換機和終端節(jié)點的連接矩陣 A=[s3，s2，s3，s1，s2，s3]，（s1，s2，s3分別代表3臺交換機）

網(wǎng)絡拓撲如圖2所示。

圖2 基于SLB的最優(yōu)拓撲Fig.2 Best topology based on SLB

如果搜索業(yè)務流量平均路徑長度最短的拓撲 （SPS），則令α=0，β=1，目標是尋找具有最小L的拓撲，得分最高的Tc及A如下：

交換機和終端節(jié)點的連接矩陣 A=[s1，s3，s3，s1，s1，s3]，（s1，s2，s3分別代表3臺交換機）

拓撲如圖3所示。

圖3 基于SPS的最優(yōu)拓撲Fig.3 Best topology based on SPS

搜索過程中，交換機負載方差σ2s的最大值為0.246 56，最小值為9.63E-05。流量的平均路徑代價L最大值為3，最小值為1?？梢姡煌耐負湓O計對參數(shù)的影響差異較大。

表1對比了基于SPS和SLB標準的拓撲中的交換機負載方差（σ2s）和流量的平均路徑代價（L）?？梢钥吹剑琒LB的交換機負載平衡性能優(yōu)于SPS，SPS業(yè)務流量的平均路徑長度小于SLB中的路徑長度。

表1 基于SLB和SPS的拓撲性能比較Tab.1 Perform ance com parion of topology based on SLB and SPS

拓撲設計中，可綜合考慮交換機負載平衡性能和業(yè)務流量的平均路徑長度這兩條準則，確定合適的α，β，平衡兩方面性能。

5 結 論

文中引入了一個新的圖論方法，定義了兩個準則：交換機負載平衡、流量最短路徑以及對應于上述兩個準則的系數(shù)。首先，根據(jù)設計目標確定α，β的值，再利用業(yè)務流量優(yōu)先級矩陣和靜態(tài)流量需求矩陣作為輸入，對所有可能的網(wǎng)絡拓撲結構分級。設計具體的遺傳算法時，利用交換機連接的鄰接矩陣和終端節(jié)點和交換機的連接矩陣作為染色體，搜索全局最優(yōu)拓撲。該算法獨立于上層應用，避免了個別交換機負載過重，同時保證高優(yōu)先級流量能夠沿最短路徑傳輸。航天器進行網(wǎng)絡拓撲設計時，可綜合考慮兩條準則，尋找最優(yōu)的拓撲或者對已設計的拓撲進行比較選擇，確定航天器內(nèi)交換機和終端設備的分布。

[1]IEEE Std 802.1W 2001.Media Access Control （MAC）Bridges Amendment 2：Rapid Reconfiguration[S].2001.

[2]Estepa，Rafael.A Productivity-Based Approach to LAN Topology Design[J].IEEE Communications Letters，2011，15（3）：349-351.

[3]胡曉婭，朱德森，汪秉文.用改進的遺傳算法設計交換式工業(yè)以太網(wǎng)拓撲[J].計算機工程與科學，2007，29（9）:9-11.HU Xiao-ya，ZHU De-sen，WANG Bing-wen.Using improved genetic algorithms to design switched industrial Ethernet topology[J].Computer Engineering&Science，2007，29（9）:9-11.

[4]Pierre，S，Elgibaoui A.Improving communication network topologies using tabu search[M].Local Computer Networks，1997.

[5]Deeter D L，Smith A E.Heuristic optimization of network designconsidering all terminal reliability[C]//Proceedings of the Reliability andMaintainability Symposium，1997:194-199.

[6]陳勇，胡愛群.通信網(wǎng)中最重要節(jié)點的確定方法[J].高技術通訊，2004，14（1）:21-24.CHEN Yong，HU Ai-qun.A method for finding the most vital node in communication networks[J].Chinese High Technology Letters，2004，14（1）：21-24.

[7]劉煥淋，陳勇.通信網(wǎng)圖論及應用[M].北京：人民郵電出版社，2010.