우리는 NS 서버 S1, S2, ..., SNS로 구성된 다중 서버 DVE 시스템을 고려합니다. 시스템이 유지하는 VE는 공간적으로 (논리적으로) NC 직사각형 모양의 셀 C1, C2, ... 및 CNC (NS << NC)로 세분됩니다.
셀은 NR 영역으로 그룹화되며 각 영역은 하나의 서버 (즉, NS = NR)로 관리됩니다.
각 서버는 사용자에 대한 최신 상태 정보를 유지 관리하고 전용 영역에있는 사용자 간의 상호 작용을 처리합니다.
사용자는 거주 지역을 관리하는 서버를 통해 상태 업데이트 메시지를 보내고받습니다.
그림 1은 16 대의 서버로 구성된 다중 서버 DVE 시스템의 모델을 보여줍니다.
VE는 256 개의 셀로 세분화되어 16 개의 영역으로 그룹화됩니다.
두 개의 셀은 공통 경계를 공유하는 경우 인접 (또는 이웃)으로 정의됩니다.
마찬가지로 한 영역에 다른 영역에 속한 셀에 인접한 셀이 포함되어 있으면 두 영역 (및 전용 서버)이 인접 영역으로 정의됩니다.
아바타가 나타내는 사용자는 지역별로 자유롭게 탐색하고 VE의 다른 사용자와 상호 작용합니다.
우리는 w (C)로 표시된 셀의 워크로드를 셀에 거주하는 사용자 수로 정의합니다.
모든 사용자가 동일한 비율로 상태를 업데이트한다고 가정하면 서버에 부과하는 셀의 처리 (계산 및 통신)로드는 셀의 사용자 수에 비례합니다.
마찬가지로 w (R)로 표시된 영역 및 해당 전용 서버의 작업 부하는 영역에 포함 된 셀의 작업 부하 합계로 정의됩니다.
각 서버는 작업 부하를 주기적으로 평가하고 작업 부하 정보를 인접 서버와 교환합니다.
시스템의 서버는 고속 네트워크를 통해 연결되어 있다고 가정합니다.
따라서 워크로드 정보를 이웃 서버와 교환하는 오버 헤드는 다른로드 분산 비용에 비해 경계가 없으며 무시할만한 수준으로 간주됩니다.
서버의 처리 능력은 제한적입니다. 즉, 서버 기능을 능가하는 대량의로드는 사용자로부터의 상태 업데이트 메시지 처리 시간을 증가시킵니다. CP로 표시된 서버의 용량은 서버가 사용자의 상호 작용 성능을 저해하지 않고 처리 할 수있는 최대 사용자 수로 정의됩니다.
모든 서버는 동일한 용량을 가진 것으로 가정합니다.
제안 된 동적 부하 분산 체계
워크로드가 용량을 초과하면 서버가로드 분산을 시작합니다.
로드 분배를 시작하는 서버는 먼저로드 분배에서 함께 사용될 서버 세트를 선택합니다.
서버 선택이 완료되면 시작 서버는 관련 서버 전용 영역을 다시 분할하여 거의 동일한 작업 부하를 갖도록합니다
.
그런 다음 관련된 서버는 다시 분할 결과에 따라 피어 - 투 - 피어 방식으로 서로의 셀과 사용자를 마이그레이션합니다.
다음 하위 절에서 위 작업을 자세히 설명합니다.
Adaptive Server 선택
기존의 로컬 및 글로벌 방식과는 달리, 제안 된 방식의 개시 서버는 다른 서버의 작업 부하 상태에 동적으로 적응하는 부하 분산에 포함될 서버 집합을 선택합니다.
시작 서버는 먼저 인접 서버 중 가장 적게로드 된 서버를 선택하고 선택된 서버가로드 분산에 참여하도록 요청합니다.
선택된 이웃 서버는 이미 다른로드 분산에 참여하거나 다른로드 분산을 수행하는 경우 요청을 거부합니다. 그렇지 않으면, 이웃 서 v에 대한 작업 부하 정보로 초기 서버에 응답하여로드 분산에 참여합니다.
참여한 이웃 서버가 시작 서버의 과도한 작업 부하를 처리 할 수없는 경우, 과부하 된 서버뿐만 아니라 선택된 이웃 서버의 인접 서버간에 선택이 다시 수행됩니다.
선택은 초기 서버의 과도한 작업 부하를 해결할 수있을 때까지 계속됩니다. 즉, 선택한 모든 서버의 평균 작업 부하가 임계 값보다 작아집니다.
부하 분산의 즉각적인 재 시작을 피하기 위해 임계 값을 CP의 90 %로 설정했습니다.
로드 분산과 관련된 서버 세트를 결정하는 절차는 다음과 같이 설명됩니다.
1.로드 밸런싱에 관여 할 서버 집합 인 SELECTED에 시작 서버가 삽입됩니다.
시작 서버의 인접 서버가 CANDIDATED에 추가되며 후보 서버가 포함됩니다
선택을 위해.
2. CANDIDATED에서 가장 적은 작업 부하를 가진 서버가 선택됩니다. 그런 다음 시작 서버는 선택한 서버
서버가로드 분산에 참여합니다.
(a) 선택된 서버가 다른로드 분산에 관여하지 않으면 시작 서버에 인접 서버의 작업 정보와 함께 응답합니다.
시작 서버가 응답을 받으면 선택된 서버가 SELECTED에 삽입되고 선택된 서버의 인접 서버가 이미 SELECTED 또는 CANDIDATED에 포함되어 있지 않으면 CANDIDATED에 추가됩니다.
(b) 선택한 서버가 이미 다른로드 분산에 참여한 경우 요청을 거부하고 선택된 서버가 후보 서버에서 제거됩니다.
3. 2 단계는 선택한 서버의 평균 작업 부하가 임계 값 -0.9 × CP보다 작아 질 때까지 반복됩니다.
그림 2와 같이 예제로 서버 선택 절차를 설명하겠습니다. 모든 서버의 용량은 동일합니다. 즉, CP = 100이다. 먼저 시작 서버 S6이 SELECTED에 삽입되고 인접 서버 (즉, S2, S5, S7 및 S10)가 CANDIDATED에 추가됩니다 (그림 2 (a)). 그런 다음 CANDIDATED 중에서 가장 적은 작업 부하를 갖는 S7이 선택되고로드 분산에 참여하도록 요청됩니다. S7이 인접 서버 (즉, S3, S6, S8 및 S11)에 대한 정보로 S6에 응답하면 S7이 SELECTED에 삽입되고 이미 SELECTED 또는 CANDIDATED에있는 S6을 제외하고 인접 항목이 SELECTED에 추가됩니다 CANDIDATED (그림 2 (b)). CANDIDATED 중에서 작업 부하가 가장 적은 S11가 선택되고 부하 분산에 참여하도록 요청됩니다. 그러나 S11은 이미 S12에서 시작된 다른로드 분산에 관련되어 있기 때문에 요청을 거부합니다. 따라서 S11은 CANDIDATED에서 제거되고 S10은 이제 CANDIDATED (그림 2 (c)) 중에서 가장 적은 작업 부하를 갖기 때문에 S10이 선택됩니다. SELECTED의 평균 작업량이 0.9 × CP = 90 미만이 될 때까지 위의 절차는 계속됩니다 (그림 2 (d) 및 그림 2 (e)).
영역 재분할 초기화 서버가로드 분산과 관련된 일련의 서버를 선택하면 관련 서버 전용 영역을 다시 분할합니다. 영역을 다시 분할 한 후에는 관련된 모든 서버의 작업 부하가 거의 같습니다. 우리는 병렬 및 고성능 컴퓨팅에서 광범위하게 사용되는 그래프 파티셔닝 기술을 활용합니다 [3]. 그래프 G = (V, E, P)는 상세한 정보, 즉 각 셀의 작업 부하를 사용하여 구성됩니다. 정점 vi ∈ V는 셀 Ci를 나타낸다. 버텍스 vi의 가중치는 셀 Ci의 작업량, 즉 w (Ci)로 설정됩니다. 에지 eij는 두 개의 셀 Ci와 Cj가 인접 해 있음을 나타낸다. 정점은 선택된 영역을 나타내는 파티션 P = {P1, P2, ..., P | SELECTED |}로 그룹화됩니다. 구성된 그래프는 [13]과 같은 그래프 파티셔닝 알고리즘을 사용하여 다시 파티셔닝되어 각 파티션에는 균등하게 가중치 된 버텍스 서브 세트가 있습니다. 즉 각 서버의 작업 부하는 대략 같습니다.
댓글