Node disjoint path forming method for hypercube having damaged n

Details Node disjoint path forming method for hypercube having damaged n Node disjoint path forming method for hypercube having damaged n

1998-01-15

2000-03-14

Sheikh, Ayaz R.

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

712 10, 712 11, 712 12, 712 16, 712 20, G06F 1516

Patent

active

060386886

ABSTRACT:
A node disjoint path forming method for a hypercube having a damaged node which is capable of using unused nodes (surplus nodes) in an n-number of node disjoint paths each having a length of n with respect to n-dimensional hypercubes more than 4-cube, so that it is possible to obtain an n-number of node disjoint paths each having a length of n even though there are damaged nodes. The method includes the steps of a first step for forming a linear arrangement consisting of an n-number of integers (0, 1, 2, . . . n-1) with respect to an n-dimension and searching a linear arrangement which is not neighbored in a linear arrangement in which integers which indicate a value of 1 in an address of a damaged node are circulated, assuming that a node address with respect to an n-address is expressed as a position of 1 among an n-number of binary digits, separating each value by a comma by defining an address value of a decimal digit indicating a position of 1 using a bracket, defining the rightmost position as 0 and the leftmost position as n-1, and a second step for forming a linear arrangement using integers of an arrangement in which values indicating a position of 1 in an address of a damaged node are not neighbored on a circumferential portion, moving the linear arrangement by one digit in the right direction and forming an nxn first matrix.

REFERENCES:
patent: 5313645 (1994-05-01), Rolfe
patent: 5669008 (1997-09-01), Galles et al.
patent: 5794059 (1998-08-01), Barker et al.
"Identification of operational subcubes in unreliable hypercubes", S. Latifi, IEEE Proceedings, vol. 139, No. 2, Mar. 1992, pp. 117-122.
"Combinatorial Analysis of the Fault-Diameter of the n-cube", S. Latifi, IEEE Transactions on Computers, vol. 42, No. 1, Jan. 1993, pp. 27-33.
"Algorithms for Node Disjoint Paths in Incomplete Star Networks", Q. Gu and S. Peng, Parallel and Distributed Systems, 1994. International Conference on Dec. 19-21, 1994, pp:296 -303.
"Fault-Tolerant Routing with Regularity Restoration in Boolean n-Cube Interconnection Networks", M. Horng and L. Kleinrock, Parallel and Distributed Processing, Dec. 1991, pp: 458 -465.
"An Efficient Algorithm for k-Pairwise Node Disjoint Path Problem in Hypercubes", Q. Gu and S. Peng, Parallel and Distributed Processing, 1995, pp: 673 -680.

Affiliated with

Also associated with

Rating

Node disjoint path forming method for hypercube having damaged n does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Node disjoint path forming method for hypercube having damaged n, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Node disjoint path forming method for hypercube having damaged n will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-180047