Julho - 2012Fabrício Murai – fabricio@land.ufrj.br1/22 Sobre dois fenômenos em redes P2P do tipo...

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 1/22

Sobre dois fenômenos emredes P2P do tipo BitTorrent

Fabrício Murai

CTD 2012

Orientadores: Daniel R. FigueiredoEdmundo A. de Souza e Silva

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 2/22

Motivação

Quero disponibilizar um arquivo na InternetArquitetura cliente-servidor

(centralizado)

Arquitetura par-a-par

(distribuído)

GRANDE POPULAR

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 3/22

Aplicação P2P: BitTorrentEficiente, mecanismos simples

Arquivo é dividido em pedaços

Pedaços trocados entre pares

Não transmite p/ todos simultaneamente

– reciprocidade

– aleatória (otimista)

A

B

CD

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 4/22

Clusterização em redes heterogêneas

“Rico troca c/ rico, pobre c/ pobre

O que é uma rede heterogênea?

E clusterização?

Cabo10M

ADSL2M

Cabo5M

Discada56K

Cabo256K

Cabo512K

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 5/22

“Rico troca c/ rico, pobre c/ pobre”

BT induz clusterização [Legout 2007]

Clusterização aumenta vazão [Bharambe 2006]

Cabo10M

ADSL2M

Cabo5M

Discada56K

Cabo256K

Cabo512K

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 6/22

Não é devido a regras explícitas

Interações são locais

Objetivo: entender como mecanismos do BT levam à clusterização

Por que clusterização acontece?

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 7/22

Abordagem

Modelos p/ dinâmica de conexões

Modelo de simulaçãoCaptura aspectos fundamentais

variação de cenário e parâmetros

Ex.: número de usuários,força da comp. aleatória

Modelo simplificado

Analiticamente tratável

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 8/22

Modelo de simulação

Número de usuários

“Quem conhece quem”Grafo de conhecimento

Capacidades de transmissão

“Quem está servindo quem”Grafo de serviço

– reciprocidade

– aleatória

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 9/22

Resultados principais

1) Sem aleatoriedade,Baixa clusterização

Medida de C

lusterização

Tempo

2) Clusterização cresce rapidamente mas não atinge níveis altos

Aleatoriedade

+

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 10/22

Downloads heterogêneos em redes homogêneas O que é uma rede homogênea?

E download heterogêneo?

Mais predominante em redes pouco populares

1 hora

30 min40 min

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 11/22

Arquivos poucos populares

58%15%

27% 1 a 45 a 910+

Torlock.comNov 2011

Por que estudar?

– Popularidade decai exponencialmente [Guo '07, Kaune '10]

– Maior parte dos arquivos num repositório é pouco popular [Hossfield '11, Murai '12]

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 12/22

Como estudamos esse fenômeno?

Simulações

– Modelo de simulação muito detalhado

Experimentos reais

– Cliente real baseado em protótipo no PlanetLab

Modelo de fluido

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 13/22

Simulações/Experimentos

tempo (min)

Cenário 1

Cenário 2

tempo (min)

chegadas

saídas

saídas

1 2 3 4 5

chegadas 2 3 4 51

1

2

3

4

5

1 2 3 4 5

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 14/22

Caracterização do fenômeno

Alta variabilidade do tempo de download

– Tempo pode ser 2x menor

Saídas em rajada

– Entre 10% e 82%

Injustiça em relação à ordem de chegada

– Quanto mais cedo, pior!Conclusão:mais novos recebem > mais velhos recebem

Intuição:mais novos têm pouco a oferecer aos mais velhos

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 15/22

Modelo de um usuário que terminou

Usuário

cc/4

c/4 c/4

c/4

1

2 3

4

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 16/22

Modelo de um usuário “velho”

Usuário

c/3c/3

c/31

2 3

4

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 17/22

Modelo de um usuário “novo”

Usuário

c/4

1

2

3

4

c/3

c/4

c/4+c/3

∞

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 18/22

Dada a demanda, como distribuir a capacidade?

Solução 1: algoritmo de preenchimento progressivo

Solução 2: Calcular taxa entre usuários em uma certa ordem (PD).

Se i mais velho que j

Caso contrário

Demanda

Distribuição

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 19/22

Resultados Comparação da taxa de download (modelo x simulação)

Modelo é acuradoFigura: erros < 1% (exceto 5 e 24); geral: < 10%

cenários

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 20/22

Clusterização por largura de banda: Publicações

Murai, F. and Figueiredo, D., “Formação de clusters em redes P2P por similaridade entre os nós”, SBC/SBRC 2009.

Murai, F. and Figueiredo, D., “Assortative Mixing in BitTorrent-like Networks”, IEEE/INFOCOM 2009Student Workshop.

Nota: Modelo de desempenho do BT p/ redes heterogêneas [Chow 2009].

Modelo de simulação paraDinâmica de conexões

Importância daComponente otimista

1

2

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 21/22

Downloads heterogêneos em redes homogêneas: PublicaçõesMurai, F., Rocha, A., Figueiredo, D., de Souza e Silva, E. “Can identical BitTorrent peers experience different download times?”. In: IFIP WG 7.3 Performance 2010, Belgium.

Murai, F., Rocha, A., Figueiredo, D., de Souza e Silva, E., “Heterogeneous download times in a homogeneous BitTorrent swarm”, Elsevier/Computer Networks 2012.

Rocha, A., Jaime, G., Murai, F., Figueiredo, D. and de Souza e Silva, E., “Novas evoluções integradas à ferramenta Tangram-II v3.1”, SBC/SBRC 2009 (Salão de Ferramentas).

Identificação do fenômeno

CaracterizaçãoModelo de simulação detalhado do BTModelo de fluido da troca de pedaçosGeneralizaçõesMedições em redes reais

3

4

5

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 22/22

Sobre dois fenômenos emredes P2P do tipo BitTorrent

Perguntas?

Slides em www.land.ufrj.br/~fabricio

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 23/22

Swarms pouco populares [Guo 2007, Kaune 2010]:

tempo entre chegadas aumenta exponencialmente com idade

[Hossfield 2011]: 97% dos swarms < 5 peers

Nossas medições (Torlock.com): 73% < 10 peers, 58% < 5 peersPorém, algumas características ocorrem

também em swarms populares!

Síndrome do pedaço faltante [Hajek 2011]: relação com sincronização de conteúdo

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 24/22

Consequências 1/2

* Parâmetros: cs = cl = 64 kBps, S = 256 MB, lambda = 1/1000 s

(1) Alta variabilidade notempo de download

(2) Injustiça c/ relação àordem de chegada

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 25/22

Consequências 2/2

(3) Partidas em rajada (4) Sincronização de conteúdo

* Parâmetros: cs = cl = 64 kBps, S = 256 MB, lambda = 1/1000s

~ 0.3

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 26/22

Clusterização por largura de banda: modelo de simulação bastante detalhadoValidação: uso de modelo de simulação

bastante detalhado Inicialmente desenvolvido por [3] Reescrito com novas funcionalidades

Ex.: instanciar peers c/ capacidades diferentes Implementa fielmente o protocolo do cliente

BitTorrent 4.0.0

[3] FILHO, L. J. H. Algoritmos para Acesso Interativo em Aplicações de Vídeo P2P. Tese de Mestrado, Universidade Federal do Rio de Janeiro/COPPE, set. 2009.

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 27/22

Trabalhos futuros

E se o swarm for muito popular?

Relação entre sincronização de conteúdo e síndrome do pedaço faltante

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 28/22

Clusterização por largura de banda: modelo simplificado

Métrica: média do número de conexões para classe X no estado estacionário Simulação

Analítico

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 29/22

Clusterização por largura de banda: modelo detalhado

Simplificações: Vértices são

escolhidos aleatoriamente p/ seleção de pares

Prioridade é dada em função apenas das capacidades de um par

Apenas uma aresta é trocada por vez

k=2, x=1

B

A

C

E

D

1

3

2

2

2

f(A,B) = 0f(A,D) = 1

Julho - 2012

Fabrício Murai – fabricio@land.ufrj.br 30/22

Contribuições

Estudo dos mecanismos do BT que levam ao AM Modelo detalhado da dinâmica de conexões Modelo simplificado da dinâmica de conexões Modelo de simulação do BT bem detalhado

Identificação e caracterização das taxas de download heterogêneas em redes homogêneas Modelo analítico p/ cálculo das taxas de

download individuais