基于距离的IPv6校园网拓扑发现整合算法*

董守玲 李佳 张凌

(华南理工大学计算机科学与工程学院，广东广州510006)

拓扑发现是网络管理的一项基本功能.由于下一代互联网IPv6协议中地址结构等方面的变化以及IPv6网络中庞大的节点数量，适用于IPv4网络的拓扑发现方法已不再适用于IPv6网络环境.由于Traceroute6探测方法是利用ICMPv6消息发现从源地址到目的地址之间通过的路由器来得到网络拓扑，它独立于IP的特性使得许多学者研究采用Traceroute6探测方法对IPv6的骨干网网络层的拓扑进行拓扑发现.Astic等［1］提出了一种基于Traceroute6的分级结构的拓扑发现思想，该方法虽然对局域网的管理收到了良好的效果，但需要在每一个子网内安置探测点，系统较为复杂.Daniel等［2］提出了一种利用源路由选项进行改进的基于Traceroute6的拓扑发现思想，对6Bone网络进行了大规模的探测，但是目前并不是所有路由器都支持IPv6的源路由选项，而且利用源路由机制进行拓扑发现会大幅增加探测时间.国内在IPv6网络拓扑发现领域的研究起步较晚，同样主要研究基于Traceroute6的拓扑发现方法［3-7］，这种方法通用性好，算法容易实现，但存在路由别名的问题(同一路由器的不同接口地址被误认为是多个路由器)，致使准确性不高;此外，Traceroute6探测方法不能发现网段信息，而且如果给定的探测目的地址缺少部分边界路由器，则这些边界路由器及相连链路不能被发现，或发现的信息不完整.若增加探测节点来提升完整性，则会增加探测时间以及出现更多的路由别名问题.针对Traceroute6拓扑发现方法存在的不足，许多学者也在使用源路由提高完整性、减少路由别名、减少冗余探测提高性能方面进行了探讨和研究［8-12］.

开放式最短路径优先(OSPF)协议是一个内部网关协议，用于在单一自治系统内决策路由.OSPF域中的每台路由器上都有一个链路状态数据库，存放关于整个路由域的链路状态信息.当网络结构发生变化时，路由器之间通过交换过程和泛洪过程实现链路状态数据库的动态同步，从而得到本区域的拓扑结构.如果能与网络上的路由器交换信息，就可以得到网络拓扑信息.曾有学者利用OSPF协议进行IPv4网络环境下的拓扑发现［13］.这种发现方法的准确率令人满意，而且包含丰富的子网信息，更重要的是，该方法不存在路由别名的问题.但是，该方法只能得到子网信息，不能得到接口信息，而且OSPF从第3版本(OSPFv3，用于IPv6网络)开始不再用IPv6地址标识路由器，虽然OSPFv3协议在IPv6网络的路由设计中得到了广泛的应用，但该发现方法在IPv6环境中的使用受到了限制.

基于Traceroute6的拓扑发现方法和基于OSPF路由协议发现方法各有优缺点，如果将这两种拓扑发现方法结合，就可以利用OSPFv3发现的拓扑信息来对Traceroute6发现的信息进行补充和修正，改善拓扑结果的覆盖率以及解决路由别名的问题，而利用Traceroute6发现的信息又可以标识OSPFv3发现的路由器的IPv6地址及接口.

这两种拓扑发现方法结合的难点在于，基于Traceroute6的拓扑发现方法是用IPv6地址来标识路由器的，而OSPFv3协议不包含地址信息，它是用RouterID来标识路由器的.

笔者曾提出一个名为ANTDBMP的算法［14］.该算法分别使用基于Traceroute6的拓扑发现方法和基于OSPF的拓扑发现方法进行拓扑发现，并基于跳数(hop)成功地将两种方法发现的结果进行整合，得到了较好的效果.但这种基于跳数的整合方法也存在一些不足之处，而且系统效率不高.针对这个问题，文中提出一个新的IPv6网络拓扑信息的整合算法DIAITD(Distance-Based Integrated Algorithm for IPv6 Topology Discovery)，并通过实际网络对该算法进行了测试.

1 DIAITD算法

根据OSPF协议，每台运行OSPF路由协议的路由器必须用RouterID来唯一标识.RouterID通常为一个IPv4地址或者是一个有意义的字符串.若仅仅拿RouterID和基于Traceroute6探测发现的IPv6地址作对比，很难发现两者的直接联系.由于OSPF的链路状态通知中有丰富的子网信息，可以利用子网信息来查找两种拓扑发现方法的关联之处.

1.1 相关工作

ANTDBMP算法［14］首先将利用 Traceroute6发现的IPv6地址和利用OSPFv3协议发现的子网信息进行比对，确定地址分布在哪些网段内;然后采用UDP数据包探测法计算IPv6地址以及属于该子网的OSPF路由器的跳数，根据对比跳数来确定IPv6地址属于哪一台OSPF路由器;最后通过其它信息对特殊的情况进行分析和修正.

但是，ANTDBMP算法存在一些缺陷.首先，OSPF路由器的跳数计算是将该路由器的RouterID作为目标地址进行Traceroute6操作从而得出，如果RouterID不是IPv4地址而是一个有意义的字符串(例如路由器的位置)，则无法计算OSPF路由器的跳数;其次，即使所有RouterID都是IPv4地址，当Traceroute6的某IPv4地址出现目的地不可达时(路由器设置了不回应)，就得不到该地址的跳数;再者，即使所有地址都可达，跳数都能正确返回，同一路由器的不同地址也会因为路由表规定的路径不同而返回不同的跳数.如图1所示，路由器R1、R2、R3两两相连，以R1为探测源点，到达R3的路径就有两条:路径1(跳数为2，R1-R3);路径2(跳数为3，R1-R2-R3).当对 R3上的 RouterID进行 Traceroute6操作时，可能路由表选了路径2，而对R3的一个IPv6地址进行Traceroute6操作时，路由表选了路径1，那么返回的跳数就不一样，这时根据跳数进行判断就会判断错误.

图1 不同的传输路径及其返回的跳数Fig.1 Different transmission paths and their hops

1.2 DIAITD 算法原理

由于基于跳数结合的方法在某些情况下变得不可靠，文中提出一种新的结合方式，不再用跳数进行判断，而是利用连接关系表中的信息.

定义D(A)为连接关系表中节点A到网关的最短距离，N1、N2、N3为子网，IPA、IPB、IPC 为 IPv6地址.

根据网络路由器之间的连接关系，有如下性质.

性质1 对于任何存根子网，有且只有一台路由器属于该存根子网.

根据性质1可以得到如下结论:∀N1∈存根子网，∃R1∈N1，∃IPA∈N1，如果 D(IPA)=D(R1)，那么IPA∈R1.

性质2 对于任何路由器间子网，有且只有两台路由器属于该子网，它们有共同的子网前缀.

根据性质2可以得到如下结论:∀N1∈路由器间子网，∃R1∈N1，∃R2∈N1，∃IPA∈N1，如果D(IPA)=D(R1)且 D(IPA)≠D(R2)，那么 IPA∈R1.

性质3 一个路由器的不同接口具有不同的子网地址.

根据上述性质和结论，分别定义基于OSPF路由协议的拓扑发现方法和基于Traceroute6的拓扑发现方法得到的节点间的连接关系为LinkList_OSPF和 LinkList_Traceroute6.以 LinkList_OSPF 为例，以网关作为根节点，通过最短路径算法求出在连接关系表中其它所有节点到网关的最短距离.对LinkList_Traceroute6作同样的分析，然后以这个距离作为度量值.

取出由Traceroute6拓扑发现方法得到的一个IPv6地址IPA，从子网集合Subnet_OSPF中进行查找，看是否存在与IPA地址前缀匹配的子网N1，若N1对应的OSPF路由器有且只有一台路由器R1(即N1为存根子网)，则比较 D(IPA)和D(R1)，若相等，则IPA属于R1;若存在另外一个路由器R2(即N1为路由器间子网)，则分别比较D(IPA)、D(R1)和D(R2)，从而得出IPA属于哪一台路由器.

但仅仅用距离来进行判断时，在以下情况下会失效:当测试地址(记为IPA)为路由器间网络的地址，且两台OSPF路由器(记为R1和R2)与网关的距离相等时，无法判断IPA是属于R1还是属于R2，如图2所示.

图2 IPA、R1、R2与网关的最短距离Fig.2 Shortest distances between gateway and IPA，R1and R2

解决方法1 对于距离相等的情况，取IPA的子网前缀prefixA，根据prefixA构造一个新的该子网下的任意地址IPB.例如，prefixA为2001:da8:250:3001::，可以构造一个 IPv6地址2001:da8:250:3001::45.通过网关对IPB发ICMP探测包，则该网段的路由器地址通常选择发出回应包的接口(如图2中的IPC)返回一个地址不可达的ICMP回应包，若D(IPC)=D(IPA)且IPC≠IPA，则IPC与IPA是同一路由器下的两个接口地址，接下来只需分别查看R1与R2的子网表，通常有且只有一个路由器包含IPC所在子网的信息，从而认定IPA属于那台有IPC子网信息的路由器.

解决方法2 查看接口表，看IPA所在路由器是否存在其它接口地址.假设存在其它地址IPC是IPA所在路由器上的另一接口地址，如图3所示.既然IPA和IPC是同一路由器的不同接口地址，而只有一个接口会遇到同一个网段距离相等的情况，因此IPC不会出现同一个网段距离相等的问题.对IPC采用上述提到的基于距离的整合方法，可以判断IPC位于路由器R1上，因此作为同一路由器的接口地址，IPA也属于路由器R1.

图3 同一路由器上的接口与网关的最短距离Fig.3 Shortest distances between gateway and interfaces on the same router

解决方法3 查看子网表和接口表，查看是否存在前缀同样为prefixA的其它接口地址.如图3所示，存在与IPA前缀相同的IPD.由于同一路由器间网络里有且只有两个接口地址，因此，若利用解决方法1和2能确定出IPD属于哪一台路由器(见图3，IPD属于R2)，相应地就能确定IPA属于该网段下的另一台路由器(即R1).

通过上述3种解决方法，能有效解决基于距离的整合方法出现距离相同时无法判断的问题.

这种基于距离的DIAITD算法无需发ICMP包进行探测，只需分析连接关系表，在减少网络通信的同时缩短了分析时间;而且，最短路径算法是一个被广泛使用的成熟算法，其时间复杂度不高，只要连接关系表的数据正确，计算出来的距离就是正确的，这样便保证了DIAITD算法的准确率;再者，由于无需借用RouterID进行判断，整合方法与路由协议无关，因此该结合方法同样适用于其它拓扑发现方法间的结合，具有很好的通用性.

1.3 DIAITD 算法描述

下面给出DIAITD算法描述，其中RouterList_Traceroute6代表基于Traceroute6获取的路由器节点集合，RouterList_OSPF代表基于OSPFv3获取的路由器节点集合，LinkList_Traceroute6代表基于Traceroute6获取的连接关系，LinkList_OSPF代表基于OSPFv3获取的连接关系，Subnet_OSPF代表基于OSPFv3获取的子网集合，D(A)代表A与网关之间的距离，CurDistance表示与网关的最短距离计数，baseNodeList表示已处理的节点列表.

首先计算基于所有OSPF路由器到网关的最短距离，其算法描述如下:

其次计算Traceroute6获得的IPv6地址到网关的最短距离，算法与上述算法类似，此处不再赘述.

根据上述计算的最短距离，对拓扑发现结果进行整合.其算法描述如下:

1.4 DIAITD算法的时间复杂度分析

计算所有路由器到网关的最短距离时，最坏的情况时要遍历LinkList才能找到对应Ri的记录，此时时间复杂度为O(ML)，其中M为RouterList的大小，L为LinkList的大小;在整合时，最坏的情况下要遍历子网表才能找到对应Ri的子网记录，测试算法的时间复杂度为O(MS)，S为Subnet_OSPF的大小.因此总的复杂度为O(ML)+O(MS).

2 测试与结果分析

基于文中所提出的拓扑发现整合算法，使用java语言在Linux环境中设计并实现了一个IPv6网络层拓扑发现系统.该系统包含5个模块:2个探测引擎、1个拓扑整合模块、1个拓扑保存以及1个拓扑显示模块.

2个探测引擎中的一个基于利用源路由改进的Traceroute6方法，另一个基于OSPFv3路由协议.系统利用这两个探测引擎分别去收集网络拓扑信息.其中，基于Traceroute6的探测引擎收集信息分为初步探测拓扑阶段、源路由测试阶段以及交叉路径发现阶段.基于OSPFv3路由协议的发现方法是将计算机模拟成路由器，与网络上的路由器交换网络拓扑信息，从而得到完整的网络拓扑信息［15］.在整合模块中，利用DIAITD算法把两个拓扑发现引擎的拓扑发现结果进行整合.整合后的拓扑结果可以通过拓扑显示模块进行显示，也可以通过拓扑保存模块保存进数据库.

实验在华南理工大学校园网上进行，为测试系统的各项指标分别进行了多项测试，同时比较新旧算法的准确性、完整性以及效率.

测试1 比较改进的基于距离的拓扑信息整合算法(DIAITD算法)和旧的基于跳数的整合算法(ANTDBMP算法).

为保证测试的真实性，随机采用每台路由器上的一个接口地址作为探测节点，共22个.通过OSPF探测引擎发现OSPF路由器22台，通过Traceroute6探测引擎发现31个IPv6地址，结合情况如表1所示，其中，准确率为成功结合的IPv6地址数与IPv6地址总数之比.

表1 新旧拓扑信息整合算法发现整合效果对比Table 1 Comparison of integration effect between original and new algorithms for topology information integration

表1的数据显示，基于距离的DIAITD算法向网络发送了10个ICMP探测包，这是由于测试时程序遇到了第1.2节中提到的距离相等的问题，而其采用解决方法1来解决问题，因此产生了网络通信.通过对比发现，新的基于距离的拓扑发现整合算法比基于跳数的算法更加准确，分析整合时间和发包数也大为减少.

测试2 分别采用基于OSPF的拓扑发现方法、基于Traceroute6的拓扑发现方法和DIAITD整合算法对网络进行测试，结果如表2所示.

表2 3种拓扑发现算法结果的比较Table 2 Comparison of results among three topology discovery algorithms

从表2中可以看出，OSPFv3发现方法只能发现子网信息，不能得到接口信息，Traceroute6发现方法可以发现接口信息，但是不能发现网段信息，并且存在别名问题，这导致发现的路由器和连接关系个数与真实情况有出入.另外Traceroute6发现的接口个数与探测节点集合的大小有关，由于本次探测的探测节点只有22个，因此只发现了31个接口，大量的接口信息不能被发现.DIAITD整合算法不仅可以发现路由器设备，还可以发现子网及接口，发现的信息比单独的OSPFv3发现方法或Traceroute6发现方法更为完整，经验证与真实拓扑图更为吻合.由于整合算法的接口信息来源于Traceroute6发现方法，因此接口数目与Traceroute6发现方法发现的一样.

测试3 校园网环境与加入公网环境拓扑结果的比较.

在原有地址集合里增加了3个公网地址:上海交通大学的地址(ipv6.sjtu.edu.cn，IP 为 2001:da8:8000:1::80)、华南农业大学的地址(ipv6.scau.edu.cn，IP 为 2001:da8:2004:1000:202:116:160:48)和谷歌的地址(ipv6.google.com，IP 为 2404:6800:8003::69).探测结果如表3所示.

表3 校园网环境与公网环境拓扑发现结果比较Table 3 Comparison of discovery results between campus network and public network

表3表明，在增加了3个公网地址后，除子网个数没有变化外，路由器个数、连接关系个数和接口个数都有不同程度的增加.子网个数没有变化的原因是子网信息是利用OSPF协议发现的，而公网和校园网不属于同一个OSPF域，因此运用OSPF协议只能获得华南理工大学校园网的信息，在校外的网络只能用Traceroute来探测.在这种情况下，校外的子网就不能被发现了.

3 结语

文中设计和实现了一个基于距离的IPv6校园网拓扑发现整合算法，该算法将两种不同的拓扑发现方法的拓扑结果进行整合.测试结果证明，该算法能更有效、准确、迅速地整合拓扑信息.拓扑信息的整合是一个相对新的研究领域，虽然文中方法目前只能对Traceroute6和OSPF协议的拓扑结构进行整合，但基于OSPF协议的广泛应用以及Traceroute6的通用性，整合之后的结果无论从完整度和精确度来看都比单一拓扑发现方法更接近实际网络情况，这种基于距离的整合方法定能对处于同一个OSPF域的IPv6校园网拓扑发现提供有效帮助.

［1］Astic I，Festor O.A hierarchical topology discovery service for IPv6 networks［C］∥Proceedings of 2002 IEEE/IFIP Network Operations and Management Symposium.Florence:Institute of Electrical and Electronics Engineers Incorporation，2002:497-510.

［2］Daniel G W，Fangzhe C，Ramesh V，et al.Topology discovery for public IPv6 networks［J］.Computer Communications Review，2003，33(3):59-68.

［3］Dong S L，Zhang L，Lan C F.Compatible IPv4 and IPv6 networks topology discovery schema based on general protocols［C］∥Proceedings of 2007 International Conference on Broadband Network ＆ Multimedia Technology.Beijing:IC-BNMT，2007:307-311.

［4］Liu Z S，Luo J Y，Wang Q X.Large scale topology discovery for public IPv6 networks［C］∥Proceedings of 7th International Conference on Networking.Cancun:IEEE Computer Society，2008:639-644.

［5］李元臣，刘维群，匡国防，等.基于 Traceroute6的 IPv6网络拓扑发现技术［J］.计算机应用，2008，28(3):560-562.Li Yuan-chen，Liu Wei-qun，Kuang Guo-fang，et al.Topology discovery for IPv6 networks based on Traceroute6［J］.Computer Applications，2008，28(3):560-562.

［6］宫晨，郎昕培，陈英，等.IPv6骨干网络的拓扑发现［J］.计算机科学，2006，33(4):29-31.Gong Chen，Lang Xin-pei，Chen Ying，et al.Topology discovery for backbone of IPv6 networks［J］.Computer Science，2006，33(4):29-31.

［7］丛林，陈阳，邓北星，等.CERNET2 IPv6网络层拓扑发现［J］.厦门大学学报:自然科学版，2007，46(增刊 2):6-8.Cong Lin，Chen Yang，Deng Bei-xing，et al.The IPv6 network layer topology discovery of CERNET2 ［J］.Journal of Xiamen University:Natural Science，2007，46(Suppl 2):6-8.

［8］周苗，杨家海，吴建平.基于滑动地址序列的IPv6网络拓扑发现引擎［J］.清华大学学报:自然科学版，2009，49(8):1241-1244.Zhou Miao，Yang Jia-hai，Wu Jian-ping.IPv6 topology discovery engine based on a sequence of sliding addresses［J］.Journal of Tsinghua University:Science and Technology，2009，49(8):1241-1244.

［9］杨柳，李振宇，张大方，等.冗余最小化的IPv6拓扑发现方法 ［J］.计算机研究与发展，2007，44(6):939-946.Yang Liu，Li Zhen-yu，Zhang Da-fang，et al.Topology discovery with smallest redundancy in IPv6 ［J］.Journal of Computer Research and Development，2007，44(6):939-946.

［10］Zhu M M，Luo J Y.An improved solution for IPv6 network topology discovery based on source routing mechanism［C］∥Proceedings of the 2009 International Conference on Communication Softwareand Networks.Macau:IEEE Computer Society，2009:279-282.

［11］Qian S Y，Wang Y H，Xu K.Utilizing destination options header to resolve IPv6 alias resolution［C］∥2010 IEEE Global Telecommunications Conference.Miami:Institute of Electrical and Electronics Engineers Incorporation，2010:1-6.

［12］Qian S Y，Xu M，Qiao Z L，et al.Route positional method for IPv6 alias resolution［C］∥2010 Proceedings of 19th International Conference on Computer Communications and Networks.Zurich:Institute of Electrical and Electronics Engineers Incorporation，2010:1-6.

［13］徐建锋，邓永平，丁圣勇.基于OSPF服务器的网络拓扑发现［J］.计算机应用，2004，24(8):98-100.Xu Jian-feng，Deng Yong-ping，Ding Sheng-yong.OSPF server based network topology discovery［J］.Computer Applications，2004，24(8):98-100.

［14］Dong S L，Li J，Zhang L，et al.A novel algorithm of IPv6 network topology discovery for campus network［C］∥2011 International Conference on Computer Science and Service System.Nanjing:IEEE Computer Society，2011:68-71.

［15］董守玲，张凌，董守斌，等.基于IPv6的下一代互联网拓扑发现系统及实现方法:中国，ZL 201010275867.x［P］.2012-03-28.