Curtin University Homepage
  • Library
  • Help
    • Admin

    espace - Curtin’s institutional repository

    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item

    Topology Design with Minimal Cost Subject to Network Reliability Constraint

    227790_227790.pdf (850.2Kb)
    Access Status
    Open access
    Authors
    Elshqeirat, Basima
    Soh, Sieteng
    Rai, S.
    Lazarescu, M.
    Date
    2015
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    Elshqeirat, B. and Soh, S. and Rai, S. and Lazarescu, M. 2015. Topology Design with Minimal Cost Subject to Network Reliability Constraint. IEEE Transactions on Reliability. 64 (1): pp. 118-131.
    Source Title
    IEEE Transactions on Reliability
    DOI
    10.1109/TR.2014.2338253
    ISSN
    0018-9529
    School
    Department of Computing
    URI
    http://hdl.handle.net/20.500.11937/29768
    Collection
    • Curtin Research Publications
    Abstract

    This paper addresses an NP-hard problem, referred to as Network Topology Design with minimum Cost subject to a Reliability constraint (NTD-CR), to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. The paper describes a dynamic programming (DP) scheme to solve the NTD-CR problem, and proposes a DP approach, called Dynamic Programming Algorithm to solve NTD-CR (DPCR-ST), to generate the topology using a selected sequence of spanning trees of the network, STXmin. The paper shows that our DPCR-ST 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 NP-complete, and proposes three greedy heuristics to generate and order only k spanning trees of the network. Each heuristic allows the DPCR-ST 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 state-of-the-art techniques. Our DPCR-ST 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, DPCR-ST approach requires only k=1214 spanning trees to generate a topology with a reliability no larger than 5.05% off from optimal.

    Related items

    Showing items related by title, author, creator and subject.

    • Dynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint
      Elshqeirat, B.; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2013)
      This paper addresses an NP-hard problem, called NTD-CR, to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. Since reliability is always a major issue in the network ...
    • Dynamic Programming for Minimal Cost Topology with Reliability Constraint
      Elshqeirat, B.; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2013)
      This paper addresses an NP-hard problem, called NTD-CR, to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. Since reliability is always a major issue in the network ...
    • A Dynamic Programming Algorithm for Reliable Network Design
      Elshqeirat, Basima; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2014)
      This paper addresses an NP-hard problem to design a network topology with maximum all-terminal reliability subject to a cost constraint, given the locations of the various computer centers (nodes), their connecting links, ...
    Advanced search

    Browse

    Communities & CollectionsIssue DateAuthorTitleSubjectDocument TypeThis CollectionIssue DateAuthorTitleSubjectDocument Type

    My Account

    Admin

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Follow Curtin

    • 
    • 
    • 
    • 
    • 

    CRICOS Provider Code: 00301JABN: 99 143 842 569TEQSA: PRV12158

    Copyright | Disclaimer | Privacy statement | Accessibility

    Curtin would like to pay respect to the Aboriginal and Torres Strait Islander members of our community by acknowledging the traditional owners of the land on which the Perth campus is located, the Whadjuk people of the Nyungar Nation; and on our Kalgoorlie campus, the Wongutha people of the North-Eastern Goldfields.