Ch2-5) P2P application

 

P2P architecture은, 항상 켜져있는 infrastructure 서버에 최소한으로 의존하고, 간헐적으로 연결되는 호스트 쌍(peer)이 서로 직접 통신하는 방식이다.

 

 

 

• 또한 네트워크에 연결되어있는 end system끼리 직접 연결되어 데이터를 주고받는다
• 이때 P2P는 self scalability의 특성을 보유하는데, 이는 새로운 피어가 네트워크에 참여하면 새로 참여한 피어는 단순히 resource를 공유받는 역할만 하는 것이 아니라, 다른 피어들에게 데이터를 제공하는 역할도 동시에 수행한다
  • 이러한 특징 덕분에, 네트워크의 resource가 증가하면서도, 동시에 service demand와 provide capacity 또한 증가하는 self scalability의 특성을 갖게 된다.
• 뿐만 아니라 imtermittently하게 연결되는 피어들은, IP 주소가 동적으로 변경되는 특성을 갖는다.
  • 그래서 복잡한 management system이 필요

⇒ 그럼, p2p 아키텍쳐가 어떻게 self scalability를 갖는지, 직접 예시를 통해서 알아보자.

 

 

 

다음과 같은 사례를 생각해보자.

How much time to distribute file (size F) from one server to N peers?

• 만약 서버가 N 피어에게 F의 사이즈를 가진 파일들을 모두 전송해야하는 데 걸리는 시간을 측정한다고 하자.
• 서버와 피어들은 접속 링크로 인터넷에 연결되어 있다.
  • 서버의 접속 링크 업로드 속도를 u(s)로, i번째 피어의 접속 링크 업로드 속도는 u(i)로,그리고 i번째 피어의 접속 링크 다운로드 속도는 d(i)로 나타낸다.

이때 인터넷 코어는 모두 풍부한 대역폭을 가지고 있으며, 네트워크의 모든 기능들이 이 distribution에 참여한다고 생각하자.

• 하나의 파일을 전송하는데 걸리는 시간 = F / u(s)일 것이다.
• ⇒ 모든 파일을 전송하는데 걸리는 시간 = NF / u(s)임을 알 수 있다.
• 또한, client중 가장 느린 download capacity를 가진 놈의 download capacity를 d(min)라고 하자.
• → 그럼 이때 가장 느린놈의 download time = F / d(min)이다.

그렇다면, Client-server 방식을 통해서 N명의 사람에게 F를 나누어 주려면, 이 distribute time을 D라고 한다면, 최소한 다음과 같은 시간이 필요하다

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

• 만약, N이 충분히 커지는 대형 system에서는 네트워크 부하가 선형적으로 증가함을 알 수 있다.

그렇다면, P2P 방식에서는 어떨까?

• 우선, 분배가 시작되면 서버만이 파일을 보유하고 있고, 서버는 적어도 한 번 파일의 각 비트를 피어 커뮤니티로 전송해야 한다.
  • 딱 한번만 하면 되는게, 이제는 피어들이 서로 파일을 전송할 수 있기 때문임.
  • 따라서 최소 전송 시간은 F / u(s)이다.
• 또한,아까와 마찬가지로 다우놀드 속도가 가장 느린 놈의 download capadity를 d(min)이라고 하면
• 가장 느린놈의 donwload time = F/d(min)이다.
• 이때 시스템 전체의 업로드 capacity는 , u(s)와 모든 u(i)들을 합친 것이므로, 이를 u(total)이라 하자.
  • 시스템은, 각 피어들에게 F만큼의 Data를 전송해야하고, 이는 u(total)보다 빠를 수 없다.
  • 그렇기 떄문에, 아무리 각 피어들이 파일 전송에 기여한다고 해도,
  • 최소한의 전송 시간 = NF / u(total)임을 알 수 있다.

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

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

둘의 N의 크기에 따른 부하시간을 그래프로 표현해보면 다음과 같다.

 

 

 

D c-s에서는, N의 크기가 증가함에 따라 선형적으로 D가 증가하는 반면,

P2P에서는 N의 크기가 증가함에 따라 피어들에게 전체 네트워크 bandwith가 분산되면서, 그래프가 완만해졌다.

→ 결국, 네트워크의 총 대역폭이 피어들이 제공하는 업로드 대역폭 만큼 증가한 것이다.

→ 이러한 P2P file distribution system을 활용한 대표적인 사례가 바로 “bitTorrent”이다.

BitTorrent

• BitTorrent란, file distribution을 위한 유명한 application layer protocol이다.
• Torrent란, 비트토렌트 용어로 특정 파일 분배에 참여하는 모든 peer들의 모임을 뜻한다.

 

 

 

• Torrent에 참가하는 피어들은 서로에게서 같은 chunk(256KB) 를 다운로드 한다.
  • 처음 가입한다면, 그 피어한테는 chunk가 없지만, 시간이 지나면서 chunk를 쌓을 수 있다.
  • 각 peer가 chunk를 다운로드 할 땐, 다운로드 함과 동시에 chunk를 다른 peer에게 업로드한다.
  • 만약 한 peer가 전체 파일을 얻으면 토렌트를 떠나거나 (selfishly) 토렌트에 남아있을 수 있다.(altruistically)

→ 그렇다면, 이러한 peer들은 서로를 어떻게 인식하는 것일까?

⇒ Torrent는, 최소 한명한테는 file하나에 해당하는 chunk가 모두 존재해야한다? (x)

Tracker

• 각 토렌트는, “Traker”라는 infrastructure node를 보유하고 있다.
  • 한 피어가 토렌트가 가입할 때는, 이 Tracker에 자신을 토렌트에 등록하고, 자신이 아직 토렌트에 남아있음을 알려 트레커가 피어 목록을 추적할 수 있도록 한다.
• 위의 사례에서, 만약 Alice가 처음 토렌트에 가입했다면, Tracker에게 자신이 가입했음을 알린다.

→ 이때 Tracker은, 참여하고 있는 peer 목록중에 임의의 subset을 선택해 subset에 속한 피어의 IP address list를 Alice에게 보낸다.

• 이 목록을 얻고 나면 Alice는 목록의 peer들과 TCP 연결을 맺고, 성공적으로 연결을 맺은 peer은 “neighbors”라고 부른다.
• 토렌트의 이러한 P2P 특성 덕분에 시간이 지남에 따라 피어들 중 일부는 떠나고, 피어의 이웃 피어들은 시간에 따라서 변한다
  • 이렇게 피어가 변동하는 것을, “Churn”이라고 부른다.

Rarest first / Tit-for-Tat

• 어느 한 순간에는, 피어들은 각각 다른 종류의 chunk를 가지고 있을 것이다.
•  
• Torrent에서는 주기적으로 neighbors에게 Chunk list를 요구하고, 다른 peer들이 어떤 chunk를 가지고 있는지 알게 된다.

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

1. 이웃으로부터 어느 청크를 먼저 요구할 것인가?
2. 이웃들 중 어느 피어에게 청크를 요청할 것인가?

• 이떄 토렌트 에서는 “Rarest first”기법으로 청크를 요구하게 된다.
• 갖고 있지 않은 chunk 중 이웃 가운데 가장 드문 chunk를 받기로 결정하고, 이를 가장 먼저 요구한다.
  • 이 방법을 통해 rare한 chunk들의 distribution 속도가 빨라져, 각 chunk의 복사본 수가 비슷해진다.

→ 그렇다면, 송신자의 입장에서는 여러개의 요청이 들어왔을 때 어느 요청을 가장 먼저 처리해야할지 생각해야 한다. 이 알고리즘이 바로 “Tit-for-Tat”알고리즘이다.

 

 

• Tit-for-Tat 알고리즘에서는, Alice에게 가장 “빠른 속도”로 데이터를 제공하는 이웃에게 먼저 답장한다.
• Peer들은 10초에 한 번씩 비트를 수신하는 속도를 측정하고 가장 빠르게 전송하는 4명의 peer를 결정한다.
  • 이 4명의 피어가 가장 우선순위를 갖게 되는 것이다
  • 이때 토렌트 용어로 이 4명의 peers는 “Unchoked”(활성화됐다)라고 한다.

→ 근데 이렇게 하면 peer가 고정될 수도 있으니, 30초에 한번 씩 임의의 peer에게 chunk를 전송한다.

• 이때 이 peer은 “optimistically unchoke”되었다고 한다.
• 즉, 이제 Alice는 임의의 peer에게 활성화 될 수 있고, 활성화가 된다면 임의의 peer도 앨리스를 활성화할 수 있다. ( Alice가 전송하는 데이터 속도가 충분히 빠르다면? )

→ 이러한 방식으로, 5명의 피어를 제외한 이웃은 비활성화 되어, 어떤 청크도 교환하지 않는다.

(Choked by Alice = Do not receive chunks from her)