Title: Dynamic update of minimum cost paths in computer networks

Authors: Gianlorenzo D'Angelo; Daniele Frigioni; Vinicio Maurizio

Addresses: Department of Electrical and Information Engineering, University of L'Aquila, Via G. Gronchi 18, I-67100 L'Aquila, Italy. ' Department of Electrical and Information Engineering, University of L'Aquila, Via G. Gronchi 18, I-67100 L'Aquila, Italy. ' Department of Electrical and Information Engineering, University of L'Aquila, Via G. Gronchi 18, I-67100 L'Aquila, Italy

Abstract: The problem of dynamically update minimum cost paths in a distributed network of computers while link update operations occur to the network is considered crucial in today|s practical applications. A number of solutions have been proposed in the literature for this problem. In this paper, we perform an extensive experimental study in the OMNeT++ simulation environment by implementing three different algorithms for the above described problem: the Bellman-Ford method; DUAL (a part of CISCO|s widely used EIGRP protocol), which is perhaps the most used algorithm; and ConFu, a recently proposed algorithm. We perform several tests both on real-world and random networks and randomly generated update sequences. These experiments show that in most cases ConFu outperforms Bellman-Ford and DUAL in terms of either number of messages sent or space occupancy per node.

Keywords: minimum cost paths; distributed networks; dynamic networks; concurrent computation; distance vector algorithms; simulation.

DOI: 10.1504/IJMNE.2011.042580

International Journal of Management and Network Economics, 2011 Vol.2 No.1, pp.58 - 74

Available online: 17 Sep 2011 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article