SYSTEM AND METHOD FOR REDUCING STATE SPACE IN REINFORCED LEARNING BY USING DECISION TREE CLASSIFICATION

• US 20160275412A1
• Filed: 03/17/2015
• Published: 09/22/2016
• Est. Priority Date: 03/17/2015
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Lu, Lei, Padala, Pradeep, Holler, Anne, Zhu, Xiaoyun
• Granted Patent: US 10,460,254 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

An automatic scaling system and method for reducing state space in reinforced learning for automatic scaling of a multi-tier application uses a state decision tree that is updated with new states of the multi-tier application. When a new state of the multi-tier application is received, the new state is placed in an existing node of the state decision tree only if a first attribute of the new state is same as a first attribute of any state contained in the existing node and a second attribute of the new state is sufficiently similar to a second attribute of each existing state contained in the existing node based on a similarity measurement of the second attribute of each state contained in the existing node with the second attribute of the new state.

Claims

1. A method for reducing state space in reinforced learning for automatic scaling of a multi-tier application, the method comprising:

receiving a new state of the multi-tier application to be added to a state decision tree for the multi-tier application, the new state including a first attribute and a second attribute;

placing the new state in an existing node of the state decision tree only if the first attribute of the new state is same as the first attribute of any state contained in the existing node and the second attribute of the new state is sufficiently similar to a second attribute of each existing state contained in the existing node based on a similarity measurement of the second attribute of each state contained in the existing node with the second attribute of the new state; and

executing the reinforced learning using the state decision tree with the new state to automatically scale the multi-tier application.

2. The method of claim 1, further comprising:

receiving another new state of the multi-tier application to be added to the state decision tree for the multi-tier application; and

placing the another new state in a new node in the state decision tree only if a first attribute of the another new state differs from a first attribute of each state included in the state decision tree.

3. The method of claim 1, further comprising:

receiving another new state of the multi-tier application to be added to the state decision tree for the multi-tier application, the another new state having a first attribute that is same as a first attribute of a state in a node of the state decision tree;

placing the another new state in a new node of the state decision tree only if the second attribute of the another new state is not sufficiently similar to a second attribute of each state contained in the node based on a similarity measurement of the second attribute of each state contained in the node with the second attribute of the another new state.

4. The method of claim 1, wherein the similarity measurement includes an amount of change in a statistical measure of values of the second attribute of each state contained in the existing node when values of the second attribute of the new state are added to the values of the second attribute of each state contained in the existing node.

5. The method of claim 4, wherein the placing of the new state in the existing node of the state decision tree includes placing the new state in the existing node of the state decision tree only if the first attribute of the new state is same as the first attribute of any state contained in the existing node and a difference between a current statistical measure of the values of the second attribute of each existing state contained in the existing node and a new statistical measure of the values of the second attribute of each existing state contained in the existing node with the values of the second attribute of the new state exceeds a threshold.

6. The method of claim 4, wherein the current statistical measure is a standard deviation of the values of the second attribute of each existing state contained in the existing node and the new statistical measure is a standard deviation of the values of the second attribute of each existing state contained in the existing node with the values of the second attribute of the new state.

7. The method of claim 1, wherein the first attribute of the new state of the multi-tier application includes numbers of virtual machines running in different tiers of the multi-tier application.

8. The method of claim 7, wherein the second attribute of the new state of the multi-tier application includes performance measures for the different tiers of the multi-tier application.

9. The method of claim 8, wherein the performance measures for the different tiers of the multi-tier application include performance latencies of the different tiers of the multi-tier application.

10. A computer-readable storage medium containing program instructions for a method for reducing state space in reinforced learning for automatic scaling of a multi-tier application, wherein execution of the program instructions by one or more processors of a computer system causes the one or more processors to perform steps comprising:

receiving a new state of the multi-tier application to be added to a state decision tree for the multi-tier application, the new state including a first attribute and a second attribute;

placing the new state in an existing node of the state decision tree only if the first attribute of the new state is same as the first attribute of any state contained in the existing node and the second attribute of the new state is sufficiently similar to a second attribute of each existing state contained in the existing node based on a similarity measurement of the second attribute of each state contained in the existing node with the second attribute of the new state; and

executing the reinforced learning using the state decision tree with the new state to automatically scale the multi-tier application.

11. The computer-readable storage medium of claim 10, wherein the steps further comprises:

receiving another new state of the multi-tier application to be added to the state decision tree for the multi-tier application; and

placing the another new state in a new node in the state decision tree only if a first attribute of the another new state differs from a first attribute of each state included in the state decision tree.

12. The computer-readable storage medium of claim 10, wherein the steps further comprises:

receiving another new state of the multi-tier application to be added to the state decision tree for the multi-tier application, the another new state having a first attribute that is same as a first attribute of a state in a node of the state decision tree;

placing the another new state in a new node of the state decision tree only if the second attribute of the another new state is not sufficiently similar to a second attribute of each state contained in the node based on a similarity measurement of the second attribute of each state contained in the node with the second attribute of the another new state.

13. The computer-readable storage medium of claim 10, wherein the similarity measurement includes an amount of change in a statistical measure of values of the second attribute of each state contained in the existing node when values of the second attribute of the new state are added to the values of the second attribute of each state contained in the existing node.

14. The computer-readable storage medium of claim 13, wherein the placing of the new state in the existing node of the state decision tree includes placing the new state in the existing node of the state decision tree only if the first attribute of the new state is same as the first attribute of any state contained in the existing node and a difference between a current statistical measure of the values of the second attribute of each existing state contained in the existing node and a new statistical measure of the values of the second attribute of each existing state contained in the existing node with the values of the second attribute of the new state exceeds a threshold.

15. The computer-readable storage medium of claim 14, wherein the current statistical measure is a standard deviation of the values of the second attribute of each existing state contained in the existing node and the new statistical measure is a standard deviation of the values of the second attribute of each existing state contained in the existing node with the values of the second attribute of the new state.

16. The computer-readable storage medium of claim 10, wherein the first attribute of the new state of the multi-tier application includes numbers of virtual machines running in different tiers of the multi-tier application.

17. The computer-readable storage medium of claim 16, wherein the second attribute of the new state of the multi-tier application includes performance measures for the different tiers of the multi-tier application.

18. The computer-readable storage medium of claim 17, wherein the performance measures for the different tiers of the multi-tier application include performance latencies of the different tiers of the multi-tier application.

19. An automatic scaling system for automatic scaling of a multi-tier application supported by hardware in a distributed computer system comprising:

a monitoring server configured to collect state information of the multi-tier application;

a reinforced learning module configured to perform reinforced learning using a state decision tree generated using the state information of the multi-tier application;

a decision tree classifier module configured to create and modify the state decision tree for the multi-tier application, the decision tree classifier module being configured to received a new state of the multi-tier application to be added to a state decision tree for the multi-tier application, the new state including a first attribute and a second attribute, the decision tree classifier module being configured to place the new state in an existing node of the state decision tree only if the first attribute of the new state is same as the first attribute of any state contained in the existing node and the second attribute of the new state is sufficiently similar to a second attribute of each existing state contained in the existing node based on a similarity measurement of the second attribute of each state contained in the existing node with the second attribute of the new state.

20. The automatic scaling system of claim 19, wherein the decision tree classifier module is further configured to:

receive another new state of the multi-tier application to be added to the state decision tree for the multi-tier application; and

place the another new state in a new node in the state decision tree only if a first attribute of the another new state differs from a first attribute of each state included in the state decision tree.

21. The automatic scaling system of claim 19, wherein the decision tree classifier module is further configured to:

receive another new state of the multi-tier application to be added to the state decision tree for the multi-tier application, the another new state having a first attribute that is same as a first attribute of a state in a node of the state decision tree;

place the another new state in a new node of the state decision tree only if the second attribute of the another new state is not sufficiently similar to a second attribute of each state contained in the node based on a similarity measurement of the second attribute of each state contained in the node with the second attribute of the another new state.

22. The automatic scaling system of claim 19, wherein the similarity measurement includes an amount of change in a statistical measure of values of the second attribute of each state contained in the existing node when values of the second attribute of the new state are added to the values of the second attribute of each state contained in the existing node.

23. The automatic scaling system of claim 19, wherein the first attribute of the new state of the multi-tier application includes numbers of virtual machines running in different tiers of the multi-tier application, and wherein the second attribute of the new state of the multi-tier application includes performance measures for the different tiers of the multi-tier application.