컴퓨터 네트워킹 하향식 접근 - Chapter 2, 5장 P2P 파일 공유

순수 P2P 아키텍처

• 항상 켜져 있는 서버가 없음
• 임의의 종단 시스템끼리 직접 통신함
• 피어들은 간헐적으로 연결되고 IP 주소가 변경됨
  • 자체 확장성 : 새로운 피어가 새로운 서비스 용량을 제공하고, 동시에 새로운 서비스 수요를 가져옴
  • 복잡한 관리 필요
• 예시
  • P2P 파일 공유 (예 : BitTorrent)
  • 스트리밍 (예 : KanKan)
  • VoIP (예 : Skype)

 

파일 배포 : 서버-클라이언트 vs P2P

Q : 파일 크기가 F인 파일을 하나의 서버에서 N명의 피어에게 배포하는 데 걸리는 시간은 얼마나 될까?

 

서버 - 클라이언트 모델

서버가 N명의 클라이언트에게 파일 크기 F를 배포하는데 걸리는 시간은 다음과 같이 계산된다.

1. 서버 전송 시간
   • 서버는 N명의 클라이언트에게 연속적으로 파일을 전송해야 함
   • 서버가 파일 한 개를 전송하는데 걸리는 시간 : F / U_s (U_s는 서버의 업로드 속도)
   • N 명의 클라이언트에게 파일을 전송하는데 걸리는 총 시간 : N * F / U_s
2. 클라이언트 다운로드 시간
   • 각 클라이언트는 자신의 다운로드 속도에 따라 파일을 다운로드함
   • 최소 다운로드 속도를 가진 클라이언트의 다운로드 시간은 F / d_min(d_min은 가장 느린 다운로드 속도)
3. 최종 배포 시간(D_c-s)
   • 서버가 모든 클라이언트에게 파일을 전송하고, 마지막 클라이언트가 다운로드를 완료하는데 걸리는 총 시간은 다음과 같이 계산된다.
     • D_c-s >= max(NF / U_s, F/d_min)
     • NF / U_s​: 서버가 N명의 클라이언트에게 파일을 업로드하는 데 필요한 시간
     • F / d_min : 가장 느린 클라이언트가 파일을 다운로드하는 데 필요한 시간

• 결론
  • 클라이언트- 서버 모델에서 파일 배포 시간은 클라이언트 수 N이 증가함에 따라 선형적으로 증가한다.
  • 병목은 서버의 업로드 속도 U_s와 가장 느린 클라이언트의 다운로드 속도 d_min에 의해 결정된다.

 

P2P

• 서버 전송 : 최소한 한 개의 복사본을 업로드해야 함
  • 한 개의 복사본을 전송하는 시간 :  F / U_s
• 클라이언트 : 각 클라이언트는 파일 복사본을 다운로드해야 함
  • 최소 클라이언트 다운로드 시간 : F/d_min
• 클라이언트들 : 전체적으로 NF 비트를 다운로드해야 함
  • 최대 업로드 속도(최대 다운로드 속도 제한)는 U_s + ∑u_i이다.
  • D_p2p >= max(NF / U_s, F/d_min, NF / (U_s + ∑u_i) )

---

 

파일 분배 : BitTorrent

• 파일은 256Kb 크기의 청크로 분할됨
• 토렌트 내의 피어들은 파일 청크를 주고, 받음
• 기반 구조 노드
  • 트래커(tracker) : 토렌트에 참여하는 피어들을 추적
  • 토렌트(torrent) : 파일의 청크를 교환하는 피어 그룹

• 토렌트에 참여하는 피어 :
  • 처음에는 청크가 없지만, 시간이 지나면서 청크를 쌓아감
  • 트래커에 등록하여 피어 목록을 받고, 그 중 일부 피어(“이웃”)와 연결
• 다운로드를 하면서, 다른 피어들에게 청크를 업로드함
• 변동(churn) : 피어들이 떠나거나 새로운 피어가 참여할 수 있음
• 피어가 파일 전체를 받으면, 이기적으로 떠나거나, 이타적으로 남을 수 있음
• 청크 요청
  • 특정 시점에, 각 피어들은 파일 청크의 서로 다른 부분들을 가지고 있음
  • 주기적으로, 피어는 각 이웃에게 그들이 가진 청크 목록을 요청함
  • 피어는 자신이 없는 청크를 요청하며, 가장 희귀한 청크를 우선적으로 요청
    • 이웃들 중에서 가장 적은 복사본을 가진 청크를 요구
    • 토렌토 내에서 각 청크의 수를 대략적으로 동일하게 유지함
• 청크 전송 : "Tit-for-Tat" 방식
  • 피어는 자신에게 가장 높은 속도로 청크를 보내고 있는 네 명의 이웃에게 청크를 보냄
  • 매 10초마다 상위 4명을 다시 평가함
  • 매 30초마다 무작위로 다른 피어를 선택해 청크 전송을 시작함
    • 이 과정을 낙관적으로 언초크(unchoke)라고 함
    • 새로 선택된 피어는 상위 4명에 합류할 수 있음

 

---

P2P: 정보 검색

P2P 시스템의 인덱스 : 정보를 피어의 위치(위치 = IP 주소 및 포트 번호)에 매핑함

 

파일 공유 (예 : e-mule)

• 인덱스는 피어들이 공유하는 파일의 위치를 동적으로 추적함
• 피어들은 자신이 가진 파일의 정보를 인덱스에 알려야 함
• 피어들은 인덱스를 검색하여 파일이 어디에서 찾을 수 있는지 확인함

인스턴트 메신저 (Instant messaging)

• 인덱스는 사용자 이름을 위치 정보(IP 주소)에 매핑함 
• 사용자가 IM 애플리케이션을 시작할 때, 자신의 위치를 인덱스에 알려야 함
• 피어들은 인덱스를 검색하여, 사용자의 IP 주소를 확인

 

중앙화된 인덱스

초기 "Napster" 설계

1. 피어가 연결되면, 중앙 서버에 다음 정보를 알림
   • IP 주소
   • 콘텐츠 정보
2. 피어는 원하는 콘텐츠를 검색
3. 피어는 콘텐츠를 공유한 피어에게 파일 요청

 

중앙화된 디렉토리의 문제점

• 단일 장애 지점 : 서버가 다운되면 전체 시스템이 작동하지 않음
• 성능 병목 : 중앙 서버에 트래픽이 집중되어 성능이 저하될 수 있음
• 저작권 침해 : 저작권이 있는 콘텐츠를 중앙 서버가 관리하면 법적 문제에 직면할 수 있음

피어들간의 파일 전송은 분산화되어 있지만, 컨텐츠를 찾는 과정은 중앙 집중화되어 있음

 

---

쿼리 플러딩(Query Flooding): Gnutella

 

• 순수 P2P 
• 완전히 분산된 시스템 
  • 중앙 서버가 없음
• 공개 도메인 프로토콜
• 여러 Gnutella 클라이언트가 이 프로토콜을 구현함

오버레이 네트워크: 그래프 형태

• 피어 X와 Y 사이에 TCP 연결이 있을 경우, 두 피어 사이에 엣지가 형성됨
• 모든 활성 피어들과 엣지들은 오버레이 네트워크를 구성함
• 엣지는 물리적인 링크가 아님
• 주어진 피어는 일반적으로 10개 미만의 오버레이 이웃과 연결됨

 

Gnutella 프로토콜

• 이웃에게 쿼리 전송
  • 쿼리 메세지는 기존의 TCP 연결을 통해 전송됨
• 이웃들이 쿼리 메세지를 전달
• QueryHit 메세지는 쿼리가 온 경로 역방향으로 전송됨

확장성 : 제한된 범위의 플러딩(limited scope flooding)

 

 

Gnutella 피어 참가 과정

 

1. 참가하는 피어 X는 Gnutella 네트워크에서 다른 피어를 찾아야 함: 후보 피어 목록을 사용
2. X는 목록에 있는 피어들과 순차적으로 TCP 연결을 시도하고, Y와 연결 설정이 완료됨
3. X는 Y에게 Ping 메시지를 전송하고, Y도 연결되어 있는 이웃 피어에게 Ping 메시지를 전달함
4. Ping 메시지를 받은 모든 피어는 Pong 메시지로 응답함
5. X는 여러 Pong 메시지를 수신하고, 추가로 TCP 연결을 설정할 수 있음

---

이질성 활용 : KaZaA

• 각 피어는 그룹 리더이거나 그룹 리더에 할당됨
  • 피어와 그룹 리더 간에 연결이 설정됨
  • 일부 그룹 리더들 간에도 TCP 연결이 설정됨
• 그룹 리더는 자신에게 할당된 모든 피어들의 콘텐츠를 추적함
• 피어는 그룹 리더에게 쿼리를 보내고, 그룹 리더는 다른 그룹 리더에게도 쿼리를 전달할 수 있음

 

쿼리 과정

• 각 파일은 해시와 설명자를 가짐
• 클라이언트는 키워드 쿼리를 그룹 리더에게 보냄
• 그룹 리더는 쿼리와 일치하는 항목에 대해 응답함
  • 각 일치 항목 : 메타 데이터, 해시, IP 주소
• 그룹 리더가 쿼리를 다른 그룹 리더들에게 전달하면, 그들도 일치하는 항목에 대해 응답함
• 클라이언트는 다운로드할 파일을 선택한 후
  • 해시를 식별자로 사용하여 해당 파일을 보유한 피어들에게  HTTP 요청을 보냄

 

KazaA 트릭들

• 동시 업로드의 제한
• 요청 대기열 
• 인센티브 우선순위
• 병렬 다운로드

 

---

P2P 사례 연구 : Skype

• 본질적으로 P2P : 사용자 간에 직접 통신하는 페어 방식
• 독점 애플리케이션 계층 프로토콜 (역공학을 통해 추론된 프로토콜을 사용)
• 계층적 오버레이 구조 : 슈퍼 노드(SN)를 이용한 계층적 네트워크 구조
• 인덱스 : 사용자 이름을 IP 주소로 매핑하며, 이는 슈포 노드(SN)에 분산되어 저장

 

피어 릴레이 (Peers as relays)

• 문제 : 두 피어 모두 NAT(Network Address Translation) 뒤에 있을 때
  • NAT는 외부 피어가 내부 피어로 직접 통신을 시작하는 것을 방해함
• 해결책
  • 두 노드의 슈퍼 노드(SN)를 사용하여 릴레이(peer relay)를 선택
  • 각 피어가 릴레이와 세션을 시작함
  • 이제 피어들은 릴레이를 통해 NAT를 우회하여 서로 통신할 수 있음

 

분배된 해시 테이블(DHT, Distributed HashTable)

• DHT : 분배된 P2P 데이터베이스
• 데이터베이스는 (key, value) 쌍을 가진다.
• 해시 테이블
  • 숫자 표현을 사용하여 키를 저장하고 검색하는 것이 더 편리함
  • 키 = 해시(원래 키)
• (key,  value) 쌍을 수백만 명의 피어들에게 걸쳐 분산시킴
  • 쌓은 피어들 간에 균등하게 분배됨
• 피어는 키를 이용해 DHT에 쿼리
  • DHT는 해당 키와 일치하는 값을 반환
• 피어는 (key, value) 쌍을 삽입할 수 있다.
• 각 피어는 소수의 다른 피어들에 대해서만 정보를 가짐
• 피어의 이탈과 참여(변동, churn)에 대해 견고함

 

키를 피어에 할당하는 방법

• 중앙 문제
  • 피어들에게 (key, value) 쌍을 할당
• 기본 아이디어
  • 각 key를 정수로 전환
  • 각 피어에게 정수를 할당
  • key에 가장 가까운 피어에게 해당 (key, value) 쌍을 포함시킴

 

DHT 식별자들

• 어떤 n에 대해 [ 0, 2^n -1] 범위 내의 정수 식별자를 각 peer에게 할당
  • 각 식별자는 n bits로 표현됨
• 각 key는 같은 범위 내의 정수일 것을 요구
• 정수 key를 얻기 위해, original key를 해쉬

 

키를 피어에 할당하는 방법

• 규칙 : 가장 가까운 ID를 가진 피어에게 키를 할당 (가장 가까운의 의미는 키의 바로 다음 후임자를 의미)
• 예시 :
  • n = 4; 피어들 : 1, 3, 4, 5, 6, 10, 12, 14
  • key = 13일 때, 후임자 피어는 14
  • key = 15일 때, 후임자 피어는 1

원형 DHT

• 쿼리를 해결하기 위해 평균적으로 N개의 피어가 있을 때 O(N) 메시지가 필요하다.

원형 DHT with 지름길

• 각 피어는 전임자, 후임자, 지름길의 IP 주소들을 계속 알고 있다.
• 6개에서 2개의 메세지로 줄였다.
• 지름길 설계를 통해 쿼리 해결 시 O(log N) 이웃과 O(log N) 메시지로 최적화하는 것이 가능하다

 

피어 변동(Churn)

• 피어들은 네트워크에 들어오고 나가는 변동(churn)이 있을 수 있음
• 각 피어는 자신의 두 후임자의 주소를 알고 있음
• 각 피어는 주기적으로 두 후임자에게 핑을 보내 생존 여부를 확인함
• 바로 다음 후임자가 떠나면, 다음 후임자를 새로운 바로 다음 후임자로 선택
• 예시 : 피어 5가 떠나는 경우
  • 피어 4는 피어 5의 이탈을 감지하고, 피어 8을 자신의 바로 다음 후임자로 설정함
  • 피어 4는 피어 8에게 바로 다음 후임자가 누구인지 물어보고, 피어 8의 바로 다음 후임자를 자신의 두 번째 후임자로 설정함