Streaming P2P baseado em árvore e malha
Nessa seção, será apresentada uma visão sobre streaming peer-to-peer,
baseado nas abordagens de árvore e malha. Em ambas as abordagens, é
utilizado o MDC (Multiple Description Coding) para acomodar a heterogeneidade
da banda. Em um MDC, um stream é codificado em vários sub-streams
chamados de description. Cada um desses description pode ser
independentemente decodificado. Porém, ao receber vários descriptions resulta
em uma melhor qualidade. Isso permite aos peers receberem um número de
descriptions proporcional à sua banda, o que maximiza a qualidade.
- Streaming P2P baseado em árvore
Na abordagem em árvore, o mecanismo de construção overlay organiza os
peers participantes em diversas árvores. O quantidade de árvores que este peer
vai se unir é baseada em sua banda disponível. Para minimizar o efeito do churn
(dinâmica dos peers participantes) e utilizar de modo eficaz os recursos do
sistema, os peers são organizados em diversas árvores. Para este fim, cada peer
é colocado como um nó interno (ou seja, um nó que possui filhos) em apenas uma
árvore e como um nó externo (folha, ou seja, não tem filhos) em outras árvores.
Então, cada description de um conteúdo MDC codificado é entregue à uma árvore
específica. A entrega de conteúdo é um mecanismo simples onde os nós internos
simplesmente encaminham qualquer pacote recebido da description
correspondente para cada um dos nós filhos. Assim, o componente principal do
streaming P2P baseado em árvore é a construção da árvore.
- Tree Construction Algorithm
O objetivo da construção é manter as árvores balanceadas, estáveis e
pequenas. O algoritmo de construção de árvore a seguir representa uma boa
solução do problema, dentro das possíveis, segundo [ 6 ].
Cada peer é colocado como um nó interno em uma apenas árvore e como
nó folha em outras árvores. Quando um peer se junta ao sistema, ele se comunica
com o nó de inicialização para identificar um “pai” no número de árvores
desejado. Para deixar a população de nós internos balanceada dentre as
diferentes árvores, um novo nó é adicionado como um nó interno na árvore que
possui o menor número de nós internos. Para manter as árvores pequenas, um
novo nó interno é colocado como um “filho” para o nó com menor profundidade
que pode acomodar mais um filho ou que tem um filho que é uma folha. Neste
último caso, o novo nó substitui o nó folha e o nó substituído se junta novamente à
árvore como folha.
Quando um nó interno da árvore se “desconecta”, cada um de seus nós
filhos, além da sub-árvore do qual eles são raiz, deverão se juntar novamente à
árvore. Os peers dessa árvore particionada da árvore original aguardam o nó raiz
da sub- árvore se juntar novamente à árvore principal como um nó interno. Se esta
raiz não conseguir se juntar à árvore em um certo período de tempo, os peers da
sub- árvore se juntam à árvore principal independentemente, na mesma posição
que tinham antes (como folhas ou nós internos).
- P2P Streaming baseado em malha
Na abordagem em malha, os peers participantes formam um overlay
conectado aleatoriamente, ou uma malha. Cada peer tenta manter um certo
número de pais (grau de entrada), e também serve um certo número de filhos
(grau de saída). Em sua chegada, o peer se comunica com o nó de inicialização
para receber uma lista de peers que poderiam servir como pais. Isso é possível
pois o nó de inicialização conhece o grau de saída de todos os peers, e então
seleciona aleatoriamente uma lista de peers que pode acomodar um novo filho em
resposta ao pedido por pais feito pelo peer que está chegando.
A abordagem em malha utiliza o fornecimento de conteúdo em swarm
(grupo de peers conectados entre si para compartilhar conteúdo) similar ao do
BitTorrent. A maior vantagem dessa técnica é sua capacidade de utilizar de modo
eficaz a banda de upload dos peers participantes conforme o tamanho do grupo
aumenta. O fornecimento de couteúdo em swarm combina os anúncios de
conteúdo com seus respectivos pedidos. Cada peer periodicamente anuncia seus
pacotes novos disponíveis para seus peers filhos, e pede pacotes específicos dos
peers pais. Um peer pai periodicamente recebe uma lista ordenada com os
pedidos de pacotes de cada peer filho, e fornece os pacotes de acordo com a
ordem dos pedidos. Os pacotes que serão pedidos são determinados por um
algoritmo de packet scheduling em cada peer filho. Este algoritmo é a
componente chave do mecanismo de streaming P2P baseado em malha, e deve
atingir os seguintes objetivos:
- Utilizar de modo eficaz a banda de todos os peers pais.
- Conseguir um bom número de descriptions (qualidade desejada) de
todos os peers pais.
- Garantir o fornecimento dos pacotes pedidos no tempo certo.
O padrão de fornecimento de conteúdo para pacotes através da malha (isto
é, o caminho que o pacote atravessa para chegar em todos os peers) depende do
comportamento do algoritmo de packet scheduling em cada peer, e da
conectividade do overlay.
Como exemplo de uso temos o PRIME ( Peer-to-Peer Receiver-dIven Mesh-
based Streaming ) [ 7 ] , que incorpora o seguinte Packet Scheduling: Cada peer
mantém 2 pedaços de informação dos pais:
- Os pacotes disponíveis
- A média ponderada da banda
Além disso, os peers monitoram a banda de entrada agregada de todos os
pais, e lentamente adapta o número de pedidos de descriptions(ou sua qualidade
alvo) com a banda agregada. Dadas as informações dos pais, mais a qualidade
alvo n, o algoritmo de scheduling é periodicamente invocado (isto é, uma vez
a
cada X segundos) para determinar uma lista de pacotes que devem ser pedidos
para cada pai:
Primeiro, o scheduler identifica os pacotes com maior timestamp que se
tornaram disponíveis entre os pais desde o último pedido (durante os ultimos X
segundos). O algoritmo de scheduling então pede todos esses novos pacotes
(até n descriptions por timestamp) dos pais correspondentes.
Em seguida, os pacotes que faltam para cada timestamp (até n descriptions por
timestamp) são identificados e uma parte aleatória desses pacotes são pedidos
à todos os pais, para utilizar totalmente sua banda. O número total de pacotes
pedidos de cada pai é determinado por sua banda disponível. Para balancear a
carga pelos pais, quando um pacote está disponível em mais de um pai, ele é
pedido ao pai que tem a menor parte de sua banda utilizada.
1. Introducao
