Optimized job scheduling and execution in a distributed computing grid

• US 10,333,812 B2
• Filed: 06/27/2017
• Issued: 06/25/2019
• Est. Priority Date: 01/27/2004
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Weinman, Jr., Joseph B.
• Primary Examiner(s): Mirza, Adnan M
• Application Number:
  US15/634,605
• Publication Number:
  US 20170302555A1
• Time in Patent Office: 728 Days
• 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

Disclosed example methods for scheduling a computer-executable job include determining valid combinations of nodes and links from a network of nodes interconnected by links, the valid combinations of nodes and links having capability and capacity to complete the computer-executable job; determining, from the valid combinations of nodes and links, first combinations of nodes and links based on a total cost associated with execution of the computer-executable job on corresponding ones of the valid combinations of nodes and links; selecting one of the first combinations of nodes and links based on a load balancing status between the first combinations of nodes and links; and scheduling the computer-executable job to be executed by the one of the first combinations of nodes and links.

Claims

1. A method, comprising:

determining, by a system including a processor, valid combinations of nodes and links from a network of nodes interconnected by links, the valid combinations of nodes and links having a capability and capacity to complete a computer-executable job;

determining, by the system, from the valid combinations of nodes and links, first combinations of nodes and links based on a total cost associated with execution of the computer-executable job on corresponding ones of the valid combinations of nodes and links;

selecting, by the system, one of the first combinations of nodes and links based on a load balancing status between the first combinations of nodes and links; and

scheduling, by the system, the computer-executable job to be executed by the one of the first combinations of nodes and links.

2. The method of claim 1, wherein the total cost is based on at least one of:

a rate dependent on volume of bandwidth;

a rate dependent on volume of data transported;

a rate dependent on level of jitter;

a rate dependent on dropped packets;

a rate dependent on network latency;

a rate dependent on processor utilization;

a rate dependent on storage utilization;

a rate dependent on completion delay;

or

any combination thereof.

3. The method of claim 1, further including tracking a number of computer-executable jobs scheduled for respective second combinations of nodes and links.

4. The method of claim 1, further including reserving link capacity for the computer-executable job prior to scheduling the computer-executable job for execution by the one of the first combinations of nodes and links.

5. The method of claim 1, further including monitoring execution of the computer-executable job by the one of the first combinations of nodes and links.

6. The method of claim 1, wherein the valid combinations of nodes and links are identified as having capability and capacity to complete the computer-executable job by comparing job metadata for the computer-executable job with node characteristics and link characteristics for a given combination of a node and a link over a given time.

7. A machine readable storage device comprising instructions that, when executed by a machine, cause the machine to perform operations, the operations comprising:

determining valid combinations of nodes and links from a network of nodes interconnected by links, the valid combinations of nodes and links having a capability and capacity to complete a computer-executable job;

determining from the valid combinations of nodes and links, first combinations of nodes and links based on a total cost associated with execution of the computer-executable job on corresponding ones of the valid combinations of nodes and links, the first combinations of nodes and links having total costs that match to within a threshold amount;

selecting one of the first combinations of nodes and links based on a load balancing status between the first combinations of nodes and links; and

scheduling the computer-executable job to be executed by the one of the first combinations of nodes and links.

8. The machine readable storage device of claim 7, wherein the total cost is based on at least one of

a rate dependent on volume of bandwidth;

a rate dependent on volume of data transported;

a rate dependent on level of jitter;

a rate dependent on dropped packets;

a rate dependent on network latency;

a rate dependent on processor utilization;

a rate dependent on storage utilization;

a rate dependent on completion delay;

or

any combination thereof.

9. The machine readable storage device of claim 7, wherein the instructions, when executed, further cause the machine to track a number of computer-executable jobs scheduled for respective second combinations of nodes and links.

10. The machine readable storage device of claim 7, wherein the instructions, when executed, further cause the machine to reserve link capacity for the computer-executable job prior to scheduling the computer-executable job for execution by the one of the first combinations of nodes and links.

11. The machine readable storage device of claim 7, wherein the instructions, when executed, further cause the machine to monitor execution of the computer-executable job by the one of the first combinations of nodes and links.

12. The machine readable storage device of claim 7, wherein the valid combinations of nodes and links are identified as having capability and capacity to complete the computer-executable job by comparing job metadata for the computer-executable job with node characteristics and link characteristics for a given combination of a node and a link over a given time.

13. An apparatus, comprising:

at least one processor; and

a memory that includes executable instructions that, when executed by the at least one processor, cause the at least one processor to perform operations, the operations including;

determining valid combinations of nodes and links from a network of nodes interconnected by links, the valid combinations of nodes and links having a capability and capacity to complete a computer-executable job;

determining from the valid combinations of nodes and links, a first combination of nodes and links and a second combination of nodes and links, the first and second combinations having a same total cost, the total cost based on the execution of the computer-executable job on corresponding ones of the first and second combinations of nodes and links;

selecting the first combination of nodes and links or the second combination of nodes and links based on a load balancing status between the first and second combinations of nodes and links; and

scheduling the computer-executable job to be executed by the selected one of the first combination of nodes and links or the second combination of nodes and links.

14. The apparatus of claim 13, wherein the total cost is based on at least one of:

a rate dependent on volume of bandwidth;

a rate dependent on volume of data transported;

a rate dependent on level of jitter;

a rate dependent on dropped packets;

a rate dependent on network latency;

a rate dependent on processor utilization;

a rate dependent on storage utilization;

a rate dependent on completion delay;

or

any combination thereof.

15. The apparatus of claim 13, wherein the operations further include tracking a number of computer-executable jobs scheduled for respective second combinations of nodes and links.

16. The apparatus of claim 13, wherein the operations further include reserving link capacity for the computer-executable job prior to scheduling the computer-executable job for execution by the one of the first combinations of nodes and links.

17. The apparatus of claim 13, wherein the operations further include monitoring execution of the computer-executable job by the one of the first combinations of nodes and links.

18. The apparatus of claim 13, wherein the valid combinations of nodes and links are identified as having capability and capacity to complete the computer-executable job by comparing job metadata for the computer-executable job with node characteristics and link characteristics for a given combination of a node and a link over a given time.

19. The apparatus of claim 13, wherein the first and second combinations have the same total cost when a first total cost for the first combination is within a threshold amount of a second total cost for the second combination.