Method, apparatus and articles-of-manufacture for network-based distributed computing

• US 6,757,730 B1
• Filed: 05/31/2000
• Issued: 06/29/2004
• Est. Priority Date: 05/31/2000
• Status: Expired due to Term

• Current Assignee: Cloud Software Group
• Original Assignee: DataSynapse, Inc. (Cloud Software Group)
• Inventors: Lee, Peter, Bernardin, James
• Primary Examiner(s): Burgess, Glenton B.
• Assistant Examiner(s): PARTON, KEVIN S
• Application Number:
  US09/583,244
• Time in Patent Office: 1,490 Days
• Field of Search: 709/104, 709/201, 709/226, 709/244, 709/202
• US Class Current: 709/226
• CPC Class Codes: G06F 9/465 Distributed object oriented systems remote method invocation [RMI] G06F9/548

Abstract

An Internet-based, secure, distributed task-brokering and parallel-processing method/system/article-of-manufacture advantageously leverages under-utilized network-based computing resources for bandwidth-intensive and/or computationally-intensive problems, and provides significant cost advantages over traditional coarse-grained parallel computing techniques.

Claims

1. A distributed computing system, implemented as a multi-tiered server/meta-server architecture using a plurality of network-connected processing elements, the distributed computing system comprising:

at least one network-connected processing element configured as a director;

a plurality of network-connected processing elements configured as brokers;

a plurality of network-connected processing elements configured as engines; and

,

at least one network-connected processing element configured as a driver;

wherein;

the director is configured to (i) maintain a registry of driver(s), (ii) maintain a registry of engines, (iii) maintain load balance among brokers, and (iv) assign driver(s) to broker(s);

the brokers are configured to (i) receive job(s), each comprised of at least one task and at least some comprised of a plurality of tasks, from their assigned driver(s), (ii) manage the execution of said task(s) by engine(s), and (iii) collate result(s) of executed task(s), so as to make completed job(s) available for delivery to driver(s);

each of the brokers is further configured to maintain a plurality of task queues for each active job, the plurality of queues including (i) a waiting task queue of task(s) that have not yet been assigned to an engine for execution, wherein the order of tasks in the waiting task queue represents the order in which tasks will be assigned to available engines, (ii) a pending task queue of task(s) that have been assigned to an engine, but have not completed, and (iii) a completed task queue of task(s) that have been executed by an engine;

the engines are configured to (i) receive tasks from the brokers, (ii) execute the received tasks, and (iii) return executed tasks to their associated brokers; and

,

at least some of the brokers are further configured to monitor their pending task queues to identify long-pending task(s) that have been pending substantially longer than an average task completion time for task(s) in the associated job, and resubmit long-pending task(s) to the job'"'"'s waiting task queue;

whereby brokers assign and supervise the execution of task(s), engines receive and execute task(s), driver(s) query assigned broker(s) to receive job results, and the director monitors the overall operation of brokers and engines.

2. A distributed computing system, as defined in claim 1, wherein said resubmitted long-pending task(s) have their ranking re-prioritized in the waiting task queue.

3. A distributed computing system, as defined in claim 1, wherein said resubmitted long-pending task(s) are placed at the front of the corresponding waiting task queue.

4. A distributed computing system, implemented as a multi-tiered server/meta-server architecture using a plurality of network-connected processing elements, the distributed computing system comprising:

at least one network-connected processing element configured as a director;

a plurality of network-connected processing elements configured as brokers;

a plurality of network-connected processing elements configured as engines; and

,

at least one network-connected processing element configured as a driver;

wherein;

the director is configured to (i) maintain a registry of driver(s), (ii) maintain a registry of engines, (iii) maintain load balance among brokers, and (iv) assign driver(s) to broker(s);

the brokers are configured to (i) receive job(s), each comprised of at least one task and at least some comprised of a plurality of tasks, from their assigned driver(s), (ii) manage the execution of said task(s) by engine(s), and (iii) collate result(s) of executed task(s), so as to make completed job(s) available for delivery to driver(s);

the engines are configured to (i) receive tasks from the brokers, (ii) execute the received tasks, and (iii) return executed tasks to their associated brokers; and

,

the system is further configured to detect aberrant performance of engines performing assigned task(s) by comparing the actual engine performance of engine(s) assigned to execute task(s) to stored performance metric(s);

whereby brokers assign and supervise the execution of task(s), engines receive and execute task(s), driver(s) query assigned broker(s) to receive job results, and the director monitors the overall operation of brokers and engines.

5. A distributed computing system, implemented as a multi-tiered server/meta-server architecture using a plurality of network-connected processing elements, the distributed computing system comprising:

at least one network-connected processing element configured as a director;

a plurality of network-connected processing elements configured as brokers;

a plurality of network-connected processing elements configured as engines; and

,

at least one network-connected processing element configured as a driver;

wherein;

the director is configured to (i) maintain a registry of driver(s), (ii) maintain a registry of engines, (iii) maintain load balance among brokers, and (iv) assign driver(s) to broker(s);

the brokers are configured to (i) receive job(s), each comprised of at least one task and at least some comprised of a plurality of tasks, from their assigned driver(s), (ii) manage the execution of said task(s) by engine(s), and (iii) collate result(s) of executed task(s), so as to make completed job(s) available for delivery to driver(s);

the engines are configured to (i) receive tasks from the brokers, (ii) execute the received tasks, and (iii) return executed tasks to their associated brokers; and

,

the system is further configured to detect aberrant performance of engines performing assigned task(s) by comparing the actual performance of multiple engines executing similar tasks;

whereby brokers assign and supervise the execution of task(s), engines receive and execute task(s), driver(s) query assigned broker(s) to receive job results, and the director monitors the overall operation of brokers and engines.

6. A distributed computing system, implemented as a multi-tiered server/meta-server architecture using a plurality of network-connected processing elements, the distributed computing system comprising:

at least one network-connected processing element configured as a director;

a plurality of network-connected processing elements configured as brokers;

a plurality of network-connected processing elements configured as engines; and

,

at least one network-connected processing element configured as a driver;

wherein;

the director is configured to (i) maintain a registry of driver(s), (ii) maintain a registry of engines, (iii) maintain load balance among brokers, and (iv) assign driver(s) to broker(s);

the brokers are configured to (i) receive job(s), each comprised of at least one task and at least some comprised of a plurality of tasks, from their assigned driver(s), (ii) manage the execution of said task(s) by engine(s), and (iii) collate result(s) of executed task(s), so as to make completed job(s) available for delivery to driver(s);

the engines are configured to (i) receive tasks from the brokers, (ii) execute the received tasks, and (iii) return executed tasks to their associated brokers; and

,

the system is further configured to detect aberrant performance of engines performing assigned task(s) and prevent assignment of additional tasks to engines that display aberrant performance;

whereby brokers assign and supervise the execution of task(s), engines receive and execute task(s), driver(s) query assigned broker(s) to receive job results, and the director monitors the overall operation of brokers and engines.

7. A method for operating a distributed computing system, implemented as a multi-tiered server/meta-server architecture using a plurality of network-connected processing elements, the method comprising:

configuring at least one network-connected processing element as a director;

configuring a plurality of network-connected processing elements as brokers;

configuring a plurality of network-connected processing elements as engines;

using the director to (i) maintain a registry of engines and (ii) maintain load balance among brokers;

using the brokers to (i) assign tasks to engines and (ii) manage the execution of tasks by engines;

using at least some of the brokers to (i) identify long-pending task(s) that have been pending substantially longer than an average task completion time and (ii) resubmit long-pending task(s); and

,

using the engines to (i) receive tasks from the brokers, (ii) execute the received tasks, and (iii) return executed tasks to their associated brokers;

whereby brokers assign and supervise the execution of tasks, engines receive and execute tasks, and the director monitors the overall operation of brokers and engines.

8. A method, as defined in claim 7, further comprising associating an increased priority with resubmitted long-pending tasks.

9. A method, as defined in claim 7, further comprising placing resubmitted long-pending tasks at the front of a waiting task queue.

10. A method for operating a distributed computing system, implemented as a multi-tiered server/meta-server architecture using a plurality of network-connected processing elements, the method comprising:

configuring at least one network-connected processing element as a director;

configuring a plurality of network-connected processing elements as brokers;

configuring a plurality of network-connected processing elements as engines;

using the director to (i) maintain a registry of engines and (ii) maintain load balance among brokers;

using the brokers to (i) assign tasks to engines, (ii) manage the execution of tasks by engines and (iii) detect aberrant engine performance by comparing the actual engine performance of engine(s) assigned to execute task(s) to stored performance metric(s); and

,

using the engines to (i) receive tasks from the brokers, (ii) execute the received tasks, and (iii) return executed tasks to their associated brokers;

whereby brokers assign and supervise the execution of tasks, engines receive and execute tasks, and the director monitors the overall operation of brokers and engines.

11. A method, as defined in claim 10, further comprising preventing engines that display aberrant performance from receiving additional tasks.

12. A method for operating a distributed computing system, implemented as a multi-tiered server/meta-server architecture using a plurality of network-connected processing elements, the method comprising:

configuring at least one network-connected processing element as a director;

configuring a plurality of network-connected processing elements as brokers;

configuring a plurality of network-connected processing elements as engines;

using the director to (i) maintain a registry of engines and (ii) maintain load balance among brokers;

using the brokers to (i) assign tasks to engines, (ii) manage the execution of tasks by engines and (iii) detect aberrant engine performance by comparing the actual performance of multiple engines executing similar tasks; and

,

using the engines to (i) receive tasks from the brokers, (ii) execute the received tasks, and (iii) return executed tasks to their associated brokers;

whereby brokers assign and supervise the execution of tasks, engines receive and execute tasks, and the director monitors the overall operation of brokers and engines.

13. A method, as defined in claim 12, further comprising preventing engines that display aberrant performance from receiving additional tasks.

14. A method for operating a distributed computing system, implemented as a multi-tiered server/meta-server architecture using a plurality of network-connected processing elements, the method comprising:

configuring at least one network-connected processing element as a director;

configuring a plurality of network-connected processing elements as brokers;

configuring a plurality of network-connected processing elements as engines;

using the director to (i) maintain a registry of engines and (ii) maintain load balance among brokers;

using the brokers to (i) assign service requests to engines and (ii) manage the servicing of service requests by engines;

using at least some of the brokers to (i) identify long-pending service requests that have been pending substantially longer than an average service request latency time and (ii) resubmit long-pending service requests; and

,

using the engines to (i) receive service requests from the brokers and (ii) provide requested services;

whereby brokers assign service requests and supervise their servicing, engines receive assigned service requests and perform requested services, and the director monitors the overall operation of brokers and engines.

15. A method, as defined in claim 14, further comprising associating an increased priority with resubmitted long-pending service requests.

16. A method, as defined in claim 14, further comprising placing resubmitted long-pending service requests at the front of a waiting request queue.