DocumentCode :
3046343
Title :
Distributed routing in computer communication networks
Author :
Schwartz, M. ; Tak-Kin Yum
Author_Institution :
Columbia University, New York, NY
fYear :
1982
fDate :
8-10 Dec. 1982
Firstpage :
600
Lastpage :
603
Abstract :
This paper considers a class of simple distributed shortest-path routing algorithms first introduced in the ARPA Network with convergence for fixed cost functions proven by W.D. Tajibnapis. The basic algorithm has since been implemented in somewhat modified form by a number of operating networks as well as in some computer communication architectures. The basic algorithm, although simple to implement, is prone to loops and utilizes O(n3) control packets during its convergence mode. A so-called Predecessor algorithm is described that retains simplicity of implementation yet reduces the incidence of loops and the number of control packets generated. Comparative theoretical studies of the two algorithms are presented for full-duplex loop networks. Comparative performance results of the two algorithms for large networks, using computer experimentation, are presented as well.
Keywords :
Algorithm design and analysis; Communication networks; Computer networks; Convergence; Distributed computing; Intelligent networks; Positron emission tomography; Routing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control, 1982 21st IEEE Conference on
Conference_Location :
Orlando, FL, USA
Type :
conf
DOI :
10.1109/CDC.1982.268213
Filename :
4047316
Link To Document :
بازگشت