Methods and systems for scheduling a task
View Patent ↗Disclosed are the methods for scheduling a task including at least one sub-task, on one or more computing devices in a distributed computing environment. A set of computing devices are identified from the one or more computing devices, based on an availability of a set of computational resources on the set of computing devices. Each computing device in the set of computing devices is ranked based on at least one of a monetary cost or a network cost, associated with the execution of the at least one sub-task on the each computing device. The at least one sub-task is allocated to at least one computing device from the set of computing devices for execution based on at least one of the ranking or an acceptable success probability associated with the execution of the at least one sub-task.
1. A method for scheduling a task including at least one sub-task, on one or more computing devices in a distributed computing environment, the method comprising:
identifying, by one or more processors, a set of computing devices from the one or more computing devices, based on an availability of a set of computational resources on the set of computing devices, wherein the set of computational resources are required to execute the at least one sub-task;
ranking, by the one or more processors, each computing device in the set of computing devices based on weighted sum of ranks associated with a monetary cost and a network cost, associated with the execution of the at least one sub-task on the each computing device; and
allocating, by the one or more processors, the at least one sub-task to at least one computing device from the set of computing devices for execution based on at least one of the ranking or an acceptable success probability associated with the execution of the at least one sub-task, wherein the acceptable success probability corresponds to a service level agreement parameter associated the task.
2. The method of claim 1 further comprising determining, by the one or more processors, a weight parameter for the at least one sub-task based on at least one of the set of computational resources required to execute the at least one sub-task or a first time duration required to execute the at least one sub-task.
3. The method of claim 2 further comprising determining, by the one or more processors, the ranks associated with the monetary cost and the network cost are based on the corresponding weight parameters.
4. The method of claim 2 , wherein the availability of the set of computational resources on the set of computing devices corresponds to a second time duration for which the set of computational resources are available to execute the at least one sub-task, wherein the second time duration is greater than the first time duration.
5. The method of claim 1 , wherein the service level agreement associated with the task includes information pertaining to a deadline for completion of the task, a cost of executing the task, and the acceptable success probability of execution of execution of the task.
6. The method of claim 1 , wherein the set of computational resources correspond to at least one of a processing unit, a memory, or a storage space.
7. The method of claim 1 further comprising receiving, by the one or more processors, a beacon message from each of the one or more computing devices, wherein the beacon message is indicative of an availability of respective computational resources associated with each of the one or more computing devices.
8. The method of claim 1 further comprising determining, by the one or more processors, an availability of respective computational resources associated with each of the one or more computing devices based on a historical data of the availability of the respective computational resources.
9. The method of claim 1 , wherein multiple replicas of the at least one sub-task are allocated to the at least one computing device, wherein execution of the multiple replicas of the at least one sub-task increases a probability of successful execution of the at least one sub-task.
10. The method of claim 9 , wherein a number of replicas of the at least one sub-task is determined based on the probability of successful execution of the at least one sub-task and the acceptable success probability.
11. The method of claim 1 further comprising determining, by the one or more processors, an aggregated network cost associated with the execution of the task based on the network cost associated with the execution of the at least one sub-task.
12. The method of claim 11 further comprising modifying, by the one or more processors, the allocation of the at least one sub-task based on the aggregated network cost.
13. A system for scheduling a task including at least one sub-task, on one or more computing devices in a distributed computing environment, the system comprising:
one or more processors configured to:
determine a weight parameter for the at least one sub-task based on at least one of a set of computational resources required to execute the at least one sub-task or a first time duration required to execute the at least one sub-task;
identify a set of computing devices from the one or more computing devices, based on an availability of the set of computational resources on the set of computing devices;
rank each computing device in the set of computing devices based on weighted sum of ranks associated with a monetary cost and a network cost, associated with the execution of the at leastone sub-task on the each computing device, wherein the ranks associated with the monetary cost and the network cost are determined based on the corresponding weight parameters; and
allocate the at least one sub-task to at least one computing device from the set of computing devices for execution based on at least one of the ranking or an acceptable success probability associated with the execution of the at least one sub-task, wherein the acceptable success probability corresponds to a service level agreement parameter associated the task.
14. The system of claim 13 , wherein the one or more processors are further configured to extract the task from a queue of tasks.
15. The system of claim 13 , wherein the availability of the set of computational resources on the set of computing devices corresponds to a second time duration for which the set of computational resources are available to execute the at least one sub-task, wherein the second time duration is greater than the first time duration.
16. The system of claim 13 , wherein the service level agreement associated with the task includes information pertaining to a deadline for completion of the task, a cost of execute the task, and the acceptable success probability of execution of the task.
17. The system of claim 13 , wherein multiple replicas of the at least one sub-task are allocated to the at least one computing device, wherein execution of the multiple replicas of the at least one sub-task increases a probability of successful execution of the at least one sub-task.
18. The system of claim 17 , wherein a number of replicas of the at least one sub-task is determined based on the probability of successful execution of the at least one sub-task and the acceptable success probability.
19. The system of claim 13 , wherein the at least one sub-task is executed in a predetermined time period, the predetermined time period being divided into one or more time slots, wherein a chronologically first time slot in the predetermined time period is utilized for scheduling the at least one sub-task.
20. A computer program product for use with a computing device, the computer program product comprising a non-transitory computer readable medium, the non-transitory computer readable medium stores a computer program code for scheduling a task including at least one sub-task, on one or more computing devices in a distributed computing environment, the computer program code is executable by one or more processors in the computing device to:
identify a set of computing devices from the one or more computing devices, based on an availability of a set of computational resources on the set of computing devices, wherein the set of computational resources are required to execute the at least one sub-task;
rank each computing device in the set of computing devices based on weighted sum of ranks associated with a monetary cost and a network cost, associated with the execution of the at least one sub-task on the each computing device; and
allocate the at least one sub-task to at least one computing device from the set of computing devices for execution based on at least one of the ranking or an acceptable success probability associated with the execution of the at least one sub-task, wherein the acceptable success probability corresponds to a service level agreement parameter associated the task.
21. A method for scheduling a task including at least one sub-task, on one ormore cloud computing infrastructures, the method comprising:
determining, by one or more processors, availability of one or more virtual machines associated with each of the one or more cloud computing infrastructures, wherein the one or more virtual machines are operable to execute the at least one sub-task;
ranking, by the one or more processors, the one or more virtual machines associated with each of the one or more cloud computing infrastructures based on weighted sum of ranks associated with a monetary cost and a network cost, associated with the execution of the at least one sub-task on the one or more virtual machines; and
allocating, by the one or more processors, the at least one sub-task to at least one virtual machine from the one or more virtual machines for execution, based on at least one of the ranking or an acceptable success probability associated with the execution of the at least one sub-task, wherein the acceptable success probability corresponds to a service level agreement parameter associated the task.
22. The method of claim 21 , wherein the one or more virtual machines are located in different cloud computing infrastructures.