Deadlock avoidance method in a computer network

Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Routing data updating

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

709224, 712 25, G06F 1100

Patent

active

06065063&

ABSTRACT:
In an apparatus having a network including successive stages of cross-point switches which collectively interconnect a plurality of nodes external to said network, wherein at least one message is carried between one of the nodes and one of the cross-point switches over a route through said network, a method for preventing routing deadlocks from occurring in the network which comprises the steps of: creating a graphical representation of the network; searching for the existence of cycles within the graphical representation; partitioning the graphical representation into at a first subgraph and a second subgraph if cycles exist in the graphical representation; searching for the existence of edges directed from the first subgraph to the second subgraph; and removing the edges directed from the first subgraph to the second subgraph. Preferably the step of partitioning the network into at a first subgraph and a second subgraph is performed such that the first subgraph and the second subgraph have an equal number of vertices, a number of directed edges from the first subgraph to the second subgraph is minimized so as to minimize the number of routes prohibited, and a set of partition constraints are satisfied. The method is recursively applied to the first subgraph and then the second subgraph, thereby removing all of the deadlock prone cycles in the network while minimizing the number of routes prohibited due to remove edges.

REFERENCES:
patent: 4912656 (1990-03-01), Cain et al.
patent: 5021947 (1991-06-01), Campbell
patent: 5453978 (1995-09-01), Sethu et al.
patent: 5533016 (1996-07-01), Cook et al.
patent: 5587922 (1996-12-01), Hendrickson et al.
patent: 5748844 (1998-05-01), Marks
Robert Horst, "ServerNet Deadlock Avoidance and Fractahedral Topologies", Proc. 10th Int. Parallel Processing Symp. (IPPS '96), pp. 274-280, Apr. 1996.
T.H. Cormen, "Introduction to Algorithms", NY: McGraw-Hill, pp. 465-485, 1990.
Wenjian Qiao et al., "Adaptive Routing in Irregular Networks Using Cut-Through Switches*", Int. Parallel Processing Symp. (IPPS '96), pp. 1-10.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Deadlock avoidance method in a computer network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Deadlock avoidance method in a computer network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deadlock avoidance method in a computer network will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-268511

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.