In distributed systems, the purpose of load balancing is to improve system performance by redistributing tasks from heavily-loaded nodes to lightly-loaded ones. The location policy is the most important component of a distributed load balancing algorithm. It locates the destination nodes to or from which tasks will be transferred. It should evenly distribute workload to the entire nodes with minimal delay for transferring task. An efficient adaptive location policy is required in the sense that it can react to changes in system state and achieve high performance.
In this thesis, we propose a new distributed adaptive location policy based on state knowledge. The state knowledge is composed of the system state information collected at run time and the predefined global static information that is a priority order of each node for transferring tasks. The information is systematically maintained in each node by using an efficient data structure and a rule for collecting state information with low overheads. When load balancing is triggered at a heavily-loaded node, the proposed location policy dynamically predicts lightly-loaded nodes and the other heavily-loaded ones by exploiting state knowledge. Then it adaptively finds a good lightly-loaded node that minimizes useless polling and maximizes even load distribution.
An analytic model is developed to compare the proposed adaptive location policy with other well known policies. The validity of the model is checked with an event-driven simulation, and it is shown that the proposed adaptive location policy exhibits a significant performance improvement over other policies, especially at high system loads. Also, the proposed policy is shown to significantly improve polling hit ratio and to avoid system instability.
분산 시스팀에서 부하균형의 목적은 부하가 높은 노드(과부하 노드)에서 부하가 낮은 노드(저부하 노드)로 태스크를 동적으로 재 분배함으로써 시스팀의 성능을 향상 시키는 것이다. 위치 정책은 분산 부하균형의 가장 중요한 구성요소이다. 위치 정책은 태스크가 이동될 목적 노드를 찾는다. 위치 정책은 최소한의 지연으로 노드들의 부하를 균등하게 하여야 한다. 따라서 시스팀 상태의 변화에 잘 적응하고 시스팀의 성능을 향상할 수 있는 효과적인 동적 위치 정책이 절실히 요구된다.
이 논문은 상태지식에 바탕을 둔 분산 동적 위치 정책을 제안한다. 상태지식은 시스팀의 운용기간 동안 수집되는 각 노드들의 상태정보와 태스크를 이동할 때 노드들 사이에 우선순위를 부여하기 위한 사전에 정의되는 정적인 전역 정보로 구성된다. 상태지식은 효과적인 데이타 구조와 시간적인 부담이 낮은 상태정보 수집규칙에 의하여 각 노드에서 체계적으로 관리된다.
부하균형이 과부하 노드에서 시작되었을 때, 제안되는 위치 정책은 상태지식을 탐색함으로써 저부하 노드들과 다른 과부하 노드들을 예측한다. 그리고 쓸모없는 노드 상태 탐색을 최소화하고 부하의 균등분배를 극대화하는 최적의 저부하 노드를 동적으로 찾아낸다.
제안되는 위치 정책과 기존의 잘 알려진 다른 위치 정책들과의 성능비교를 위하여 분석 모형이 설정된다. 분석 모형의 타당성은 event-driven 시뮬레이션 결과에 의하여 검증되며 제안되는 위치 정책이 시스팀의 과부하 부분에서 다른 정책들에 비해 특히 좋은 성능을 나타낸다는 사실이 보여진다. 또한 제안되는 위치 정책의 저부하 노드의 탐색에 대한 성공비율이 다른 정책에 비하여 아주 높으며 과부하 상태에서 태스크의 처리는 하지 못하고 쓸모없는 부하균형 만 반복적으로 실시하는 시스팀의 불안정한 상태가 초래되지않는 것도 보여진다.
