Abstract:

The importance evaluation of network links is important to network design and maintenance. This paper proposes a novel importance evaluation method named as Birnbaum ordered-binary-decision-diagram (BO),which is based on ordered binary decision diagram (OBDD). Birnbaum measurement is introduced to qualify the link importance, and the OBDD structure of the network is constructed with an edge expansion diagram (EED). Based on reliability calculations, the Birnbaum measurement value is gotten with the network reliability when links are fault. Furthermore, the efficient OBDD structure and hash table are used to identify those isomorphic subnetworks. As a result, some redundant states and repeated computations are decreased, and computation efficiency is enhanced. Some large networks from classic reliability literatures are introduced into experiments and are used as benchmark networks. Experiments show that the proposed method is more efficient than the factoring algorithm and can accurately evaluate the importance of network links.