Relationships between network parameters and the performance of distributed adaptive-routing algorithms using learning automata in packet-switched datagram networks
Soon L. Lim, Richard E. Newman-Wolfe · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1992
Large computer networks with dynamic links present special problems in adaptive routing. If the rate of change in the network links is fairly rapid and the changes are nonperiodic, then obtaining the optimal solution for adaptive routing becomes complex and expensive. In addition to the academic value of the solution, the growth of computer networks gives the problem practical importance. Learning automata is logical approach to the above problem. With the right parameter values, learning automata can converge arbitrarily close to the solution for a given network topology and set of conditions. The adaptability of automata reduces the depth of analysis needed for network behavior; the survivability and robustness of the network is also enhanced. Finally, each automaton behaves independently, making automata ideal for distributed decision-making, and minimizing the need for inter-node communication. Previous work on automata and network routing do not address how changes in network parameter values affect the performance of automata-based adaptive routing. Such knowledge is essential if we are to determine the suitability of an automata-based routing algorithm for a given network. Our paper focuses on this question and shows that in packet- switched datagram networks, relationships do indeed exist between network parameters and the performance of distributed adaptive routing algorithms. Additionally, our paper compares the performance and behavior of several types of learning automata, as well as changes in automata behavior over a range of reward and penalty values. Finally, the performance of two automata-based adaptive routing algorithms is compared. Our automaton model is a stochastic, linear, S-model automaton. In other words, the automaton's matrix of action probabilities changes as a result of performance feedback which it receives from the environment, the response to environment feedback is linear, and finally, the feedback it receives from the environment is over a continuous interval.© (1992) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.