期刊
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
卷 33, 期 8, 页码 1902-1910出版社
IEEE COMPUTER SOC
DOI: 10.1109/TPDS.2021.3132412
关键词
Fault tolerant systems; Fault tolerance; Hypercubes; Tools; Routing; Network topology; Broadcasting; Completely independent spanning trees; a protection routing; CIST-partition; Hamilton bipartition sufficient condition; constructive algorithm
资金
- National Natural Science Foundation of China [11971054, 11731002]
This article proves the existence of dual Completely Independent Spanning Trees (CISTs) in an infinite number of networks satisfying certain conditions. A unique algorithm for constructing a CIST partition is proposed, which can be easily implemented in various networks and parallel or distributed systems. Comparison analysis with known results shows the significant advantage of our proposed conditions, with a strict bound. These results provide a powerful framework for the design of fault-tolerant network topologies and routing protocols for future networks.
The main method to achieve fault-tolerant network systems is by exploiting and effectively utilizing the edge-disjoint and/or inner-vertex-disjoint paths between pairs of source and destination vertices. Completely independent spanning trees (CISTs for short) are powerful tools for reliable broadcasting/unicasting and secure message distribution. Particularly, it has been shown that two CISTs have an application on configuring a protection routing in IP networks, such as mobile ad hoc networks and relatively large (static) network topologies with scalability in [IEEE/ACM Trans. Netw., 27 (2019) 1112-1123]. Many results focus on CISTs in specific networks in the literature, however, few results are given on an infinite class of networks having common properties. In this article, we prove the existence of dual-CISTs in an infinite number of networks satisfying some Hamilton sufficient conditions. A unique algorithm to construct a CIST-partition is proposed, which can be applied to not only many kinds of networks, but our algorithm can also be implemented very easily in parallel or distributed systems satisfying the conditions. In addition, we make a comparative analysis between the proposed conditions and several known results on an infinite number of networks, the advantage of our result is significant. In particular, the bound in our conditions is sharp. The results will provide a powerful framework for the design of fault-tolerant network topologies and routing protocols for future networks.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据