KR20060045065A

KR20060045065A - Ｐ2ｐ 네트워크에서의 라우팅

Info

Publication number: KR20060045065A
Application number: KR1020050026940A
Authority: KR
Inventors: 큐이아오 리안; 유 첸; 젱 장
Original assignee: 마이크로소프트 코포레이션
Priority date: 2004-03-31
Filing date: 2005-03-31
Publication date: 2006-05-16
Anticipated expiration: 2025-03-31
Also published as: CN1681257B; KR101120724B1; AU2005201191A1; JP4806203B2; MXPA05003462A; CN1681257A; AU2005201191B2; RU2005109223A; RU2408064C2; CA2503360A1; ATE488083T1; EP1583326A2; EP1583326B1; US20050223102A1; BRPI0501178A; JP2005323346A; US7730207B2; EP1583326A3; DE602005024636D1

Abstract

P2P 네트워크에서의 라우팅이 설명되어 있다. 일 실시예에서, 본 방법은 P2P 네트워크 내의 복수의 노드들 중 한 노드에서 P2P 네트워크 내의 다른 노드에 의한 P2P 네트워크 내의 회원자격 상의 변화에 대한 표시를 수신하는 단계를 포함한다. 이 변화를 기술한 보고서가 방송된다. 이 보고서는 위의 한 노드에 포함된 라우팅 테이블 내에서 참조된 각 노드에 의한 수신용이다.

P2P, 네트워크, 노드, 라우팅 테이블, 방송

Description

Ｐ2Ｐ 네트워크에서의 라우팅{ROUTING IN PEER-TO-PEER NETWORKS}

도 1은 P2P 네트워크를 제공하도록 구성된 환경을 도시한 예시적인 일 실시예의 도면.

도 2는 P2P 네트워크의 복수의 노드들이 좀더 상세하게 도시된 예시적인 일 실시예에서의 시스템의 도면.

도 3은 일차원적인 논리 키 공간 내에서 시스템 내의 복수의 노드들에 대한 복수의 소프트 상태 라우팅 테이블들의 스냅샷(snapshot)을 도시한 예시적인 일 실시예의 도면.

도 4는 식별자를 회전시키고 다른 링을 만듦으로써 주어진 블록에 대한 소프트 상태 라우팅 테이블을 사용한 라우팅 내의 항목들을 만드는 것을 도시한 예시적인 일 실시예의 도면.

도 5는 도 4와 관련하여 설명된 링들의 소프트 상태 라우팅 테이블을 사용한 라우팅을 도시한 예시적인 일 실시예의 도면.

도 6은 소프트 상태 라우팅 테이블의 일부와 소프트 상태 라우팅 테이블 내의 일 항목의 생성을 도시한 예시적인 일 실시예의 도면.

도 7은 재귀적인 블룸 필터를 도시한 예시적인 일 실시예의 도면.

도 8은 한 노드가, P2P 네트워크 내의 회원자격의 변화를 표시하는, 자신이 수신한 이벤트들을 설명하는 보고서를 형성하고 통신하는 예시적인 일 실시예의 한 프로시저를 보여주는 흐름도.

도 9는 노드의 이용가능한 자원들에 기초해 라우팅 테이블 크기가 동적으로 결정되는 예시적인 일 실시예의 프로시저를 보여주는 흐름도.

도 10은 P2P 네트워크 내에 노드를 제공하는 데 사용될 수 있는 컴퓨팅 장치의 예를 도시한 도면.

동일한 도면 부호가 명세서 및 도면에서 유사한 구성요소 및 특징들을 지칭하는 것으로 사용되었다.

<도면의 주요 부분에 대한 부호의 설명>

100: 시스템 102(a): 클라이언트

104(1)-104(B): 컴퓨팅 장치 106: 네트워크

108: DHT 110(1)-110(8): 존(zone)

112: 리프세트 114: 핑거 테이블

본 발명은 일반적으로 P2P(Peer-to-peer) 네트워크에 관련된 것이고, 특히, P2P 네트워크에서의 라우팅에 관련된 것이다.

P2P 네트워크는, 적응성(adaptation), 자기-조직성(self-organization), 부하의 균형도(load-balancing), 오류-내구성(fault-tolerance), 저비용(low cost), 높은 이용도(high availability), 범용성(scalability), 대규모의 자원 풀을 제공할 수 있는 능력과 같은 다양한 바람직한 특징들로 인해 점점 더 인기를 얻고 있는 중이다. P2P 네트워크는, 예컨대 개체들(peers)이 P2P 네트워크에서 다운로드할 수 있는 것으로 표시된 노래들을 다른 개체로부터 다운로드하는 것과 같이 대량의 데이터를 공유하는 대중적인 방식으로서 출현했다.

그러나, P2P 네트워크를 제공하는 데 사용되는 전통적인 아키텍처는 시스템을 형성하는 회원들, 즉 노드들(nodes)의 증대하는 숫자를 제대로 감당하지 못해 왔다. 예컨대, P2P 네트워크의 현재의 예는 400만명 이상의 사용자들에게 230만 번 이상의 다운로드를 제공해왔다. 그러나, 회원들의 숫자는 계속적으로 증가할 것으로 예측되어, 초거대 시스템의 경우 1조 이상의 노드들을 갖게 될 수 있다. 따라서, 현재의 아키텍처가 대규모의 노드들을 가진 시스템을 감당할 수 있다 하더라도, 현재의 아키텍처는 초거대 시스템에서 사용되기에는 여전히 부족할 수 있다.

P2P 네트워크에서 특정 자원(resource)을 찾아내기 위해서는, 예컨대 네트워크의 각 노드가 특정 자원, 예컨대 특정 아이템의 데이터를 가진 노드를 찾기 위해서, 네트워크 내의 하나 이상의 다른 노드들을 참조(reference)할 수 있다. 따라서, 특정의 아이템을 찾기 전까지 일련의 "홉(hop)"이 한 노드에서 다른 노드로 라우팅되는 요청으로서 사용될 수 있다. 홉의 횟수가 증가할수록, 노드들의 하드웨어 및 소프트웨어 자원 사용 및 시스템의 네트워크 자원 사용도 증가한다. 따라서, 홉의 횟수 증가로 인해, 특정 아이템을 찾는데 사용되는 시간이 증가할 뿐만 아니라 시스템의 자원도 비효율적으로 사용되는 결과를 가져온다.

따라서, P2P 네트워크에서 라우팅의 향상에 대한 지속적인 요구가 있다.

P2P 네트워크에서 메시지들(예컨대, 특정 자원에 대한 요청 및 이 요청에 대한 응답)을 라우팅하는 데 라우팅 테이블을 사용하는 라우팅이 설명된다. 라우팅 테이블은 P2P 네트워크에서 노드들을 참조하는 라우팅 테이블 내의 항목들을 업데이트하라는 방송(broadcasting)에 의해 업데이트될 수 있다. 일 실시예에서, 각 노드의 라우팅 테이블들을 유지하는 데 사용되는 유지 버짓(maintenance budget)은, 각 세그먼트에 대한 조밀한 라우팅 테이블 항목들(entries)을 만듦으로써, P2P 네트워크의 자원 공간의 다중 세그먼트들에 분배된다. 따라서, 라우팅 테이블을 유지하기 위한 전반적인 유지 버짓은 감소될 수 있고, 이에 의해 P2P 네트워크의 하드웨어, 소프트웨어 및 네트워크 자원이 자유로워져 바람직한 메시지 라우팅 기능을 제공한다.

일 실시예에서, 본 방법은 P2P 네트워크 내의 복수의 노드들 중 하나에서 P2P 네트워크의 다른 노드에 의한 P2P 네트워크의 회원자격의 변화를 나타내는 표시(indication)를 수신하는 단계를 포함한다. 상기 변화를 설명하는 보고서(report)가 방송된다. 상기 보고서는 한 노드에 포함된 라우팅 테이블에서 참조되는 각 노드에 의한 수신을 위한 것이다.

다른 실시예에서, 본 방법은 P2P 네트워크 내에 포함되려하는 노드에 대해 P2P 네트워크 내에서의 통신을 위해 상기 노드의 이용가능한 자원을 결정하는 단계를 포함한다. 상기 결정에 기초해, 라우팅 테이블은 P2P 네트워크 내에서의 요청 들을 라우팅하기 위해 상기 노드에 형성된다.

또 다른 실시예에서, 본 방법은, P2P 네트워크 내의 복수의 노드들 중 하나에 의한 재귀적인 블룸 필터(iterative bloom filter)를 사용하여 라우팅 테이블 내의 항목들을 설명하는 데이터를 압축하는 단계를 포함한다. 상기 압축된 데이터를 다른 상기 노드로 통신하기 위해 통신이 형성된다.

개 관(Overview)

P2P 네트워크 내의 라우팅이 설명된다. 상술한 바와 같이, 적은 수의 홉은 더 적은 수의 전달하는 노드들(forwarding nodes)이 사용될 수 있어서 전체 대역폭(bandwidth)의 소비가 감소되므로 바람직하다. 작으면서도 조절가능한 노드별 유지 버짓을 갖고도, 조절가능 초거대 시스템(즉, 1조의 노드들) 내에서 자원을 찾는 데 사용되는 홉의 숫자를 감소시킨 라우팅 기술이 설명된다.

P2P 네트워크 내의 다른 노드들을 참조하기 위해 노드는 라우팅 테이블들을 사용한다. 그러나, 라우팅 테이블의 전통적인 유지 방법은 초거대 시스템에서 용인할 수 없을 정도의 대량의 하드웨어, 소프트웨어 및 네트워크 자원의 사용을 필요로 할 수 있다. 예컨대, 전통적인 유지 기술은, 테이블에 의해 참조된 노드가 시스템 내에서 현재 이용가능한지 여부를 판정해달라는 요청과 이에 대한 응답을 송신함으로써 라우팅 테이블 내의 항목들이 업데이트되도록 탐지(probing)하는 방법을 사용하였다. 각 탐지에 사용되는 하드웨어, 소프트웨어 및 네트워크 자원의 양이 비교적 작다 할지라도, 이 자원 사용이 전체 시스템에 대해 취합 (aggregation)될 때, 그 양은 상당한 정도가 될 수 있다. 따라서, 초거대 시스템은 이러한 전통적인 유지 기술을 사용할 때 기능 상의 상당한 손실로 고통받을 수 있다. 본 명세서에 설명된 유지 기술에서는 각 세그먼트에 대해 밀집한 라우팅 테이블 항목들을 건설함으로써 라이팅 테이블을 유지하는 데에 사용되는 유지 버짓을 P2P 네트워크의 자원 공간의 다중 세그먼트들에 분산시킬 수 있다. 따라서, 라우팅 테이블을 유지하기 위한 전체적인 유지 버짓을 감소시킬 수 있고, 이에 의해 P2P 네트워크의 하드웨어, 소프트웨어, 및 네트워크 자원이 자유로워져 라우팅 요청 및 이 요청에 대한 응답의 소망되는 기능을 제공할 수 있다. 이런 방식으로, 라우팅 테이블은, 용인될 수 없는 수준의 유지 버짓없이도, 초거대 시스템 내에서 더 적은 홉들을 사용하여 유지될 수 있다. 밀집한 라우팅 항목들과 라우팅 테이블의 유지에 대한 더 자세한 설명은 도 3과 관련하여 제공되어 있다.

추가적으로, 상용화된 종전 O(logN) 라우팅 기술이 현재의 시스템에서는 성공적이지만, 종전 기술에서 현재 허용되는 작은 베이스(즉, O(log _b N)에서의 변수 b)는 초거대 시스템에 대해서는 더 이상 충분하지 못하다. 예컨대, 시스템 내의 노드들의 수 "N"가 1조일 때, 전통적인 O(logN) 라우팅 기술을 사용할 때 최악의 홉 카운트는 20이다(b가 4이고 항목이 약 60개일 때). "라우팅 성능"항목에서 더 자세하게 기술될 일 실시예에서, 여기에 기술된 라우팅 기술을 채택한 1조의 노도를 가진 시스템의 평균 라우팅은 5.5 홉으로 감소된다.

예시적인 환경

도 1은 P2P 네트워크를 제공하도록 구성된 시스템(100)을 보여주는 예시적인 일 실시예의 도면이다. 시스템(100)은 복수의 클라이언트(102(a))를 포함하는데, 여기서, "a"는 1부터 "A"까지 중 임의의 정수이며, 위 시스템은 네트워크(106) 상에서 복수의 컴퓨팅 장치들(104(1)-104(B))과 통신가능하게 연결되어 있다. 이 실시예에서, 복수의 클라이언트들(102(a))과 복수의 컴퓨팅 장치들(104(1)-104(B)) 각각은 네트워크(106) 내의 노드를 나타낸다. 노드는, 데이터를 다른 노드들에 공급하는 재분배 지점 및/또는 데이터의 목적지 및/또는 소스(source)인 말단 지점과 같이 데이터를 전송하기 위한 연결 지점으로 생각될 수 있다.

복수의 클라이언트들(102(a))과 복수의 컴퓨팅 장치들(104(1)-104(B))은 다양한 방식으로 구성될 수 있다. 예컨대, 클라이언트들(102(a))과 컴퓨팅 장치들(104(1)-104(B))은 네트워크(106) 상에서 통신할 수 있는 컴퓨터들, 예컨대 무선 전화[예컨대, 컴퓨팅 장치(104(1))], 타블릿 컴퓨터[예컨대, 컴퓨팅 장치(104(2))], 노트북 컴퓨터[예컨대, 컴퓨팅 장치(104(3))], 데스크탑 컴퓨터[예컨대, 컴퓨팅 장치(104(4))], 서버들[예컨대, 컴퓨팅 장치들(104(5)-104(6))], 메인프레임 컴퓨터[예컨대, 컴퓨팅 장치(104(B))] 및 이동국, 엔터테인먼트 기기들, 셋톱 박스 등등과 같은 다른 컴퓨팅 장치들로 구성될 수 있다. 컴퓨팅 장치의 예에 대한 추가의 논의는 도 10과 관련하여 제공되어 있다. 따라서, 복수의 클라이언트들(102(a)) 및 컴퓨팅 장치들(104(1)-104(B))은 상당한 크기의 메모리와 프로세서 자원을 가진 풀 자원 장치들(full resource devices)(예컨대, 개인용 컴퓨터, 하드 디스크가 장착된 텔레비전 녹화기)부터 제한된 메모리 및/또는 프로세싱 자원들을 가진 저-자원 장치들까지 다 가능하다. 또한, 클라이언트들(102(a))은 해당 클라이언트를 작동하는 개인 및/또는 단체와 관계가 있을 수 있다. 달리 말하면, 클라이언트(102(a))는 사용자 및/또는 기계를 포함하는 논리적 클라이언트(logical client)를 가리킬 수 있다.

네트워크(106)는 P2P 네트워크로 구성된다. P2P 네트워크는 네트워크(106)의 노드들이 각 노드들, 즉 복수의 클라이언트들(102(a)) 및 복수의 컴퓨팅 장치들(104(1)-104(B))에 위치한 공유 자원을 액세스할 수 있게 한다. 과거부터 공지되고 사용되어온 P2P 네트워크의 예에는 다음과 같은 것들이 포함된다.

ㆍ "프리넷: 분산된 익명의 정보 기억장치 및 재생 시스템(I. Clarke, B. Wiley, O. Sanberg, and T. Hong, "Freenet: A Distributed Anonymous Information Storage and Retrieval System", Proc . Int . Workshop on Design Issues in Anonymity and Unobservability, Springer Verlag, LNSC 2009, 2001)에 기술된 프리넷.

ㆍ"코드, 인터넷 애플리케이션을 위한 범용성있는 P2P 룩업 서비스"(I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, H. Balakrishnan, "Chord A Scalable Peer-to-peer Lookup Service for Internet Application, " Proc . ACM SIGCOMM'01, San Diego, California, USA, 2001)에 기술된 코드(Chord)

ㆍ"범용성있는 콘텐츠-어드레싱가능한 네트워크"(S. Ratnasamy, P.Francis, M. Handley, R. Karp and S. Shenker, "A Scalable Content-Addressable Network," Proc. ACM SIGCOMM'01, San Diego, CAlifornia, USA, 2001)에 기술된 캔(CAN)

ㆍ "패스트리: 대규모 P2P 시스템을 위한 범용적이며 탈중앙화된 오브젝트 배치 및 라우팅"(A. Rowstron and P. Druschel, "Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems," IFIP /ACM Int. Conf . Distributed Systems Platforms ( Middleware ), 2001)에 기술된 패스트리(Pastry)

ㆍ"타페스트리: 오류-내구적인 광역 배치 및 라우팅을 위한 기반구조"(B.Y.Zhao, J.Kubiatowicz, and A.D. Joseph, "Tapestry: An Infrastructure for Falut-tolerant Wide-Area Location and Routing," Technical Report No. UCB / CSD -01-1141, Univ. of California, Berkeley)에 기술된 타페스트리(Tapestry)

P2P 네트워크는 중복성(redundancy) 및 오류 내구성(fault tolerance)과 같은 다양한 특징들을 제공할 수 있다. 예컨대, P2P 네트워크에 저장된 데이터는 데이터가 P2P 네트워크의 노드들에 의해 복제됨에 따라 점차 퍼질 수 있다. 따라서, 데이터는 P2P 네트워크에서 상당히 중복될 수 있어서, 결국 데이터의 신뢰도 및 이용가능성의 증진으로 이어질 수 있다.

데이터, 프로세싱 사이클, 데이터 저장소 등과 같은 다양한 자원들은 P2P 네트워크를 사용해 교환될 수 있다. 따라서, P2P 네트워크는 복수의 클라이언트들(102(a))과 복수의 컴퓨팅 장치들(104(1)-104(B))의 집합적인 파워를 레버리지(leverage)하기 위해서 사용될 수 있다. P2P는 각 노드, 즉 "회원"이 다른 회원과 직접 또는/및 중간에 존재하는 컴퓨팅 장치를 통해 통신할 수 있는 통신 모델이다. 클라이언트들(102(a)) 및 컴퓨팅 장치들(104(1)-104(B))은 요청 및 응답과 같은 메 시지들을 사용해 네트워크(106)를 통해 통신할 수 있다. 7개의 컴퓨팅 장치들(104(1)-104(B))이 도시되어 있지만, 매우 다양한 컴퓨팅 장치들이 본 환경에서 사용될 수 있다. 추가적으로, P2P 네트워크에서 복수의 클라이언트들(102(a)) 또한 "개체들(peers)", 즉 회원들로 구성될 수 있다.

네트워크(106)는, 클라이언트들(102(a))과 복수의 컴퓨팅 장치들(104(1)-104(B)) 간에 메시지들을 라우팅하기 위한 인터페이스 역할을 하는 분산된 해시 테이블(DHT; distributed hash table)(108)을 포함한다. DHT(108)는 (키, 값) 쌍들을 저장하는 해시 테이블 데이터 구조의 분산된 버전으로 생각될 수 있다. 예컨대, 키(key)는 파일명에 대응할 수 있고, 값(value)은 파일의 콘텐츠에 대응할 수 있다. 네트워크(106)의 각 개체, 즉 컴퓨팅 장치들(104(1)-104(B))은 (키, 값) 쌍들의 부분집합을 저장한다. 따라서, DHT(108)는 대응 키를 책임지는 노드를 찾는데 사용된다. 다른 말로, DHT(108)는 클라이언트들(102(a))과 복수의 컴퓨팅 장치들(104(1)-104(B)) 사이에 메시지들을 라우팅하기 위하여 노드에 키를 맵핑(mapping)한다. 파일 공유 서비스, 기록 저장 서비스(예, 웹 기록보관소), 데이터베이스, 네이밍 시스템(naming system), 서비스 발견(service discovery), 애플리케어션-레이어 멀티캐스트(application-layer multicast), 이벤트 공지(event notification), 채팅 서비스, 랑데부-기반 통신(rendezvous-based communication), 쿼리 및 인덱싱(query and indexing), 데이터 출판/구독 등과 같은 다양한 서비스가 DHT(108)" 상(on-top)에" 건설될 수 있다.

DHT(108)는 복수의 컴퓨팅 장치들(104(1)-104(B))에 의해 제공되는 자원들을 복수의 존(zone)(110(1)-110(8)), 즉 "버킷들(buckets)"로 파티션화한다. 복수의 존(110(1)-110(8)) 각각은 시스템(100) 내에서 공유되는 총 자원들의 일부로 생각될 수 있다. 예컨대, 상술한 바와 같이, DHT(108)는 자원들을 키들과 연관시킨다. DHT(108)를 사용해 복수의 존(110(1)-110(8)) 중 특정 존을 찾기 위해서 키는 해싱(hashing)된다. 복수의 존(110(1)-110(8))은 다양한 방식으로 제공된다. 예컨대, 존(110(1))은 도 1에서 컴퓨팅 장치(104(1))에 의해 제공되는 것으로 도시되어 있다. 마찬가지로, 존들(110(2), 110(3), 110(4), 110(5), 110(6))은 각각 컴퓨팅 장치들(104(2), 104(3), 104(4), 104(5), 110(6))에 의해 제공된다. 추가적으로, 한 컴퓨팅 장치가 둘 이상의 존을 제공할 수 있는데, 도 1에서 존들(110(7), 110(8))은 컴퓨팅 장치(104(B))에 의해 제공되는 것으로 도시되어 있다.

DHT(108)는 리프세트(leafset)(112), 핑거 테이블(finger table)(114) 및 소프트-상태 라우팅 테이블(SSRT; soft-state routing table)(116)을 포함하는 3층 구조를 채택하고 있는 것으로 도시되어 있다. 리프세트(112)는 키 공간의 완전성(integrity)을 보장하기 위해서 사용된다. 예컨대, 리프세트(112)가 일관된 해싱을 사용해서, 상술한 바와 같이, 자원 공간과 노드의 응답 공간을 하나 또는 그 이상의 복수의 존들(110(1)-110(8))로 분할할 수 있다.

핑거 테이블(114), 즉 중간층은 O(logN) 프리픽스 라우팅 알고리즘(prefix routing algorithm)[여기서, "N"은 노드의 총수]과 같이 프리픽스 기반 라우팅 알고리즘(prefix-based routing algorithm)을 구현하는 데 사용될 수 있다. 예컨대, 각 노드는 시스템(100) 내의 다른 노드들을 포인팅하는 항목들, 즉 핑거들을 갖는 핑거 테이블(114)를 포함할 수 있다. 핑거 테이블(114)의 항목들은 시스템(100) 내의 일련의 "다른" 노드들을 참조하기 위하여 로그 함수를 따를 수 있다. 핑거 테이블(114)의 항목들은, 대응 노드의 ID의 비트를 플립핑(flipping)한 후 결과 키를 보관하는 노드를 포인팅함으로써 구성될 수 있다. 정기적인 비콘(beacon)은 리프세트(112)와 핑거 테이블(114) 항목들을, 예컨대 탐지 메커니즘(probing mechanism)을 사용하여, 업데이트하기 위하여 채택될 수 있다. 따라서, 리프세트(112)와 핑거 테이블(114)은 DHT(108)에 O(logN) 실행을 제공할 수 있다.

SSRT(116)는 이동율(churn rate), μ이 작은 때(예컨대, 노드가 시스템(110)에 가입하거나 탈퇴할 때)에는 시스템(110)의 회원들인 노드들의 목록을 제공한다. 따라서, SSRT(116)는 원하는 노드를 신속하게 찾는 데 사용될 수 있다. SSRT(116)의 구성은 충분한 중복성(redundancy)을 가진 방송 그래프를 형성하는 시스템(110) 내의 모든 노드들의 핑거들을 사용함으로써 달성될 수 있다. 본 설명의 편의를 위해, 방송은 한 그래프 내에서의 데이터의 전파를 의미하는데, 이 그래프에서 최초발신자(originator)라 불리는 한 정점(vertex)이 그래프의 가장자리를 따라 일련의 콜(call)들을 배치함으로써 데이터를 다른 모든 정점들에 분배한다. 일단 데이터를 입수하면, 다른 정점들은 최초발신자의 메시지 배포를 돕는다. 방송 그래프는 방송이 "[log₂n]" 시간 단위 내에 이루어질 수 있는 그래프이다.

도 2는 P2P 네트워크의 복수의 노드들(202(x))[여기서, "x"는 일부터 "X"까지의 임의의 정수가 될 수 있음]이 더 상세하게 도시된 예시적인 실시예에서의 시 스템(200)의 도면이다. 노드(202(x))는 도 1의 시스템 내의 노드들, 예컨대 컴퓨팅 장치들(104(1)-104(H)) 및 클라이언트들(102(a))과 동일하거나 상이한 것일 수 있다. 노드(202(x))는 리프세트(112(x)), 핑거 테이블(114(x)) 및 SSRT(116(x))를 가진 대응 DHT(108(x))를 포함하는 것으로 도시되어 있는데, 이들 테이블들은 도 1의 DHT(108), 리프세트(112), 핑거 테이블(114) 및 SSRT(116)의 버전임을 표시하도록 도면 부호가 매겨졌다.

노드(202(x))는 각 노드로부터 수신한 이벤트들(회원자격의 변화, 예컨대 "가입" 또는 "탈퇴" 이벤트를 기술함)의 수신을 통해 리프세트(112(x))의 다른 노드들의 회원자격을 감시할 수 있다. 노드(202(x))가 회원자격의 변화를 알 때, 노드(202(x))는 가입 또는 탈퇴 이벤트과 같은 복수의 이벤트들(204(c)) 중 하나 이상을 보고서(206(x))에 삽입한다. 보고서(206(x))는 핑거 테이블(114(x))에 의해 기술된 노드(202(x))의 각 핑거를 통해 미리결정된 방송 간격에 맞춰 평행하게 방송된다. 복수의 노드들(202(x)) 각각은, 노드가 알게 된 이벤트들을 기술하는 보고서들을 만들고 시스템(200) 내의 다른 노드들로부터 발산된 이벤트들을 기술함으로써 동일한 동작을 수행할 수 있다. 따라서, 높은 전파 속도로(평균 O(logN)으로) 신뢰할 수 있는 방송을 전달하기에 충분한 중복성(O(logN))을 제공하는 발산 알고리즘(flooding algorithm)이 제공된다.

유지 비용을 조절하기 위하여, 할당이 초과된 경우 이벤트들은 큐(queue)(208(x))에서 내부적으로 버퍼될 수 있다. 추가적으로, DHT(108)는 하나 이상의 규칙을 사용함으로써 견고성(robustness)을 상황에 맞춰 다룰 수 있다. 예 컨대, SSRT(116(x))의 항목들이 높은 품질인 것[예컨대, SSRT(116(x)) 항목들이 도 1의 시스템(100)의 현재 회원자격을 기술하는 경우]을 보장하기 위해서, 특정 노드가 시스템(100)을 탈퇴한 것을 기술하는 "탈퇴" 이벤트는 다른 이벤트들, 예컨대 "가입" 이벤트들 전에 발송된다. 이런 방식으로, 시스템(100)은 다른 노드가 시스템(100)에 가입할 때 통지받는 것보다 앞서 시스템을 탈퇴한 특정 노드들의 자원이 더이상 이용가능하지 않게 된 때를 알게 되고, 이것은 시스템(100)의 평형을 재구축하는데 사용된다. 시스템의 평형에 대한 더 상세한 설명은 "적응성" 항목에서 찾을 수 있다.

정상 상태에서, 유효한 SSRT(116(x)) 항목들의 수, M은 다음 방정식을 풀어서 알아낼 수 있다.

Q = 4μ·E·M· logN

여기서, E는 이벤트의 크기다. 일 실시예에서, 이벤트는 34 바이트이고, 이벤트의 유형, 시각소인(timestamp), IP 주소 및 노드 ID를 기술하는 데이터를 포함한다. 방정식의 상수 "4"는 각 세션에 대한 가입 및 탈퇴뿐만 아니라 전송 및 수신에 대한 대역폭 비용(bandwidth cost)을 의미한다.

따라서, DHT(108(x))는 시간 도메인(예컨대, 보고서에 이벤트들을 차례로 넣는 것)과 공간 도메인(예컨대, Olog₂ N 노드들과의 상호작용하는 것) 양쪽에서 실시되는 취합(aggregation)을 광범위하게 사용할 수 있다. 또한, 회원자격 상의 변화를 통신하기 위하여 방송을 사용함으로써, 전체 클러스터(full cluster)가 유지된 다 할지라도, 통신할 이벤트가 없는 때에는, 네트워크의 트래픽이 거의 없어서 네트워크 효율성이 증대된다.

DHT

이 항목에서는, 초거대 규모를 가진 시스템에 대한 동적인 환경에서 DHT(108) 구조를 사용하는 것이 설명될 것이다. DHT(108)는 매우 큰 b를 가진 O(log_b N) 라우팅의 효과를 제공하는데, 각 항목의 능동적인 탐지(probing)를 필요로 하지 않는다. 전술한 바와 같이, DHT(108) 내의 항목들을 업데이트하기 위하여 프로브(probe)를 전송하거나 프로브에 응답하기 위한 대역폭의 소비가 작을 수 있지만, 도 1의 시스템(100)의 전체 혹은 일부에 대해 수집될 때에는 거대한 양의 프로브를 전송하고 그에 응답하는 것은 상당한 오버헤드가 될 수 있다. 추가적으로, 탐지 빈도를 감소시키는 것은 바람직하지 않을 수 있는데, 왜냐하면 놓친 것(miss)은, 예컨대 시스템 내의 원하는 자원을 찾아내는 데 있어서 무작위적인 IP 홉(hop)으로 이어질 수 있는 것과 같이 감지하기에는 비용이 많이 들기 때문이다.

다음의 실시예에서, N이 1조일 때, b = 4,000 프리픽스-기반 라우팅의 성능(performance)이 복제된다. 다음 설명의 편의를 위해, 방송 버짓 Q는 5kb/s이고, 이동율 μ는 1/(3시간)이라고 가정하자. 이 변수들로는, 4K 크기의 전체 클러스터(full cluster)가 DHT(108)을 사용해서 만들어질 수 있다. 다양한 방송 버짓과 이동율이 본 명세서에 개시된 라우팅 기술들에 의해 처리될 수 있다.

상기 성능(performance)을 전달하는 데 사용할 수 있는 라우팅 기술의 예는 두 구성요소들을 포함한다. 첫 번째 구성요소는, 방송 버짓의 1/4, 즉 Q/4를 사용해서 전체 자원 공간 대신에 하위 영역에 대한 크로스바(crossbar)의 건설을 포함한다. 두 번째 구성요소는 라우팅시 그와 같은 크로스바들을 네 개 사용하여 40비트들을 회전(revolving)시키는 메커니즘의 고안이다. 각 구성요소들은 차례로 다음 항목에서 설명된다.

하위 영역 크로스바의 건설

전체 자원 공간 T은 소정의 정수 "i"에 대해서 t/2 ⁱ 영역들로 분할될 수 있다. 예컨대, 상기 분할은, 평균적으로 각 영역 M이 약 천 개의 노드들을 포함하는 것일 수 있다. 임의의 노드 x에 대해, 그 노드가 속하는 영역을 R(x)라고, 영역 R의 다른 노드들을 포인팅하는 R에 속하는 x의 핑거들의 하위집합을 beamers (x)라고 하자. 따라서, 동일한 R을 공유하는 모든 노드들에 있어서, 대응하는 비머(beamer)들이 집합적으로 R을 커버하는 방송 그래프를 형성하고, 상당한 수준의 중복성을 갖는다. 비머들을 통해 DHT(108) 내에서 동일한 방송 프로토콜을 적용함으로써, 각 노드는 대응 영역 R을 커버하는 대응 SSRT를 공급받는다. 대역폭 비용은 다음과 같이 계산될 수 있다: 4μ·E·M· logM . 따라서, E=34B이고 μ=1/(3시간)인 현재의 실시예에 있어서, 대역폭 비용은 약 1 kb/s이다. 이런 방식으로, 첫번 째 구성요소는 충족되는데, 즉 Q/4 미만을 사용하여 하나의 홉을 갖고 가장 짧은 10 베이스-2 핑거 범위(the shortest 10 base-2 finger range)를 해결할 수 있는 클러스터를 만든다. 본질적으로, 하위-영역 클러스터는 1000개의 노드들의 리프세 트로 간주될 수 있다. 예컨대, 룩업 키(lookup key)가 이 범위에 속하면, 하나의 홉으로도 원하는 자원을 찾기에 충분할 것이다.

R은 다양한 방식으로 예측될 수 있다. 예컨대, 각 노드가 평균 존 크기

를 그에 대응하는 리프세트의 정보를 사용해 계산할 수 있다. 이후, 다음 노드는 영역 R의 예측치를

보다 10 비트만큼 더 큰 것이라고 할 수 있다. 상술한 바와 같이, 비머들은 영역 예측치 내의 핑거들이다. 그 경계는 이 영역 예측치 바깥에 있는 노드들에 의해 전송된 가입-이벤트들을 거부함으로써 한층 강화될 수 있다. 따라서, 노드의 SSRT는 이웃한 영역들로부터의 항목들에 의해 오염되지 않을 것이다.

도 3은 P2P 네트워크에서 구현된 시스템 내의 몇몇 노드들의 SSRT들을 기술하는 일차원 논리 키 공간(300)을 도시한 도면이다. 일차원 논리 공간 키(300)의 제1 영역(302)은 도 2의 복수의 노드들(202(x)) 중 제1 노드의 SSRT에 의해 기술될 수 있고, 일차원 논리 공간 키(300)의 제2 영역(304)은 도 2의 복수의 노드들(202(x)) 중 제2 노드의 SSRT에 의해 기술될 수 있으며, 나머지도 유사하다. 도 3에 도시된 점선들은 이론적인 영역 분할선이다. 따라서, 도 3에 도시된 바와 같이, SSRT는 대응 노드의 대응 영역을 커버하는 항목들에 의해 구성되어 있다.

다중 블록들의 해독(Resolving Multiple Blocks)

다음 설명의 편의를 위해, 각 노드의 ID 길이는 160 비트이고, ID에서 10 비트의 세그먼트를 "블록"이라고 지칭하기로 하자. 상술한 바와 같이, ID는 P2P 네 트워크의 노드의 주소로 볼 수 있다. b=4K인 프리픽스-기반 라우팅(prefix-based routing)은 한 번에 한 블록씩 검색하여 해독(resolving)한다. 1조 개의 노드들을 가진 시스템에 대한 현재의 예에서는, 해독되어야 할 총 4개의 10비트 블록들이 있다.

목적지가 가장 짧은 10개의 핑거들에 의해 커버되는 영역 내에 있게 될 때까지 핑거들을 통해 한번에 주소(address)의 1 비트를 매칭하면서 라우팅은 영역의 클러스터 내에게 계속된다. 목적지가 영역 내에 있게 된 때, SSRT는 한 홉(hop)에 자원으로의 액세스를 전달한다. 효과적으로, 이 최종 열 개의 핑거들은 이 액세스를 확장하기 위하여 2¹⁰개의 SSRT 항목들로 팽창될 수 있다. 달리 표현하면, 다른 선도적인 블록들 내에 있는 핑거들은 동일한 프리픽스-범위(prefix-range) 내에 포함되기 위한 SSRT 항목들로 팽창된다.

일조 개의 노드들의 시스템에서, 각 노드는 평균적으로 40 핑거들을 갖는다. 설명의 목적상, Ring₀은 베이스 링을 표시하는 데 사용된다. 추가적으로, 설명의 목적상, 노드의 ID는 도 4에 도시된 바와 같이 알파벳 순서대로 명명된 10 비트의 블록들로 분할되어 있다. 10 비트의 블록들이 도시되어 있지만, 블록들은 서로 다른 비트 수를 사용할 수 있다. 예컨대, 각 블록은 2 이상의 비트들을 갖거나, 5 이상의 비트를 갖거나, 기타 등등이 가능하다.

예컨대, 도 4의 블록 A(402)를 보자. 블록 A(402)의 SSRT 항목들을 만들기 위해서, ID(404)는 우측으로 회전하여 새로운 ID_A(406)을 얻는데, 이 ID_A(406)에서 는 블록 A(402')가 4번째 블록이다. 각 노드는 ID_A(406)을 사용해서 Ring_A라고 명명된 다른 링에 가입한다. Ring_A은 자신의 리프세트와 O(log₂ N) 핑거들을 갖고 Ring₀과 동일한 방식으로 만들어진다. 그 위에, 하위-영역 클러스터 알고리즘(sub-region cluster algorithm)이 유사하게 적용된다. 따라서, 노드는 SSRT_A(408)을 1K 크기의 Ring_A에서 획득하고, 그 항목들은 그 ID_A가 앞선 세 개의 블록들(즉, N|O|P)을 그 노드와 공유하지만 4번째 블록, 즉 블록 A(402')에서는 상이한 노드들이다.

ID(404)와 ID_A(406)의 관계는 이 4 개의 노드들이 ID의 최후의 3개 블록들을 공유하지만 Ring₀ 내의 블록 A에서는 다른 것들이라는 것을 의미한다. 따라서, 블록 A 내의 10 베이스-2 핑거들을 2¹⁰ SSRT 항목들로 확장하는 일은 달성된다. 유사한 배열이 블록들 B, C, 및 D[예컨대, SSRT_D(410)]에 대해서 수행될 수 있다. 각 링은 대응하는 블록을 커버하는 SSRT 항목들을 만들 수 있게 한다.

다 합하면, 4 개의 링들이 이 예에서 만들어졌다. 설명 목적상, 블록 A에 대한 SSRT 항목들은 SSRT_A라고 칭하고, 블록 B에 대한 SSRT 항목들은 SSRT_B라고 칭하고, 다른 것들도 이와 동일한 방식으로 칭하기로 하자. 최후의 SSRT는 네 개의 작은 SSRT들(예컨대, SSRT_A, SSRT_B, SSRT_C, SSRT_D)의 조합이고, 크기가 약 4K이다. DHT를 사용한 라우팅은, 중간의 홉들(intermediate hops)을 통해 진행하기 위해서, 비트들이 최대한 공격적으로 매칭되면서 진행될 수 있다.

라우팅

도 5는 도 1의 시스템(100)의 각 노드에 위치한 SSRT 테이블을 사용해서 수행된 라우팅을 보여주는 예시적인 실시예의 도면이다. 룩업 키(502)를 SSRT(504)와 연관하여 사용해서 특정 주소(506)를 가진 노드를 찾아낸다. 앞의 섹션에서 설명한 바와 같이, SSRT(504)는 다양한 레벨의 유사성을 가진 주소들을 가진 노드들을 참조하는 항목들을 포함한다.

SSRT(504)는, 예컨대, 각각 SSRT(516, 518, 520, 522) 항목들을 가진 복수의 부분들(508, 510, 512, 514)로 구성될 수 있다. 제1 부분(508)은 블록 A(524)에 기술될 수 있는 상이한 주소들을 가진 각 노드들을 참조하는 SSRT_A(516) 항목을 포함한다. 제2 부분(510)은 주소 블록 A에 대해 상호 매칭하는 주소들을 가진 각 노드들을 참조하는 SSRT_B(518) 항목을 포함한다. 그러나, 제2 부분은 블록 B(524) 내에 기술될 수 있는 서로 다른 각각의 주소를 가진 각 노드를 참조한다. 다른 말로 하면, SSRT_B(518) 내의 모든 항목들은 상호 매칭하지만 상이한 블록 B를 갖는 블록 A를 갖는다. 유사하게, 제3 부분(512)은 각각이 상호 매칭하는 각각 주소 블록들 A 및 B를 갖는 각 노드를 참조하는 SSRT_C(520) 항목을 포함한다. 그러나, 제3 부분(512)은 블록 C에 기술될 수 있는 상이한 주소들 각각을 갖는 각 노드를 참조한다. 따라서, SSRT_C(520) 내의 모든 항목들은 각각 매칭 블록들 A 및 B를 갖지만 상이한 블록 C를 갖는다. 마지막으로, 제4 부분(514)은, 매칭 주소 블록들 A, B, 및 C를 갖는 각 노드를 참조하는 SSRT_D(522) 항목을 갖는다. 그러나, 제4 부분(514)은 블록 D에 기술될 수 있는 상이한 주소들 중 하나를 가진 각 노드를 참조한다. 따라서, SSRT_D(518) 내의 모든 항목들은 매칭 블록들 A, B 및 C를 갖지만, 상이한 블록 D를 가지며, 블록 D는 개별 노드에 대한 "하나의 홉" 라우팅을 제공한다. 이런 방식으로, 개별 노드에 의해 유지되는 각 SSRT는 P2P 네트워크에서 효율적인 라우팅을 제공하는 유사한 주소를 가진 노드들의 상이한 계층들을 기술하는 방법을 제공할 수 있다.

예컨대, SSRT(504)는 룩업 키(502)를 사용해서 SSRT(504)를 검사함으로써 특정 자원을 발견하는데 사용될 수 있다. 룩업 키(502)의 블록 A(524), 블록 B(526), 블록 C(528) 및 블록 D(530)가 SSRT(504) 테이블의 SSRT_D(522) 항목들에 기술된 대응 블록들 A, B, C 및 D와 매칭한다면, SSRT(504)는 요청을 대응 소스 노드(506)로 바로, 즉 하나의 홉(hop)만에 라우팅하는데 사용될 수 있다.

다른 예에서, 룩업 키(502)의 블록 A(524)와 블록 B(526)는 SSRT(504)의 블록 A와 블록 B와는 매칭하지만, 블록 C와는 매칭하지 않으면, 매칭 블록들 A, B 및 C를 가진 노드들을 기술하는 대응 노드로 호핑(hopping)하기 위해 룩업 키(502)는 SSRT_C(520)과 비교된다. 그러면, 대응 노드는 한 홉만에 소스 노드(506)를 발견하는데 사용될 수 있는 제4 부분을 가진 SSRT를 가질 수 있다. 룩업 키가 SSRT(504) 내의 항목들과 어느 정도 매칭하는지에 기초해 제1 및 제2 부분들(508, 510)을 사용해 유사한 검색(lookup)들이 수행될 수 있다. 따라서, 각 노드는 초거대 시스템 에서 노드를 신속하게 발견하는 데 사용될 수 있는 SSRT를 포함한다.

도 6은 도 1의 시스템(100)의 각 노드에 위치한 도 6의 SSRT 테이블을 사용함으로써 수행되는 라우팅을 보여주는 예시적인 실시예(600)의 도면이다. 도 4와 관련해 상술된 바와 같이, SSRT는, 각 노드의 식별자를 회전시킴으로써 P2P 네트워크 내의 각 노드의 위치를 참조하는 복수의 링들로부터 구성될 수 있다. 예컨대, ring_A(602)은 복수의 항목들을 가진 SSRT_A(604)를 가질 수 있다. 이 예에서, SSRT_A(604) 내의 각 항목은 서로 매칭하는 3개의 초기 블록들(도 6에는 "N|O|P"로 도시됨)을 갖는다. SSRT_A(604) 내의 제4 블록 "A"는 이 제4 블록에 대한 대응 주소를 가진 시스템 내의 각 위치를 기술한다. SSRT_A(604)을 만들기 위해서, ID, 즉 P2P 네트워크 내의 노드의 주소에 대한 항목을 "회전시킨다." 예컨대, 주소(606) "110|…N|O|P|"는 회전하여(608) ID(610) "N|O|P|110|…"를 형성하고, ID(610) "N|O|P|110|…"는 SSRT_A(604) 내에 포함된다. 이런 방식으로, 초거대 시스템 내의 원하는 자원을 찾아내기 위해 수행되는 홉의 양을 감소시킨 SSRT가 형성될 수 있다.

라우팅 성능

상술한 실시예들에서, 상위 블록에서의 라우팅 분해도(routing resolution)는, 가장 짧은 10개의 핑거들에 의해 커버되는 범위 내에 목적지가 있는 경우를 제외하고는, 각 블록마다 하나의 홉보다 약간 더 많이 걸린다. 예컨대, 도 5에 도시 된 1조 개의 노드 시스템을 고려해보자. 노드 x가 검색(lookup)을 개시할 때, 목적지 키 k는 무작위 값이다. addr_A(k)가 k의 A 블록(즉, 10개의 가장 중요한 비트)이라고 하면, addr_A(k)는 2¹⁰의 가능한 값들을 갖는다. 전술한 바와 같이, 1K SSRT_A(x) 항목들은 그 ID들이 ID(x)의 최후 세 개의 블록들을 공유하지만 블록 A에서는 상이한 노드들이다. 노드 ID가 무작위이기 때문에, SSRT_A(x)의 항목들의 "A" 블록들도 addr_A(k)의 2¹⁰의 가능한 값들을 포함한다.

상술한 문제점은 완전한 자원 공간을 약 천 개의 빈(bin)들로 분할하는 것과 같고, x뿐만 아니라 SSRT_A(x) 내의 노드들도 이 빈들에 무작위적으로 떨어지는 볼(ball)인 셈이다. 도 6에 도시된 바와 같이, addr_A(k)에 의해 인덱싱된 빈이 비어있지 않는 경우에만 블록 A 내의 검색(lookup)은 일 홉(hop) 내에서 해결될 수 있다. 유사하게, 공간이 512 개의 빈들로 분할되고 addr_A(k)는 비어있지 않은 빈을 포인팅하면, 9개의 가장 중요한 비트들은 SSRT_A(x)를 사용함으로써 해독될 수 있으며, 다른 노드의 SSRT_B를 사용하기 시작하기 전에 핑거 테이블로부터 평범한 "핑거"를 사용하는 것을 해독하기 위하여 하나의 홉을 남겨둔다.

P _i 가 적어도 i 비트들은 해독될 수 있는 가능성이라고 하자. P _b 를 계산하기 위해서, 공간은 2 ⁱ 빈들로 분할되어 있고, 2¹⁰ 볼들이 이 공간으로 떨어진다. 따라 서, 1-P _i 는 (1- 2 ^-i )¹⁰²⁴이고, 다른 말로, 빈 하나를 무작위로 뽑았을 때 볼이 전혀 없을 확률은 e ^{-2^(10-i)} , 따라서 P _i =1-e ^{-2^(10-i)}

이제, 홉들의 기대치가 계산될 수 있다.

에 대해서, p _i =P _i - P _i+1 라고 하자(여기서, p _i 는 SSRT_A를 사용해 i 비트들이 해독될 확률임). 그러면, 다음과 같은 것이 관찰된다.

따라서, 블록 A(또는 1 홉이 걸리는 최후의 블록을 제외한 다른 임의의 블록)를 해독하는 데에는 평균 1.52 홉이 걸린다. 따라서, N이 1조라면, 평균 라우팅은 약 5.5 홉이 걸린다.

성능은 1 조의 노드 시스템과 관련하여 기술되었다. 일반적으로, 평균 성능은 ([log₁₀₂₄ N-1])·1.52 + 1에 의해 구속된다. 따라서, N=256,000이면, 최악의 경우의 성능은 높은 확률로 2.52인 것이 아니라 2.02이다. 예컨대, SSRT_B가 1.02 홉의 예측치로 8비트를 간단히 해독할 수 있다. 이 지점에서, 남은 열 개의 핑거들 로 만들어진 전체 크로스바(full crossbar)는 최후의 홉에 전달될 것이다. 유사하게, N = 256백만이면, 성능은 높은 확률로 3.54 홉에 의해 구속된다.

유지 비용 및 견고성(robustness)

전술한 바와 같이, 이동율(churn rate) μ=1/(3시간)이고 1 링 내에 1000 개의 노드의 영역 클러스터를 유지하는 총 비용은 약 1 kb/s다. 4 개의 링의 SSRT를 유지하는 데에는 위의 비용의 약 4 배가 사용된다. 다른 비용들은 리프세트 회원들과 모든 4개의 링들의 핑거들에 대한 정기적인 탐지를 포함하는데, 비교적 적은 비용에 해당한다. 이에 의하면 1조 노드 시스템에서의 평균 라우팅 성능은 5.5 홉이 된다는 점에 유의하자.

적응성(adaptation)

상술한 예시적인 라우팅 기술이 대역폭 버짓 Q에 맞는 때조차 대역폭 소비의 피크(peak)들이 여전히 존재할 수 있다. 따라서, 도 2와 관련해 상술한 바와 같이, 추가의 대역폭이 이용가능해질 때까지 이벤트들은 도 2의 큐(queue)(208(x)) 내에 내부적으로 버퍼될 수 있다. 다양한 다른 적응성 기술들 또한 시스템 내에서 동적인 변화가 발생할 때 SSRT의 품질을 조절하기 위하여 채택될 수 있다. 예컨대, 적응성 기술은 스트레스 하에서는 라우팅 성능을 적절하게 낮췄다가 뒤에 정상적인 라우팅 성능으로 되돌리는 데 사용될 수 있다.

이러한 적응성 기술의 첫번째 예는 높은 이동율 μ를 제시하는데, 높은 이동율 μ는 또한 시스템을 정상 조건 하에서 평형 상태로 안정화시킬 것이다. 이런 적응성 기술은 방송 트래픽을 적응성있게 조절하기 위하여 보고서 내에 포함된 중 복되는 이벤트들을 "잘라내는 것(pruning)"을 포함하고 있다. 최종 결과로, 잘 유지되는 높은 품질의 SSRT이 된다. 중복되는 이벤트들이 포함되지 않은 보고서의 구성에 대한 더 자세한 논의는 도 8과 관련된 부분에서 찾을 수 있다.

이러한 적응성 기술의 두번째 예는 첫번째 적응성 기술을 기초로 이루어지는데, 여기서 SSRT는 도 3에 도시된 바와 같이 전체 자원 공간의 일부를 커버하는 크로스바가 된다. 첫번째 및 두번째 적응성 기술들을 결합하여 각 노드 내에 포함된 SSRT를 구체화함으로써, 각 노드의 SSRT를 결합할 때 이 두 최적화의 결합에 의해 다층 구조가 얻어진다. 예컨대, 제1층은 전체 자원 공간으로 확장되고, 제2층은 국지적인 크로스바를 제공하는 2층 구조가 채택될 수 있다. 다른 예에서는, 도 5와 관련하여 설명된 바와 같이 4층 구조가 채택될 수 있다. 이러한 하이브리드적인 접근법을 가지고, 큰 수의 노드를 가진 시스템에서, O(l)에 도달하면서도 대역폭 버짓 Q는 초과하지 않을 수 있다.

일 실시예에서, "eSSRT"가 "온라인" 상태인 SSRT 항목들의 부분집합을 가리킨다고 하자. eSSRT의 크기를 희생시키더라도 그 상태가 가능한 한 정확한 것을 보장하기 위해서 필터링이 사용될 수 있다. 즉, 낮은 오류-긍정 비율(low false-poistive rate)이 더 큰 수의 오류-부정 항목(false-negative entries)을 갖고 달성된다. 여기서, 가정은 "미스(miss)"가 일반적으로 "히트(hit)"보다 댓가가 더 크다는 것이다.

이 목적을 달성하기 위하여, 필터링은 다양한 규칙을 사용할 수 있는데, 예를 들면 다음과 같다:

1. 낮은 오류-긍정 비율을 보장하기 위하여 더 높은 우선권을 갖고 "탈퇴" 이벤트들이 전송된다.

2. 이벤트가 상태를 변경하지 않는다면, 전파되지 않는다.

두번째 규칙은 상태 기계(state machine)를 사용함으로써 실현될 수 있다. 예컨대, 이벤트의 유형이 상태 기계에 의해 표시된 현재의 상태와 일치한다면, 시각소인(timestamp)은 현재 상태에 대한 변화없이 업데이트된다; 그리고 다른 경우에는 그 상태는 무효가 된다. 후자의 경우, "has-sent" 필드 역시 무효가 된다. 예컨대, "온라인" 상태이면서 "has-sent"가 거짓인 항목이 "탈퇴" 이벤트를 수신하면 상태는 "오프라인"으로 변경되고 "has-sent"는 참인 것으로 설정된다. 다른 말로, 이 특정 이벤트는 더 이상 전파될 필요가 없다. 따라서, 중복되는 메시지는 이벤트들의 버퍼링의 도움으로 잘라내진다.

이런 기술들을 사용함으로써, 시스템은 자동적으로 평형 상태에 도달할 것인데, 왜냐하면 버퍼링된 이벤트들이 장래에 수신할 이런 이벤트들을 잘라내는 데 도움을 줄 것이기 때문이다. 이동율 μ가 높을 때에는, "과잉" 참가 이벤트들이 버퍼링되면서 탈퇴 이벤트들은 적응 초기에 대역폭의 할당분의 대부분을 차지할 수 있다. 시간이 좀 지난 시점에서, 버퍼링된 참가 이벤트들은, 수신되었을 때, 탈퇴 이벤트들을 상쇄할 것이고, 그에 의해 참가 이벤트들을 배포하는데 지분을 할애할 수 있다. 이동율 μ가 정상 상태가 될 때, 참가 및 탈퇴 이벤트들을 전송하는 데 사용되는 네트워크의 지분과 노드 자원은 결국 대략 동일해질 것이다. 따라서, 이동율이 높을수록, 이 접근법은 P2P 네트워크 내에서 네트워크 자원의 전체적인 사 용을 감소하는 데 더 효과적이다. 둘째, 버퍼링된 이벤트들은 대역폭 할당분이 다시 이용가능해질 때 배포되어서, 시스템이 이벤트의 폭풍들(즉, 시간 상의 특정 지점에서 통신되는 복수의 이벤트들로 인한 회원 자격상의 급격한 변화)을 견디어내고, 후에 신속하게 정상 성능 수준으로 되돌아가게 할 것이다. 이런 방식으로, 견고한 라우팅 기술이 제공된다.

재조정-설정(Set-Reconciliation)

대규모 라우팅 테이블을 사용하는 임의의 DHT 라우팅 기술에 대한 현실적인 문제 하나는 "재조정-설정"이라고 지칭될 수 있는 리턴하는 개체(peer)의 라우팅 테이블(들)의 흐름(current)을 어떻게 끄집어낼 것인가하는 점이다. 예컨대, 상술한 라우팅 기술들에서는, P2P 네트워크에 가입할 때 최신의 SSRT를 얻는 방법에 문제가 생기는데, 이는 리턴하는 노드의 리프세트와 핑거 테이블이 이 노드가 P2P 네트워크에 가입할 때마다 새롭게 구성될 수 있기 때문이다.

예컨대, SSRT는 백그라운드에서 안정적인 저장장치 내에서 존속할 수 있고, 그 회원자격 목록(예컨대, 다른 모든 노드들의 <ID, IP> 쌍을 가진 항목들)은 노드가 자신의 과거 역사(past history)를 통해 알게된 것들을 모두 포함한다. 시스템에게 전적으로 새로운 노드는 최초 가입시에 SSRT를 복사할 수 있다. 따라서, 시스템이 충분한 기간동안 동작해 왔다면, SSRT 내의 회원자격 리스트 세트는 전체 시스템에서 대체로 일관될 것이다.

그러나, 탈퇴한 노드가 P2P 네트워크로 돌아올 때(예컨대, P2P 네트워크에 가입할 때), 가입하는 노드는 자신의 대응 SSRT에 기록된 개체들의 상태를 알지 못 할 수 있다. 따라서, 가입하는 노드는 SSRT 내의 각 항목들을 오프라인 상태로 리셋한 뒤, P2P 네트워크 내의 현존하는 하나 이상의 노드들로부터 정보를 얻으려 노력할 것이다. 예컨대, 두 노드들의 SSRT들이 서로 동기화된 경우, 현존하는 노드는 자신의 SSRT로부터 다른 개체들의 상태를 나타내는 벡터(vector)의 각 비트를 가진 벡터를 전송할 수 있다. 이동율 μ이 높고 온라인 항목의 수가 작을 때에는 eSSRT를 복사하는 것이 실용적이다. 예컨대, 128kb/s 링크에 대해 각각 32 바이트씩 가진 약 4K의 항목들을 전송하는 데에는 약 8초가 걸릴 수 있다. 그러나, 이동율 μ이 낮거나 초거대 시스템 내에서는 이는 그다지 견고한 해결책은 아닐 수 있다.

SSRT 항목들을 기술하는 데이터의 보다 효율적인 통신을 위해서, 블룸 필터(bloom filter)를 이용해 데이터를 압축하여 SSRT를 업데이트하는 데 사용되는 대역폭의 양을 감소시킬 수 있다. 이런 방식으로, 효율적인 통신이 초거대 시스템에 제공될 수 있다. 블룸 필터는 복수의 해시 함수들(multiple hash functions)을 단일 어레이의 비트들로 이용함으로써 대규모 세트 내의 회원자격을 검사하는 데 사용되는 확률 알고리즘(probabilistic algorithm)이다. 예컨대, 공간/대역폭이 문제이고 작은 오류는 허용될 수 있는 때에 블룸 필터는 효과적으로 동작할 수 있다.

예컨대, 블룸 필터에서 n개의 아이템의 리스트는 m 비트들로, 즉 b=아이템 당 m/n(여기서, "b"는 "필터 파라미터"를 의미함)로 압축될 수 있다. 각 아이템마다, 그 범위가 [0..m]에 속하는 한 세트의 해시 함수들이 적용되고, m-비트 벡터 내에 대응 비트를 설정한다. 블룸 필터의 부작용은 오류-긍정(false-positive)이 발생할 수 있다는 점, 즉 수신 노드가 원본 리스트 바깥에 있는 몇몇 구성요소들을 잘못 포함할 수 있다는 점이다. 그 확률은 (0.6185) ^b 로 나타내지고, m=8n이면 확률은 0.02를 약간 넘는다.

한 아이템의 크기가 E 바이트이면, nE 바이트의 목록을 전송하는 대신에, b=8이고 필터의 크기는 8n 비트(즉, n 바이트)이고, 압축율은 1/E이 된다. 예컨대, 노드의 ID 및 IP 주소를 전달하면서 시각소인(timestamp)을 전달하지 않기 위해서는 E는 약 32 바이트가 될 수 있고, 1/32 압축율이라는 상당한 결과를 얻는다. 일 실시예에서, 최초 프로토콜은 블룸 필터를 온라인이 아닌 항목들에 대해 적용한다. 그러면, 블룸 필터의 오류-긍정(false-positive)은 수신하는 쪽에서 온라인 노드들의 2%가 오프라인으로 기록된다는 것을 의미한다.

"재귀적인 블룸 필터"(iterative bloom filter)를 사용함으로써 또 다른 실시예에서는 정확성이 더 개선될 수 있다. 예컨대, 전송 노드, 즉 수신 노드의 SSRT를 업데이트하기 위한 데이터를 전송하는 노드는 온라인 노드들 P(PRESENT)의 필터를 더 작은 필터 파라미터 a로 연산한다. 다음으로, 전송 노드는 오류 긍정 노드들의 세트 A⊂P를 식별하고, 필터 파라미터 b를 가진 보충 필터를 적용한다. 그러면, 양 필터는 수신 노드, 즉 SSRT를 업데이트하기 위한 데이터를 요청한 노드에 전송된다. 정성적으로 말하면, 몇몇 온라인 노드를 놓치기 때문에 이 방법은 보수적인 접근법이 되어버린다. 통계적으로 말하면, 블룸 필터의 오차율은 필터 파라미터에 의해서만 결정되기 때문에, 이러한 항목들의 수는 단일-수준의 블룸 필 터와 동일하다.

재귀적인 블룸 필터(700)의 예가 도 7에 도시되어 있다. 재귀적인 블룸 필터(700)는 세 개의 블룸 필터들의 세트(702(1)-702(3))를 포함하는 것으로 도시되어 있다. P(704)와 A(706)는 각 필터의 오류-긍정 항목들의 집합이다.

이 재귀적인 접근법이 대역폭을 절약하게 하는지 여부를 계산하기 위하여, N _a 및 N _p 가 각각 오프라인 노드들 및 온라인 노드들의 수라고 가정하자. 단일-수준의 b 비트 블룸 필터의 경우, 총 메시지 크기는 bN _a 비트이다. 이 재귀적인 방법의 최초 필터는 메시지 크기 aN _p 를 갖는다. A의 크기, 즉 오류-긍정 항목들의 수는 N _a (0.6185)^a이다. 따라서, 보충 필터는 N _a b(0.6185)^a의 크기를 갖고, 결과적으로 총 메시지의 크기 S는 다음과 같이 나타낼 수 있다.

최소 메시지 크기를 구하면, 다음과 같다:

"a"는 음수가 아닌 정수이기 때문에, 상기 방정식은 다음과 같은 두 경우로 나누어 볼 수 있다:

상기 실시예에서, 필터 파라미터 b는 8일 때, 그리고 Na가 Np의 25%보다 작은 경우에, 단일-수준 블룸 필터는 사용될 수 있다. 이에 대한 의사-코드(pseudo-code)의 예는 다음과 같다.

상기 재조정 설정 의사 코드(set reconciliation pseudo-code)에서, b는 미리 정의되어 있고(예컨대, 8), 수신 단(end)에서의 SSRT의 항목들은 오프 라인 상 태로 모두 시작한다.

예시적인 프로시저 (Exemplary Procedures)

다음의 설명은 상술한 시스템 및 장치들을 사용해서 구현될 수 있는 SSRT를 업데이트하고 구성하는 방법에 관한 것이다. 각 프로시저의 양상은 하드웨어, 펌웨어 또는 소프트웨어 및 이들의 조합의 형태로 구현될 수 있다. 프로시저들은, 하나 이상의 장치에 의해 수행되는 동작들을 구체화한 블록들의 세트로 도시되어 있다. 프로시저는, 각 블록들에 의해 수행되는 동작의 순서를 반드시 따르는 것은 아니다.

도 8은, 자신이 수신한 이벤트들(P2P 네트워크에서의 회원자격의 변화를 표시하는 것임)을 기술하는 보고서를 노드가 형성하고 통신하는 실시예에서의 프로시저(800)를 도시한 흐름도이다. 블록(802)에서, 노드는 P2P 네트워크에서의 회원자격의 변화를 표시하는 이벤트를 수신한다. 예컨대, 제1 노드는 무작위 식별자 ID를 선택하고 검색(lookup)을 실행해서 이 식별자가 P2P 네트워크에 이미 포함되어 있는지 판정한다. 이 식별자는 P2P 네트워크 내에서의 제1 노드의 주소로 간주될 수 있다. 식별자 ID가 P2P 네트워크 내에 이미 포함되어 있지 않으면, 제1 노드는 ID'라고 지칭된 차상위 식별자를 가진 "후계자(successor)" 노드를 찾아서, 후계자 노드에게 제1 노드가 P2P 네트워크에 가입하였음을 공지한다. 공지는 "가입" 이벤트를 후계자 노드에게 통신함으로써 수행될 수 있다.

결정 블록(804)에서, 이 노드가 이 이벤트를 전에 수신한 적이 있는지 여부에 대한 판정이 이루어진다. 이 노드가 이 이벤트를 전에 수신한 적이 있으면(블 록 804), 이 이벤트는 삭제된다(블록 806). 따라서, 이 예에서, 이벤트들은 이 노드에 의해 1회보다 많이 통신되지 않는다. 다른 예에서, P2P 네트워크를 구현한 시스템에서 원하는 중복성을 제공하기 위하여 미리결정된 횟수만큼 이벤트들을 통신하도록 임계치가 사용될 수 있다.

이 노드가 이 이벤트를 전에 수신하지 않았으면(블록 804), 결정 블록(808)에서 이벤트들을 다른 노드들에게 통신하는 데 있어서 임계치가 초과되었는지 여부에 대한 판정이 이루어진다. 임계치가 초과되지 않았으면(블록 808), 이벤트는 큐(queue)에 추가된다(블록 810). 이런 방식으로, 프로시저(800)는 주어진 시간 동안 이벤트들을 미리결정된 횟수 이하로 통신함으로써, P2P 네트워크 내의 유지 비용을 조절할 수 있다.

임계치가 초과되지 않았으면(블록 808) 또는 이벤트가 큐에 추가된 이후(블록 810), 결정 블록(812)에서 미리결정된 방송 시간에 도달했는지 여부가 판정된다. 예컨대, P2P 네트워크의 각 노드는 상이한 미리결정된 간격만큼 자신이 수신한 이벤트들을 방송하여 이벤트를 통신하는데 사용되는 네트워크 자원상의 비용을 골고루 "분산시킬 수 있다." 미리결정된 방송 시간에 도달하지 않았다면(블록 812), 프로시저(800)는 블록(802)으로 돌아가서 추가 이벤트가 있다면 이를 수신한다.

해당 노드에 대한 미리 결정된 방송 시간이 도달할 때(블록 812), 이벤트들을 포함하는 보고서가 형성된다. 예컨대, 해당 노드는 복수의 노드들로부터 수신한 이벤트들을 취합(aggregation)하여 이벤트들을 지닌 단일 통신문이 전송되게 할 수 있다. 이벤트는 블록(810)에서 저장된 이벤트들의 큐로부터 및/또는 당해 노드에서 수신한 이벤트들을 저장하는데 사용되어온 다른 저장 장치로부터 얻을 수 있다.

블록(816)에서, 보고서가 어디로 방송되어야 하는지를 결정하기 위하여 라우팅 테이블을 조사한다. 블록(818)에서, 보고서는 라우팅 테이블에서 참조된 각 노드들로 나란히 방송된다. 각 블록들(816, 818)에서의 라우팅 테이블 및 방송은 다양한 방식으로 실시될 수 있다. 예컨대, 라우팅 테이블은, 복수의 다른 노드들을 기술하는 로그 함수를 사용한 도 1의 핑거 테이블(114)과 같이 구성될 수 있다. 상술한 바와 같이, 도 1의 핑거 테이블(114)의 "핑거들"은 보고서가 노드들이 존재하는 영역 내의 노드들로 배포되는데 충분한 중복성을 가진 방송 그래프를 형성한다. 다른 실시예에서는, 핑거들이 이 영역 밖에 있는 다른 노드들에게 보고서를 방송하기 위하여 사용될 수도 있다.

보고서를 수신한 각 노드는 프로시저(800)를 수행해서 이 보고서에 기록된 이벤트들이 각 후계 노드들에 포함된 핑거 테이블들에서 참조된 노드들로 방송될 수 있다. 따라서, 이벤트들은 각 핑거 테이블 내의 핑거들에 의해 정의된 방송 그래프를 통해 원조 노드(originating node)로부터 다른 모든 노드들로 이벤트들을 통신함으로써 전파된다. 이벤트들이 다른 노드들에서 수신되자마자, 다른 노드들은 이벤트들을 배포하는 데 있어서 원조 노드를 돕는다.

그러면, 각 노드들은 자신이 포함하는 각각의 SSRT들을 업데이트하기 위하여 보고서에 기술된 이벤트들을 사용할 수 있다. 따라서, 소망하는 데이터를 찾는데 필요한 홉(hop)의 수를 감소시키고 라우팅 테이블을 유지하는 데 사용되는 네트워크 대역폭의 양을 감소시키기 위하여, SSRT를 사용할 수 있다.

도 9는 노드의 이용가능한 자원에 기초해 라우팅 테이블의 크기가 동적으로 결정되는 실시예에서의 프로시저(900)를 도시한 흐름도이다. P2P 네트워크의 몇몇 실시예에서는, 네트워크의 각 노드는 동일한 하드웨어, 소프트웨어, 및/또는 네트워크 자원에 액세스하지 못할 수가 있다. 예컨대, 도 1에 도시된 바와 같이, 컴퓨팅 장치(104(B))는 상당한 양의 하드웨어 및 소프트웨어 자원을 가질 수 있는데 반해, 컴퓨팅 장치(104(1))는 휴대용으로 설계되었기 때문에 제한된 하드웨어 및 소프트웨어 자원을 가질 수 있다. 추가적으로, 한 노드는 다이얼 업 접속(dial-up connection)을 사용하는 데 비해 다른 노드는 DSL(digital subscriber line)을 사용하는 경우와 같이 노드들마다 네트워크로의 접속을 위한 대역폭이 상이할 수 있다. 노드가 이용가능한 자원에 적합한 방식으로 P2P 네트워크 내에서 라우팅을 하기 위해, 노드의 이용가능한 자원에 기초해 각 노드의 라우팅 테이블을 동적으로 구성할 수 있다.

예컨대, 블록(902)에서 한 노드가 P2P 네트워크에 가입한다. 예컨대, 이 노드는 상술한 바와 같이 무작위 식별자를 생성할 수 있다. 블록(904)에서, 이 노드는 이용가능한 자신의 하드웨어, 소프트웨어, 및/또는 네트워크 자원들을 결정한다. 예컨대, 이 노드는 자신의 처리 및 메모리 용량을 결정하는 소프트웨어 모듈을 실행할 수 있다. 이 소프트웨어 모듈은, 실행될 때, 공지된 네트워크 목적지로부터의 응답을 수신하는데 걸리는 시간을 판정하는 것 등의 방법으로 네트워크 접 속의 이용가능한 대역폭을 또한 결정할 수 있다.

블록(906)에서, 이 노드의 라우팅 테이블은 자원 결정(블록 904)에 기초해 구성된다. 일례에서, 이 소프트웨어 모듈은 네트워크 접속 대역폭에 기초해 라우팅 테이블 내에 포함될 수 있는 항목의 양을 기술하는 다양한 임계치를 저장할 수 있다. 예컨대, 이 노드가 다이얼 업 접속을 통해 접속되어 있다면, 라우팅 테이블은 노드가 케이블 모뎀을 통해 접속된 경우보다 더 적은 항목들을 가지도록 구성될 수 있다.

다른 예에서, 이 소프트웨어 모듈은 이 노드의 이용가능한 하드웨어, 소프트웨어 및/또는 네트워크 자원을 네트워크 내의 다른 노드들 비교하여, P2P 네트워크 내의 다른 라우팅 테이블 크기들과 일치하는 라우팅 테이블 크기를 도출한다. 예컨대, 이 노드가 P2P 네트워크에 가입할 때, 이 노드는 상술한 바와 같이 후계자 노드를 찾아낼 수 있다. 찾아냈을 때, 이 노드는 후계자 노드에게 후계자 노드의 하드웨어, 소프트웨어, 및/또는 네트워크 자원에 기초해 구성된 라우팅 테이블의 크기를 판정해달라고 문의한다. 그러면, 이 노드는 자신의 이용가능한 자원들을 후계자 노드의 것들과 비교하고, 이 비교에 기초해 다수의 항목을 가지도록 라우팅 테이블을 구성한다. 예컨대, 이 노드가 후계자 노드보다 더 많은 자원을 가진 경우, 이 노드는 후계자 노드의 라우팅 테이블보다 더 많은 항목을 갖도록 라우팅 테이블을 구성할 수 있다. 적절하게 자원들을 비교하고 라우팅 테이블을 구성하는 데에는 다양한 알고리즘이 사용될 수 있다.

추가적으로, 라우팅 테이블은 이 노드가 P2P 네트워크의 회원일 때 정기적으 로 재구성될 수 있다. 예컨대, 이 노드가 자신이 P2P 네트워크의 회원인 동안에 자원의 정기적인 판정을 할 수 있다. 따라서, 라우팅 테이블은 P2P 네트워크 내의 대응 노드의 이용가능한 자원에 기초해 구성될 수 있으며, 노드가 P2P 네트워크의 회원인 동안에는 노드의 현재 이용가능한 자원을 반영하도록 유지될 수 있다.

예시적인 컴퓨팅 장치

본 명세서에 기술된 다양한 구성요소들과 기능은 많은 컴퓨터들로 구현할 수 있다. 도 10은, P2P 네트워크 내의 노드를 제공하는 데 적합한 도면 부호 1002로 표시된 컴퓨터를 포함하여, 컴퓨터 환경(1000)의 구성요소들의 대표적인 예를 보여준다. 컴퓨터(1002)는 도 1의 복수의 클라이언트들(102(a))과 복수의 컴퓨팅 장치들(104(1)-104(B))와 동일할 수도 있고, 상이할 수 있다. 도 10에 도시된 구성요소들은 오직 예시적인 것이며, 본 발명의 기능상의 범위를 제한하기 위한 것이 아니다; 본 발명은 도 10에 도시된 특징들에 반드시 의존하는 것은 아니다.

일반적으로, 다양하고 상이한 범용 및 특정 컴퓨팅 시스템 구성이 사용될 수 있다. 본 발명에 사용하기에 적합할 수 있는 잘 알려진 컴퓨팅 시스템, 환경 및/또는 구성은, 개인용 컴퓨터, 서버 컴퓨터, 핸드헬드(hand-held), 또는 랩탑 장치들, 멀티프로세서 시스템, 마이크로프로세서-기반 시스템(microprocessor-based systems), 셋톱 박스(set top boxes), 프로그램가능한 소비자 전자제품, 네트워크 PC들, 네트워크-레디 장치들(network-ready devices), 미니컴퓨터, 메인프레임 컴퓨터, 상기 시스템 또는 장치들 중 임의의 것을 포함하는 분산형 컴퓨터 환경 등을 포함하고 이에 국한되지 않는다.

컴퓨터의 기능은, 컴퓨터에 의해 실행되는 소프트웨어 컴포넌트와 같은 컴퓨터로 실행가능한 명령어에 의해 많은 경우 구체화된다. 일반적으로, 소프트웨어 컴포넌트들은, 특정 작업을 수행하거나 특정 추상 데이터 유형을 구현하는 루틴, 프로그램, 오브젝트, 컴포넌트, 데이터 구조 등을 포함한다. 작업들은 통신 네트워크를 통해 연결된 원격 프로세싱 장치들에 의해 수행될 수도 있다. 분산 컴퓨팅 환경에서는, 소프트웨어 컴포넌트들은 로컬 및 원격 컴퓨터 저장장치들에 위치할 수 있다.

명령어 및/또는 소프트웨어 컴포넌트들은 상이한 시기에 컴퓨터의 일부이거나 컴퓨터에 의해 판독될 수 있는 다양한 컴퓨터 판독가능한 매체에 저장된다. 프로그램들은, 예컨대 플로피 디스크, CD-ROM, DVD 또는 변조된 신호와 같은 몇몇 유형의 통신 매체에 통상 분배된다. 이곳으로부터, 프로그램들은 컴퓨터의 제2 메모리에 인스톨되거나 로드된다. 실행시, 프로그램들은 컴퓨터의 주요 전자 메모리(primary electronic memory) 내로 적어도 부분적으로 로드된다.

설명의 편의상, 운영 체제와 같은 프로그램들과 다른 실행가능한 프로그램 컴포넌트들은 본 명세서에서는 별도의 블록들로 도시되지만, 이와 같은 프로그램 및 컴포넌트들은 다양한 시기에 컴퓨터의 상이한 저장 장치에 존재하며, 컴퓨터의 데이터 프로세서에 의해 실시된다는 점에 유의하자.

도 10과 관련하여, 컴퓨터(1002)의 컴포넌트들은 프로세싱 유닛(1004), 시스템 메모리(1006) 및 시스템 버스(1008)를 포함하지만 이에 한정되지는 않으며, 시스템 버스(1008)는 시스템 메모리를 프로세싱 유닛(1004)에 연결하는 것을 포함하 여 다양한 시스템 컴포넌트들을 연결한다. 시스템(1008)은 메모리 버스 또는 메모리 제어기, 주변 버스(peripheral bus), 및 다양한 버스 아키텍처 중 임의의 것을 사용하는 로컬 버스를 포함하는 몇몇 유형의 버스 구조 중 임의의 것일 수 있다.

컴퓨터(1002)는 통상 다양한 컴퓨터 판독가능한 매체를 포함한다. 컴퓨터 판독가능한 매체는 컴퓨터(1002)에 의해 액세스할 수 있는 이용가능한 임의의 매체일 수 있으며, 휘발성 및 비휘발성 매체, 착탈식 및 비착탈식 매체를 포함한다. 예컨대, 컴퓨터 판독가능한 매체는 컴퓨터 저장장치 및 통신 매체를 포함할 수 있으며 이에 한정되지 않는다. "컴퓨터 저장장치"는, 컴퓨터 판독가능한 명령어, 데이터 구조, 프로그램 모듈 또는 다른 데이터와 같은 정보의 저장을 위한 임의의 방법 또는 기술로 구현된 휘발성 및 비휘발성, 착탈식 및 비착탈식 매체들을 포함한다. 컴퓨터 저장장치는 RAM, ROM, EEPROM, 플래시 메모리 또는 다른 메모리 기술, CD-ROM, DVD 또는 다른 광학 디스크 저장장치, 자기 카세트, 자기 테이프, 자기 디스크 저장장치 또는 다른 자기 저장장치, 또는 원하는 정보를 저장하는 데 사용될 수 있고 컴퓨터(1002)로 액세스할 수 있는 임의의 다른 매체를 포함하며, 이에 한정되는 것은 아니다. 통신 매체는 통상 컴퓨터 판독가능한 명령어, 데이터 구조, 프로그램 모듈 또는 반송파(carrier waver)와 같은 변조된 데이터 신호 또는 다른 전송 메커니즘 상의 다른 데이터를 구체화하고, 임의의 정보 전달 매체를 포함한다. "변조된 데이터 신호"라는 용어는 신호 내의 정보를 부호화하기 위한 방식으로 하나 이상의 그 특성이 설정되거나 변경된 신호를 의미한다. 예컨대, 통신 매체는 유선 네트워크 또는 직통-유선 접속(direct-wired connection) 및 음향, RF, 적외선 및 다른 무선 매체와 같은 무선 매체를 포함하며, 이에 한정되지는 않는다. 상기 예 중 임의의 것들의 조합 역시 컴퓨터 판독가능 매체의 범위에 포함된다.

시스템 메모리(1006)는 ROM(1010) 및 RAM(1012)와 같은 휘발성 및/또는 비휘발성 메모리의 형태인 컴퓨터 저장 매체를 포함한다. 컴퓨터를 켤 때와 같은 경우에 컴퓨터(1002) 내의 구성요소들 간에 정보를 전달하는 것을 돕는 기본 루틴을 포함하는 기본적인 입/출력 시스템(BIOS)(1014)은 ROM(1010)에 통상 저장된다. RAM(1012)은 프로세싱 유닛(1004)에 직접 액세스할 수 있는/있거나 프로세싱 유닛(1004)에 의해 현재 연산되는 데이터 및/또는 소프트웨어 컴포넌트들을 포함한다. 예컨대, 도 10은 운영 체제(1016), 애플리케이션(1018), 소프트웨어 컴포넌트(102) 및 프로그램 데이터(1022)를 도시하고 있는데, 이에 한정되는 것은 아니다.

또한, 컴퓨터(1002)는 다른 착탈식/비착탈식, 휘발성/비휘발성 컴퓨터 저장 매체를 포함할 수 있다. 예를 들면(오직 예시적인 목적을 위한 것임), 도 10은 비착탈식, 비휘발성 자기 매체로 읽고 쓰는 하드 디스크 드라이브(1024), 착탈식, 비휘발성 자기 디스크(1028)에 읽고 쓰는 자기 디스크 드라이브(1026), 그리고 CD ROM이나 다른 광학 매체와 같은 착탈식, 비휘발성 광학 디스크(1032)에 읽고 쓰는 광학 디스크 드라이브(1030)를 도시하고 있다. 이 예시적인 운영 체제에서 사용될 수 있는 다른 착탈식/비착탈식, 휘발성/비휘발성 컴퓨터 저장 매체는 자기 테이프 카세트, 플래시 메모리 카드, DVD, 디지털 비디오 테이프, 고체 상태 RAM(solid state RAM), 고체 상태 ROM 등을 포함하며 이에 한정되는 것은 아니다. 하드 디스크 드라이브(1024)는 통상 데이터 매체 인터페이스(1034)와 같은 비착탈식 메모리 인터페이스를 통해 시스템 버스(1008)에 접속되고, 자기 디스크 드라이브(1026)와 광학 디스크 드라이브(103)은 통상 착탈식 메모리 인터페이스를 통해 시스템 버스(1008)에 접속된다.

상술한 그리고 도 10에 도시된 드라이브들과 이들과 연관된 컴퓨터 저장 매체는 컴퓨터(1002)의 컴퓨터 판독가능한 명령어, 데이터 구조, 소프트웨어 컴포넌트들 및 다른 데이터의 저장을 제공한다. 도 10에서, 예컨대 하드 디스크 드라이브(1024)는 운영 체제(1016'), 애플리케이션(1018'), 소프트웨어 컴포넌트(1020') 및 프로그램 데이터(1022')를 저장하는 것으로 도시되어 있다. 이 구성요소들은 운영 체제(1016), 애플리케이션(1018), 소프트웨어 컴포넌트(1020) 및 프로그램 데이터(1022)와 동일할 수도, 상이할 수도 있다는 점에 유의하자. 운영 체제(1016'), 애플리케이션(1018'), 소프트웨어 컴포넌트(1020') 및 프로그램 데이터(1022')가 최소한 상이한 복사본들임을 보여주기 위해서 본 명세서에서는 이들에게 상이한 번호들을 부여하였다. 사용자는 마우스, 트랙볼 또는 터치 패드라고 보통 말하는 포인팅 장치(도시되지 않음) 및 키보드(1036)와 같은 입력 장치들을 통해 컴퓨터(1002)에 명령 및 정보를 입력할 수 있다. 다른 입력 장치들은 (스트리밍 데이터를 공급하는 마이크로폰(1038) 또는 카메라(104)와 같은) 소스 장치들, 조이스틱, 게임 패드, 위성 접시, 스캐너 등을 포함할 수 있다. 이들 및 여타 입력 장치들은 종종 시스템 버스에 연결된 입/출력 인터페이스(I/O interface)(1042)를 통해 프로세싱 유닛(1002)에 접속되지만, 병렬 포트, 게임 포트 또는 USB(universal serial bus)와 같은 다른 인터페이스 및 버스 구조를 통해 접속될 수도 있다. 모 니터(1044) 또는 다른 유형의 디스플레이 장치 또한 비디오 어댑터(1046)과 같은 인터페이스를 통해 시스템 버스(1008)에 접속된다. 모니터(1044) 외에도, 컴퓨터는 I/O 인터페이스(1042)를 통해 접속될 수 있는 다른 렌더링 장치들(예컨대, 스피커) 및 하나 이상의 프린터들을 포함할 수 있다.

컴퓨터는, 원격 장치(1050)와 같은 하나 이상의 원격 컴퓨터에 대한 논리 접속(logical connection)을 사용하는 네트워크 환경에서 동작할 수 있다. 원격 장치(105)는 개인용 컴퓨터, 네트워크-레디 장치(network-ready device), 서버, 라우터, 네트워크 PC, 피어 장치(peer device) 또는 다른 공통 네트워크 노드(common network note)일 수 있으며, 컴퓨터(1002)와 관련하여 상술한 구성 요소들 중 다수 또는 모든 것을 포함한다. 도 10에 도시된 논리 접속은 LAN(local area network)(1052) 및 WAN(wide area network)(1054)를 포함한다. 도 10에 도시된 WAN(1054)은 인터넷이지만, WAN(1054)은 다른 네트워크를 포함할 수도 있다. 이러한 네트워크 환경은 사무실에서 흔한 것으로서, 기업-기반 컴퓨터 네트워크, 인트라넷 등이 있다.

LAM 네트워크 환경에서 사용될 때, 컴퓨터(1002)는 네트워크 인터페이스 또는 어댑터(1056)을 통해 LAN(1052)으로 접속된다. WAN 네트워크 환경에서 사용될 때, 컴퓨터(1002)는 모뎀(1058) 또는 인터넷을 통해 통신을 설정하기 위한 다른 수단들을 통상 포함한다. 모뎀(1058)은 외장형 또는 내장형일 수 있는데, I/O 인터페이스(1042) 또는 다른 적절한 메커니즘을 통해 시스템 버스(1008)에 접속될 수 있다. 네트워크 환경에서, 컴퓨터(1002)와 관련하여 도시된 프로그램 모듈 또는 그 일부는 원격 장치(105)에 저장될 수 있다. 예컨대, 도 10은 원격 장치(105)에 있는 원격 소프트웨어 컴포넌트(1060)을 도시한다. 도시된 네트워크 접속은 예시적인 것이며, 컴퓨터 간에 통신 링크를 설정할 수 있는 다른 수단이 사용될 수 있다는 점에 주의하자.

결 론

본 발명은 구조적 특징들 및/또는 방법상의 절차들에 대해 특유한 언어로 기술되었지만, 첨부된 청구범위에 정의된 본 발명은 상술한 특징들 및 절차들에 반드시 한정되는 것은 아니다. 오히려 특유한 특징들 및 절차들은 청구범위의 발명을 실시하기 위한 예시적인 형태로서 개시된 것이다.

P2P 네트워크에서 메시지들(예컨대, 특정 자원에 대한 요청 및 이 요청에 대한 응답)을 라우팅하는 데 라우팅 테이블을 사용하는 라우팅이 설명되었다. 라우팅 테이블은 P2P 네트워크에서 노드들을 참조하는 라우팅 테이블 내의 항목들을 업데이트하라는 방송(broadcasting)에 의해 업데이트될 수 있다. 일 실시예에서, 각 노드의 라우팅 테이블들을 유지하는 데 사용되는 유지 버짓(maintenance budget)은, 각 세그먼트에 대한 조밀한 라우팅 테이블 항목들(entries)을 만듦으로써, P2P 네트워크의 자원 공간의 다중 세그먼트들에 분배된다. 따라서, 라우팅 테이블을 유지하기 위한 전반적인 유지 버짓은 감소될 수 있고, 이에 의해 P2P 네트워크의 하드웨어, 소프트웨어 및 네트워크 자원이 자유로워져 바람직한 메시지 라우팅 기능을 제공한다.

다른 실시예에서, 본 방법은 P2P 네트워크 내에 포함되려하는 노드에 대해 P2P 네트워크 내에서의 통신을 위해 상기 노드의 이용가능한 자원을 결정하는 단계를 포함한다. 상기 결정에 기초해, 라우팅 테이블은 P2P 네트워크 내에서의 요청들을 라우팅하기 위해 상기 노드에 형성된다.

Claims

P2P 네트워크 내의 복수의 노드들 중 한 노드에서 상기 P2P 네트워크 내의 다른 노드에 의한 회원자격 상의 변화에 대한 표시(indication)를 수신하는 단계; 및

보고서를 방송하는 단계를 포함하고,

상기 보고서는 상기 변화를 기술하고, 상기 한 노드에 포함된 라우팅 테이블에서 참조된 상기 각 노드에 의한 수신을 위한 것인 방법.
제 1 항에 있어서, 상기 표시는 P2P 네트워크 내의 상기 다른 노드에 대한 가입 또는 탈퇴 이벤트인 방법.
제 1 항에 있어서,

상기 라우팅 테이블은 복수의 핑거 테이블 항목들을 가진 핑거 테이블(finger table)이고,

상기 각 핑거 테이블 항목은 로그 함수를 사용하여 대응하는 상기 노드를 참조하는 방법.
제 1 항에 있어서, 상기 P2P 네트워크 내의 상기 각 노드는 P2P 네트워크 내의 하나 이상의 네트워크 자원에 대한 해시 공간(hash space)을 정의하는 리프세트 (leafset) 테이블을 포함하는 방법.
제 1 항에 있어서,

둘 이상의 상기 노드들의 회원 자격 상의 변화를 표시하며 상기 둘 이상의 상기 노드들로부터 수신한 복수의 상기 표시를 취합(aggregation)함으로써, 상기 보고서를 형성하는 단계를 더 포함하고,

상기 보고서는 둘 이상의 상기 노드들의 회원자격 상의 상기 변화를 기술하는 방법.
제 1 항에 있어서, 상기 표시가 전에 상기 한 노드에 의해 수신된 적이 있는지 여부를 판정하고, 수신된 적이 없는 경우에는 상기 표시를 상기 보고서에 포함시킴으로써, 상기 보고서를 형성하는 단계를 더 포함하는 방법.
제 1 항에 있어서, 상기 라우팅 테이블은 상기 복수의 노드들 중 상기 다른 노드 하나 이상을 참조하지 않는 방법.
제 1 항에 있어서, 상기 방송은 미리 결정된 방송 시간에 도달하면 수행되는 방법.
제 1 항에 있어서, 상기 각 노드는 컴퓨팅 장치로 제공되는 방법.
컴퓨터에서 실행될 때, 제 1 항의 방법을 수행하도록 컴퓨터에게 지시하는 컴퓨터 실시가능한 명령어를 포함하는 하나 이상의 컴퓨터로 판독가능한 매체
복수의 노드를 가진 P2P 네트워크 내에 포함되기 위해 구성된 노드에 있어서,

상기 노드에서 상기 다른 노드에 의한 표시 방송(indication broadcast)을 수신하는 단계; 및

상기 표시의 수신에 응답하여, 소프트 상태 라우팅 테이블(SSRT) 내의 하나 이상의 SSRT 항목들을 업데이트하는 단계 - 복수의 상기 SSRT 항목들 각각은 대응하는 상기 노드를 참조함 - 를 포함하는 방법.
제 11 항에 있어서, 상기 표시는 가입 또는 탈퇴 이벤트인 방법.
제 11 항에 있어서, 상기 표시는 핑거 테이블(finger table)을 조사한 뒤에 상기 다른 노드에 의해 방송되는 방법.
제 11 항에 있어서, 상기 노드는 상기 P2P 네트워크에 공급된 자원들에 대한 해시 공간(hash space)을 정의하는 리프세트 테이블(leafset table)을 포함하는 방법.
제 14 항에 있어서, 상기 리프세트 테이블은 상기 다른 노드들 중 하나 이상을 탐지(probing)함으로써 유지되는 방법.
제 11 항에 있어서, 상기 노드는 복수의 핑거 테이블 항목들을 가진 핑거 테이블(finger table)을 포함하고, 상기 각 핑거 테이블 항목은 대응하는 상기 노드의 위치를 로그 함수를 사용해서 기술하는 방법.
제 16 항에 있어서, 상기 핑거 테이블은 상기 핑거 테이블에 참조된 상기 대응하는 노드 각각을 탐지(probing)함으로써 유지되는 방법.
제 11 항에 있어서, 상기 각 표시가 상기 노드에 의해 전에 수신된 적이 있는지 여부를 판정하는 단계, 및

그렇지 않은 경우 상기 업데이트를 수행하는 단계를 더 포함하는 방법.
컴퓨터에서 실행될 때, 제 11 항의 방법을 수행하도록 상기 컴퓨터에 지시하는 컴퓨터 실시가능한 명령어들 포함하는 하나 이상의 컴퓨터로 판독가능한 매체.
P2P 네트워크에 포함되려는 노드 상에서, 상기 P2P 네트워크 내에서의 통신을 위해 상기 노드의 이용가능한 자원들을 결정하는 단계; 및

상기 결정에 기초해, 상기 P2P 네트워크 내의 라우팅 요청들에 대해 상기 노드 상의 라우팅 테이블을 형성하는 단계를 포함하는 방법.
제 20 항에 있어서, 상기 자원은 상기 노드의 하드웨어, 소프트웨어, 또는 네트워크 자원들 중 적어도 하나인 방법.
제 20 항에 있어서, 상기 형성 단계는 상기 결정에 기초해 상기 라우팅 테이블 내에 다수의 항목들을 유도하는 단계를 포함하는 방법.
제 20 항에 있어서, 상기 이용가능한 자원들이 결정된 상기 노드가 상기 P2P 네트워크에 가입할 때, 상기 결정 단계가 수행되는 방법.
제 20 항에 있어서, 상기 이용가능한 자원들이 결정된 상기 노드가 상기 P2P 네트워크의 회원일 때 상기 결정 단계가 정기적으로 수행되는 방법.
제 20 항에 있어서,

상기 결정 단계는 상기 P2P 네트워크 내의 상기 다른 노드들 중 적어도 하나의 이용가능한 자원들을 결정하는 단계를 더 포함하고,

상기 형성 단계는 상기 노드 및 상기 다른 노드들 중 적어도 하나 이상의 이용가능한 자원들에 대한 결정에 기초해, 상기 노드 상의 상기 라우팅 테이블을 구 성하는 단계를 더 포함하는 방법.
컴퓨터 상에서 실행될 때, 제 20 항의 방법을 수행하도록 상기 컴퓨터에 지시하는 컴퓨터 실시가능한 명령어들을 포함하는 하나 이상의 컴퓨터로 판독가능한 매체.
P2P 네트워크 내의 복수의 노드들 중 하나에 의하여 재귀적인 블룸 필터(iterative bloom filter)를 사용하여 라우팅 테이블 내의 항목들을 기술하는 데이터를 압축하는 단계; 및

상기 압축된 데이터를 다른 노드에 통신하기 위한 통신문을 형성하는 단계를 포함하는 방법.
제 27 항에 있어서, 상기 재귀적인 블룸 필터를 상기 다른 노드에 통신하는 단계를 더 포함하는 방법.
제 27 항에 있어서, 상기 압축된 데이터를 사용하여 상기 다른 노드의 라우팅 테이블의 하나 이상의 항목들을 업데이트하는 단계를 더 포함하는 방법.
컴퓨터에서 실행될 때, 제 27 항의 방법을 수행하도록 상기 컴퓨터에 지시하는 컴퓨터 실시가능한 명령어들 포함하는 하나 이상의 컴퓨터로 판독가능한 매체.
하나 이상의 컴퓨터로 판독가능한 매체에 있어서,

컴퓨터 상에서 실행될 때,

복수의 노드들 중 하나 이상의 노드에 대해 P2P 네트워크 내의 회원자격 상의 변화가 발생한 때를 판정하는 단계; 및

상기 변화가 발생한 때에는, 상기 복수의 노드들의 한 부분집합에 대해 보고서를 방송하는 단계를 수행하라고 상기 컴퓨터에게 지시하는 컴퓨터-실행가능한 명령어를 포함하고,

상기 보고서는 회원자격 상의 상기 변화를 기술하고, 상기 부분집합은 상기 부분집합 내의 상기 각 노드를 참조하는 테이블을 조사함으로써 만들어지는 컴퓨터로 판독가능한 매체.
제 31 항에 있어서,

상기 테이블은 복수의 핑거 테이블 항목들을 가진 핑거 테이블(finger table)로서 구성되어 있고,

상기 각 핑거 테이블 항목은 로그 함수를 사용해 대응하는 상기 노드의 위치를 기술하는 컴퓨터로 판독가능한 매체.
제 31 항에 있어서,

P2P 네트워크 내의 상기 복수의 노드들은 상기 복수의 노드들에 의해 제공되 는 자원 공간을 복수의 존(zone)들로 분할하기 위한 분산된 해시 테이블(distributed hash table)을 채택한 컴퓨터로 판독가능한 매체.
제 31 항에 있어서,

상기 테이블은 상기 부분집합 내에서 참조된 상기 각 노드를 탐지(probing)함으로써 유지되는 컴퓨터로 판독가능한 매체.
각각 컴퓨터 명령어를 실행하기 위한 프로세서를 포함하는, P2P 네트워크 내에 배치된 복수의 노드들을 포함하는 시스템에 있어서,

상기 각 노드는 상기 노드들의 세트를 참조하는 복수의 소프트-상태 라우팅 테이블(SSRT) 항목들을 포함하는 SSRT를 포함하고,

상기 각 SSRT 항목은 상기 노드들의 세트로부터 상기 각 노드를 참조하고,

상기 프로세서에 의해 실행될 때, 상기 컴퓨터 명령어는 상기 노드들의 세트에 포함된 적어도 하나의 상기 노드로부터 표시 방송(indication broadcast)을 수신하면 상기 각 대응하는 SSRT 항목들을 업데이트하는 시스템.
제 35 항에 있어서, 상기 표시는 가입 또는 탈퇴 이벤트인 시스템.
제 35 항에 있어서, 상기 표시는, 상기 적어도 하나의 노드에 포함된 핑거 테이블(finger table)을 조사함으로써 상기 적어도 하나의 노드에 의한 방송을 위 해 구성되는 시스템.
제 35 항에 있어서, 상기 각 노드는 상기 P2P 네트워크에서 제공되는 자원을 위한 해시 공간(hash space)을 정의하는 리프세트 테이블(leafset table)을 더 포함하는 시스템.
제 35 항에 있어서, 상기 각 노드는 복수의 핑거 테이블 항목을 갖는 핑거 테이블(finger table)을 포함하고, 상기 각 핑거 테이블 항목은 대응하는 상기 노드의 위치를 로그 함수를 이용해 기술하는 시스템.
각각 복수의 블록으로 분할될 수 있는 식별자를 통해 찾아질 수 있는 복수의 노드를 가진 P2P 네트워크에 포함되기 위한 노드로서,

상기 노드는 프로세서 및 메모리를 포함하고,

상기 메모리는

상기 P2P 네트워크 내에서 제공되는 자원들에 대한 해시 공간(hash space)을 정의하는 리프세트 테이블(leafset table);

복수의 핑거 테이블 항목들을 가진 핑거 테이블(finger table); 및

소프트-상태 라우팅 테이블(SSRT; soft-state routing table)을 유지하도록 구성되어 있고,

상기 각 핑거 테이블 항목은 로그 함수를 이용해 대응하는 상기 노드의 위치 를 기술하고,

상기 SSRT는

각각이 상기 각 노드를 참조하는 SSRT 항목들;

상호 매칭하는 제1 상기 블록을 가진 SSRT 항목들의 제1 그룹; 및

매칭하는 상기 제1 블록 및 상호 매칭하는 제2 상기 블록을 가진 SSRT 항목들의 제2 그룹을 포함하는 노드.
제 40 항에 있어서,

상기 리프세트 테이블 및 상기 핑거 테이블은 탐지(probing)를 통해 업데이트되도록 구성되어 있고,

상기 SSRT는 상기 SSRT 항목에 의해 참조되는 하나 이상의 상기 노드들로부터의 지시(indication)의 방송의 수신에 의해 업데이트되도록 구성된 노드.
제 41 항에 있어서, 상기 지시는 하나 이상의 상기 노드에 포함된 핑거 테이블을 조사함으로써 하나 이상의 상기 노드에 의한 방송을 위해 구성되는 노드.
제 40 항에 있어서, 상기 SSRT 내의 상기 SSRT 항목들의 수는 상기 노드의 이용가능한 자원들에 기초해 결정되는 노드.
제 40 항에 있어서, 상기 SSRT 내의 상기 SSRT 항목들의 수는 상기 노드의 이용가능한 자원들의 상기 P2P 네트워크 내의 다른 상기 노드들에 대한 비교에 기초해 결정되는 노드.
복수의 노드를 가진 P2P 네트워크에 포함되기 위한 노드에 있어서,

상기 노드는 프로세서 및 메모리를 포함하고,

상기 메모리는

각각이 상기 각 노드를 참조하는 소프트-상태 라우팅 테이블(SSRT) 항목들을 가진 SSRT; 및

다른 상기 노드와의 통신을 위해 상기 SSRT 항목들을 압축하기 위한 재귀적인 블룸 필터(iterative bloom filter)를 유지하도록 구성되어 있는 노드
제 45 항에 있어서, 상기 재귀적인 블룸 필터는 복수의 블룸 필터를 포함하는 노드.