# US 2014/0237468 A1 · Token-Based Adaptive Task Management for Virtual Machines

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0237468 A1
- Document ID: US20140237468A1
- Status: Published application
- Kind: A1
- Application number: 13/772,556
- Filed: 2013-02-21
- Published: 2014-08-21
- Earliest claimed: 2013-02-21
- Assignees: VMware, Inc.
- Applicants: Vmware, Inc.
- Inventors: Aalap Desai; Chirag Bhatt
- Web page: https://patentgrep.com/patent/US20140237468A1

## CPC

- G06F 9/5083: {Techniques for rebalancing the load in a distributed system}
- G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments perform adaptive throttling of tasks into a virtual datacenter having dynamically changing resources. Tasks are processed concurrently in batches. The rate of change in throughput at different batch sizes is calculated. With each iteration, the batch size is increased or decreased based on the rate of change to achieve a maximum throughput for given resources and load on the virtual datacenter.

## Claims

### Claim 1

A system for achieving maximal throughput in a virtual datacenter having dynamically changing resources, said system comprising:
a memory area associated with a task management device, said memory area storing a plurality of outstanding tasks to be performed by a plurality of virtual machines (VMs) executing in the virtual datacenter; and
a processor programmed to:
normalize the outstanding tasks stored in the memory area by assigning a quantity of tokens to each of the outstanding tasks, the tokens representing an amount of work performed by the virtual datacenter when performing the outstanding tasks, the assigned quantity of tokens representing a second token batch size;
measure, by the task management device, a first throughput at a first token batch size and a second throughput at the second token batch size;
calculate, by the task management device, a rate of change between the measured first throughput at the first token batch size and the measured second throughput at the second token batch size; and
identify an output token batch size by:
if the calculated rate of change is negative, identify an output token batch size based on a combination of the first token batch size and the second token batch size; and
otherwise, select, by the task management device, a third token batch size and repeat said measure, said calculate, and said identify using the second token batch size as the first token batch size and the third token batch size as the second token batch size during the repeating.

### Claim 2 (depends on 1)

The system of claim 1, wherein the processor is further programmed to select a quantity of the normalized outstanding tasks, the selected quantity corresponding to the identified output token batch size.

### Claim 3 (depends on 2)

The system of claim 2, wherein the processor is further programmed to identify the selected quantity of the normalized outstanding tasks to the virtual datacenter.

### Claim 4 (depends on 1)

The system of claim 1, wherein the tokens represent an amount of resources consumed by the virtual datacenter when performing the outstanding tasks.

### Claim 5 (depends on 1)

The system of claim 1, wherein the processor is further programmed to receive the plurality of outstanding tasks from a client device.

### Claim 6 (depends on 1)

The system of claim 1, wherein the processor is programmed to normalize the outstanding tasks by assigning the quantity of tokens to each of the outstanding tasks based on the amount of resources to be consumed during performance of each of the outstanding tasks, wherein each of the tokens represents consumption of the same amount of resources.

### Claim 7 (depends on 1)

The system of claim 1, wherein the memory area further stores values, each value representing an amount of resources to be consumed by each of the tasks, and wherein the memory area further stores values representing an amount of resources available in the virtual datacenter.

### Claim 8 (depends on 7)

The system of claim 7, wherein the processor is further programmed to update the values representing the amount of resources available in the virtual datacenter as resources are added and/or removed from the virtual datacenter.

### Claim 9 (depends on 1)

The system of claim 1, wherein each of the plurality of outstanding tasks stored in the memory area is associated with a task type, each task type being associated with an amount of resources to be consumed.

### Claim 10 (depends on 1)

The system of claim 1, further comprising means for iteratively determining an optimal token batch size to achieve optimal throughput in the virtual datacenter.

### Claim 11

A method for iteratively determining an optimal amount of work to be performed efficiently by a computing device, the method comprising:
measuring, by a task management device, a first throughput at a first token batch size and a second throughput at a second token batch size, the first token batch size and the second token batch size each representing an amount of work performed by a computing device;
calculating, by the task management device, a rate of change between the measured first throughput at the first token batch size and the measured second throughput at the second token batch size;
selecting, by the task management device, a third token batch size based on the calculated rate of change;
providing a quantity of tasks corresponding to the selected third token batch size to the computing device for processing; and
repeating said measuring, said calculating, said selecting, said providing, and said repeating using the second token batch size as the first token batch size and the third token batch size as the second token batch size during said repeating.

### Claim 12 (depends on 11)

The method of claim 11, wherein calculating the rate of change comprises calculating a gradient.

### Claim 13 (depends on 12)

The method of claim 12, wherein selecting the third token batch size comprises selecting the third token batch size based on the calculated gradient.

### Claim 14 (depends on 11)

The method of claim 11, wherein if the calculated rate of change is negative, further comprising throttling the amount of work performed by the computing device.

### Claim 15 (depends on 14)

The method of claim 14, wherein throttling the amount of work comprises reducing the quantity of tasks to be performed by rejecting and/or queuing one or more of the tasks.

### Claim 16 (depends on 11)

The method of claim 11, wherein measuring the second throughput at the second token batch size comprises measuring the second throughput at a second token batch size selected based on a quantity of outstanding tasks to be performed by the computing device.

### Claim 17

One or more computer-readable storage media including computer-executable instructions that, when executed, cause at least one processor to intermittently identify maximal throughput in an environment having dynamically changing resources by:
measuring, by a task management device, a first throughput at a first token batch size and a second throughput at a second token batch size, the token batch size representing an amount of work performed by a computing device;
calculating, by the task management device, a rate of change between the measured first throughput at the first token batch size and the measured second throughput at the second token batch size; and
identifying an output batch size by:
if the calculated rate of change is negative, allocating a quantity of tokens based at least on the first token batch size to outstanding tasks to be performed by the computing device; and
otherwise, selecting, by the task management device, a third token batch size and repeating said measuring, said calculating, and said identifying using the second token batch size as the first token batch size and the third token batch size as the second token batch size during said repeating.

### Claim 18 (depends on 17)

The computer storage media of claim 17, wherein the computer-executable instructions further cause the processor to normalize the outstanding tasks by weighting each of the outstanding tasks based on anticipated resource usage during performance of the outstanding task.

### Claim 19 (depends on 18)

The computer storage media of claim 18, wherein the computer-executable instructions cause the processor to normalize the outstanding tasks by grouping the outstanding tasks into categories and dynamically weighting each of the categories.

### Claim 20 (depends on 18)

The computer storage media of claim 18, wherein the computer-executable instructions cause the processor to normalize the outstanding tasks by associating a quantity of tokens with each of the outstanding tasks based on the anticipated resource usage during performance of the outstanding task.
