Efficient Reliability Evaluation of Multi-Domain Networks with Secure Intra-Domain Privacy

Atsushi TANIGUCHI  Takeru INOUE  Kohei MIZUNO  Takashi KURIMOTO  Atsuko TAKEFUSA  Shigeo URUSHIDANI  

Publication
IEICE TRANSACTIONS on Communications   Vol.E103-B    No.4    pp.440-451
Publication Date: 2020/04/01
Publicized: 2019/09/27
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2019EBP3119
Type of Manuscript: PAPER
Category: Network Management/Operation
Keyword: 
network reliability,  social sustainability,  inter-domain networks,  graph theory,  

Full Text: FreePDF(2MB)
Summary: 
Communication networks are now an essential infrastructure of society. Many services are constructed across multiple network domains. Therefore, the reliability of multi-domain networks should be evaluated to assess the sustainability of our society, but there is no known method for evaluating it. One reason is the high computation complexity; i.e., network reliability evaluation is known to be #P-complete, which has prevented the reliability evaluation of multi-domain networks. The other reason is intra-domain privacy; i.e., network providers never disclose the internal data required for reliability evaluation. This paper proposes a novel method that computes the lower and upper bounds of reliability in a distributed manner without requiring privacy disclosure. Our method is solidly based on graph theory, and is supported by a simple protocol that secures intra-domain privacy. Experiments on real datasets show that our method can successfully compute the reliability for 14-domain networks in one second. The reliability is bounded with reasonable errors; e.g., bound gaps are less than 0.1% for reliable networks.