OPTIMIZED JOB SCHEDULING AND EXECUTION IN A DISTRIBUTED COMPUTING GRID

• US 20130219407A1
• Filed: 03/15/2013
• Published: 08/22/2013
• Est. Priority Date: 01/27/2004
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Weinman, Joseph B. Jr.
• Granted Patent: US 9,128,775 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9023 for implementing a jitter-buffer

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.

Claims

1. A tangible machine readable storage medium comprising instructions which, when executed, cause a machine to perform a method comprising:

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;

selecting a total cost combination of nodes and links 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;

scheduling the computer-executable job to be executed on at least one selected node, the scheduling based on compiled instructions comprising the computer-executable job; and

reserving at least some of the link capacity of at least one of the links connected to the at least one selected node, to match a job transport capacity requirement of the computer- executable job.

2. The tangible machine readable storage medium of claim 1, wherein the scheduling of the computer-executable job on the at least one selected node is based on respective abilities of the nodes to execute the computer-executable job at a given time.

3. The tangible machine readable storage medium of claim 1, wherein the method further comprises determining costs to execute the computer-executable job at respective nodes at a given time, and wherein the scheduling of the computer-executable job on the at least one selected node is based on the at least one selected node having a lowest cost.

4. The tangible machine readable storage medium of claim 1, wherein the method further comprises:

storing job metadata for the computer-executable job in a job metadata storage;

storing node characteristics in a node characteristics storage;

storing link characteristics in a link characteristics storage; and

determining a possible validity of a given node by comparing the job metadata with the node characteristics of the given node and the link characteristics.

5. The tangible machine readable storage medium of claim 1, wherein the method further comprises:

storing node-specific cost data in a node cost storage;

storing link-specific cost data for combinations of job metadata, nodes, and links in a link cost storage; and

determining a total cost corresponding to the total cost combination of nodes and links based on the job metadata, the node-specific cost data, and the link-specific cost data.

6. The tangible machine readable storage medium of claim 5, wherein the link-specific cost data includes at least one of:

at least one rate dependent on volume of bandwidth;

at least one rate dependent on volume of data transported;

at least one rate dependent on level of jitter;

at least one rate dependent on dropped packets;

or

at least one rate dependent on network latency

7. The tangible machine readable storage medium of claim 5, wherein the node-specific cost data includes at least one of:

at least one rate dependent on processor utilization;

or

at least one rate dependent on storage utilization

8. The tangible machine readable storage medium of claim 5, wherein the job metadata includes a cost function dependent on completion delay.

9. The tangible machine readable storage medium of claim 1, further comprising setting costs associated with different combinations of nodes and links from the network of nodes to zero before 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 the computer-executable job by the deadline.

10. A tangible machine readable storage medium comprising instructions which, when executed, cause a machine to perform a method comprising:

determining which nodes from a network of nodes connected by links are capable of executing a computer-executable job;

analyzing measures of total cost associated with execution of the computer-executable job on respective nodes that were determined to be capable of executing the computer-executable job;

based on a measure of least total cost associated with execution of the computer-executable job on the respective nodes, selecting at least one selected node from the network of nodes for executing the computer-executable job, the selection based on compiled instructions comprising the computer-executable job;

scheduling the computer-executable job for execution; and

causing the computer-executable job to be executed at the at least one selected node.

11. The tangible machine readable storage medium of claim 10, wherein the analyzing measures of total cost, includes at least one of:

evaluating at least one rate dependent on volume of bandwidth;

evaluating at least one rate dependent on volume of data transported;

evaluating at least one rate dependent on level of jitter;

evaluating at least one rate dependent on dropped packets;

or

evaluating at least one rate dependent on network latency.

12. The tangible machine readable storage medium of claim 10, wherein the analyzing measures of total cost, includes at least one of:

evaluating at least one rate dependent on processor utilization;

or

evaluating at least one rate dependent on storage utilization.

13. The tangible machine readable storage medium of claim 10, wherein the analyzing measures of total cost, includes evaluating at least one cost function dependent on completion delay.

14. The tangible machine readable storage medium of claim 10, wherein determining which nodes are capable of executing the computer-executable job includes:

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 candidate node, 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 each candidate node can be met, given the planned utilization of the links over time; and

determining zero or more valid nodes to be those candidate nodes that allow link requirements to be met, while executing the computer-executable job.

15. The tangible machine readable storage medium of claim 10, wherein the selecting the at least one selected node, includes:

determining a total cost to execute the computer-executable job for each valid node; and

selecting the at least one selected node such that there is no other valid node with a lower total cost.

16. The tangible machine readable storage medium of claim 15, wherein the method further comprises:

selecting a planned node from among the at least one selected node;

reserving at least a portion of a remaining capability and capacity of each of the links that are required to meet the specified requirements of the computer-executable job planned to be executed at the planned node;

reserving at least a portion of a remaining capability and capacity of the planned node required to meet the requirements of the computer-executable job; and

causing the computer-executable job to be executed at the planned node.

17. A tangible machine readable storage medium comprising instructions which, when executed, cause a machine to perform a method comprising:

determining abilities of respective nodes to execute a computer-executable job at a given time;

determining whether there is at least one valid combination of nodes and links with capability and capacity over time to complete the computer-executable job by a deadline;

determining costs to execute the computer-executable job at the respective nodes at the given time;

selecting a total cost combination of nodes and links 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; and

scheduling the computer-executable job for execution on at least a first node from the network of nodes that is able to execute the computer-executable job and that has a lowest cost to execute the computer-executable job at the at least the first node at the given time, the scheduling of the computer-executable job for execution on the at least the first node being based on compiled instructions comprising the computer-executable job.

18. The tangible machine readable storage medium of claim 17, wherein the method further comprises determining a possible validity of a given node by comparing job metadata of the computer-executable job with node characteristics of the given node and link characteristics.