茍曉軍，羅順輝，肖 良

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

0 引言

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

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

1 模型

1.1 網(wǎng)絡拓撲G

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

圖1 20個節(jié)點的網(wǎng)絡拓撲舉例

1.2 探測

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

1.3 探測與節(jié)點的貝葉斯模型

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

圖2 探測與節(jié)點關系的貝葉斯模型

2 鏈路特征

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

2.1 鏈路覆蓋關系

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

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

2.2 探測矩陣及化簡

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

(1)

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

3 基于鏈路特征的電力通信網(wǎng)探測選擇算法

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

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

4 性能分析

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

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

圖4 平均度數(shù)為6的網(wǎng)絡拓撲的探測站點數(shù)量比較

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

圖5 平均度數(shù)為3的網(wǎng)絡拓撲的探測選擇時長比較

圖6 平均度數(shù)為6的網(wǎng)絡拓撲的探測選擇時長比較

5 結語

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