Distributed Hash Tables (DHTs) have been noted as a promising paradigm that provides an efficient lookup service for peer-to-peer applications. However, as many peer-to-peer applications are associated with a semantic and multi-attribute lookup service, existing DHTs have been modified to accommodate multi-attribute complex queries. Randomizing hash functions (e.g., SHA-1) that has been traditionally adopted by DHTs are now being replaced by the na$\"{i}$ve-order preserving mapping, and a multi-attribute scheme has been integrated into DHT-based systems. However, most existing approaches focus on reducing the load imbalance caused by such a mapping with an external load balancing scheme (e.g., virtual server-based schemes). We have noted that it is not sufficient enough for large scale peer-to-peer systems since the overhead of an external load balancing becomes larger and larger as the systems’ size and the skewness of data distribution increase. This thesis proposes ArithNet, a scalable protocol for supporting multi-attribute complex queries and inherent load balancing. ArithNet differs from previous complex query supporting systems in that it supports multi-attribute complex queries and inherent load balancing simultaneously. To guarantee efficient routing and inherent load balancing, ArithNet uses Arithmetic Mapping and the most selective attribute query resolution based on statistics obtained from studying training models. Our evaluation shows that ArithNet is able to achieve its goals of logarithmic-hop routing and near-uniform inherent load balancing in a very efficient and sophisticated way.
분산 해시 테이블(Distributed Hash Table)은 다양한 P2P 어플리케이션(peer-to-peer)을 위해 효율적인 검색 서비스 및 라우팅 기능을 제공하는 플랫폼으로 많이 이용되고 있다. 하지만 현재 점점 더 많은 어플리케이션들이 의미 기반의 검색 서비스와 다중 속성 검색을 요구하고 있다. 예를 들면 그리드 자원 검색(Grid resource discovery)의 경우 자원들이 다중 속성에 의해 등록(register)이 되며 다중 속성에 의해 검색이 된다. 또한 프린터의 PPM같은 속성들은 기존의 랜덤 해쉬를 사용하면 그 데이터의 시맨틱이 파괴되므로 효율적인 검색을 제공할 수 없게 된다. 현재 DHT기반의 시스템들이 그러한 2가지 문제를 해결하기 위해서 Mercury나 Squid와 같은 많은 솔루션들을 내놓았다. 하지만 그러한 솔루션들은 단순한 매핑(Na\iumlve-Order Preserving Mapping)을 사용함으로 인해 DHT 고유의 특성인 내재적 로드 밸런싱이라는 특성을 잃어버렸다. 그리고 다중 속성을 지원함에 있어서도 여러 개의 DHT를 한 시스템상에서 논리적으로 관리함으로 인해 큰 오버헤드가 발생하였다. 따라서 본 논문에서는 시맨틱과 다중 속성을 지원하는 네트워크인ArithNe을 제안한다. ArithNet은 다중 속성 콤플렉스 쿼리와 내재적 로드 밸런싱을 지원하는 확장가능(scalable)한 프로토콜이다. ArithNet이 기존 콤플렉스 쿼리와 다른점은 콤플렉스 쿼리와 내재적 로드 밸런싱을 동시에 지원한다는 점이다. 내재적 로드 밸런싱을 지원하기 위해 ArithNet은 산술적 매핑과 트레이닝 데이터에서 통계적 자료를 추출하여 만들 통계적 모델에 기초한 가장 셀렉티브한 쿼리 레졸루션(Most SelectiveQuery Resolution)을 사용한다. 또한 산술적 매핑과 가장 셀렉티브한 쿼리 레졸루션은 많은 불필요한 문제를 해결하여 ArithNet을 더 간결하면서도 견고하게 만든다. 예를 들어 산술적 매핑과 다중 속성 차원을 결합하기 위해 개발한 통계자료기반 속성 선택 기법(Statistics-based Attribute Selection)은 기존의 시스템에서 발생하던 통신 오버헤드를 제거한다. 하지만 사용하는 트레이닝 데이터의 정확도에 따라 그 정확성이 떨어질 수 있다는 단점이 있다. 본 논문은 다양한 실험을 통해 ArithNet이 기존 DHT의 장점인 로그적인 홉 라우팅과 유니폼한 로드 밸런싱을 그리고 시맨틱과 다중속성을 지원함을 보인다. 그리고 본 연구에서는 Mercury와 Squid같은 기존 시스템들과의 비교를 통해 ArithNet의 우수성을 증명하였다. 하지만 ArithNet에도 단점은 있다. 데이터 모델이 추측이 틀린 경우에는 매핑의 질(Quality)이 떨어질 수 있고 또한 데이터 모델의 변화는 시스템에 반영시킬 수 없다는 점이다. 또한 런타임 오버헤드는 감소한 반면 오프라인(off-line) 오버헤드가 발생하였다. 오프라인 오버헤드의 대부분은 매핑을 위해서 데이터 모델을 트레이닝하는 단계에서 발생한다. 하지만 영어나 언어의 특성상 항상 정확한 데이터 모델을 알지 못할 경우에도 ArithNet의 장점은 유지됨으로 그 문제의 심각성은 크지 않다고 할 수 있다. 향후 연구로는 변화하는 데이터의 분포를 시스템에 반영하기 위한 적응적 산술 코딩에 대한 연구를 통하여 변화하는 데이터 분포에서도 데이터를 균등하게 매핑하는 기술을 적용할 것이다. 또한 보다 더 많은 노드가 있고 동적인 P2P 네트워크에서 실험을 진행할 예정이다. 그리고Planetlab과 같은 실제 테스트베드에서 보다 실제적인 성능을 평가 또한 진행할 예정이다.
