Bi-Objective Network Topology Design with Reliability Constraint
MetadataShow full item record
This paper addresses an NP-hard problem, called NTD-CB/R, whose solution is of importance to applications requiring one or more Quality of Service (QoS). Specifically, the problem calls for a network topology that meets two objectives, i.e., minimal cost and maximum bandwidth, subject to a predefined (s, t) reliability constraint. We approach the problem by converting it into one with a single objective. This is achieved via a ratio, called bcr, between network bandwidth and cost to measure the goodness of each topology, and by applying Lagrange relaxation. Then we propose a dynamic programming (DP) scheme, and propose a heuristic solution, called DPCB/R, to generate each topology using all of its n (s, t) paths. This paper also proposes three heuristic path orders that allow DPCB/R to generate and use only k≤n paths to reduce its time complexity while producing similar results. Extensive simulations using 125 benchmark networks with various sizes show the merits of the path-orders, and effectiveness of our approach. DPCB/R is able to generate 88% optimal results for the networks. Further, its non-optimal results have a bcr ratio, bandwidth, and cost of only up to 1.56%, 0.9%, and, 2.1% off from the optimal, respectively. Further, for a grid network that contains 299 paths it uses only 1.1-27% of the paths while producing a topology that is only 0.92% off from optimal, with respect to bcr metric.
Showing items related by title, author, creator and subject.
Elshqeirat, Basima; Soh, Sie Teng; Rai, S.; Lazarescu, Mihai (2015)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 ...
Loh, Ruen Chze (2010)Most of today’s computer communications use only a single (s,t) path to transmit a message from a source node s to a destination node t. There are two major problems with this single path communication. Firstly, the ...
Elshqeirat, B.; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2013)This paper addresses an NP-hard problem of designing a network topology with maximum (s, t) reliability subject to given constraints, such as the computer centers location (nodes), their connecting links reliability and ...