Article ID: | iaor199849 |
Country: | United Kingdom |
Volume: | 24 |
Issue: | 6 |
Start Page Number: | 521 |
End Page Number: | 527 |
Publication Date: | Jun 1997 |
Journal: | Computers and Operations Research |
Authors: | Rugelj Joe, Klavar Sandi |
Keywords: | heuristics, networks |
A new mechanism for effectively routing packets from a source to multiple destinations in large point-to-point communication networks is presented in this article. As there is no central node with the complete knowledge of network topology, and therefore conventional Steiner tree algorithms can not be used, the need for a distributed approach emerges where each node is supposed to know only the topology of its vicinity. A distributed algorithm based on the cheapest insertion heuristics is proposed in this article. Simulation results have shown that the efficiency of the proposed distributed algorithm is practically identical to that of the distributed Kou–Markowsky–Berman algorithm, whereas it substantially surpasses the DKMB as regards time complexity.