M.Sc Thesis

M.Sc StudentPosener Eyal
SubjectDynamic Memory Allocation in Cloud Computers Using
Progressive Second Price Auction
DepartmentDepartment of Computer Science
Supervisor PROF. Assaf Schuster
Full Thesis textFull thesis text - English Version


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 progressive second price (PSP) auction. 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 make 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.

Ginseng was experimented and simulated under different conditions, in order 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.