網絡基礎設施中重要網元子圖的確定

劉 崢,郭舒婷,周綺鳳,李 濤

(1.南京郵電大學計算機學院,江蘇 南京 210023;2.江蘇省大數據安全與智能處理重點實驗室,江蘇 南京 210023;3.廈門大學航天航空學院,福建 廈門 361005)

目前,現代大規模復雜網絡基礎設施的日常運維往往依賴于集中式網絡監控平臺和人工干預來保證網絡服務的可靠性[1-2].重要網元的監視和管理對保障網絡服務的可靠性至關重要.網元的重要性往往由網絡管理員根據經驗來判斷,然而在網絡基礎設施規模日益增大和網絡管理人力資源有限的背景下,對于承載重要業務的網元相對較易確定,而對于處于網絡基礎設施拓撲結構中的重要節點的判斷卻很難由人工判定,常常出現錯誤及遺漏.

網絡基礎設施中面向業務的網元子圖是指網絡基礎設施中承載具體業務的重要網元的拓撲子圖,也包括其他非重要網元.通過確定面向業務的網元子圖,可以滿足大規模網絡基礎設施中運維需求,僅需投入較少人力對這些拓撲子圖中的網元進行重點監控,就可以提高故障分析的效率,節省網絡基礎設施運維的成本.目前在網絡基礎設施運維中并沒有成熟的網元子圖的確定方法,傳統的方法是從發生故障的網元出發,將其鄰域網元所組成的子圖作為網元子圖.

在社交網絡研究領域,已經有一些學者對節點的影響力進行了研究,并將高影響力的節點作為重要節點.Kempe等[3]研究了影響最大化問題,集中介紹了描述節點激活行為的模型.Leskovec等[4]提出一種高性價比的懶惰前向(cost-effective lazy forward,CELF)貪心算法的優化策略,運用獨立級聯型的次模特性(sub-modularity),大大降低了選擇最具影響力節點的工作次數.此外,Lei等[5]提出了一個能夠在市場病毒式營銷中學習到傳播概率的方法.Farajtabar等[6]通過對社會活動進行建模,構建了一個凸優化框架確定激勵用戶刺激社交活動所需的活動水平.但這些社交網絡中的影響力評估算法著重關注社交網絡中信息的傳播模型,而不是故障傳播模型,并不適用于評估網絡技術設施中網元的影響力.在圖數據挖掘的研究領域中,已經有一些學者提出了一些節點之間關系的度量方法.Jeh等[7]提出了一種通過節點鄰域的相似性來度量節點之間的相似度的方法,稱為SimRank,表征從兩個節點出發的隨機游走的期望相遇距離.Palmer等[8]定義了一個距離函數來衡量兩個屬性數據集之間的相似度,用圖模型來表示屬性值,兩個屬性值之間的距離定義為重啟隨機游走的逃逸概率.但這些重要性的度量方法都沒有考慮到網絡基礎設施中網元重要性的特點,沒有將重要節點的鄰域節點進行深入分析.此外,由于拓撲結構和承載業務兩者的異構性,也不能直接利用上述方法度量網元的重要性.另一方面重要網元子圖的確定與社交網絡研究領域中的社區發現有一定相似.目前,對圖上的社區發現算法主要包括:基于譜分析的聚類算法[9],基于圖劃分的聚類算法[10],基于層次的聚類算法[11]以及基于密度的聚類算法[12].Liu等[13]搜索網絡中的極大團,并依據其連接情況合并極大團來獲得網絡的社區結構.Pons等[14]提出利用長度為l的隨機游走來度量圖上兩個節點的相似度用于社區發現.Tong等[15]也提出了利用重啟隨機游走在圖數據上發現中心子圖.但社交網絡中的社區發現偏重于尋找社交網絡中的相似節點的集合,而不是根據節點的影響力來判斷節點的影響范圍.

為了同時考慮網元連接關系的重要性和承載業務的重要性,本研究將業務轉換為圖模型上的點,利用鄰域影響度來衡量網元之間(圖上節點之間)的連接關系,并由此評估節點的重要性.識別重要節點后,根據其重要性衡量標準,將確定網元子圖的問題變成一個在圖上對節點進行分組的問題.為此,本文中提出了一個3步的框架來識別重要網元子圖:

1) 評估網元節點的重要性,尋找重要的網元節點;

2) 從每個重要網元節點出發,根據節點之間的相關性,生成網元重要子圖;

3) 融合網元重要子圖,形成網元重要子圖集合.

1 評估網元節點的重要性

為了同時考慮網元連接關系的重要性和承載業務的重要性,首先需要弄清重要網元的特征.從大規模復雜網絡運維實際出發,網元的重要性主要體現在以下兩方面:1) 重要網元與其他網元的直接連接或間接連接的關系較密切,體現在重要網元與其他網元之間的連通路徑較多,一旦重要網元發生故障,可能會影響其他網元之間的通信或服務交互.2) 重要網元所承載的業務的數量較多,級別也較高.一旦重要網元發生故障,會影響到承載同樣業務的其他網元服務的穩定性.

根據重要網元的特征，本研究將業務轉換為圖模型上的節點,再利用鄰域影響度捕捉節點的連接關系,進而將連接關系的重要性和承載業務的重要性統一起來.本文中的網絡基礎設施用圖模型G=〈V，E〉表示,其中V是所有網元節點vi所組成的集合,E表示網元之間連接關系的集合,即圖上兩個節點之間的邊ei的集合.

對于用圖模型G表示的網絡基礎設施,令A表示有權重圖的鄰接矩陣.A(i,j)表示邊eij=(vi,vj)上的權重.基于隨機游走的概念,在圖G上的影響力擴散是指從某一節點v0出發,并按一定概率在圖上沿節點和邊隨機移動.假設目前第vs步的隨機游走在節點s+1上,則第s+1步將以概率Pst移動到vs的某一相鄰節點vt上,即vt∈N(vs),其中N(vs)表示節點vs在圖G上的所有相鄰節點的集合,其轉移概率Pst=A(s,t)/∑vk∈N(vs)A(s,k),所經過的節點路徑組成一個馬爾科夫鏈.令D表示一個對角矩陣,其中對角線上某個值d(s)=∑vk∈N(vs)A(s,k),則對應的馬爾科夫鏈的轉移概率矩陣P的矩陣表示為P=D-1A.從節點vj到節點vk的長度為l的概率Qjk可以通過轉移矩陣P經過l次乘積后相應位置上的對應元素來表示,故Q=(Qjk)=Pl.

當G為非二項圖時,由于馬爾科夫鏈的無記憶性,從任何節點出發,經過無限步的影響度最后落在同一個節點vk的概率只和最終節點的度的大小有關.可以通過返回概率c,將影響度傾向于在出發節點的周圍的局部的連接關系,同時只考慮長度為l的隨機游走,即鄰域影響度所能達到的節點與出發的節點的最短路徑長度不超過l.值得注意的是,本文中提出的算法可以根據不同需要自由地增大l以擴大鄰域的范圍.

定義1鄰域影響度:若隨機游走的長度為l,則節點vj到節點vk的鄰域影響度(影響力)為

其中,0

由此可知鄰域影響度的矩陣可表示為:

(1)

根據鄰域影響度(影響力)矩陣,重要網元節點的重要性可定義為

S(vj)=∑vk∈VΠjk,

(2)

其中,重要性分值S(vj)表示節點vj的影響力.是根據重要節點對其他節點的影響力,即鄰域影響度長度的總和來決定.

式(2)定義網絡基礎設施圖模型G上的重要性,為了同時考慮承載業務的重要性,本文中提出將業務也轉換為圖模型上的點,如圖1所示.假設網絡基礎設施中的業務有{w1,w2,w3,…}.每種業務wj在圖上都映射相應的節點wj.如果某網元承載某業務,則在圖上增加連接網元對應節點vi到業務對于節點wj的一條邊e(vi,wj).這樣生成的包括業務信息的圖模型用G′表示.在圖G′上利用鄰域影響度來統一衡量節點的重要性,可同時衡量連接關系的重要性和關于業務的重要性.對于業務的級別,可以通過給邊e(vi,wj)賦予相應的權重,為簡化描述,本文中假設所有業務級別都一樣,即相應的邊的權重為1.下文中將不區分G′和G,兩者都表示包括業務信息的圖模型.

圖1 業務轉化為圖上的節點Fig.1 Service vertices in the graph

網元節點重要性評估算法步驟為:

1) 計算轉移概率矩陣P.將業務轉化為圖上業務節點,利用圖上網元節點的鄰接關系和網元承載業務情況得到鄰接矩陣A,根據P=D-1A計算轉移概率矩陣P.

2) 計算影響力距離矩陣Π.設置合適的隨機游走長度l和隨機游走的重啟概率c,根據式(1) 計算Π.

3) 根據式(2) 計算網元節點的重要性分值.

4) 生成重要網元節點列表.重要性分值大于ξ的網元節點稱為重要節點,其中ξ表示重要網元節點重要性的閾值.圖2所示的是基于本文中實驗部分數據集的網絡基礎設施圖G上的網元重要性的分布情況.通過對網元節點影響力的曲線擬合,可見網元節點影響力分布曲線與冪律分布函數y=1.72x-0.06-1的曲線基本吻合,遵循冪律(power law)分布,因此確定重要節點的重要性的閾值ξ并不是絕對的,而是相對的.在下文3.2節對ξ的取值進行了討論.

圖2 網元節點影響力分布曲線Fig.2 The curve of vertex influence distribution

由于評估節點重要性需要對兩個矩陣進行乘積,所以整體的時間復雜度是O(ln3),其中n是圖中的網元個數.在實際應用中,可以利用快速稀疏矩陣乘法來代替通常的矩陣相乘算法以加快計算速度.

2 生成重要網元子圖

重要網元子圖應包括重要網元節點和與重要網元節點相似度較大的節點,即被重要節點影響大的節點,有如下幾個特點:1) 重要網元子圖應該是一個連通圖;2) 重要網元子圖應該包括重要節點;3) 重要網元子圖應該包括被重要節點影響的節點.

本文中提出了一個類似高維空間中密度聚類思想的擴展策略,從重要網元節點擴展出網元子圖.生成重要網元子圖的算法步驟如下:

1) 從重要網元節點列表中選擇當前重要性分值最大的網元vj,初始化子圖gs為空,并將該網元插入到空節點圖中,從重要網元節點列表中刪除vj,標記vj為已訪問節點,設置子圖擴展的停止條件閾值ε,計算公式為:

ε=max(Π(j,∶))×rlb，

其中rlb的取值為冪律分布曲線的拐點位置.

2) 初始化最大堆H,將所有未被訪問過的重要網元vj的相鄰節點vm和影響力值Πjm插入到最大堆H中.

3) 從最大堆H的堆頂獲取當前影響力最大值節點vk和其影響力值,若該影響力值大于閾值ε,將所有未被訪問過的vk的相鄰節點vm和影響力值Πkm插入到最大堆H中,同時將vk加入到圖gs中,標記vk為已訪問,如果節點vk是重要網元,更新閾值ε,更新公式為:

ε=max(Π(k,∶))×rlb.

重復步驟3),若該影響力值小于閾值ε,則將當前生成的子圖gs加入到重要網元子圖集合Gs中;若重要網元節點列表不為空,返回步驟1);否則進行步驟4).

4) 融合重要網元子圖.遍歷重要網元子圖集合Gs,若兩個重要網元子圖存在節點在原圖上是直接相連的,將兩個網元子圖合并成一個網元子圖.

生成重要網元子圖的算法從重要網元節點出發,通過擴展重要網元來生成重要網元子圖.步驟2)和3)使用最大堆來維持影響力大的節點,每次從最大堆H中取出第一個節點加入到當前的重要網元子圖gs中.檢查是否結束當前重要網元子圖gs的擴展的判斷條件是當前網元子圖gs中的所有節點對待擴展節點的影響力是否小于閾值ε.閾值ε為最后加入到網元子圖的重要節點對圖上其他節點的影響力的最大值的rlb倍.由于影響力距離遵循冪律分布,rlb的取值為冪律分布曲線的拐點位置,在本文中根據實驗中的具體冪律分布情況,rlb的值為0.2.在步驟4)中,對于生成的重要網元子圖集合,如果兩個重要網元子圖存在節點在原圖上是直接相連的,那么這兩個網元子圖將被合并成一個網元子圖.

3 實驗結果與分析

本文中實驗所使用的運行環境為OS X 10.10.5,CPU為Intel i5 1.6 GHz,內存為4 GB,算法的實現基于Python語言.在所有實驗中,使用的隨機游走的返回概率為0.15.

3.1 數據集

本研究在數據集SNAP1N、SNAP1U、SNAP2N、SNAP2U上進行實驗.這4個數據集由數據集SNAP1和SNAP2生成，數據集SNAP1和SNAP2均來源于俄勒岡大學路由查看計劃,來自Stanford大學的SNAP項目(https:∥snap.stanford.edu/data/).兩個數據集的基本特征如表1所示.

表1 數據集特征

數據集中每個節點代表一個自治系統(如路由),自治系統之間的通信遵循邊界網關協議,基于邊界網關協議的日志消息可以構建自治系統之間的通信網絡拓撲圖.由于SNAP1和SNAP2中并沒有網元所承載的業務信息,本研究中在其上疊加了合成的業務數據.假設有100種不同的業務,對于每個節點,允許其承載10個不同的業務,承載的業務的數量有均勻分布和正態分布兩種情況.隨機地從100種業務中選擇某節點所承載的具體業務.通過對SNAP1和SNAP2疊加兩種不同的業務分布,共生成4個不同的數據集供實驗中使用,后文用SNAP1U、SNAP1N、SNAP2U、SNAP2N表示.其中,SNAP1U表示在SNAP1上疊加均勻分布的業務數量,SNAP1N表示在SNAP1上疊加正態分布的業務數量.SNAP2的表示與之類似.

3.2 有效性

首先介紹如何衡量重要網元子圖的質量.對于確定的某重要網元子圖Gs,可以利用式(3)來衡量重要網元子圖的質量：

(3)

其中Π是影響力矩陣.∑vj,vk∈V(Gs),score(vj)≥ξΠjk表示重要網元子圖內節點之間的影響力,∑vj∈V(Gs),vk∈V(G),score(vj)≥ξΠjk衡量了重要網元子圖內的重要節點到子圖內其他節點的影響力,Rcoverage值越高,說明重要網元子圖內捕捉到大部分重要節點的影響力越大.

圖3顯示了在數據集SNAP1U和SNAP1N上，對于不同的ξ找到的前10個重要網元子圖的Rcoverage的算術平均值.對于每個ξ,變化鄰域影響度的長度為2～6.當隨機游走的長度為2時,Rcoverage的算術平均值在兩個數據集上都只有0.3左右,這是因為長度為2的隨機游走在圖上所能訪問范圍過小,不足以捕捉重要節點的影響力.當隨機游走的長度超過3時,發現兩個數據集上的Rcoverage的算術平均值都超過70%,例如對于長度為5,ξ為85%時,重要網元子圖內的重要節點的影響力超過85%都在子圖內部.

圖3 數據集SNAP1U和SNAP1N的RcoverageFig.3 Rcoverage of dataset SNAP1U and SNAP1N

圖中數值表示網元的編號,下同.圖4 數據集SNAP1U和SNAP1N的重要網元子圖示例Fig.4 An element subgraph of dataset SNAP1U and SNAP1N

圖4展示了分別在數據集SNAP1U和SNAP1N上找到的重要網元子圖,其中隨機游走的長度為4,ξ為85%，灰色節點表示重要網元子圖中的重要節點.可見,找到的重要網元子圖里包括相當部分的重要節點,也包括與重要節點相連的非重要節點.尋找網元子圖的傳統方法是從同一時間窗口內的每個故障網元出發,以每個故障網元為中心,尋找與其路徑距離小于h的網元節點.將故障網元以及這些故障網元的鄰接網元節點所構成的子圖作為此故障網元的鄰域子圖，即為重要網元子圖.同一時間窗口內的故障網元鄰域子圖如有重合,即包含相同節點,則把重合的鄰域子圖合并.圖5展示了在數據集SNAP1U和SNAP1N上利用傳統的方法找到的與圖4對應的網元子圖,即包括發生故障網元的鄰域子圖,其中鄰域子圖中的節點到發生故障節點的路徑長度為2.可見,傳統方法找到的網元子圖包括的節點遠遠多于本文中所找到的重要網元子圖中的節點,會極大地增加運維人員的負擔.

3.3 運行時間

圖5 數據集SNAP1U和SNAP1N的傳統網元子圖示例Fig.5 An element subgraph of dataset SNAP1U and SNAP1N

圖6 數據集的運行時間Fig.6 The running time on datasets

本研究在4個數據集上都進行了運行時間的實驗,其中隨機游走的長度為4和6,ξ為85%.圖6顯示了在SNAP1U、SNAP1N、SNAP2U、SNAP2N的運行時間,包括長度為4和6的隨機游走.運行時間分兩部分,分別對應評估網元節點的重要性和生成重要網元子圖.其中,SNAP1U和SNAP1N的實驗結果對應左邊的坐標縱軸,SNAP2U和SNAP2N的實驗結果對應右邊的坐標縱軸.由于評估網元重要性算法的時間復雜度為O(ln3),所以評估網元節點重要性所需的時間隨l的增加而增加.生成重要網元子圖算法是一個啟發式的算法,其時間復雜度與重要節點的個數以及重要節點的影響范圍有關,但l的變化會影響重要節點的個數,所以生成重要網元算法的時間也會隨l的變化而變化.由于生成重要網元子圖中要頻繁更新最大堆中所對應的影響力值,其時間復雜度為O(logm),其中m是最大堆里的元素個數,所以擴展生成重要網元子圖的時間相對較長.

為了衡量算法的時間復雜度,本研究中分別選取不同節點數,在數據集SNAP2N上進行實驗.圖7顯示了在不同大小的圖上算法的運行時間,其中隨機游走的長度為4,ξ為85%.可見,隨著節點數量的增加,計算網元重要性算法和生成重要網元子圖算法的運行時間符合上面的復雜度分析,整體上呈多項式時間增長.當節點數為2 000時，生成重要網元子圖步驟的變化也反映了啟發式算法的啟發策略對整體運行時間的影響.

4 結 論

快速而準確地確定重要網元子圖可以用于提高網絡基礎設施的運維效率,降低運維成本.本研究的主要貢獻:1) 針對在大規模網絡基礎設施中確定面向業務的重要網元子圖的問題,提出利用鄰域影響度來統一衡量網元在連接和業務兩方面的重要性;2) 給出了確定重要網元子圖的算法,利用類似密度聚類的思想,通過擴展重要網元生成重要網元子圖;3) 在真實的網絡基礎設施數據集上,通過疊加合成的業務承載數據進行了廣泛的實驗,實驗結果驗證了提出的方法可以高效地找到高質量的重要網元子圖,并將其用于網絡基礎設施的運維.未來可能的研究方向包括利用其他影響力模型來構建重要網元子圖,以及在動態網絡基礎設施中如何維護所發現的重要網元子圖等.