Technical Report MSC-2013-16

Title: Dynamic Memory Allocation in Cloud Computers using Progressive Second Price Auction
Authors: Eyal Posener
Supervisors: Assaf Schuster
Abstract: Physical memory is the most expensive resource in today's cloud computing platforms. Cloud providers would like to maximize their clients' satisfaction by renting precious physical memory to those clients who value it the most. But real-world cloud clients are selfish: they will only tell their providers the truth about how much they value memory when it is in their own best interest to do so. Under these conditions, how can providers find an efficient memory allocation that maximizes client satisfaction?

This research presents Ginseng, the first market-driven framework for efficient allocation of physical memory to selfish cloud clients. Ginseng incentivizes selfish clients to bid their true value for the memory they need when they need it. Ginseng continuously collects client bids, finds an efficient memory allocation, and re-allocates physical memory to the clients that value it the most.

We bring two major modifications of the known PSP auction, as presented by Lazar and Semret. The one is a change of the bidding language. The player may bid with a list of allowed and forbidden memory regions. This makes players with non-concave and non-monotonically rising valuation function to consider participating in the auction. The second is a change of the social cost function. A term of memory exchange penalty is added to the social cost in order to reduce the costly memory exchanges in the system. Those modifications among some other minor modifications, makes the PSP auction useful for auctioning memory.

In this research, an approach for a new type of application for efficient memory allocation in a dynamic memory cloud computer is suggested. The efficiency of the approach is demonstrated through a special developed benchmark called Memory Consumer and a modification of a widely used caching application called Memcached. An approach for notifying the guest in advance that its memory allocation is going to change is also presented. It is shown that by letting the guest prepare for a memory change, the performance can be improved. Higher memory usage without OS interference was enabled by changing the OS default configuration. It is demonstrated that in the not-overcommitted system, higher performance was achieved.

An experimental environment was developed to test Ginseng under different workloads, simulate it under different conditions, and compare the results to determine system efficiency. Ginseng was shown to achieve a x6.2 - x31.5 improvement in aggregate client satisfaction, or x1.6 in the application performance when compared with state-of-the-art approaches for cloud memory allocation. It achieved 83% - 100% of the optimal aggregate client satisfaction.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2013
To the main CS technical reports page

Computer science department, Technion