Bi-Objective Topology Design of Communication Networks Using Dynamic Programming

Abstract

This paper provides an algorithm to design a communication network topology with minimal cost (C) and maximum (s, t) reliability (R) subject to a pre-defined bandwidth (Bmin) constraint, given (i) locations of the various computer nodes, (ii) their connecting links, (iii) each link’s reliability, cost and bandwidth, and (iv) a minimum bandwidth for the network. The bi-objective optimization problem is known NP-hard; henceforth we call the problem NTD-CR/B. We use the dynamic programming (DP) formulation as the engine in our proposed approach, DPCR/B, to generate the topology for solving NTD-CR/B. Further, we propose three greedy heuristics that enumerate and order only k?n (s, t) paths, where n is the total number of (s, t) paths in the network. Each heuristic allows DPCR/B to obtain the selected paths to form the topology using only k paths, which improves the time complexity while producing near optimal topology. Extensive simulations on large networks with various sizes show that DPCR/B is able to generate 91.2% optimal results while using only 1.37-27% of all paths in the grid networks that typically contain up to 299 paths.