Electrical computers and digital processing systems: multicomput – Multiple network interconnecting
Reexamination Certificate
1999-06-02
2003-10-07
Caldwell, Andrew (Department: 2157)
Electrical computers and digital processing systems: multicomput
Multiple network interconnecting
C712S013000
Reexamination Certificate
active
06631421
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data processing systems and, more particularly, to recursively partitioning networks.
BACKGROUND OF THE INVENTION
Networks comprise a number of nodes that are interconnected via links. As used herein, the term “node” refers to any device capable of communicating, such as a computer, router, switch, network processor, or symmetric multi-processor. The specific configuration of nodes and links in a network is referred to as the “network topology.”
Some conventional networks may be partitioned into subnetworks. The “partitioning” of a network refers to subdividing the network into two subnetworks, each of which is independent of the other. The term “independent” refers to each link of the original network belonging to at most one of the two resulting subnetworks and each node of the original network belonging to at most one of the two resulting subnetworks.
Partitioning a network is desirable because it provides fault tolerance. That is, partitioning a network into two subnetworks ensures that the failure of a node in one subnetwork does not affect the other. For example, a node in one of the subnetworks may fail and become nonoperational. In this situation, although the failure affects performance of the subnetwork in which it resides because none of the other nodes can route traffic through the failed node, the other subnetwork remains unaffected by the failure.
Although conventional systems exist for partitioning a network, these systems partition the network in a restricted manner: each subnetwork is constrained as to the number of nodes that it contains. For example, in one conventional system, each subnetwork contains either one-half or one-fourth of the total number of nodes in the network. Similarly, another conventional system restricts the number of nodes in the network to a power of 2.
Although these conventional systems allow for partitioning, because the number of nodes in the subnetwork is constrained, these systems are inflexible, which can lead to the under utilization of resources. For example, in the conventional system where each subnetwork contains either one-half or one-fourth of the total number of nodes, if the total number of nodes were 16 and the system administrator needed a subnetwork of only 3 nodes to run a particular set of programs, the administrator would be restricted to dividing the network into two subnetworks of 8 nodes or a subnetwork of 4 nodes and a subnetwork of 12 nodes. In either case, at least one node goes underutilized. It is therefore desirable to improve the partitioning of networks.
SUMMARY OF THE INVENTION
Methods and systems consistent with the present invention provide a family of networks ranging from 2 nodes to 16 nodes that can be partitioned in an unconstrained manner. That is, where the number of nodes in one of these networks is N, each subnetwork can contain any number of nodes from 1 to N−1 as long as the total number of nodes in both subnetworks equals N. Furthermore, each subnetwork can be partitioned repeatedly until reaching the atomic level (i.e., when the subnetwork contains a single node). In accordance with methods and systems consistent with the present invention, when a network is partitioned, each subnetwork has various desirable properties. For example, the maximum path length between any two nodes in each subnetwork is 3, and each subnetwork has a set of deadlock-free routings.
In accordance with methods consistent with the present invention, a method is provided in a data processing system with a number of nodes N, where N is greater than 4. This method receives an indication of a first number of nodes and a second number of nodes. The first number of nodes and the second number of nodes are capable of being any number from 1 to N−1 as long as the sum of the first number of nodes and the second number of nodes is N. Furthermore, the method partitions the nodes into a first subnetwork having the first number of nodes and a second subnetwork having the second number of nodes.
In accordance with methods consistent with the present invention, a method is provided that provides a network that has nodes and a plurality of the nodes are partner nodes having a partnership relationship. Furthermore, the method partitions the network into a plurality of subnetworks such that the partnership relationship between the partner nodes remains intact.
In accordance with methods consistent with the present invention, a method is provided in a distributed system having a network of nodes. This method partitions the network into a plurality of subnetworks, provides each of the subnetworks with a routing table that avoids deadlock, and routes traffic through each of the subnetworks using the provided routing tables such that deadlock is avoided.
In accordance with systems consistent with the present invention, an administrative node of a network is provided. The network contains a number of nodes N, where N is greater than 4. This administrative node contains a memory and a processor. The memory comprises routing software with first code that receives an indication of a first number of nodes and an indication of a second number of nodes, the first number and the second number being unconstrained such that the first number and the second number are capable of being any number between 1 and N−1 as long as the first number and the second number sum to N. The routing software also contains second code for partitioning the network into a first partition with the first number of nodes and a second partition with the second number of nodes. The processor runs the routing software.
REFERENCES:
patent: 5128932 (1992-07-01), Li
patent: 5453978 (1995-09-01), Sethu et al.
patent: 5602839 (1997-02-01), Annapareddy et al.
patent: 5680116 (1997-10-01), Hashimoto et al.
patent: 5721819 (1998-02-01), Galles et al.
patent: 5740346 (1998-04-01), Wicki et al.
patent: 5751710 (1998-05-01), Crowther et al.
patent: 5751967 (1998-05-01), Raab et al.
patent: 5768501 (1998-06-01), Lewis
patent: 5781546 (1998-07-01), Sethu
patent: 5812549 (1998-09-01), Sethu
patent: 5859981 (1999-01-01), Levin et al.
patent: 5874964 (1999-02-01), Gille
patent: 5884047 (1999-03-01), Aikawa et al.
patent: 5914953 (1999-06-01), Krause et al.
patent: 5970232 (1999-10-01), Passint et al.
patent: 6005860 (1999-12-01), Anderson et al.
patent: 6031835 (2000-02-01), Abali et al.
patent: 6055618 (2000-04-01), Thorson
patent: 6064671 (2000-05-01), Killian
patent: 6097718 (2000-08-01), Bion
patent: 6137781 (2000-10-01), Goto et al.
patent: 6230252 (2001-05-01), Passint et al.
patent: 6243760 (2001-06-01), Armbruster et al.
patent: 6256295 (2001-07-01), Callon
patent: 6295573 (2001-09-01), Bailey et al.
patent: 6437804 (2002-08-01), Ibe et al.
patent: 0817097 (1997-06-01), None
Peercy, M. et al., “Distributed Algorithms for Shortest-Path, Deadlock-Free Routing and Broadcasting in Arbitrarily Faulty Hypercubes,” International Symposium on Fault Tolerant Computing Systems (FTCS), US, Los Alamitos, IEEE Comp. Soc. Press, vol. Symp. 20, Jun. 26, 1990, pp. 218-225.
Fleury, E. et al., “A General Theory for Deadlock Avoidance in Wormhole-Routed Networks,” IEEE Trans. on Parallel and Distributed Systems, IEEE Inc., NY, vol. 9, No. 7, Jul. 1, 1998, pp. 626-638.
Pifarre G. D. et al., “Adaptive Deadlock-and Livelock-Free Routing in the Hypercube Network,” IEEE Trans. on Parallel and Distributed Systems, IEEE Inc., NY, vol. 5, No. 11, Nov. 1, 1994, pp. 1121-1138.
Whay C. Lee, “Topology Aggregation for Hierarchical Routing in ATM Networks”, Apr. 1, 1995, pp. 82-92, Computer-Communication Review.
IBM, “Clustering Algorithm for Computer Network Management Graphics”, Jun. 1988, pp. 71-79, IBM Technical Disclosure Bulletin, vol. 31, No. 1.
Cassiday Daniel
Heller Steven K.
Steele, Jr. Guy L.
Wade Jon
Caldwell Andrew
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Sun Microsystems Inc.
LandOfFree
Recursive partitioning of networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Recursive partitioning of networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recursive partitioning of networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3118910