In this paper, we propose a novel and efficient load balancing scheme to solve maintenance overhead and query routing latency problems in virtual server-based DHT systems. A unique feature of our scheme is a functional separation of the virtual server. That is, we functionally divide a virtual server into two logical nodes: Virtual Routing Node and Virtual Storage Node. Also, we suggest a simple routing algorithm which causes only $\theta(1)$ additional hop on top of Chord, and we apply two different join algorithm to reduce the overhead for load balancing process without affecting the routing performance.
We perform an extensive simulation with varying parameters in terms of load balancing effect, load balancing overhead, maintenance overhead and routing performance. The simulation results show that our scheme effectively achieves good load balancing with considerably reduced query routing length and without increasing the number of connections that each physical node maintains compared to the legacy virtual server scheme.
분산 해시 테이블(Distributed Hash Table)은 다양한 P2P 어플리케이션(Peer-to-peer Application)을 위해 효율적인 검색 서비스(Service) 및 라우팅(Routing) 기능을 제공하는 플랫폼(Platform)으로 많이 이용되어 왔다. 하지만 분산 해시 테이블이 다수의 노드들이 참여하는 P2P 네트워크에서도 효과적으로 이용되기 위해서는 로드 밸런싱(Load Balancing)이 일차적으로 해결되어야 할 문제이다. 분산 해시 테이블은 해시 함수에 의해 일정 수준의 로드 균형 효과를 갖기 때문에, 기존의 가상 서버(Virtual Server)의 개념을 이용한 기법을 추가적으로 적용하면 효과적으로 로드의 불균형을 해소할 수 있다. 가상 서버 방식은 한 개의 물리적 노드가 다수의 가상 서버를 관리함으로써 물리적 노드의 로드를 작은 로드로 분할하고 로드가 집중된 노드에서 집중되지 않은 노드로 가상 서버를 이동시킴으로써 로드의 균형을 이룬다.
하지만 현재 많은 어플리케이션들이 의미 기반의 검색 서비스와 연관되면서 분산 해시 테이블에서 해싱(Hashing)을 통해 제공하는 정확한 키워드 매칭(Matching) 기반의 검색이 제한되고, 해시 함수를 이용하지 않는 색인(Indexing) 방법들이 이용 되면서 또다시 로드 밸런싱 문제가 제기되고 있다. 해시를 사용하지 않는 색인 방법이 데이터에 내재되어 있는 불균형이 그대로 P2P 네트워크에 이루는 노드들에게 반영되어 심각한 로드 불균형 문제를 발생시키기 때문이다. 따라서 로드 불균형 해소를 위해서는 훨씬 많은 가상 서버들이 필요하게 되고, 이는 (1) 가상 서버의 관리 부하와 (2) 질의 응답의 대기 시간을 급격하게 증가시키는 문제점을 발생시킨다
본 논문에서는 위에 기술한 두 가지 문제를 해결하고 효과적으로 로드 불균형을 해소하는 새로운 로드 밸런싱 기법을 제안한다. 제안된 기법은 가상 서버가 갖는 라우팅과 데이터 관리(Data Management) 두 가지 기능을 분리시켜서 가상 라우팅 노드(Virtual Routing Node)와 가상 스토리지 노드(Virtual Storage Node) 두 가지 종류의 논리적인 노드들을 이용한다. 즉, 기존의 모든 가상 서버가 관리 부하를 발생시키는 라우팅 기능을 갖고 있던 것에 반해, 라우팅 기능을 라우팅 노드라고 불리는 소수의 노드에 집중시킴으로써 효율적으로 관리 부하를 줄인다. 또한 핑거 테이블(Finger Table)과 스토리지 노드 테이블(Storage Node Table)에 기반하는 라우팅 기법을 제안함으로써 가상 서버에 의해 발생하는 질의 응답의 라우팅 지연문제를 해결하고 라우팅 노드와 스토리지 노드에 서로 다른 조인 알고리즘을 적용하여 라우팅 성능의 저하없이 로드 밸런싱 과정에서 발생하는 오버헤드 또한 최소화한다.
본 연구가 수행한 실험결과를 통해, 제안된 로드 밸런싱 기법은 효과적으로 로드의 균형을 달성하는 한편, 기존의 가상 서버 기법에서 발생하는 질의 응답 라우팅의 지연을 상당량 줄이고, 가상 서버의 수에 관계없이 라우팅 테이블 관리 오버헤드를 일정한 수준으로 저하시킨다는 것을 증명하였다. 향후 연구로 제안된 로드 밸런싱 기법을 보다 노드가 많고 동적인 P2P 네트워크에서 실험을 할 것이며 Planetlab과 같은 실제 테스트베드(Testbed)에서 보다 실제적인 성능을 평가할 예정이다.
