This thesis proposes a combinatorial auction-based marketplace mechanism for cloud
computing services, which allows users to reserve arbitrary combination of services at
requested timeslots, prices and quality of service. The proposed mechanism helps enterprise
users build workflow applications in a cloud computing environment, specifically on the
platform-as-a-service, where the users need to compose multiple types of services at different
timeslots.
The proposed marketplace mechanism consists of a forward market for an advance
reservation and a spot market for an immediate allocation of services. Each market employs
mixed integer programming to enforce a Pareto optimum allocation with maximized social
economic welfare, as well as double-sided auction design to encourage both users and
providers to compete for buying and selling the services.
A marketplace simulator, named W-Mart, is specially developed for this thesis. It
implements the proposed mechanism on Java platform being powered by CPLEX, the
state-of-the-art MIP solver. W-Mart is designed after the multi-agent virtual market system
U-Mart, and is also capable to deal with human agents and machine agents at the same time.
Three experiments are carried out by means of multi-agent simulations. First, the
accuracy of the combinatorial allocation scheme is validated. The result demonstrates that it
works properly. Second, the overhead of the proposed market mechanism including MIP
solver is assessed. The result shows that the overhead is acceptable to deal with an expected
number of participants within the proposed trading schedule. Third, the performances of four
types of market mechanisms are extensively evaluated. The results clarify that (1) the
proposed forward/combinatorial mechanism outperforms other non-combinatorial and/or
non-reservation (spot) mechanisms in both user-centric rationality and global efficiency, (2)
running both a forward market and a spot market improves resource utilization without
disturbing advance reservations, and (3) the users' preference between the forward market
and the spot market affects the performance of whole marketplace significantly in tight
demand/supply conditions.
Study on Combinatorial Auction Mechanism for Resource Allocation in Cloud Computing Environment
運用要項