メカニズムデザインに基づくマルチティアサーバシステムのQoS公平化

摘要

マルチティアサーバシステムは,複数のティアによってタスクを処理する分散システムである.マルチティァサーバシステムにおいて,過負荷状態を回避しつつQoS (Quality of Service)を公平化するリソース配分問題が研究されている.このときサーバは,クライアントの実行するアプリケーションのQoSに関する情報をあらかじめ知る必要がある.一方,クライアントが各自の実行するアプリケーションの QoSを最大化するように利己的に行動する場合には,サーバに対し虚偽の表明を行う可能性がある.本報告では,この問題をゲーム理論的状況としてモデル化し,クライアントの虚偽の表明に対してペナルティをかけることにより,クライアント間の QoS の公平化を実現するメ力ニズムを提案する.%We consider a resource allocation problem that ensures a fair QoS (Quality of Service) level among clients in a multi-tier server system. The multi-tier server system is a distributed system that processes tasks by multiple tiers. To avoid the overload conditions, the fair QoS based resource allocation has been studied. Selfish clients want to maximize their own QoS levels of executed applications. So, they may reveal incorrect QoS characteristics of their tasks in order to get more resources. This situation can be modeled in a game theoretic setting. The server can observe the QoS levels of applications which are executed by the clients. We propose a resource allocation mechanism which imposes penalties on the clients revealing incorrect QoS characteristics so as to achieve a fair resource allocation.