基于IPv4和IPv6混合网络环境下拓扑发现算法研究

摘要：对于网络性能优化，配置控制和故障监控等来说有一个准确的网络拓扑结构是至关重要的。文中提出两个网络层拓扑发现算法分别对应于IPv6-only和 IPv4-only网络，一个数据链路层拓扑发现算法以及一个在共存的网络中的转换探测算法来进行各方面的网络拓扑发现。

关键字：拓扑发现；IPv6；SNMP；转换方式

中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)34-1585-03

Topology Discovery for Coexisting IPv6 and IPv4 Networks

CHEN Wen-feng, LU Ji-guang, WANG Juan

(School of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

Abstract: Having an accurate network topology is vital for network performance optimization, configuration control, and fault monitoring … etc. In this paper, two network layer topology discovery algorithms for IPv6-only and IPv4-only networks, a data link layer topology discovery algorithm, and a transition detection algorithm of coexisting networks are presented to discover network topologies from various aspects.

Key words: topology discovery; IPv6; SNMP; transition mechanism

1 引言

在网络管理功能中，拥有一个精确和完整的网络拓扑结构是非常重要的， 如性能优化，配置控制和故障监控等。拓扑图可以描述TCP/IP协议的每一个层，同时能有效协助网络管理员更好地管理网络。

有许多IPv4网络下拓扑发现方法，如报告[2-3]。此外，还有关于IPv6-only的一些建议，如报告[4-5]。大部分这些拓扑发现算法都是基于ICMP和SNMP。然而这些已经众所周知的方法还是不足以管理IPv6和IPv4共存的网络。为展示两个IP版本一起的拓扑结构，要首先探测重合的部分，即下文中转换方式部署的节点。

在本文中，提出IPv4与IPv6共存网络的拓扑发现算法。在网络层和数据链路层同时采取SNMP和ICMP技术。通过ip6routetable或iproutetable的SNMP获得的动态管理信息用来构建网络层拓扑图，通过attable和dot1dtpfdbtable获取的信息用来构建数据链路层拓扑图。使用多播IPv6逆邻居发现报文及广播IPv4 RARP报文收集所有的IP地址。经过分析所有IP地址的格式，IP地址重叠的主机就找了出来，同时可以得出所有MAC地址和其相对应的全部IP地址。从而就彻底呈现一个完整的混合网络拓扑结构。

2 SNMP MIB和ICMP

SNMP MIBs和ICMP报文中的信息是拓扑发现两个最常用的资源。SNMP的MIBs提供网络管理信息，ICMP可有效地用于发现网络中任意路径的主机状态。

2.1 MIB-II,IPv6 MIB,和Bridge MIB

SNMP的MIB的是一个存放管理对象信息的仓库。MIB-II,IPv6 MIB,和Bridge MIB管理组在发现算法中都有使用到。用到MIB-II中三个重要的表：sysservices，attable，iproutetable。system组中的sysservices是用来通过管理节点确定服务支持。at组的attable包含当前活动的IPv4节点和他们相应的MAC地址。IP组的iproutetable是发现网络层拓扑的关键所在。具体来说，iproutenexthop值是路径上下一个路由器的目的地，可通过iproutedest和iproutemask来确定。

类似于MIB-II，生成IPv6网络层拓扑需要IPv6 MIB。ip6routedest，ipv6routepfxlength，ip6nexthop在ip6routetable的作用类似于iproutedest，iproutemask，iproutenexthop在iproutetable中对应的作用。此外，管理器可以从ipv6nettomediatable中得出IPv6地址和MAC地址之间的映射。

子网中的交换机和网桥其工作方式是基于设备的物理地址进行的，对于三层拓扑发现是透明的，所以处于数据链路层的网络设备的发现原理是依据地址转发表来收集拓扑信息的。Bridge MIB记录链路层的管理信息。在dot1dtpfdbtable表中，Dot1dTpFdbAddress表示物理地址，dot1dTpFdbPort表示源数据帧主机通信的端口，dot1dTpFdbStatus表式端口状态，这些都是数据链路拓扑发现的重要部分。

2.2 Internet控制消息协议（ICMP）

相对于SNMP MIB对管理信息的作用，ICMP则便于找出当前网络主机的状态。icmpv4一般用来检测IPv4的主机的活动与否。事实上，所有当前活动的主机会在接到来自一个主机发出的icmpv4响应请求后，都会发出对应的icmpv4响应应答消息。在IPv6中，icmpv6响应请求和响应应答报文类似于icmpv4中的。唯一不同的是，广播在IPv6是不允许的。取而代之的是在整个管理域中使用多播icmpv6报文。具体来说，向被管理的主机发送逆邻居发现报文，无论该地址是否属于管理范围，所有获得这个报文的活动主机都会回应IPv6地址。通过对icmpv4和icmpv6的使用，就可收集所有相关的IP地址。

3 网络拓扑发现的算法

在下文中，将设计包括Ipv6网络层，Ipv4网络层，链路层，以及混合网络转换方式在内的4种算法来进行各个方面网络拓扑发现。

3.1 Ipv6网络层拓扑发现

IPv6网络 层拓扑发现的方法类似于树状结构的广度优先搜索，通过检查所有路径的路由表来发现所有能到达的路由器。首先，把算法执行主机的第一个网关作为一个出发点，通过检查ip6RouteTable来发现所有邻近路由器，然后，在新发现的路由器重复上述过程，直到没有发现新的路由器。执行期间，该算法维持一个名为IP6_TOPO的链表，来存储可到达的路由器信息以及其邻近路由器的信息。图1说明了IP6_TOPO的数据结构，从一个已知的路由器开始，他全部的邻接路由器通过adj指针连接，所有检测到的路由器通过router指针一个接一个地添加。也就是说，IP6_TOPO每一行记录头部路由器相连接的所有邻近路由器，并且每行的头部存储路由器的IP地址。INSERT-ROUTER和INSERT-ADJ，用于增加新发现路由器。该算法的主体如下所示：

1 IP6_TOPO = NULL

2 LIST_ROUTER = NULL

3 QUEUE_IP6_ADDR = NULL

4 ENQUEUE( QUEUE_IP6_ADDR , IPv6 address of a local gateway )

5 while QUEUE_IP6_ADDR ≠ NULL

6 do IP6_ADDR = DEQUEUE( QUEUE_IP6_ADDR )

7 INSERT-ROUTER( IP6_TOPO , IP6_ADDR)

8 LIST_ROUTER LIST_ROUTER ∪ IP6_ADDR

9 for each ROUTER _ADDR ∈ ip6RouteTable in router IP6_ADDR

10 do INSERT-ADJ(IP6_TOPO , ROUTER _ADDR)

11 if ROUTER _IP6_ADDR !∈LIST_ROUTER

12 then ENQUEUE( QUEUE_IP6_ADDR , ROUTER _ADDR )

在这个算法中，LIST_ROUTER保存所有探测到的路由器， QUEUE_IP6_ADDR是一个发现的路由器队列。在第4行中，所有网关的IPv6地址都插入到QUEUE_IP6_ADDR ，它存储所发现路由器的IPv6地址。5到12行循环处理从QUEUE_IP6_ADDR中提取的一个路由器所有邻接的路由器。探测到所有可达路由器后循环将停止。6-8行是从QUEUE_IP6_ADDR提取路由器信息，并存储这个路由器的IPv6地址到IP6_TOPO和LIST_ROUTER 。9-12行是处理所有邻接路由器的一个循环。一旦算法完成后， IP6_TOPO包含IPv6网络拓扑结构必要的信息。

3.2 Ipv4网络层拓扑发现

类似于IP6_TOPO，IP4_TOPO保存发现了的IPv4路由器所有必要的数据。两个数据结构也类似，IP4_TOPO和IP6_TOPO之间的差异在目标MIB的使用方式不同。在算法中除了将IP6_ADDR更换为IP4_ADDR，唯一的变化在第9行中使用ipRouteTable ，而不是ip6RouteTable 。采用此算法，可以得到IP4_TOPO结构，从而建造IPv4的网络层拓扑。

3.3 链路层拓扑发现

链路层拓扑发现的算法可分为两部分：每个交换机直接相连主机的探测，和交换机之间的连接结构。为了发现所有邻接的主机，我们首先计算dot1dTpFdbTable中dot1dTpFdbPort的每个独特值得发生出现次数。dot1dTpFdbPort的每个值对应设备的一个物理端口。如果一个值在dot1dTpFdbPort列中仅出现一次，那么仅有一台主机连接到相应的端口。否则，就有多重IP的主机通过一个或多个交换机连接到这个端口。算法的第一部分说明了每个交换机连接的所有交换机和所有主机。通常我们把一个以太网IP网络视为一个有着根，节点和连接边的树，对应于网关，主机以及对应的内部连接。我们采取了一个自上而下的方法来建立交换机之间的连接关系。从一个位于叶子节点的指定交换机开始，dot1dTpFdbTable表的dot1dTpFdbAddress列包含主机的MAC地址，而不是交换机的，我们向上查找它上层的交换机，或者称为父交换机。直到根交换机被删除才执行结束，从而就发现了交换机间的连接。

在算法的执行过程中，涉及到LINK_TOPO 和 SWITCH_TOPO两个数据结构，LINK_TOPO保存所有交换机直接连接的主机，SWITCH_TOPO则记录所有交换机之间的连接状态。图2说明了LINK_TOPO 的数据结构，SWITCH_TOPO的结构类似于LINK_TOPO，除了将att替换为lnk，LINK_TOPO每一行的头存储一个已经发现交换机的MAC地址。所有直接相连的主机通过att指针来连接，被检测的交换机则由switch指针连接。在SWITCH_TOPO中，只记录交换机的MAC地址。INSERT-SWITCH，INSERT-ATTACH, 和 INSERT-LEAF这三个函数分别用于插入一个新的交换机（在 LINK_TOPO 和SWITCH_TOPO中），一个直接相连的主机（在LINK_TOPO中），和一个孩子交换机（在SWITCH_TOPO中）。

LINK-TOPO在链路层拓扑结构的应用算法可以描述如下：

1 LINK_TOPO = NULL

2 SWITCH_TOPO = NULL

3 QUEUE1_SWITCH = NULL

4 QUEUE2_SWITCH = NULL

5 LIST_SWITCH = NULL

6 LIST_LEAF = NULL

7 ENQUEUE( QUEUE1_SWITCH , MAC address of gateway)

8 ENQUEUE( QUEUE2_SWITCH , MAC address of gateway)

9 while QUEUE1_SWITCH ≠ NULL

10 do MAC_ADDR = DEQUEUE( QUEUE1_SWITCH )

11 INSERT-SWITCH( LINK_TOPO , MAC_ADDR )

12 INSERT-SWITCH( SWITCH_TOPO , MAC_ADDR )

13 for each HOST_ ADDR∈ dot1dTpFdbTable in MAC_ADDR

14 do if HOST_ ADDR is switch and!∈ LIST_SWITCH

15 then ENQUEUE( QUEUE1_SWITCH , HOST_ ADDR )

16 ENQUEUE( QUEUE2_SWITCH , HOST_ ADDR )

17 LIST_SWITCH = LIST_ SWITCH ∪ HOST_ ADDR

18 else if the value of dot1dTpFdbPort in HOST_MAC_ADDR is unique

19 then INSERT-ATTACH( LINK_TOPO , HOST_ ADDR )

20 while QUEUE2_SWITCH ≠ NULL

21 do MAC_ADDR = DEQUEUE( QUEUE2_SWITCH )

22 if all SWITCH_ ADDR in dot1dTpFdbTable in MAC_ADDR!∈ LIST_SWITCH

23 then LIST_SWITCH = LIST_SWITCH － MAC_ADDR

24 LIST_LEAT = LIST_LEAF ∪ MAC_ADDR

25 else if all SWITCH_ ADDR in dot1dTpFdbTable in MAC_ADDR ∈ LIST_LEAF

26 then INSERT-LEAF( SWITCH_TOPO , all SWITCH_ ADDR )

27 LIST_LEAF = LIST_LEAF－ all SWITCH_ ADDR

28 else ENQUEUE( QUEUE2_SWITCH , MAC_ADDR )

在此算法中，QUEUE1_SWITCH 和QUEUE2_SWITCH是进行处理的迭代交换机队列，LIST_SWITCH包含所有已经发现的交换机。网关的MAC地址一旦插入到QUEUE1_SWITCH 和 QUEUE2_SWITCH，则9到19行的while循环用来检测每一个交换机所有的直接连接主机。dot1dTpFdbTable的dot1dTpFdbPort 同样值的数量反应了连接这一端口的主机数量，如果该值是独一无二的，它表明只有一台主机连接到端口。检测完所有发现交换机后循环停止，主机和交换机的连接信息保存在LINK_TOPO。处于20到28行的while循环是用来建立所有交换机之间的连接。22到24行是如果交换机是树上的叶子节点就删除交换机。25到27行处理所有交换机叶节点。如果交换机的状态仍然未知，它将被再次插入到QUEUE2_SWITCH。这个循环当所有交换机被访问时结束，从而连接状态储存在SWITCH_TOPO 中。结合LINK_TOPO和SWITCH_TOPO 两个数据结构，就可以提出一个链路层拓扑。

3.4 转换方式发现

为了结合IPv6与IPv4网络层拓扑图，应该首先发现双重地址主机或路由器。因此，一个检测IPv6转换方式的算法是必要的。通过多播IPv6的逆邻居发现报文和广播IPv4的 RARP报文，分析应答消息可以获得所有与MAC地址对应的IP地址。通过分析收集到的所有IP地址的格式，就可以建立MAC地址和其相关IP地址的对应关系。执行期间，该算法有个名为 MAC_IP的连接链表，用于储存所有IP地址相应的MAC地址。图3说明了MAC_IP的数据结构，每行的头节点存储了一个处理范围内的MAC地址。如图3所示，所有与此MAC相关的IP地址都通过IP指针连接 ，而所有MAC地址通过每个节点的mac指针连接，INSERT-MAC 和 INSERT-IP函数是分别用来增加的一个新的MAC地址和IP地址。

TRANS_DET算法，使用MAC_IP结构，以确定使用哪个转换机制，如下:

1 MAC_IP=NIL

2 QUEUE_MAC = NULL

3 Broadcasting ICMPv4 echo request

4 for each MAC_ADDR in atTable of gateway

5 ENQUEUE( QUEUE_MAC , MAC_ADDR )

6 while QUEUE_MAC ≠ NULL

7 do MAC_ADDR = DEQUEUE( QUEUE_MAC )

8 INSERT-MAC( MAC_IP , MAC_ ADDR )

9 Multicasting IPv6 Inverse Neighbor Solicitation message

10 Broadcasting IPv4 RARP requests

11 for each replied message

12 do INSERT-IP( MAC_IP , all IP addresses in replied message )

首先，MAC_IP数据结构和QUEUE_MAC队列中在TRANS-DET算法里初始化。QUEUE_MAC维持所有从最初网关中atTable获得的MAC地址。唯一的while循环检查所有存储在QUEUE_MAC队列的MAC地址。第7行将MAC插入到MAC_IP中，8到9行发送IPv6逆邻居请求消息和IPv4的RARP请求消息。检测应答消息,获得所有后来插入到MAC_IP的IP地址。通过分析主机的IP地址，来建立MAC地址和IP地址的转换方式。因此，无论路由器或主机， IPv6与IPv4网络的重叠部分都将被发现。从而，就可以得出IPv6与IPv4网络的拓扑共存图。

4 小结

本文主要论述了网管系统中一个重要部分：网络拓扑发现的算法研究。提出IPv6-only和 IPv4-only的网络层拓扑发现算法，一个数据链路层拓扑发现算法以及一个在共存的网络中的转换探测算法。网络层拓扑构造使用ip6routetable和iproutetable中的路由信息，而数据链路层采用atTable和dot1dtpfdbtable中数据来创建。转换探测通过收集和分析两个IP版本整个IP地址来实施，在其中通过使用逆ipv6多播邻居发现报文和ipv4 RARP的广播报文。来找出在共存网络部署哪种转换方式。因此，路由器和主机的重叠可以判定来完成IP网络拓扑发现。

参考文献：

[1] 汪浩,张尧弼,马月玲.以太网物理拓扑发现算法[J].微型电脑应用,2007,23(5).

[2] Spring N,Mahajan R,Wetherall D,et al.Measuring ISP topologies Rocketfuel[J].IEEE/ACM Transactions on Networking,2004,12(1):2-16.

[3] Breitbart Y,Garofalakis M,Jai B,et al.Topology discovery in heterogeneous IP networks: the NetInventory system[J]. IEEE/ACM Transactions on Networking,2004,12(3):401-414.

[4] Astic I,FestorO.A hierarchical topology discovery service for IPv6 networks[J].Network Operations and Management Symposium,2002:497-510.

[5] IPv6 Network Topology Discovery System -Dolphin[EB/OL]./ipv6/210.25.133.26/default.php.

[6] 王志刚,王汝传,王绍棣,等.网络拓扑发现算法的研究[J].通信学报,2004,25(8):36-43.

[7] 熊坤,寇晓蕤,范元书,等.网络拓扑发现算法定性分析[J].计算机工程与应用,2004(14):136-137.

[8] 黄晓波,潘雪增.网络拓扑发现的算法和实现[J].计算机应用与软件,2007(7):159-161.