Method and apparatus for allocating tasks to remote networked processors

• US 6,112,243 A
• Filed: 12/30/1996
• Issued: 08/29/2000
• Est. Priority Date: 12/30/1996
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Downs, Terry, Kisor, Gregory Hurst
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): KIM, HAROLD J
• Application Number:
  US08/777,487
• Time in Patent Office: 1,338 Days
• Field of Search: 395/200.3, 395/200.31, 395/200.32, 395/200.48, 395/200.49, 395/200.54, 395/200.55, 395/200.56, 340/825.5, 709/200, 709/201, 709/202, 709/218, 709/219, 709/222, 709/224, 709/225, 709/226
• US Class Current: 709/226
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method and apparatus for providing remote, distributed processing of a task by employing a wide area network (e.g., the Internet). A resource provider initiates the process by sending an application to a resource allocator requesting to be added to the resource allocator'"'"'s list of providers. The resource allocator accepts or rejects a particular resource provider based on the application. If accepted, the resource provider waits for a task from the resource allocator. Upon receiving a task, the resource provider evaluates the currently available local resources. The resource provider determines whether or not it is currently able to handle the task in view of the available local resources. If the resource provider is able to handle the task, it accepts the task. The resource provider processes the task and returns the results to either the resource allocator or the original resource requester. If the resource provider is unable to handle the task in view of the current load, the resource provider notifies the resource allocator or the resource requester that it is unable to complete the task.

Claims

1. A method of allocating tasks among resource providers which may be intermittently reachable over a network, comprising:

determining potential resource providers for performing different tasks;

receiving a task request having required resource for performing a task from a requester;

first identifying at least one available resource provider having said required resource for performing the task;

receiving information required to accomplish the requested task;

second identifying at least one available resource provider having said required resource for performing the task;

distributing the task and the information required to accomplish the task to one of said at least one available resource provider;

receiving a status response from one of said at least one available resource provider indicating willingness or unwillingness to perform the distributed task; and

if the status response indicates willingness to perform, then allocating completion of the distributed task thereto.

2. A method according to claim 1, further comprising:

wherein said second identifying confirms continued availability of said at least one available resource provider identified from said first identifying.

3. The method of claim 1, further comprising:

determining if there are too few willing resource providers to complete the task.

4. The method of claim 3, further comprising:

wherein if there are too few willing resource providers, then third identifying of additional available resource providers to perform the task.

5. The method of claim 3, further comprising:

receiving completion of task data from each of said at least one available resource provider by E-mail.

6. The method of claim 1, wherein said completion of task data is received by E-mail.

7. A method according to claim 1, in which the task has associated costs/constraints, and wherein said identifying said at least one available resource provider comprises:

selecting from said at least one resource provider a candidate resource provider having associated capabilities; and

comparing said capabilities of the candidate resource provider with said task costs/constraints.

8. A method according to claim 1, further comprising:

determining if insufficient resource providers are available to process the task, and

if so, deferring allocating the task by E-mailing said task request to said at least one resource provider.

9. A method according to claim 1, wherein said determining potential resource providers comprises:

polling a network connection to identify active connections between a task allocator and said potential resource providers.

10. A method according to claim 1, further comprising:

receiving notification from a first one of said potential resource providers that said first one has idle resources; and

transmitting cost/constraints of the task to said first one so as to allow said first one to determine if it has sufficient resources to perform the task.

11. The method of claim 1, further comprising:

notifying the allocator, by said potential resource providers, of interest in receiving tasks distributed by said allocator.

12. A method for an allocator to allocate a task among potential resource providers, comprising:

determining potential resource providers for performing different tasks;

receiving a task request specifying resource required to perform a task;

first identifying one available resource provider having the resource to perform the task;

receiving information required to accomplish the task;

second identifying one available resource provider having the resource to perform the task;

distributing the task to said one available resource provider;

receiving a status response from said available resource provider indicating said willingness or unwillingness to perform the task; and

if the status response indicates willingness to perform, then allocating completion of the distributed task thereto.

13. A method according to claim 12, wherein distributing the task and receiving the completion of task data is performed by E-mail.

14. A method according to claim 12, wherein determining said status response comprises:

identifying available provider resources;

comparing said available provider resources to said required resource; and

if said comparing indicates availability of said required resource to process the task, then sending the status response indicating willingness to perform the task.

15. The method of claim 14, the method further comprising:

receiving plural task requests from a requestor;

wherein distributing the task comprises distributing at least one of said plural task requests to said available resource provider.

16. The method of claim 12, the method further comprising:

receiving plural task requests from a requestor;

wherein distributing the task comprises distributing at least one of said plural task requests to said available resource provider.

17. A method according to claim 12, wherein determining said status response comprises:

determining an associated payment for processing the task; and

determining if said associated payment is sufficient, and if so, sending the status response configured to indicate willingness to perform the task.

18. A method for a resource provider to process a task distributed by a task allocator, comprising:

first identifying available provider resources;

notifying the allocator, if available resources are identified, that the resource provider wants to receive tasks distributed by said allocator;

receiving from the allocator a task request specifying resource required to perform the task, information required to accomplish the requested task, and a processing fee;

second identifying of available provider resources to confirm availability of said specified resource for accomplishing the task; and

determining willingness or unwillingness to perform the task based at least in part on said processing fee and said second identifying.

19. A method according to claim 18, wherein the task is received by E-mail.

20. The method of claim 18, further comprising:

determining a worst-case performance completion estimate; and

submitting the worst-case performance to the allocator.

21. A readable medium having instructions encoded thereon for allocating tasks among resource providers, said instructions capable of directing a processor to:

determine potential resource providers for performing a task;

receive a task request specifying required resource for performing the task;

first identify one available resource provider having the specified resource to perform the task;

receive information required to accomplish the requested task;

second identify one available resource provider having the specified resource to perform the task;

distribute the task to said available resource provider;

receive a status response from said available resource provider indicating willingness or unwillingness to perform the distributed task; and

if the status response indicates willingness to perform, then allocate completion of the distributed task thereto.

22. The medium of claim 21, wherein said second identifying confirms continued availability of said at least one available resource provider identified from said first identifying.

23. The medium of claim 21, said instructions including further instructions capable of directing the processor to:

determine if there are too few willing resource providers to complete the task.

24. The medium of claims 23, said instructions including further instructions capable of directing the processor to:

determine if there are too few willing resource providers, and if so, third identify of additional available resource providers to perform the task.

25. The medium of claim 23, said instructions including further instructions capable of directing the processor to:

receive completion of task data from each of said at least one available resource provider by E-mail.

26. The medium of claim 21, wherein said completion of task data is received by E-mail.

27. The medium of claim 21, in which the task has associated costs/constraints, and wherein said instructions for identifying said at least one available resource provider comprises instructions capable of directing the processor to:

select from said at least one resource provider a candidate resource provider having associated capabilities; and

compare said capabilities of the candidate resource provider with said task costs/constraints.

28. The medium of claim 21, said instructions including further instructions capable of directing the processor to:

determine if insufficient resource providers are available to process the task; and

if so, deferring allocating the task by E-mailing said task request to said at least one resource provider.

29. The medium of claim 21, wherein said instructions for determining potential resource providers comprises instructions capable of directing the processor to:

poll a network connection to identify active connections between a task allocator and said potential resource providers.

30. The medium of claim 21, said instructions including further instructions capable of directing the processor to:

receive notification from a first one of said potential resource providers that said first one has idle resources; and

transmit cost/constraints of the task to said first one so as to allow said first one to determine if it has sufficient resources to perform the task.

31. The medium of claim 21, said instructions including further instructions capable of directing the processor to:

notify the allocator, by said potential resource providers, of interest in receiving tasks distributed by said allocator.

32. A readable medium having instructions encoded thereon for allocating tasks among resource providers, said instructions capable of directing a processor to:

determine potential resource providers for performing different tasks;

receive a task request specifying resource required to perform a task;

first identify one available resource provider having the resource to perform the task;

receive information required to accomplish the task;

second identify one available resource provider having the resource to perform the task;

distribute the task to said one available resource provider;

receive a status response from said available resource provider indicating said willingness or unwillingness to perform the task; and

if the status response indicates willingness to perform, then allocate completion of the distributed task thereto.

33. The medium of claim 32, wherein distributing the task is performed by E-mail.

34. The medium of claim 32, wherein said instructions for determining said status response comprises instructions capable of directing the processor to:

identify available provider resources;

compare said available provider resources to said required resource; and

determine if said comparing indicates availability of said required resource to process the task, and if so, then send the status response indicating willingness to perform the task.

35. The medium of claim 34, said instructions including further instructions capable of directing the processor to:

receive plural task requests from a requester;

wherein said instructions for distributing the task comprises further instructions for distributing at least one of said plural task requests to said available resource provider.

36. The medium of claim 32, said instructions including further instructions capable of directing the processor to:

receive plural task requests from a requestor;

wherein said instructions for distributing the task comprises further instructions for distributing at least one of said plural task requests to said available resource provider.

37. The medium of claim 32, wherein said instructions for determining said status response comprises instructions capable of directing the processor to:

determine an associated payment for processing the task; and

determine if said associated payment is sufficient, and if so, send the status response configured to indicate willingness to perform the task.

38. A readable medium having instructions encoded thereon for a resource provider to process a task distributed by a task allocator, said instructions capable of directing a processor to:

first identify available provider resources;

notify the allocator, if available resources are identified, that the resource provider wants to receive tasks distributed by said allocator;

receive from the allocator a task request specifying resource required to perform the task, information required to accomplish the requested task, and a processing fee;

second identify of available provider resources to confirm availability of said specified resource for accomplishing the task; and

determine willingness or unwillingness to perform the task based at least in part on said processing fee and said second identifying.

39. The medium of claim 38, wherein the task is received by E-mail.

40. The medium of claim 38, said instructions including further instructions capable of directing the processor to:

determine a worst-case performance completion estimate; and

submit the worst-case performance to the allocator.