Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS
Pagination or Media Count:
Several proposed routing algorithms for store and forward communication networks, including one currently under implementation in the ARPANET, route messages along shortest paths computed by using some set of link lengths. When these lengths depend on current traffic conditions as they must in an adaptive algorithm, dynamic behavior questions such as stability, convergence, and speed of convergence are of interest. This paper is the first attempt to analyze systematically these issues. It is shown that minimum queuing delay path algorithms tend to exhibit violent oscillatory behavior in the absence of a damping mechanism. Several easily implementable damping schemes are proposed and analyzed by using nonlinear stability theory techniques.
- Statistics and Probability
- Computer Systems
- Non-Radio Communications