基于負載均衡和流量優先級的網絡拓撲設計

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

（北京衛星信息工程研究所 北京 100086）

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

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

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

1 網絡模型

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

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

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

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

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

2 基于業務優先級和負載均衡的拓撲設計

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

Pij值越大，表明從節點i到節點j的業務流量在優先級考慮中所占的權重越大。

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

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

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

其中，

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

其中 pathcost（i，j）表示業務流量從節點 i到節點 j的交換機數目。

對于一個具有N個節點的網絡，算法的輸入參數是流量矩陣 D=Dij，i，j=1，...，N，i≠j，客戶業務優先級矩陣 P=Pij（i，j=1，2，...，M，i≠j），和 α，β（0≤α，β≤1，α+β=1）。

算法如下：

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

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

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

歸一化這些參數，分別用Sc1，Sc2代表，

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

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

3 計 算

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

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

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

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

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

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

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

7）根據交換機節點的鄰接矩陣和交換機和終端節點的連接矩陣A，確定網絡拓撲。

4 仿真結果

通過MATLAB實現拓撲選擇算法。其輸入參數為一個具有M個終端節點的網絡流量需求矩陣 D，元素為 Dij，i，j=1，2，...，M，（Dii=0）， 終端節點間流量優先級矩陣 Pij和 α，β（0≤α，β≤1，α+β=1）。 輸出為分級的拓撲。

利用圖1對算法進行說明

圖1 網絡節點Fig.1 Network element

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

終端節點間的流量矩陣為

業務流量優先級矩陣

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

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

網絡拓撲如圖2所示。

圖2 基于SLB的最優拓撲Fig.2 Best topology based on SLB

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

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

拓撲如圖3所示。

圖3 基于SPS的最優拓撲Fig.3 Best topology based on SPS

搜索過程中，交換機負載方差σ2s的最大值為0.246 56，最小值為9.63E-05。流量的平均路徑代價L最大值為3，最小值為1。可見，不同的拓撲設計對參數的影響差異較大。

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

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

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

5 結 論

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

[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]胡曉婭，朱德森，汪秉文.用改進的遺傳算法設計交換式工業以太網拓撲[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]陳勇，胡愛群.通信網中最重要節點的確定方法[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]劉煥淋，陳勇.通信網圖論及應用[M].北京：人民郵電出版社，2010.