高雅娟，王玉峰

(中國礦業(yè)大學(xué)銀川學(xué)院，寧夏 銀川 750021)

1 引言

ISP發(fā)展之初，將接入服務(wù)作為主體，進行ISP網(wǎng)絡(luò)拓撲匹配優(yōu)化，可以實現(xiàn)對網(wǎng)絡(luò)的維護，匯聚鄰近節(jié)點，避免設(shè)備之間的異構(gòu)性與不兼容性，從而給用戶制造穩(wěn)定安全的網(wǎng)絡(luò)環(huán)境，但是緩解網(wǎng)絡(luò)壓力程度較低。

針對上述問題，相關(guān)研究人員給出如下解決方案。文獻[1]在粒子群優(yōu)化基礎(chǔ)上實現(xiàn)網(wǎng)絡(luò)拓撲匹配的優(yōu)化。該算法結(jié)合SDN方法將全局網(wǎng)絡(luò)拓撲數(shù)據(jù)進行可視化處理，利用粒子群優(yōu)化，結(jié)合所處網(wǎng)絡(luò)鏈路資源狀態(tài)等數(shù)據(jù)，將通過最小優(yōu)化獲取鏈路最大利用率為目標進行全局優(yōu)先匹配。實驗證明該方法能有效加強網(wǎng)絡(luò)吞吐量。文獻[2]利用最優(yōu)子網(wǎng)的虛擬網(wǎng)絡(luò)映射算法，對滿足約束條件的虛擬節(jié)點進行合并，通過廣度優(yōu)先搜索方法構(gòu)建子網(wǎng)集合，達到粗化網(wǎng)絡(luò)拓撲目的，并將粗化后的虛擬網(wǎng)絡(luò)映射到最佳子網(wǎng)絡(luò)中。這種方法可以減少鏈路映射跳數(shù)，提高網(wǎng)絡(luò)請求接受率。文獻[3]基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)，在反饋過程中計算AC值，利用鄰接矩陣作為反饋路徑，提出一種可達中心性算法，更準確、有效地識別出重要節(jié)點。

上述優(yōu)化方法雖然一定程度上緩解拓撲不匹配問題，但是沒有構(gòu)建明確的拓撲性能評價指標，無法精確衡量拓撲一致性?；诖?，本文融合多維特征對ISP網(wǎng)絡(luò)拓撲匹配進行優(yōu)化。其創(chuàng)新之處在于構(gòu)建合理性能評價指標，對ISP網(wǎng)絡(luò)無向圖進行多維特性分析，融合多維特征，通過節(jié)點加入、退出、失效等過程，使匹配程度達到最大化，實現(xiàn)網(wǎng)絡(luò)拓撲匹配優(yōu)化。

2 ISP網(wǎng)絡(luò)拓撲匹配優(yōu)化性能指標構(gòu)建

現(xiàn)階段，覆蓋網(wǎng)絡(luò)和拓撲匹配程度的指標主要指伸縮比。其中常用的是路徑伸縮比(PS)與時延伸縮比(LS)。文本通過時延伸縮比表達網(wǎng)絡(luò)拓撲匹配程度，其公式如下

(1)

式中，n代表網(wǎng)絡(luò)中節(jié)點數(shù)量，i與j為節(jié)點排列序號，0≤i，j

LS主要表示網(wǎng)絡(luò)時延方面的匹配程度，只能大概的進行反映，無法得到拓撲匹配的詳細特征[4]，因此精準度較低。但是拓撲結(jié)構(gòu)的匹配度對于網(wǎng)絡(luò)結(jié)構(gòu)的改變與優(yōu)化起到關(guān)鍵作用，如果可以獲得局部匹配特征，不但能提高LS，還能改善整個ISP網(wǎng)絡(luò)的QOS。因此，本文對全局拓撲匹配比GTMR與局部鄰居節(jié)點準確度LNA兩個指標進行定義，從而更準確的得到拓撲匹配的詳細信息。

2.1 全局拓撲匹配比定義

GTMR用于描述鏈路匹配程度，其描述不同網(wǎng)絡(luò)中相互匹配的鏈路數(shù)量和總鏈路數(shù)量的比值，表達式如下

(2)

2.2 鄰居節(jié)點準確度定義

LNA值鄰居節(jié)點之間的匹配比例，關(guān)系式如下所示

(3)

圖1 不同鄰居節(jié)點集合關(guān)系示意圖

假設(shè)h=1，表示統(tǒng)計節(jié)點的1跳鄰居節(jié)點的準確度。此時整個網(wǎng)絡(luò)中LNAi為1的節(jié)點數(shù)量與覆蓋網(wǎng)絡(luò)節(jié)點數(shù)量的比值情況通過下述表達式獲取

(4)

式中，n為節(jié)點總數(shù)量，n≤i

3 融合多維特性的ISP網(wǎng)絡(luò)拓撲匹配優(yōu)化

3.1 多維特性分析

本文利用無向圖G對多維特征進行分析，G能夠通過對稱鄰接矩陣A代表[6]。G中的i與j節(jié)點之間存在邊關(guān)聯(lián)性，則Aij=Aji=1，反之Aij=0，Aji=0。一個圖的特征值其實是它的鄰接矩陣特征值，因此分析多維特性對優(yōu)化網(wǎng)路拓撲匹配具有重要價值。

1)譜密度

無向圖G的譜其實為該圖鄰接矩陣A的特征密度值[7]，通常表示為ρ(λ)。很對有限系統(tǒng)來說，ρ(λ)能夠描述為有關(guān)特征值的δ函數(shù)之和

(5)

假設(shè)N→∞時，它收斂于一個連續(xù)函數(shù)，這時λi表示此無向圖的鄰接矩陣特性值中第i個特征值。譜密度能夠描述特征值的分布規(guī)律。

現(xiàn)有研究成果說明ER隨機圖的譜密度呈半圓狀，并且底邊區(qū)域呈指數(shù)分布。而無標度圖的譜密度呈對稱連續(xù)函數(shù)，此函數(shù)的中間部分為三角形，兩邊為冪律分布。

上述分析表明，ISP拓撲圖不是ER隨機圖，其屬于一種無標度圖，但又不滿足BA模型的分布。

2)無符號拉普拉斯譜

無向圖G的無符號拉普拉斯矩陣|L|的定義式為

|L|=D+A

(6)

式中，D為G的節(jié)點度對角矩陣，A為鄰接矩陣。無符號拉普拉斯譜(SLS)即為|L|特征集合。結(jié)合代數(shù)圖原理說明，在單位矩陣的所有線性組合里，無符號拉普拉斯譜是劃分不同類型圖效果最顯著的譜，同樣表明，SLS可以描述拓撲性質(zhì)。

SLS的分布特征值為降序排列，λi的排列順序按照(i-1)(N-1)進行規(guī)格化處理[8]。其中，N表示節(jié)點數(shù)量，雖然子圖之間規(guī)模與平均度不盡相同，但是SLS分布情況非常相似，特征值為1的概率都很高，且尾重特性及其相似。通過冪律擬合結(jié)果得出，所有子圖中全部高于1的特征值和排列順序之間均滿足冪律分布規(guī)則，特征指數(shù)較為相近。

3)規(guī)格化拉普拉斯譜

無向圖G的規(guī)格化拉普拉斯譜(NLS)矩陣L的定義式為

L=D-1/2×L×D-1/2

(7)

式中，L為G的拉普拉斯矩陣，L=D-A，D與A具有相同含義。NLS屬于L的特征集合，經(jīng)過規(guī)格化的拉普拉斯特征值區(qū)間為[0，2]，按照升序排列結(jié)果為：λ1≤λ2≤…≤λN。NLS的分布特征比較相似，均呈三個臺階狀分布，并且重數(shù)相對大的特征值位置大致相同。

3.2 匹配優(yōu)化算法實現(xiàn)

對上述三個多維特征進行融合，利用面向測量的方式，優(yōu)化網(wǎng)絡(luò)拓撲匹配。優(yōu)化算法的實現(xiàn)主要包括新節(jié)點加入、節(jié)點失效與退出三個部分。

圖2 優(yōu)化方法框架圖

3.2.1 節(jié)點加入

(8)

根據(jù)上述條件，判斷出新加入節(jié)點需要符合如下連接條件：

1)網(wǎng)絡(luò)成本歸一化度量

將節(jié)點距離當作網(wǎng)絡(luò)成本度量。若節(jié)點nodem+1和節(jié)點nodei發(fā)生連接，其中i∈{1，2，…，m}。兩個節(jié)點構(gòu)建的連接成本歸一化度量表示為mDi。

則mDi度量越大，構(gòu)建鏈路所花費的成本越小。

2)網(wǎng)絡(luò)時延歸一化度量

將平均最短路徑距離當作時延度量。如果有節(jié)點nodem+1與節(jié)點nodei存在連接時，且i∈{1，2，…，m}。在連接建立后，網(wǎng)絡(luò)時延表示為hi，兩個節(jié)點構(gòu)建的時延歸一化度量為mHi。此時度量值mHi越大，網(wǎng)絡(luò)時延越小。

3)網(wǎng)絡(luò)健壯性歸一化度量

將網(wǎng)絡(luò)遭到一定威脅后仍然正常傳輸?shù)牧髁慨斪鹘研远攘?。在nodem+1和nodei兩個節(jié)點發(fā)生連接后，網(wǎng)絡(luò)受到隨機攻擊或惡意攻擊后仍可以進行正常通信的節(jié)點占比情況表示為ri，節(jié)點nodem+1與nodei的網(wǎng)絡(luò)健壯性歸一化度量表示為mRi，歸一化度量越高，網(wǎng)絡(luò)越健壯。

4)網(wǎng)絡(luò)吞吐量歸一化度量

將網(wǎng)絡(luò)臨界數(shù)據(jù)出現(xiàn)率作為吞吐量度量。假設(shè)在節(jié)點nodem+1與nodei建立聯(lián)系后，網(wǎng)絡(luò)吞吐量用ti表示，則兩個節(jié)點連接的吞吐量歸一化度量為mTi。此時，該度量越大吞吐量越高。

5)連接判斷度量measure

如果在優(yōu)化過程中成本權(quán)重、時延權(quán)重、健壯性權(quán)重與吞吐量權(quán)重分別表示為：wD、wH、wR與wT，因此新加入節(jié)點nodem+1和存在最大連接度量measure并且沒有構(gòu)建鏈路的節(jié)點i建立新鏈路。假設(shè)此時出現(xiàn)很多節(jié)點均滿足該條件，需要隨機挑選一個備用節(jié)點與新加入節(jié)點構(gòu)建連接。其中

measure=wDmDi+wHmHi+wRmRi+wTmTi

stwD+wH+wR+wT=1

(9)

其中，wD∈[0，1]，wH∈[0，1]，wR∈[0，1]，wT∈[0，1]。

圖3 節(jié)點加入算法

其中DR存在動態(tài)變化性質(zhì)，在算法初始化過程中，DR=R，此時建立上圖中(a)所示的示意圖；在DR發(fā)生改變時，需要對J與新產(chǎn)生的DR以及子節(jié)點存在的關(guān)系進行判斷，結(jié)合三角形邊長關(guān)系，可以得到三種節(jié)點跳數(shù)發(fā)生的處理情況，從而確定最佳父節(jié)點添加到網(wǎng)絡(luò)中。

3.2.2 節(jié)點退出

為確保整個ISP網(wǎng)絡(luò)中節(jié)點之間的兼容性、貫通性，維護鄰居關(guān)系和層次關(guān)系，并且降低網(wǎng)絡(luò)拓撲的維護成本，把需要退出節(jié)點的父節(jié)點設(shè)為動態(tài)根節(jié)點形式。在網(wǎng)絡(luò)節(jié)點退出過程中，必須對其子節(jié)點與父節(jié)點做合理調(diào)整。假如退出的節(jié)點為葉子節(jié)點，需要將退出消息發(fā)送到父節(jié)點，之后直接退出即可；假設(shè)不屬于葉子節(jié)點，此時需要先將退出消息傳送給父節(jié)點，并且找到更佳的節(jié)點代替該父節(jié)點。

3.2.3 節(jié)點失效

若節(jié)點發(fā)生失效情況，該節(jié)點不能將消息傳輸給父節(jié)點與子節(jié)點。此時，需要通過廣播方式將消息傳送到其它節(jié)點。假設(shè)失效節(jié)點是葉子節(jié)點，利用發(fā)現(xiàn)節(jié)點把失效信息傳遞給父節(jié)點；當失效節(jié)點不屬于葉子節(jié)點時，將失效節(jié)點全部子節(jié)點退出，使其重新回到網(wǎng)絡(luò)中。以此完成了ISP網(wǎng)絡(luò)拓撲匹配優(yōu)化。

4 仿真研究

為驗證所提方法的合理性，本文利用BRITE拓撲生成器形成六個不相同規(guī)模的網(wǎng)絡(luò)拓撲：{100，200，400，800，1600，3200}，節(jié)點最小度設(shè)為3，且位置符合隨機分布條件。仿真中，將本文方法與文獻[1]、文獻[2]、文獻[3]方法進行對比，以鄰居節(jié)點準確度最大值、節(jié)點消耗個數(shù)與全局拓撲匹配比作為評價指標。

鄰居節(jié)點準確度最大值對比測試獲得的實驗結(jié)果如表1所示：

表1 不同方法優(yōu)化結(jié)果對比表

從表1中可以看出，本文方法網(wǎng)絡(luò)拓撲的LAN值匹配程度均高于其它文獻方法。在節(jié)點數(shù)量沒有超過800時，本文方法和對比方法最大值相差不大，但是超過800時，獲得的最大值差距明顯。因此在ISP網(wǎng)絡(luò)中，本文算法拓撲匹配優(yōu)化算法性能更佳。

節(jié)點消耗個數(shù)對比結(jié)果如圖4所示。

圖4 不同優(yōu)化算法維護開銷對比圖

從圖4中可以看出本文優(yōu)化算法對網(wǎng)絡(luò)的維護開銷低于其它文獻方法，其中，本文方法在節(jié)點規(guī)模為3200時的維護代價最高，為2.3N，而其它文獻方法分別為2.5N、3.2N和4.1N，最高差可達1.8，說明本文方法對節(jié)點的利用效率較高。

全局拓撲匹配比對比測試結(jié)果如圖5所示。

圖5 不同方法拓撲匹配比測試結(jié)果

由圖5可知，本文方法的節(jié)點返回個數(shù)一直高于其它文獻方法，說明本文方法優(yōu)化后，網(wǎng)絡(luò)拓撲不匹配現(xiàn)象減弱，可完成對節(jié)點位置優(yōu)劣、流量傳輸效率、網(wǎng)絡(luò)延時、靈敏度等高要求的業(yè)務(wù)。

5 結(jié)論

為改善ISP網(wǎng)絡(luò)拓撲不匹配缺陷，本文利用融合多維特征方法對其進行匹配優(yōu)化。得出如下結(jié)論：

1)根據(jù)時延伸縮比表達網(wǎng)絡(luò)拓撲匹配程度，構(gòu)建性能評價指標，在節(jié)點規(guī)模為3200時的維護代價最高，為2.3N，與其它方法最高差可達1.8，對節(jié)點的利用效率高達99%，滿足ISP網(wǎng)絡(luò)拓撲匹配需求，

2)在構(gòu)建性能評價指標后，對多維特征進行分析，強化多維特征，在節(jié)點數(shù)量超過800時，獲得的最大值差距明顯，節(jié)省了維護開銷，均衡節(jié)點負載，適用于ISP網(wǎng)絡(luò)。

3)通過新節(jié)點加入、節(jié)點退出和節(jié)點失效操作實現(xiàn)拓撲匹配優(yōu)化的目的?？赏瓿筛哽`敏度、高要求的網(wǎng)絡(luò)業(yè)務(wù)。