期刊
INFORMATION SCIENCES
卷 541, 期 -, 页码 516-530出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2020.05.048
关键词
Completely independent spanning trees; Crossed cubes; Interconnection networks; Secure-protection routing; Tree searching algorithms
资金
- MOST from the Ministry of Science and Technology, Taiwan [107-2221-E-131-011, 107-2221-E-141-002, 108-2115-M-262-001, 107-2221-E-141-001-MY3]
Kwong et al. (2011) proposed a reactive routing scheme using the multi-paths technique for integrating two mechanisms of route discovery and route maintenance in intra-domain IP networks. They further defined a route to be a protection routing if there is a loop-free alternate path for packet forwarding when a single failed component (including link or node) occurs. Later on, Tapolcai (2013) showed that a network possessing two completely independent spanning trees (CISTs for short) suffices to configure a protection routing. A set of k( >= 2) spanning trees in a network is called CISTs if they are pairwise edge-disjoint and inner-node-disjoint. Particularly, if k = 2, such a set of CISTs is called a dual-CIST. In the early stage, Hasunuma (2002) already pointed out that the problem of determining whether there exists a dual-CIST in a graph is NP-complete. In this paper, we investigate how to construct CISTs in a kind of hypercube-variant networks, called crossed cubes, and obtain the following results: 1) We develop a tree searching algorithm to find three CISTs of the crossed cube CQ(6), and then extend the result to the high-dimensional crossed cube CQ(n) for n >= 7 by induction. 2) We demonstrate that protection routing is also suitable for relatively large (static) network topologies with scalability, such as interconnection networks with recursive structure. 3) We configure a routing scheme called secure-protection routing as an application of CISTs in crossed cubes such that the routing is not only protected but also secure (i.e., no other node except the destination in the network can receive the complete message). 4) We provide simulation results to show the performance evaluation of the proposed routing. (C) 2020 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据