Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Routing data updating
Patent
1998-01-29
2000-05-16
Maung, Zarni
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Routing data updating
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.
Dinh Khanh
International Business Machines Corp.
Maung Zarni
LandOfFree
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.
Profile ID: LFUS-PAI-O-268511