* 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. *
P2P
Properties
- central databse가 없다.
- 계층적 구조가 아니다. (모든 노드가 클라이언트/서버가 될 수 있다.)
- 확장성이 있다.
- 모든 피어에 접근할 수 있다.
- Unreliable하다.
1. Napster
냅스터는 기본적으로 hybrid p2p 방식이다.
이 방식에서 서버는 diretory의 역할만 한다고 했었다.
- 피어가 연결되면 central server에 IP address와 content를 알린다.
- Almost distributed system이다. 파일의 위치는 centralized 되어있지만, 직접적인 통신은 peer간에 이루어진다.
- 쿼리가 빠르다.
- 그러나 Server-Client의 고질적인 문제, 서버가 고장나면 아무것도 할 수 없다는 점이 문제점이다.
2. Gnutella
- fully distributed p2p protocol(pure p2p)방식이다.
- public domain protocol
- 자체적인 protocol을 가지고 있다. (ping/pong : 그룹 확인, query/query hit : search)
때문에 네트워크안에서 건설된 하나의 네트워크라고 볼 수 있다.
Gnutella는 크게 두가지 과정으로 나뉜다.
1. Join
2. Search
Join
1. 참여 하고싶은 User A는 GnuCache서버에 연결해 Gnutella nets에 연결되어있는 peer의 리스트를 요구한다.
2. GnuCache는 Gnutella nets에 있는 node들의 리스트를 return하고 User A는 그 중 하나(User B)를 선택한다.
3. User A는 User B에게 Gnutella nets에 join하기 위해 요청을 보낸다.
4. User B는 User A에게 OK를 보내고 비로소 User A는 Gnutella nets의 part가 되었고 그중 하나와 연결되었다.
5. Gnutella에 연결된 peer들은 주기적으로 자신에게 연결된 모든 neighbor들에게 ping메시지를 보낸다. 이 ping메시지는 pong메시지로 응답되어 오고 또한 상호 연결된 모든 servent로 퍼져 나아간다.
6. 5의 과정에서 User A는 User C로부터 온 ping메시지를 통해 User C에대한 정보를 알게되고 연결한다. 일반적으로 Gnutella의 servent들은 다른 servent 약 3개에 연결된다.
Search
- TCP 커넥션을 통해 쿼리메시지가 전송된다.
- 피어는 자신에게 연결된 피어들에게 쿼리메시지를 연달아 전송한다.
- 만약 정보가 있다면 query hit메시지를 반환하고 지금까지 온 경로를 통해 전송된다.
- 이러한 쿼리메시지를 연결된 모든 peer를 통해 계속 보내면 비효율적이기 때문에 자신으로부터 몇단계까지만 보낼지 리밋을 걸어놓는다.
매우 심플하고 좋은 방식이지만 몇가지 문제점이 있다.
1. 앞서 말했듯이 연결된 모든 peer들에게 쿼리메시지를 보내면 excessive한 쿼리 traffic이 문제가 된다.
- limited-scope query flooding을 통해 해결
2. overlay네트워크에 대한 유지가 필요하다.
- 만약 연결된 peer사이간에 만들어진 TCP커넥션에 아무런 정보가 흐르지 않아도 연결을 유지시키고 있어야 한다.
3. Free riding
- 대부분의 Gnutella user들은 정보를 받기만 할뿐 다른 peer에게 정보를 제공하지 않는다.
- 상위 1%의 host가 요청하는 정보를 찾기위해 47%의 응답이 필요하다.
Hierarchcial Overlay
따라서 좀더 보완된 overlay에 대한 아이디어가 나왔다.
- 각 peer는 그룹의 리더거나 그룹안에 속한 peer이다.
- 그룹 리더간의 TCP커넥션과 리더와 그 자식들간의 TCP커넥션만 존재한다.
- 그룹 리더는 어떤 자식에게 해당 정보가 있는지 알려준다.
Client-Server vs P2P
P2P에 대해 알아봤으니 Client-Server와 P2P에서의 이론적인 속도비교를 해보자.
예제는 다음과 같다.
초기 서버에서 다른 N개의 컴퓨터로 파일을 보내는데에 얼마나 시간이 걸리는가를 기준으로 하겠다.
앞서 transmission delay는 (전송할 데이터의 크기/bandwidth) 였다.
Client-Server
일단 서버가 네트워크에 N개의 파일을 업로드 해야한다.
이때 걸리는 시간은 N*F/u(s)이다.
또한 각 클라이언트 i가 파일을 다운로드 하는 속도는 F/d(i)일 것이다. 클라이언트들이 각각 다운로드 하는 것은 순차적이 아닌 동시에 일어날 수 있기 때문에 그중 가장 오래걸린 시간은 F/min(d(i)) 일것이다.
즉, 문제에서 요구한 시간은 (time to distribute F to N clients) 다음과 같다.
즉 N이 매우크다면 F/Min(d(i))는 무시 될것이고 최종 시간은 NF/u(s)가 될것이다.
P2P
가정 : 서버는 하나의 copy만 네트워크에 보내면 된다.
-> F/u(s)
클라이언트 i는 다운로드 하는데 F/d(i)만큼의 시간이 소요된다.
또한 그럴순 없지만 어떤 한 peer에게 서비스 해줄 수 있는 매우 이상적인 상황은 서버와 모든 peer들이 서비스를 해줄 수 있는 상황이다. 즉 ideal upload rate = u(s) + (u(1)+u(2)+...u(N))이 될 것이다.
즉, 문제에서 요구한 시간은 최소 다음과 같아야 한다.
어디까지나 이상적인 best case에서의 상황이고 실제로는 다를 수 있다.
즉, N이 매우커지게 되면 다음 식만 영향을 받는다.
이 식은 분모와 분자 모두 N이 커지면 값이 커지기 때문에 CS에서 N에 따른 time의 증가량보다 P2P에서의 증가량이 작다는 것을 유추할 수 있다.
실제로 N이 커짐에 따라 P2P와 CS에서의 time을 측정한 결과이다.
P2P의 time증가량이 더 작은것을 볼 수 있다.
BitTorrent
우리가 아는 그 토렌트가 맞다.
토렌트는 P2P네트워크를 통해 이루어진다.
- 트래커는 토렌트에 가입한 피어들의 정보를 가지고 있다.
- 토렌트는 피어들이 속한 집합이다.
- file은 256KB의 chunk로 쪼개진다.
- 처음 토렌트에 join한 피어는 아무런 chunk도 가지고 있지 않다. 하지만 토렌트를 이용해 다운로드 하면서 다운로드 받았던 chunk들을 축적해 나아간다.
- 축적해놓은 chunk들을 다른 피어들에게 서비스해줄 수 있다.
- 다운로드를 끝낸 피어는 토렌트 그룹을 나갈 수도 있고 유지한 채 다른 피어들에게 서비스를 해줄 수도 있다.
Requesting chunks
- 각 피어는 서로다른 chunk의 set을 가지고 있을 것이다.
- 주기적으로 피어는 자신의 negibor들에게 그들이 가지고 있는 chunk의 리스트를 물어본다.
- rarest firts원칙으로 요청을 한다
: 만약 A가 chunk1, chunk2, chunk3 / B가 chunk1, chunk 3, chunk 4 / C가 chunk1, chunk 3, chunk4를 가지고 있다면, 가장 귀한 chunk2부터 요청을 하는 것이다. (만약 A와 연결이 끊어져도 chunk1과 chunk3는 다른 피어에게 있을 확률이 높으므로)
Sending chunks
- 자신에게 연결된 모든 peer들에게 서비스를 제공하지 않고 자신에게 가장 많은 서비스를 해줬던 상위 peer 4개에게만 서비스를 해준다. 이때 이 평가과정은 10초마다 이루어진다.
- 그러나 만약 초기진입(아무런 chunk를 가지고 있지 않은)한 peer들은 서비스를 제공해줄 정보가 없기 때문에 이런 peer들에게도 서비스를 제공해주기 위해 30초마다 랜덤으로 하나의 peer를 선택해 서비스를 제공해준다.
- 위 과정을 통해 P2P에서 발생하는 free-riding을 예방할 수 있다.
Bit-torrent방식은 P2P의 문제점들을 해결한 새로운 방식이다.
DHT(Distributed Hash Table)
DHT는 hybrid P2P방식에서 cetnralized된 directory server의 문제점을 해결하기 위해 directory table을 각 노드로 분산시켜 저장하게 하는 방식이다.
- database는 {object ID, value}형태의 pair를 저장한다.
- object id는 key가 되고 key를 통해 value를 찾는다.
- 테이블이 분산되어 있기 때문에 각 peer는 전체 네트워크의 어떤 부분만 알고 있다. 때문에 effective하고 scalable한 프로시져를 통해 쿼리를 날린다.
How to assign keys to peers?
- 각 key를 정수로 변환한다.
- 변환한 정수를 각 피어에게 할당한다.
- 가장 가까운 key가 할당된 peer에게 (key, value)를 put한다.
- 일단 peer와 object에 대한 ID는 같은 범위를 가진다.
- 각 노드와 item에 대한 key를 할당하고, 각 노드들을 연결한다. 그 후에 아이템을 assign하는 방식으로 접근한다.
예시를 들자면 다음과 같다.
각 peer들과 object들이 해쉬를 통해 ID를 할당 받은 모습이다.
현재 노드들은 다음과 같은 ring구조로 연결되어 있다.
그리고 object들을 자신의 ID보다 크거나 같은 ID를 가진 peer에 저장한다.
예를들어 movie1.avi는 12번의 ID를 가졌는데 12보다 크거나 같은 ID를 가진 node는 csee.handong.edu이므로 해당 peer에 아이템을 저장하는 것이다.
이런 방식을 이용하면 현재 그룹에 속해있는 peer가 빠질 때나 새로운 peer가 들어올 때 효과적인 처리를 할 수 있다.
'컴퓨터 네트워크 > Computer Networking 정리' 카테고리의 다른 글
| CH3 : Transport Layer (1) (0) | 2021.10.17 |
|---|---|
| CH2 : Application Layer (6) (0) | 2021.10.17 |
| CH2 : Application Layer (4) (0) | 2021.10.16 |
| CH2 : Application Layer (3) (0) | 2021.10.16 |
| CH2 : Application Layer (2) (0) | 2021.10.16 |
