[컴퓨터 네트워크] Kademlia DHT 카뎀리아 분산해시테이블 알아보기

Kademlia의 개념

• 분산 P2P(peer-to-peer) 컴퓨터 네트워크를 위한 분산해시테이블(Distributed Hash Table DHT)
• UDP를 사용해서 노드간 소통
  ** UDP : User Datagram Protocol / 데이터를 데이터그램/독립적인 패킷 단위로 처리하는 프로토콜
  (비연결형 서비스 제공, 정보 주고받을 때 별도의 신호 주고 받지 않음, 신뢰성이 낮으나 속도가 빠름) 
• 참여 노드간 가상/오버레이 네트워크 형성 
  ** 오버레이 네트워크: 물리 네트워크 위에 성립되는 가상의 네트워크로 물리적 네트워크는 고려하지 않고 논리적 링크로 많은 노드들을 연결할 수 있음 
• 노드 ID로 노드 식별 - 파일 해시에 대한 direct map, 카뎀리아 상에서의 위치 정보 저장 

Kademllia 알고리즘

• 찾고자 하는 노드의 ID (key)와 더 가까운 노드를 탐색
  • 찾고자 하는 노드를 반환
  • 또는 해당 노드와 가장 가까운 노드를 반환 
• 두 노드간 거리 distance(x,y) = x XOR y
• n개의 노드가 있을 때 탐색 시간 복잡도 = O(logn)

Kademlia : Identifier Space

• 각 노드 ID = m-bit identifier 
• 2^m 개의 리프 노드를 가진 이진트리
• 각 노드는 m 개의 서브트리를 가짐 (즉, 라우팅 테이블에서 m 개의 행을 갖는다)
• ex) ID가 4-bit라면 identifier space는 16(2^4)개의 리프노드를 가지고, 높이가 4인 이진트리
• key-n 은 자신과 인접한 양 옆은 노드 N-i 또는 N-j 를 가지고 n XOR i n XOR j 연산을 하여 더 작은 값을 가진 노드에 저장됨 

Kademlia : Routing Table

• m-bit identifier인 경우 각 노드들은 m개의 서브트리를 가지며, 라우팅 테이블에서 m개의 행을 가짐
• 한 노드의 라우팅 테이블(서브 트리)에서  m 개의 행 중 값이 작은 행 (0에 가까운 행)에 자신 보다 뒤에 위치한 m개 이하의 노드들 각각 XOR연산을 했을 때 그 값이 가장 작은 수를 0번부터 차례대로 삽입 
• ex) N6 노드를 그 앞에 있는 N8, N11, N15와 XOR 연산을 해보면 각 결과가 14, 13, 9가 도출됨 따라서 N6의 라우팅 테이블의 0 번부터 2에 삽입될 노드 순서는 N15 - N11 - N8이 됨 
• ex2) N0 노드가 key12를 찾으라는 메시지를 받은 경우 )
  1. N0 = 0000, K12 = 1010 => common prefix의 길이 = 0
  2. N0의 라우팅 테이블에서 0번째 행에 있는 노드 (N8)로 메시지를 보냄
  3. N8 = 1000, K12 = 1010 => common prefiex의 길이 = 1
  4. N8의 라우팅 테이블에서 1번째 행에 있는 노드(N15)로 메시지를 보냄 
  5. N15는 K12를 저장하고 있으므로 값을 반환 

Kademlia : k-Buckets

• 노드 별 라우팅 테이블의 각 행은 k-bucket 을 참조 
• 각 행은 자신이 속한 서브트리 (라우팅 테이블)에서 최소 k개의 노드를 유지
• 카뎀리아는 a개의 병렬적인 쿼리를 k-bucket의 꼭대기에 있는 a개의 노드에 보내는걸 허용  
• 노드가 쿼리 또는 응답을 받으면 k-bucket 업데이트 
• 쿼리에 대한 응답이 없으면 쿼리를 보낸 쪽은 k-bucket에서 목적지 노드를 제거

 

---

References

• en.wikipedia.org/wiki/Kademlia
• mangkyu.tistory.com/15
• ko.wikipedia.org/wiki/%EC%98%A4%EB%B2%84%EB%A0%88%EC%9D%B4_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC
• 성균관대학교 소프트웨어학과 추현승 교수님 2021-1 컴퓨터 네트워크 개론 수업