 |
International Society of Science and Applied Technologies |
| Modeling Quickest Path Reliability in Networks with Random Transmission Time | ||||
| Author | Ding-Hsiang Huang
|
|||
| Co-Author(s) | Cheng-Fu Huang
|
|||
| Abstract | Modern computer systems, such as IoT, cloud platforms, and wireless sensor networks, are often modeled as multi-state flow networks (MSFNs) to capture uncertainties in arc capacities caused by failures and bandwidth variability. The quickest path (QP) problem seeks to identify a path that transmits a required demand within the shortest time under time and capacity constraints. However, computing the quickest path reliability, the probability that the required flow is successfully delivered within a time limit, is NP-hard due to the exponential number of minimal paths (MPs) in large-scale networks. To address this challenge, this study develops a Monte Carlo-based simulation algorithm that simultaneously generates random arc capacities and stochastic transmission time to approximate quickest path reliability. Unlike prior methods assuming fixed transmission time, the proposed framework better reflects realworld conditions. Extensive experiments on a practical network, NSFNET, demonstrate the algorithm’s effectiveness and efficiency. Across six test scenarios with varying arc capacities, the estimated reliabilities closely match exact values, with average deviation less than 0.1% and average CPU time of only 0.0013 seconds. These results confirm the proposed method’s accuracy and scalability for evaluating quickest path reliability in complex, time-sensitive systems.
|
|||
| Keywords | multi-state flow networks (MSFNs), quickest path (QP), quickest path reliability, random transmission time, Monte Carlo-based simulation | |||
| Article #: RQD2025-221 | ||||
Proceedings of 30th ISSAT International Conference on Reliability & Quality in Design |