Recently, Distributed hash tables (DHTs) have been widely adopted in many P2P systems as a scalable and efficient infrastructure. Since most of the recent DHT-based P2P systems perform key encoding using consistent hash functions, even semantically related objects are stored at randomly selected peer nodes. This de-clustering of semantically related objects results in significant inefficiency in processing multi-dimensional range queries and data updates as are common in emerging DHT-based applications such as massively multiplayer online games (MMOGs) and P2P auctions because of the large number of DHT lookups required for such processing. This paper proposes an efficient object clustering framework, CISS, for DHT-based P2P applications. Using DHT as a basic lookup layer, CISS applies a locality preserving function (LPF) for object clustering instead of a consistent hash function. Moreover, to maximize the benefit of object clustering, it proposes efficient routing protocols for multi-dimensional range queries and data updates. CISS also suggests efficient load balancing algorithms as the skewed distribution of queries and objects can result in significant load imbalance. The performance benefits of CISS are demonstrated by conducting intensive simulations. The results show that CISS has good load balancing performance and significantly reduces the number of DHT lookups compared to existing DHT-based P2P systems which use a hash function.
기존의 DHT(Distributed Hash Table) 기반의 P2P (Peer-to -peer) 시스템들은 해쉬(hash) 함수를 사용하여 키(key)를 인코딩(encoding)하기 때문에 의미적으로 관련 있는 객체들을 전혀 다른 노드에 저장시키게 된다. 이로 인해 기존의 시스템들은, MMOG(Massively Multiplayer Online Game)나 P2P 옥션과 같이 최근 새롭게 등장하는 응용프로그램에서 요구하는 다차원 영역질의(multi-dimensional range query)나 연속된 데이터 업데이트(data update)를 처리하기 위해 많은 수의 DHT lookup을 유발시키게 된다. 그리고 이러한 다수의 DHT lookup은 라우팅 측면에서 상당한 비효율성을 가져온다. 이 논문은 DHT 기반의 피어-투-피어 응용프로그램들을 위한 효율적인 객체 클러스터링 프레임워크(object clustering framework), CISS를 제안한다. CISS는 DHT를 기본적인 Lookup 계층으로 이용하지만, 해쉬 함수 대신 지역성 보존 함수(LPF: Locality Preserving Function)를 제공함에 의해 의미적으로 관련 있는 객체들의 클러스터링을 보장한다. 그리고 객체 클러스터링의 효과를 극대화 하기 위해, 연속된 데이터 업데이트와 다차원 영역 질의를 위한 효율적인 라우팅 프로토콜인 caching-based update routing protocol과 forwarding-based query routing protocol을 각각 제시한다. 하지만, CISS에서는 각 노드가 의미적으로 관련된 객체들을 담당하기 때문에, 질의 또는 객체들이 한 영역에 집중됨에 의해 그 영역을 담당하는 노드가 과부하 될 수 있게 된다. 따라서 CISS는 노드가 과부하 되는 것을 막을 수 있는 부하 분배 (load balancing) 알고리즘을 제안한다.
이 논문에서는 시뮬레이션을 통해 CISS의 성능을 측정하였다. 시뮬레이션 결과는 caching based update routing protocol을 통해 100,000개의 노드 상황에서 데이터 업데이트를 위한 DHT lookup 수가 93%까지 줄어들고 forwarding-based query routing protocol을 통해 다차원 영역질의를 위한 DHT lookup 수가 보다 더 현저하게 줄어드는 것을 보여준다. 또한 시뮬레이션 결과는 제안된 부하 분배 알고리즘이 객체 클러스터링을 유지하면서 과부하 된 노드의 부하를 효율적으로 분산시키는 것을 나타낸다.
