Title :
Using Multi-valued Decision Diagrams to Solve the Expected Hop Count Problem
Author :
Herrmann, Johannes U. ; Soh, Sieteng ; West, Geoff ; Rai, Suresh
Author_Institution :
Dept. of Comput., Curtin Univ. of Technol., Bentley, WA
Abstract :
The expected hop count (EHC) of a computer communication network has so far been computed for network models that consider only device or link failure, but not both. We introduce an augmented ordered multi-valued decision diagram (OMDD-A) to obtain the EHC of a network in which both devices and links may fail. The OMDD-A approach can compute the EHC of a 2times100 grid network with 299 paths, which is unsolvable using existing techniques. We show that OMDD-A generates significantly fewer nodes than the corresponding ordered binary decision diagram, leading to large reductions in processing time.
Keywords :
binary decision diagrams; computer network reliability; graph theory; augmented ordered multivalued decision diagram; computer communication network reliability; expected hop count problem; graph theory; grid network; ordered binary decision diagram; Application software; Boolean functions; Communication networks; Computer network reliability; Computer networks; Data structures; Electronic mail; Grid computing; Maintenance; Telecommunication network reliability; expected hop count; imperfect links; imperfect nodes; multi-value decision diagram; network reliability;
Conference_Titel :
Advanced Information Networking and Applications Workshops, 2009. WAINA '09. International Conference on
Conference_Location :
Bradford
Print_ISBN :
978-1-4244-3999-7
Electronic_ISBN :
978-0-7695-3639-2
DOI :
10.1109/WAINA.2009.124