[논문]게임 서버 클러스터에서 서버들간의 부하 균형을 고려한 게임 배치 방법

차충용; 김상철

doi:10.7583/jkgs.2012.12.3.49

게임 서버 클러스터에서 서버들간의 부하 균형을 고려한 게임 배치 방법
A Game Placement Method Considering Load Balancing between Game Servers in a Game Server Cluster 원문보기

한국게임학회 논문지 = Journal of Korea Game Society, v.12 no.3, 2012년, pp.49 - 58

차충용 (한국외국어대학교 컴퓨터공학과) , 김상철 (한국외국어대학교 컴퓨터공학과)

초록
AI-Helper

한 업체가 신규 게임 또는 사용자가 많지 않은 게임들을 서비스 하는 경우, 게임별 별도의 서버를 두는 것 보다 서버 여러 대에서 함께 서비스하는 경우가 편리할 것이다. 본 논문에서는 동일 성능의 서버들로 구성된 클러스터 상에서 게임 여러 개를 효과적으로 서버에 배치하는 방법을 제안한다. 우리의 방법에 의하면, 서버들간 부하 불균등을 줄여 사용자 기각률을 최소화할 수 있는 게임 배치를 구할 수 있다. 본 논문에서 제안한 방법은 게임 서비스 시 서버 수, 서버당 게임 수 등과 같은 서버 운영 사항들을 결정하는데 도움을 줄 것으로 예상한다. 우리의 조사에 따르면, 서버 클러스터에서의 게임 배치에 관한 기존 연구는 거의 발표되지 않았다.

Abstract ▼ AI-Helper

When a company provides new games or games with a small number of users, it is convenient to provide the game service in which those games are placed in a server cluster instead of a separate server for an individual game. This paper proposes a method for placing games in a cluster of servers with the same capacities. The method reduces the load imbalance among servers and minimizes the rejection ratio of user requests. We expect that the proposed method is useful for determining the server operation factors such as the number of servers, the number of games for a server, etc. To our survey, little research has been published on game placement on a cluster of game servers.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

Layerx 까지만 서버에 배치한 직후 서버들간의 부하 불균형 지표를 ℒx라고 하자.
사용자가 많지 않은 게임들인 경우, 각 게임을 별도의 서버에서 운영하기 보다는 서버 여러 대에서 함께 서비스하는 경우가 편리할 것이다. 본 논문에서 우리는 서버 클러스터 상에서 게임 여러 개를 효과적으로 배치하는 방법을 제안하였다. 우리의 배치 방법은 다양한 서버 수, 서버에 배치한 최대 게임 수, 게임의 최대 복사 수 등에 대해, 서버들간 부하 불균등을 줄여 사용자 기각률을 최소화 할 수 있는 게임 배치를 구한다.
본 논문에서는 동일한 성능의 게임 서버를 클러스터 형태로 운영하는 환경에서 서버 부하가 서버들간에 최대한 균등해 사용자 기각률을 최소화 할 수 있는 게임 배치 방법을 제안한다.
게임들의 동시 접속자 수의 합계를 10,000으로 설정하고, 각 게임별 동시 접속자 수는 앞에서 언급한 인기도 비에 따라 결정하였다. 본 실험의 목적은 게임별 복사 수의 최대치, 서버별 설치할 수 있는 게임 수의 최대치, 서버 성능 및 서버 개수 등의 파라미터들이 게임 배치 및 사용자 기각률에 미치는 영향을 분석하는 것이다.

가설 설정

본 논문에서 서버 s_i들의 성능은 동일하다고 가정한다. 본 논문의 내용은 각 서버의 성능이 다른 경우에도 쉽게 확장할 수 있을 것이다.
게임의 인기도에 따라서 한개 게임을 서버 클러스터(즉, 서버 여러 대)에 배치하거나 또는 여러 게임을 서버 한대에 동시에 배치하게 될 것이다. 본 논문에서는 게임 인기도는 평균 동시 접속자 수로 측정한다고 본다.
우리의 시뮬레이션에서는 λ = 10,000으로 설정하고, 사용자의 접속 유지 시간은 같다고 가정한다.

제안 방법

첫 번째 작업은 각 게임별로 배치 수를 구하는 것이고, 두 번째 작업은 게임들을 배치한 서버들을 결정하는 것이다. 2.2절의 게임 배치 문제는 빈 패킹(bin packing) 문제의 일종으로서 NP-complete 복잡도를 갖기 때문에, 우리는 휴리스틱 알고리즘을 제안한다.
2GHz의 Pentium CPU의 컴퓨터에서 성능을 테스트하였다. 다양한 서버 개수 및 성능, 게임별 최대 설치 수에 대해서, 우리의 방법으로 게임 배치를 구한 후 사용자 요구에 대한 기각률을 시뮬레이션하였다. 게임의 인기도는 온라인 콘텐츠 사용 분석에 많이 사용되는 Zipf[12] 분포를 사용하였다.
본 논문에서 제안한 알고리즘을 VC++로 구현하고, 3.2GHz의 Pentium CPU의 컴퓨터에서 성능을 테스트하였다. 다양한 서버 개수 및 성능, 게임별 최대 설치 수에 대해서, 우리의 방법으로 게임 배치를 구한 후 사용자 요구에 대한 기각률을 시뮬레이션하였다.

대상 데이터

다양한 서버 개수 및 성능, 게임별 최대 설치 수에 대해서, 우리의 방법으로 게임 배치를 구한 후 사용자 요구에 대한 기각률을 시뮬레이션하였다. 게임의 인기도는 온라인 콘텐츠 사용 분석에 많이 사용되는 Zipf[12] 분포를 사용하였다. Zipf 분포의 특징에 따라, 게임들을 사용자들이 갖는 선호도의 내림차순으로 정렬 하면 게임별 인기도는 순번의 지수 승에 반비례하게 된다.

성능/효과

N을 증가시키면, 게임 평균 인기도 (즉, P_AVG(g_j))들의 평균값과 최대값은 줄어드는 경향이 있다. 두 번째 작업인 게임 배치는 일종의 빈패킹 문제로 볼 수 있는데, 빈은 서버에 해당되며 일정한 용량을 가지고, 게임은 빈에 배치하는 물체에 해당되며, 게임의 평균 인기도는 물체의 크기로서, 빈 패킹의 목적은 빈들간의 부하 불균형을 최소화시키는 것이라 할 수 있다. 빈 패킹 문제와 유사하게, 게임들의 평균 인기도가 작고 서로간의 차이가 적어지면, 그 만큼 서버들간의 부하 균형을 맞추기 쉽게 된다.
제안된 게임 배치 방법은 서버들간 부하 불균형을 최대한 줄여 줌을 알 수 있었다. 또한, 서버의 수, 게임의 최대 복사 수, 각 서버당 배치하는 게임의 최대 수 등이 서버들간 게임 배치의 결과에 영향을 미침을 알 수 있었다. 본 연구 결과는 여러 게임들을 동시에 운영하는 환경에서, 사용자 기각률을 최소화시키기 위한 서버의 수나 게임 배치를 결정하고자 할 때, 유용하게 이용될 수 있을 것이다.
실험 결과, 우리의 방법에서 서버의 수, 서버에 배치할 최대 게임 수, 게임의 최대 복사 수는 서버부하 및 사용자 기각률 면에서 게임 배치에 많은 영향을 미침을 알 수 있었다. 또한, 적절한 서버수나 서버 성능 또는 게임의 최대 복사 수를 선택하면, 사용자 기각률을 현저히 낮게(가능하면 0까지)하는 게임 배치를 구할 수 있음을 알 수 있었다. 본 논문에서 제안한 방법은 게임 서비스 시 서버수, 서버당 게임 수 등과 같은 서버 운영 정책을 결정하는데 큰 도움을 줄 것으로 기대한다.
시뮬레이션 시각 t에서, 게임 서버 클러스터에 대한 사용자들의 총 접속 요구 수는 평균 λ을 갖는 포아송 분포를 따르고, 게임별 접속 요구의 비율은 게임의 인기도 비율과 같다고 보았다.
실험 결과, 사용자 기각률은 게임별 복사 수의 최대치인 COG, 서버별 설치할 수 있는 게임 수의 최대치인 SC 및 서버 개수인 MAX_S에 영향을 받았다.
실험 결과, 서버들간 부하 불균형이 작은 게임 배치일수록 사용자 기각률이 낮아짐을 알 수 있었다. 제안된 게임 배치 방법은 서버들간 부하 불균형을 최대한 줄여 줌을 알 수 있었다.
실험 결과, 우리의 방법에서 서버의 수, 서버에 배치할 최대 게임 수, 게임의 최대 복사 수는 서버부하 및 사용자 기각률 면에서 게임 배치에 많은 영향을 미침을 알 수 있었다. 또한, 적절한 서버수나 서버 성능 또는 게임의 최대 복사 수를 선택하면, 사용자 기각률을 현저히 낮게(가능하면 0까지)하는 게임 배치를 구할 수 있음을 알 수 있었다.
실험 결과, 서버들간 부하 불균형이 작은 게임 배치일수록 사용자 기각률이 낮아짐을 알 수 있었다. 제안된 게임 배치 방법은 서버들간 부하 불균형을 최대한 줄여 줌을 알 수 있었다. 또한, 서버의 수, 게임의 최대 복사 수, 각 서버당 배치하는 게임의 최대 수 등이 서버들간 게임 배치의 결과에 영향을 미침을 알 수 있었다.

후속연구

또한, 적절한 서버수나 서버 성능 또는 게임의 최대 복사 수를 선택하면, 사용자 기각률을 현저히 낮게(가능하면 0까지)하는 게임 배치를 구할 수 있음을 알 수 있었다. 본 논문에서 제안한 방법은 게임 서비스 시 서버수, 서버당 게임 수 등과 같은 서버 운영 정책을 결정하는데 큰 도움을 줄 것으로 기대한다.
들의 성능은 동일하다고 가정한다. 본 논문의 내용은 각 서버의 성능이 다른 경우에도 쉽게 확장할 수 있을 것이다.
또한, 서버의 수, 게임의 최대 복사 수, 각 서버당 배치하는 게임의 최대 수 등이 서버들간 게임 배치의 결과에 영향을 미침을 알 수 있었다. 본 연구 결과는 여러 게임들을 동시에 운영하는 환경에서, 사용자 기각률을 최소화시키기 위한 서버의 수나 게임 배치를 결정하고자 할 때, 유용하게 이용될 수 있을 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	게임 배치란?	따라서 한 업체가 동시 접속자 수가 적은 게임 여러 개를 운영하고자 하는 경우, 서버 성능과 서버 수뿐만이 아니라 게임 배치의 결정도 고려하여야 한다. 여기서, 게임 배치란 각 게임을 어떤 서버에 배치하느냐는 것을 나타낸다. 게임 배치가 중요한 이유는 서버 배치 결과가 사용자 기각률에 영향을 미치기 때문이다.
	네트워크상의 서버 배치를 주제로 제시된 방법에는 어떤 방법이 있는가?	게임 서버에 관한 기존 연구는 크게 네트워크상의 서버 배치와 사용자 접속 요구의 균등 배분이라는 주제로 진행되어 왔다. 전자의 경우, 사용자와 서버간의 지연시간을 최소화하도록 사용자에게 가장 가까운 서버 배정하는 방법[6,7], 사용자와 서버간의 최대 지연 시간이라는 조건하에서 서버의 수를 최소화하는 방법[8] 등이 제시되었다. 후자의 경우, 전체 게임 맵을 여러 지역으로 나눈 후 지역별로 서버를 두어 서버 부하를 분산하는 방법[3,4,9], 신규 사용자 접속 요구에 대해 최소 부하를 갖는 서버를 동적으로 선택하는 방법[2,5] 등이 제안되었다.
	대부분의 온라인 컴퓨터 게임은 어떤 방식으로 동작하나?	대부분 온라인 컴퓨터 게임의 경우, 많은 사용자들이 동시에 서버에 접속하는 방식으로 동작한다. 상업화에 성공한 MMORPG 게임의 경우에는 그 수가 수천내지 수만에 이르지만, 출시된 지 얼마지 않은 게임, 특정 사용자 집단을 위한 게임, 또는 특정 목적 하에 만들어진 기능성 게임은 잠재 사용자수가 많지 않아 동시 접속자 수백정도에 불과한 경우가 있다.

참고문헌 (13)

D. Saha, S. Sahu, and A. Shaikh, "A service platform for online games," Proc. of the 2nd Workshop on Network and System Support for Games, pp.180-184, 2003.
Herbert Jordan, et. al, "Dynamic Load Management for MMOGs in Distributed Environments," Proc. of the 7th ACM International Conference on Computing Frontiers, pp.337-346, 2010.
F. Lu, S. Parkin, and G. Morgan. "Load balancing for massively multiplayer online games," Proc. of 5th ACM SIGCOM Workshop on Network and System Support for Games, pp.1-5, 2006.
R. Chertov and S. Fahmy. "Optimistic load balancing in a distributed virtual environment," Proc. of the 16th International Workshop on Network and Operating Systems Support for Digital Audio and Video, pp.1-6, 2006.
Rynson W.H. Lau, "Hybrid Load Balancing for Online Games," Proc. of the International Conference on Multimedia, pp.100-103, 2010.
J. Lui, M. Chan, "An Efficient Partitioning Algorithm for Distributed Virtual Environment Systems," IEEE Trans. on Parallel and Distributed System, Vol 13, No 2, pp.193-211, 2002.

상세보기
P. Morllo et al., "Improving the Performance of Distributed Virtual Environment Systems," IEEE Trans on Parallel and Distributed Systems, Vol 16, No 7, pp.637-649, 2005.

상세보기
Kang-Won Lee, Bong-Jun Ko, Seraphin Calo, "Adapter Server Selection for Large Scale Interactive Online Games," Proc. of the 14th International Workshop on Network and Operating Systems Support for Digital Audio and Video, pp.152-157, 2004.
N. Ng, A. Si, R. Lau, and F. Li, "A Multi-server Architecture for Distributed Virtual Walkthrough," Proc. of ACM Symposium on Virtual Reality Software and Technology, pp.163-170, 2002.
Xiaobo Zhou, Cheng-Zhong Xu, "Optimal Video Replication and Placement on a Cluster of VOD Servers," Proc. of the International Conference on Parallel Processing, pp.547-555, 2002.
A. Dan and D. Sitaram. "On line video placement policy based on bandwidth to space ratio (BSR)," In Proc. of ACM International Conference on Management of Data, pp.376-385, 1995.
T. Ibarkai, N. Katoh, Resource allocation problem - Algorithm approaches, The MIT Press, 1988.
A. L. Chervenak, D. A. Patterson, and R. H. Katz, "Choosing the best storage system for video service," In Proc. of the Third ACM International Conference on Multimedia, pp.109-119, 1995.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증