期刊
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
卷 32, 期 3, 页码 665-673出版社
IEEE COMPUTER SOC
DOI: 10.1109/TPDS.2020.3029654
关键词
Data centers; Hypercubes; Broadcasting; Servers; Scalability; Fault tolerance; Fault tolerant systems; Augmented cube; hamiltonian cycle; edge-disjoint hamiltonian paths; data center network; completely independent spanning trees
资金
- Joint Fund of the National Natural Science Foundation of China [U1905211]
- National Natural Science Foundation of China [61572337]
- Natural Science Foundation of the Jiangsu Higher Education Institutions of China [18KJA520009]
- China Postdoctoral Science Foundation [2015M581858]
- Jiangsu Planned Projects for Postdoctoral Research Funds [1501089B]
- Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD)
This article discusses the importance and applications of constructing Completely Independent Spanning Trees (CISTs) in a network, especially in data center networks. It also introduces the augmented cube AQn as the underlying structure of a data center network and studies how to construct n-1 optimal CISTs in its logic graph L-AQDNn. Additionally, the relationship between the dimension of a hypercube-family network and the number of CISTs it can host is established for the first time.
A set of spanning trees T1; T2;...; Tk in a network G are Completely Independent Spanning Trees (CISTs) if for any two nodes u and v in V oGTHORN, the paths between u and v in any two trees have no common edges and no common internal nodes. CISTs have important applications in data center networks, such as fault-tolerant multi-node broadcasting, fault-tolerant one-to-all broadcasting, reliable broadcasting, secure message distribution, and so on. The augmented cube AQn is a prominent variant of the well-known hypercube Qn, and having the important property of scalability, and both Qn and AQn have been proposed as the underlying structure for a data center network. The data center network based on AQn is denoted by AQDNn, and the logic graph of AQDNn is denoted by L-AQDNn. In this article, we study how to construct n- 1 CISTs in L-AQDNn. The constructed n- 1 CISTs are optimal in the sense that n- 1 is the maximally allowed CISTs in L-AQDNn. The correctness of our construction algorithm is proved. It is the first time a direct relationship is established between the dimension of a hypercube-family network and the number of CISTs it can host.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据