Kademlia 알고리즘

정의

카뎀리아(Kademlia)는 분산 P2P 컴퓨터 네트워크를 위한 분산 해시 테이블로 2002년 Petar Maymounkov와 David Mazières가 고안하였다. 논문은 네트워크 구조 및 노드 탐색을 통한 정보교환에 대한 명세를 기술하고 있다. 카뎀리아 노드는 UDP를 이용하여 서로 통신하며 참여 노드간에 가상 또는 오버레이 네트워크를 형성한다. 노드는 숫자 또는 '노드 ID'로 구분하는데 '노드 ID'는 노드를 식별하는 것 뿐만 아니라 카뎀리아 알고맂므이 값(일반적으로 파일 해시 또는 키워드)의 위치를 찾는데도 사용한다. 실제로 '노드 ID'는 파일 해시에 대한 직접 사상(direct map)으로 파일 또는 자원을 어디서 획득 할 수 있는지에 대한 정보를 저장하고 있다.

값을 찾을 때, 카뎀리아 알고리즘은 연관 키를 갖고몇번의 단계를 거쳐 네트워크를 탐색한다. 각 단계는 키(key)와 더 가까운 노드를 탐색하는 작업으로 연결된 노드가 찾던 값을 반환하거나 더 가까운 노드를 찾을 수 없을 때까지 계속 된다. 이는 매우 효율적인 방식으로, 카뎀리아는 다른 DHT와 같이 시스템 전체에 n개의 노드가 존재할 때 O(log(n))개의 노드만 탐색한다.

분산 구조에서 얻을 수 있는 추가적인 장점은 서비스 거부 공격에 대한 저항성이다. 모든 노드가 넘쳐 흐르더라도 네트워크 가용성에는 제한적인 영향만 미치며, 이 "구멍"들 주위로 네트워크를 긴밀히 연결하여 스스로 기능을 회복한다.