IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v312y2022i1d10.1007_s10479-020-03923-y.html
   My bibliography  Save this article

Reliability of spare routing via intersectional minimal paths within budget and time constraints by simulation

Author

Listed:
  • Yi-Kuei Lin

    (National Chiao Tung University
    Asia University
    China Medical University
    Chaoyang University of Technology)

  • Cheng-Fu Huang

    (Feng Chia University)

  • Chin-Chia Chang

    (National Taiwan University of Science and Technology)

Abstract

A stochastic flow network composed of multistate arcs can be utilized to describe several practical systems such as computer networks, where transmission time taken for sending data to a sink is an important index. Determining a path with minimum transmission time is known as the quickest path problem (QPP). All algorithms addressing the QPP assume that the determined minimal paths (MPs) are disjoint. Further, for the general case of intersectional MPs, if a congestion phenomenon occurs during the transmission process, these algorithms will lead to an incorrect outcome. Moreover, in practical scenarios, as a budget limit is considered, spare routing is applied to consolidate the system. The objective is to develop an algorithm based on Monte Carlo simulations (MCSs) for evaluating the system reliability while considering the congestion phenomenon. The system reliability is the probability that a specific amount of data can be transmitted successfully through multiple MPs under both time and budget constraints. Furthermore, spare routing to increase the system reliability is established in advance to specify the main and spare MPs. Experiments validate the evaluation of system reliability based on MCSs. The credibility and efficiency of the proposed algorithm are also discussed.

Suggested Citation

  • Yi-Kuei Lin & Cheng-Fu Huang & Chin-Chia Chang, 2022. "Reliability of spare routing via intersectional minimal paths within budget and time constraints by simulation," Annals of Operations Research, Springer, vol. 312(1), pages 345-368, May.
    • Handle: RePEc:spr:annopr:v:312:y:2022:i:1:d:10.1007_s10479-020-03923-y
    DOI: 10.1007/s10479-020-03923-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-020-03923-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-020-03923-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yi-Kuei Lin & Cheng-Fu Huang, 2015. "Assessment of spare reliability for multi-state computer networks within tolerable packet unreliability," International Journal of Systems Science, Taylor & Francis Journals, vol. 46(6), pages 1020-1035, April.
    2. Ramirez-Marquez, Jose Emmanuel & Coit, David W., 2007. "Multi-state component criticality analysis for reliability improvement in multi-state systems," Reliability Engineering and System Safety, Elsevier, vol. 92(12), pages 1608-1619.
    3. Janssen, Hans, 2013. "Monte-Carlo based uncertainty analysis: Sampling efficiency and sampling convergence," Reliability Engineering and System Safety, Elsevier, vol. 109(C), pages 123-132.
    4. George S. Fishman, 1986. "A Monte Carlo Sampling Plan for Estimating Network Reliability," Operations Research, INFORMS, vol. 34(4), pages 581-594, August.
    5. Bai, Guanghan & Tian, Zhigang & Zuo, Ming J., 2016. "An improved algorithm for finding all minimal paths in a network," Reliability Engineering and System Safety, Elsevier, vol. 150(C), pages 1-10.
    6. Duque, Daniel & Lozano, Leonardo & Medaglia, Andrés L., 2015. "An exact method for the biobjective shortest path problem for large-scale road networks," European Journal of Operational Research, Elsevier, vol. 242(3), pages 788-797.
    7. Benkamra, Zohra & Terbeche, Mekki & Tlemcani, Mounir, 2011. "Tow stage design for estimating the reliability of series/parallel systems," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 81(10), pages 2062-2072.
    8. Lin, Yi-Kuei, 2010. "System reliability of a stochastic-flow network through two minimal paths under time threshold," International Journal of Production Economics, Elsevier, vol. 124(2), pages 382-387, April.
    9. Herminia Calvete & Lourdes del-Pozo & José Iranzo, 2012. "Algorithms for the quickest path problem and the reliable quickest path problem," Computational Management Science, Springer, vol. 9(2), pages 255-272, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yi-Kuei Lin & Thi-Phuong Nguyen & Louis Cheng-Lu Yeng, 2022. "Reliability evaluation of a stochastic multimodal transport network under time and budget considerations," Annals of Operations Research, Springer, vol. 312(1), pages 369-387, May.
    2. Tian, Wei & Song, Jitian & Li, Zhanyong & de Wilde, Pieter, 2014. "Bootstrap techniques for sensitivity analysis and model selection in building thermal performance analysis," Applied Energy, Elsevier, vol. 135(C), pages 320-328.
    3. Abdirizak Omar & Mouadh Addassi & Volker Vahrenkamp & Hussein Hoteit, 2021. "Co-Optimization of CO 2 Storage and Enhanced Gas Recovery Using Carbonated Water and Supercritical CO 2," Energies, MDPI, vol. 14(22), pages 1-21, November.
    4. K.-P. Hui & N. Bean & M. Kraetzl & Dirk Kroese, 2005. "The Cross-Entropy Method for Network Reliability Estimation," Annals of Operations Research, Springer, vol. 134(1), pages 101-118, February.
    5. Ruiying Li & Qiang Dong & Chong Jin & Rui Kang, 2017. "A New Resilience Measure for Supply Chain Networks," Sustainability, MDPI, vol. 9(1), pages 1-19, January.
    6. Lin, Yi-Kuei & Yeh, Cheng-Ta, 2011. "Maximal network reliability for a stochastic power transmission network," Reliability Engineering and System Safety, Elsevier, vol. 96(10), pages 1332-1339.
    7. Cook, Jason L. & Ramirez-Marquez, Jose Emmanuel, 2009. "Optimal design of cluster-based ad-hoc networks using probabilistic solution discovery," Reliability Engineering and System Safety, Elsevier, vol. 94(2), pages 218-228.
    8. Hou, Tianfeng & Nuyens, Dirk & Roels, Staf & Janssen, Hans, 2019. "Quasi-Monte Carlo based uncertainty analysis: Sampling efficiency and error estimation in engineering applications," Reliability Engineering and System Safety, Elsevier, vol. 191(C).
    9. Haritha, P.C. & Anjaneyulu, M.V.L.R., 2024. "Comparison of topological functionality-based resilience metrics using link criticality," Reliability Engineering and System Safety, Elsevier, vol. 243(C).
    10. Si, Shubin & Levitin, Gregory & Dui, Hongyan & Sun, Shudong, 2014. "Importance analysis for reconfigurable systems," Reliability Engineering and System Safety, Elsevier, vol. 126(C), pages 72-80.
    11. Yi-Kuei Lin & Lance Fiondella & Ping-Chen Chang, 2022. "Reliability of time-constrained multi-state network susceptible to correlated component faults," Annals of Operations Research, Springer, vol. 311(1), pages 239-254, April.
    12. Li, Jiahui & Qi, Xiaogang & He, Yi & Liu, Lifang, 2024. "SDN candidate and protection path selection for link failure protection in hybrid SDNs," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    13. J. L. Cook & J. E. Ramirez-Marquez, 2007. "Reliability of capacitated mobile ad hoc networks," Journal of Risk and Reliability, , vol. 221(4), pages 307-318, December.
    14. Xu, Bei & Liu, Tao & Bai, Guanghan & Tao, Junyong & Zhang, Yun-an & Fang, Yining, 2022. "A multistate network approach for reliability evaluation of unmanned swarms by considering information exchange capacity," Reliability Engineering and System Safety, Elsevier, vol. 219(C).
    15. Kotireddy, Rajesh & Hoes, Pieter-Jan & Hensen, Jan L.M., 2018. "A methodology for performance robustness assessment of low-energy buildings using scenario analysis," Applied Energy, Elsevier, vol. 212(C), pages 428-442.
    16. Calvete, Herminia I. & del-Pozo, Lourdes & Iranzo, José A., 2018. "Dealing with residual energy when transmitting data in energy-constrained capacitated networks," European Journal of Operational Research, Elsevier, vol. 269(2), pages 602-620.
    17. Davila-Frias, Alex & Yodo, Nita & Le, Trung & Yadav, Om Prakash, 2023. "A deep neural network and Bayesian method based framework for all-terminal network reliability estimation considering degradation," Reliability Engineering and System Safety, Elsevier, vol. 229(C).
    18. Yi-Kuei Lin & Cheng-Fu Huang, 2016. "Reliability evaluation according to a routing scheme for multi-state computer networks under assured accuracy rate," Annals of Operations Research, Springer, vol. 244(1), pages 221-240, September.
    19. Paredes, R. & Dueñas-Osorio, L. & Meel, K.S. & Vardi, M.Y., 2019. "Principled network reliability approximation: A counting-based approach," Reliability Engineering and System Safety, Elsevier, vol. 191(C).
    20. Dui, Hongyan & Li, Shumin & Xing, Liudong & Liu, Hanlin, 2019. "System performance-based joint importance analysis guided maintenance for repairable systems," Reliability Engineering and System Safety, Elsevier, vol. 186(C), pages 162-175.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:312:y:2022:i:1:d:10.1007_s10479-020-03923-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.