基于traceroute的互联网拓扑关键节点发现机制研究

发布时间：2018-04-10 13:43

本文选题：网络测量 + 互联网拓扑　；参考：《北京邮电大学》2017年硕士论文

【摘要】：随着互联网技术的不断发展,由互联网基础设施相互连接所构成的互联网拓扑日趋复杂化。研究表明,互联网拓扑具有无标度的统计特性。这使得互联网对网络蓄意攻击具有脆弱性,即破坏少数几个特定节点可以对网络的整体性能产生重大影响。因此,找出网络中的关键节点在网络安全、网络管理、网络优化等方面都具有十分重要的意义。在已有的关于复杂网络中关键节点发现算法的研究中,一类算法基于显著性等价于重要性的思想,即通过网络中节点的中心性指标来刻画节点的重要程度。另一类算法基于破坏性等价于重要性的思想,即通过计算网络中某节点的失效对网络性能的影响程度来衡量该节点的重要性。然而,这些算法缺乏对网络实际运行数据的考虑,从而使得算法脱离了网络实际应用场景。本课题在已有研究成果的基础上,基于破坏性等价于重要性的思想,提出了一种新的互联网拓扑关键节点发现算法。该算法将互联网中的链路时延与负载等真实运行数据加入到关键节点发现算法中,并模拟了路由器对数据传递路径进行重新规划。本课题首先通过traceroute测量数据对路由级互联网拓扑进行构建,并从traceroute测量数据中提取了链路时延与链路负载数据。之后,利用本课题提出的关键节点发现算法对互联网拓扑中节点的关键度进行计算,从而实现关键节点的发现。通过分析发现,该算法的时间复杂度为O(n3),高于部分基于显著性等价于重要性算法,低于基于破坏性等价于重要性的级联失效算法。此外,该算法可识别出网络中负载大但重要度低的节点,因此,本课题提出的关键节点发现算法相比于通过节点负载衡量节点重要性的关键节点发现算法在结果准确性上有所提高。
[Abstract]:With the continuous development of Internet technology, the Internet topology composed of Internet infrastructure interconnection is becoming more and more complicated.The research shows that the Internet topology has scale-free statistical properties.This makes the Internet vulnerable to deliberate network attacks, that is, the destruction of a few specific nodes can have a significant impact on the overall performance of the network.Therefore, it is very important to find out the key nodes in the network security, network management, network optimization and so on.In the existing research on key node discovery algorithms in complex networks, a class of algorithms based on the idea that salience is equivalent to importance, that is, to depict the importance of nodes by the central index of nodes in the network.The other algorithm is based on the idea that the damage is equivalent to the importance, that is, the importance of a node is measured by calculating the influence of the failure of a node on the performance of the network.However, these algorithms lack the consideration of the actual running data of the network, so that the algorithm is divorced from the network practical application scenario.Based on the existing research results and the idea of destructiveness equivalent to importance, a new algorithm for discovering the key nodes of Internet topology is proposed in this paper.In this algorithm, the real running data such as link delay and load in the Internet are added to the key node discovery algorithm, and the router is simulated to replan the data transfer path.Firstly, the routing level Internet topology is constructed by traceroute measurement data, and the link delay and link load data are extracted from the traceroute measurement data.After that, the key node discovery algorithm proposed in this paper is used to calculate the critical degree of nodes in the Internet topology, so as to realize the discovery of key nodes.It is found that the time complexity of the algorithm is more than that of the importance algorithm based partly on salience and the cascade failure algorithm based on the destructive equivalence of importance.In addition, the algorithm can identify the nodes in the network with high load but low importance, so,The key node discovery algorithm proposed in this paper is more accurate than the key node discovery algorithm, which measures the importance of nodes by node load.
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.02

【相似文献】