2.5 P2P: P2P 파일 분배 Computer Network

2.5 P2P 파일 분배

P2P 구조는 항상 켜져있는 인프라스트럭처 서버에 최소한으로 의존하고, 간헐적으로 연결되는 호스트 쌍들(피어, peer)이 서로 직접 통신한다.

클라이언트-서버 파일 분배에서 서버는 파일 복사본을 각 클라이언트에게 보내려면 서버에게 커다란 부하를 주고, 많은 양의 서버 대역폭을 소비한다.

P2P 파일 분배에서 각 피어는 수신한 파일의 임의의 부분을 다른 피어들에게 재분배할 수 있어서 서버의 분배 프로세스를 도울 수 있다.

2020년에 가장 인기 있는 P2P 파일 분배 프로토콜은 비트 토렌트(BitTorrent)다.

P2P 구조의 확장성

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

서버의 접속 링크 업로드 속도를 u(s)로, i번째 피어의 접속 링크 업로드 속도는 u(i)로,그리고 i번째 피어의 접속 링크 다운로드 속도는 d(i)로 나타낸다.

또한, 분배되는 파일의 크기는 F bit로, 파일을 얻고자 하는 피어들의 수는 N으로 나타낸다.

분배 시간은 모든 N개의 피어들이 파일의 복사본을 얻는데 걸리는 시간이다.

다음 분배 시간에 대한 분석에서 클라이언트-서버와 P2P 구조 모두의 경우, 인터넷 코어가 풍부한 대역폭을 갖고 있다는 간단한 가정을 하며,

이는 모든 병목 현상은 다른 네트워크 애플리케이션에 참여하지 않아서 이들의 모든 업로드와 다운로드 접속 대역폭은 이 파일 분배에 모두 사용된다고 가정한다.

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

서버는 파일 복사본을 N개의 피어 각각에게 전송해야 한다. 따라서 서버는 NF 비트를 전송해야 한다.

즉, 서버가 파일을 분배하는 시간은 적어도 NF/u(s)이다.

d(min)이 가장 낮은 다운로드 속도를 가진 피어의 다운로드 속도를 나타낸다고 하자.

가장 낮은 속도를 가진 피어는 F/d(min)초보다 적은 시간에 파일의 모든 F 비트를 얻을 수 없다.
즉 최소 분배 시간은 F/d(min)이다.

즉, 분배 시간을 D(cs)라고 하면 다음과 같은 수식을 얻을 수 있다.


D(cs) ≧ max{ NF/u(s) , F/d(min)}

위 식에서 충분히 큰 N에 대해 클라이언트-서버 분배 시간은 NF/u(s)로 주어진다는 사실을 알 수 있다. 즉, N에 따라 선형 증가한다.

P2P 구조 분배 시간

여기서는 각 피어들이 서버가 파일을 분배하는 데 도움을 줄 수 있다.

특히 한 피어가 파일 데이터 일부를 수신할 때, 피어는 그 데이터를 다른 피어들에게 재분배하는 데 자신의 업로드 용량을 이용할 수 있다.

분배가 시작되면 서버만이 파일을 갖고 있다.

이 파일이 피어 커뮤니티에 도달할 수 있도록 하기 위해, 서버는 적어도 한 번 접속 링크로 파일의 각 비트를 보내야 한다.
따라서 최소 분배 시간은 적어도 F/u(s)다.(서버가 한 번 보낸 비트는 서버가 다시 보낼 필요가 없는데, 이는 피어들이 그들 사이에서 재분배할 수 있기 때문이다.)

클라이언트-서버 구조와 마찬가지로 다운로드 속도가 가장 낮은 피어는 F/d(min)초보다 적은 시간 안에 파일의 모든 F 비트를 얻을 수 없다.

따라서 최소 분배시간은 적어도 F/d(min)이다.

마지막으로, 시스템의 전체 업로드 용량은 전체적으로 서버의 업로드 속도와 각 피어들의 속도를 더한 것이다. 이를 u(total)이라 하자.

시스템은 각 피어들 각각에게 F 비트를 전달해야 한다. 이는 u(total)보다 빠르게 할 수 없다.
따라서 최소 분배 시간은 NF/u(total)이다.

즉, 분배시간을 D(p2p)라고 하면 다음과 같은 수식을 얻을 수 있다.


D(p2p) ≧ max{ F/u(s) , F/d(min), NF/u(total)

위 수식들에서 하한값은 서버-클라이언트 구조에서 서버가 전송을 스케줄링 하거나,

P2P 구조에서는 각 피어가 비트를 수신하자마자 그 비트를 재분배할 수 있다고 가정하면(실제로는 chunk가 재분배된다.),

식의 하한값을 최소 분배시간으로 채택할 수 있다.

위 그래프를 통해 임의의 피어 수 N에 대해 클라이언트-서버 구조보다 P2P 구조가 더 시간이 적다는 것을 볼 수 있다.

따라서 P2P 구조를 가진 애플리케이션은 자가 확장성을 갖는다.

비트토렌트(BitTorrent)

비트토렌트(BitTorrent)는 파일 분배를 위한 인기 있는 P2P 프로토콜이다.

토렌트(torrent)

비트토렌트 용어로 특정 파일의 분배에 참여하는 모든 피어의 모임을 토렌트(torrent)라고 부른다.

토렌트에 참여하는 피어들은 서로에게서 같은 크기의 청크(chunk)를 다운로드한다. (일반적으로 256KB)

처음으로 가입하면 그 피어에는 청크가 없지만, 시간이 지나면 점점 많은 청크를 쌓을 수 있다.(accumulate chunks over time from other peers)

피어가 청크를 다운로드할 때 또한 청크를 다른 피어들에게 업로드한다.

일단 한 피어가 전체 파일을 얻으면 토렌트를 떠나거나, 토렌트에 남아서 다른 피어들로 청크를 계속해서 업로드할 수 있다.

트래커(tracker)

각 토렌트는 트래커(traker)라고 부르는 인프라스트럭처 노드를 갖고있다.

한 피어가 토렌트에 가입할 때 트래커에 자신을 등록하고 주기적으로 자신이 아직 토렌트에 있음을 알려, 트래커는 토렌트에 있는 피어들을 추적할 수 있다.

위의 그림을 예시로 보자.

새로운 피어 앨리스가 토렌트에 가입하면

트래커는 참여하고 있는 피어 집합에서 임의로 피어들의 부분집합(정확히는 50)을 선택하여 이 50개 피어들의 IP 주소를 앨리스에게 보낸다.

이 피어들의 목록을 얻고 나서, 앨리스는 이 목록에 있는 모든 피어와 동시에 TCP 연결을 맺고,

성공적으로 맺은 피어를 이웃 피어(neighbors)라고 부른다.

The peers fluctuate over time

churn : peers may come and go

시간이 지남에 따라 피어들 중 일부는 떠나고, 다른 피어들이 앨리스와 TCP 연결을 시도하고, 피어의 이웃 피어들은 시간에 따라 변동한다.

가장 드문 것 먼저

requesting chunks: rarest first

어느 임의의 시간 안에 앨리스는 청크의 일부를 가질 것이고, 이웃들이 어느 청크를 가지고 있는지를 알게 될 것이다.

앨리스는 이러한 정보를 바탕으로 다음 2가지 결정을 한다.

이웃으로부터 어느 청크를 먼저 요구할 것인가?

이웃들 중 어느 피어에게 청크를 요청할 것인가?

이때 rarest first(가장 드문 것 먼저) 기술을 사용한다.

갖고 있지 않은 청크 중에서, 이웃 가운데 가장 드문 청크를 결정하고 이를 먼저 요구하는 것이다.

이 방법을 통해 가장 드문 청크들은 더 빨리 재분배될 수 있어서 각 청크의 복사본 수가 대략적으로 동일해질 수 있다.

현명한 교역

sending chunks: tit-for-tat

어느 요청에 응답할지 결정할 때 앨리스가 가장 빠른 속도로 그녀에게 데이터를 제공하는 이웃에게 우선순위를 주는 것이다.

특히, 계속해서 비트를 수신하는 속도를 측정하고 가장 빠르게 전송하는 4개의 피어를 결정하고, 이 4개의 피어에게 청크를 보냄으로써 보답한다.

이는 10초마다 계산하여 집합을 수정한다.

비트 토렌트 용어로 4개의 피어는 활성화되었다(unchoked)고 한다.

40초마다 위 피어를 제외하고 임의의 피어에게 청크를 보낸다.

비트 토렌트 용어로 이 피어는 낙관적으로 활성화되었다(optimistically unchoked)고 한다.

즉, 이제 앨리스는 임의의 피어에게 활성화될 수 있고, 활성화가 된다면 임의의 피어도 앨리스에게 활성화될 수 있다.

임의의 선택을 통해 고정된 피어들과만 청크를 교역하는 것이 아니라 여러 피어와 교역할 수 있게 된다.

이러한 5개의 피어 외의 모든 이웃 피어는 비활성화되어 어떤 청크도 교역하지 않는다. (choked by Alice = do not receive chunks from her)

비트 토렌트는 여기서 논의하지 않은 여러 기법들도 갖고 있다.