多域网络逻辑拓扑布局算法研究

贾百韬，艾中良

(华北计算技术研究所，北京 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-)，男，研究员级高级工程师，主要研究方向：网格计算、信息共享及信息安全。