Optimized job scheduling and execution in a distributed computing grid
First Claim
1. A machine readable storage device comprising instructions which, when executed, cause a machine to perform operations comprising:
- selecting a total cost combination of nodes and links from among valid combinations of nodes and links from a network with capability and capacity over time to complete a computer-executable job by a deadline;
setting costs associated with different combinations of the nodes and the links from the network of nodes to zero;
determining whether the combinations of the nodes and the links with the capability and the capacity over time to complete the computer-executable job by the deadline are valid based on determining a possible validity of a given node by comparing job information with;
stored node characteristics of the given node, and stored link characteristics of the links associated with the give node;
scheduling a first node for the selected combination of the nodes and the links to execute the computer-executable job, the scheduling based on binary machine code comprising the computer executable job; and
reserving link capacity of a link connected to the first node, to match a job transport capacity requirement of the computer-executable job.
1 Assignment
0 Petitions
Accused Products
Abstract
A disclosed example involves determining whether there is at least one valid combination of nodes and links from the network of nodes with capability and capacity over time to complete a computer-executable job by a deadline. A total cost combination of nodes and links is selected from among the at least one valid combination of nodes and links with the capability and capacity over time to complete the computer-executable job by the deadline. The computer-executable job is scheduled to be executed on at least one selected node. The scheduling is based on compiled instructions comprising the computer-executable job. At least some of the link capacity of at least one of the links connected to the at least one selected node is reserved, to match a job transport capacity requirement of the computer-executable job.
9 Citations
14 Claims
-
1. A machine readable storage device comprising instructions which, when executed, cause a machine to perform operations comprising:
- selecting a total cost combination of nodes and links from among valid combinations of nodes and links from a network with capability and capacity over time to complete a computer-executable job by a deadline;
setting costs associated with different combinations of the nodes and the links from the network of nodes to zero;
determining whether the combinations of the nodes and the links with the capability and the capacity over time to complete the computer-executable job by the deadline are valid based on determining a possible validity of a given node by comparing job information with;
stored node characteristics of the given node, and stored link characteristics of the links associated with the give node;
scheduling a first node for the selected combination of the nodes and the links to execute the computer-executable job, the scheduling based on binary machine code comprising the computer executable job; and
reserving link capacity of a link connected to the first node, to match a job transport capacity requirement of the computer-executable job. - View Dependent Claims (2, 3, 4, 5, 6, 7)
- selecting a total cost combination of nodes and links from among valid combinations of nodes and links from a network with capability and capacity over time to complete a computer-executable job by a deadline;
-
8. A machine readable storage device comprising instructions which, when executed, cause a machine to perform operations comprising:
- determining which nodes from a network of nodes connected by links are capable of executing a computer-executable job by;
determining a planned utilization of the links over time, limited by a capability and a capacity of the respective links;
determining a planned utilization of the nodes over time, limited by a capability and a capacity of the respective nodes;
determining zero or more candidate nodes having a capability and a capacity that meets or exceeds specified requirements of the computer-executable job;
for each of the candidate nodes, determining link requirements over time on the links if the computer-executable job were executed at that candidate node;
determining whether the link requirements for the candidate nodes can be met, given the planned utilization of the links over time; and
determining zero or more candidate nodes as valid nodes that allow link requirements to be met, while executing the computer-executable job;
analyzing measures of total cost associated with execution of the computer-executable job on respective one of the nodes that were determined to be capable of executing the computer-executable job;
based on a measure of least total cost associated with the execution of the computer executable job on the respective nodes, selecting a selected node from the network of nodes to execute the computer-executable job, the selection based on object code comprising the computer-executable job;
scheduling the computer-executable job for execution; and
causing the computer-executable job to be executed at the selected node. - View Dependent Claims (9, 10, 11, 12, 13)
- determining which nodes from a network of nodes connected by links are capable of executing a computer-executable job by;
-
14. A machine readable storage device comprising instructions which, when executed, cause a machine to perform operations comprising:
- determining abilities of respective nodes to execute a computer-executable job at a given time by;
determining a planned utilization of the respective nodes over time, limited by a capability and a capacity of the respective nodes; and
determining zero or more candidate nodes having a capability and a capacity that satisfies specified requirements of the computer-executable job;
determining whether there is a valid combination of the nodes and links with capability and capacity over time to complete the computer-executable job by a deadline based on determining a possible validity of a given candidate node by comparing job information with node characteristics of the candidate node and link characteristics of the links associated with the candidate node;
determining costs to execute the computer-executable job at respective ones of the nodes in the valid combination at the given time;
selecting a total cost combination of the nodes and the links from among the valid combination; and
scheduling the computer-executable job to execute on a first one of the nodes from the valid combination that has a lowest cost to execute the computer-executable job at the given time, the scheduling of the computer-executable job based on object code comprising the computer-executable job.
- determining abilities of respective nodes to execute a computer-executable job at a given time by;
Specification