[Network] P2P 파일 분배의 개념과 비트 토렌트

P2P 파일 분배

P2P 구조는 항상 켜져 있는 인프라스트럭처 서버에 최소한으로 의존한다.
- 인프라스트럭처 서버에 전혀 의존 안 할 수도 있음
- cf ) 클라이언트-서버 구조 → 인프라스트럭처 서버에 많이 의존함
P2P는 간헐적으로 연결되는 피어(호스트 쌍)들이 서로 직접 통신
- 피어는 사용자가 제어하는 데스크톱과 랩톱, 스마트폰이 보유한다.
  - 서비스 제공자가 소유하는 것이 아님

자연적인 P2P 애플리케이션

커다란 파일을 한 서버에서 다수의 호스트(피어)로 분배한다.
- 파일이 될 수 있는 것
  - 리눅스 운영체제의 새로운 버전
  - 기존 운영체제 혹은 애플리케이션을 위한 소프트웨어 패치(patch)
  - MP3 음악파일 혹은 MPEG 비디오 파일
클라이언트-서버 파일 분배에서 서버는 파일 복사본을 각 피어들에게 보내야 함
→ 이런 행위는 서버에게 큰 부하를 주고 많은 양의 서버 대역폭을 소비
- P2P 파일 분배에서 각 피어는 서버의 분배 프로세스를 도울 수 있다.
  ← 피어는 수신한 파일의 일부분을 다른 피어들에게 재분배할 수 있다.

P2P 구조의 확장성

한 파일을 고정된 수의 피어들에게 분배하는 양적 모델

서버와 피어들은 접속 링크로 인터넷에 연결되어 있다.

U(s) : 서버의 접속 링크 업로드 속도
U(i) : i 번째 피어의 접속 링크 업로드 속도
d(i) : i 번째 피어의 접속 링크 다운로드 속도
파일 : F : 분배되는 파일의 크기(단위는 비트)
N : 파일의 복사본을 얻고자 하는 피어들의 수
분배 시간(distribution time) : 모든 N개의 피어들이 복사본을 얻는 데 걸리는 시간

클라이언트-서버 구조에 대한 분배 시간

가정
- 모든 업로드와 다운로드 접속 대역폭을 이 파일 분배에 모두 사용
- 인터넷 코어가 풍부한 대역폭을 갖고 있다.
분배 시간(D(cs)) 산출 과정
- 클라이언트-서버 구조에서는 어떤 피어도 파일을 분배하는데 도움을 주지 않는다.
- 서버는 파일 복사본을 N개의 피어 각각에게 전송해야 함
  → 서버는 NF 비트를 전송해야 한다.
  → 서버의 업로드 속도가 U(s)이기 때문에 파일 분배 시간 = NF/U(s)
- 가장 낮은 다운로드 속도를 가진 피어는 F/d(min) 초보다
  적은 시간에 파일의 모든 F 비트를 얻을 수 없다.
  
  → 따라서 최소 분배 시간은 적어도 F/d(min)
  - d(min) : 가장 낮은 다운로드 속도를 가진 피어의 다운로드 속도
- 이는 클라이언트-서버 구조에 대한 최소 분배 시간의 하한값을 제공
  클라이언트-서버 구조의 분배 시간 공식
최종 산출 수식

클라이언트 - 서버 구조의 분배 시간 공식
- 제공된 하한값을 실제 분배 시간으로 채택한다.
- 분배 시간은 피어의 수 N에 따라 선형적으로 증가
  → NF/U(s)가 성립하기 때문

P2P 구조에 대한 분배 시간

해당 구조에서 피어들은 각 서버가 파일을 분배하는데 도움을 줄 수 있다.
- 한 피어가 파일 데이터 일부를 수신할 때,
  피어는 그 데이터를 다른 피어들에게 재분배하는데 자신의 업로드 용량을 이용 가능
P2P 구조에서 분배 시간
→ 각 피어가 다른 피어들에게 파일의 일부를 분배하는데 달림
분배 시간 산출 과정(D(psp)로 표기)
- 서버에 있는 파일을 피어 커뮤니티로 전달해야 함
  → 서버는 적어도 한 번 접속 링크로 파일의 각 비트를 보내야 함
  → 따라서 최소 분배 시간은 적어도 F/U(s)
  - 서버가 한번 보낸 비트는 서버가 다시 보낼 필요 없음
    ← 피어들이 그들 사이에서 이 비트를 재분배할 수 있기 때문
- 다운로드 속도가 가장 낮은 피어는 F/d(min) 초
  - F/d(min) 초 보다 적은 시간 안에 파일의 모든 F비트를 얻을 수 없다.
    → 최소 분배 시간은 적어도 F/d(min)이다.
- 시스템의 전체 업로드 용량 = 서버의 업로드 속도 + 각 피어들의 업로드 속도
  - U(total) = U(s) + U(1) + U(2) + … + U(N)
  - 시스템은 N개 피어들 각각에게 F비트를 전달(업로드)해야 함
  - 이는 U(total) 보다 더 빠른 속도로 할 수 없음
    → 최소 분배 시간은 적어도 NF/U(total)

최종 산출 식
P2P 구조의 분배시간 공식
- P2P 구조에 대한 최소 분배 시간에 대한 하한값을 제공
  - 실제 최소 분배 시간에 대한 좋은 근삿값을 제공
  - 이론상으로만 실제 하한값을 얻을 수 있음
    → 비트를 수신하자마자 그 비트를 재분배할 수 있을 때만 가능
  - 실제로는 개별적인 비트보다는 파일의 청크(chunk)가 재분배됨

클라이언트-서버 구조와 P2P 구조 최소 분배 시간 비교

가정
- 모든 피어가 같은 업로드 속도 u를 가진다고 가정
- F/u = 1시간
  - 피어는 전체 파일을 1시간 안에 보낼 수 있음
- U(s) = 10u
  - 서버 전송률은 피어 업로드 속도의 10배
- d(min) ≥ U(s)로 설정
  - 피어 다운로드 속도는 영향을 받지 않을 정도로 크게 설정

클라이언트-서버 구조
- 피어의 수가 증가함에 따라 분배 시간이 선형적으로 증가
- 한계 없이 증가
P2P 구조
- 최소 분배 시간이 클라이언트-서버 분배 시간보다 항상 작지는 않다.
- 피어 수 N이 몇 개든 N에 대해 분배시간이 1시간보다 작다.
  → P2P 구조를 가진 애플리케이션은 자가 확장성을 갖는다.
  - 이 확장성은 피어가 비트의 소비자이자 재분배자인 것에 대한 직접적인 결과

비트토렌트

비트 토렌드 : 파일 분배를 위한 인기 있는 P2P 프로토콜
- 토렌트(torrent) : 특정 파일의 분배에 참여하는 모든 피어의 모임
  - 비트 토렌트에서 쓰는 용어

청크(Chunk)

토렌트에 참여하는 피어들은 서로에게 같은 크기의 청크(chunk)를 다운로드
- 청크의 일반적인 크기는 256KB
처음을 토렌트에 가입했을 경우
→ 피어는 청크가 없지만 시간이 지남에 따라 점점 더 많은 청크를 쌓을 수 있다.
- 피어가 청크를 다운로드할 때, 피어는 또한 청크를 다른 피어들에게 업로드
한 피어가 전체 파일을 얻으면 피어는 3가지 행동 가능
1. 토렌트를 떠난다.(이기적)
2. 토렌트에 남아서 다른 피어들로 청크를 계속해서 업로드(이타적)
3. 일부 청크만을 가진 채, 토렌트를 떠날 수도 있고, 나중에 재가입 가능

비트 토렌트 동작 과정

한 피어가 토렌트에 가입할 때 트래커에 자신을 등록 후,
주기적으로 자신이 토렌트에 있음을 알림
- 각 토렌트는 트래커라고 부르는 인프라스트럭처 노드를 가지고 있음
  - 트래커(tracker) : 토렌트에 참여하는 피어들을 추적

새로운 피어 A가 토렌트에 가입
트래커는 참여하고 있는 피어 집합에서 임의로 피어들의 부분 집합을 선택
선택한 피어들의 IP 주소를 A에게 보냄
→ A는 피어들의 목록을 얻음
A는 목록에 있는 모든 피어와 동시에 TCP 연결 설정
- A가 성공적으로 TCP 연결을 설정한 모든 피어 → 이웃 피어라고 부름
시간에 지남에 따라 이웃 피어 중 일부는 떠나고 다른 피어들은 A와 TCP 연결 시도
→ 이웃 피어들은 시간에 따라 변동됨
- 여기서 다른 피어들이란 이웃 피어를 제외한 다른 피어를 뜻함
- 임의의 주어진 시간에 각 피어는 파일 청크들의 일부를 갖고 있고,
  서로 다른 피어들은 다른 부분을 가지고 있음
주기적으로 A는 이웃 피어들 각각에게 피어들이 가지고 있는 청크 목록을 요구
- A가 L개의 이웃 피어를 가지고 있다면, L개의 청크 목록을 얻음
  → 이를 바탕으로 A는 지금 갖고 있지 않은 청크에 대해 요구

→ A는 청크의 일부를 가지고, 이웃 피어들이 어느 청크를 갖고 있는지 알게 된다.

청크를 요구할 때의 2가지 결정 사항

이웃 피어로부터 어떤 청크를 먼저 요구할 것인가
이웃 피어 중 어떤 피어에게 청크를 요청할 것인가?

가장 드문 것 먼저(rarest first) 기술

가장 드문 것 먼저(rarest first)
- 본인이 가지고 있지 않은 청크 중, 이웃 피어 가운데 가장 드문 청크를 먼저 요구
- 어느 청크 요청을 할 것인지 선택할 때 가장 드문 것 먼저(rarest first) 기술 사용
가장 드문 것 먼저 기술 장점
- 가장 드문 청크들은 더 빨리 재분배될 수 있음
  → 토렌트에 각 청크의 복사본의 수가 대략적으로 동일해진다.

현명한 교역(trading) 알고리즘

어느 요청에 A가 응답할지를 결정하기 위해 현명한 교역(trading) 알고리즘 사용
A가 가장 빠른 속도로 A에게 데이터를 제공하는 이웃에게 우선순위를 주는 것
→ 기본 아이디어
이웃 피어에 대해 A는 계속해서 자신이 비트를 수신하는 속도를 측정
→ 가장 빠르게 전송하는 4개의 피어를 결정한 뒤, 그 피어들에게 청크를 보냄
- 4개의 상위 피어라고 부름
- 10초마다 속도를 재계산하고 4개의 피어 집합을 수정한다.
- 비트 토렌트 용어로 이러한 4개의 피어는 활성화(unchoked)되었다고 함.
또한 30초마다, A가 추가적으로 피어 B를 선택하여 청크를 보낸다.
→ 이때 B는 낙관적으로 활성화(optimistically unchoked) 되었다고 함.
- aka 탐색(probing) 피어
- A가 B에게 데이터를 보내고 있기 때문에 A는 B의 4개 업로더 중 하나가 될 수 있다.
  → 이 경우, B는 A에게 데이터를 보내기 시작한다.
- B가 데이터를 A에게 보내는 속도가 충분히 높다면,
  B는 다시 A의 4개 업로더 중 하나가 될 수 있다.
  - 30초마다 A는 임의로 새로운 교역 파트너를 선택하교 교역한다.
  - 양립할 수 있는 속도로 업로드할 능력이 있는 피어들이 서로를 찾으려는 경향 존재
    → A와 B 피어는 서로 더 좋은 피어를 만나기 전까지 서로를 4개의 목록에 넣는다.
  - 임의의 이웃 선택은 새로운 피어들이 청크를 얻게 하기 위한 기능이 존재한다.
- 5개 피어 외의 모든 이웃 피어는 비활성화(chocked)
  → 외의 다른 아웃 피어는 A로부터 어떠한 청크도 받지 않는다.

비트 토렌트의 현재

TFT : 위에서 기술한 교역을 위한 보상 방식
- 해당 보상 방식은 회피할 수 있다.
비트 토렌트 생태계는 매우 성공적
- 수십만 개의 토렌트에서 동시에 수백만의 피어들이 능동적으로 파일 공유 중
- 비트 토렌트가 TFT 없이 설계되었다면, 비트 토렌트는 지금 존재하지 않았을 것

DHT(Distributed Hash Table, 분산 해시 테이블)

DHT : 데이터베이스 레코드가 P2P 시스템 피어에 분산되어 있는 단순한 데이터베이스
- P2P의 다른 애플리케이션
DHT는 다양하게 구현되어 있으며, 광범위한 연구 대상이 되었다.

저작자표시 변경금지

Today :

P2P 파일 분배

자연적인 P2P 애플리케이션

P2P 구조의 확장성

한 파일을 고정된 수의 피어들에게 분배하는 양적 모델

클라이언트-서버 구조에 대한 분배 시간

P2P 구조에 대한 분배 시간

클라이언트-서버 구조와 P2P 구조 최소 분배 시간 비교

비트토렌트

청크(Chunk)

비트 토렌트 동작 과정

청크를 요구할 때의 2가지 결정 사항

가장 드문 것 먼저(rarest first) 기술

현명한 교역(trading) 알고리즘

비트 토렌트의 현재

DHT(Distributed Hash Table, 분산 해시 테이블)

티스토리툴바

P2P 파일 분배

자연적인 P2P 애플리케이션

P2P 구조의 확장성

한 파일을 고정된 수의 피어들에게 분배하는 양적 모델

클라이언트-서버 구조에 대한 분배 시간

P2P 구조에 대한 분배 시간

클라이언트-서버 구조와 P2P 구조 최소 분배 시간 비교

비트토렌트

청크(Chunk)

비트 토렌트 동작 과정

청크를 요구할 때의 2가지 결정 사항

가장 드문 것 먼저(rarest first) 기술

현명한 교역(trading) 알고리즘

비트 토렌트의 현재

DHT(Distributed Hash Table, 분산 해시 테이블)

검색 태그

티스토리툴바