earticle

영어

This paper discusses the design and evaluation of KTree, a reliable constant degree distributed hash table (DHT) for distributed data storage and retrieval for peer-to-peer systems. KTree’s ability to route efficiently even when a large number of nodes are joining and/or leaving the system makes it an ideal choice for different sort of applications including data sharing. Each node in KTree has a unique node identifier belonging to an identifier space. In KTree, we partition the identifier space into levels and segments and fix the manager of every segment. A node in KTree maintains links with a constant number of nodes at the next level to forward queries. A node also creates a link with a node at the top level to get the global view of the system. This way KTree traverses a logarithmic number of nodes to route a query to its destination. An insert operation stores a key on a number of diverse nodes. The lookup operation, on the other hand, retrieves the stored data efficiently and reliably. A prototype implementation of KTree on PeerSim proves its reliability and efficiency. The experimental results achieved with a network of 50,000 nodes confirm its self-configurability and ability to route messages even under a high rate of churn.

한국어

본 논문은 P2P 시스템에서 분산 데이터 저장과 획득을 위한 신뢰성 있는 라우팅 방법인 KTree의 설계와 실험 평가를 다룬다. 많은 노드들이 시스템에 들어오고 나가는 상황에서도 KTree는 효율적인 라우팅을 가능하게 하여 자료 공유를 포함한 다양한 응용에 이상적인 선택이다. KTree에서 각각의 노드는 식별자 공간에 속하는 고유한 식별자를 갖는다. KTree는 식별자 공간을 층과 칸으로 나누고 각 칸마다 관리 노드를 정한다. 질의를 전달하기 위해서 각 노드는 다음 층의 일정한 숫자의 노드들과의 연결을 유지한다. 또한 시스템 전체에 대한 시야 확보를 위해서 각 노드는 꼭대기 층에 있는 노드와의 연결도 유지한다. 이러한 방법으로 KTree는 질의를 목적지까지 보내기 위해서 log(n) 개의 노드를 거치게 된다. 삽입 연산은 데이터를 여러 노드에 저장한다. 검색 연산은 이렇게 저장된 데이터를 효율적이고 안정적으로 되찾는다. PeerSim에 구현한 KTree의 시험적 구현을 통해서 신뢰성과 효율성을 확인할 수 있었다. 50,000 노드의 네트워크를 대상으로 한 실험 결과에서 노드들의 잦은 상태 변경에도 메시지를 잘 전달 할 수 있음을 확인할 수 있었다.