基于MapReduce的互联网拓扑特征参数算法研究

摘要

In order to improve the efficiency of the traditional single machine algorithms in computing Internet topological parameters,we used MapReduce to study the Internet topological parameters algorithms.Through discussing the difficulties of parallelizing the traditional algorithms,this paper gave the concurrent design discipline of graph algorithms based on MapReduce and presented the message passing mechanism of graph algorithms.We designed and improved parallel algorithms to compute 4 topological parameters by using message passing mechanism.The experimental results show that the proposed MapReduce algorithm effectively improves the efficiency,and has a good scalability.%针对传统单机算法在计算大规模互联网拓扑特征参数时效率低的问题,基于MapReduce分布式计算框架对网络拓扑特征参数算法进行研究.通过分析单机图算法并行移植时存在的问题,提出了图算法并行化设计的原则和消息传递机制;根据设计原则和消息传递机制,为4个网络拓扑参数设计了并行算法.实验证明,并行的拓扑参数算法能够有效提高计算效率,且具备良好的可扩展性.