Method of scheduling hosts for software updates in a distributed computer network

• US 20040243996A1
• Filed: 05/29/2003
• Published: 12/02/2004
• Est. Priority Date: 05/29/2003
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: Leighton, F. Thomson, Sheehy, Justin J.
• Granted Patent: US 7,203,745 B2
• Time in Patent Office: Days
• US Class Current: 717/174
• CPC Class Codes: G06F 8/61 Installation

Abstract

A method of and system for managing installs to a set of one or more field machines in a distributed network environment. In an illustrative embodiment, the system includes at least one change coordinator server that includes a database with data identifying a current state of each field machine, and a change controller routine for initiating a given control action to initiate an update to the current state on a given field machine. In particular, the change controller routine may include a scheduling algorithm that evaluates data from the database and identifies a set of field machines against which the given control action may be safely executed at a given time. At least one install server is responsive to the change controller routine initiating the given control action for invoking the update to the current state on the given field machine.

Claims

1. A method of scheduling hosts to timeslots to enable a given control action, wherein given hosts are associated with one or more potentially overlapping constraint sets and/or have given precedent relationships, comprising:

maintaining a given state of a set of hosts;

generating a first rank order of the hosts by assigning to each host a cumulative value of all constraint sets in which that host is contained;

altering the first rank order to accommodate precedent relationships, if any, to generate a second rank order of the hosts; and

executing a given heuristic against the second rank order.

2. The method as described in claim 1 wherein the given heuristic assigns hosts into a set of one or more timeslots in a greedy fashion.

3. The method as described in claim 1 wherein hosts are pulled from the second rank order and pushed into a first timeslot t₁ until a given constraint is violated.

4. The method as described in claim 3 further including the step of continuing to pull hosts from the second rank order and pushing the hosts into a set of one or more additional timeslots until all hosts have been assigned to a timeslot t_n.

5. The method as described in claim 1 wherein executing the given heuristic identifies a subset of the hosts against which the given control action may be safely executed at a given time.

6. The method as described in claim 1 wherein the given control action is a software install.

7. A method of scheduling hosts to timeslots to enable a given control action, wherein given hosts are associated with one or more potentially overlapping constraint sets and/or have given precedent relationships, comprising:

maintaining a given state of a set of hosts;

generating a rank order of the hosts by assigning to each host a cumulative value of all constraint sets in which that host is contained; and

executing a given heuristic against the rank order, wherein the given heuristic assigns hosts into a set of one or more timeslots in a greedy fashion.

8. The method as described in claim 7 wherein hosts are pulled from the rank order and pushed into a first timeslot t₁ until a given constraint is violated.

9. The method as described in claim 8 further including the step of continuing to pull hosts from the rank order and pushing the hosts into a set of one or more additional timeslots until all hosts have been assigned to a timeslot t_n.

10. The method as described in claim 7 wherein executing the given heuristic identifies a subset of the hosts against which the given control action may be safely executed at a given time.

11. The method as described in claim 7 wherein the given control action is a software install.