Christmas Tree: A 1-Fault-Tolerant Network for Token Rings*

Chun-Nan Hung and Lih-Hsing Hsu^*
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.

Ting-Yi Sung
Institute of Information Science
Academia Sinica
Taipei, Taiwan 115, R.O.C.

Abstract:

The token ring topology is required in token passing approach used in distributed operating systems. Fault tolerance is also required in the design of distributed systems. In this paper, we consider the 1-fault-tolerant design for token rings, which can tolerate 1-processor fault or 1-link fault. Note that the 1-fault-tolerant design for token rings is equivalent to the design of 1-hamiltonian graphs. This paper introduces a new family of interconnection networks called Christmas tree. The under graph of the Christmas tree, denoted by CT(s), is a 3-regular, planar, 1-hamiltonian, and hamiltonian-connected graph. The number of nodes and the diameter of CT(s) are $3 \times 2^s - 2$ and 2s, respectively. In other words, the diameter of CT(s) is $2 \log_2 n - O(1)$, where n is the number of nodes.

Keywords: Christmas tree; hamiltonian; 1-hamiltonian; hamiltonian-connected; fault-tolerant; token ring;