×

An evolutionary programming algorithm for finding constrained optimal disjoint paths for multihop communication networks. (English) Zbl 1213.90079

Summary: 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.

MSC:

90B18 Communication networks in operations research
90C59 Approximation methods and heuristics in mathematical programming
68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI