基于H3的拓扑可视化研究及实现

辛富国，李荣芳，王中振，权东晓

（1.陕西邮电职业技术学院 咸阳 712000；2.西安电子科技大学 西安 710071）

1 引言

随着社会的不断发展，网络在人们日常生活和工作中的作用越来越重要。网络的功能越来越强大，网络的规模也在不断扩大，流量也不断上升。即使是网络管理员也可能并不清楚网络的拓扑结构，因此拓扑发现的作用变得越来越重要。拓扑发现包括合作探测和非合作探测[1]。合作探测时，管理员可以通过访问路由表、MBI库[2]等来辅助探测拓扑，这能够帮助管理员了解网络的连接关系，同时根据流量信息对网络进行扩容；非合作探测主要用作攻击，指的是在没有访问权限的情况下，通过向网络发送数据分组，根据其返回的信息来推测网络拓扑。传统的算法是基于 ICMP（internet control messages protocol，互联网控制报文协议）来进行拓扑发现[3]，由于一些路由器不响应，使得发现的拓扑不完整，较好的解决方案是结合流量、时延[4]、地址转发表[5]等信息进行网络断层扫描[3～5]，推测拓扑信息。

通过拓扑发现可以得到网络地址的连接关系，但是如何将得到的拓扑信息很好地显示给用户,也是一个比较困难的问题。拓扑可视化就是通过已知的拓扑数据将目标网络的节点和连接状况完整、清晰地呈现在人们眼前，为人们分析、了解目标网络的状况提供依据。单点拓扑发现的结果是树型结构，如果以平面的形式来显示[6]，由于树的节点数量随着树的深度的增加呈现指数增长，那么能够显示的节点数量就是有限的，并且层次越深，节点的符号就越小。但是由于双曲空间中空间大小呈现指数增长，正好与树的节点增长的趋势一致，所以可以借助双曲空间来进行显示[7]。基于H3的拓扑可视化[8]就是基于这样的原理实现的。

本文首先给出一个高效的网络拓扑发现算法，然后详细介绍了基于H3的拓扑可视化的基本原理，最后基于MFC（microsoft foundation class，微软基础类）进行了编程实现并以其对校园网进行了测试与分析。

2 算法描述

2.1 拓扑发现算法

在这里采用常用的基于ICMP的拓扑发现算法，首先利用ping程序探测主机是否在线，如果在线则逐步改变TTL（time to live,生存时间）值进行路径探测。为了提高效率，对算法做了以下改进。

一是采用多线程编程来进行探测。由于利用ping程序探测时，如果主机在线则会立即返回信息，否则必须默认等待超时后才能确定主机不在线，需要的时间比较长。若主机在线，需要逐步改变TTL值进行路径探测。因此当探测的地址空间较大时，单线程执行需要的时间会很长，所以采用多线程编程来提高探测速度。

二是采用由远及近的探测方式。在图1所示的拓扑结构中，假设主机A探测到主机H在线后，依次设定TTL值为2和1，则分别会收到节点G和F返回的超时信息ICMP_timeout。A到H的路径探测结束，然后探测节点J，首先设置TTL值为3，则会接收到节点I返回的信息，然后设置TTL值为2，接收到节点G返回的信息。由于在前面已经探测过A到G的路径了，因此后面就没有必要设置TTL值为1继续探测，提高了探测速度。在真实网络中，特别是探测距离较远的外网时，能大大提高探测速度，减少发送分组的数量，对网络造成的影响也较小。

图1 网络拓扑结构示意

2.2 数据预处理

拓扑探测得到的路径信息，用数据库进行存储，包括目的节点以及经过的每一个路由器的IP地址。由于有的路由器对ICMP数据分组没有响应，如果没有收到回复，在数据库中则将路由器的地址记为255.255.255.255，方便以后将IP地址转换成整数进行压缩存储。

如果对图1所示的拓扑结构进行探测，则探测结果见表1。

表1 图1的拓扑探测结果

而H3可视化软件的输入文件中每一行代表一个节点，其内容格式为:depth identifier[…]。

depth是指当前节点在骨干树中的深度，如果当前行A的前面数行中某行B的深度比行A的深度小1，则说明在树中A是B的孩子节点，有一个连线从B到A。identifier用来描述节点，一般为IP地址等信息，[]中的信息为附加信息，用来描述节点是主机、路由器、显示标志等。图1所示的网络拓扑结构，其对应的文件格式为:

观察该文件和图1可知，该文件的输入顺序类似于图的深度优先遍历序列。要实现拓扑的可视化，关键是如何从表1得到H3要求的输入文件，最终将一条条独立记录的路径信息归并成一棵树。并且在实现时必须考虑算法的高效性，因为当拓扑记录达到数千上万条的时候，时间复杂度超过O(n2)的算法都将会变得非常缓慢。

在处理时，可以对数据库的内容先进行hop_1（第1跳）的排序，再对hop_2进行排序……在对hop_30进行排序后（假设最多为30跳），表1将会变成表2的结果。

表2 排序后的探测结果

从表2中的数据可以看出，相似度越高的记录越邻近，那么在遍历数据库生成H3需要的文件的时候，只需要比较当前记录和上一条记录的差异，就可以依据这些差异添加相应的节点，从而减少了不必要的比较。同时，该过程中对每一条记录的每一跳的遍历刚好是一个深度遍历的序列，这样就可以生成H3需要的文件。该算法的时间复杂度是O(n)，速度比较快。

2.3 拓扑可视化

得到文件以后，就要根据文件对拓扑结构进行可视化。由于基于单点探测的网络拓扑是一个树型结构，需要布局的节点数量随着树的深度的增加呈现指数增长。而在欧几里得空间中可用的布局空间则呈现多项式增长，这样为了显示结果就要将离根节点较远的节点占用的空间减小，从而导致能够看到离根节点较近的拓扑连接关系，而较远的节点无法看清。由于双曲几何空间中可用的布局空间随着半径的增长呈现指数形式的增长，所以H3借助双曲几何空间进行显示。通过投射模型将双曲空间投影到欧几里得空间进行显示，因为直线的显示速度要快很多，在用户拖动查看拓扑结构时速度较快。

在树的布局上，H3可视化算法是由施乐帕克研究中心开发的圆锥树[9]系统扩展来的。圆锥树将叶子节点布局在从双亲节点发散出来的圆锥的圆周上，而H3算法则将叶子节点布局在一个覆盖在圆锥之上的半球面上。这个算法要进行两趟遍历:自底向上执行一趟来估算每个半球容纳所有的孩子半球所需要的半径大小，自顶向下执行一趟来将每个孩子半球布局到双亲半球的表面。这两步是不能合并的，因为在布局孩子半球的时候需要先确定双亲半球的半径[8]。

（1）自底向上的估算

设双亲半球的半径为rp，在p+1层有n个孩子半球，每个孩子半球的地面圆的面积为Dk，则p层的半球的表面积为p+1层的所有孩子半球的底面圆的面积和，即:

从而得到双亲半球的半径为:

则对应到双曲空间分别为:

通过自底向上的估计，可以得到所需要的球的半径，下面通过自顶向下的方式来布局各个节点。

（2）自顶向下的布局

在布局的时候，所有的孩子半球都依据其子孙的数量进行排序，依据孩子半球的大小自内向外地在环状带上填充，子孙数量最多的填充到极点位置。图2（a）为填充方式的侧视图，图 2（b）为填充方式的俯视图，从图2（c）可以看出如果不对节点进行排序，则会浪费很多空间。

图2 填充解决方案示意

设每个孩子半球的坐标为:(rp,,θ)，通过第一步，已经得到了半径rp，下面求出 和θ。

由于图3可以得到，两个相邻的孩子节点的θ的增量取决于两个孩子半球的半径，通过推导可以得到:

图3 孩子半球的布局点θ的变化

在一个环状带内，顺时针不断增大θ值来布局孩子节点，当环状带j填充至θ=2π时，则移动至下一个离极点更远的环状带j+1。由于对节点进行了排序，所以每个环状带内的第一个节点半径最大，可以通过第一个孩子半球的半径求得 的增量:

（3）测试与分析

基于提出的拓扑发现算法和可视化方法，在VC6.0环境下借助MFC编写了拓扑发现软件，数据库采用MySQL，对校园网进行了测试，测试结果如图4所示。

左侧以列表的形式显示发现的主机，通过点击“+”号可以将到达目标节点的路由信息显示到下方的编辑框里。通过多次测量，得到了254个主机，并绘制了拓扑结构，初始拓扑中，根节点的 和θ均为0，显示在球表面的中心位置。通过拖拽可以实现旋转效果，方便观察感兴趣的节点，如图5所示。

3 结束语

图4 拓扑结构初始状态

图5 旋转后的拓扑结构

本文给出了一种快速且对网络产生负载较小的拓扑发现算法，利用数据库来存储信息，方便程序对其进行快速的检索。并基于H3的拓扑可视化原理对数据进行预处理，最终实现了拓扑可视化。测试结果表明，该方法可以很好地对网络拓扑进行可视化，但是发现的拓扑不是很完整，需要通过多种手段识别匿名路由器，借助网络断层扫描技术推测拓扑结构，也可以进行分布式拓扑发现。

1 闫兴篡，殷建平，蔡志平.网络拓扑发现算法综述.计算机工程与应用，2007,43(14):131～135

2 卢红梅.一种网络拓扑算法的研究和分析.科技信息，2012(31):144～145

3 刘香丽，吴辰文，茹俊年等.基于Tarceroute和邻接分组对的网络拓扑推测方法.兰州交通大学学报，2013,32(1):88～91

4 张耀方，孔德弟，石佳玉.改进的网络拓扑推断算法.电子测试，2014(1):36～41

5 李丹程，马东琳，韩春燕等.面向Trunk技术的网络拓扑发现算法研究，2012,33(11):2435～2441

6 徐阔海.一种基于Rapha I图形库的网络拓扑生成系统.软件导刊,2014,13(1):149～151

7 Lamping J,Rao R.Laying out and visualizing large trees using a hyperbolic space.Proceedings of UIST’94,Marina del Rey,California,USA,1994:13～14

8 Munzner T.Interactive visualization of large graphs and networks.Doctoral Dissertation of Stanford University,2000

9 Robertson G,Mackin lay J,Card S.Cone trees:animated 3D visualizations of hierarchical information.Proceedings of the Conference on Human Factors in Computing Systems(CHI’91),New Orleans,Louisiana,USA,1991:189～194