Tópicos Avançados em Redes de
Computadores II
Módulo VII – Redes P2P
Prof. Paulo Gonçalves
[email protected]
www.cin.ufpe.br/~pasg
CIn/UFPE
INTRODUÇÃO
1-2
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Arquiteturas de Aplicações
Cliente-servidor
Peer-to-peer (P2P)
Híbrido cliente-servidor e P2P
3
Arquitetura cliente-servidor
servidor:
Host sempre “on-line”
Enderenço IP permanente
Múltiplos servidores para
escalabilidade
clientes:
Se comunicam com o
servidor
Podem ter conexão
intermitente (nem sempre
“on-line”)
Podem ter endereço IP
dinâmico
Não se comunicam
diretamente entre eles
4
Arquitetura P2P pura
Nenhum servidor sempre “on-
line”
end systems (peers)
arbitrários se comunicam
diretamente
peers são conectados de
forma intermitente e podem
mudar de endereço IP
peer
peer
5
Híbrido: cliente-servidor e P2P
Mistura ambas as abordagens anteriores
Presença de servidores ou nós especiais
Peers precisam contactar servidores ou nós
especiais para encontrarem conteúdo ou outros
peers
Presença de peers que se comunicam
diretamente
6
Mas o que é P2P?
A peer-to-peer (or P2P) computer network is a network
that relies primarily on the computing power and
bandwidth of the participants in the network rather
than concentrating it in a relatively small number of
servers
A pure peer-to-peer network does not have the notion
of clients or servers, but only equal peer nodes that
simultaneously function as both "clients" and "servers"
to the other nodes on the network
This model of network arrangement differs from the
client-server model where communication is usually to
and from a central server
Taken from the wikipedia free encyclopedia - www.wikipedia.org
Abordagens P2P
Centralizada
Nosso foco
Não-Estruturada
Estruturada (Distributed Hash Tables - DHTs)
Exemplo de Abordagem
Centralizada e Híbrida
Introdução
1-9
Napster, Primeira Aplicação P2P Amplamente
Utilizada
A Aplicação
Aplicação P2P para a distribuição de arquivos mp3
Cada usuário contribui com o seu próprio conteúdo
Como funciona(va)
Servidor de Indexação Central
Mantém lista de todos os peers ativos e seus conteúdos
compartilhados
Armazenamento distribuído e download
Nó cliente também atua como servidor de arquivo
Todo conteúdo baixado é compartilhado
Centralized index
original “Napster” design
1) when peer connects, it
informs central server:
Bob
centralized
directory server
1
peers
IP address
content
2) Alice queries for “Hey
Jude”
3) Alice requests file from
Bob
1
3
1
2
1
Alice
Centralized model
Bob
Alice
file transfer is
decentralized, but
locating content is highly
centralized
Judy
Jane
Centralized
Benefits:
Low per-node state
Limited bandwidth
usage
Short location time
High success rate
Fault tolerant
Drawbacks:
Single point of failure
Limited scale
Possibly unbalanced
load
copyright infringement
Bob
Judy
Alice
Jane
Napster
program for sharing files over the Internet
a “disruptive” application/technology?
history:
5/99: Shawn Fanning (freshman, Northeasten U.) founds
Napster Online music service
12/99: first lawsuit
3/00: 25% UWisc traffic Napster
2000: est. 60M users
2/01: US Circuit Court of
Appeals: Napster knew users
violating copyright laws
7/01: # simultaneous online users:
Napster 160K, Gnutella: 40K, Morpheus: 300K
Napster: how does it work
Application-level, client-server protocol over point-topoint TCP
Four steps:
Connect to Napster server
Upload your list of files (push) to server.
Give server keywords to search the full list with.
Select “best” of correct answers. (pings)
Napster
1. File list is
uploaded
napster.com
users
Napster
2. User
requests
search at
server.
napster.com
Request
and
results
user
Napster
napster.com
3. User pings
hosts that
apparently
have data.
Looks for best
transfer rate.
pings
pings
user
Napster
napster.com
4. User retrieves
file
Retrieves
file
user
Napster
Central Napster server
Can ensure correct results
Fast search
Bottleneck for scalability
Single point of failure
Susceptible to denial of service
• Malicious users
• Lawsuits, legislation
Hybrid P2P system – “all peers are equal but some are more equal
than others”
Search is centralized
File transfer is direct (peer-to-peer)
Napster
Napster foi a primeira aplicação P2P. Várias outras
também surgiram em seguida …
Protocolos P2P de Download de Arquivos:
1999: Napster
2000: Gnutella, eDonkey
2001: Kazaa
2002: eMule, BitTorrent
E Hoje em Dia?
P2P-File download
Napster, Gnutella,
KaZaa, eDonkey,…
P2P-Communication
VoIP, Skype,
Messaging, …
P2P-Video-on-Demand
22
P2P-Computation
seti@home
P2P-Streaming
PPLive, ESM, …
P2P-Gaming
…
E Hoje em Dia?
P2P is not restricted to file download!
P2P Protocols:
1999: Napster, End System Multicast
(ESM)
2000: Gnutella, eDonkey
2001: Kazaa
2002: eMule, BitTorrent
2003: Skype
2004: PPLive
… TVKoo, TVAnts, PPStream, SopCast…
… Video-on-Demand, Gaming
23
Application type:
File Download
Streaming
Telephony
Video-on-Demand
Gaming
Why is P2P so successful?
Scalable – It’s all about sharing resources
No need to provision servers or bandwidth
Each user brings its own resource
E.g. resistant to flash crowds
• flash crowd = a crowd of users all arriving at the same time
Resources could be:
capacity
•Files to share;
•Upload bandwidth;
•Disk storage;…
Why is P2P so successful?
(cont’d)
Cheap - No infrastructure needed
Everybody can bring its own content (at no cost)
Homemade content
Ethnic content
Illegal content
But also legal content
…
High availability – Content accessible most of time
25
Abordagens P2P
Centralizada
Não-Estruturada
Estruturada (Distributed Hash Tables - DHTs)
Exemplo de Abordagem NãoEstruturada
Introdução
1-27
Unstructured
fully distributed
no central server
used by Gnutella
Each peer indexes the
files it makes available
for sharing (and no
other files)
overlay network: graph
edge between peer X
and Y if there’s a TCP
connection
all active peers and
edges form overlay net
edge: virtual (not
physical) link
given peer typically
connected with < 10
overlay neighbors
Gnutella: Query flooding
❒ Query message
sent over existing TCP
connections
❒ peers forward
Query message
❒ QueryHit
sent over
reverse
path
File transfer:
HTTP
Query
QueryHit
Query
QueryHit
Gnutella: Peer joining
joining peer Alice must find another peer in
Gnutella network: use list of candidate peers
2. Alice sequentially attempts TCP connections with
candidate peers until connection setup with Bob
3. Flooding: Alice sends Ping message to Bob; Bob
forwards Ping message to his overlay neighbors
(who then forward to their neighbors….)
❒ peers receiving Ping message respond to Alice
with Pong message
4. Alice receives many Pong messages, and can then
setup additional TCP connections
1.
Unstructured
Carl
Jane
Scalability:
limited scope
flooding
Bob
Alice
Judy
Unstructured
Carl
Jane
Gnutella model
Benefits:
Limited per-node state
Fault tolerant
Drawbacks:
High bandwidth usage
Long time to locate item
No guarantee on success rate
Possibly unbalanced load
Bob
Alice
Judy
Gnutella
Searching by flooding:
If you don’t have the file
you want, query 7 of your
neighbors.
If they don’t have it, they
contact 7 of their
neighbors, for a maximum
hop count of 10.
Requests are flooded, but
there is no tree structure.
No looping but packets may
be received twice.
Reverse path forwarding
* Figure from http://computer.howstuffworks.com/file-sharing.htm
Gnutella
fool.* ?
TTL = 2
Gnutella
X
fool.her
IPX:fool.her
TTL = 1
TTL = 1
TTL = 1
Gnutella
Y
fool.me
fool.you
IPY:fool.me
fool.you
Gnutella
IPY:fool.me
fool.you
Gnutella: strengths and weaknesses
pros:
flexibility in query processing
complete decentralization
simplicity
fault tolerance/self-organization
cons:
severe scalability problems
susceptible to attacks
Pure P2P system
Gnutella: initial problems and fixes
2000: avg size of reachable network only 400-800
hosts. Why so small?
modem users: not enough bandwidth to provide search
routing capabilities: routing black holes
Fix: create peer hierarchy based on capabilities
previously: all peers identical, most modem black holes
preferential connection:
• favors routing to well-connected peers
• favors reply to clients that themselves serve large number
of files: prevent freeloading
+Exemplo de Abordagem NãoEstruturada
1-40
BitTorrent
Protocolo proposto em 2001 por Bram Cohen
Usado em uma das mais populares aplicações P2P de
distribuição de arquivos
Reconhecido por
Sua forma escalável de distribuir conteúdo (arquivos grandes)
Sua capacidade de reduzir a carga em servidores
Sua capacidade de minimizar custos de distribuição de arquivos
Sua capacidade de reduzir o tempo de download visto pelos usuários
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
BitTorrent
É um sistema P2P Híbrido
maioria das interações são entre peers
necessita de interações ocasionais com um
servidor para localizar peers
Peers são organizados em uma rede
overlay conhecida como Torrent
Mas o que é uma rede overlay?
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Redes Overlay (Redes Sobrepostas)
Overlay
Underlay
43
BitTorrent
Cada arquivo sendo distribuído requer
a criação de um torrent separado
Possui um nó especial chamado
Tracker que armazena metainformações sobre peers ativos em
um torrent
Peers interagem com o Tracker
usando um protocolo no topo do HTTP
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
BitTorrent
Cada item compartilhado precisa
estar associado a um meta-arquivo
.torrent
.torrent
contém informações necessárias para o
compartilhamento
•
•
•
•
Nome do arquivo
Tamanho
Hash
url do(s) Tracker(s)
Existem sites onde os .torrents podem ser
encontrados
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
BitTorrent
Introdução
1-46
BitTorrent
Peer (par)
Host que participa da rede P2P
Leecher (sangue-suga)
Denominação dada ao host
enquanto faz o download de um
arquivo
Seeder/Seed
(semeador/semente)
Host que possui um arquivo
completo compartilhado
Seja tal host o primeiro que
disponibilizou o arquivo ou outros
que já o tenham o “baixado”
completamente
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
BitTorrent
Swarm
Nome dado ao conjunto de hosts
que compartilham o mesmo
arquivo
e.g. arquivo “constantine.avi”
sendo compartilhado por 2
seeders e 8 peers: swarm de 10
hosts
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
BitTorrent
Processo de compartilhamento
Cont.
Arquivo é disponibilizado para
download postando-se seu
.torrent
Após obter lista, peer contacta
entre 20 e 40 peers dela para
adicioná-los como vizinhos
Peer que deseja fazer o download
de um arquivo, obtém primeiro seu
.torrent equivalente
O peer então contacta o Tracker
e requisita lista de IP/porta dos
outros peers que já estão
participando em no torrent
Se o número de peers vizinhos cai
abaixo de 20, o peer deve
contactar o Tracker para obter
uma nova lista do conjunto de
peers ativos no torrent
Tracker ao receber requisição
informa uma lista de ~50
potenciais peers vizinhos que são
selecionados aleatoriamente do
conjunto de peers ativos no
torrent
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
BitTorrent
Processo de compartilhamento
(resumo)
(1) qd peer A deseja se assoaciar
ao torrent, ele primeiro “baixa” o
.torrent correspondente
(2) peer A contacta o Tracker e
requisita lista de peers já
participando no torrent
(3) Tracker envia lista de ~50
peers que estão participando no
torrent
(4) peer A seleciona, por exemplo,
35 peers da lista como seus
vizinhos e estabelece conexão
com eles
(5) Após conexões serem
estabelecidas, peer A pode iniciar
o processo de obtenção do arquivo
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
BitTorrent
Obtenção do Arquivo
Um arquivo no BitTorrent é divido
em pequenos pedaços
denominados pieces (tipicamente
de 256 KB)
Cada piece é subdivido em
unidades menores denominadas
block ou chuncks (tipicamente de
16 KB)
Peers “trocam” pieces entre eles
Qd o download de um piece é
completo, seu hash (SHA-1) é
computado e comparado com o
valor informado no meta-arquivo
.torrent
Se o hash “bate” o peer anuncia a
disponibilidade desse piece
completo aos seus vizinhos
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
BitTorrent
Obtenção do Arquivo
Na prática, a obtenção de 1 piece
é feita através da obtenção dos
blocos que compõem tal piece
BitTorrent usa conexões TCP em
pipeline. Tipicamente são
requisitados 5 blocos por vez. A
chegada de um bloco “dispara” a
requisição de outro bloco para
manter a conexão ocupada
Um peer “baixa” pieces não só dos
seeds mas também de outros
peers (leechers). Isso reduz a
carga sobre as sementes
BitTorrent usa um mecanismo
chamado de “Choking” (bloqueio) –
recusa temporária à uploads
(conexões ainda são mantidas)
Um peer pode “servir” 4 peers
simultaneamente e ele seleciona
os 4 melhores para desbloqueio
(“unchoke”) e o restante é
mantido bloqueado (“choke)”
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Mais sobre o Algoritmo de
Choke
Choke Algorithm
Cada peer “unchokes” um número fixo de peers
(default = 4)
• 3 peers com base no mecanismo de seleção de peers
denominado “tit-for-tat”
• 1 peer com base no mecanismo de selecção de peers
denominado “Optimistic unchoke”
53
Mecanismos do BitTorrent
Os mecanismos consistem
basicamente em estratégias de
seleção de peers e de pieces
Boa estratégia de seleção de peers
Maximização da capacidade do sistema
Estratégia eficiente de seleção de
pieces
Garantia de que cada peer pode encontrar
pieces que deseja através de seus peers
vizinhos
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Mecanismos de Seleção de Peers
Tit-for-Tat (TFT)
Optimistic unchoking
Anti-snubbing
Upload only
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
O que é Tit-for-Tat?
Based on the English saying meaning "equivalent retaliation" ("tip
for tap"), an agent using this strategy will respond in kind to a
previous opponent's action.
Toma lá dá cá!
Olho por olho, dente por dente
If the opponent previously was cooperative, the agent is
cooperative. If not, the agent is not
This strategy is dependent on the following conditions that has
allowed it to become the most prevalent strategy for the
Prisoner's Dilemma:
1. Unless provoked, the agent will always cooperate
2. If provoked, the agent will retaliate
3. The agent is quick to forgive
Taken from the wikipedia free encyclopedia - www.wikipedia.org
Tit-for-Tat (TFT) no BitTorrent
Estratégia usada por um peer para
preferencialmente fazer upload para
seus vizinhos que provêem a ele as
melhores taxas de download
Em qq tempo, um peer troca pieces
com um número fixo de peers vizinhos
(no máximo 4)
Um leecher preferencialmente faz
upload para os seus 3 melhores
vizinhos que o oferecem as melhores
taxas de download. Os outros
vizinhos são bloqueados (“choke”)
A cada 10 segundos, o leecher
reavalia a taxa de download dos peers
que estão enviado dados a ele
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Tit-for-Tat (TFT) no BitTorrent
Se outro peer oferece melhor taxa
de download, o leecher bloqueia
(choke) o peer com a menor taxa de
download e desbloqueia (unchoke) o
peer com essa melhor taxa
TFT tenta encorajar contribuidores e
punir “free-riders” de forma a
previnir leechers de fazerem
download sem contribuírem.
Funciona?
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Optimistic unchoking
A cada 30 segundos, um peer
desbloqueia aleatoriamente um peer
vizinho de forma independente de sua
taxa de upload
Permite a um peer descobrir
melhores vizinhos para a troca de
pieces, pois outros vizinhos podem
ter taxas melhores do que os peers
desbloqueados atualmente
Se peers usassem apenas TFT, não
haveria oportunidade para a
descoberta de peers que pudessem
oferecer taxas melhores
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Anti-snubbing
Um peer pode ser bloqueado por
peers dos quais ele estava baixando
pieces, reduzindo sua taxa de
download
Para resolver isso, qd um peer
(leedcher) nota que se passou
determinado tempo sem conseguir
pieces de um peer vizinho, o leecher
assume que ele é “ignorado”
(snubbed) por tal peer e deixa de
fazer upload para ele
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Upload only
Uma vez que um peer termina de
fazer o download completo de um
arquivo, ele se torna um seed
Como seeds não possuem nada para
baixar, eles não podem selecionar
peers baseados na taxa de download.
Em vez disso, os seeds preferem
fazer upload para peers com
melhores taxas de upload
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Mecanismos do BitTorrent
Os mecanismos consistem
basicamente em estratégias de
seleção de peers e de pieces
Boa estratégia de seleção de peers
Maximização da capacidade do sistema
Estratégia eficiente de seleção de
pieces
Garantia de que cada peer pode encontrar
pieces que deseja através de seus peers
vizinhos
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Mecanismos de Seleção de Pieces
Strict Priority
Rarest First
Random First Piece
Endgame Mode
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Strict Priority
No BitTorrent, peers se concentram
em “baixar” um piece completo antes
de requisitarem outro piece
Se um bloco é requisitado, o bloco
subsequente será requisitado
preferencialmente para completar o
download do piece o mais rápido
possível
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Rarest First
Os peers frequentemente preferem
baixar pieces mais raros dado o
conjunto de seus vizinhos – rarest
first
Cada peer mantém uma lista de pieces
que cada vizinho possui
A lista é atualizada cada vez que a
cópia de um piece é disponibilizada
por seus vizinhos
O peer então constrói uma lista de
pieces mais raros (em menor quantidade) e faz
o download deles
Consequência: aumenta a chance de
um peer poder colaborar oferecendo
pieces que outros desejam
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Rarest First
Consequência: reduz sobrecarga na
semente
A saída de uma semente não tira de
outros peers a oportunidade de
download (pieces são distribuídos
para outros leechers)
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Random First Piece
Exceção ao Rarest First quando um
peer se associa a um torrent
Como o peer não possui pieces é
importante que consiga um piece
completo o mais rápido possível por
causa do TFT
Para isso, o novo peer escolhe um
piece aleatoriamente para baixar
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Endgame Mode
Usado por peers que estão quase
terminando um download
Se um piece é requisitado de um peer
com baixa taxa de transferência, o
tempo de download será prolongado
Solução: peer requisita a todos os
seus vizinhos blocos que ele ainda não
recebeu
Uma vez obtido um bloco, o peer
cancela a requisição daquele bloco
feita a outros peers vizinhos,
permitindo redução no desperdício de
banda-passante e recursos por causa
de doanloads redundantes
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Pesquisas sobre o BitTorrent
1-69
Avaliação de Desempenho: 3 focos
básicos
Medidas Reais
Participação em torrents reais
Alteração de clientes para
“logar” informações a serem
avaliadas
Captura de pacotes em
backbones
Simulação
Ambiente controlado
Maior flexibilidade para avaliar
diversos mecanismos do
BitTorrent
Mas abstrações precisam ser
feitas geralmente
Modelos Analíticos
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)
Tópicos Avançados sobre
BitTorrent
Melhorias na Topologia Overlay
Proximidade física entre peers
Redução de tráfego entre ISPs (Cross-ISP traffic)
Melhorias no Mecanismo de Troca de Pieces
Melhoria da colaboração entre peers
Melhoria da justiça (fairness)
Como lidar com “Free-Ridings”?
1-71
Copyright © 2010 Paulo Gonçalves (Cin/UFPE)