Streaming em Redes Peer to Peer
Arquitecturas
Arquitectura em árvore
Arquitectura em Malha
DONet
Desenho do DONet
Membership Management
Parcerias
Algoritmo de Escalonamento
Resultados práticos obtidos
Uma primeira abordagem para fazer streaming de vídeo pode ser um sistema de Multicast IP, em que se envia o stream em multicast para todos os clientes que queiram assistir à emissão. Esta solução atenua o problema da falta de largura de banda, mas não funciona na Internet actualmente, já que os routers existentes na rede não o permitem, ou seja, seria necessário um grande esforço para mudar todos eles, o que provocaria um tempo de instalação muito grande e, portanto, dificilmente será uma solução viável. [5].
Uma solução independente de hardware é criar uma ALM, ou seja, uma rede virtual ao nível da aplicação que ofereça gestão de grupos e multicast usando apenas Unicast IP. Contudo esta solução é ineficiente, pois também sobrecarrega demasiado a rede. Um exemplo de ALM são as Content Delivery Networks (CDNs), que consistem numa rede privada da organização fornecedora de conteúdos. Nas CDNs a carga é distribuída por proxies distribuídos geograficamente.
Usando uma solução P2P, pode‑se dividir a responsabilidade do servidor por, num caso extremo, todos os clientes. Estas redes que, normalmente, transportam dados (mesmo que filmes ou música) assincronamente, agora têm que transportar streams de vídeo, tendo estes requisitos bastante mais apertados. Espera‑se então as seguintes características:
- Suporte a uma larga escala de utilizadores simultâneos, na casa das dezenas de milhares.
- Performance. São necessários débitos na ordem das centenas de kilobits por segundo.
- Restrições de tempo real, sendo necessária uma sincronização temporal e continua na entrega do stream. A interactividade tem que ser garantida, mas pode haver pequenos atrasos devido à utilização de buffers.
- Degradação cuidada da qualidade, a qualidade do stream deve ir sendo alterada à medida das variações de débitos.
Arquitecturas
Nesta arquitectura os vários nós da rede estão organizados em árvore, ou seja, com uma estrutura pai‑filho. Esta organização é útil para a propagação dos pacotes pela rede com um menor esforço. A difusão da informação desenvolve‑se da seguinte forma: um nó recebe um pacote do seu pai e imediatamente envia‑o aos seus filhos.
Figura 1. Estrutura em árvore.
Apesar desta arquitectura ser eficiente, com as saídas e entradas aleatórias de nós na rede, a árvore pode perder o seu balanceamento, tornando o sistema menos eficiente. Por isso é necessário ter em conta o algoritmo de entrada, saída e falha dos nós. Estas situações acontecem com muita frequência, logo não pode haver falhas perceptíveis na entrega de pacotes aos clientes quanto se está a proceder a reestruturação da árvore. Cada vez que um nó pai falha é necessário que os filhos desse nó voltem a fazer parte da árvore, senão ficariam sem dados. Esta situação é particularmente grave no caso de falha dos nós mais perto da raiz da árvore, porque estes são responsáveis por uma árvore maior.
Cada implementação desta estrutura pode tomar decisões quanto aos critérios de balanceamento da árvore, por exemplo, pode ter números fixos de filhos por nó ou pode fazer a distribuição baseada na largura de banda ou na localização física de cada nó.
Actualmente existem vários sistemas baseados na estrutura em árvore, entre eles, PeerCast [6], ZIGZAG [7], NICE [8] , Overcast [9] e Bayeux [10].
Uma das grandes limitações numa arquitectura deste tipo é que os nós folha não têm nenhuns nós filho, ou seja, não contribuem para a rede. Para colmatar esta situação existe um tipo de arquitectura em que cada nó pertence a várias árvores: arquitectura em floresta. É esta a ideia implementada pelo SplitStream [11]. Este sistema divide um stream de vídeo em várias stripes. Estas stripes complementam‑se entre elas, resultando numa qualidade de vídeo proporcional à quantidade de stripes. Então se numa árvore um nó é folha e não contribui para a difusão de um stripe, noutra já não o é e difunde‑o para os seus nós filho.
Usando este sistema de stripes separadas, se uma das árvores falhar, consegue‑se assistir ao vídeo, contudo com uma qualidade inferior, permitindo assim uma maior tolerância a falhas.
Na arquitectura baseada em árvore convencional, um nó só recebe informação do seu nó pai. Devido a grande heterogeneidade da rede, um nó pode não ser capaz de satisfazer os requisitos de débito necessários para garantir o stream para os seus nós filho. Este aspecto pode provocar graves problemas de performance na descodificação e renderização do vídeo. Mesmo usando uma arquitectura em floresta, cada nó só recebe cada stripe a partir de apenas um nó, ou seja, tem o mesmo problema da arquitectura em árvore simples.
Uma estrutura com mais do que um nó emissor resolve estes problemas, tornando‑se mais eficiente. Nesta situação, cada nó pode escolher os nós emissores de um conjunto em que cada um contribui com uma porção do streaming. Devido à constante entrada e saída de nós e às variações do débito e atraso da Internet, o conjunto de nós conhecidos vai variar dinamicamente. Cada nó pode enviar ou receber dados de quaisquer outros nós, formando assim uma estrutura em malha. Esta abordagem trás novos desafios: como seleccionar o conjunto de emissores mais adequados e como coordenar e escalonar os dados recebidos dos vários emissores. Tem‑se como exemplos de implementação destas estruturas em malha, CollectCast [12], GnuStream [13] e o DONet [14]. Em 3.2 fala‑se em detalhe sobre este último.
Um modo simples para distribuir dados sem ter uma estrutura fixa na rede é usar algoritmos gossip [15], [16]. Num algoritmo gossip, um nó envia um pacote recém‑criado para um conjunto aleatório de nós, estes nós voltam a fazer o mesmo, assim como os seguintes até o pacote ter sido recebido por todos os nós. O facto de os emissores escolherem aleatoriamente a quem enviam as mensagens torna o sistema tolerante a falhas e totalmente distribuído.
DONet
O DONet (Data‑driven Overlay Network) é uma rede em malha, pelo que não tem uma estrutura rígida, mas utiliza um algoritmo gossip para transmitir informação entre os nós.
O método para a transmissão de dados também é baseado em ideias dos algoritmos gossip, mas não é um algoritmo gossip, já que enviar os dados aleatoriamente para os outros nós iria fazer com que houvesse muita redundância, o que não é aceitável devido ao grande volume de dados que tem que ser transmitido. Assim, foi desenvolvido um algoritmo inteligente de escolha de parceiros de entre os nós ligados à rede e um algoritmo de escalonamento para pedir dados a esses parceiros.
O CoolStreaming faz streaming nos formatos Real Video ou Windows Media, mas pode utilizar outros formatos, desde que os clientes os suportem.
Desenho do DONet
Figura 2. Arquitectura de um nó do DONet.
A figura 2 mostra as várias componentes de um nó da DONet. De entre estes os mais importantes são: (1) Membership Manager, que guarda informação sobre os nós conhecidos em toda a rede; (2) Partnership Manager, que gere o subconjunto de parceiros, a quem se vai pedir dados; (2) Scheduler, que faz o escalonamento dos pedidos de dados aos parceiros.
Para cada segmento de vídeo, cada nó pode ser emissor e/ou receptor, excepto o nó de origem da transmissão, que é sempre emissor.
Membership Management
Quando um novo nó se junta á rede, ele comunica com o nó de origem. O nó de origem vai escolher um dos nós que conhece como deputy, e reencaminhar o nó que entrou para ele. O deputy vai dar ao nó que entra a sua lista de membros e assim, o nó fica com uma lista de membros e pode escolher entre eles os nós parceiros.
Periodicamente, cada nó envia para a rede uma mensagem a avisar da sua existência. Para espalhar mensagens entre os nós é utilizado o Scalable Gossip Membership protocol (SCAM), que está descrito em detalhe em [17]
Parcerias
Figura 3. Parcerias na DONet.
Um exemplo de parcerias na DONet está representado na figura 3. Os parceiros de um nó são os nós que lhe vão enviar dados. Estes são escolhidos pelo nó, olhando para o número de segmentos que recebeu ou enviou para um determinado nó por unidade de tempo, de forma a escolher os nós com que tem melhor ligação.
Na DONet, as streams de vídeo são divididas em segmentos de tamanho uniforme. A disponibilidade destes segmentos é guardada no Buffer Map (BM), que é continuamente trocado com os parceiros, para que estes saibam quais os segmentos que podem pedir.
Experimentalmente, determinou‑se que a latência entre todos os nós raramente passa 1 minuto. Portanto, se o vídeo estiver dividido em segmentos de 1s, um buffer de 120 segmentos deverá ser sempre suficiente. O BM guarda apenas para cada segmento 1 bit a indicar se esse segmento está disponível ou não e o número de sequência do primeiro segmento do buffer.
Algoritmo de Escalonamento
Os requisitos para o algoritmo de escalonamento são:
- Ser capaz de cumprir a deadline para os segmentos serem mostrados ao utilizador.
- Utilizar o débito dos parceiros de forma justa.
O algoritmo começa por calcular o número de fontes para cada segmento. Como será mais difícil um segmento com menos fontes cumprir a sua deadline, o algoritmo começa por tratar os segmentos com apenas uma fonte, depois com duas, e continua assim até estarem tratados todos os segmentos. Em cada uma destas iterações, ele vai seleccionar para cada segmento a fonte que tem maior largura de banda e mais tempo disponível.
Após o algoritmo ser executado, vai ser enviada uma mensagem para os nós seleccionados a indicar quais os segmentos que se quer daquele nó. Os segmentos são então entregues através de um protocolo de transporte. Numa primeira implementação foi utilizado o TCP, mas a DONet não impõe qual o protocolo a ser usado.
Quando um nó se desliga da rede, envia uma mensagem para a rede a avisar que se vai desligar. Caso ele não consiga enviar esta mensagem, quando algum nó detectar que esse nó se desligou, esse nó irá enviar a mensagem a informar isso. Em qualquer dos casos, quando um nó se desliga, os outros nós actualizam as suas listas de membros de parcerias.
Resultados práticos obtidos
Aqui são apresentados os resultados obtidos por uma implementação do DONet, o Coolstreaming, numa situação real. Os dados foram obtidos durante um evento transmitido num certo canal a 12 de Março e o pico de utilizadores foi de aproximadamente 15.000 e o streaming foi feito a 330 kbit/s [18].
Figura 4. Número de utilizadores e índice de continuidade.
Figura 5. Índice de continuidade média vs. Tempo de subscrição de utilizador.
Figura 6. Distribuição cumulativa de perda de pacotes.
O índice de continuidade é o quociente entre o número de segmentos que chega ao cliente cumprindo a deadline e o número total de segmentos.
Como se pode ver na figura 4, o índice de continuidade parece estar relacionado com o número de utilizadores, aumentando com o número de utilizadores. A figura 5 mostra que á medida que o tempo passa, o utilizador consegue ter uma maior taxa de pacotes a cumprir o deadline. Isto poderá estar relacionado com o facto de que o cliente consegue escolher melhores parceiros depois de algum tempo ligado ao sistema. A figura 6 mostra a perda de pacotes observada na altura de pico (aproximadamente nos 250 minutos), quando estavam ligados 15.000 clientes. Aqui pode‑se ver que 13.000 clientes têm perda de pacotes de 0 e apenas 1000 têm uma perda superior a 10%.
Figura 7. Número de utilizadores vs. Tempo de subscrição do utilizador.
Como se pode ver na figura 7, cerca de 100 utilizadores mantêm o canal sempre subscrito para o poderem ver em qualquer altura. Estes utilizadores formam um backbone estável para o sistema.