Accelerating a Bellman-Ford routing algorithm using GPU

This conference paper was presented in the 2014 FTRA International Symposium on Frontier and Innovation in Future Computing and Communications, FCC 2014; Auckland; New Zealand; 13 January 2014 through 16 January 2014 [© 2014 Springer Science+Business Media Dordrecht] The conference paper's definite version is available at: :http://dx.doi.org/10.1007/978-94-017-8798-7_19This paper presents a graphics processing unit (GPU)-based implementation of the Bellman-Ford (BF) routing algorithm used in distance-vector routing protocols. In the proposed GPU-based approach, multiple threads concurrently run in numerous streaming processors in the GPU to update the routing information instead of computing the individual vertex distances one-by-one, where an individual vertex distance is considered as a single thread. This paper compares the performance and energy consumption of the GPU-based approach with those of the equivalent central processing unit (CPU) implementation for varying the number of vertices. Experiment results show that the proposed approach outperforms the equivalent sequential CPU implementation in terms of execution time by exploiting massive parallelism inherent in the BF routing algorithm.Publishe