[Network] 2-6. Peer-to-Peer File Distribution

Computer Networking: A Top-Down Approach, 7th Edition의 번역 및 정리입니다.

지금까지 다룬 웹, 이메일 DNS 앱들은 모두 클라이언트-서버 아키텍처를 사용한다. 이와 달리 P2P 아키텍처는 항상 켜져 있는 인프라 서버에 거의 의존하지 않고, 피어(peer)라 불리는, 간헐적으로 연결되는 호스트 쌍이 직접 서로 통신을 한다. 이 섹션에서는 한 서버에서 다수의 호스트로 큰 파일을 배포하는 P2P 애플리케이션에 대해 알아본다.

클라이언트-서버 파일 배포에서는 서버가 파일의 복사본을 각 피어에게 보내야 한다. 이 작업은 서버에 큰 부담을 주고, 서버 대역폭도 많이 소비한다. P2P 파일 배포에서는 각 피어가 자신기 가지고 있는 파일의 일부분을 다른 피어에게 보내 서버의 배포 과정을 돕는다.

Scalability of P2P Architectures

P2P 아키텍처와 클라이언트-서버 아키텍처를 비교해보자.

서버와 피어들은 모두 액세스 링크를 통해 인터넷에 접속되어 있다. 서버 액세스 링크의 업로드 속도는 $u_s$다. $i$번째 피어 액세스 링크의 업로드 속도는 $u_i$이고, 다운로드 속도는 $d_i$다. 배포될 사이즈의 사이즈는 $F$ 비트, 파일의 복사본을 받고자 하는 피어의 수는 $N$이라 하자.

모든 피어가 파일의 복사본을 받는 데 걸리는 시간을 배포 시간(distribution time)이라 한다. 이제 클라이언트-서버 아키텍처와 P2P 아키텍처에서의 배포 시간을 계산해보자. 단, 인터네 코어에는 충분한 대역폭이 마련되어 있고, 모든 병목은 액세스 네트워크에서만 일어난다고 가정한다. 또한 서버와 클라이언트들이 다른 네트워크 애플리케이션은 사용하지 않아, 업로드와 다운로드 액세스 대역폭을 이 파일 배포에만 사용할 수 있다고 가정한다.

클라이언트-서버 아키텍처의 배포 시간

클라이언트-서버 아키텍처의 배포시간 $D_{cs}$를 계산해보자. 클라이언트-서버 아키텍처에서는 어떤 피어도 파일 배포에 도움을 주지 않는다. 따라서 다음과 같은 사실들을 알 수 있다.

• 서버는 파일의 복사본을 $N$명의 피어들에게 각각 보내야 하므로, 총 $NF$ 비트를 전송해야 한다. 서버의 업로드 속도가 $u_s$이므로, 파일을 배포하기 위한 시간은 적어도 $NF/U_s$가 된다.
• $d_{min}$이 가장 느린 다운로드 속도를 가지고 있는 피어의 다운로드 속도라고 하자. 이 피어는 $F$ 비트 파일을 $F/d_{min}$ 초보다 빠르게 받을 수 없다. 따라서 최소 배포 시간은 적어도 $F/d_{min}$은 되어야 한다.

따라서 클라이언트-서버 구조에서의 최소 배포 시간은 다음을 만족한다.

이때 $N$이 충분히 커지는 경우 클라이언트-서버에서의 배포 시간은 $NF/u_s$에 가까워질 것이고, 따라서 배포 시간은 피어의 수 $N$에 따라 선형적으로 증가하게 된다.

P2P 아키텍처의 배포 시간

P2P 아키텍처에서는 각 피어들이 서버의 파일 배포를 돕는다. 구체적으로, 각 피어들은 파일 데이터의 일부를 받고 이를 다른 피어에게 직접 재배포한다. P2P 아키텍처에서의 배포 시간 계산은 클라이언트-서버 아키텍처보다 복잡하다. 배포 시간이 각 피어가 다른 피어들에게 파일 일부분을 어떻게 배포하느냐에 의존하기 때문이다.

• 파일 배포를 시작할 때에는 서버만이 파일을 가지고 있다. 이 파일을 피어 커뮤니티로 보내기 위해, 서버는 일단 파일을 적어도 한 버은 액세스 링크를 통해 내보내야 한다. 따라서 최소 배포 시간은 $F/u_s$는 넘게 된다.
• 클라이언트-서버 아키텍처에서처럼, 가장 느린 다운로드 속도를 가지고 있는 피어는 $F/d_{min}$초보다 빠르게 파일을 얻지 못한다. 따라서 최소 배포 시간은 적어도 $F/d_{min}$은 넘어야 한다.
• 피어들은 파일을 다운로드 받을 뿐만 아니라, 업로드를 해야 한다. $u_{total} = u_s + u_1 + ... + u_N$이라 하자. 시스템에서는 $N$ 피어들에게 $F$비트가, 그러니까 총 $NF$ 비트가 보내져야 한다. 따라서 최소 배포 시간은 적어도 $NF/u_{total}$은 넘게 된다.

따라서 P2P의 최소 배포 시간 $D_{P2P}$는 다음을 만족해야 한다.
$D_{P2P} \geq max(F/u_s, F/d_{min}, NF/u_{total})$
실제로는 파일이 비트 단위가 아니라 청크 단위로 재배포되지만, 그럼에도 위 부등식은 실제 최소 배포 시간을 계산하기 위해 쓸 만하다.

위 표는 클라이언트-서버 아키텍처와 P2P 아키텍처의 최소 배포 시간을 비교한 것이다. 단 모든 피어가 같은 업로드 속도 $u$를 가지고 있다고 가정한다. $F/u = 1$ 시간, $u_s = 10u$, $d_{min} \geq u_s$라 하자. 즉 한 피어는 파일 하나 전체를 1시간에 전송할 수 있고, 서버의 전송 속도는 피어의 업로드 속도의 10배다. 또한 피어의 다운로드 속도는 충분히 빨라 영향이 없다고 가정한다.

여기서 우리는 클라이언트-서버 아키텍처의 배포 속도는 피어의 수가 늘어남에 따라 선형적으로 증가함을 볼 수 있다. 한편 P2P 아키텍처의 경우 클라이언트-서버 아키텍처보다 항상 빠르며, 뿐만 아니라 P2P 아키텍처의 피어들은 항상 파일을 1시간보다도 빠르게 받을 수 있다. 따라서 P2P 아키텍처 애플리케이션들은 높은 확장성을 가진다고 할 수 있다.

BitTorrent

BitTorrent는 파일 배포를 위해 가장 많이 쓰이는 P2P 프로토콜이다. BitTorrent에서는 특정 파일 배포에 참가하는 모든 피어들의 집합을 토렌트(torrent)라고 부른다. 토렌트의 피어들은 다른 피어로부터 동일한 크기의 파일 청크를 받는데, 청크 사이즈는 보통 256KB다.

한 피어가 토렌트에 참가한다고 하자. 이 피어는 원래 청크를 가지고 있지 않다. 시간이 지나면서 이 피어는 더욱 더 많은 청크들을 축적하며, 이렇게 받은 청크들을 또한 다른 피어들에게도 업로드한다. 파일 전체를 다 받은 피어는 토렌트를 떠날 수도 있고, 혹은 토렌트에 남아 계속 다른 피어들에게 청크를 업로드할 수도 있다. 피어는 청크 일부만을 받고 토렌트를 떠났다가, 나중에 다시 토렌트에 참가해 청크를 이어 받을 수도 있다.

BitTorrent가 어떻게 동작하는지 조금 더 자세히 알아보자. 각 토렌트에는 트래커(tracker)라 불리는 인프라 노드가 있다.

토렌트에 참가할 때, 피어는 자신을 트래커에 등록하고, 주기적으로 트래커에 자신이 아직 토렌트에 있음을 알린다. 이를 통해 트래커는 현재 토렌트에 참가중인 피어들을 추적할 수 있게 된다.

앨리스가 새로운 피어로서 토렌트에 참가하려 한다고 해보자. 트래커는 해당 토렌트에 참가 중인 피어의 일부를 임의로 골라 그 IP 주소를 앨리스에게 보낸다. 이 피어 리스트를 받으면 앨리스는 그 리스트의 모든 피어들과 TCP 연결을 맺는다. 이렇게 앨리스와 연결을 맺은 피어들을 이웃 피어라고 하자. 시간이 지남에 따라 이웃 피어들이 토렌트를 떠날 수도 있고, 혹은 또 다른 피어가 토렌트에 참가해 앨리스와 TCP 연결을 맺을 수도 있다.

각 피어들은 파일의 일부 청크들을 가지고 있고, 다른 피어들은 또 다른 청크들을 가지고 있다. 앨리스는 주기적으로 자신의 이웃 피어들에게 그들이 가지고 있는 청크 리스트를 묻는다. 앨리스의 이웃이 $L$명이라면 앨리스는 $L$개의 리스트를 얻게 된다. 이를 통해 앨리스는 자신이 가지고 있지 않은 청크를 요청한다.

리스트를 받았다면, 앨리스는 (1) 어떤 청크를 달라고 (2) 누구에게 요청할지를 결정해야 한다. 이때 쓰는 테크닉을 rarest first라 한다. 자신이 가지고 있지 않은 청크들 중, 이웃들이 가장 적게 가지고 있는 청크를 골라 가장 우선적으로 요청하는 것이다. 이러한 방식으로 가장 레어한 청크는 좀 더 빠르게 배포된다. 토렌트 내에 있는 청크들의 복사본 수를 최대한 비슷하게 만들기 위함이다.

이번에는 앨리스에게 요청이 들어왔다고 해보자. 이 요청에 응답할 때에도 BitTorrent는 기발한 교환 알고리즘을 사용한다. 기본적인 아이디어는 현재 자신에게 가장 빠른 속도로 데이터를 제공하는 이웃에게 우선권을 주는 것이다. 구체적으로, 앨리스는 이웃들 중 자신에게 가장 빠르게 데이터를 보내는 4명의 피어를 고르고, 그들에게 자신이 가지고 있는 청크를 보냄으로써 응답한다. 매 10초마다 앨리스는 속도를 재측정하고, 기존에 선정한 4명의 피어를 바꿀 수도 있다. BitTorrent에서는 이 네 피어를 가리켜 unchoked라 부른다.

또한 매 30초마다 앨리스는 추가로 한 명의 이웃을 임의로 골라 청크를 보낸다. 이렇게 임의로 선정된 피어를 밥이라 부르자. BitTorrent에서는 밥을 optimistically unchoked라 부른다. 앨리스가 밥에게 데이터를 보내기 때문에, 앨리스는 밥의 unchoked 중 한 명이 될 수도 있고, 만약 그렇게 된다면 밥도 앨리스에게 데이터를 보내기 시작할 것이다. 만약 밥이 앨리스에게 데이터를 보내는 속도가 충분히 빠르다면, 밥은 앨리스의 unchoked가 될 수도 있을 것이다.

다시 말해, 앨리스는 30초마다 새로운 교환 파트너를 골라 그 파트너와 교환을 시작한다. 만약 두 파트너가 서로에게 교환을 할 만큼 빠르게 데이터를 보낸다면, 이들은 서로를 unchoked로 두고 계속해서 교환을 할 것이고, 이때 원래 unchoked에 있다가 빠져 나온 피어는 더 나은 다른 파트너를 찾으려 하게 될 것이다.

이를 통해 얻을 수 있는 효과는 다음과 같다.

• 일정 속도 이상으로 업로드를 할 수 있는 피어들은 서로를 찾을 수 있게 된다.
• 임의의 이웃 선정을 통해 새 피어는 청크를 얻을 수 있고, 이를 가지고 교환에 참가할 수 있게 된다.

unchoked와 optimistically unchoked를 제외한 피어들은 choked라 부르며, 이들은 앨리스로부터 어떠한 청크도 받지 못한다.