基于鏈路特征的電力通信網探測選擇算法

茍曉軍，羅順輝，肖 良

(國網信通億力科技有限責任公司北京分公司，北京 100000)

0 引言

隨著5G網絡在各行各業中應用的快速增長，核心網承載的業務類型和規模快速增長。為了保證5G業務的穩定運行，必須對核心網的性能進行實時監測。主動網絡探測技術是網絡性能檢測的一種關鍵技術[1]。需要向網絡中發送探測，并通過探測結果推斷網絡的性能。所以，如何通過盡可能少的探測掌握網絡的性能，已成為一個關鍵的研究問題。已有研究主要包括：探測數據報文的收集和分析，最優化探測選擇。為了實現探測數據報文的收集和分析，Handigol等[2]采用在交換機上部署探測報文流表分析技術，實現了探測報文所經過路徑的快速分析，為探測站點選擇提供了基礎數據支持。Dai等[3]以SDN環境下的探測選擇為研究目標，采取FPGA協議對研究問題進行建模和分析，不但能夠對單條探測進行分析，而且可對并發探測路徑的探測效果進行有效分析。為了選擇最優化的探測，Ali等[4]為解決光網絡中部署探測的問題，分析了單鏈路故障和多鏈路故障兩種情況下的探測選擇問題，并采用預測技術提出了探測選擇算法。Jeswani等[5]以解決網絡動態環境下的探測站點選擇問題為目標，采用周期性的探測站點選擇算法，實現了主動獲取網絡特征的功能。在具體的探測站點優化研究方面，智能算法[6]、模糊分析理論[7]、專家系統[8]等理論也被成功應用到已有研究中，并取得了較好的結果。

在探測數據包分析、探測站點優化方面，已經取得較好的研究成果。但是，在探測選擇時，對探測之間的關聯性分析研究較少，導致探測中出現重復探測現象，給網絡正常運行帶來了負面影響。本研究基于網絡拓撲與探測的關聯關系，構建了探測與節點的貝葉斯模型。創建探測矩陣并基于高斯約旦消元法將探測矩陣化簡為最簡行階梯探測矩陣，提出了基于鏈路特征的電力通信網探測選擇算法，該算法包括：基于鏈路覆蓋關系求解初始探測集合、構建探測矩陣并化簡、基于節點覆蓋的探測數量選擇最優探測節點。

1 模型

1.1 網絡拓撲G

網絡拓撲G是由網絡節點和網絡鏈路構成的無向圖。網絡節點被網絡鏈路連接起來。X={X1，X2，…，Xi}表示節點集合。使用L={L1，L2，…，Lj}表示鏈路集合。兩個網絡節點之間是否有網絡鏈路，由實際網絡運營商的網絡情況決定。20個節點的網絡拓撲如圖1所示。

圖1 20個節點的網絡拓撲舉例

1.2 探測

探測是指從探針節點發送數據包到指定節點所經過的節點和鏈路。使用T={T1，T2，…，Tm}表示由m個探測構成的探測集合。例如，探測1表示為11→12→2→4→6→18。

1.3 探測與節點的貝葉斯模型

為了將探測與網絡關聯，建立探測與節點的貝葉斯模型，包括上下兩層(見圖2)。上層為網絡節點，下層為探測。上下層之間的有向連線表示探測經過的節點。網絡節點和探測都是二進制取值。當取值為1時，表示網絡節點和探測都不正常。當取值為0時，表示網絡節點和探測都正常。當探測正常時，表示當前探測經過的所有節點都正常。否則，表示至少有一個節點不正常。

圖2 探測與節點關系的貝葉斯模型

2 鏈路特征

為了選擇最少的探測，覆蓋所有的網絡節點，從而快速了解網絡性能，下面首先介紹本研究提出的鏈路覆蓋關系概念，其次給出探測矩陣及化簡方法。

2.1 鏈路覆蓋關系

探測的主要用途是覆蓋所有網絡節點。一般來說，探測選擇算法對執行時間都比較敏感。通過分析節點和鏈路的關系可知，如果想讓探測覆蓋節點，只要探測能夠覆蓋經過該節點的鏈路，就可以實現覆蓋當前節點的目標。所以，本研究從覆蓋鏈路的角度出發，進行節點覆蓋，基于鏈路覆蓋關系，可以有效縮短鏈路選擇花費的時間。

對于任意兩點s、d間的路徑Ps，d，其包含的鏈路數量使用Us，d表示，則Us，d=|Ps，d|。使用最短路徑算法Dijkstra可以獲得任意兩個網絡節點之間的最短路徑。所以，將兩點s、d作為探針，采用最短路徑算法Dijkstra獲得的路徑發送探測，就可以對兩點s、d間的鏈路進行覆蓋。任意兩點間最短路徑最長的探測，其覆蓋的鏈路數量最多，該探測的價值越大。所以，在選擇探測時，首先，對所有節點中的任意兩個節點采用最短路徑算法Dijkstra，獲得包含的鏈路數量。其次，按照鏈路數量降序排列，并逐個選擇鏈路數量最多的兩個節點的兩端節點作為探針，將其覆蓋的鏈路標記為已探測，直到所有鏈路已經覆蓋。此種方法選擇的探測數量將快速減少。

2.2 探測矩陣及化簡

基于探測與節點的貝葉斯模型，創建探測矩陣，該矩陣為二維坐標，且矩陣的元素值為二進制0或1。其中，行向量表示每個探測及經過的節點，當探測經過某個節點，該元素為1，否則為0。列向量表示每個節點包含在哪些探測中，如當前節點包含在某個探測中，該元素為1，否則為0。例如，包含6個探測、7個節點的探測矩陣A如公式(1)所示。

(1)

從矩陣的線性變換關系可知，探測矩陣的一些行可以通過其他行進行表示。這種關系對應到探測矩陣的物理意義為：一些探測可以使用其他探測進行代替。所以，如果能找到這些探測之間的代替關系，就可以減少探測的數量。高斯約旦消元法可以通過線性變換，將探測矩陣化簡為最簡行階梯探測矩陣，從而減少探測的數量。在使用高斯約旦消元法時，由于線性變換會導致矩陣元素變為負值，此種情況會導致探測不可用，所以，當某步驟導致矩陣元素出現負值時，高斯約旦消元法不執行此步驟。例如，矩陣A通過變換，可以得到矩陣B。此時，矩陣中的每一行表示一個獨立的探測，探測之間沒有關聯關系，從而大大減少了探測的數量和探測的復雜度。

3 基于鏈路特征的電力通信網探測選擇算法

本研究提出的基于鏈路特征的電力通信網探測選擇算法(Probe selection algorithm of power communication network based on link characteristics，PSA-LC)如表1所示，該算法包括基于鏈路覆蓋關系求解初始探測集合、構建探測矩陣并化簡、基于節點覆蓋的探測數量選擇最優探測節點。

表1 基于鏈路特征的電力通信網探測選擇算法

4 性能分析

實驗中的網絡拓撲環境使用BRITE[9]工具生成。考慮到網絡節點的度數對探測數量影響較大，在生成網絡拓撲時，生成了網絡節點度數平均值為3和6的兩種網絡拓撲。為驗證本研究提出算法PSA-LC的性能，將本研究算法與隨機選擇探測站點算法PSA-RD(Probe selection algorithm based on RanDom)進行了比較。其中，算法PSA-RD是根據網絡規模限制條件隨機從網絡節點中選擇探測節點，直到覆蓋所有節點。在性能分析指標方面，使用探測站點數量和選擇探測站點時長作為評價指標。

兩種算法的探測站點數量比較結果如圖3—4所示，X軸表示網絡節點的數量從100個增加到600個，Y軸表示探測站點的數量。從圖3—4可知，隨著網絡節點數量增加，兩種算法的探測站點數量都在快速增加。這是因為網絡規模增加，需要覆蓋全部網絡節點和網絡鏈路，需要更多的探測站點。對圖3和圖4進行比較可知，圖3中兩種算法選擇的探測站點數量都高于圖4中選擇的探測站點數量。這是因為圖4中網絡拓撲的平均度數加大，從而使網絡鏈路增加，每個探測所經過的網絡節點和網絡鏈路數量增加，所以探測站點的數量都會減少。從兩種算法的探測站點數量比較結果可知，兩種網絡拓撲下，本研究算法PSA-LC的探測站點數量比算法PSA-RD的探測站點數量少，這是因為本研究算法通過鏈路的覆蓋關系，能夠找到比較優化的探測，從而減少重復探測。

圖4 平均度數為6的網絡拓撲的探測站點數量比較

兩種算法的探測選擇時長比較結果如圖5—6所示，X軸表示網絡節點的數量從100個增加到600個，Y軸表示探測選擇時長。可知，隨著網絡節點數量增加，兩種算法的探測選擇時長都在快速增加。這是因為網絡規模增加，需要覆蓋全部網絡節點和網絡鏈路，需要更多的探測選擇過程。對圖5—6進行比較可知，圖5中兩種算法的探測選擇時長都低于圖6中探測選擇時長，因為圖6中網絡拓撲的平均度數加大，從而使網絡鏈路增加，為覆蓋更多的網絡鏈路，兩個算法的探測選擇時長都會增加。兩種網絡拓撲下，本研究算法PSA-LC的探測選擇時長比算法PSA-RD的探測選擇時長要大。這是因為本研究算法PSA-LC需要對探測之間的關系進行分析，導致探測選擇的時間較長。隨著服務器性能和云計算技術的提升，可以通過部署高性能計算環境，解決此問題。

圖5 平均度數為3的網絡拓撲的探測選擇時長比較

圖6 平均度數為6的網絡拓撲的探測選擇時長比較

5 結語

主動網絡探測技術通過向網絡中發送探測，并通過探測結果推斷網絡性能，對網絡性能進行實時監測、保證網絡業務的穩定運行起到非常重要的作用。基于鏈路覆蓋關系降低了鏈路選擇花費的時長，構建了探測與節點的貝葉斯模型。提出了基于鏈路特征的電力通信網探測選擇算法，并且從探測站點數量和選擇探測站點時長兩個方面驗證了算法性能。在網絡設備發生故障時，快速準確地定位故障是保證網絡業務可靠性的關鍵技術。下一步工作中，將基于文章的探測站點選擇成果，對網絡故障定位問題進行深入研究。