多域網絡邏輯拓撲布局算法研究

賈百韜，艾中良

(華北計算技術研究所，北京 100083)

多域網絡邏輯拓撲布局算法研究

賈百韜，艾中良

(華北計算技術研究所，北京 100083)

網絡空間態勢可視化已經成為網絡空間態勢信息綜合與分析的重要環節，在態勢可視化中網絡邏輯拓撲的布局生成技術也得到了越來越多的關注。本文針對網絡邏輯拓撲結構復雜、多域的特點，結合層級布局、力導引布局等圖布局算法，提出了一種針對網絡空間態勢邏輯拓撲數據的布局生成算法。經過實驗驗證，該算法能夠完成多域網絡邏輯拓撲的自動布局，并保證布局的清晰、合理。

態勢可視化；拓撲生成；層級布局；力導引

本文著錄格式：賈百韜，艾中良. 多域網絡邏輯拓撲布局算法研究[J]. 軟件，2017，38（1）：93-97

0 引言

網絡空間態勢感知技術已經成為網絡空間信息分析的一種重要手段，作為網絡空間態勢感知信息的最直接體現，網絡空間態勢可視化能夠將網絡空間中獲取的態勢信息經過處理后，以直觀、清晰的方式加以展示[1]。

而網絡空間態勢數據中涉及大量邏輯空間數據，如自治域或業務系統的內網拓撲數據等。從網絡管理與分析人員的角度來說，內網中每一個網絡節點的經緯度位置并不重要，網絡節點的漏洞、軟件、開啟服務等屬性信息和節點之間的連接關系、協議、帶寬、業務域劃分等才是最重要的[2]。這些網絡邏輯數據的展現方式，將影響著網絡分析人員對邏輯域態勢的掌握。

因此，對于網絡邏輯拓撲數據，需要可視化處理過程支持邏輯視圖的顯示。而對于網絡拓撲，也需要針對網絡信息分析的業務需要，對不同網絡節點、網絡屬性進行描述，對不同網絡業務區域進行層級化處理，支持拓撲的分區顯示[3]。并面向用戶的邏輯視圖查看和操作習慣進行拓撲布局生成計算等處理，保證自動生成的邏輯拓撲布局符合節點連接關系，并保證連線與連線不交迭、節點與節點不重合，各節點排版布局要合理、美觀，整體拓撲圖形要符合用戶的理解。

本論文將研究現有的圖布局算法，并在此基礎上設計多域網絡邏輯拓撲布局算法，該算法可以對網絡空間態勢感知過程中獲取的復雜網絡邏輯數據進行處理，自動生成網絡邏輯拓撲布局，并保證布局效果正確合理，符合用戶的視覺要求。

1 圖布局算法研究

傳統的圖布局算法有樹形布局算法、層級布局算法等，這些算法比較適用于規模相對較小的圖拓撲結構[4]。由Fruchterman和Reingold提出的力導引（Force-Directed）布局算法可以計算圖中節點間相互的斥力，迭代地調整節點位置，以達到最理想的布局效果[5]。力導引布局算法及其改進算法多用于節點規模大，節點關系復雜的情況。

1.1 層級布局算法

層級布局算法基于圖的深度屬性，將根節點作為布局的頂層，根節點的一級子節點作為第二層布局，并以此類推，最終形成樹狀結構。

對于節點關系復雜的圖布局，當圖結構中出現環路時，節點的深度并不是唯一，這就造成布局混亂，節點連線交叉。而且如果節點數量規模巨大，可能出現某一層的節點數量特別多，影響布局效果。

由于網絡邏輯拓撲中很少出現拓撲環路的情況，所以當網絡設備節點較少時，可以使用層級布局算法進行處理。

對于任意節點v，所占二維空間最小為：

對于一個待處理的節點集合，遍歷集合中的每一個節點，以根節點為基準，可以計算出每個節點v的縱坐標偏移量：

其中f為該節點層數。

對于葉子節點v，由于其不存在子節點，所以所占橫坐標空間為：

而對于非葉子節點v，其所占橫坐標空間為子節點橫坐標空間之和,遞歸計算公式為：

其中Nchild為節點v子節點的個數。

因此，根節點所占的橫坐標空間即為整體網絡拓撲布局的寬，所以整體布局范圍為：

此時，每個圖元節點處于自身所在空間范圍的中心點，并根據子節點調整橫向偏移量。如下圖所示，為6個節點、深度為3的樹結構使用層級布局算法處理后生成的布局結果視圖。

圖1 層級布局算法處理生成的邏輯拓撲結構

1.2 力導引布局算法

力導引布局算法多用于節點規模大，節點關系復雜的情況。

FR算法是在Eades經典彈簧算法的基礎上，使用力引導模型進行處理。FR算法的每次遞歸分為三個部分：首先是計算節點與節點之間的排斥力，然后是計算圖結構中有邊連接的節點與節點之間的吸引力，最后綜合處理吸引力與排斥力，并通過限制最大位移來控制節點的偏移距離[6]。

對于一個高度為H，寬度為W的區域，任意節點v都存在兩個布局參數：節點的位置pos和受合力所用而產生的位置偏移disp。

顯示區域：

平衡距離：

其中|v|是圖結構中節點的個數。

節點與節點之間的幾何距離：

相鄰兩個節點u和v之間的吸引力公式：

節點u和v之間的排斥力公式：

計算排斥力引起的位置偏移disp的遞歸函數為：

計算連接線e兩端節點由吸引力產生的位置偏移disp的遞歸函數為：

對點坐標進行置換的遞歸函數：

其中t為最大位移限定參數。t=cool(t)，采用模擬退火算法，t從某個初始值開始逐漸衰減到0，用限制節點的移動范圍。

如下圖所示，為一個含有20個節點的拓撲結構使用力導引算法自動布局生成的邏輯拓撲布局顯示效果。

圖2 力導引算法處理生成的邏輯拓撲結構

所以力導引算法更適用于網絡結構相對較復雜，網絡設備相對較多的內網邏輯拓撲布局處理中。

2 多面域網絡拓撲結構分析

由于網絡邏輯拓撲中一般情況下不會出現環路，所以可以將網絡邏輯拓撲看做樹形結構。在網絡邏輯拓撲樹形結構中，以路由器、交換機、網關類網絡交換設備為代表的節點，在網絡中起到路由和轉發的作用，它們是節點和節點之間、節點和區域子網之間以及區域子網和區域子網之間連接關系的樞紐，因此，第一步就是通過節點的設備類別篩選出可以作為樹的根節點的節點集。第二步，則是通過這些路由交換類節點的連接出入度來判斷根節點的下一級節點，層級最高且連接了另一組路由交換類節點的交換設備，可以作為拓撲顯示圖的核心節點，以核心節點為第一層節點，其子節點依次向下劃分層次，而設備類別為主機、服務器等的終端類節點通常只能作為末端葉子節點，即最低層次節點。

圖3 多面域網絡邏輯拓撲圖

通常情況下，如圖3所示，網絡拓撲中的多個終端與一個路由交換設備同時所屬一個區域子網，每個區域子網均有各自的業務功能，因此還需要在終端的上一層建立一個面域層，以涵蓋其下的所有終端及相關交換節點，從而對區域的業務性質進行劃分。同時，某一面域內部也可以具有不同的網段或業務劃分，因此面域內部也可以出現面域嵌套顯示的情況。本系統內網拓撲的顯示以面域形式來表征不同的業務區域，并支持面域嵌套的功能。

所以對圖3所示網絡邏輯拓撲關系的數據存儲結構如下圖所示：

圖4 拓撲關系存儲結構

如上圖所示，面域也被看作為網絡基本單元，面域中的元素通過指針與其所屬面域相關聯，所以代表網絡邏輯拓撲基本單元的結構體代碼如下所示：

3 多面域網絡邏輯拓撲生成算法實現

由于網絡拓撲中的存在多個區域子網，每個區域子網均有各自的業務功能，因此在進行拓撲生成處理時需要將每一個子網區域建立一個面域層，以涵蓋其下的所有終端及相關交換節點，而且，某一面域內部也可以具有不同的網段或業務劃分，因此面域內部也可以出現面域嵌套顯示的情況。所以設計多面域網絡邏輯拓撲生成算法時需要綜合考慮節點與面域的關系。

由于層級布局算法處理后生成的邏輯拓撲布局將會在頂層單獨顯示根節點，而在多面域網絡邏輯拓撲結構中，面域內部網絡與外部網絡的出入口設備明顯可以作為面域內部網絡拓撲結構中的根節點，如圖3所示，其中應用服務區的交換機設備可以作為本面域的根節點，其下連接的兩個服務器與一臺主機作為根節點的一級子節點。所以，當面域內部網絡結構簡單，網絡設備較少時，使用層級布局算法對其進行布局顯示處理，而當網絡設備較多時，系統采用力導引算法進行布局處理。

多面域網絡邏輯拓撲生成算法類圖如下所示：

圖5 多面域網絡邏輯拓撲生成算法類圖

如類圖所示，TopoBase的功能是根據拓撲數據整理拓撲關系的存儲結構，TopoView實現了邏輯拓撲視圖的基本元素的繪制，TopoOperation利用層級布局及力導引布局算法，生成最終的布局效果。

在對多面域網絡邏輯拓撲進行處理計算時，將面域也被看作為一種元素類型，由于網絡邏輯拓撲結構可能出現面域嵌套的情況，所以需利用遞歸的思想，先將面域內部子網進行處理。將拓撲關系存儲結構進行布局生成的處理流程如下圖所示：

圖6 拓撲關系存儲結構布局處理流程圖

使用遞歸的方式實現多面域網絡邏輯拓撲生成算法拓撲處理部分的偽代碼如下所示：

使用本文設計的多面域網絡邏輯拓撲生成算法對圖3所示的網絡邏輯拓撲結構進行布局顯示處理，處理結果如下圖所示：

當需要布局處理的網絡規模較大，并出現面域嵌套現象時，如下圖所示，為深度5、節點規模為一百數量級、并有面域嵌套情況的網絡使用本文提出的多面域網絡邏輯拓撲生成算法處理后的布局效果。

可見針對多面域內網邏輯拓撲結構，本文設計的布局算法處理結果清晰、合理，符合用戶的視覺需求。

圖7 多面域網絡邏輯拓撲生成算法處理的布局結果

圖8 復雜網絡處理后的布局結果

4 總結

本文針對網絡空間態勢邏輯拓撲信息可視化的總體需求，分析了態勢感知過程中獲取到的網絡拓撲數據復雜多域的特點，并結合網絡拓撲特性，定義了多面域網絡邏輯拓撲的存儲結構，在此基礎上，綜合層級布局與力導引布局算法，設計并實現了多面域網絡邏輯拓撲生成算法，并對算法加以驗證。實驗表明，算法處理生成的邏輯拓撲布局清晰、合理。

但是目前僅僅是從二維視角對態勢邏輯數據進行布局處理，當拓撲中包含超大規模網絡設備時，基于三維視圖的可視化處理算法會提供更清晰美觀的布局展示效果，而本文提出的算法采用遞歸的方法進行處理，所以當網絡規模特別大時處理效率也不是很理想。所以，將二維布局擴展到三維空間，以及算法處理效率的提升將是本課題后續的研究重點。

[1] 雷璟. 網絡空間攻防對抗技術及其系統實現方案[J]. 電訊技術, 2013, 11: 1494-1499.

[2] 曲朝陽, 胡緒超. 基于SNMP的網絡拓撲發現與拓撲生成樹的繪制[J]. 網絡安全技術與應用, 2007, 03: 23-24+27.

[3] 古潤南, 艾中良. 基于LOD控制與內外存調度的大規模網絡態勢數據節點處理算法[J]. 軟件, 2016, 03: 89-93.

[4] 姜雪飛. 基于SNMP的網絡安全態勢可視化技術[D]. 哈爾濱工程大學, 2010.

[5] Fruchterman T M J, Reingold E M. Graph drawing by force-directed placement[J]. Software: Practice and experience, 1991, 21(11): 1129-1164.

[6] 李海峰. 圖布局FR算法的研究與實現[J]. 電腦知識與技術, 2013, 12: 2864-2865.

Research on Logical Topology Layout Algorithm of Multi-domain

JIA Bai-tao, AI Zhong-liang

(North China Institute of Computing Technology, Beijing 100083, China)

The visualization of cyberspace situation has become an important link in synthesis and analysis of cyberspace situation information, and the layout generation of network topology has also received more and more attention in the situation visualization. The topology data of cyberspace situation has the characteristics of complex and multi-domain. This paper proposes a logic layout generation algorithm for topology data in cyberspace, combined with the hierarchical layout and force-directed layout. Experimental results show that the proposed algorithm can automate the topology layout of the multi-domain network and ensure the layout is clear and reasonable.

Situation visualization; Topology generation; Hierarchical layout; Force-directed

TP311

A

10.3969/j.issn.1003-6970.2017.01.019

賈百韜(1989-)，男，研究生，主要研究方向：態勢可視化；艾中良(1971-)，男，研究員級高級工程師，主要研究方向：網格計算、信息共享及信息安全。