Automatic clustering for self-organizing grids

• US 9,602,573 B1
• Filed: 02/19/2013
• Issued: 03/21/2017
• Est. Priority Date: 09/24/2007
• Status: Active Grant

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: National Science Foundation (Government of the United States of America)
• Inventors: Abu-Ghazaleh, Nael, Yang, Weishuai, Lewis, Michael
• Primary Examiner(s): Chang, Jungwon
• Application Number:
  US13/770,798
• Time in Patent Office: 1,491 Days
• Field of Search: 709/209, 709/224, 709/226, 709/201, 707/100, 707/737, 713/324, 718/108, 370/310, 370/238
• US Class Current: 1/1
• CPC Class Codes: G06F 15/16 Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1044 Group management mechanisms management of multicast group membership H04L12/185; reconfiguring of node membership in a computing system to eliminate errors G06F11/1425
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

A cluster of nodes, comprising: a plurality of nodes, each having a security policy, and being associated task processing resources; a registration agent configured to register a node and issue a node certificate to the respective node; a communication network configured to communicate certificates to authorize access to computing resources, in accordance with the respective security policy; and a processor configured to automatically dynamically partition the plurality of nodes into subnets, based on at least a distance function of at least one node characteristic, each subnet designating a communication node for communicating control information and task data with other communication nodes, and to communicate control information between each node within the subnet and the communication node of the other subnets.

Claims

1. A method for clustering node devices for accomplishing a task, comprising:

automatically dynamically repartitioning a set of node devices within a communication network into a plurality of subnets as node devices join and leave the set, using a partitioning algorithm based at least a distance function of at least one node device characteristic, each subnet having a communication node device within for communicating at least control information and task data with respective communication node devices of other respective subnets, the communication node device within the each subnet being selected from among node devices within the same subnet to control each node device within the subnet,

communicating control information from the each node device within the subnet to the communication node device of the subnet in which it is partitioned, and

designating a set of preferred node devices for allocation of portions of a task, wherein the designated set is dependent on both the partitioning and the task.

2. The method according to claim 1, wherein the node devices are partitioned based on a link delay metric.

3. The method according to claim 1, wherein the at least one node device characteristic comprises a pairwise communication latency between respective node devices.

4. The method according to claim 1, wherein the automatically dynamically repartitioning is initiated prior to allocating portions of a task, and wherein partitions defined by the repartitioning are dynamically controlled in dependence on current conditions determined by at least proactive communications.

5. The method according to claim 4, wherein the proactive communications comprise a heartbeat signal.

6. The method according to claim 5, wherein the heartbeat signal is provided as part of a communication between respective node devices provided for at least one other purpose.

7. The method according to claim 1, wherein the repartitioning occurs while a task is in progress.

8. The method according to claim 1, wherein communication node devices are selected dynamically.

9. The method according to claim 1, wherein the set of node devices or organized hierarchically, in a hierarchy having at least three levels.

10. The method according to claim 9, further comprising estimating a network state representing the set of node devices based on communications with fewer than all available node devices in the set of node devices.

11. The method according to claim 1, further comprising placing a new node device within a subnet, or deleting an existing node device from the subnet, while a task is being accomplished, and reallocating a portion of the task in response to the placement of the new node device.

12. The method according to claim 1, further comprising splitting a subnet while a task is being accomplished, into a plurality of subsets, each subnet having a node device selected to be a communication node device, and reallocating a portion of the task in response to the splitting of the subnet.

13. The method according to claim 1, further comprising moving a node device from a first subnet to a second subnet while the node device is accomplishing a portion of the task, without interrupting the accomplishing the portion of the task.

14. The method according to claim 1, further comprising:

providing security policies for each respective node device;

registering node devices with at least one registration agent and upon successful registration with the registration agent, issuing a node device certificate to the respective node devices; and

communicating certificates from respective node devices for authorizing access to computing resources associated with other node devices, in accordance with the respective security policies.

15. A method for clustering node devices for accomplishing a task, comprising:

providing a network comprising node devices configured for communications, the node devices having associated computing resources for processing tasks, the node device having respective security policies;

registering node devices with at least one registration agent and upon successful registration with the registration agent, issuing a node device certificate to the respective node devices;

communicating certificates from respective node devices for authorizing access to computing resources of other node devices, in accordance with the respective security policies;

automatically dynamically partitioning a set of node devices within the network into a plurality of subnets, based on at least a distance function of at least one node device characteristic, each respective subnet having a communication node device within for communicating at least control information and task data with respective communication node devices of other respective subnets of the network, the communication node device within the each subnet being selected from among node devices within the same subnet to control each node device within the subnet; and

communicating control information between the each node device within the subnet and the communication node device of the respective subnet.

16. The method according to claim 15, further comprising designating a set of preferred node devices for allocation of portions of a task, wherein the designated set is dependent on both the partitioning and the task.

17. The method according to claim 15, wherein the at least one node device characteristic comprises a pairwise communication latency between respective node devices.

18. The method according to claim 15, wherein the automatically dynamically partitioning is dynamically controlled in dependence on current conditions determined by at least proactive communications within the network.

19. A cluster of node devices for accomplishing a task, comprising:

a plurality of node devices configured for communications, each having a respective security policy, the plurality of node devices having associated computing resources for processing tasks;

at least one registration agent configured to register a node device and upon successful registration issue a node device certificate to the respective node device;

a communication network configured to communicate certificates from a first node device to a second node device, to authorize access to computing resources of the second node device in accordance with the respective security policy of the second node device; and

at least one processor configured to automatically dynamically partition the plurality of node devices within the network into a plurality of subnets, based on at least a distance function of at least one node device characteristic, each respective subnet designating a communication node device within for communicating at least control information and task data with respective communication node devices of other respective subnets of the network, the communication node device within the each subnet being selected from among node devices within the same subnet to control each node device within the subnet, and to communicate control information between each node device within the subnet and the communication node device of other respective subnets.

20. The cluster of node devices according to claim 19, wherein at least one processor is further configured to designate a set of preferred node devices for allocation of portions of the task, wherein the designated set is dependent on both the partitioning and the task.