Adaptive Load Balancing based on Consistency

국문 초록 (Abstract)

부하 평형은 과부하 사이트의 부하종 일부를 다른 사이트로 옮김으로써 분산 처리 시스템의 성능 개선을 꾀한다. 본 논문에서는 source-initiate와 server-initiate 방 식을 모두 지원하며 극단적인 예로서 m/m/1 대기행렬(부하 비평형)과 m/m/n 대기 행렬 (완전한 부하 평형)도 모델화 할 수 있는 부하 평형 방식을 제안하였다. 이 방식은 상 태 변수를 각 사이트에 복제하고 각 복사본의 일치성을 완화한다. 그리고 오래된 스케 줄러가 통신을 하지 않고도 부하 평형을 보장할 수 있는 충분조건을 요도하였다. 이 모델을 이용하면 부하 평형의 문제가 상태의 일관성을 유지하는 문제로 바뀌게 되며 기존의 비딩 알고리즘보다 통신량이 적어지게 된다. 이벤트 트레이싱 방법으로 모의 실험하였으며 2개의 극단적인 경우 및 비딩알고리즘과 비교하였다. 그 결과 평균 응답 시간과 통신량에 있어서 비딩알고리즘보다 각각 0-35%, 40-100%의 성능향상을 보였다. 마지막으로 각 시스템 피라미터의 영향을 분석하였다.

다국어 초록 (Multilingual Abstract)

Load balancing attempts to improve the performance of a distributed computing system by transferring some of the workload of a congested site to others. A load balancing scheme that supports both the source-initiated and the server- initiated load balancing is proposed in this paper. It can model both the m/m/1 queue(no load balancing) and the m/m/n queue(perfect load balancing) as the extreme State variables are replicated into every site, and copy consistency constraints are relaxed more weakly. We propose weak copy consistency constraints which correlate the outdated state information to that of the current state. We also derive sufficient conditions under which each scheduler can guarantee the load balancing without communication Using this model, the problem of load balancing is converted to that of maintaining the consistency of states and communication overhead becomes less than that of the bidding algorithm. The scheme is simulated by event tracing, compared to the two extreme cases and the bidding algorithm. The results show that the mean response time and the number of messages are reduced by 0-35% and 40-100% respectively, compared with the bidding algorithm. Finally the effects of some system parameters are described.