賈百韜，艾中良

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

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

賈百韜，艾中良

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

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

態(tài)勢可視化；拓撲生成；層級布局；力導引

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

0 引言

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

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

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

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

1 圖布局算法研究

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

1.1 層級布局算法

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

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

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

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

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

其中f為該節(jié)點層數。

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

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

其中Nchild為節(jié)點v子節(jié)點的個數。

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

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

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

1.2 力導引布局算法

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

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

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

顯示區(qū)域：

平衡距離：

其中|v|是圖結構中節(jié)點的個數。

節(jié)點與節(jié)點之間的幾何距離：

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

節(jié)點u和v之間的排斥力公式：

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

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

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

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

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

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

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

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

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

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

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

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

圖4 拓撲關系存儲結構

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結

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

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

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

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

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

[4] 姜雪飛. 基于SNMP的網絡安全態(tài)勢可視化技術[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-)，男，研究生，主要研究方向：態(tài)勢可視化；艾中良(1971-)，男，研究員級高級工程師，主要研究方向：網格計算、信息共享及信息安全。