Seminário LAND A Preferential Attachment Model for Tree Construction in P2P Video Streaming Marcio N. Miranda - Daniel R. Figueiredo Submetido ao First

Seminário LAND Seminário LAND

A Preferential Attachment Model for Tree

Construction in P2P Video Streaming

Marcio N. Miranda - Daniel R. Figueiredo

Submetido ao First IEEE International Workshop on Network Science for

Communication Networks – Infocom 09

Roteiro Roteiro

• Motivação

• O Modelo

• Métricas

• Resultados / Discussão

• Conclusões / Trabalho Atual

MotivaçãoMotivação

• Objetivo: Disseminação de vídeo na Internet

• Características: Centenas ou milhares de usuários

=> Necessidade de grande quantidade de recursos e

maior escalabilidade da arquitetura do sistema → P2P

• Abordagem possível (P2P) → árvore de distribuição de vídeo:

servidor – raiz usuários (peers) - nós internos

Motivação Motivação

Problema: construção da árvore de distribuição

árvores diferentes fornecem QoS diferentes aos usuários

falta de conhecimento da qualidade da árvore

mesmo que os peers fossem conhecidos a priori, organizá-los na melhor árvore é uma tarefa difícil devido à falta de informações sobre banda e atrasos na conexão entre os peers


• Duas características fundamentais para a qualidade do vídeo:

grau do nó: número de fluxos de vídeo que estão sendo fornecidos pelo nó – banda limitada

distância do nó ao servidor: número de hops entre o nó e o servidor – atrasos e perdas

Obs: um mecanismo eficiente de construção da

árvore de distribuição de vídeo deve considerar

essas duas características


• Objetivos do trabalho:

geração da árvore de distribuição utilizando um mecanismo de construção aleatório e simples

processo de crescimento baseado no grau do nó e na distância do mesmo ao servidor

analisar as propriedades topológicas e a qualidade das árvores geradas através de simulações

O ModeloO Modelo

Suposições:

• Sistema de distribuição de vídeo composto por um servidor e dezenas de milhares de peers homogêneos

• Servidor é responsável pela geração ou armazenamento do vídeo

• Novos usuários (peers) que chegam ao sistema podem receber o fluxo de vídeo do servidor ou de um (apenas um) outro usuário da árvore

O ModeloO Modelo

• Peers recebem e fornecem serviço para outros peers através do repasse do fluxo de vídeo

• Não existem usuários egoístas (peer sempre repassa o vídeo, caso seja escolhido)

• Peers nunca deixam o sistema e nem trocam de posição dentro da árvore (posição determinada no momento da chegada)

O ModeloO Modelo

O ModeloO Modelo

Modelo de Construção:

• Baseado no princípio de preferential attachment

• Preferência de conexão dada aos nós com maior utilidade (medida de qualidade do vídeo servido)

• função de utilidade com um parâmetro (α) que controla o peso dado ao grau do nó e à distância do nó ao servidor

O ModeloO Modelo

Intuição:

• qualidade do vídeo fornecido é inversamente proporcional ao grau do nó (banda finita)

• qualidade do vídeo também é inversamente proporcional à distância do nó ao servidor (atrasos e perdas maiores para distâncias maiores)

=> qualidade do vídeo determinada por uma combinação

das duas características

O ModeloO Modelo

Função de Utilidade:

• usada para determinar o “nó pai” do novo usuário

• α controla a importância relativa do grau do nó e de sua distância ao servidor

• α influencia a estrutura da árvore gerada

O ModeloO Modelo

Probabilidade de conexão ao nó v

• pv

varia com o número de nós na árvore

Métricas Métricas

Métricas para caracterizar as propriedades

topológicas da árvore gerada:

Distância máxima Distância média Grau máximo Grau médio Distribuição dos graus dos nós

MétricasMétricas

Métricas para avaliar a qualidade média da árvore gerada:

qv

→ qualidade do vídeo recebido pelo nó v

a qualidade do vídeo recebido depende do grau do pai!!!

MétricasMétricas

Parâmetro para análise da qualidade da árvore

gerada pelo modelo:

conjunto de árvores k-completas: árvores cujos nós possuem exatamente k filhos, com possível

exceção do penúltimo e do último níveis

intuitivamente são as árvores que proporcionariam a melhor qualidade devido ao balanceamento entre o grau e a distância através do parâmetro k.

obs: k = 1 → linha; k = |S| → estrela

MétricasMétricas

Árvore k-completa de melhor qualidade:

Resultados / DiscussãoResultados / Discussão

Simulação:

inicia-se com o servidor adiciona-se peers sequencialmente, seguindo a regra de

preferential attachment para a utilidade, calcula-se a probabilidade de cada nó e “sorteia-se um nó” para anexação

uma vez anexado o novo peer, recalcula-se as probabilidades para todos os nós


Simulação:

simulação pára quando n = 60.000 nós

para cada α executa-se a simulação 20 vezes e calcula-se a média

interesse está na análise do comportamento do modelo generativo em função do parâmetro α


Resultados:

Grau do Servidor e Grau máximo da árvore vs α


Comentários: (Grau do Servidor e Máximo vs α)

ambas as curvas decaem monotonicamente com α

a variação em função de α não é significativa!!!

para α = 0 a árvore não deveria tender para uma estrela?

a probabilidade de um nó específico decresce com n

não existe um nó específico que atraia os que chegam, forma que a topologia da árvore seja estrela


Resultados:

Complementary Cumulative Distribution Function (CCDF) para diferentes valores de α


Comentários: (CCDF para diferentes valores de α)

a cauda da distribuição aumenta quando α diminui

para valores de α maiores que 0.5 a distribuição dos nós cai abruptamente

em qualquer dos casos (α perto de 1 ou perto de 0) a a cauda da distribuição não parece seguir uma lei de potência!!


Resultados:

Distâncias média e máxima vs α


Comentários: (Distâncias média e máxima vs α)

Ambas as curvas crescem com α, como esperado

Distâncias não são muito grandes!!! Mesmo a máxima!

Para α = 1 a árvore não deveria tender para uma linha?

mesmo argumento utilizado para os graus vale aqui: a probabilidade de um nó específico decresce com n

a probabilidade de uma folha ser sempre escolhida é muito pequena!


Resultados:

Qualidade da árvore vs α


Comentários: (Qualidade das árvores geradas e k-completas vs α)

comparação com a árvore k-completa de melhor qualidade

para inúmeros valores de alfa a qualidade da árvore gerada é similar ou até melhor do que a da árvore k-completa!!!

nos extremos (alfa = 0 ou alfa = 1) a qualidade da árvore k-completa é bem superior

a forma de geração da árvore do modelo explica este resultado: o modelo não gera árvores degeneradas

Conclusões e Trabalho AtualConclusões e Trabalho Atual

• ao contrário do modelo clássico de PA, o modelo proposto leva a uma “auto-organização” dos nós na árvore, sem permitir a formação de estruturas topológicas degeneradas

• a qualidade das árvores geradas pelo modelo é surpreendentemente boa, comparada com a k-completa

• isso se deve ao mecanismo de auto-organização, consequência da natureza probabilística da anexação dos nós

• a construção de uma árvore k-completa, além de ser mais complexa, leva a estruturas rígidas, ao contrário do modelo proposto

Conclusões e Trabalho AtualConclusões e Trabalho Atual

Trabalhos em andamento:

Documents

Seminário LAND A Preferential Attachment Model for Tree Construction in P2P Video Streaming Marcio N. Miranda - Daniel R. Figueiredo Submetido ao First