[논문]게임 스트리밍 환경에서 최대 부하 균등 및 자동 프레임 레이트 조절을 위한 클라이언트-서버 배정 방법

김상철

doi:10.7583/jkgs.2020.20.4.77

게임 스트리밍 환경에서 최대 부하 균등 및 자동 프레임 레이트 조절을 위한 클라이언트-서버 배정 방법
A Method for Client-Server Allocation for Maximum Load Balancing and Automatic Frame Rate Adjustment in a Game Streaming Environment 원문보기

한국게임학회 논문지 = Journal of Korea Game Society, v.20 no.4, 2020년, pp.77 - 88

초록
AI-Helper

최근 클라우드 기반 게이밍에서 게임 스트리밍에 대한 관심이 높다. 게임 스트리밍에서는 원격지의 게임 서버가 그래픽 렌더링 작업을 수행하고 렌더링 결과물인 씬 이미지들을 플레이어 장치에 인터넷을 통해 스트리밍하게 된다. 우리는 다중 게임 서버 기반의 게임 스트리밍 환경에서, 서버간의 GPU 부하 균등을 위한 CSA (Client-Server Allocation) 문제를 최적화 문제로 모델링하고, 그 해를 구하는 시뮬레이티드 어닐링 기반 방법을 제안한다. 우리 방법의 특징은, 네트워크 지연에 대한 제약을 고려한 것과, 필요시 신규 게임 세션의 프레임 레이트를 자동으로 하향 조절하는 기능을 지원하는 것이다.

Abstract ▼ AI-Helper

Recently, interest in game streaming is high in cloud-based gaming. In game streaming, remote game servers perform graphics rendering and stream the resulting scene images to clients' device on the Internet. We model the client-server allocation (CSA) problem for balancing the GPU load between servers in a game streaming environment as an optimization problem, and propose a simulated annealing-based method. The features of our method are that the method takes into account the constraints on network delay and has the ability to automatically adjust the frame rate of game sessions if necessary.

주제어

표/그림 (12)

그림 [Fig. 1] Definition of Client-Server Assignment For Load Balance
그림 [Fig. 2] Definition of Client-Server Assignment for Frame Rate Maximization
그림 [Fig. 3] Client_Server_Alloc Procedure
그림 [Fig. 4] Procedure Greedy_Alloc
그림 [Fig. 5] Procedure Lower_Frame_Rate
그림 [Fig. 6] Comparison of Load Balance w.r.t. Methods
그림 [Fig. 7] Comparison of Load Balance w.r.t. Client-Server Network Delay Constraints
그림 [Fig. 8] Comparison of Load Balance w.r.t. Number of Games
그림 [Fig. 9] Comparison of Load Balance w.r.t. No of Clients
그림 [Fig. 10] Comparison of Load Balance w.r.t. Frame Rates of Games
그림 [Fig. 11] Comparison of Frame Rate Adjustments Results w.r.t. Number of Clients
그림 [Fig. 12] Comparison of Frame Rate Adjustment Results w.r.t. Frame Rates of Games

AI 본문요약
AI-Helper

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

문제 정의

또한, 클라이언트들의 수가 증가함 따라 클라이언트-서버 배정 결과의 차이를 알아보고자 실험을 실시했다. 이 실험도 클라이언트 수의 변화를 주는 것 외에는 기본 실험과 동일한 조건하에서 수행했다.
본 논문에서 우리는 다중 서버를 가진 게임 스트리밍 환경에서 신규 클라이언트들을 서버들 간의 GPU 부하 균등과 필요시 프레임 레이트의 자동조절을 지원하면서 서버에 배정하는 문제를 최적화 문제로 모델링했고, 그 해를 구하는 알고리즘을 제안했다. 참고로 GPU는 게임 스트리밍을 위한 서버 구조에서 가장 비싼 자원이며 렌더링 타임에큰 영향을 미친다.
본 논문에서는 게임 스트리밍 환경에서 서버들 간의 GPU 부하 균등과 게임 세션의 프레임 레이트(frame rate)의 자동 조절을 지원하는 CSA 문제를 최적화 문제로 모델링하고, 그 해를 구하는 SA(Simulated Annealing) 기반의 해법을 제안한다. 시뮬레이티드 어닐링[3]는 폴리노미알 타임 복잡도의 해가 존재하지 않는 최적화 문제의 해를 구하는 대표적인 방법 중 하나이다.
온라인 게임에서는 특히 서버간의 부하 균등에 관한 연구가 많이 발표되었다. 부하 균등을 통해 일부 서버들의 과부하와 함께 이런 서버 주변 네트워크에 트래픽이 늘어 네트워크 지연이 발생하는 것을 예방하고자 함이다.
접속자 수가 많이 몰리는 시간대에는, 렌더링 서버의 과부하로 인해 신규 클라이언트들이 요구하는 프레임 레이트로 렌더링 작업을 수행할 없는 상황이 발생할 수 있다. 우리는 이런 상황에서, 신규 게임 세션들의 프레임 레이트를 자동으로 줄여 모든 게임 세션들이 시작될 수 있는 방법을 제안한다. 이때 자동으로 조절되는 프레임 레이트는 클라이언트의 초기 요구에 최대한 근접하도록 하는 것을 목표로 한다.
우리는 제안된 클라이언트-서버 배정 방법을 MS Visual Studio 2019를 이용해 C++ 코드로 작성했다. 우리의 CSA 방법의 특성과 성능을 분석하고자 여러 실험을 실시했다. 이들에 적용한 기본적인 실험 조건은 다음과 같다.
우리는 이런 상황에서, 신규 게임 세션들의 프레임 레이트를 자동으로 줄여 모든 게임 세션들이 시작될 수 있는 방법을 제안한다. 이때 자동으로 조절되는 프레임 레이트는 클라이언트의 초기 요구에 최대한 근접하도록 하는 것을 목표로 한다.

가설 설정

각 클라이언트와 서버간의 지연은 50^~150(ms) 사이의 값을 가진다. DVMAX=100, DMAX는 편의상 충분히 큰 값으로 가정한다.
, g_K] 이고, 이들 게임은 모든 서버에서 서비스 가능하다고 가정한다. 각 서버는 같은 GPU 성능을 가지고 있다고 가정하고, 각 서버가 처리할 수 있는 최대 부하를 FMAX로 표현한다.
, gs_N]로 정의한다. 게임 서버의 리스트는 SS = [s₁, s₂, ..., s_M], 게임 응용의 리스트는 GS=[g₁, g₂, ..., g_K] 이고, 이들 게임은 모든 서버에서 서비스 가능하다고 가정한다. 각 서버는 같은 GPU 성능을 가지고 있다고 가정하고, 각 서버가 처리할 수 있는 최대 부하를 FMAX로 표현한다.
게임들 중 반은 전자를, 나머지 반은 후자로 사용한다. 게임 세션들은 K개 게임 중 한 게임을 플레이한다고 가정한다. 각 게임 세션에 대해 해당 클라이언트 그룹은 선택 가능한 프레임 레이트들 중 가장 높은 것을 요구한다.
서버의 GPU 성능은 동일하다고 가정하고, FMAX=40000으로 정했다. 각 게임 세션의 프레임당 처리 부하는 15^~60 사이의 값을 가진다.

제안 방법

클라이언트들의 게임 시작 전의 대기 시간을 고려하면서 서버 프로비저닝 비용을 감소시키는 클라이언트 배정 방법도 발표되었다[17,18]. 또한 앞에서 언급한 것 같이 GPU가 비싼 자원임을 감안해, Dinaki와 Shirmohammadi는 GPU 사용도(utilization factor)과 사용자가 느끼는 플레이의 품질을 최대화하는 서버 배정 문제를 모델링하고, 유전자 알고리즘 방식의 해를 구했다[2].
또한, 신규 클라이언트들이 시작하는 게임 세션들의 프레임 레이트를 하향 조절하되 최대한 원래 요구에 맞추는 알고리즘을 제안했고, 그 특성을 분석했다. 이 알고리즘은 게임 세션들이 요구하는 GPU 서버 부하들이 서버들의 남은 용량을 넘게 되면, 이들 게임 세션을 모두 시작할 수 없는 상황에 적절히 사용될 것이다.
7]에 나타난다. 앞에서 언급한 기본 실험 조건하에서 실시했고, 단지 클라이언트-서버간의 지연 편차의 허용치인 DVMAX 값을 다양하게 설정했다.
우리는 여러 실험을 통해, 제안된 클라이언트서버 배정 방법의 특성을 분석했다. 분석 결과, 지연에 대한 제약조건이 강해질수록 GPU 부하 균등지수가 낮아진다.
우리는 전체 서버의 GPU 처리 능력에 비해 신규 클라이언트들의 게임 세션들이 더 높은 GPU 부하를 요구할 때의 서버 배정 경우를 실험했다. [Fig.

이론/모형

우리는 제안된 클라이언트-서버 배정 방법을 MS Visual Studio 2019를 이용해 C++ 코드로 작성했다. 우리의 CSA 방법의 특성과 성능을 분석하고자 여러 실험을 실시했다.

성능/효과

우리는 여러 실험을 통해, 제안된 클라이언트서버 배정 방법의 특성을 분석했다. 분석 결과, 지연에 대한 제약조건이 강해질수록 GPU 부하 균등지수가 낮아진다. 반면에 서비스되는 게임의 수가 증가할수록, 낮은 게임 레이트를 요구하는 게임의 비율이 높아질수록, 부하 균등 지수가 높아지는 경향이 있다.
따라서 서버 배정에 필요한 총 GPU 부하가 줄어들게 된다. 우리는 이런 경우에 L이 증가하면 Unalloc Clients는 줄고 FU는 증가하는 경향을 실험을 통해 확인할 수 있었다.
대략 100을 넘는 구간에서는 DVMAX 값이 증가해도 LBF 값의 차이가 크지 않는다. 확인 결과, 이 구간에서는 클라이언트 팀별 선택 가능한 서버의 수는 전체 서버의 절반을 넘었다. 이 정도의 후보 서버들이 클라이언트 팀별로 존재한다면, 클라이언트 팀들이 차례로 이런저런 서버에 배정되면서 궁극적으로 전체 서버에 골고루 배정되는 효과가 나타나는 것으로 보인다.

후속연구

우리의 조사에 따르면, 게임 스트리밍 환경에서 네트워크 지연 제약 조건하에서 서버간의 GPU 부하 균등과 프레임 레이트의 자동 조절을 고려하는 서버 배정에 관한 연구 사례가 드물었다. 본 연구의 결과는 게임 스트리밍 서비스의 품질 향상에 기여할 것이다.
이것은 클라이언트와 서버간의 물리적 거리와 네트워크 상태에 영향을 받는다. 사용자 장치와 서버간의 메시지 전달의 지연을 모니터링해서 통계적으로 파악할 수 있을 것이다. C3은 각 클라이언트는 너무 긴 지연이 걸리는 서버에는 배정하지 말라는 제약 조건을 나타낸다.
또한, 신규 클라이언트들이 시작하는 게임 세션들의 프레임 레이트를 하향 조절하되 최대한 원래 요구에 맞추는 알고리즘을 제안했고, 그 특성을 분석했다. 이 알고리즘은 게임 세션들이 요구하는 GPU 서버 부하들이 서버들의 남은 용량을 넘게 되면, 이들 게임 세션을 모두 시작할 수 없는 상황에 적절히 사용될 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	렌더링 서버는 무엇을 합쳐 부르는 말인가?	게임 스트리밍 환경에서의 게임 서버는 크게 게임 세션 및 게임 상태를 관리하는 시스템, GPU(Graphic Processing Unit)를 구비해 프레임 렌더링하는 시스템, 렌더링된 이미지들을 인코딩 후 비디오 스트리밍하는 시스템으로 구성된다. 렌더링, 인코딩 및 비디오 스트리밍 시스템을 합쳐서 렌더링 서버라고 별도로 부른다. 일반적으로 많은 접속자를 지원하기 위해 다중 게임 서버 구조를 가지게 된다.
	다중 게임 서버 구조는 일반적으로 어디에 위치하는가?	일반적으로 많은 접속자를 지원하기 위해 다중 게임 서버 구조를 가지게 된다. 이들 서버들은 일반적으로 여러 지역에 흩어진 데이터 센터에 위치하고, 각 렌더링 서버는 여러 GPU들을 구비하고 있다. 서버에는 여러 게임 응용들이 미리 설치되어, 신규 플레이어의 요구에 따라 해당 게임의 게임 세션(game session)을 시작하게 된다.
	게임 스트리밍 환경에서의 게임 서버은 어떻게 구성되는가?	게임 스트리밍 환경에서의 게임 서버는 크게 게임 세션 및 게임 상태를 관리하는 시스템, GPU(Graphic Processing Unit)를 구비해 프레임 렌더링하는 시스템, 렌더링된 이미지들을 인코딩 후 비디오 스트리밍하는 시스템으로 구성된다. 렌더링, 인코딩 및 비디오 스트리밍 시스템을 합쳐서 렌더링 서버라고 별도로 부른다.

참고문헌 (22)

Ryan Shea, et al., Cloud Gaming: Architecture and Performance", IEEE Network, 2013, pp. 16-21.
H. E. Dinaki, S. Shirmohammadi, "GPU/QoE-Aware server selection using metaheuristic algorithms in multiplayer cloud gaming", NetGames'18, Article No.4, 2018, pp. 1-6.
en.wikipedia.org/wiki/Simulated_annealing
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.
Y. Chen, et al, "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, 2012, pp. 136-144.
Y Deng, et al., "The Server Allocation Problem for Session-Based Multiplayer Cloud Gaming", IEEE Trans. on Multimedia, Vol. 20, Issue 5, May 2018, pp 1233-1245.

상세보기
K Chanthaphram, et al., "Building a cloud-based MOG game server", 10th Int'l Joint Conf. on Computer Science and Software Eng., 2013, pp 143-148.
K.-T. Chen, et al., "Measuring the latency of cloud gaming systems", 19th Int'l Conf. on Multimedea, 2011, pp. 1-5.
M. Claypool and D. Finkel, ''The effects of latency on player performance in cloud-based games,'' 13th NetGames, 2014, pp. 1-6.
L. Pantel, L. C. Wolf, "On the Impact of Delay on Real-Time Multiplayer Games," ACM NOSSDAV, 2002. pp. 23-29.
T. Fritsch, H. Ritter, J. H. Schiller, "The Effect of Latency and Network Limitations on MMORPGs: a Field Study of Everquest 2," ACM NetGames, 2005.
G. Armitage, "An experimental estimation of latency sensitivity in multiplayer Quake 3," 11th IEEE Int'l Conf. on Networks, ICON, 2003, pp. 137-141,
H. Wang, et al., "On design and performance of cloud-based distributed interactive applications," IEEE ICNP, 2014, pp. 37-46.
M. Marzolla, S. Ferretti, G. D'Angelo, "Dynamic resource provisioning for cloud-based gaming infrastructures", ACM Comp. in Entertainment, Vol.10, No.3, Article No.: 4, 2012, 4:1-4:20.
D. Wu, Z. Xue, J. He, "iCloudaccess: Cost-effective streaming of video games from the cloud with low latency," IEEE Trans. on Circuits and Systems for Video Technology, vol.24, no.8, 2014. pp. 1405-1416,

상세보기
M. Basiri, A. Rasoolzadegan, "Delay-aware resource provisioning for cost-efficient cloud gaming," IEEE Trans on Circuits and Systems for Video Technology, 2016.
K.-T. Chen, et al., "On the Quality of Service of Cloud Gaming Systems," IEEE Trans. Multimed., vol.16, no.2, 2014. pp. 480-495.

상세보기
K. Claypool, M. Claypool, "On Frame Rate and Player Performance in First Person Shooter Games", Springer Multimedia Systems Journal, Vol.13, No.1, 2007, pp. 3-17

상세보기
T. Zinner, et al., "Impact of frame rate and resolution on objective QoE metrics," 2nd Int'l Workshop on Quality of Multimedia Experience, 2010, pp. 29-34.
M. Wimmer, P. Wonka, "Rendering Time Estimation for Real-Time Rendering", 14th Eurographics Workshop on Rendering Techniques, 2003. pp. 118-129.

저자의 다른 논문 :

표제어: 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

연합인증