Distributed computer

• US 7,937,704 B2
• Filed: 06/19/2003
• Issued: 05/03/2011
• Est. Priority Date: 06/20/2002
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: McKee, Paul F
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): ARCOS, CAROLINE H
• Application Number:
  US10/517,434
• Publication Number:
  US 20050257220A1
• Time in Patent Office: 2,875 Days
• Field of Search: 718/104, 718/100, 718/102, 709/201, 709/221, 709223-226, 709/227, 709/229
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/505 Clust
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

A distributed computing network is disclosed, the membership of which is determined in accordance with policy data stored at existing member nodes. A node wishing to join the distributed computing network sends profile data indicating the resources it has available for shared computation to a member node. The member node compares the resources with the requirement indicated in the priority data. If the comparison indicates that the applicant node should join, then data indicating the topology of the distributed computing network is updated at the member node and created at the applicant node. This allows for the creation of a distributed computing network whose topology is well-suited to a given task, provided the policy properly reflects the requirements of the task.

Claims

1. A method of dividing a task amongst a plurality of nodes within a distributed computer, said method comprising:

operating each of said plurality of nodes, each of said nodes having recorded therein graph data representing a task-suited logical network comprising a plurality of nodes and the links between them, to

receive immediate neighbour requirements data indicating desired properties of immediate neighbour nodes in a task-suited logical network of nodes and interconnections between them, which properties lead to said task-suited logical network being suited to said task or tasks of a similar type, said requirements data including distinctive immediate neighbour requirements data indicating desired immediate neighbour properties which differ from immediate neighbour properties for one or more other nodes;

receive node capability data from an applicant node available to join said task suited logical network;

determine whether to allow said applicant node to become an immediate neighbour in dependence upon said distinctive immediate neighbour requirements data and said node capability data; and

update said stored graph data on deciding to grant a task-suited logical network connection request received from an applicant node, send a response to the applicant node sending said request indicating that said request was successful, and distribute said task amongst the plurality of nodes in accordance with the task-suited logical network topology thus determined.

2. A method according to claim 1 wherein said immediate neighbour requirements data comprises one or more property-value pairs.

3. A method according to claim 2 wherein said immediate neighbour requirements data is arranged in accordance with a predefined data structure defined by requirements format data stored in said computer, said method further comprising the step of verifying that said immediate neighbour requirements data is formatted in accordance with predefined data structure by comparing said immediate neighbour requirements data to said requirements format data.

4. A method according to claim 1 wherein said node capability data comprises one or more property-value pairs.

5. A method according to claim 4 wherein said node capability data is arranged in accordance with a predefined data structure defined by node capability format data stored in said computer, said method further comprising that said node capability data is formatted in accordance with predefined data structure by comparing said node capability data to said node capability format data.

6. A method according to claim 1 further comprising the step of operating a node seeking to join said task-suited logical network to generate node capability data and send said data to one or more nodes already included within said task-suited logical network.

7. A method according to claim 1 wherein said task distribution involves a node forwarding a task to a node which neighbours it in said task-suited logical network topology.

8. A method according to claim 1 wherein said immediate neighbour requirements data comprises data relating to the amount of data storage or processing power available at said node.

9. A method according to claim 1 wherein said immediate neighbour requirements data comprises data relating to the quality of communication between said node and one or more nodes already selected for said task-suited logical network.

10. Distributed computer apparatus comprising:

a plurality of data processor nodes, each connected to at least one other of said data processor nodes via a communications link;

each of said nodes having recorded therein;

a) task-suited logical network membership policy data, said logical network membership policy data including distinctive immediate neighbour requirements data indicating desired immediate neighbour properties which differ from immediate neighbour properties for one or more other nodes;

b) graph data representing a task-suited logical network comprising a plurality of nodes and the links between them; and

c) processor readable code executable to update said graph data, said code comprising;

task-suited logical network membership request generation code executable to generate and send a task-suited logical network membership request including node profile data to another node indicated to be a member of said task-suited logical network;

task-suited logical network membership request handling code executable to receive a task-suited logical network connection request including node profile data, and decide whether said request is to be granted in dependence upon the task-suited logical network distinctive immediate neighbour requirements data stored at each of said nodes; and

task-suited logical network membership update code executable to update said stored graph data on deciding to grant a task-suited logical network connection request received from an applicant node, and to send a response to the applicant node sending said request indicating that said request is successful.

11. Distributed computer apparatus according to claim 10, wherein each node further has recorded therein node profile data generation code executable to generate said node profile data.

12. Distributed computer apparatus according to claim 10 or claim 11, wherein each node further has recorded therein task-suited logical network policy data distribution code executable to distribute said policy data, said policy distribution code comprising:

policy input code operable to receive policy data;

policy storage code operable to store said received policy data at said node; and

policy forwarding code operable forward said policy from said node to at least one other node in said distributed computer apparatus.

13. Distributed computer apparatus according to claim 10, wherein each node further has recorded therein policy format data;

and policy data format verification code executable to check that said received policy data accords with said policy format data.

14. Distributed computer apparatus according to claim 10, wherein each node further has recorded therein profile format data;

and profile data format verification code executable to check that said received node profile data accords with said profile format data.

15. Distributed computer apparatus according to claim 10, wherein each node further has recorded therein received program data execution code executable to receive program data from another of said nodes and to execute said program.

16. Distributed computer apparatus according to claim 15, wherein said plurality of processor nodes comprise computers executing different operating systems programs, and said received program execution code is further executable to provide a similar execution environment on nodes despite the differences in said operating system programs.

17. A method of operating a member node of a distributed computing network, said method comprising:

accessing task-suited logical network connection policy data including distinctive immediate neighbour requirements data comprising one or more property-value pairs indicating one or more criteria for becoming an immediate neighbour of said member node in a task-suited logical network built on said distributed computing network, said node having recorded therein graph data representing a task-suited logical network comprising a plurality of nodes and the links between them;

receiving, from an applicant node, profile data comprising one or more property-value pairs indicating characteristics of the applicant node;

determining whether said applicant profile data indicates that said applicant node meets said connection criteria for becoming an immediate neighbour of said node in said task-suited logical network; and

responsive to said determination indicating that said applicant node meets said connection criteria, updating task-suited logical network membership data accessible to said node to indicate that said applicant node is an immediate neighbour of said member in said task-suited logical network, including updating said stored graph data on deciding to grant a task-suited logical network connection request received from an applicant node, and sending a response to the applicant node sending said request indicating that said request was successful.

18. A method according to claim 17 wherein said member node stores graph data representing a task-suited logical network comprising a plurality of nodes and the links between them.

19. A method according to claim 18 wherein said member node stores said task-suited logical network connection policy data.

20. A method according to claim 19 further comprising the steps of:

updating task-suited logical network connection policy data;

removing indications that one or more nodes are members of said task-suited

logical network from said graph data; and

sending an indication to said one or more nodes requesting them to re-send said profile data.

21. A computer storage containing a computer program product loadable into a memory of a digital computer at a node of a plurality of nodes in a distributed computing network and executable by the digital computer, wherein the computer program comprises:

task-suited logical network immediate neighbour requirements data reception code to receive and store received task-suited logical network immediate neighbour requirements data, wherein said requirements data includes distinctive immediate neighbour requirements data indicating desired immediate neighbour properties which differ from immediate neighbour properties for one or more other nodes, each of said nodes having recorded therein graph data representing a task suited logical network comprising a plurality of nodes and the links between them;

node capability profile data reception code to receive and store received node capability profile data;

comparison code to compare said node capability data and said distinctive immediate neighbour requirements data to find whether the node represented by said node capability data meets said distinctive immediate neighbour requirements data;

task-suited logical network topology update code to add an identifier of said represented node to a task-suited logical network topology data structure on said comparison code indicating that said represented node meets said requirements; and

task execution code to update said stored graph data on deciding to grant a task-suited logical network connection request received from an applicant node, to send a response to the applicant node sending said request indicating that said request was successful, to receive code from another node in said task-suited logical network and to execute said code or forward said code to a node represented as an immediate neighbour in said task-suited logical network topology data structure.

22. A method of operating a plurality of nodes in a distributed network to create a logical network topology based on the physical topology of said network, said logical network topology being suited to a task, said method comprising:

identifying a member node as a member of said task-suited logical network, each of said nodes having recorded therein graph data representing a task-suited logical network comprising a plurality of nodes and the links between them;

storing immediate neighbour requirements data including distinctive immediate neighbour requirements data representing what is required of nodes in order for them to be a suitable immediate neighbour of said member node in said task-suited logical network;

storing candidate neighbour node capability data representing the capabilities of a candidate neighbour node in said physical network;

operating said network to compare said candidate neighbour node capability data with said distinctive immediate neighbour requirements data of the node of which the candidate neighbour node seeks to be an immediate neighbour; and

responsive to said comparison indicating that said candidate neighbour node meets said requirements, making said candidate node an immediate neighbour in said logical network, and updating said stored graph data on deciding to grant a task-suited logical network connection request received from said candidate node, and sending a response to the candidate node sending said request indicating that said request was successful.