Topology Design with Minimal Cost Subject to Network Reliability Constraint
Access Status
Authors
Date
2015Type
Metadata
Show full item recordAbstract
This paper addresses an NPhard problem, referred to as Network Topology Design with minimum Cost subject to a Reliability constraint (NTDCR), to design a minimalcost communication network topology that satisfies a predefined reliability constraint. The paper describes a dynamic programming (DP) scheme to solve the NTDCR problem, and proposes a DP approach, called Dynamic Programming Algorithm to solve NTDCR (DPCRST), to generate the topology using a selected sequence of spanning trees of the network, STXmin. The paper shows that our DPCRST approach always provides a feasible solution, and produces an optimal topology given an optimal order of spanning trees. The paper proves that the problem of optimally ordering the spanning trees is NPcomplete, and proposes three greedy heuristics to generate and order only k spanning trees of the network. Each heuristic allows the DPCRST approach to generate STXmin using only k spanning trees, which improves the time complexity while producing a near optimal topology. Simulations based on fully connected networks that contain up to 2.3×109 spanning trees show the merits of using the ordering methods and the effectiveness of our algorithm visàvis to four existing stateoftheart techniques. Our DPCRST approach is able to generate 81.5% optimal results, while using only 0.77% of the spanning trees contained in networks. Further, for a typical 2 × 100 grid network that contains up to 1.899102 spanning trees, DPCRST approach requires only k=1214 spanning trees to generate a topology with a reliability no larger than 5.05% off from optimal.
Citation
Source Title
Department
Collections
Related items
Showing items related by title, author, creator and subject.

Elshqeirat, Basima; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2014)This paper addresses an NPhard problem to design a network topology with maximum allterminal reliability subject to a cost constraint, given the locations of the various computer centers (nodes), their connecting links, ...

Elshqeirat, B.; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2013)This paper addresses an NPhard problem, called NTDCR, to design a minimalcost communication network topology that satisfies a predefined reliability constraint. Since reliability is always a major issue in the network ...

Elshqeirat, B.; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2013)This paper addresses an NPhard problem, called NTDCR, to design a minimalcost communication network topology that satisfies a predefined reliability constraint. Since reliability is always a major issue in the network ...