论文摘要
由于互联网的复杂性、异构性等问题严重制约互联网行为的研究,网络模拟就成为了研究Internet的重要手段。网络拓扑数据作为网络模拟的基础数据,其真实性直接影响模拟的真实性。所以,真实而准确的网络拓扑数据是网络模拟的必要准备。网络模拟所用的拓扑数据全部来源于拓扑测量,然而,由于拓扑测量技术的不完善及其他各种因素(丢包、保密区域、路由器不响应等)的影响,拓扑测量得到的拓扑图通常并不连通,为了使网络模拟更具真实性、提高模拟规模、并为拓扑划分提供依据,有必要对网络拓扑进行连通性恢复。本文主要研究Internet拓扑性质,根据Internet拓扑性质设计恢复算法。对Internet拓扑性质的描述,以复杂网络理论为基础,其若干基本概念(介数、平均路径长度、聚集系数等)已经很好的应用于描述拓扑性质。网络拓扑分为自治域级网络拓扑和路由器级网络拓扑,本文研究对象为路由器级网络拓扑。恢复路由器级网络拓扑的连通性,不仅要研究拓扑性质,也要研究网络建设的基本原则。本文提出三种候选节点选择方案,两种拓扑连通性恢复算法。节点的“所属地”属性说明网络拓扑中并不是每个节点都具有连接的资格。候选节点作为有资格连接的节点,选择依据有三个:网络建设因素、地理位置因素、规模因素。根据这三个因素确定候选节点。基于小世界现象的网络拓扑连通性恢复算法:以Internet展示的小世界现象为基础,结合网络建设的基本原则,对关键节点进行连接操作,通过定义阈值控制边数。该算法适用于两个连通分支规模相近或都很大的情况。基于分层的网络拓扑连通性恢复算法:以拓扑的层次结构为基础。首先对拓扑分层,然后统计、分析拓扑层次数据,根据分析结果进行连接操作。该算法适用于连通分支规模相差悬殊的情况。实验结果表明两种算法都很好的完成了拓扑连通性的恢复。