Show simple item record

dc.contributor.authorElshqeirat, Basima
dc.contributor.authorSoh, Sie Teng
dc.contributor.authorRai, S.
dc.contributor.authorLazarescu, Mihai
dc.identifier.citationElshqeirat, B. and Soh, S.T. and Rai, S. and Lazarescu, M. 2015. Bi-Objective Topology Design of Communication Networks Using Dynamic Programming. International Journal of Performability Engineering. 11 (3): pp. 265-274.

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.

dc.publisherRAMS Consultants
dc.subjectbi-objective optimisation
dc.subjectlagrange relaxation
dc.subjectnetwork topology design
dc.subjectDynamic programming
dc.titleBi-Objective Topology Design of Communication Networks Using Dynamic Programming
dc.typeJournal Article
dcterms.source.titleInternational Journal of Performability Engineering
curtin.departmentDepartment of Computing
curtin.accessStatusFulltext not available

Files in this item


This item appears in the following Collection(s)

Show simple item record