Bi-Objective Network Topology Design with Reliability Constraint
Access Status
Authors
Date
2015Type
Metadata
Show full item recordCitation
Source Title
Source Conference
ISBN
Faculty
School
Collection
Abstract
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.
Related items
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 ...