Dynamic Network Routing Protocols

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.