一种并行网络拓扑发现方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN107404411A(43)申请公布日2017.11.28(21)申请号201710810497.7(22)申请日2017.09.11(71)申请人哈尔滨工程大学地址150001黑龙江省哈尔滨市南岗区南通大街145号哈尔滨工程大学科技处知识产权办公室(72)发明人玄世昌苘大鹏王巍朱新立靳小鹏郁晨张超张宁(51)Int.Cl.H04L12/24(2006.01)权利要求书2页说明书4页附图3页(54)发明名称一种并行网络拓扑发现方法(57)摘要本发明公开了一种并行网络拓扑发现方法，主要涉及网络拓扑发现领域。其中主要包括并行拓扑发现和动态轮转模式两部分；并行拓扑发现主要是由预处理模块和路由探测模块组成。在预处理模块和路由探测模块之间通过循环队列进行共享数据。预处理模块和路由探测模块是并行执行的。本发明通过改变共享全局停止集的方式来减少探测源间通信量，并在拓扑发现过程中加入随机验证算法和并行探测机制来提高拓扑发现完整度和探测效率。在不同的网络拓扑环境下的实验结果表明，改进的拓扑发现方法比Doubletree方法提高了探测效率和完整性，同时减少了探测源间共享全局停止集产生的通信量。因此，改进的拓扑发现方法在网络拓扑发现上有较高的性能。CN107404411ACN107404411A权利要求书1/2页1.一种并行网络拓扑发现方法包括并行拓扑发现和动态轮转模式，其中动态轮转模式是用来实施并行拓扑发现的；拓扑发现其中是通过如下步骤实现的：步骤一：在预处理模块从探测目的集中选取一个探测目的节点；步骤二：进行主机探测，计算出探测源节点机到探测目的节点的总跳数；步骤三：将目的节点、TTL值、探测标志以结构体的形式保存到循环队列中；并进入由初始探测模块、交换探测模块和任务调度模块组成的路由探测模块；步骤四：在初始探测模块中使用改进的折半查找算法定位出最小的未探测节点min；步骤五：通过任务调度模块使用多线程对未探测节点进行并行探测，探测的结果保存在临时停止集中；步骤六：将临时停止集中的路由器节点以目的节点，中间路由器节点形式拷贝到全局停止集中，将TTL值小于等于h/2的路由器节点以中间路由器节点保存到本地停止集，将TTL值大于等于h/2的路由器节点以中间路由器节点，TTL保存到本地停止集；步骤七：清空临时停止集，释放临时停止集所占的空间；步骤八：在交换探测模块中发送TTL等于h/2值的探测数据包，等待响应报文并从中获取路由器的接口mid，如果目的节点，路由器接口mid在全局停止集中，则说明第二部分和第三部分的路径已经被探测过，在第二部分和第三部分使用随机验证算法进行验证，转到步骤九；否则转到步骤十；步骤九：如果路由器接口mid在本地停止集中，则说明第一部分的路径已经被探测过，使用随机验证算法对第一部分进行验证，转到步骤十三；否则使用TTL以h/2递减的方式向后进行探测，转到步骤十三；步骤十：如果路由器接口mid在本地停止集中，则说明第一部分的路径已经被探测过，对第一部分使用随机验证算法进行验证，转到步骤四；否则在第一部分使用改进的折半查找算法找到最小的未探测节点min，转到步骤十一；步骤十一：探测源发送TTL为3h/4值的探测数据包，等待响应报文并从中获取路由器的接口mid2，如果目的节点，路由器接口mid2在全局停止集中，则说明第三部分的路径已经被探测过，则使用TTL以h/2递增的方式向前进行探测，之后在第三部分使用随机验证算法进行验证，转到步骤十三；否则转到步骤十二；步骤十二：如果路由器接口mid，TTL和路由器接口mid2，TTL同时都本地停止集中，则在第二部分使用随机验证算法进行验证，之后使用TTL以3h/4递增的方式向前进行探测，转到步骤十三；否则使用TTL以3h/4递增的方式向前进行探测，转到步骤十三；步骤十三：通过任务调度模块使用多线程对未探测节点进行并行探测，探测的结果保存在临时停止集中；然后将临时停止集中的路由器节点以目的节点，中间路由器节点形式拷贝到全局停止集中，将TTL值小于等于h/2的路由器节点以中间路由器节点形式保存到本地停止集，将TTL值大于等于h/2小于等于3h/4之间的路由器节点以中间路由器节点，TTL形式保存到本地停止集；最后清空临时停止集，释放临时停止集所占的空间。2.根据权利要求1所述的一种并行网络拓扑发现方法，其特征在于，所述的动态轮转模式实施方式流程如下所示：步骤一：初始探测时，总控节点机给所有的探测源节点机发送探测指令，并指定探测源Si节点机应该探测的目的集分组Di，所有探测源Si节点机并行的探测相应的目的集Di分组；2CN107404411A权利要求书2/2页当探测源节点机Si探测完成相应目的集Di分组中的所有目的节点后，探测