DONet, Datadriven Overlay Network, é uma rede overlay de streaming de media
ao vivo. Suas operações são bem simples: cada nó periodicamente troca
informações sobre seus dados disponíveis com seus parceiros, recebe dados
novos de um ou mais parceiros, ou fornece dados à eles.
Os três recursos principais desse design “impulsionado por dados” são:
- Fácil de implementar – não é necessário montar e manter uma estrutura
global complexa.
- Eficiente – o encaminhamento de dados é determinado dinamicamente
de acordo com a disponibilidade, e não está restrito à direções
específicas.
- Robusto e Resistente – as parcerias permitem uma troca rápida entre
os diversos fornecedores.
O DONet é baseado numa concepção data-centric de um streaming overlay, onde
um nó sempre encaminha dados para os que estão esperando esses dados, sem
nenhum papel pré-determinado como pai/filho, nóinterno/nóexterno, etc. Em outras
palavras, é a disponibilidade de dados que guia o fluxo, não uma estrutura de
overlay específica. Essa abordagem é adequada para overlays em que os nós
são muito dinâmicos.
Protocolo Gossip
Em um algoritmo de gossip, um nó envia uma mensagem nova para um
conjunto aleatório de nós selecionados. Estes nós fazem o mesmo no próximo
round, e assim é feito até a mensagem chegar a todos. A escolha aleatória dos
alvos do gossip oferece resistência à falhas aleatórias e permite operações
descentralizadas. No DONet, o protocolo gossip é utilizado para gerenciamento
dos membros, enquanto o fornecimento de dados é parcialmente motivado por
este conceito. Todavia o uso do gossip em streaming não é tão simples pois
como a escolha de pra quem a mensagem será enviada é aleatória, pode causar
redundância significativa, o que é muito grave para aplicações de streaming de
alta banda. Assim, foi desenvolvido um algoritmo inteligente de seleção de
parceiros e um algoritmo de escalonamento de baixo overhead que pega dados
de múltiplos parceiros, o que reduz significativamente a redundância.
Estrutura do DONet
Figura 3 [ 3 ]
A figura acima ilustra o sistema de um nó DONet. Existem 3 módulos chave:
- Membership Manager - que mantém uma visão parcial sobre os outros
nós do overlay.
- Partnership Manager - que estabelece e mantém parcerias com os outros
nós.
- Scheduler - escalona a transmissão de video (dados).
Para cada segmento de um stream de vídeo, um nó DONet pode ser tanto um
receptor ou um fornecedor, ou ambos, dependendo dinamicamente da informação
disponível deste segmento, que é periodicamente trocada entre um nó e seus
parceiros. Uma excessão é o nó fonte, que é sempre um fornecedor, e é
conhecido como o nó de origem. Este pode ser um servidor de vídeo, ou
simplesmente um nó overlay que possui um programa ao vivo para distribuir.
Membership Management e Entrada de Nós
Cada nó DONet possui um identificador único, como um endereço IP, e
mantém um membership cache (mCache) contendo uma lista parcial dos
identificadores para os nós ativos. Em um algoritmo básico de entrada de nós, um
nó que entrou recentemente primeiro contacta o nó de origem, que seleciona
aleatoriamente um nó deputy (assistente) de sua mCache e redireciona esse
novo nó para o deputy.Esse novo nó pode então obter a lista de candidatos à
parceiro do deputy, e entrar em contato com esses candidatos para estabelecer
suas parcerias.
Esse processo geralmente é viável pois o nó de origem continua durante
toda a transmissão e seu endereço/identificador é conhecido por todos. Esse
redirecionamento permite uma seleção de parceiros mais uniforme, e reduz
bastante a carga do nó de origem.
Cada nó, periodicamente gera uma membership message para anunciar
sua existência. Essas mensagens são distribuídas entre os nós com o Scalable
Gossip Membership protocol (SCAM), detalhado em [ 8 ].
Representação e Troca do Buffer Map
Figura 4 [ 3 ]
Um exemplo de parceria no DONet é mostrado na figura 4. Nem os
parceiros nem a direção na transmissão de dados são fixas no DONet. Um
stream de vídeo é dividido em vários segmentos de tamanho uniforme, e a
disponibilidade desses segmentos no buffer de um nó pode ser representada por
um Buffer Map (BM). Cada nó troca continuamente seu BM com os parceiros, e
então escalona qual segmento será buscado, e de qual parceiro.
Experimentalmente [ 3 ], observou-se que a latência entre os nós dificilmente
ultrapassa 1 minuto. Assumindo que cada segmento tem 1s, uma janela de 120
segmentos pode representar o BM de um nó. Para cada segmento, 1 representa
que está disponível, e 0 o contrario. Além disso, o número de sequência do
primeiro segmento é armazenado.
Algoritmo Escalonador
Dois pontos devem ser levados em conta pelo algoritmo escalonador: o
deadline de cada segmento que será mostrado e a banda heterogênea dos
parceiros. Se o primeiro requisito não for cumprido, pelo menos o número de
segmentos atrasados deve ser mínimo.
O algoritmo primeiro calcula o número de fornecedores em potencial para
cada segmento. Para um segmento com poucos fornecedores será mais difícil
cumprir o deadline, então o algoritmo determina os segmentos com apenas um
fornecedor, depois dois, e assim por diante. O fornecedor com maior banda e
tempo disponível será escolhido para cada segmento.
Com o fim do algoritmo, será mandada para o fornecedor uma mensagem
contendo os segmentos a serem pedidos, e estes serão entregues através de um
protocolo de transporte em tempo real. O DONet não especifica um protocolo em
particular, mas utiliza o TCP nos experimentos e nas aplicações atuais.
Recuperação de Falhas
No DONet, um nópode se desligar da rede de modo natural (ou seja, ele
anuncia que irá sair) ou pode sair acidentalmente. Em ambos os casos, a saída é
facilmente detectada, após um tempo ocioso ou troca de BM.
Quando um nó se desliga "naturalmente", este envia uma mensagem de saída.
Quando um nó falha, o parceiro que detecta esta falha envia essa mensagem de
partida avisando que aquele nó saiu.
Resultados de experimentos
Através dos experimentos [ 3 ] feitos no PlanetLab, pôde-se perceber:
- Baixo overhead de controle
- Alta continuidade de playback
- Grande escalabilidade
Existe uma aplicação DONet pública, chamada CoolStreaming. Sua primeira
versão saiu em 30 de Maio de 2004. É feita em Python, e contém
aproximadamente 2000 linhas, o que mostra sua simplicidade. Atualmente, são
aceitos os formatos de Real Video e Windows Media Video para streaming.