基于負(fù)載均衡和流量優(yōu)先級(jí)的網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)

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

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

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

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

文中根據(jù)終端節(jié)點(diǎn)之間的業(yè)務(wù)優(yōu)先級(jí)及其靜態(tài)流量要求，提出了一種網(wǎng)絡(luò)拓?fù)溥x擇算法，確定交換機(jī)的生成樹拓?fù)湟约敖K端節(jié)點(diǎn)和交換機(jī)的連接關(guān)系。該方法對(duì)拓?fù)溥M(jìn)行評(píng)分，在所有可能的拓?fù)浣Y(jié)構(gòu)中找到最好的拓?fù)浣Y(jié)構(gòu)，確定交換機(jī)之間的樹型拓?fù)浜徒K端節(jié)點(diǎn)的分布位置。在網(wǎng)絡(luò)拓?fù)湓u(píng)估中考慮兩條準(zhǔn)則：交換機(jī)負(fù)載均衡，和流量最短路徑選擇。定義兩個(gè)系數(shù)α，β分別對(duì)應(yīng)上述準(zhǔn)則，根據(jù)目標(biāo)確定每個(gè)準(zhǔn)則的權(quán)重。算法獨(dú)立于上層應(yīng)用，可以用來保證高優(yōu)先級(jí)的業(yè)務(wù)流量經(jīng)過最短路徑，同時(shí)避免網(wǎng)絡(luò)資源的利用不足。同時(shí)考慮到可靠性，可以將最好的拓?fù)溥M(jìn)行結(jié)合，構(gòu)造交換機(jī)之間的冗余網(wǎng)絡(luò)拓?fù)洹?/p>

1 網(wǎng)絡(luò)模型

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

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

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

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

子圖G1的鄰接矩陣Tc，及交換機(jī)和終端節(jié)點(diǎn)的連接矩陣A可確定唯一的網(wǎng)絡(luò)拓?fù)洹?/p>

2 基于業(yè)務(wù)優(yōu)先級(jí)和負(fù)載均衡的拓?fù)湓O(shè)計(jì)

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

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

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

對(duì)于每種拓?fù)浣Y(jié)構(gòu)，在分配流量要求后，可以定義Si（i=1，2，...，N）為第 i個(gè)交換機(jī)的流量負(fù)載，以 Gbps為單位。

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

其中，

在SPS標(biāo)準(zhǔn)，其目標(biāo)是找到一個(gè)最低L.的拓?fù)浣Y(jié)構(gòu)，這樣可以保證高優(yōu)先級(jí)的業(yè)務(wù)流量沿最短路徑傳輸。

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

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

算法如下：

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

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

3）基于SLB和SPS標(biāo)準(zhǔn)，為每種拓?fù)渲付?個(gè)參數(shù)Sc1，Sc2

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

4）為SLB和SPS，分別指定系數(shù)α，β，并基于用戶的目標(biāo)找到最好的樹形拓?fù)浣Y(jié)構(gòu)。要做到這一點(diǎn)，在第3步中獲得的每個(gè)歸一化參數(shù)乘以其相應(yīng)的系數(shù)，并求和，

這樣可以為所有可能的拓?fù)浣Y(jié)構(gòu)分級(jí)。此處，不考慮所有終端節(jié)點(diǎn)連接到同一臺(tái)交換機(jī)的情況。選擇得分最高的拓?fù)?，作為最?yōu)拓?fù)?，確定交換機(jī)節(jié)點(diǎn)之間的鄰接矩陣Tc，及交換機(jī)和終端節(jié)點(diǎn)的連接矩陣A。

3 計(jì) 算

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

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

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

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

4）計(jì)算適應(yīng)度 適應(yīng)度等于目標(biāo)函數(shù)值Final_score。

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

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

7）根據(jù)交換機(jī)節(jié)點(diǎn)的鄰接矩陣和交換機(jī)和終端節(jié)點(diǎn)的連接矩陣A，確定網(wǎng)絡(luò)拓?fù)洹?/p>

4 仿真結(jié)果

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

利用圖1對(duì)算法進(jìn)行說明

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

圖1中有3臺(tái)交換機(jī)，形成全連接拓?fù)洌粨Q機(jī)的交換容量[C1，C2，C3]=[2Gbps，1.5Gbps，3Gbps]，6 臺(tái)終端節(jié)點(diǎn)設(shè)備，拓?fù)溥x擇算法將確定交換機(jī)的生成樹拓?fù)?，并且?臺(tái)終端節(jié)點(diǎn)設(shè)備分配到3臺(tái)交換機(jī)上。給出客戶業(yè)務(wù)優(yōu)先級(jí)矩陣和終端節(jié)點(diǎn)間的流量需求矩陣：

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

業(yè)務(wù)流量優(yōu)先級(jí)矩陣

如果搜索交換機(jī)負(fù)載均衡最好的拓?fù)洌⊿LB），則令α=1，β=0，得分最高的Tc及A如下：

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

網(wǎng)絡(luò)拓?fù)淙鐖D2所示。

圖2 基于SLB的最優(yōu)拓?fù)銯ig.2 Best topology based on SLB

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

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

拓?fù)淙鐖D3所示。

圖3 基于SPS的最優(yōu)拓?fù)銯ig.3 Best topology based on SPS

搜索過程中，交換機(jī)負(fù)載方差σ2s的最大值為0.246 56，最小值為9.63E-05。流量的平均路徑代價(jià)L最大值為3，最小值為1。可見，不同的拓?fù)湓O(shè)計(jì)對(duì)參數(shù)的影響差異較大。

表1對(duì)比了基于SPS和SLB標(biāo)準(zhǔn)的拓?fù)渲械慕粨Q機(jī)負(fù)載方差（σ2s）和流量的平均路徑代價(jià)（L）?？梢钥吹?，SLB的交換機(jī)負(fù)載平衡性能優(yōu)于SPS，SPS業(yè)務(wù)流量的平均路徑長度小于SLB中的路徑長度。

表1 基于SLB和SPS的拓?fù)湫阅鼙容^Tab.1 Perform ance com parion of topology based on SLB and SPS

拓?fù)湓O(shè)計(jì)中，可綜合考慮交換機(jī)負(fù)載平衡性能和業(yè)務(wù)流量的平均路徑長度這兩條準(zhǔn)則，確定合適的α，β，平衡兩方面性能。

5 結(jié) 論

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

[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ìn)的遺傳算法設(shè)計(jì)交換式工業(yè)以太網(wǎng)拓?fù)鋄J].計(jì)算機(jī)工程與科學(xué)，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é)點(diǎn)的確定方法[J].高技術(shù)通訊，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)圖論及應(yīng)用[M].北京：人民郵電出版社，2010.