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
• Motivação
• O Modelo
• Métricas
• Resultados / Discussão
• Conclusões / Trabalho Atual
Motivaçã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
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
Motivação
• 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
Motivação
• 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 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 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 Modelo
O 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 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 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 Modelo
Probabilidade de conexão ao nó v
• pv
varia com o número de nós na árvore
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é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é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étricas
Árvore k-completa de melhor qualidade:
Resultados / 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
Resultados / Discussão
Simulação:

simulação pára quando n = 60.000 nós

para cada α executa-se a simulação 20 vezes e calculase a média

interesse está na análise do comportamento do modelo
generativo em função do parâmetro α
Resultados / Discussão
Resultados:

Grau do Servidor e Grau máximo da árvore vs α
Resultados / Discussão
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 / Discussão
Resultados:

Complementary Cumulative Distribution Function (CCDF) para
diferentes valores de α
Resultados / Discussão
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 / Discussão
Resultados:

Distâncias média e máxima vs α
Resultados / Discussão
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 / Discussão
Resultados:

Qualidade da árvore vs α
Resultados / Discussão
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 kcompleta é 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 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 Atual
Trabalhos em andamento: