基于网络模拟的拓扑划分评价模型研究-计算机科学与技术专业论文.docxVIP

Classified Index: TP393.08 U.D.C: 681.3.06 Dissertation for the Master Degree in Engineering RESEARCH ON AN EVALUATION MODEL FOR TOPOLOGY PARTITIONING BASED ON NETWORK SIMULATION Candidate： Ge Wentang Supervisor： Prof. Li Bin Academic Degree Applied for： Master of Engineering Specialty： Computer Science and Technology Affiliation： School of Computer Science and Technology Date of Defence： July, 2012 Degree-Conferring-Institution： Harbin Institute of Technology 哈尔滨工业大学工学硕士学位论文 哈尔滨工业大学工学硕士学位论文 - - I - 摘 要 随着互联网的迅速发展，网络规模急剧增大，结构日趋复杂，大规模网络 已经成为网络研究的热点。网络模拟能够研究复杂网络行为，评价尚未实施的 网络协议，具有成本低，易使用、模拟真实性较高等优点，因此网络模拟得到 了广泛的应用。大规模的网络模拟需要巨大的计算开销，由于硬件资源的限制， 单机模拟已经无法满足大规模网络模拟的需求。并行离散事件模拟技术已经成 为研究大规模网络模拟的重要手段。并行网络模拟的一个重要的研究内容是如 何合理的分配模拟任务，保证负载均衡，以减少模拟运行时间，降低模拟资源 消耗，进而提高模拟性能。 并行网络模拟的任务分配通常采用拓扑划分的方式来实现，本文致力于研 究并行网络模拟中的拓扑划分及其评价方法，主要内容包含如下三部分： 第一，本文从并行离散事件模拟机制出发，综合分析了影响模拟性能的各 种因素，并进行归纳分类，它们包括模拟软硬件环境、模拟任务和拓扑划分结 果。受拓扑划分影响的因素主要包括负载均衡因素、远程通信开销因素和同步 周期因素。 第二，目前的任务划分方法仅从影响模拟性能的部分因素出发，本文采用 基于图的划分算法，对模拟效率的提高有限，而且缺少评价拓扑划分结果优劣 的方法。鉴于此，以模拟运行时间为评价拓扑划分结果优劣的标准，提出了计 算负载均衡因素、远程通信开销因素和同步周期因素对模拟性能影响程度的方 法，建立了基于模拟运行时间的拓扑划分评价模型。使用 PDNS 模拟器进行 DDoS 模拟，对比模型计算值与实验值，发现二者误差在 5%~10%之间，验证 了模型的准确性 ；以 METIS 算法和子网 消减划分算 法为例进行评 价，发 现 METIS 算法评价值比子网消减算法高约 13%，与实验结果相符，验证了模型 的有效性。 第三，鉴于 METIS 等图划分工具存在易陷入局部最优的不足，本文提出 并实现了基于时间消耗评价的拓扑划分优化方法，该方法以拓扑划分评价模型 为指 导 ，从 负 载均 衡 因素 、 远程通 信 开销 因 素和 同 步周 期 因素 三 个方 面 对 METIS 的划分结果进行了优化，解决了局部最优的缺陷。实验结果证明，该 方法能够有效地提高并行网络模拟性能，平均约为 20%。 关键词：并行模拟；拓扑划分；评价模型；模拟运行时间；优化划分方法 - - II - Abstract With the rapid development of the Internet, the scale of network increases rapidly, and the structure becomes more complicated, large-scale network has become a hot topic of network research. N etwork simulation can do research into complex network behaviors and evaluate implemented network protocols. It has several advantages, such as low cost, easy to use and high simulation authenticity, so it has been widely used. Large-scale network simulation requires huge computational overhead, because of hardwar