Routing in Packet-Switched Networks Using Path-Finding Algorithms.

摘要

Route assignment is one of the operational problems of a communication network. The function of a routing algorithm is to guide packets through the communication network to their correct destinations. This dissertation is on the design and analysis of distributed, adaptive routing algorithms and protocols for packet switching networks. We introduce the general framework on which these algorithms are based. Using this general model, we propose several routing techniques to suit heterogeneous environments. In this dissertation, we concentrate on distance-vector algorithms. One important drawback of previous distance-vector algorithms based on the distributed Bellman-Ford algorithm for shortest-path computation is that they suffer from counting-to-infinity problem and the bouncing effect. Recently, distributed shortest-path algorithms which utilize information about distance and second-to- last hop along the shortest-path to each destination have been proposed. This class of algorithms are called path-finding algorithms. Our proposals are based on path-finding algorithms.