[컴네/CN] 응용 P2P

순수 P2P 구조

 

P2P는 peer to peer의 약자로 peer들끼리 직접 통신을 하는 프로토콜이다.

이때 peer는 동료라는 뜻으로 하나의 컴퓨터, 휴대폰 등을 일컫는다.

 

전통적으로 네트워크는 always on인 서버를 가지고 클라이언트들이 접속하는 상태이지만,

p2p는 always on인 서버가 존재하지 않는다.

피어들이 직접적으로 가끔 연결되어 통신하는데, 보통 연결이 안 된 상태가 많다.

 

이러한 조건을 바탕으로 p2p 구조를 잘 만들기 위해서는 '파일 배포 방법'과 '정보 검색 방법'이 중요하다.

 

Server-Client vs. P2P

1개의 서버가 N개의 피어에게 파일을 배포할 때 얼마의 시간이 걸리는지 비교해보자.

 

- 파일의 크기: F

- 서버에 파일을 업로드 하는 대역폭: us

- 피어 i가 파일을 업로드 하는 대역폭: ui

- 피어 i가 파일을 다운로드 하는 대역폭: di

라고 했을 때,

각 방식 별로 파일을 배포하는 시간에 대해 알아 보자.

 

Server-Client

- 서버가 N개의 파일을 순서대로 보내는 시간(업로드 시간): N*F/us

- i번째 클라이언트가 파일을 다운로드 받는 시간(다운로드 시간): F/di

이므로 배포에 걸리는 시간은 아래와 같다.

 

이때, 서버가 N개의 파일을 보내는 이유는 각 클라이언트마다 파일을 하나씩 전송해야 하기 때문이다.

또한 서버에 업로드함과 동시에 client에서의 다운로드가 동시에 진행되므로 두 값 중의 최댓값을 구하는 것이 파일의 배포시간이 된다.

 

이때, 업로드 시간이 클라이언트 수인 N에 비례하여 선형적으로 증가하므로 보통 최대값으로 업로드 시간이 잡힌다. 따라서 Server-Client의 경우 보통 다운 받는 클라이언트의 수에 비례하여 시간이 증가한다.

 

P2P

- 서버가 파일을 업로드하는 시간: F/us

- i번째 클라이언트가 파일을 다운로드 받는 시간: F/di

- 파일을 n번 업로드 하는 시간: N*F bits / (us + ∑ui)

이므로 배포에 걸리는 시간은 아래와 같다.

 

이때, 서버는 초기에 파일을 배포한 후 여러 클라이언트들이 파일의 조각을 보유하고 있기 때문에 해당 조각을 상대 피어에 전송하므로 서버에서는 업로드를 한 번만 진행해도 된다.

 

N*F bits / (us + ∑ui)는 서버가 한 번 업로드하는 시간과 나머지 피어에서 업로드 하는 시간을 합한 것으로 N에 비례한다. 따라서 보통 최대값으로 해당 수식이 잡힌다.

 

클라이언트가 많아질 수록 N이 커지지만 분모도 함께 증가하므로 linear하게 증가하지 않는다. 따라서 Server-Client 방식에 비해 파일 배포 시 적은 시간을 소요할 수 있다.

 

두 방법의 시간을 그래프로 표기하면 아래와 같다.

 

위 그래프에서 확인할 수 있듯이, 클라이언트(또는 피어)의 수가 증가할 수록 p2p의 이점이 잘 드러난다.

 

BitTorrent

 

BitTorrent는 대표적인 p2p 파일 배포 방식을 사용하는 예이다.

이때 tracker는 현재 파일 배포에 어떤 피어가 참여하고 있는지, 해당 피어는 어떤 조각을 가지고 있는지를 파악하고 연결해주는 역할을 한다.

torrent는 파일의 조각을 공유하고 교환 가능한 그룹이다.

 

BitTorrent는 파일을 256KB의 아주 작은 청크로 분할한 후 파일을 주고 받는다.

각 피어는 다운로드 받으며 동시에 업로드를 진행할 수 있도록 하여 모든 피어가 파일 배포에 참여하도록 하게 하며

피어는 참여와 탈퇴가 자유롭다. 다운로드를 받자마자 컴퓨터를 종료해도 다운로드를 받으며 업로드를 동시에 진행하도록 하기 때문이다.

 

청크 수신

각 피어들은 청크를 수신할 때 다른 청크를 유지하며

주기적으로 이웃의 청크 리스트에 대해 물어본 후 없는 청크부터 요청한다.

청크 자체의 리스트도 관리를 해야 하는데, 대부분은 조각 중 자주 연결되어 받을 수 없는 청크부터 수신하도록 한다.

 

청크 송신

피어의 참여와 탈퇴가 자유로우므로 피어는 4명의 이웃에게 매 30초마다 주기적으로 피어를 임의적으로 선택하여 청크를 전송한다.

 

Distributed Hash Table(DHT)

피어를 통해 파일을 다운로드 받을 때 각 피어가 어떤 파일을 보유하고 있는지 파악해야 한다.

따라서 해당 정보들을 가지고 있는 테이블을 Distributed Hash Table(DHT)라고 한다.

이때 DHT는 피어들의 참여와 탈퇴가 자유로우므로 분산된 동적인 DB이다.

 

(key, value) 쌍으로 이루어져 있으며 key는 파일, value는 peer의 ip 주소이다.

각 피어는 파일을 요청할 때 DHT에 파일을 통해서 해당 파일을 가지고 있는 피어의 주소를 얻는다.

 

새로 생성된 피어는 (key, value)의 값을 새롭게 삽입할 수 있다.

 

DHT identifier

이때, DHT에서 각 피어를 n비트를 이용하여 정수 식별자[0, 2^n-1]로 할당한다.

각 키는 특정 범위 이내의 정수여야 한다.

 

정수인 키 값을 얻기 위해 원래 키 값(파일)에 대해 해싱한다.

예를 들어 파일 이름이 'movie'라면, h('movie')를 통해(해싱을 통해) 정수 키 값을 반환할 수 있다.

 

각 피어들은 key값을 통해 연결되어야 하는데, 이웃 피어가 누구고 어떤 값을 갖는지에 대해 알고 있어야 하므로 각 피어는 연결되어야 한다.

 

각 피어의 연결 방법은 다양한데, 그 중 하나는 key 값을 가장 가까운 ID를 가진 피어(인접한 이웃, the immediate successor of the key)에게 할당한다.

 

Circular DHT

 

피어는 원형으로 연결되어 있으며 각 피어는 인접 노드(immediate successor and predecessor)만 알고 있다.

 

어떤 파일을 요청 받았을 때, 해당 파일을 보유하고 있으면 돌려주고, 보유하고 있지 않으면 그 다음 노드를 방문하는 방식으로 파일을 찾기 위해 모든 노드를 한 번씩 방문할 수 있다. 이러한 방식은 물리적인 네트워크가 아닌 오버레이 네트워크(overlay network)라고 부른다.

 

피어들은 이러한 오버레이 네트워크 상에서 원형으로 연결되어 있고 대표적인 예가 위와 같은 circular DHT이다.

 

위 경우 각 노드가 binary 형태로 표현되어 있고 1110을 찾을 때 0011에서 시작하여 인접 노드를 방문한 후 가장 1100과 가장 가까운 1111에서 응답을 해준다. 이때 이 응답은 요청한 0011을 향한다.

 

이러한 방식은 N개의 피어를 모두 방문해야 하므로 O(N)의 시간복잡도를 가진다.

 

Circular DHT with Shortcuts

 

피어가 많아질수록 방문해야 하는 피어가 늘어나므로 소요 시간 또한 증가하게 된다.

따라서 이러한 구조를 빠르게 하기 위해 지름길(shortcuts)을 연결할 수 있다.

 

위와 같이 노드를 2개씩 건너 뛸 수 있으며 이러한 방법을 사용하면 시간 복잡도를 O(log N)까지 줄여줄 수 있다.

 

Skype

스카이프는 p2p 구조를 사용한 voice over IP 통신이다.

전용 응용 프로토콜을 사용하고, BitTorrent의 tracker의 역할을 supernode가 해주며

supernode로부터 계층적인 구조를 확인할 수 있다.

 

따라서 p2p 방식은 server-client 방법보다 성능이 뛰어나다는 장점이 있지만, 피어들이 참여와 탈퇴가 자유롭기 때문에 원하는 파일을 찾기가 어렵다. 또한, circular DHT 구조를 유지 및 관리하기 어렵다는 단점이 있다.