Method and apparatus for deadlock-free routing around an unusabl

Details Method and apparatus for deadlock-free routing around an unusabl Method and apparatus for deadlock-free routing around an unusabl

1995-11-22

1999-04-27

Beausoliel, Jr., Robert W.

G06F 1100

Patent

active

058988262

ABSTRACT:
A method and apparatus for deadlock-free routing around an unusable routing component in a network reroutes paths between source and destination nodes by initially identifying an unusable routing component. A shadow direction within the network is then determined, the shadow direction being from the unusable routing component to an edge of the network. The paths between nodes are then rerouted so that the paths bypass the unusable routing component and limit the use of any routing components in the network between the unusable routing component and the edge in the shadow direction.

REFERENCES:
patent: 4814980 (1989-03-01), Peterson et al.
patent: 5008882 (1991-04-01), Peterson et al.
patent: 5072379 (1991-12-01), Eberhardt
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5138615 (1992-08-01), Lamport et al.
patent: 5151900 (1992-09-01), Snyder et al.
patent: 5170393 (1992-12-01), Peterson et al.
patent: 5218676 (1993-06-01), Ben-Ayed et al.
patent: 5517656 (1996-05-01), Shi
patent: 5533198 (1996-07-01), Thorson
patent: 5583990 (1996-12-01), Birrittella et al.
M. Sultan Alam, et al., "Routing in Modular Fault Tolerant Multiprocessor Systems", 22nd Annual Intl. Symp. on Fault-tolerant Computing, pp. 185-193, 1992.
R.V. Bopanna, et al., "New Wormhole Routing Algorithms for Multicomputers", International Parallel Processing Symposium, pp. 419-423, 1993.
S. Borkar, et al., "iWarp: An Integrated Solution To High-speed Parallel Computing", Supercomputing '88, pp. 330-339, 1988.
J. Bruck, et al., "Efficient Fault-Tolerant Mesh and Hypercube Architectures", International Symposium on Fault-tolerant Computing, pp. 162-169, 1992.
S. Chalsani, et al., "Fault-tolerant Routing in MIN-based Supercomputers", Supercomputing, pp. 244-253, 1990.
M.S. Chen, et al., "Depth-first Search Approach For Fault-tolerant Routing In Hypercube Multicomputers", IEEE Trans. on Parallel and Distributed Systems, pp. 152-159, Apr. 1990.
A. A. Chien, et al., "Planar-adaptive Routing: Low-cost Adaptive Networks For Multiprocessors", Proc. 19th Annual International Symposium on Computer Architecture, pp. 268-277, 1992.
L. Ciminiera, et al. "A Connecting Network With Fault Tolerance Capabilities", IEEE Transactions on Computers, pp. 578-580, Jun. 1986.
W. Dally, et al., "Adaptive Routing using Virtual Channels", Laboratory for Computer Science Massachusetts Institute of Technology, pp. 1-24, Jul. 1990.
W. Dally, et al., "Deadlock-free Adaptive Routing In Multicomputer Networks Using Virtual Channels", IEEE Trans. on Parallel and Distributed Computing, pp. 466-475, Apr. 1993.
W. Dally, et al., "Deadlock-Free Message Routing In Multiprocessor Interconnection Networks", IEEE Transactions on Computers, pp. 547-553, May 1987.
W. Dally, "Performance Analysis of k-ary n-cube Interconnection Networks", IEEE Transactions on Computers, pp. 775-785, Jun. 1990.
W. Dally, et al., "The torus routing chip", Distributed Computing, pp. 187-196, 1986.
W. Dally, "Virtual Channel Flow Control", IEEE Trans. on Parallel and Distributed Systems, pp. 194-205, 1990.
Abdel Aziz Farrag, "Tolerating A Faulty Edge In A Multi-Dimensional Mesh", International Phoenix Conference on Computers and Communications, pp. 9-15, 1993.
S.A. Felperin, et al., "Routing Techniques For Massively Parallel Communications", proceedings of the IEEE, pp. 488-503, 1991.
Tse-yun Feng, "A Survey of Interconnection Networks", Computer, pp. 5-20, 1981.
P.T. Gaughan, et al., "Pipelined Circuit-switching: A Fault-tolerant Variant of Wormhole Routing", Proc Fourth IEEE Symposium on Parallel and Distributed Processing, pp. 148-155/92.
C.J. Glass, et al., "Fault-tolerant Wormhole Routing In Meshes", 23rd Annual International Symposium on Fault-Tolerant Computing, pp. 240-249, 1993.
C.J. Glass, et al., "The Turn Model For Adaptive Routing", Proc 19th Annual Int. Symposium on Computer Architecture, pp. 278-287, 1992.
J. Gordon, et al., "Hypercube Message Routing In The Presence of Faults", 3rd Hypercube Computers Conference, pp. 318-327, 1988.
R. E. Johnson, et al, "Interconnect Topologies with Point-to-Point Rings", Computer Science Department University of Wisconsin-Madison, pp. 1-30 and A1-A6, Dec. 1991.
J. Kim, et al., "Deadlock-free Fault-tolerant Routing In Injured Hypercubes", IEEE Trans. on Computers, pp. 1078-1088, Sep. 1993.
S., Latifi, et al, "Optimal Ring Embedding In Hypercubes With Faulty Links", 22nd Annual Intl. Symp. on Fault-tolerant Computing, pp. 178-184, 1992.
T. Lee, et al., "A Fault-tolerant Communication Scheme for Hypercube Computers", IEEE Trans. on Computers, pp. 1242-1256, Oct. 1992.
X. Lin, et al., "Deadlock-Free Multicast Wormhole Routing in Multicomputer Networks", Department of Computer Science Michigan State University, pp. 1-24, Oct. 1990.
X. Lin, et al., "Performance Evaluation of Multicast Wormhole Routing in 2D-Mesh Multicomputers", 1991 International Conference on Parallel Processing, pp. I-435--1-442, 1991.
D.H. Linder, et al., "An Adaptive and Fault Tolerant Wormhole Routing Strategy For k-ary n-cubes", IEEE Trans on Computers, pp. 2-12, 1991.
K. Padmanabhan, et al., "A Class of Redundant Path Multistage Interconnection Networks", IEEE Trans. on Computers, pp. 1099-1108, Dec. 1983.
M. Peercy, et al., "Distributed Algorithms for Shortest-Path, Deadlock-free Routing and Broadcasting In Arbitrarily Faulty Hypercubes", 20th Ann. Intl. Symp. on Fault-tolerant computing, pp. 218-225, 1990.
C.S. Raghavendra, et al., "Free Dimensions--An Effective Approach To Achieving Fault Tolerance In Hypercubes", 22nd Annual Intl. Symp. on Fault-tolerant Computing, pp. 170-117/92.
D. A. Reed, et al., "Interconnection Networks", IEEE Computer, pp. 63-73, Jun. 1987.
A. Varma, et al., "Fault-tolerant routing in Multistate Interconnection Networks", IEEE Transactions on Computers, pp. 385-393, Mar. 1989.
C.S., Yang, et al., "A Reconfigurable Modular Fault-tolerant Binary Tree Architecture", International Phoenix Conference on Computers and Communications, pp. 37-41, 1993.
J.T. Yantchev, et al., "Adaptive, Low-latency Deadlock-free Packet Routing For Networks of Processors", IEEE proceedings, pp. 178-186, May 1989.
Yener et al., "Fault Tolerant Convergence Routing", Proceedings of ICNP, IEEE, pp. 229-238, Oct. 1994.

Affiliated with

Also associated with

Rating

Method and apparatus for deadlock-free routing around an unusabl does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for deadlock-free routing around an unusabl, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for deadlock-free routing around an unusabl will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-691494