[컴퓨터네트워크] 응용계층 part3-3

P2P 파일 공유

• 간혈적 접속
• P2P 어플리케이션이 파일을 가지고 있는 피어 정보 화면에 보여줌
• Alice는 특정 피어 Bob을 선택
• Bob의 pc에서 Alice 노트북으로 복사 : HTTP
• 앨리스가 밥으로부터 파일을 받는 형태
• 또 다른 피어가 앨리스로부터 업로드 제공

P2P라고 하는 것은 그 피어가 동작상태에 따라서 클라이언트로도 서버로도 동작을 할 수 있습니다. 상황에 따라서 클라이언트와 서버의 역할을 바뀌는 것입니다.

 

순수 P2P의 구조

서버가 없는 피어들과의 동작입니다.

 

end-system끼리의 직접적인 커뮤니케이트로 계속해서 변화하는 IP주소를 가지고 있으며 확장성이 높다는 특징이 있습니다. 따라서 이제 피어들이 계속적으로 변화하는 IP주소, 간혈적인 접속의 특징을 가지고 있기에 management가 엄청 복잡합니다.

 

p2p의 대표적인 예가 비트토렌트, 스트리밍, voip 등이 있습니다.

 

P2P 통신에서 첫번째로 살펴볼 주제는 Client-Server와 P2P의 파일 지연을 비교를 해보는 것입니다. 여기서 비교해볼것은 얼마나 많은 시간을 분배하는데 걸리는지 확인해보게씃ㅂ니다.

 

n개의 피어들이 있다고 가정을 하고 네트워크의 서버 업로드 대역폭을 us라고 하고 각각 피어들의 대역폭을 u1, d1, u2, d2, ui, di라고 가정을 해봅시다.

 

클라이언트 - 서버 방식 걸리는 시간

서버 N file 전송

 

서버가 하나의 파일을 전송하는데 걸리는 시간 F/Us

서버가 N번 업로드 하는데 걸리는 시간 : NF/Us

 

클라이언트들은 서버로부터 다운로드 받기 위해서 걸리는 시간

• F/dmin
• 시간이 많이 걸리는 것은 다운로드 대역폭이 가장 낮은 시간일 것입니다. 

이 네트워크가 클라이언스 서버 방식으로 했을 떄 

이정도 시간이 걸린다는 것을 알 수 있습니다. 이는 N에 선형적으로 증가해서 비례합니다.

 

P2P가 걸리는 시간 

클라이언트 서버방식보다는 계산이 복잡합니다.

 

처음에는 서버 F에 파일이 존재하기에 서버가 최소한 한번은 F를 업로드 해주어야 합니다. 이는 F/us가 걸립니다.

 

이제 피어들이 다운로드 받는데 오래걸리는 것은 F/dmin입니다. 이제 P2P의 특성은 피어들끼리 직접적을 분배하는 과정은 array형태로 네트워크를 분배해야 하는 것은 NF bits가 분배되어야 하고

 

전체 업로드 대역폭은 : 서버 업로드 대역폭 + ui의 합입니다.

 

P2P방식에서는

서버가 한번 업로드 하는 시간, PEER 가 다운로드 받는 시간, 전체 업로드/분배해야하는 파일 사이즈 NF비트 이렇게 맥시멈값이 분배시간이 됩니다.

 

이것이 일반적으로 분배시간이 됩니다.

 

클라이언트 업로드 VS P2P

Client upload rate = u, F/u = 1 hour, us= 10u, dmin>=us

 

클라이언트 방식은 피어의 개수가 증가함에 따라서 선형적으로 증가를 합니다. 그치만 p2p방식은 피어의 개수가 증가함에 따라서 분배시간이 아주 완만하게 증가하는 것을 볼 수 있습니다.

 

비트토렌트

 

파일을 잘게 쪼개서 분배하는데 이는 256KB로 쪼개서 분배합니다. 이제 file chunk를 전송하고 수신하는 것입니다. 1메가를  256kb로 잘게 쪼개서 전달하는 방식을 사용합니다.

 

기본적인 네트워크 구조는 기반 구조 노드로 tracker가 있습니다. 이는 관리하기 위한 하나의 노드입니다. 비트토렌트에서 참여한 피어를 관리하고 

 

torrent는 피어의 그룹입니다.

 

어떤 사용자 Alice가 비트토렌트를 이용해서 파일을 공유하고 싶다면 기반 노드에 접속을 해서 기반 노드로부터 피어의 리스트를 받아옵니다. 그 피어리스트를 이용해서 참여한 목록을 보고 앨리스가 연결을 만들면 토렌트가 참여를 하면 됩니다.

 

그럼 앨리스가 공유를 할 수 있는 것입니다.

 

토렌트 조인 방법

트랙커에 등록해서 토랜트를 이으면 됩니다. 상호작용하면서 모을 수 있는 것입니다. 비트토렌트 역시 p2p방식이기 때문에 클라이언트와 서버 역할을 동시에 할 수 있습니다.

 

Churn

피어가 계속 들어갔다 나갔다를 반복하는 것, 필요한 시점에 참여를 하고 끝나면 p2p를 빠져나가는 것을 말합니다. 이런 형태를 Churn이라고 합니다.

 

이 churn이 selfishly 특정을 가집니다. 대부분의 피어가 p2p를 종료시키고 빠져나가는 이기적인 특성을 관리하기 때문에 이것을 어떻게 관리하는지가 난제입니다.

 

Chunk를 요청하면 다른 chunk를 가지고 peer는 자신의 이웃 피어들에게 chunk 리스트를 요청하고 자신이 가지고 있지 않은 것의 request를 보냅니다. 

 

이는 이웃들 중에서 가장 적은 복사본을 가진 chunk 를 요구합니다. 토렌트에서 각 chunk의 수가 대략적으로 동일하게 합니다.

 

가장 빠른 속도로 데이터를 제공하는 이웃에게 우선순위를 부여

• 10초마다 재선정 가장 빠르게 전송하는 peer 4명에게 전송
• 30초마다 랜덤으로 선택 후 전송

 

P2P 정보검색

정보검색을 하기 위한 p2p서비스에서 인덱스는 peer의 location과 정보에 대한 location입니다.

 

File sharing

• 인덱스는 파일이 공유하고 있는 로케이션을 동적 추정
• 자신이 가지고 있는 인덱스를 알릴 필요가 있고
• 피어들은 파일이 어디에 있는지 인덱스를 검색하면 됩니다.

 

Instant messaging

• 인덱스 = username + location 매핑
• 어플리케이션을 실행하면 자신의 위치에 대한 location을 알릴 필요가 있습니다.
• 피어들은 ip address를 알아내기 위해 index 검색을 수행합니다.

P2P : Centralized index

Napster

1. 피어가 어플리케이션을 실행하면 자신의 정보를 알림 (ip address + content)
2. 본인이 검색하고 싶은 것을 directory server로 검색
3. 피어의 리스트를 요청자에게 알려주고 요청자가 해당 피어에게 요청을 하면 됩니다. 

P2P Centralized 문제점

• Single point of failure / centralized directory가 오류 발생 > 전체 오류
• 병목지점이 결국 centralized
• p2p에서 Copyright 문제 

피어들간의 파일 전송은 분산화되어 있지만 컨텐츠를 찾는 과정은 매우 중앙집중화되어 있습니다.

 

순수 P2P : Gnutella

완전 분산이면서 centralized 서버가 없는 것입니다.

 

overlay network : 가상의 컴퓨터, graph

가상의 네트워크를 정의합니다. 이를 overlay 중첩 네트워크입니다. 이를 모델링하기 위해 사용하는 것이 그래프입니다.

• 간선은 두 TCP사이 Connection이 있으면 피어 x와 y사이 간선 표기 가능
• 모든 active peer들은 정점으로 표현 / 간선이 하나의 overlay net 구성
• Edge는 물리적인 링크가 아님 

Gnutella는 centralized가 없기에 검색을 위한 쿼리를 이웃 피어에게 전달하고 그 쿼리를 본 이웃피어 역시 전달을 해나가는 것이 gnutella 방식입니다. 

 

자신의 이웃피어들에게 계속해서 꼬리를 물고 보내는, 이렇게 전파를 해가면서 가지고 있는 피어를 찾으면 이를 Queryhit로 역경로로 전달이 됩니다.이 파일의 전송은 피어들간 직접적으로 이루어집니다. 

 

Gnutella peer joining

1. 피어x가 조인을 하기 위해선 gnutella가 이미 참여한 다른 피어를 찾기 (candidate peer의 리스트 사용)
2. 피어x가 TCP connection을 만들기 위해 계속 시도 (피어 y와 커넥션)
3. 그럼 피어y에게 Ping message를 보낸비다. y는 핑 메세지를 이웃 피어에게 전파해나갑니다.
4. 핑 메세지를 수신한 모든 피어들은 동일한 메세지로 응답해야 합니다.
5. X는 많은 피어들로부터 Pong을 받습니다. 그럼 그 피어들과 TCP connection을 하면 됩니다.

이것이 Join의 과정입니다.

 

KaZaA

그룹 리더가 있고 거기에 연결된 방식이기에 centralized 구조라고 볼 수 있습니다. 두 가지가 결합된 방식입니다.

 

1. 각 파일에는 해시와 설명자가 있다.
2. 클라이언트는 키워드 검색을 그룹 리더에게 보낸다.
3. 그룹 리더는 검색 결과를 반환한다.
4. 각 결과에는 메타데이터, 해시, IP 주소가 포함된다.
5. 그룹 리더가 다른 그룹 리더에게 쿼리를 전달하면, 그들도 결과를 반환한다.
6. 클라이언트는 다운로드할 파일을 선택한다.
7. HTTP 요청은 원하는 파일을 가진 피어들에게 해시를 식별자로 사용해 전송된다.

 

즉, KaZaA의 검색 과정은 클라이언트가 그룹 리더에게 파일 검색을 요청하고, 그룹 리더는 검색 결과를 반환하며, 그 결과를 바탕으로 클라이언트가 파일을 선택해 다운로드하는 구조입니다.

 

Skype

centralized + p2p가 결합된 방식

독점적인 application 프로토콜로 상세사항이 공개되어 있지 않습니다. skype client가 있으면 supernode(SN)에 연결이 됩니다. 이것이 Centralized 역할을 하고 또 다른 것이 있으면 Supernode끼리 p2p방식으로 연결된 방식입니다.

 

스카이프에서 Index는 username을 IP address로 매핑하는 정보입니다.  클라이언트들을 관리하기 위해서 skype login server를 가지면서 관리를 더 용이하게 합니다.

 

NAT 뒤에 클라이언트가 존재할 때

공유기 기술은 여러 호스트들이 공유해서 사용하는 방식입니다. 그래서 Net이라는 기술이 내부 피어의 call을 하는 것이 어렵게 됩니다. 외부에 있는 피어가 net의 내부에 있는 피어에게 할 때 NAT이 방해합니다.

 

이때 Relay 노드를 사용합니다. 이는 relay 노드를 통해 supernode없이도 사용할 수 있는 것입니다.

 

DHT

DHT : 분산 P2P 데이터 베이스

이 데이터베이스는 (key, value) 쌍을 저장을 합니다.

p2p에서 컨텐츠들을 분배할 때 비디오 파일을 분해한다고 할 때 key는 영화 타이틀이 될 것이고, value는 그것의 ip주소가 될 것입니다.

 

Hash Table

이 키의 숫자 표현, 수치 표현에서 어떤 검색이나 저장을 하는 것이 편리합니다. 문자의 string을 저장하기보다 수치적인 형태로 변경해서 그 값을 저장하는 방법을 많이 씁니다. original 키가 string 값이면 그것을 hash해서 나온 값을 저장합니다.

• P2P에서 (key, value)를 분산시켜서 저장
• 피어가 DHT의 key값을 가지고 쿼리 -> 일치하는 Value가 반환
• 삽입같은 연산자도 지원 (insert)
• 각각의 피어들은 적은 수의 피어들만 알고 있으면 됩니다.
• churn (들어오고 나가는) 것에 견고합니다.

Dht에서 해결해야 하는 중요한 문제

ans) key 값을 피어에게 어떻게 할당 할 것인가?

• 각각의 key를 정수로 전달
• 각 peer에게 정수를 할당
• key에 가장 가까운 peer에게 (key,value)쌍을 포함시킴

 

DHT 식별자

• 어떤 n에 대해 [0, 2^n-1]의 범위의 정수 식별자가 피어에 할당이 됩니다. 각 식별자는 [0,2^n-1]의 정수값입니다 각 식별자는 n bits로 표현됩니다.
• key도 같은 범위 내의 정수일 것을 요구합니다. 정수 key를 얻기 위해 original key를 해쉬합니다. 
• key = hash("Led Zeppelin lV")
• 명칭에 해쉬 테이블은 해시는 오리지널 키를 해시함수를 이용해서 숫자값으로 변환한다는 것에서 해시를 씁니다.

규칙

가장 가까운 ID를 가진 Peer에게 key 할당, 가장 가까운의 의미는 key의 바로 다음 후임자(immediate successor)입니다. 

n=4; peer : 1,3,4,5,8,10,12,14

• key = 13, then successor peer = 14
• key = 15, then successor peer = 1

각 피어는 다음 후임자와 바로 직전의 전임자만을 알고 있습니다. 이는 overlay network에 해당합니다.

 

키에 대한 할당 검색에 있어서 N개에 있어서 복잡도는 O(N)으로 표현을 할 수 있습니다. 

 

지름길을 이용할 수도 있습니다.

 

Peer churn

• 직전의 피어와 그 다음 피어만 알고 있지만
• 두개의 연속된 후임자의 주소를 알아야 churn을 다룰 수 있습니다.
• 피어들은 peerchurn에 대해서 대처할 수 있는데 주기적으로 key 메세지를 보내서 확인해야합니다.
• 만약 후임자에게 응답이 없다면 네트워크에서 빠져나간 것으로 판단합니다.

만약 자신의 다음 후임자가 없어졌을 때 그 다음의 후임자에게 연결을 하는 방식입니다.