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: