[네트워크] Ch3.3 Circular DHT

 

본 글은 학교 네트워크 수업을 들으며, "Computer Networking: A Top-Down Approach 8ed(컴퓨터 네트워킹: 하향식 접근 제8판)"을 기반으로 공부한 내용을 정리한 글입니다.

 

Ch3.3 Circular DHT

- DHT의 특수한 형태 : 둥글게 말린 모양.

- 각 peer은 자신의 immediate successor과 predecessor만 알고 있음.

- circular linked list 생각하면 됨.

- peer가 N개 있을 때, 어떤 peer가 쿼리를 할 때 응답의 시간복잡도는 O(N)

=> 좀 빠르게 쿼리할 수 없을까?

 

Shortcut Mechanism

- 각 peer는 predecessor, successor뿐만 아니라, `shortcut`의 정보 까지도 저장하고 있음.

- 각 peer는 다른 어떤 peer로부터 응답을 한 번 받으면, 그 peer까지의 shortcut이 있다는 걸 알게 됨.

- 그 다음부터는 쿼리할 때 저 shortcut을 활용하게 됨.

- shortcut을 사용한 쿼리 응답의 시간복잡도는 O(log N)까지 떨어짐.

peer Churn(들락날락)

: 어떤 peer이 따로 warning없이 연결에 들락날락 하는 게 빈번히 발생하는 상황.

Handling peer churn

- 각 peer들이 `immediate successor` 뿐만 아니라, `next successor`의 정보까지 알도록 해놓고,

- 각 peer들이 주기적으로 저 두 peer에게 ping 메시지를 보내 아직 살아있는지 체크하도록 함

IF. 어떤 peer의 immediate successor가 연결을 떠났다?

=> 그 peer의 next successor을 immediate successor로 삼음. 

* 이는 당연하게도 predecessor에 대해서도 적용됨. ping 메시지도 4개의 peer에게 보낸다고 보는 게 맞을듯.

 

IF. 새로운 peer가 Circular DHT에 들어오고자 한다?

- 만약 새로운 peer 28이 오직 peer 60에 대해서만 알고 있다면, 

- peer 60으로 JOIN 메시지를 보내고, 이는 immediate successor로 relay됨.

- peer 25이 JOIN 메시지를 받으면, 이 peer은 28이 자신과 자신의 successor 사이에 있다는 것을 알고 있음.

- 따라서 peer 25 선에서 JOIN-ACK을 peer 28에게 보내고, peer 28은 이를 받고 peer 25와 32 사이에 참여함.