[computer networking] 2. Application(4)

2.6 Peer-to-Peer Applications

• peer란 간헐적으로 서로 연결된 host pair

• peer는 서비스 공급자가 소유하지 않고 사용자가 제어하는 데스크탑과 랩탑이다.

• 두 가지 종류
  1) a single source to a large number of peers 예) BitTorrent
  2) a database distributed over a large community of peers (DHT, Distributed Hash Table)

Scalability of P2P Architectures (vs client-server architechtures)

• distribution time : 파일 복사본을 모든 N개 peer에 가져오는데 걸리는 시간
• Dcs : client-server architecture ㅊ
  client-server architechture에서 distribution에 도움되는 peer는 없다.
• distribution time에는 upload, download 시간, bandwidth, 병목현상으로 인한 시간 등이 포함되어 있다.
• 서버는 N개 peers에 각 파일 복사본을 전송해야한다. → NF bits를 전송.
  upload rate : Us, distribution에 걸리는 시간은 NF/Us.
• dmin: the lowest download rate. dmin = min{d1,dp,...,dN}.
• minimum distribution time : F/dmin
• client-server distribution time은 N이 커질 수록 distribution time이 커진다.
• P2P 아키텍쳐를 보면 각 peer는 파일 분산해서 서버를 본다. peer가 일부 파일 데이터를 수신하면 자체 업로드 용량을 사용해 데이터를 다른 피어로 재배포 할 수 있다. client-server 아키텍쳐에 비해 계산이 복잡하다. 왜냐하면 distribution time은 각 peer가 파일의 일부를 다른 peer로 배포하는 방법에 따라 달라지기 때문
• 처음에는 서버만 해당 파일을 가지고 있다. Thus, the minimum distribution time is at least F/us.
• 다운로드 속도가 가장 낮은 피어는 F/dmin초 이내에 파일의 모든 F비트를 가져올 수 없다. 따라서 최소 분포 시간은 최소 F/dmin
• 시스템 전체 업로드 용량 = 서버의 업로드 용량 + 각 피어의 업로드 용량, 즉 (총 = us + u1 + … + UN)
• Thus, the minimum distribution time is also at least NF/(us + u1 + … + uN).
• Peer-to-Peer distribution time은 N이 커져도 distribution time이 크게 커지지 않는다.
  → 로그함수 모양, 각 peer가 server의 역할을 분담하기 때문에.

Distributed Hash Tables (DHTs)

• client-server architecture : 하나의 중앙 서버에 모든 (key-value) pair를 저장한다.
• simple database 구현 방법 : a centralized version of this simple database. key, value pair가 포함되어 있다.
• key를 사용해서 데이터베이스에 query한다. 일치하는 key-value pair가 있으면 데이터베이스에서 해당 값을 반환한다.
• P2P에서 수백만개의 peer의 key-value 값을 저장하는 방법
  • 각 peer는 (key-value) pair 전체 중 작은 하위 집합만을 가진다. → 전체를 가지고 있지 않다.
    1. 모든 peer는 특정 key로 distributed database를 query한다.
    2. distributed database는 (key-value) pair가 있는 peer를 찾고 해당 peer는 (key-value) pair을 query한 peer로 반환합니다.
    3. 모든 peer는 새 (key-value) pair를 데이터페이스에 삽입 할 수 있다.
       이런 분산 데이터베이스를 distributed hash table(DHT)라 한다.
• P2P 파일 공유 context에서 DHT 서비스 설명 :
  • key : contents 이름, value: contents 복사본이 있는 peer의 IP 주소
    • DHT 데이터베이스가 peer를 통해 분산되기 때문에 일부 peer가 'Linux' 키를 담당하며 해당 (key-value) pair를 갖게 된다.
      → 밥과 찰리가 각각 최신 리눅스 배포의 복사본을 가지고 있다고 하는 경우
      즉, DHT 데이터베이스에는 (Linux, IPBob)와 (Linux, IPCharlie)의 두 개의 (key-value) pair 포함된다.
    • 구체적인 순서
    1. 앨리스가 'Linux' 복사본을 가지고 싶어한다고 가정
       → 어떤 peer가 리눅스 복사본을 가지고 있는지 알아야함
    2. 'Linux'를 key로 DHT에 query한다.
    3. DHT는 peer인 데이브가 키 'Linux'를 담당한다고 판단한다.
    4. DHT는 peer 데이브에 연결 해 데이브로부터 (key-value) pair인 (Linux, IPBob) 및 (Linux, IPCharlie)을 가져와 Alice에게 전달한다.
    5. Alice는 IPBob 또는 IPCharlie에서 최신 Linux 배포를 다운로드한다.
• 일반적인 (key, value) pairs에 대한 DHT 설계 문제
  • (key, value) pairs을 모든 peers에 무작위로 분산시키고 각 peer가 모든 참여 peer의 IP 주소 목록을 유지하도록 하는 건 문제이다.
    이런 방법은 어떤 peer가 query를 보낼 때 다른 모든 peer에 query를 보내야지만 (key, value) pairs를 포함하는 peer와 일치하는 pair를 응답받을 수 있다. 이런 방식은 확장 불가능하고 각 peer는 다른 모든 peers에 대해 알아야 할 뿐만 아니라 각 query를 모든 peer에게 전송해야하는 문제가 있다.
  • 해결 :
    • 식별자를 각 peer에 할당한다. 여기에서 각 식별자는 고정 n에 대해 [0, 2^n-1]이다.
      → 각 peer에 정수를 할당한다고 생각하면 된다.
    • 실제로는 위의 키 값은 정수가 아니다 → 이런 키로 정수 생성을 위해 각 키를 범위의 정수에 매핑하는 해시함수를 사용한다.
    • 해시 함수는 두 개의 다른 입력이 동일한 출력을 가질 수 있는 다대일 함수이나 해시 함수는 시스템의 모든 피어가 사용할 수 있는 것으로 가정한다. 즉, 'key'는 원래 'key'의 해시를 참조하는 것이다.
    • 예를 들어 원래 키가 "Led Zeppelin IV"인 경우 DHT에서 사용되는 키는 "Led Zeppelin IV"의 해시에 해당하는 정수
  • Distributed Hash function에 hash가 사용되는 이유
• DHT에 (key, value) pairs을 저장하는 문제
  • 가장 중요한 문제는 peer에게 key를 할당하는 규칙을 정의하는 것
  • 각 peer가 정수 식별자를 가지고 있고 각 key도 동일한 범위의 정수라는 점에서, 자연스러운 접근법은 식별자가 key에 가장 가까운 peer에 각(key, value) pairs을 할당하는 것
  • "가장 가까운" → 편의상 가장 가까운 피어를 키의 가장 가까운 후속 피어로 정의한다고 가정
  • 책 그림 참조 :
    n=4라고 가정 했을 때 모든 peer와 key 식별자는 [0, 15]사이에 있다. 더 나아가 식별자가 1, 3, 4, 5, 8, 10, 12 및 15인 8개의 피어가 시스템에 있다고 마지막으로 (key, value) pairs을 저장한다고 가정한다.
  • (11, 조니 우)는 8명 중에 한 명이고 가장 근접한 규칙을 사용하면 peer12가 가장 근접한 후속 peer이다. 때문에 peer12에 (11, 조니 우)를 저장한다.
  • 앨리스는 열쇠에 가장 가까운 피어를 어떻게 결정할까?
    : 앨리스는 시스템의 모든 peer(peer ID 및 해당 IP주소)를 추적해야하는 경우 가장 가까운 피어를 로컬로 확인할 수 있다. 하지만 이런 방식의 경우 각 피어가 DHT의 다른 모든 피어를 추적해야하며 이는 비현실적이다.

Circular DHT

• peer가 원형으로 되어 있다고 생각하자. 방향은 오른쪽.
• 순환 배치에서 peer는 자신의 직전 peer와 직후 peer만을 알고 있다. 아깡의 예를 보면 peer5sms peer 8과 peer 4만을 알고 있다. 이런 peer의 순환 배치는 overlay network의 특수한 경우이다.
  peer는 물리적 링크, 라우터 및 호스트로 구성된 'underlay' 컴퓨터 네트워크 위에 상주하는 추상 논리적 네트워크를 형성하지만 overlay network는 링크의 물리적 링크가 아닌 peer pairs 간의 가상 연결을 의미한다.
• peer3이 key 11을 찾을 때 peer3은 메시지를 시계방향으로 돌린다. 피어가 이런 메시지를 받을 때마다 직전, 직후 식별자(peer)만을 알기 때문에 해당 key에 대한 책임이 있는지(가장 가까운지) 여부를 판단 할 수 있고 책임지지 않는 경우 그냥 메시지를 다음으로 넘긴다. 이는 key 11에 가장 가까운 peer 12에 전달 될 때까지 지속된다.
• circular DHT는 각 peer가 관리해야하는 overlay 정보의 양을 줄여준다.
• 하지만 최악의 경우 각 피어가 인접한 두 피어만 알고 있지만 키를 담당하는 노드를 찾기위해 DHT의 모든 N 노드가 원을 중심으로 메시지를 전달해야 할 수도 있다. (N/2 메시지).
• 이를 해결하기 위해 'shortcut'이 있다. 각 peer는 직전, 직후의 peer뿐만아니라 근접한 다른 peer를 추적한다. 'shortcut'는 query message의 routing이 신속하게 이루어지도록 사용된다.

Peer Churn (피어 변동)

• peer는 임의로 탈퇴하거나 가입할 수 있다.
• 이를 위해 각 peer는 두 개의 후속 peer의 IP address를 알고 있어야한다.
• 후속 peer 중 하나가 이탈하면 그 다음의 peer에 대한 IP address를 가지도록 업데이트한다.
• 각 peer는 두 후속 peer들이 살아 있는지 확인을 위해 주기적으로 ping messages를 보낸다.