融合多維特征的ISP網絡拓撲匹配優化仿真

高雅娟，王玉峰

(中國礦業大學銀川學院，寧夏 銀川 750021)

1 引言

ISP發展之初，將接入服務作為主體，進行ISP網絡拓撲匹配優化，可以實現對網絡的維護，匯聚鄰近節點，避免設備之間的異構性與不兼容性，從而給用戶制造穩定安全的網絡環境，但是緩解網絡壓力程度較低。

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

上述優化方法雖然一定程度上緩解拓撲不匹配問題，但是沒有構建明確的拓撲性能評價指標，無法精確衡量拓撲一致性。基于此，本文融合多維特征對ISP網絡拓撲匹配進行優化。其創新之處在于構建合理性能評價指標，對ISP網絡無向圖進行多維特性分析，融合多維特征，通過節點加入、退出、失效等過程，使匹配程度達到最大化，實現網絡拓撲匹配優化。

2 ISP網絡拓撲匹配優化性能指標構建

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

(1)

式中，n代表網絡中節點數量，i與j為節點排列序號，0≤i，j

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

2.1 全局拓撲匹配比定義

GTMR用于描述鏈路匹配程度，其描述不同網絡中相互匹配的鏈路數量和總鏈路數量的比值，表達式如下

(2)

2.2 鄰居節點準確度定義

LNA值鄰居節點之間的匹配比例，關系式如下所示

(3)

圖1 不同鄰居節點集合關系示意圖

假設h=1，表示統計節點的1跳鄰居節點的準確度。此時整個網絡中LNAi為1的節點數量與覆蓋網絡節點數量的比值情況通過下述表達式獲取

(4)

式中，n為節點總數量，n≤i

3 融合多維特性的ISP網絡拓撲匹配優化

3.1 多維特性分析

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

1)譜密度

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

(5)

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

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

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

2)無符號拉普拉斯譜

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

|L|=D+A

(6)

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

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

3)規格化拉普拉斯譜

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

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

(7)

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

3.2 匹配優化算法實現

對上述三個多維特征進行融合，利用面向測量的方式，優化網絡拓撲匹配。優化算法的實現主要包括新節點加入、節點失效與退出三個部分。

圖2 優化方法框架圖

3.2.1 節點加入

(8)

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

1)網絡成本歸一化度量

將節點距離當作網絡成本度量。若節點nodem+1和節點nodei發生連接，其中i∈{1，2，…，m}。兩個節點構建的連接成本歸一化度量表示為mDi。

則mDi度量越大，構建鏈路所花費的成本越小。

2)網絡時延歸一化度量

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

3)網絡健壯性歸一化度量

將網絡遭到一定威脅后仍然正常傳輸的流量當作健壯性度量。在nodem+1和nodei兩個節點發生連接后，網絡受到隨機攻擊或惡意攻擊后仍可以進行正常通信的節點占比情況表示為ri，節點nodem+1與nodei的網絡健壯性歸一化度量表示為mRi，歸一化度量越高，網絡越健壯。

4)網絡吞吐量歸一化度量

將網絡臨界數據出現率作為吞吐量度量。假設在節點nodem+1與nodei建立聯系后，網絡吞吐量用ti表示，則兩個節點連接的吞吐量歸一化度量為mTi。此時，該度量越大吞吐量越高。

5)連接判斷度量measure

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

measure=wDmDi+wHmHi+wRmRi+wTmTi

stwD+wH+wR+wT=1

(9)

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

圖3 節點加入算法

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

3.2.2 節點退出

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

3.2.3 節點失效

若節點發生失效情況，該節點不能將消息傳輸給父節點與子節點。此時，需要通過廣播方式將消息傳送到其它節點。假設失效節點是葉子節點，利用發現節點把失效信息傳遞給父節點；當失效節點不屬于葉子節點時，將失效節點全部子節點退出，使其重新回到網絡中。以此完成了ISP網絡拓撲匹配優化。

4 仿真研究

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

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

表1 不同方法優化結果對比表

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

節點消耗個數對比結果如圖4所示。

圖4 不同優化算法維護開銷對比圖

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

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

圖5 不同方法拓撲匹配比測試結果

由圖5可知，本文方法的節點返回個數一直高于其它文獻方法，說明本文方法優化后，網絡拓撲不匹配現象減弱，可完成對節點位置優劣、流量傳輸效率、網絡延時、靈敏度等高要求的業務。

5 結論

為改善ISP網絡拓撲不匹配缺陷，本文利用融合多維特征方法對其進行匹配優化。得出如下結論：

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

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

3)通過新節點加入、節點退出和節點失效操作實現拓撲匹配優化的目的。可完成高靈敏度、高要求的網絡業務。