动态网络路由协议研究

【作者】 瞿晓高；

【导师】 谭国真；

【作者基本信息】 大连理工大学 ， 计算机应用技术， 2003， 硕士

【摘要】 随着互联网络技术的高速发展，网络上传输的数据流无论从数量上还是从类型上都飞速增长，仅仅从硬件上提高网络性能已经不能适应网络发展的需要。因此，从算法的角度上进一步提高网络的效率就成了一个迫切的问题。 网络路由算法对于网络整体效率有着非常大的影响。传统的网络路由协议是利用静态网络模型和传统的最优路径理论设计的，不能描述网络系统的动态特性和结点的不同类型。因此，运用动态网络模型，采取合适的路由策略，用动态的观点来研究路由协议，从而提高网络的整体性能的研究工作受到了广泛的关注。本文在分析传统路由协议和当前国际上对动态网络路由算法的研究基础上，提出了时间依赖的混合型网络模型(Heterogeneous Time Dependent Network，简称为HTDN模型)，该模型可以有效地描述网络中链路权值随时间变化的特性，网络中不同的结点可以采用不同的等待策略；并证明了HTDN模型中最优路径的共同特性。在此基础上设计了有效的分布式路由协议——DMDRP协议，然后从理论上证明了该协议的正确性，并分析了协议的复杂性，通过实例证明了协议的有效性。 利用网络中数据包生存时间有限的特点，对路径总长度进行限制，本文实现了有环时间依赖网络中的最短路径算法，获得的最短路径可以包括环路，也可以不包括环路。 在此基础上，本文还设计了在离散随机时间依赖网络模型中考虑结点处等待的期望最短路径算法，并给出了实例分析，为今后在随机时间依赖网络中计算期望最短路径的分布式路由协议的研究作了前期工作。更多还原

【Abstract】 The inter-network technology is developing faster and faster. Exploding data flows require the network to significantly improve its efficiency.Routing algorithm is a key issue for the network. Traditional and standard network routing protocols followed static network models and classical optimal path theories. So they could describe neither the dynamic characters nor the heterogeneous nodes in the network. As a result, it becomes a focused area to apply dynamic network models and various routing strategies to research on the routing algorithms and protocols in dynamic view. Based on the analysis of traditional and standard routing protocols, as well as the research background of routing algorithms and protocols for dynamic networks, this thesis proposes a Heterogeneous Time Dependent Network (HTDN) model. It can efficiently describe the time-varying link weights and different waiting strategies of nodes. The similarity of the optimal path in HTDN model is also proved. Based on that, an efficient distributed routing protocol, DMDRP protocol for HTDN, is proposed. Then the correctness of this protocol is proved. The complexities of this protocol are also analyzed. Experimental result also shows the efficiency of DMDRP protocol.In this paper, the length of path is limited based on the fact that datagrams in actual network have limited living time. Then a shortest path algorithm for cyclic time dependent network is proposed. The obtained shortes path may be acyclic or cyclic.In addition, an expected shortest path algorithm for discrete stochastic time dependent network model is also proposed in this thesis. The properties of this algorithm are analyzed, together with an experimental result. Some prophase research works are finished for the purpose of designing a distributed routing protocol to obtain the expected shortest path in stochastic time dependent network.更多还原