|
|
|
One-to-one communication in twisted cubes under
restricted connectivity |
| Jianxi FAN1,Shukui ZHANG1,Wujun ZHOU1,Baolei CHENG1,Kenli LI2, |
| 1.School of Computer Science
and Technology, Soochow University, Suzhou 215006, China; 2.School of Computer and
Communication, Hunan University, Changsha 410082, China; |
|
|
|
|
Abstract The dimensions of twisted cubes are only limited to odd integers. In this paper, we first extend the dimensions of twisted cubes to all positive integers. Then, we introduce the concept of the restricted faulty set into twisted cubes. We further prove that under the condition that each node of the n-dimensional twisted cube TQn has at least one fault-free neighbor, its restricted connectivity is 2n − 2, which is almost twice as that of TQn under the condition of arbitrary faulty nodes, the same as that of the n-dimensional hypercube. Moreover, we provide an O(NlogN) fault-free unicast algorithm and simulations result of the expected length of the fault-free path obtained by our algorithm, where N denotes the node number of TQn. Finally, we propose a polynomial algorithm to check whether the faulty node set satisfies the condition that each node of the n-dimensional twisted cube TQn has at least one fault-free neighbor.
|
| Keywords
connectivity
set of restricted faulty nodes
unicast
fault-free path
twisted cube
|
|
Issue Date: 05 December 2010
|
|
|
Harary F. Conditional connectivity. Networks, 1983, 13(3): 347–357
|
|
Esfahanian A H. Generalized measures of fault tolerance with applicationto n-cube networks. IEEE Transactions on Computers, 1989, 38(11): 1586–1591
|
|
Gu Q P, Peng S. Unicast in hypercubes with large number of faulty nodes. IEEE Transactions on Parallel and Distributed Systems, 1999, 10(10): 964–975
|
|
Abraham S, Padmanabhan K. The twisted cube topology for multiprocessors: A Study in network asymmetry. Journal of Parallel and Distributed Computing, 1991, 13(1): 104–110
|
|
Hilbers P A J, Koopman M R J, Van de Snepscheut J L A. The twisted cube, parallel architectures on PARLE: Parallel Architectures and Languages Europe, 1987, 1: 152–158
|
|
Chang C P, Wang J N, Hsu L H. Topological properties of twisted cubes. Information Sciences, 1999, 113(1-2): 147–167
|
|
Abuelrub E, Bettayeb S. Embedding of complete binary trees in twisted hypercubes. In: Proceedings of Int'l Conf. Computer Applications in Design,Simulation, and Analysis, 1993, 1–4
|
|
Huang W T, Tan J J M, Hung C N, Hsu L H. Fault-tolerant hamiltonicity of twisted cubes. Journal of Parallel and Distributed Computing, 2002, 62(4): 591–604
|
|
Fan J, Jia X, Lin X. Embedding of cycles in twisted cubeswith edge-pancyclic. Algorithmica, 2008, 51(3): 264–282
|
|
Fan J, Jia X, Lin X. Optimal embeddings of paths with variouslengths in twisted cubes. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(4): 511–521
|
|
Fan J, Lin X, Pan Y, Jia X. Optimal fault-tolerant embedding of paths in twisted cubes. Journal of Parallel and Distributed Computing, 2007, 67(2): 205–214
|
|
Fan J, Lin X. The t/k-diagnosability of the BC graphs. IEEE Transactions on Computers, 2005, 54(2): 176–184
|
|
Efe K. A variation on the hypercube with lower diameter. IEEE Transactions on Computers, 1991, 40(11): 1312–1316
|
|
Larson S M, Cull P. The M?biuscubes. IEEE Trans. Computers, 1995, 44(5): 647–659
|
|
Yang X, Evans D J, Megson G M. The locally twisted cubes. International Journal of Computer Mathematics, 2005, 82(4): 401–413
|
|
Fan J, He L. BC interconnectionnetworks and their properties. Chinese J. Computers, 2003, 26(1): 84–90 (in Chinese)
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
