Efficient Network Reliability Evaluation with Guaranteed Error Bound Using Binary Decision Diagrams

Evaluating network reliability is crucial for designing communication infrastructures, particularly for such next-generation networks as 6 G, which require extremely high reliability levels, often reaching seven 9's (99.99999 %). However, network reliability evaluation is computationally tough, making it computationally intractable to achieve accurate results for large-scale networks within a reasonable time. Consequently, existing methods either sacrifice computational efficiency or lack guaranteed error bounds. This paper presents an efficient approximation method for network reliability evaluation that guarantees that the approximation error remains within a specified bound. Our proposed method first determines the maximum degree of simultaneous link failures that can be safely ignored without exceeding the bound. With binary decision diagrams, our method efficiently computes both the lower and upper bounds of network reliability. We validate our method through numerical experiments on real-world networks. Our method, which outperformed existing methods by several orders of magnitude, evaluated a network with 434 links in just 7 seconds; an existing method required more than 28 hours.