Pastry DHT가 효율적인 라우팅을 사용하는 이유

Question

최근에 Pastry DHT에 대한 기사를 읽었습니다. Pastry DHT에는 효율적인 라우팅이 있습니다. Pastry의 라우팅에서 각 단계의 노드 ID는 대상 노드와 더 긴 공통 접두어를 사용하지만 노드 ID는 무작위로 할당되므로 메시지가 대상에 도착하기 전에 매우 먼 거리를 이동할 수 있으므로 라우팅이 효율적이지 않습니다.

예를 들어, Pastry 라우팅, 대상 노드 ID는 d467c4, 시작 노드 ID는 65a1fc, 라우팅 프로세스는 65a1fc-> d13da3-> d4213f-> d462ba-> d46702-> d467c4입니다. 이 라우팅의 노드는 전 세계에 걸쳐 있습니다 (ID는 무작위로 할당됩니다.) 메시지는 최종 노드에 도착하기 전에 전 세계를 여행 할 것입니다. 따라서이 라우팅은 효율적이지 않습니다.

왜 Pastry DHT가 효율적인 라우팅을 가지고 있습니까?

Answer 1

이는 효율성에 대한 귀하의 생각에 달려 있습니다. 오버레이 네트워크를 설계 할 때 첫 번째 관심사는 일반적으로 네트워크 크기에 비례하여 총 홉 수를 제한하는 것입니다. 즉, n 노드가있는 경우 O (n) 라우트의 경우 O (log n)은 전체 네트워크 인식 없이도 달성 할 수 있기 때문에 일반적인 목표입니다.

링크를 따라 대기 시간, 경로 비용 또는 최소 대역폭에 대한 경로 길이는 두 번째 순위 문제입니다. 홉 길이가 최적화 된 후 일종의 지역 인식 또는 클러스터링을 추가함으로써 종종 달성됩니다.

패스트리는 홉 메트릭에 효율적입니다.