A Meta-Heuristic Approach for Dynamic Data Allocation on a Multiple Web Server System

Masaki KOHANA  Shusuke OKAMOTO  Atsuko IKEGAMI  

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.12   pp.2645-2653
Publication Date: 2013/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.2645
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
web-based application,  dynamic data allocation,  tabu search algorithm,  

Full Text: PDF(795.9KB)>>
Buy this Article

This paper describes a near-optimal allocation method for web-based multi-player online role-playing games (MORPGs), which must be able to cope with a large number of users and high frequency of user requests. Our previous work introduced a dynamic data reallocation method. It uses multiple web servers and divides the entire game world into small blocks. Each ownership of block is allocated to a web server. Additionally, the ownership is reallocated to the other web server according to the user's requests. Furthermore, this block allocation was formulated as a combinational optimization problem. And a simulation based experiment with an exact algorithm showed that our system could achieve 31% better than an ad-hoc approach. However, the exact algorithm takes too much time to solve a problem when the problem size is large. This paper proposes a meta-heuristic approach based on a tabu search to solve a problem quickly. A simulation result shows that our tabu search algorithm can generate solutions, whose average correctness is only 1% different from that of the exact algorithm. In addition, the average calculation time for 50 users on a system with five web servers is about 25.67 msec while the exact algorithm takes about 162 msec. An evaluation for a web-based MORPG system with our tabu search shows that it could achieve 420 users capacity while 320 for our previous system.