IPv6网络路由器级拓扑发现方法

摘要

本发明涉及计算机网络管理技术领域，公开了一种IPv6网络路由器级拓扑发现方法，包括以下步骤：A1、基于OSPF协议进行拓扑发现；A2、基于traceroute6进行拓扑发现；A3、将步骤A1与A2的结果进行整合。本发明综合了基于OSPF协议的拓扑发现方法与基于traceroute6的拓扑发现方法进行设计。实验表明，使用该方法发现结果准确率、节点、链路覆盖率均为100%。对于基于OSPF协议获取的拓扑图节点的IPv6地址信息进行了有效的补充，整合地址信息的准确率为100%，整合时间<1s。

主权项

一种IPv6网络路由器级拓扑发现方法，其特征在于，包括以下步骤： A1、基于OSPF协议进行拓扑发现，其具体步骤包括： 步骤1.1.在服务器上实现OSPF协议，并使所述服务器与一台被管网络路由器建立紧邻关系，监听网络中洪泛的LSA报文； 步骤1.2.根据监听得到的LSA报文，获得网络中各路由器节点之间的连接关系，将得到的拓扑连接图记为G_A，其中的路由器节点用id标识； 步骤1.3.由步骤1.1中的LSA报文中提取出的配置了Loopback state接口的路由器的id与其ip的匹配关系以及配置基于OSPF协议拓扑发现所需的路由器id与其ip的匹配关系构成集合Mapped，以及id与集合Mapped对应的子网前缀的匹配集合N；若集合Mapped覆盖了全部id，则将id替换为IPv6地址，拓扑发现结束；若集合Mapped未覆盖全部id，则继续执行步骤A2；若Mapped集合为空集，将与所述服务器紧邻的路由器的id与ip的对应关系加入集合Mapped； A2、基于traceroute6进行拓扑发现，其具体步骤包括： 以所述服务器为源点进行单点的traceroute拓扑测量，将得到的拓扑连接图记为G_B，测量的目标地址集通过人工配置或者利用步骤A1的拓扑发现结果中集合N中的子网前缀自动生成； A3、以OSPF协议信息作为启发式条件根据步骤A1与A2结果中的拓扑图特征，将步骤A1与A2的结果进行整合，其具体步骤包括： 步骤3.1.参数初始化： 步骤3.1.1.对于集合Mapped，从中取出已经完成匹配的ip加入集合S1，并从中取出其中已经完成匹配的id加入集合S2； 步骤3.1.2.对照集合S1，将未完成匹配的ip加入集合IPList； 步骤3.1.3.对于G_A中的每个节点，计算其连接度数，加入集合DegreeId；对于G_B当中的每个节点，统计其连接度数，加入集合DegreeIp； 步骤3.1.4.对于G_A中的每个节点inode，依次执行步骤3.1.4.1～3.1.4.2： 步骤3.1.4.1.将节点inode加入队列nodelist，并将inode标记为已访问，并且在inode之后加入一个标记节点tnode用于计算节点之间的距离，初始化s为0，s表示节点之间的距离； 步骤3.1.4.2.如果nodelist不为空，则循环执行步骤3.1.4.2.1～3.1.4.2.3： 步骤3.1.4.2.1.按照先入先出的顺序从nodelist取出一个节点jnode； 步骤3.1.4.2.2.如果jnode是G_A中的节点，则节点inode与节点jnode之间的最短距离为s，将此最短距离信息加入集合DistanceId，并将jnode的所有未被访问过的邻居节点加入nodelist，然后标记这些未被访问过的邻居节点为已访问； 步骤3.1.4.2.3.如果jnode是标记节点tnode，且此时nodelist队列为空，则结束步骤3.1.4；如果此时队列不为空，则将标记节点tnode放回序列nodelist，并且将s加1； 步骤3.1.5.对于G_B中的每个节点inode，做与步骤3.1.4中相同的操作，将各个节点之间的距离存入集合DistanceIp； 步骤3.1.6.将循环标记变量Flag置为1； 步骤3.2.当Flag为1时，循环执行步骤3.2.1～3.2.2： 步骤3.2.1.将Flag置为0； 步骤3.2.2.对于集合S1中的每一个元素IP_i，i为集合中 元素的序号，依次执行步骤3.2.2.1～3.2.2.3： 步骤3.2.2.1.从集合Mapped中取出IP_i对应的ID_i，ID _i表示与IP_i对应的路由器的id信息； 步骤3.2.2.2.对于步骤A1的拓扑发现结果中每一个不属于集合S2的路由器标识ID_k,执行步骤3.2.2.2.1： 步骤3.2.2.2.1.对于集合IPList中的每一个元素IP_c，执行步骤3.2.2.2.1.1： 步骤3.2.2.2.1.1.如果集合DistanceIp中IP_i与IP_c之间的距离大于或等于集合DistanceId中ID_i与ID_k之间的距离并且度数集合DegreeId中节点k的度数大于或等于DegreeIp中节点c的度数则将ID_k作为一个IP_c可能的匹配加入IP_c的序列MapListB；步骤3.2.2.3.对于每一个IPList中的元素IP_h，依次执行步骤3.2.2.3.1～3.2.2.3.2： 步骤3.2.2.3.1.合并IP_h的MapListA与MapListB，若其MapListA不为空，使MapListA取MapListA与MapListB元素的交集，同时将MapListB置为空集；如果MapListA为空集，则将MapListB所有元素加入MapListA，同时将MapListB置为空集； 步骤3.2.2.3.2.如果IP_h的MapListA所含元素个数为1，则依次执行步骤3.2.2.3.2.1～3.2.2.3.2.5； 步骤3.2.2.3.2.1.将IP_h加入集合S1； 步骤3.2.2.3.2.2.将IP_h的MapListA所含的唯一元素ID_h加入集合S2； 步骤3.2.2.3.2.3.将IP_h从IPList中删除； 步骤3.2.2.3.2.4.将IP_h与ID_h的对应信息加入集合Mapped； 步骤3.2.2.3.2.5.将Flag置为1； 步骤3.3.对于S1中所有元素IP_i，依次执行步骤3.3.1～3.3.2： 步骤3.3.1.从集合Mapped中，取出与IP_i对应的id信息ID_i； 步骤3.3.2.将G_A中对应的ID_i用IP_i代替； 步骤3.4.输出经过处理的G_A。