几类网络模型及路由算法研究

【作者】 杜艳；

【导师】 刘方爱；

【作者基本信息】 山东师范大学 ， 计算机应用技术， 2011， 硕士

【摘要】 目前,随着互连网络、复杂网络等网络技术的快速发展,网络模型及其通信效率已成为各领域的研究热点,尤其是在高性能计算、网格计算等方面。网络技术的不断创新使得各种拓扑结构的网络模型应运而生,为资源传输、资源共享、资源副本等关键技术的研究奠定了基础。同时,在不同的网络结构中需要不同的通信模式以实现路由通信,如何高效的实现这些通信模式是目前学术界研究的重要课题之一。而网络中的通信效率直接依赖于不同路由算法的效率,因此在不同的网络拓扑结构下,研究如何高效的实现各种通信模式的路由算法具有十分重要的理论和现实意义。本文即针对不同的网络应用,在构造网络模型拓扑结构的同时,分析讨论了在不同路由算法的基础上网络通信效率的问题。在对各种网络模型和路由算法研究的基础上,本文的主要研究内容及创新点如下:首先,综述了互连网络模型的拓扑性质和路由通信算法。针对互连网络,在互连网络的发展概况基础上,介绍了互连网络的特性和性能参数,讨论了互连网络中的几种常见网络模型,分析了互连网络中的通信路由算法。其次,讨论了P2P网络中的网络模型及经典路由机制。针对P2P网络,总结了P2P网络的发展历史和研究现状,在P2P网络与传统的C/S模式比较的基础上,分析了P2P网络的特点和优势,讨论了基于P2P网络的几种结构化网络模型的路由机制,总结了结构化P2P网络路由算法研究面临的主要问题。再次,提出了一种规则的互连网络模型层次双环网络HDRN(k),讨论了其路由算法。基于层次环结构和双环网络的概念和性质,嵌入Petersen图构造了一类层次双环网络模型HDRN(k),讨论了HDRN(k)网络的路由性质,设计了点点路由和Broadcast路由算法,证实了HDRN(k)网络是一种具有良好拓扑结构、高效路由通信的互连网络模型。接着,仿真模拟了层次双环网络HDRN(k)的性能和路由通信效率,利用NS2网络模拟器研究了其数据包成功接收率、端到端延时以及路由开销等问题。针对网络模型及路由算法的仿真模拟,总结了目前仿真模拟实验的基础知识,分析比较了几种网络仿真模拟工具,重点分析了NS2网络模拟器的特点、安装调试过程以及仿真步骤。最后,在以上规则网络模型拓扑结构的研究基础上,讨论了复杂网络的演化模型,为进一步将复杂网络演化模型应用到实际网络中奠定了理论基础。针对复杂网络,综述了复杂网络的发展、应用及研究意义,阐述了复杂网络的基础知识,重点讨论了几种复杂网络的演化模型。更多还原

【Abstract】 Nowadays, with the rapid development of the network technologies, such as interconnection network, complex network, network model and its communication efficiency have become the research focuses, especially in high-performance computing and grid computing. Due to the innovation of the network technologies, network models with different topologies are proposed, establishing a foundation for the research of key technologies, like resource transfer, resource sharing, resource copies. Meanwhile, in order to implement routing communication, different communicating models are used in different networks. So how to realize such communication modes efficiently is an important subject for research. The communication efficiency in the network depends on the efficiency of routing algorithm, so study on routing algorithms of different communication modes under different topologies has important theoretical and realistic significance.This paper constructed different network models for different network applications, and analyzed the network communication efficiency based on different routing algorithms. A variety of network models and routing algorithms are researched in this paper and the main contents and innovations are as follows:Firstly, the topologies and routing communication algorithms of the interconnection network are summarized. For the interconnection network, this paper summarized the development of its topologies, described its characteristics and parameters, and then focused on discussing several common network models and routing communication algorithms. Secondly, several network models and classical routing algorithms of the P2P network are discussed. For P2P network, this paper gives an overview of its research status and history, and then the advantages of the P2P network are given out based on the comparison between P2P networks and traditional C/S model. After the discussion of several routing mechanisms in P2P networks, several issues in the research of structured P2P network routing algorithms are proposed.Thirdly, a kind of ruled interconnection network model is established and its routing algorithms are discussed. HDRN (k) is proposed on the basis of hierarchical interconnection networks. The construction and properties of HDRN (k) are investigated. Then, the routing strategies of HDRN (k) are discussed and two routing algorithms, point-to-point and broadcast, are designed. It is proved that HDRN (k) is a new kind of network, with good topological properties and high communication efficiency.Then, the performance and routing efficiency of HDRN (k) are simulated. NS2 simulator is utilized to research its rate of successfully received data packets, end to end delay, network overhead and other issues. According to the simulation of the network models and routing algorithms, this paper summarizes the current knowledge of simulation experiments, analyzes several network simulation tools and emphasizes on the analysis of NS2 simulator’s characteristic and step.Finally, based on the research of the above-mentioned ruled network’s topologies, complex network’s evolution model is discussed, which established the foundation for the further research. For complex network, this paper introduces its development, application and significance, sums up its basic knowledge, and then emphasizes on the discussion of several revolution model.更多还原