A general and efficient framework for improving Balanced Failure Biasing

Balanced Failure Biasing (BFB) is a way to simulate the probability of reaching a rare goal state in highly reliable Markovian systems (HRMSs). BFB gives the same probability to each ralely-arrived path of one state, therefore leading to large expenditures on paths with little influence on results. We propose a new framework using Stratified Sampling, which is a general and efficient framework for improving BFB. We introduce Stratified Sampling on BFB (SBFB), which divides the original state space into many subspaces, and rearranges the attention on each subspace. To make a further reduction on average path length, we introduce Stratified Sampling on Distance-based BFB (SBFB-D). According to experiments based on case of Workstation Cluster and case of Distributed Database System, SBFB has about 0.07% and 2.13% relative error on these two cases respectively, while SBFB-D has about 0.07% and 0.197%, comparing to standard BFB's 11.1% and 11.1%. Besides, SBFB spends about 12.30s and 28.65s on path simulation respectively, while SBFB-D spends about 13.10s and 17.40s, comparing to standard-BFB's 26.44s and 36.78s.