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

    A Practical Algorithm for Reliable Network Topology Design

    Access Status
    Fulltext not available
    Authors
    Elshqeirat, B.
    Soh, Sieteng
    Rai, S.
    Lazarescu, Mihai
    Date
    2013
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    Elshqeirat, Basima and Soh, Sieteng and Rai, Suresh and Lazarescu, Mihai. 2013. A Practical Algorithm for Reliable Network Topology Design. International Journal of Performability Engineering. 9 (4): pp. 397-408.
    Source Title
    International Journal of Performability Engineering
    Additional URLs
    http://www.ijpe-online.com/attachments/article/696/pp.397-408%20Paper%205%20IJPE%20443.12%20Soh%2029.08.12.pdf
    ISSN
    0973-1318
    URI
    http://hdl.handle.net/20.500.11937/29118
    Collection
    • Curtin Research Publications
    Abstract

    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 cost, and the maximum budget cost to install the links. Cost is a major issue in the network design, and thus the problem is applicable for networks requiring maximized reliability. This paper presents a dynamic programming (DP) scheme to solve the problem. Then, it describes a DP approach, called DPA, to generate the topology using all (s, t) paths in the network. Five different path-orders are proposed to improve the effectiveness of DPA. Further, the path-orders allow DPA to generate only k=1 paths dynamically from the graph model of the network and stops if a path inclusion leads to an insignificant addition in the resulting topology’s reliability. This step reduces the time complexity significantly while producing almost equal results as compared to using all (s, t) paths. Extensive simulations using benchmark networks with various sizes show the merits of path-orders, and the effectiveness and advantage of our DPA vis-à-vis to three existing techniques. Our proposed DPA is able to generate 92% optimal results on the networks using only 6% to 11% of the (s, t) paths for large networks. Further, its non-optimal results are no more than 0.77% off that of optimal. Finally, for a 2×100 grid network that contains 299 paths, DPA requires only up to k=987 paths to generate topology with cost 99% of the total cost and reliability 99.35% of that of the original network.

    Related items

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

    • Bi-Objective Topology Design of Communication Networks Using Dynamic Programming
      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 ...
    • Bi-Objective Network Topology Design with Reliability Constraint
      Elshqeirat, Basima; Soh, Sie Teng; Chin, K. (2015)
      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 ...
    • Topology Design with Minimal Cost Subject to Network Reliability Constraint
      Elshqeirat, Basima; Soh, Sieteng; Rai, S.; Lazarescu, M. (2015)
      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 ...
    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.