1회차 : A Scalable Dynamic Load Distribution Scheme for Multi-Server Distributed Virtual Environment Systems With Highly-Skewed User Distribution

제목 : A Scalable Dynamic Load Distribution Scheme for Multi-Server Distributed Virtual Environment Systems With Highly-Skewed User Distribution

심하게 불균형한 사용자 분포를 가지는 다중 서버 분산 가상 환경 시스템을 위한 확장 가능한 동적 부하분산 기법.

Abstract : 심하게 불균형한 사용자 분포도를 가지는 다중 서버 분산 가상환경 시스템을 위한 동적 부하 분산 기법을 제안함.

기존의 접근방식과 달리 다른 서버의 작업 부하에 대해 부하분산을 시작한 서버가 동적으로 대응해 부하분산할 서버 집합을 선택함.

서버 선택이 완료되면 참여한 서버는 그래프 분할 알고리즘을 사용하여 관련 서버 전용 영역을 다시 분할하여 관련된 모든 서버가 비슷한 작업 부하를 가지도록 한다. 

그후 관련된 서버는 다시 분할한 결과에 따라 서로의 작업부하를 P2P방식으로 이주한다.

 

Intro : 분산형 가상환경(DVE) 시스템은 지리적으로 분산된 사용자가 인터넷같은 네트워크를 통해 정보를 교환해 서로 상호작용하고 가상환경(VE)의 일관된 뷰를 공유하게 함.

DVE시스템의 확장성을 위한 접근법중 하나는 연계논문에 소개된 다중 서버 아키텍쳐이다.

VE를 여러 영역으로 분할하고 여러 서버에 영역관리 책임을 분삲면 개별 서버의 부하를 크게 줄일수 있다. 

결과적으로 DVE시스템은 더 많은 동접자와 더 큰 VE를 지원할수 있다.

그러나 VE를 통한 사용자 분포가 균일하지 않으면 서버간의 작업부하 불균형이 발생한다. 일부 서버는 작업부하가 많은 혼잡지역을 처리하게 된다.

그 결과로 작업부하가 많은 서버에서 서비스 받는 사용자는 대화형 성능이 저하되는 문제가 발생한다.

이 문제를 해결하기 위해 동적 부하분산 기법들이 제안되었다. 과부하된 서버는 부하가 적은 서버로 넘치는 부하를 전송하여 해결한다.

이미 존재하는 다중 서버 DVE 시스템에 대한 동적 부하분산 기법은 2가지 접근이 있었다.

지역 접근법은 과부하된 서버는 근처에 인접한 서버만 사용하여 지역적으로 부하 분산한다. 인접한 서버끼리만 부하분산하니 소량의 사용자 이주가 발생하여 글로벌 방식보다 적은 오버헤드를 가진다.

하지만 심하게 불균형한 작업 부하상황, 즉 과부하된 서버가 인접한 경우에는 부하를 분산할수가 없어진다.

반면에 전역 접근법은 모든 서버가 전역 정보와 함께 부하분산을 수행하기때문에 작업부하 불균형이 심할때에도 작업 부하 분산을 고르게 할수 있다.

그러나 VE의 크기와 시스템의 서버 수만큼 재분할의 오버헤드와 사용자 이주가 급격하게 증가한다.

이 논문에서는 VE를 통해 사용자가 심하게 불균형하게 분배되어있는 상황에서 동적 부하분산 기법을 제안함.

기존의 지역 접근 방식과 달리 제안하는 구성표의 과부하된 서버는 인접서버 이외의 서버집합과 서버의 작업 부하 상태에 맞게 동적으로 선택되는 부하 분산을 수행한다.

과부하된 서버의 작업부하를 해결할 수 있는 서버의 부분 집합만 선택한다는 점에서 전역 접근법과 다르다.

1. 부하분산을 시작하는 서버는 부하분산과 관련된 서버집합을 선택한다. 

1.1이웃 서버중에 가장 부하가 적은 서버를 선택하고 부하분산에 참여하도록 요청. 

1.2 이미 부하분산에 참여했거나 하는 중이면 거부. 아니면 해당 서버의 작업부하 정보를 시작한 서버로 전송해 참여한다.

2. 참여한 이웃 서버가 작업 부하를 처리 할수 없는경우 이웃서버의 이웃서버에 대해 다시 선택한다.

2.1 작업부하를 처리 할수 있을 때까지 선택을 반복.

3. 서버에 지정된 영역을 그래프 분할 알고리즘을 사용해 다시 분할해 부하분산과 관련된 모든 서버가 동일한 수의 사용자를 가지게 한다. 

4. 관련된 서버는 재분할한 결과에 따라 P2P 방식으로 서로 사용자를 이주한다.

자체적으로 평가한 결과는 이러하다.

제안 된 동적 부하 분산 기법과 기존의 로컬 및 글로벌 기법의 성능을 시뮬레이션을 통해 평가하고 비교한다. 시뮬레이션에서 사용자는 랜덤 웨이 포인트 모빌리티 모델 [7]을 따라 위치를 이동하고 업데이트합니다. 그런 다음 서버는 동적로드 분산을 동시에 수행합니다. 랜덤 웨이 포인트 모빌리티 모델은 고도로 왜곡 된 사용자 분포를 생성합니다 [16]. 사용자는 VE의 경계 영역이 아닌 중앙 영역 주위로 몰려들 것입니다. 시뮬레이션 결과는 사용자 및 서버 수가 각각 22,500 및 100 일 때 기존의 로컬 및 글로벌 방식보다 성능이 우수함을 보여줍니다. 효율성 측면에서 동적 부하 분산 방식으로 인해 과부하 된 서버로 인한 사용자 비율이 감소하는 경우 제안 된 구성표는 로컬 구성표 (70 %)보다 약 23 % 높고 약 6 %가 약 93 % 글로벌 방식 (99 %). 부하 분산의 결과로 마이그레이션되는 사용자의 수는 제안 된 계획 및 로컬 스키마는 비교적 낮은 오버 헤드 (각각 3.2 % 및 1.8 %)를 가지지 만 글로벌 스키마는 다른 스키마보다 약 5 배 더 많은 사용자 마이그레이션을 발생시킵니다. 또한 서버 수가 16 개에서 144 개로 늘어남에 따라 제안 된 구성표의 효율성은 약 6 % 만 감소하는 반면 로컬 구성표의 효율성은 약 36 %입니다. 또한 글로벌 방식의 오버 헤드는 약 26 % 증가하지만 제안 된 방식의 오버 헤드는 약 4 % 만 증가합니다.

Sections : 

2장 : 다중 서버 DVE시스템을 위한 기존 동적 부하분산 기법의 소개

3장 : 제안하는 동적 부하분산 기법.

4장 : 시뮬레이션을 통해 기존의 기법과 제안한 기법의 성능 비교.

5장 : 결론

Results : 

시뮬레이션 결과는 사용자 및 서버 수가 각각 22,500 및 100 일 때 기존의 로컬 및 글로벌 방식보다 성능이 우수함을 보여줍니다.

효율성 측면에서 동적 부하 분산 방식으로 인해 과부하 된 서버로 인한 사용자 비율이 감소하는 경우 제안 된 구성표는 로컬 구성표 (70 %)보다 약 23 % 높고 약 6 %가 약 93 % 글로벌 방식 (99 %). 부하 분산의 결과로 마이그레이션되는 사용자의 수는 제안 된 계획 및 로컬 스키마는 비교적 낮은 오버 헤드 (각각 3.2 % 및 1.8 %)를 가지지 만 글로벌 스키마는 다른 스키마보다 약 5 배 더 많은 사용자 마이그레이션을 발생시킵니다. 또한 서버 수가 16 개에서 144 개로 늘어남에 따라 제안 된 구성표의 효율성은 약 6 % 만 감소하는 반면 로컬 구성표의 효율성은 약 36 %입니다. 또한 글로벌 방식의 오버 헤드는 약 26 % 증가하지만 제안 된 방식의 오버 헤드는 약 4 % 만 증가합니다.

연계 논문 : Networked Virtual Environments: Design and Implementation.