Study on combinatorial auction mechanism for resource allocation in Cloud computing environment クラウドコンピューティング環境における資源割り当てのための組合せオークションメカニズムに関する研究

博士論文

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.

application/pdf

総研大甲第1513号