一种基于Rapha l图形库的网络拓扑生成系统

摘要：网络拓扑生成是网络监控的重点之一，在目前移动终端大量涌现，计算平台越来越多样的背景下，能够在不同的终端设备上一致性地显示网络拓扑显得越来越重要。Web应用具有平台无关性，将网络拓扑显示与Web应用结合，可在不同终端设备上呈现一致的拓扑图像，从而获得一致的用户体验。rapha l是一个兼容多浏览器的小型JavaScript矢量绘图库，在网络拓扑图邻接表的基础上，可使用Rapha l绘图库在Web页中动态绘制网络拓扑图。由于Rapha l的广泛兼容性，在不改变源代码的情况下，可达到多终端一致呈现的效果。

关键词：网络拓扑；Web；Rapha l绘图库；JavaScript

中图分类号：TP399 文献标识码：A 文章编号文章编号：16727800（2014）001014903

作者简介作者简介：徐阔海（1989-），男，四川大学计算机学院硕士研究生，主要研究方向为嵌入式系统和移动计算。

0 引言

网络拓扑生成是网络监控的重点之一，在目前移动终端大量涌现，计算平台越来越多样的背景下，能够在不同的终端设备上一致性地显示网络拓扑显得越来越重要。Web应用因其平台无关性，只要有浏览器支持，就可在任意终端运行。因此，将网络拓扑显示与Web应用结合，就可在不同终端设备上呈现一致的拓扑图像，从而达到一次编写多处运行的效果。

但由于Web浏览器厂商众多，各自互不兼容，通常为一种浏览器编写的JavaScript程序，很难在另一浏览器中完全一致地呈现。虽然由于HTML 5技术的出现，为编写通用浏览器程序打开了一扇大门，然而现阶段HTML 5技术并不成熟，各浏览器的支持有限，且稳定性不够，还不适合应用到实际工程中。Rapha l是一个兼容多浏览器的小型JavaScript矢量绘图库，底层使用SVG和VML作为基础，因而创建的每个图形都是DOM对象，很容易与JavaScript事件绑定，也便于后期修改。Rapha l目前支持Firefox3.0+、Safari3.0+、Chrome5.0+、Opera9.5+和Explorer6.0+[2]，基本覆盖了所有主流浏览器。因此，使用Rapha l绘图库来绘制网络拓扑，基本上可以达到一次编写多处运行的目的，在手机、平板、桌面等不同终端设备上获得一致的用户体验。需要说明的是，本文中所提到的网络拓扑大部分情形下指网络拓扑图，有时也指网络拓扑布局，需依据语境区分。

1 网络拓扑生成流程

本系统由中心服务器与Web前端组成，采用生成树方法来构造层次化的网络拓扑。中心服务器采集网络拓扑结构，存储在邻接表中。Web前端使用Ajax技术从服务器取得邻接表数据，再由邻接表生成一棵广度优先生成树，使用Rapha l图形库在Web页中绘制出画布，然后将生成树结点按层次均匀分布到画布中央，计算出各结点的中心坐标，根据结点的设备类型，为其选择合适的图标，以结点中心坐标为基准放置图标，最后从邻接表中找出所有具有连接关系的结点对，在其对应的图标间绘制直线，表示其连接关系。另外，采用JavaScript的定时器功能，设置定时器来定期获取邻接表数据，重绘拓扑图，以实现网络拓扑的动态更新。为避免连接关系复杂时生成的拓扑图显得杂乱，为每个结点图标都添加拖拽事件，以便于手工调整图标位置。

2 网络拓扑生成方法

2.1 生成广度优先树

图的广度优先生成树是在广度优先遍历图时产生的生成树。由图的邻接表构造广度优先生成树，其思想是从网络拓扑图的根结点出发，按与根的距离由近到远遍历图的所有结点，遍历过程中，记录下每个图结点在生成树中的父结点，和其所有子结点，具体算法参见文献[1]。需要注意的是，为方便后续计算结点中心坐标，应当在生成树中记录下树的高度和每个结点的深度。

2.2 计算结点中心坐标

从邻接表得到广度优先生成树后，便可由树结点的分布来计算出每个结点的中心坐标。结点的分布思想是，将树中深度相等的结点视为处于同一层，先将各层均匀分布到画布中，再将各层的结点均匀分布到其所在层中，如图1所示。图中Height和Width分别为画布的高度与宽度，w与h为边缘留空，Hi为第i层高度，Wi为第i层结点间距。根据计算机中绘图习惯，将画布的左上角顶点作为原点建立直角坐标系，则各结点的中心坐标计算过程如下：第i层高度为：

由此，可得到计算结点中心坐标的算法evaluateNodesPosition，该算法输入为拓扑图的宽度优先生成树，输出是各结点的中心坐标。算法采用类似JavaScript语言的伪代码描述，但赋值和循环等控制结构与文献[1]保持一致。算法1～4行创建一个元素为链表的数组layerNodes，数组长为树高，即结点的层次数；5～11行将结点按深度划分层次，将相同深度的结点放入同一层中（第9行），具体做法是先创建队列Q（第5行），再按图的宽度优先遍历方式对生成树T进行遍历（6～11行），其目的在于保证每层的结点与上层中父结点的放置顺序相同，例如结点A的孩子结点为A1、A2，结点B的孩子结点为B1、B2，若结点A、B处于第i层且放置顺序为B、A，则可以保证A、B的孩子结点在第i+1层中的放置顺序为B1、B2、A1、A2，这样可减少最终拓扑图中连线间的不必要交叉，使拓扑图简洁明晰。需要注意的是，因为T是树结构，每个结点都只能在访问其父结点时获得一次入队列机会，所以不需要设置遍历图时的visited辅助数组；第12行根据式（1）计算层高Hi；13～15行遍历所有的结点层，根据式（2）计算各层结点间距Wi；16～18行根据式（3）计算结点的中心坐标。

2.3 网络拓扑生成

获得结点的中心坐标后，就可将结点图标绘制到画布的相应位置上，再在具有连接关系的结点间绘制直线将相应图标相连，即得到网络拓扑图，具体方法如下：

（1）根据结点的设备类型，选择相应的图标，再将图标位置设置成该结点的中心坐标，此时便可将所有的网络结点以图形的形式在画布上展示出来，具体操作通过调用Rapha l的Paper.image（）函数完成。需要注意的是，不同类型结点图标大小不同，需要根据图标大小适当调整图标位置以使其中心与结点中心坐标重合。

（2）遍历拓扑图的邻接表，获取所有结点的连接关系，连接关系通过相连的结点对来表示，如（A， B）表示结点A、B间有连接关系。

（3）遍历连接关系结点对，根据其两端结点的中心坐标，绘制直线将两结点对应的图标相连，此时即可生成树状层次化的网络拓扑图，具体操作通过调用Rapha l的Paper.line（）函数完成。

通过以上方法生成的网络拓扑图通常都比较简洁，但若网络拓扑本身比较复杂，则结点间连线可能会比较混乱，这个问题可为每个结点图标设置一个拖动事件，使图标可通过手工拖动改变位置来解决。同时，使图标可以响应拖动事件，也可增强交互性，获得更丰富的用户体验。具体操作通过Rapha l的Element.drag（）函数设置。需要注意的是，在拖动图标时还应实时重绘图标间的连线，以保证拖动图标时网络拓扑不发生改变。

2.4 网络拓扑更新

每隔一定时间重绘网络拓扑，就可使其动态更新。但由于网络拓扑在网页中显示，传统网页技术只能刷新整个网页，而不能单独刷新某一部分，因此使用Ajax技术来动态更新网络拓扑。Ajax可以在不刷新整个网页的前提下，单独更新网页的一部分，获得更为快捷的响应速度。由于网络拓扑不是每次都变化，为避免每次获取邻接表后都重绘网络拓扑，需要保留一份旧邻接表副本，在取得新的邻接表后，与旧表进行比较，若没有变化，就不再重绘拓扑。否则，必须根据新邻接表重绘拓扑图，并将新邻接表

图2是一个具有冗余网络的拓扑结构最终的显示效果，图中3台PC机连接到两台交换机中，两台交换机互为备份，以避免一台交换机损坏造成网络的崩溃。从图2可以看出，拓扑图占用了画布的中央部分，各结点按层次均匀分布，结点间连线简洁明晰。

图2 实际效果

3 结语

不同于以往主要在后台服务器中生成网络拓扑，本文将网络拓扑生成过程移到浏览器中完成。使用Ajax技术直接从服务器获取邻接表数据，降低了服务器端的开销和前后台通信消耗的网络流量，同时由于结点图标的可拖动性，大大增强了交互性，改善了用户体验。采用Rapha l JavaScript绘图库可以在所有主流浏览器中生成一致的图像，只要终端设备有浏览器支持，就可以在不同设备上用相同方式查看拓扑图，从而获得一致的用户体验。在实际操作中，发现不同浏览器运行的效率和稳定时间不同。部分浏览器在长时间连续运行之后，会出现不稳定情况，这是由于Rapha l库底层必须依赖浏览器的实现。另外，在不同平台上的运行效率差别较大，这是由平台本身决定的，因为不同平台的计算能力差别较大。

参考文献：

[1] THOMAS H CORMEN，CHARLES E LEISERSON，RONALD L RIVEST，et al.Introduction to algorithms （Third Edition）[M].The MIT Press， 2009：600601.

[2] Rapha l—JavaScript Library[EB/OL].http：//.

[3] Javascript Tutorial[EB/OL].http：///js.

[4] JOHN RESIG.Pro JavaScript techniques[M].California：Apress，2006.