콘텐츠 주소 지정 가능 네트워크

Content-addressable network

CAN(Content-Addressable Network)은 분산형 분산형 P2P 인프라스트럭처로 인터넷과 같은 규모로 해시 테이블 기능을 제공합니다.CAN은 Code, Pastry 및 Tapestry와 동시에 도입된 최초의 4가지 분산 해시 테이블 제안 중 하나였습니다.

개요

다른 분산 해시 테이블과 마찬가지로 CAN은 확장성이 뛰어나고 폴트 톨러런스하며 자가 구성되도록 설계되었습니다.건축 설계는 다중 토러스 상의 오버레이 네트워크의 일종인 가상 다차원 데카르트 좌표 공간입니다.이 n차원 좌표 공간은 노드의 물리적 위치 및 물리적 연결과는 완전히 독립적인 가상 논리 주소입니다.공간 내의 점은 좌표로 식별됩니다.좌표공간 전체가 시스템 내의 모든 노드 간에 동적으로 분할되어 모든 노드가 전체 [1]공간 내에 적어도1개의 별개의 존을 소유한다.

라우팅

CAN 노드는 각 네이버의 IP 주소와 가상 좌표 존을 유지하는 라우팅 테이블을 유지합니다.노드는 좌표 공간 내의 목적지 지점을 향해 메시지를 라우팅한다.노드는 먼저 어느 네이버존이 행선지 포인트에 가장 가까운지 판별한 후 라우팅 [1]테이블을 통해 해당 존노드의 IP 주소를 검색합니다.

노드 결합

CAN에 가입하려면 가입 노드가 다음 조건을 충족해야 합니다.

  1. 오버레이 네트워크에 이미 있는 노드를 찾습니다.
  2. 분할할 수 있는 영역을 특정합니다.
  3. 새로 분할된 [1]존에 인접한 노드의 라우팅 테이블을 업데이트합니다.

오버레이 네트워크에 이미 존재하는 노드를 검출하기 위해 부트스트랩노드를 사용하여 오버레이 네트워크에 현재 [1]있는 노드의 IP 주소를 가입 노드에 통지할 수 있습니다.

가입 노드는 이미 CAN에 있는 노드의 IP 주소를 수신한 후 자신의 존 식별을 시도할 수 있습니다.조인 노드는 좌표 공간 내의 점을 랜덤으로 선택하여 랜덤포인트로 전송되는 조인 요구를 수신된IP 주소 중 하나로 송신합니다.오버레이 네트워크 내의 노드는 존 투 IP 라우팅 테이블을 통해 가입 요구를 올바른 디바이스에 라우팅합니다.수신처 포인트의 존을 관리하는 노드는 조인 요구를 수신하면 존을 반으로 분할하여 전반부에 할당하고 후반부에 조인 노드를 할당함으로써 조인 요구를 수용할 수 있습니다.가입요구에 따르지 않을 경우 가입노드는 [1]네트워크에 정상적으로 가입할 때까지 좌표공간 내의 랜덤포인트를 계속 선택하여 이들 랜덤포인트로의 가입요구를 송신합니다.

존 분할 및 할당이 완료되면 네이버노드는 2개의 새로운 존의 좌표와 대응하는 IP 주소로 갱신됩니다.라우팅 테이블이 갱신되고 업데이트가 네트워크를 [1]통해 전파됩니다.

노드 출발

출발 노드를 처리하려면 CAN이 다음을 수행해야 합니다.

  1. 노드가 출발하는 것을 식별하다
  2. 출발 노드의 존이 인접 노드에 의해 병합되거나 인계되는
  3. 네트워크 [1]전체에서 라우팅 테이블을 업데이트합니다.

노드 이탈 검출은 예를 들어 네이버 간의 라우팅 테이블 정보를 정기적으로 브로드캐스트하는 하트비트 메시지를 통해 수행할 수 있습니다.네이버에서 소정의 시간 동안 무음 상태가 지속되면 그 네이버노드는 장애로 판단되어 [1]출발 노드로 간주됩니다.또는 기꺼이 출발하는 노드는 그러한 통지를 그 네이버에 브로드캐스트할 수 있다.

출발 노드가 식별되면 해당 노드를 Marge 또는 인계해야 합니다.우선, 인접 노드의 존이 유효한 존을 형성하기 위해서 인접 노드의 존과 결합할 수 있는지 아닌지를 판단하기 위해서, 출발 노드의 존을 분석한다.예를 들어, 2d 좌표 공간의 구역은 정사각형 또는 직사각형이어야 하며 L자 모양일 수 없습니다.검증 테스트는 모든 인접 존을 순환하여 머지가 정상적으로 이루어질 수 있는지 여부를 판별할 수 있습니다.잠재적인 머지 중 하나가 유효한 머지로 간주되면 존이 머지됩니다.유효한 것으로 간주되는 Marge가 없는 경우 존이 가장 작은 네이버노드가 출발 노드의 [1]존 제어를 이어받습니다.테이크오버 후 테이크오버노드는 추가 제어된 존을 각 네이버존과 정기적으로 Marge를 시도할 수 있습니다.

머지가 성공하면 인접 존 노드의 라우팅 테이블이 머지를 반영하도록 갱신됩니다.네트워크는 오버레이 네트워크의 서브섹션을 머지 후 1개의 단일 존으로 간주하고 모든 라우팅 처리를 이 사고방식으로 처리합니다.테이크오버를 실시하기 위해 테이크오버노드는 인접 존노드의 라우팅 테이블을 갱신하여 어느 한 존에 대한 요구가 테이크오버노드로 해결되도록 합니다.이와 같이 네트워크는 오버레이 네트워크의 서브섹션을 2개의 독립된 존으로 간주하여 모든 라우팅 처리를 이러한 사고방식으로 처리합니다.

개발자

실비아 래트나사미, 폴 프란시스, 마크 핸들리, 리처드 카프, 스콧 셴커

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d e f g h i Ratnasamy; et al. (2001). "A Scalable Content-Addressable Network" (PDF). In Proceedings of ACM SIGCOMM 2001. Retrieved 2013-05-20. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)