다수 클라이언트(사용자)들이 동시에 진행하는 온라인 게임은 대부분 다중 서버 구조를 채택하고 있다. 그룹 플레이의 경우, 같은 그룹내 클라이언트들 사이에 사용자 반응시간에 큰 차이가 나면 게임의 공정성과 흥미를 떨어뜨리게 된다. 본 논문에서는 신규 클라이언트들을 대상으로, 이런 시간의 중요한 요소인 클라이언트-서버간 거리의 편차를 최소하도록 클라이언트를 서버에 배정하는 방법을 제안한다. 본 방법은 그룹 플레이를 위한 클라이언트 매칭과 서버 부하 균등도 함께 지원하고 있다. 우리는 클라이언트-서버 배정 문제를 IP(Integer Programming)으로 모델링라고 그 해를 구하는 GA(Genetic Algorithm) 기반의 알고리즘을 제안한다. 우리는 본 논문에서 재안한 방법을 다양한 조건하애서 실험했고 그 특성을 분석한다. 우리가 조사해 본바, 클라이언트 매칭과 서버 부하를 고려하면서, 클라이언트-서버 거리 편차를 최소화하는 클라이언트-서버 배정에 관한 기존 연구는 많지 않았다.
다수 클라이언트(사용자)들이 동시에 진행하는 온라인 게임은 대부분 다중 서버 구조를 채택하고 있다. 그룹 플레이의 경우, 같은 그룹내 클라이언트들 사이에 사용자 반응시간에 큰 차이가 나면 게임의 공정성과 흥미를 떨어뜨리게 된다. 본 논문에서는 신규 클라이언트들을 대상으로, 이런 시간의 중요한 요소인 클라이언트-서버간 거리의 편차를 최소하도록 클라이언트를 서버에 배정하는 방법을 제안한다. 본 방법은 그룹 플레이를 위한 클라이언트 매칭과 서버 부하 균등도 함께 지원하고 있다. 우리는 클라이언트-서버 배정 문제를 IP(Integer Programming)으로 모델링라고 그 해를 구하는 GA(Genetic Algorithm) 기반의 알고리즘을 제안한다. 우리는 본 논문에서 재안한 방법을 다양한 조건하애서 실험했고 그 특성을 분석한다. 우리가 조사해 본바, 클라이언트 매칭과 서버 부하를 고려하면서, 클라이언트-서버 거리 편차를 최소화하는 클라이언트-서버 배정에 관한 기존 연구는 많지 않았다.
Multi-client online games usually employ multi-serve architectures. For group play, if the user response time deviation between the clients in a group is large, the fairness and attractions of the game will be degraded. In this paper, given new clients, we propose a method for assigning the clients ...
Multi-client online games usually employ multi-serve architectures. For group play, if the user response time deviation between the clients in a group is large, the fairness and attractions of the game will be degraded. In this paper, given new clients, we propose a method for assigning the clients to servers to minimize the deviation of client-server distance which plays a major role in the user response time. This method also supports client matching for group play and server load balancing. We formulate the client-server assignment problem as an IP one, and present a GA(Genetic Algorithm)-based algorithm to solve it. We experimented our method under various settings and analyzed its features. To our survey, little research has been previously performed on client-server assignment under consideration of client matching, distance deviation minimization and server load balancing.
Multi-client online games usually employ multi-serve architectures. For group play, if the user response time deviation between the clients in a group is large, the fairness and attractions of the game will be degraded. In this paper, given new clients, we propose a method for assigning the clients to servers to minimize the deviation of client-server distance which plays a major role in the user response time. This method also supports client matching for group play and server load balancing. We formulate the client-server assignment problem as an IP one, and present a GA(Genetic Algorithm)-based algorithm to solve it. We experimented our method under various settings and analyzed its features. To our survey, little research has been previously performed on client-server assignment under consideration of client matching, distance deviation minimization and server load balancing.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서 DV는 같은 그룹에 속한 클라이언트들과 배정된 서버간의 평균 거리 편차를 나타낸다. 목적 함수는 DV를 최소화 하는 것이다.
본 논문에서는 클라이언트 매칭을 지원하면서 클라이언트-서버간의 거리 편차를 최소화하는 클라이언트-서버 배정 문제를 IP로 모델링하고, 그 해를 구하는 GA 기반의 방법을 제안했다. 우리의 IP 모델에는 서버 부하 균등에 관한 제약조건을 포함 함으로써, 클라이언트를 서버에 배정 시 서버 부하 균등도 함께 고려하였다.
가설 설정
단위 시간 동안의 신규 클라이언트 수는 푸아송 분포(Poisson distribution)를 따른다고 가정한다. 편의상 클라이언트와 서버간의 거리는 1 - 10 사이의 값을 갖고, 평균값이 5인 균일 분포(Uniform distribution)를 갖는 것으로 가정했다.
다중 서버 기반의 온라인 게임에서의 서버 클라이언트간의 실제 거리 분포 데이터를 획득할 수 없어 균일 분포를 사용했다. 서버들의 성능은 동일하고, 서버 성능은 최대 클라이언트 도착률을 처리할 정도로 충분히 크다고 가정한다. PlayAlloc 프로시저에서 LOOP_THR=50로 설정했다.
H의 증가로 제약조건 C1을 만족하는 서버들이 늘어나기 때문에, 그 만큼 서버 배정을 위한 선택의 폭이 커져 DV 값의 개선을 기대할수 있다. 실험에서는 서버들과 클라이언트들이 네트워크상에 고루 분산되어 있다고 가정한다. 따라서 부하 불균형을 심화시키면서 적용한 클라이언트-서버 배정에서도, 서버별로 클라이언트들간의 거리 편차는 현저히 개선되지 않는 것으로 보인다.
이것은 서버의 개수가 많아지면, 주어진 클라이언트 그룹에 대해 보다 거리 편차가 작은 서버를 찾을 있는 확률이 높아 지기 때문이다. 앞에서 언급한대로 서버들과 클라이언트들의 네트워크상에 고루 분산되었다고 가정하기에, 서버의 수가 늘어도 서버별 클라이언트들 간의 거리 편차는 큰 폭으로 개선되지 않는 것으로 판단된다.
이때 클라이언트-서버간의 거리 편차를 최소화하고, 서버 부하의 균등도 제약조건 형태로 함께 고려한다. 우리는 한 게임 그룹은 동일한 서버에 배정되는 경우를 가정한다. 따라서 서버들 간의 수반되는 통신 오버헤드는 크지 않기에 서버 간의 부하 차이는 서버에 접속된 클라이언트 수의 차이에 거의 좌우된다고 할 수 있다.
단위 시간 동안의 신규 클라이언트 수는 푸아송 분포(Poisson distribution)를 따른다고 가정한다. 편의상 클라이언트와 서버간의 거리는 1 - 10 사이의 값을 갖고, 평균값이 5인 균일 분포(Uniform distribution)를 갖는 것으로 가정했다. 우리의 방법은 특정 네트워크 토폴로지에 국한되지 않는다.
제안 방법
우리의 방법은 특정 네트워크 토폴로지에 국한되지 않는다. 다중 서버 기반의 온라인 게임에서의 서버 클라이언트간의 실제 거리 분포 데이터를 획득할 수 없어 균일 분포를 사용했다. 서버들의 성능은 동일하고, 서버 성능은 최대 클라이언트 도착률을 처리할 정도로 충분히 크다고 가정한다.
본 논문에서 우리는 로비 서버에 새로이 도착한 클라이언트들을 대상으로, 이들을 정해진 그룹 크기만큼 무작위로 묶은 후 서버에 배정하는 방식을 제안한다. 이때 클라이언트-서버간의 거리 편차를 최소화하고, 서버 부하의 균등도 제약조건 형태로 함께 고려한다.
우리는 [Fig. 2]에 기술된 클라이언트-서버 배정 방법의 특성과 유용성을 실험을 통해 분석했다. 실험에 사용한 파라미터는 게임 플레이를 원하는 신규 사용자 도착률(user arrival rate) λ, 서버 개수 M, 해 집단의 크기 PS, 교차 연산 수와 변이 연산 수의 비 CMR, 클라이언트 그룹의 크기 U, 서버 부하 불균형 허용치인 H이다.
우리는 클라이언트-서버 배정 문제를 IP(Integer Programming)으로 모델링하고, 그 해를 구하는 유전자 알고리즘 (GA: Generic Algorithm)[4] 기반의 휴리스틱 알고리즘을 제시한다. 우리의 클라이언트-서버 배정 문제는 특수한 형태의 bin-packing 문제인데, 이것은 NP-complete 문제이다.
본 논문에서는 클라이언트 매칭을 지원하면서 클라이언트-서버간의 거리 편차를 최소화하는 클라이언트-서버 배정 문제를 IP로 모델링하고, 그 해를 구하는 GA 기반의 방법을 제안했다. 우리의 IP 모델에는 서버 부하 균등에 관한 제약조건을 포함 함으로써, 클라이언트를 서버에 배정 시 서버 부하 균등도 함께 고려하였다.
사용자 도착률은 단위 시간 동안 발생하는 게임 플레이를 원하는 클라이언트들의 평균 명수를 나타낸다. 이들 파라미터에 다양한 값을 설정한 후, 평균 거리 편차인 DV를 비교해 보았다.
따라서 우리의 방법에서는 교차 연산과 변이 연산이 해의 적합도 향상에 미치는 효과는 거의 동일하다고 볼 수 있다. 자연계에서는 교차가 변이보다는 많이 일어나므로, 본 장에서의 실험에서는 그런 값 중 하나인 2를 CMR로 설정 했다.
다중 게임 서버 환경에 관한 주요 연구 이슈 중 하나가 클라이언트들을 서버에 배정하는 것이고[1], 이를 클라이언트-서버 배정 (Client-Server Assignment)이라 부른다. 클라이언트-서버 배정에서는 여러 가지 목표 지표들을 최적화하고자 하는데, 본 논문에서는 클라이언트와 서버간의 거리 편차, 서버 부하 균등및 클라이언트 매칭(client matching)에 초점을 둔다.
Step 2: Step 1에서 파악한 각 서버에 대해, 아직 서버 배정이 되지 않은 클라이언트들만으로 구성되면서 평균 거리 편차가 가장 작은 그룹을 다음같이 찾는다. 클라이언트들을 해당 서버와의 거리 순으로 정렬한 후, 연이은 U명의 클라이언트들을 한 그룹으로 차례로 묶고 그들 간의 거리 편차를 서로 비교해 본다.
대상 데이터
5]는 다양한 λ에 따라 구한 클라이언트- 서버간의 거리 편차 및 기타 특성이다. 실험 파라미터는 M=10, PS=20, U=4, CMR=2, H=1로 설정 했다. [Fig.
실험 파라미터는 앞선 실험에서 같이 PS=20, U=2, CMR=2, H=1, λ=40로 설정했다.
실험에 사용한 파라미터는 게임 플레이를 원하는 신규 사용자 도착률(user arrival rate) λ, 서버 개수 M, 해 집단의 크기 PS, 교차 연산 수와 변이 연산 수의 비 CMR, 클라이언트 그룹의 크기 U, 서버 부하 불균형 허용치인 H이다.
이론/모형
Step 1에서는 PS개의 유전체로 초기화 되는데, 초기 염색체들은 뒤에서 설명할 FinishAlloc 함수를 이용해서 생성된다. 이 함수는 거리 편차가 가장 작은 클라이언트 그룹과 해당 서버를 차례로 구해가는 휴리스틱 방법을 사용한다.
성능/효과
클라이언트 도착률이 높은 경우에도 수십 ms 안에 해를 구할 수 있기에, 실시간 응용에서 사용하기에 지장이 없음을 알 수있었다. 또한, 해 집단의 크기, 서버의 개수, 허용 가능한 부하 불균형 지수가 커지면, 클라이언트-서버간의 거리 편치는 줄어드는 경향을 보인다. 반면에 클라이언트 그룹의 크기가 커지면, 거리 편차는 늘어나는 경향을 보였다.
우리의 방법을 다양한 파라미터 세팅하에서 실험한 결과, FIFO나 탐욕(greed)의 기반의 방법보다는 좋은 성능을 보였다. 클라이언트 도착률이 높은 경우에도 수십 ms 안에 해를 구할 수 있기에, 실시간 응용에서 사용하기에 지장이 없음을 알 수있었다.
우리의 방법을 다양한 파라미터 세팅하에서 실험한 결과, FIFO나 탐욕(greed)의 기반의 방법보다는 좋은 성능을 보였다. 클라이언트 도착률이 높은 경우에도 수십 ms 안에 해를 구할 수 있기에, 실시간 응용에서 사용하기에 지장이 없음을 알 수있었다. 또한, 해 집단의 크기, 서버의 개수, 허용 가능한 부하 불균형 지수가 커지면, 클라이언트-서버간의 거리 편치는 줄어드는 경향을 보인다.
후속연구
우리가 조사해 본 바, 클라이언트 매칭과 클라이언트-서버간 거리 편차를 부하 균등과 함께 고려한 서버 배정에 관한 기존 연구는 거의 없었다. 거리 편차 최소화로 통해 얻는 게임 플레이의 성능 개선에 대한 분석은 추후 연구에서 다룬다.
앞선 기존 연구의 결과와 본 논문에서 고려중인 무작위 매칭은 같이 사용할 수 있다. 즉, 신규 클라이언트의 수가 많은 게임의 경우, 먼저 클라이언트들을 특성에 따라서 여러 카테고리들로 분류한 후, 각 카테고리별로 본 논문에서 제안한 방법을 적용하면 될 것이다.
질의응답
핵심어
질문
논문에서 추출한 답변
클라이언트 매칭이란?
클라이언트 매칭은 그룹 플레이를 위해 클라이언트들을 그룹으로 묶는 것을 말한다. 클라이언트 그룹의 크기는 게임의 성격에 따라 달라지는데, 예를 들어 바둑은 2명, 마작은 4명이다.
클라이언트-서버 배정은 무엇인가?
동시에 접속하는 클라이언트(또는 사용자)가 많은 온라인 게임의 경우에는 원활한 게임 진행을 위해 여러 서버들을 운영하게 된다. 다중 게임 서버 환경에 관한 주요 연구 이슈 중 하나가 클라이언트들을 서버에 배정하는 것이고[1], 이를 클라이언트-서버 배정 (Client-Server Assignment)이라 부른다. 클라이언트-서버 배정에서는 여러 가지 목표 지표들을 최적화하고자 하는데, 본 논문에서는 클라이언트와 서버간의 거리 편차, 서버 부하 균등및 클라이언트 매칭(client matching)에 초점을 둔다.
실시간 게임에서 큰 사용자 반응 시간의 편차가 어떤 영향을 미치는가?
이와 같은 그룹 플레이에서는 사용자 반응 시간의 편차를 줄이는 것이 중요하다. 특히 실시간 게임에서는 이런 편차가 크면 게임 플레이의 공정성과 정확성을 해치게 되어, 결국 사용자들의 게임에 대한 흥미를 떨어드리게 된다. 사용자 반응시간은 크게 클라이언트 서버간의 지연시간과 서버의 부하 처리 시간에 영향을 받는다.
참고문헌 (18)
S. Farlow, J. L. Trahan, "Client-Server Assignment in Massively Multiplayer Online Games", Proc. of CGAMES, 2014, pp.1-8.
C. Eduardo B. Bezerra, et. al, "Adaptive Load-balancing for MMOG Servers Using KD-trees", ACM Computers in Entertainment, Vol. 10, No. 3, Article 5, 2012, pp. 1-16.
R. W.H. Lau, "Hybrid Load Balancing for Online Games", Proc. of ACM International Conference on Multimedia, 2010, pp.1231-1234.
G. Armitage. "Optimising Online FPS Game Server Discovery through Clustering Servers by Origin Autonomous System." Proceedings of the International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV), 2008, pp. 3-8.
S. Gargolinski, C. St. Pierre, M. Claypool. "Game Server Selection for Multiple Players." Proc. of 4th ACM SIGCOMM Workshop on Network and System Support for Games, 2005, pp. 1-6.
Y. Chen, S. Radhakrishnan, S. Dhall, S. Karabuk. "Server Selection with Delay Constraints for Online Games." Proceedings of GLOBECOM Workshops, 2010, pp. 882-887.
M. Kohana, et. al, "Dynamic ReAssignment Rules on Multi-Server Web-based MORPG System", International Journal of Grid and Utility Computing, vol. 3, no. 2/3, pp. 136-144, 2012
L. Zhang, X. Tang, "The Client Assignment Problem for Continuous Distributed Interactive Applications: Analysis, Algorithms, and Evaluation," IEEE Trans. Par. Distrib. Sys., vol. 25, no. 3, 2014, pp.785-795.
D. T. Ahmed "A microcell oriented load balancing model for collaborative virtual environments", Proc. of VECIMS. 208, pp.86-91.
B. De Vleeschauwer, et. al, "Dynamic Microcell Assignment for Massively Multiplayer Online Gaming", Proc. of NetGames, 2005, pp. 1-7.
B. Ng, A. Si, R. Lau, F. Li, "A Multi-Server Architecture for Distributed Virtual Walkthrough", Proc. of the ACM Symposium on Virtual Reality Software and Technology, 2002, pp.11-13
D. Lee, M. Lim, S. Han, K. Lee, "ATLAS: A Scalable Network Framework for Distributed Virtual Environments", Presence: 16(2), 2007, pp.125-156
S.-Y. Yun, A Proutiere, "Distributed Proportional Fair Load Balancing in Heterogenous Systems", Proc. of SIGMETRICS, 2015, pp.17-30.
Y Francillette, "A Players Clustering Method to Enhance the Players' Experience in Multi-player Games", Proc. of CGAMES, 2013, pp.229-234.
C. Schlup. "Automatic Game Matching", http://dcg.ethz.ch/theses/ws0203/OnlineMatching_abstract.pdf.
R. S. Anders Drachen, "Guns, Swords and Data: Clustering of Player Behavior in Computer Games in the Wild," Proc. of IEEE Conference on Computational Intelligence and Games (CIG), 2012, pp. 163-170.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.