토렌트 알고리즘

인터넷을 통해 대용량 데이터를 효율적으로 전송하기 위해 BitTorrent는 독특한 파일 공유 방식을 사용합니다. 단순히 파일을 업로드하고 다운로드하는 것 이상의 복잡한 알고리즘이 숨어있는데요, 이번 글에서는 BitTorrent 프로토콜이 어떻게 작동하는지 슈도코드를 활용해 쉽게 설명해드리겠습니다.

1. 파일 분할 (Split File)

BitTorrent는 큰 파일을 전송할 때, 파일을 작은 조각들로 분할합니다. 이렇게 파일을 여러 조각으로 나누면, 각 조각을 여러 피어(peer)로부터 동시에 다운로드할 수 있기 때문에 다운로드 속도가 크게 증가합니다.

슈도코드로 간단히 표현하면 다음과 같습니다.

pseudo

코드 복사

function split_file(file, chunk_size): split the file into chunks of size chunk_size return list_of_chunks

즉, 파일을 미리 정해둔 크기(보통 몇 메가바이트)로 나누고, 이 조각들이 각 피어로 전송됩니다. 각각의 피어는 받은 조각을 다른 피어와 공유하게 됩니다.

2. 조각 배포 (Distribute Chunks)

BitTorrent의 핵심 아이디어는 피어들이 서로 다른 파일 조각을 받아 나눔으로써 전체 파일을 빠르게 완성할 수 있게 하는 것입니다. 이때 트래커(tracker)는 누가 어떤 조각을 가지고 있는지 추적하여, 어떤 피어가 어느 파일 조각을 받을지 결정합니다.

슈도코드는 다음과 같습니다.

pseudo

코드 복사

function distribute_chunks(peers, chunks): for each peer in peers: assign random chunks to the peer return peer_chunk_map # Mapping of peers to their chunks

트래커는 파일을 나눠 각 피어에게 배포하고, 피어들 간의 상호작용을 통해 조각들이 다시 공유됩니다. 이렇게 분산된 방식은 단일 서버에 대한 과부하를 방지하고, 더 빠르고 안정적인 파일 전송을 가능하게 합니다.

3. 피어 간 상호 호혜 (Tit-for-Tat)

BitTorrent의 또 다른 중요한 요소는 '상호 호혜 전략(tit-for-tat)'입니다. 피어는 자신이 조각을 업로드하는 만큼 상대 피어에게 다운로드 받을 수 있습니다. 이를 통해 무임승차(free riding)를 방지하고, 네트워크 내 공정성을 유지합니다.

pseudo

코드 복사

function exchange_pieces(peer_1, peer_2): if peer_1 uploaded to peer_2, then peer_2 will upload to peer_1

이러한 방식으로 피어들은 자신이 기여한 만큼 파일을 빠르게 다운로드할 수 있습니다.

4. 엔드 게임 모드 (End Game Mode)

다운로드가 거의 완료되었을 때 BitTorrent는 "엔드 게임 모드"에 돌입합니다. 이 단계에서는 남은 모든 파일 조각을 가능한 모든 피어에게 동시에 요청하여, 마지막 남은 조각을 빠르게 받습니다. 이를 통해 다운로드가 빠르게 종료되도록 합니다.

pseudo

코드 복사

function end_game_mode(peer): request remaining pieces from all available peers

이 과정은 다운로드 완료 시간을 크게 줄이는 역할을 합니다.

5. uTP와 공정성 알고리즘

BitTorrent는 네트워크 트래픽과의 충돌을 최소화하기 위해 uTP(Micro Transport Protocol)를 사용합니다. 이는 파일 전송 과정에서 다른 인터넷 트래픽과의 충돌을 줄이고, 보다 원활한 네트워크 사용을 가능하게 합니다.

또한, BitTorrent는 피어 간의 공정성을 유지하기 위해 다양한 알고리즘을 사용합니다. 예를 들어, 자주 기여하는 피어에게 더 빠르게 파일 조각을 제공하는 방식으로 피어들 간의 균형을 맞춥니다.