P2P 파일 분배와 BitTorrent — 분배 시간에서 tit-for-tat까지

1. P2P 구조 — 항상 켜진 서버가 없는 응용

앞 글까지 다룬 HTTP, SMTP, DNS는 모두 클라이언트-서버 구조였습니다. 웹 서버나 DNS 서버는 누군가 하루 종일 켜 두고, 고정된 IP 주소를 가집니다. 클라이언트는 그 서버에 요청하고 서버는 응답합니다. 응용을 만드는 또 하나의 구조가 P2P(peer-to-peer)입니다.

P2P 구조에는 항상 켜진 서버(always-on server)가 없습니다. 사용자의 노트북이나 휴대폰 같은 임의의 종단 시스템(end system)끼리 직접 데이터를 주고받습니다. 이 종단 시스템 하나하나를 피어(peer)라고 합니다. 피어는 다른 피어에게 서비스를 요청하고, 동시에 다른 피어에게 서비스를 제공합니다. 내 노트북이 어떤 피어에게서 파일을 받는 클라이언트이면서, 다른 피어에게는 파일을 보내 주는 서버가 됩니다.

표의 마지막 줄이 P2P의 가장 큰 장점입니다. 새 피어는 서비스 수요(service demand)를 더하지만 서비스 용량(service capacity)도 더합니다. 이 성질을 자기 확장성(self scalability)이라고 합니다. 3~5절에서 이 성질을 분배 시간 식으로 확인합니다.

관리는 어려워집니다. 피어는 간헐적으로 접속하고(intermittently connected), 접속할 때마다 IP 주소가 바뀔 수 있습니다. 그래서 피어끼리 서로를 어떻게 찾는지, 피어가 계속 들어오고 나가도 서비스가 어떻게 이어지는지를 응용이 직접 해결해야 합니다. P2P를 쓰는 예로는 파일 분배의 BitTorrent, 영상 스트리밍, Skype 같은 인터넷 전화(VoIP), 블록체인이 있습니다.

2. 파일 분배 문제를 세웁니다

두 구조를 같은 일로 비교합니다. 크기 F 비트인 파일 하나를 서버에서 N개 호스트에게 나눠 주는 파일 분배(file distribution)입니다. 처음에는 서버만 파일을 가지고 있습니다. 분배 시간(distribution time)은 N개 호스트 모두가 파일 전체를 받을 때까지 걸리는 시간입니다.

계산을 단순하게 하려고 가정을 둘 둡니다. 첫째, 네트워크 코어의 대역폭은 넉넉해서(abundant bandwidth) 코어에서는 기다리지 않습니다. 둘째, 속도를 제한하는 곳은 가장자리의 접속 회선(access link)뿐입니다. 서버의 업로드 속도와 호스트의 업로드·다운로드 속도만 따지면 됩니다.

그러면 지연은 전송 지연(transmission delay)만 남습니다. 2주차에 본 전송 지연 L / R에서 L 자리에 보낼 비트 수를, R 자리에 업로드나 다운로드 속도를 넣으면 됩니다. 아래 식들은 모두 이 꼴입니다.

3. 클라이언트-서버의 분배 시간

클라이언트-서버에서는 서버가 N개 클라이언트에게 사본을 하나씩 따로 보냅니다. 클라이언트끼리는 주고받지 않습니다. 두 쪽을 나눠 봅니다.

서버 쪽

서버의 업로드 회선은 하나이고 사본 N개가 모두 그 회선을 지나야 합니다. 사본 하나를 올리는 데 F / u_s, N개를 올리는 데 NF / u_s가 걸립니다. 클라이언트가 10명이면 10F / u_s, 1,000명이면 1,000F / u_s입니다.

클라이언트 쪽

클라이언트 i가 파일 전체를 받는 데는 적어도 F / d_i가 걸립니다. 다운로드가 가장 느린 클라이언트는 F / d_min이 걸리고, 이 값이 모든 F / d_i 가운데 가장 큽니다. 모두가 받을 때까지를 재므로 가장 느린 클라이언트가 이 쪽 시간을 정합니다.

두 쪽의 시간 가운데 어느 쪽도 피할 수 없으므로 분배 시간은 둘 가운데 큰 값 이상입니다.

D_c-s ≥ max{ NF / u_s , F / d_min }

서버가 사본을 잘 나눠 보내면 이 하한에 도달할 수 있어서, 교재는 이 값을 최소 분배 시간으로 씁니다. 첫 항 NF / u_s는 N에 비례해 커집니다(increases linearly in N). N이 작을 때는 가장 느린 다운로드가 시간을 정하지만, N이 어느 정도 커지면 첫 항이 더 커지고 그 뒤로는 서버의 업로드 회선이 병목(bottleneck)이 됩니다. 클라이언트가 두 배가 되면 분배 시간도 두 배가 됩니다.

문제 1

크기 6 Gbit인 파일을 클라이언트-서버 구조로 나눠 줍니다. 서버 업로드 속도는 40 Mbps이고, 모든 클라이언트의 다운로드 속도는 4 Mbps입니다. N = 5, 50, 500일 때 최소 분배 시간을 구하고, 두 항이 같아지는 N을 구하십시오.

단위를 Mbit와 Mbps로 맞추면 F = 6,000 Mbit입니다. 클라이언트 쪽 항은 6,000 / 4 = 1,500초로 N과 상관없습니다. 서버 쪽 항은 N × 6,000 / 40 = 150N초입니다. N = 5이면 750초이므로 max{750, 1,500} = 1,500초입니다. N = 50이면 7,500초, N = 500이면 75,000초(약 20.8시간)이고 두 경우 모두 서버 쪽 항이 더 큽니다. 두 항은 150N = 1,500, 곧 N = u_s / d_min = 10에서 같아집니다. 클라이언트가 10명을 넘으면 서버 업로드 회선이 병목입니다.

4. P2P의 분배 시간

P2P에서는 파일 일부를 받은 피어가 그 부분을 곧바로 다른 피어에게 올립니다. 서버가 모든 피어에게 사본을 보낼 필요가 없습니다. 분배 시간에는 하한이 셋 있습니다.

셋째 항을 조금 더 풀어 봅니다. 피어 N개가 각자 F 비트를 받아야 하므로 시스템 전체로 보면 NF 비트가 내려받혀야 합니다. 내려받힌 비트는 누군가 올린 비트입니다. 올리는 쪽은 서버와 N개 피어 전부이고, 그들이 동시에 낼 수 있는 업로드 속도의 합은 u_s + u₁ + u₂ + … + u_N입니다. 전송 지연 L / R에 L = NF, R = u_s + ∑u_i를 넣은 값이 셋째 항입니다.

D_P2P ≥ max{ F / u_s , F / d_min , NF / (u_s + ∑_i=1^N u_i) }

피어가 받은 비트를 받는 즉시 다시 올릴 수 있다고 보면 이 하한에 도달하는 분배 방식이 있음을 보일 수 있어서, 이 값도 최소 분배 시간으로 씁니다.

클라이언트-서버의 식과 비교하면 차이는 셋째 항에 있습니다. 피어가 하나 늘면 분자에 F가 더해지지만 분모에도 그 피어의 업로드 속도 u_i가 더해집니다. 새 피어가 받기만 하지 않고 곧바로 업로더가 되기 때문입니다. 그래서 분배 시간이 N에 비례해 늘지 않습니다. 1절의 자기 확장성이 식에서 이렇게 나타납니다.

모든 피어의 업로드 속도가 u로 같으면 셋째 항은 NF / (u_s + Nu)이고, N이 아주 커지면 F / u에 가까워집니다. 이 값을 넘지는 않습니다. 피어 하나가 파일 하나를 올리는 시간이 피어가 아무리 많아져도 셋째 항의 상한입니다.

5. 피어 수가 늘 때 두 구조 비교

숫자를 넣어 두 식을 나란히 그려 봅니다. 조건은 이렇습니다.

• 모든 피어의 업로드 속도는 u로 같고, 피어 하나가 파일을 한 번 올리는 시간 F / u를 1시간으로 둡니다.
• 서버는 피어보다 4배 빠릅니다. u_s = 4u이므로 F / u_s = 0.25시간입니다.
• 다운로드 속도는 서버 업로드 속도 이상이라고 둡니다. 그러면 F / d_min ≤ F / u_s여서 이 항은 최댓값이 되지 못하므로 뺍니다.

시간을 시간(hour) 단위로 쓰면 두 식이 간단해집니다.

D_c-s = NF / (4u) = N / 4 시간

D_P2P = max{ 0.25 , NF / (4u + Nu) } = max{ 0.25 , N / (N + 4) } 시간

클라이언트-서버는 N에 비례해 한없이 커집니다. P2P는 N이 아무리 커도 1시간을 넘지 않습니다. N / (N + 4)는 언제나 1보다 작기 때문입니다. N = 1에서는 두 구조 모두 서버가 사본 하나를 올리는 0.25시간으로 같고, 그다음부터 차이가 벌어집니다. 같은 파일, 같은 서버인데 피어 100명에게 나눠 주는 시간이 25시간과 1시간 미만으로 갈립니다.

다운로드 속도가 느린 경우도 생각해 볼 수 있습니다. d_min이 u_s보다 작으면 F / d_min이 0.25시간보다 커집니다. 그러면 N이 작을 때는 두 구조 모두 F / d_min에 묶여 같은 값이 되고, N이 커져 다른 항이 F / d_min을 넘어선 뒤에야 차이가 납니다. 피어가 적을 때는 가장 느린 다운로드가 병목입니다.

문제 2

문제 1과 같은 파일과 서버(F = 6 Gbit, u_s = 40 Mbps, d_min = 4 Mbps)로 P2P 분배를 합니다. (가) 모든 피어의 업로드 속도가 1 Mbps일 때 N = 5, 50, 500의 최소 분배 시간을 구하십시오. (나) 업로드 속도가 4 Mbps로 오르면 N = 500의 답은 어떻게 됩니까.

앞의 두 항은 N과 u에 상관없이 F / u_s = 6,000 / 40 = 150초, F / d_min = 1,500초입니다. (가) 셋째 항은 N × 6,000 / (40 + N × 1)입니다. N = 5이면 30,000 / 45 ≈ 667초라 max{150, 1,500, 667} = 1,500초입니다. N = 50이면 300,000 / 90 ≈ 3,333초로 셋째 항이 가장 커서 약 3,333초입니다. N = 500이면 3,000,000 / 540 ≈ 5,556초입니다. 클라이언트-서버의 75,000초와 비교하면 13분의 1 정도입니다. 셋째 항은 N이 커져도 F / u = 6,000초를 넘지 않습니다.

(나) 셋째 항이 3,000,000 / (40 + 2,000) ≈ 1,471초로 줄어 F / d_min = 1,500초보다 작아집니다. 답은 1,500초입니다. 업로드 속도가 다운로드 속도 이상이면 셋째 항의 상한 F / u가 F / d_min 이하이므로, N이 몇이든 가장 느린 피어의 다운로드 시간이 답이 됩니다. 클라이언트-서버의 답은 u와 상관없지만 P2P의 답은 피어가 얼마나 빨리 올리느냐에 따라 달라집니다.

6. BitTorrent — 청크, 토렌트, 트래커

식으로 본 P2P를 실제 시스템으로 옮긴 대표적인 예가 BitTorrent입니다. BitTorrent는 P2P 파일 분배 프로토콜이고, 다음 세 용어로 설명됩니다.

• 청크(chunk) — 파일을 같은 크기로 나눈 조각입니다. BitTorrent는 보통 256 KB(킬로바이트) 단위로 나눕니다. 1 GB(2³⁰ 바이트) 파일이면 2³⁰ / 2¹⁸ = 4,096개 청크가 됩니다. 피어끼리는 청크 단위로 주고받습니다.
• 토렌트(torrent) — 한 파일의 청크를 주고받는 피어들의 무리입니다.
• 트래커(tracker) — 토렌트에 참여한 피어들의 목록을 관리하는 노드입니다. 피어는 트래커에게 물어 다른 피어를 찾습니다.

새 피어가 토렌트에 들어오기까지

1. 지수가 파일을 받으려고 먼저 작은 .torrent 파일을 구합니다. 여기에는 받을 파일에 대한 정보와 트래커의 주소가 들어 있습니다.
2. 지수의 BitTorrent 프로그램이 트래커에 등록하고, 지금 토렌트에 참여한 피어들의 목록을 받습니다.
3. 목록에 있는 피어들과 TCP 연결을 맺고 청크를 주고받기 시작합니다.

트래커는 참여자 목록만 가집니다. 파일을 저장하지 않고 청크를 보내지도 않습니다. 파일 데이터는 모두 피어 사이에서 오갑니다. 1절에서 남겨 둔 질문, 곧 주소가 수시로 바뀌는 피어끼리 서로를 어떻게 찾는가에 대한 BitTorrent의 답이 트래커입니다.

7. 피어의 합류와 이탈

토렌트에 막 들어온 피어는 청크를 하나도 가지고 있지 않습니다. 시간이 지나면서 다른 피어에게서 청크를 모읍니다.

• 트래커에게 받은 목록 전체와 연결하지 않고, 그 가운데 일부와만 연결합니다. 연결된 피어들을 이웃(neighbor)이라고 합니다.
• 내려받는 동안 이미 가진 청크를 다른 피어에게 올립니다. 파일 전체를 다 받을 때까지 기다리지 않고, 청크 하나만 받아도 그 청크를 남에게 줄 수 있습니다.
• 청크를 주고받는 상대는 고정되지 않고 바뀝니다.

피어는 수시로 들어오고 나갑니다. 이 현상을 이탈(churn)이라고 합니다. 이웃이 떠나면 그 자리를 다른 피어가 채우므로, 한 피어가 청크를 주고받는 상대도 계속 바뀝니다.

새 피어는 첫 청크를 받는 순간부터 업로더가 됩니다. 4절 식의 분모 ∑u_i가 실제로 커지는 방식이 이것입니다. 파일을 모두 받은 피어는 바로 떠날 수도 있고(selfishly), 남아서 계속 올려 줄 수도 있습니다(altruistically). 남으라고 강제하는 장치는 없습니다. 모든 피어가 받기만 하고 올리지 않으면 분모가 다시 서버의 u_s만 남고, P2P의 장점이 사라집니다. 피어가 올리게 만드는 방법은 9절에서 봅니다.

8. 어떤 청크를 요청하나 — 가장 드문 청크 먼저

BitTorrent 피어는 두 가지를 정해야 합니다. 이웃에게 어떤 청크를 요청할지(requesting chunks), 그리고 청크를 달라는 이웃 가운데 누구에게 보낼지(sending chunks)입니다. 먼저 요청입니다.

어느 순간이든 피어마다 가진 청크가 다릅니다. 지수는 주기적으로 이웃들에게 각자 가진 청크 목록을 묻고, 자기에게 없는 청크를 요청합니다. 없는 청크가 여럿이면 순서를 정하는 규칙이 가장 드문 청크 먼저(rarest first)입니다. 없는 청크 가운데 이웃들 사이에서 사본이 가장 적은 청크부터 요청합니다.

모든 피어가 파일 앞쪽 청크부터 차례로 요청한다고 해 봅시다. 앞쪽 청크는 거의 모든 피어가 가지게 되고, 뒤쪽 청크는 소수만 가집니다. 뒤쪽 청크를 가진 몇 안 되는 피어가 떠나면 그 청크는 토렌트에서 아무도 갖지 않게 되고, 남은 피어 누구도 파일을 완성하지 못합니다. 드문 청크를 먼저 가져오면 그 청크의 사본이 빨리 늘어납니다. 청크마다 사본 수가 고르게 맞춰지므로 피어 몇이 떠나도 모든 청크가 토렌트 안에 남습니다.

9. 누구에게 보내나 — tit-for-tat과 낙관적 언초크

지수에게 청크를 달라는 이웃은 많은데 지수의 업로드 속도는 한정되어 있습니다. BitTorrent는 보낼 상대를 tit-for-tat(맞대응) 규칙으로 정합니다. 내게 청크를 많이 보내 주는 상대에게 나도 청크를 보냅니다.

• 지수는 이웃들이 자기에게 청크를 보내 주는 속도를 계속 잽니다.
• 그 속도가 가장 높은 이웃 4명에게 청크를 보냅니다. 이 4명의 상태를 언초크(unchoked)라고 합니다.
• 나머지 이웃은 초크(choked)되어 지수에게서 청크를 받지 못합니다.
• 이웃들이 보내 주는 속도는 바뀌므로 10초마다 상위 4명을 다시 고릅니다.

낙관적 언초크

이 규칙만 있으면 새로 들어온 피어가 손해를 봅니다. 새 피어는 가진 청크가 적어 지수에게 보내 줄 것이 별로 없고, 그래서 지수의 상위 4명에 들지 못합니다. 지수에게서 청크를 받지 못하니 계속 줄 청크가 없습니다. 지수 쪽에서도 아직 써 보지 않은 이웃 가운데 더 빠른 상대가 있을 수 있는데 찾을 길이 없습니다.

그래서 지수는 30초마다 이웃 하나를 무작위로 골라 청크를 보내기 시작합니다. 이것을 낙관적 언초크(optimistic unchoking)라고 합니다.

지수가 태호를 낙관적으로 언초크했다고 합시다. 태호는 지수의 상위 4명이 아니었지만 지수에게서 청크를 받기 시작합니다. 태호 쪽에서 보면 지수가 빠르게 보내 주는 상대가 되어 태호의 상위 4명에 들고, 태호도 지수에게 청크를 보내기 시작합니다. 태호가 보내는 속도가 충분히 높으면 다음 평가에서 태호가 지수의 상위 4명에 들어갑니다. 두 피어가 서로의 교환 상대(trading partner)가 됩니다.

이 규칙 덕분에 업로드 속도가 높은 피어는 더 좋은 교환 상대를 찾고 파일을 더 빨리 받습니다. 올리지 않는 무임승차자(free-rider)는 누구의 상위 4명에도 들지 못하고, 낙관적 언초크로 가끔 받는 청크에 기대야 해서 느리게 받습니다. 협력을 강제하는 중앙 기관 없이 프로토콜 규칙만으로 피어가 올리게 됩니다. 7절에서 남은 문제, 받기만 하고 주지 않는 피어를 줄이는 장치가 이 규칙입니다.

문제 3

지수의 이웃은 6명입니다. (가) 지수에게 없는 청크는 3, 5, 8, 9번이고, 이웃 6명 가운데 각 청크를 가진 이웃 수는 3번 5명, 5번 1명, 8번 3명, 9번 0명입니다. 요청 순서를 정하십시오. (나) 이웃들이 지수에게 보내 주는 속도가 A 300, B 50, C 220, D 0, E 180, F 120 kbps입니다. 지수가 언초크하는 상위 4명은 누구이고, D는 어떻게 청크를 받을 수 있습니까.

(가) 가장 드문 청크부터 요청하므로 5번, 8번, 3번 순서입니다. 9번은 지금 이웃 가운데 가진 피어가 없어 요청할 수 없습니다. 이웃이 바뀌어 9번을 가진 피어와 연결되면 그때 요청하고, 그 시점에는 9번이 가장 드물 가능성이 높습니다. (나) 속도가 높은 순서로 A, C, E, F입니다. B와 D는 초크됩니다. D는 30초마다 있는 낙관적 언초크에서 무작위로 뽑혀야 청크를 받습니다. 뽑힌 뒤 받은 청크로 지수에게 120 kbps보다 빠르게 보내 주면, 10초마다 하는 다음 평가에서 F 대신 상위 4명에 들어갈 수 있습니다.

정리

P2P 구조에는 항상 켜진 서버가 없고, 피어가 클라이언트이면서 서버로 동작합니다. 크기 F인 파일을 N명에게 나눠 줄 때 클라이언트-서버의 최소 분배 시간은 max{NF / u_s, F / d_min}이라 N에 비례해 늘어납니다. P2P는 max{F / u_s, F / d_min, NF / (u_s + ∑u_i)}이고, 피어가 늘면 분모의 업로드 용량도 함께 늘어 분배 시간이 F / u 근처에서 멈춥니다. BitTorrent는 파일을 256 KB 청크로 나누고, 트래커가 토렌트의 피어 목록을 알려 주며, 피어는 이웃 일부와 청크를 주고받습니다. 없는 청크는 가장 드문 것부터 요청하고, 청크는 tit-for-tat으로 자기에게 가장 빨리 보내 주는 4명에게 보내며, 30초마다 낙관적 언초크로 새 상대를 시험합니다.