Title: An evolutionary programming algorithm for finding constrained optimal disjoint paths for multihop communication networks

Authors: Urmila Bhanja, Rajarshi Roy, Sudipta Mahapatra

Addresses: Department of E&ECE, Indian Institute of Technology, Kharagpur – 721302, West Midnapur, West Bengal, India. ' Department of E&ECE, Indian Institute of Technology, Kharagpur – 721302, West Midnapur, West Bengal, India. ' Department of E&ECE, Indian Institute of Technology, Kharagpur – 721302, West Midnapur, West Bengal, India

Abstract: We present an evolutionary programming algorithm (EP) for finding hop count and bandwidth constrained cost optimal disjoint paths in multihop communication networks. In general, multi-constrained path selection is an NP complete problem. Our proposed algorithm can be used for real-time online network applications, which can initiate and process a number of calls simultaneously on disjoint paths, without overloading the network. This algorithm also requires a small memory space and low execution time. The proposed algorithm, which maintains a balance between finding an optimal shortest path and CPU mean execution time, also generates parallel suboptimal paths during the process of generating the best path. One of these suboptimal paths can be used as a backup path if it is link disjoint with all the primary paths (best paths) of the concurrent requests. Thus, the proposed algorithm provides a limited degree of reliability for routing of packets as well.

Keywords: evolutionary programming algorithms; disjoint paths; constrained optimisation; fitness functions; mean execution time; hop count bound; NP hard problem; QoS constraints; quality of service; dynamic topology; metaheuristics; fitness deviation; bandwidth constraints; multimedia delivery; telecommunications networks.

DOI: 10.1504/IJMHEUR.2010.034203

International Journal of Metaheuristics, 2010 Vol.1 No.2, pp.132 - 155

Published online: 19 Jul 2010 *

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