제목 : A load balancing scheme for massively multiplayer online games
Abstract :
분산 MMOG 서버구조에 대한 내용.
이 구조에서의 서버노드는 플레이어 상태 업데이트로 인한 Overload의 가능성이 존재함.
여기에서의 load는 각 서버 노드에 접속한 플레이어의 숫자에 비례한다.
단, 이 논문에서는 동종의 동일스펙 서버노드로 한정하고 진행한다.
두가지 주 목표를 가지고 load balancing 구조를 제안함.
1. 각 서버 노드의 load에 비례하여 load를 할당하고 서버간 통신 overhead를 줄이는것.
2. load를 각 서버 노드의 점유 대역폭으로 간주하는것.
여기에서 4가지 구조의 알고리즘을 제안.
ProGReGA가 Overhead 감소에 제일 적합.
ProGReGA-KF가 서버간 플레이어 이주에 제일 적합.
Intro :
MMOG의 특징은 수십~수십만이 동시 접속함.
이용자간의 상호작용으로 네트워크 트래픽이 2차적으로 증가할수 있다.
C/S 구조를 사용하면 서버가 이 상호작용을 제어해야함.
이때 서버에는 큰 load가 작용해서, 많은 리소스가 필요함. -> MMOG에서의 병목현상.
분산서버에서는 이 load를 각 서버 노드에 비례하게 분산해야함.
초기 분산서버구조에서는 단순히 플레이어 수를 나눔.
문제는 플레이어에 의한 load는 상호작용 방법에 따라 다름.
경우에 따라서 load가 플레이어수의 제곱이 될수도, 선형적으로 증가할수도 있다.
한 플레이어 그룹에서 각 플레이어에게 전송되는 패킷은 그룹원에 비례함.
배포에 대한 overhead문제가 존재.
서버간 통신이 필요해서 트래픽을 최소화하는 방법을 통해 서버의 자원낭비를 줄이는 방법이 필요.
Hot spot은 MMOG에서 캐릭터틀이 자유롭게 움직이다가 일정 구역으로 몰리는 현상을 일컬음.
플레이어를 서버 자원에 비례하게 나누기 위한 조건을 정함.
1. 플레이어가 선형적으로 증가할때 서버의 대역폭 사용량은 플레이어 수에 제곱으로 증가한다. 플레이어는 어떤 그룹에 포함되어있는데 그룹사이의 각 플레이어로의 패킷 전송률은 그룹 구성원 수에 비례한다.
2. overhead의 분산. 서버는 다른 서버와 통신이 필요할때, 서버 시스템의 리소스를 낭비하지 않기 위해 트래픽을 최소화할 필요가 있다.
MMOG를 위한 Load balancing 구조는 Hot spot이 발생해 허용가능 한도를 초과해서 게임 품질 저하요인이 되는것을 막아야하는것.
이 논문에서는 Balancing 구조를 제안할때 Load 분산할 기준으로 upload 대역폭을 고려하였다. 또한 서버간 통신 overhead를 줄이기 위해 Greedy Graph Partition Growing 알고리즘을 사용했다.
결론 :
제안한 알고리즘으로 가상환경에서 몇몇 아바타로 시뮬레이션 한결롸를 나타냄.
가상환경은 2차원 환경이고, 225셀로 나뉘어 15*15 행렬로 구성하였고 750명의 아바타를 사용하였다.
각 서버의 용량은 다르게 설정하였고 i * 20000의 비율이었다.
서버는 총 8개 각각의 서버에 Region 하나씩을 담당시켰고, 각각의 셀은 각자 다른 Region에 포함된다.
테스트 세션은 각 알고리즘당 20분동안 실행했다.
처은 제안한 알고리즘에서부터 나중에 제안한 알고리즘의 순서대로 비례하게 성능이 증가했다.
가끔 overhead가 더 늘어나는 경우가 있는데 Region단편화 문제 때문이다.
제안한 알고리즘
ProGReGA,
ProGReGA-KF
BFBCT
Ahmed
전체적인 성능 : 순서대로 비례
Overhead 성능 : 거의 역순. (표준을 고려하지 않음.)
2가지의 이주에 대한 성능 : walking migration : 새로운 서버로 이주.(Region 사이의 이주.), still migration : 이동없이 서버 교체할때 이주. 역시나 순서대로 비례.
상황에 맞는 알고리즘을 사용하면 될것이다.라는게 결론.
1. 논문의 카테고리 : 분산서버, load balancing
2. 문맥 : 그래프 분할 이론을 통해 서버의 load 를 효과적으로 분산하기 위함.
3. 가정 : 동종의 동일 스펙의 서버노드와 업로드 대역폭으로만 가정.
4. 주제 : MMOG의 load를 정의하고 효과적으로 분산하기 위한 논문.
5. 명료도 : 주제에 대해서 여러가지 알고리즘을 제안하며 그에 대한 평가도 적절.
이어서 볼 논문 :
Game traffic analysis : an MMORPG perspective
An efficient heuristic procedure for partitioning graphs.
댓글