Elias de Oliveira Granja Junior Heurísticas para

Transcrição

Universidade Estadual de Campinas
Instituto de Computação
INSTITUTO DE
COMPUTAÇÃO
Elias de Oliveira Granja Junior
Heurísticas para minimização de custos em um
P2P-Cloud CDN.
CAMPINAS
2016
Heurísticas para minimização de custos em um P2P-Cloud CDN.
Dissertação apresentada ao Instituto de
Computação da Universidade Estadual de
Campinas como parte dos requisitos para a
obtenção do título de Mestre em Ciência da
Computação.
Orientador: Prof. Dr. Luiz Fernando Bittencourt
Este exemplar corresponde à versão final da
Dissertação defendida por Elias de Oliveira
Granja Junior e orientada pelo Prof. Dr.
Luiz Fernando Bittencourt.
CAMPINAS
2016
Agência(s) de fomento e nº(s) de processo(s): Não se aplica.
Ficha catalográfica
Biblioteca do Instituto de Matemática, Estatística e Computação Científica
Maria Fabiana Bezerra Muller - CRB 8/6162
G766h
Granja Junior, Elias de Oliveira, 1992GraHeurísticas para minimização de custos em um P2P-Cloud CDN / Elias de
Oliveira Granja Junior. – Campinas, SP : [s.n.], 2016.
GraOrientador: Luiz Fernando Bittencourt.
GraDissertação (mestrado) – Universidade Estadual de Campinas, Instituto de
Computação.
Gra1. Arquitetura peer-to-peer (Redes de Computadores). 2. Computação em
nuvem. I. Bittencourt, Luiz Fernando,1981-. II. Universidade Estadual de
Campinas. Instituto de Computação. III. Título.
Informações para Biblioteca Digital
Título em outro idioma: Heuristics for a P2P-Cloud video on demand system
Palavras-chave em inglês:
Peer-to-peer architecture (Computer networks)
Cloud computing
Área de concentração: Ciência da Computação
Titulação: Mestre em Ciência da Computação
Banca examinadora:
Luiz Fernando Bittencourt [Orientador]
Fábio Luciano Verdi
Edmundo Roberto Mauro Madeira
Data de defesa: 18-07-2016
Programa de Pós-Graduação: Ciência da Computação
Powered by TCPDF (www.tcpdf.org)
Instituto de Computação
INSTITUTO DE
COMPUTAÇÃO
Heurísticas para minimização de custos em um P2P-Cloud CDN.
Banca Examinadora:
• Prof. Dr. Luiz Fernando Bittencourt
UNICAMP
• Prof. Dr. Edmundo R. M. Madeira
UNICAMP
• Prof. Dr. Fábio L. Verdi
UFSCar
A ata da defesa com as respectivas assinaturas dos membros da banca encontra-se no
processo de vida acadêmica do aluno.
Campinas, 18 de julho de 2016
Valeu a pena? Tudo vale a pena
Se a alma não é pequena.
Quem quer passar além do Bojador
Tem que passar além da dor.
Deus ao mar o perigo e o abismo deu,
Mas nele é que espelhou o céu.
(Fernando Pessoa)
Agradecimentos
Um trabalho de dois anos é cheio de altos e baixos. As vezes é aquele código que não
compila ou mostra resultados não esperados, as vezes a alegria de ver a proposta ganhando
forma e sendo implementada. Mas no fim é a resiliência que conta e o resultado apenas
uma reação de uma longa e incessante caminhada. Caminhada que definitivamente não
pode ser feita sozinha: “Quando a neve cai e os ventos brancos sopram, o lobo solitário
morre, mas a matilha sobrevive.” - George R.R. Martin.
Por conta disto, gostaria de agradecer aos meus pais, Elias e Graça, pelo apoio e
incentivo durante todo o mestrado, inclusive na época que decidi sair do trabalho para me
dedicar totalmente as aulas no primeiro semestre. Ao meu irmão, Felipe, pelos momentos
de descontração.
Aos amigos: Douglas, pelos conselhos dados, piadas ruins e pelas nossas conversas
durante nossas idas ao Extra. Carreiro pelo companheirismo, pelas cervejas ostentadas
em bares caros ou tomadas na calçada em frente ao Pão de Açúcar. Fernando por ser
aquele amigo sempre disponível e pronto para ajudar. Nana pela amizade inesperada,
mas sincera (mesmo ela não gostando do Jon Snow).
Ao professor Doutor Luiz que sempre estava pronto para ajudar e aconselhar, com
toda a paciência do mundo. Guiando não só o desenrolar da dissertação, mas ajudando
em todos os aspectos da vida acadêmica.
Aos doutores Ioan Petri e Omer F. Rana pela orientação no artigo realizado durante
nossa visita à Universidade de Caerdydd.
À Beatriz por fazer dupla de estudo durante o primeiro semestre das aulas e pela
constante preocupação com os estudos, que sempre me inspirou.
Por fim aos meus escritores favoritos: Douglas Adams, George R.R. Martin e Tolkien
cujos livros renovavam minha energia a cada final de dia.
Ab imo pectore.
Resumo
A utilização de sistemas de vídeo sob demanda tem crescido nos últimos anos, aumentando
o interesse em formas de distribuição de arquivos multimídia com um baixo custo e uma
alta qualidade de experiência para o usuário. Entre as formas de distribuição utilizadas
atualmente estão o Content Distribution Network, a nuvem de computação pública e
protocolos Peer-to-Peer, estes com naturezas distintas, onde a nuvem utiliza a arquitetura
cliente-servidor, é estável, porém se usada de maneira leviana pode acarretar em altos
custos. Por outro lado protocolos Peer-to-Peer permitem aos usuários atuarem ao mesmo
tempo como receptor e como distribuidor de conteúdo, diluindo o custo da infraestrutura
entre os próprios usuários, porém sem a garantia de qualquer qualidade de experiência.
Unindo as duas arquiteturas é possível criar um sistema mais barato. Otimizando a
utilização da nuvem e usando protocolos Peer-to-Peer entre os usuários para auxiliar a
distribuição de conteúdo é possível minimizar o custo final. Porém é necessário balancear o custo com a qualidade acordada por acordos de nível de serviço entre usuário e
fornecedor de conteúdo. Este trabalho propõe três categorias de heurísticas: proativa,
reativa e híbrida, para alocar recursos na nuvem visando o mínimo custo possível e uma
boa qualidade de experiência para o usuário.
As heurísticas reativas reagem a interrupções na visualização do vídeo, enquanto que
as proativas tentam agir antes da interrupção, alocando máquinas quando há entrada de
usuários. A heurística híbrida é uma mescla entre as duas categorias.
As heurísticas foram simuladas utilizando o arcabouço Peersim com diferentes cenários.
Os resultados mostraram que as heurísticas são mais eficientes que dois métodos ingênuos,
o primeiro alugando servidores para cada usuário e o segundo mantendo um número
estático de servidores. Neste trabalho também são discutidas maneiras de se implementar
um sistema real utilizando as heurísticas propostas.
Abstract
As video on demand systems grows in popularity, new approaches to deal with the media
distribuition in the internet have being studied. Companies providing this service are
insterested in increasing the quality of experience of the user, while keeping a low cost of
infrastructure. Between the approaches to distribute content, we can hightlight Content
Distribuition Network, Cloud Computing systems, and Peer-to-Peer protocols. Cloud
Computing systems and P2P protocols work in a different manner, but can be mixed
togheter to provide a high quality and low cost service. While Cloud Computing works
with a client-server architeture and is more realible, stable and at same time more expensive if used in a naive way, P2P protocols allow users to both distribiute and consume
content, making it to build a video on demand system.
The merge between both approaches must optimize the Cloud Computing bandwith,
using the “free” user upload bandwith of P2P at the same time that keeps a good quality
of service. In this paper we provide three categories of heuristics - proactive, reactive, and
hybdrid - to allocate resources in the cloud with the aim to balance the cost and quality
of experience.
The reactive approach rents more VMs when the number of video stall events increase,
while the proactive reacts to the quantity of users in the system. The hybrid merges both
behaviors.
The heuristics were simulated with the Peersim framework. The results showed the
heuristics are more effiecient than two naive approches: the first one renting one server
per user and the second keeping a static number of servers. Moreover, in the end of this
work it is discussed the results togheter with ways to implement it in a real system.
Lista de Figuras
2.1
2.2
2.3
4.1
Exemplo de overlay de uma rede P2P: as conexões entre os nós não necessariamente refletem a conexão na rede física. . . . . . . . . . . . . . . . . . 17
Arquitetura do MetaCDN.org [12] . . . . . . . . . . . . . . . . . . . . . . . 18
Arquitetura de um sistema P2P-Cloud CDN: o usuário u (círculo rosa)
faz requisições para o grupo de usuários U (círculo verde) e para o CDN
(retângulo azul). As duas fontes compartilham o arquivo b (arquivo de
vídeo) simultaneamente com u. . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4
Usuário u recebe pedaços de Chunk em round-robin dos Servidores a, b e
dos Superpeers l, m. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Fluxo do Tracker ao receber uma requisição do usuário. . . . . . . . . . .
Representação visual do cálculo das interrupções. Onde playback_window
representa um intervalo de tempo, e QoE_KBP S ⇤ playback_window
todos os chunks que deveriam ter sido visualizados pelo usuário até aquele
instante. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Fluxo do sistema de monitoramento. . . . . . . . . . . . . . . . . . . . .
5.1
Fluxo da arquitetura do sistema. . . . . . . . . . . . . . . . . . . . . . . . 33
6.1
6.2
6.3
6.4
6.5
Resultados das simulações. . . . . . . . . . . . . . . . . . . . . . . . . . .
Simulação com 2 mil usuários. . . . . . . . . . . . . . . . . . . . . . . . .
Simulação com número maior de banda de saída dos usuários. . . . . . .
Simulação com a estratégia Híbrida com 2000 usuários. . . . . . . . . . .
Simulação com cenário similar ao de [34], utilizando a heurística Híbrida
com arquivos de diferente tamanhos. . . . . . . . . . . . . . . . . . . . .
7.1
Exemplo da escolha do segmento de vídeo a ser enviado pelo usuário (a)
ao usuário (b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Exemplo de rede overlay utilizando tree-push P2P. . . . . . . . . . . . . . . 53
4.2
4.3
7.2
. 26
. 28
. 29
. 29
.
.
.
.
41
42
44
46
. 47
Sumário
1 Introdução
2 Conceitos básicos
2.1 Computação em nuvem
2.2 Protocolos P2P . . . .
2.3 Cloud-CDN . . . . . .
2.4 P2P-Cloud CDN . . .
12
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
15
16
17
18
3 Trabalhos Relacionados
20
4 O sistema
4.1 Atores do sistema . . . . . . . . . . . . . . . . . .
4.1.1 Provedor do sistema de vídeo sob demanda
4.1.2 Servidores da Nuvem . . . . . . . . . . . .
4.1.3 Usuários . . . . . . . . . . . . . . . . . . .
4.1.4 Superpeers e organização dos usuários . .
4.2 Divisão do sistema . . . . . . . . . . . . . . . . .
4.3 Protocolos . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
25
25
25
25
26
26
27
28
5 Modelo
5.1 Redução do custo . . . . . .
5.2 Heurísticas . . . . . . . . . .
5.2.1 Heurísticas Proativas
5.2.2 Heurísticas Reativas
5.2.3 Métodos ingênuos . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
32
32
34
34
36
37
6 Simulações
6.1 Cenários . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Cenário básico . . . . . . . . . . . . . . . . . .
6.1.2 Melhores heurísticas . . . . . . . . . . . . . .
6.2 Heurística Híbrida . . . . . . . . . . . . . . . . . . .
6.2.1 Simulação com 2000 usuários . . . . . . . . .
6.2.2 Simulação com vídeos de 12800 Kbps de SLA
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
38
39
39
40
43
45
45
7 Discussão
7.1 Heurísticas e estratégias auxiliares
7.1.1 Estratégias auxiliares . . .
7.1.2 Resultados das simulações
7.1.3 Superpeers . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
48
48
48
49
49
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7.2
Possíveis implementações . . . . . . .
7.2.1 Provedor IaaS . . . . . . . . .
7.2.2 Alocação de máquinas . . . .
7.2.3 Requisitando o arquivo . . . .
7.2.4 Saída e entrada de usuários no
. . . . .
. . . . .
. . . . .
. . . . .
sistema
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
50
50
51
51
54
8 Conclusões
55
Referências Bibliográficas
58
Capítulo 1
Introdução
Content Delivery Networks (CDNs) são sistemas de servidores geograficamente distribuídos que visam distribuir conteúdo para usuários atendendo a um SLA (nível de serviço
acordado entre o provedor e o cliente, do inglês Service Level Agreement). Esse tipo de
serviço é utilizado, por exemplo, em sistemas de vídeo sob-demanda (video-on-demand,
VoD) como o Netflix [10].
O interesse sobre sistemas VoD e a utilização de CDN aumentaram recentemente
devido ao aumento do número de provedores de VoD (com grandes empresas entrando
no mercado como HBO, Amazon e até provedores piratas como o PopCorn-Time), assim
como a demanda por estes serviços. De fato mais da metade do tráfego de internet
mundial é relacionado com a transferência de arquivos multimídia. De acordo com [13],
P2P respondeu por 20 a 26% em 2008 e sistemas VoD, como o youtube, entre 30% e
40%, totalizando cerca de 66% do tráfego, enquanto que em 2012 somente o Netflix foi
responsável por 29.7% do tráfego nos EUA [10], o número de usuários desses sistemas
também é extremamente relevante. O Youtube por exemplo, tem ao menos 20 milhões
de visualizações por dia [21].
Com o aumento do número de sistemas de VoD e também do número de usuários
(somente o netflix contava com cerca de 40.3 milhões de usuários em 2013 [19]) , surge a
necessidade de otimizar custos, a fim de manter um preço competitivo. Apesar de prático,
o acesso a provedores de CDN muitas vezes não é financeiramente viável para pequenas
ou médias empresas, além de frequentemente existir uma obrigação de contratar o serviço
por períodos pré-estabelecidos [14].
Em paralelo ao crescimento dos sitemas VoD, também houve um acréscimo no número
de provedores de Nuvem e das empresas os utilizando. Provedores de nuvem são empresas
que oferecem softwares, plataforma de desenvolvimento ou infraestrutura como serviço.
Ao invés de uma empresa de entrega de comida, por exemplo, comprar servidores para
instalar os programas necessários para ofertar o serviço pela internet, ela pode alugar a
quantidade necessária de servidores de provedores como Amazon AWS, Microsoft Azure
ou Oracle Cloud para atender a demanda daquele momento.
Com o crescimento desses provedores de infraestrutura na nuvem, surgiram estudos
e serviços que visam utilizar estes provedores como um CDN. Um exemplo desse tipo
de serviço é o MetaCDN.org, que mesclando o uso de provedores como o Amazon S3 e
Nirvanix SDN [14], é capaz de funcionar como um CDN, porém sem a necessidade de
12
CAPÍTULO 1. INTRODUÇÃO
13
ter sua própria infraestrutura de servidores espalhados geograficamente. Como o custo
dessa infraestrutura é compartilhado entre todos os clientes dos provedores de nuvem,
é possível atingir preços menores. Esses sistemas são chamados de Cloud-CDN, pois
utilizam a infraestrutura de provedores de nuvem ao invés de contratarem um serviço de
CDN clássico [14].
Importante notar que tanto o CDN tradicional quanto o Cloud-CDN incluem também
a arquitetura de cliente-servidor, onde o crescimento da quantidade de usuários acarreta
também em crescimento da banda de saída utilizada nestes servidores. No caso da nuvem,
onde um valor é cobrado pelo uso, isto pode acarretar em aumento do preço da solução
[37].
Por sua vez, em sistemas P2P a distribuição de conteúdo normalmente é de responsabilidade dos próprios clientes, que dividem entre si o papel de cliente e servidor ao
compartilhar um conteúdo. Explorar essa característica de sistemas P2P pode diminuir
significativamente o preço da banda de saída de servidores nas nuvens [37], pois ao invés
de o tráfego fluir da nuvem para os clientes múltiplas vezes, uma vez que este dado seja
transferido da nuvem para algum(ns) cliente(s), a distribuição pode acontecer também
entre os próprios clientes, evitando a cobrança por tráfego de saída do provedor de nuvem
público. Essa combinação pode reduzir de forma significativa a banda de saída de um
sistema VoD, por exemplo [21].
Esta combinação, quando feita de modo otimizado, pode cortar custos de empresas
como o Netflix drasticamente, dada a sua dependência 1 atual de provedores de nuvem, ou
mesmo possibilitar um aumento na competição por empresas menores. O próprio governo
brasileiro2 , por meio da SAV (Secretaria do Audiovisual), órgão vinculado ao Ministério da
Cultura, anunciou recentemente planos para um sistema VoD estatal utilizando redes P2P
e CDN para distribuição do conteúdo, tornando o tema ainda mais relevante e mostrando
sua aplicabilidade em sistemas reais.
A proposta aqui apresentada visa minimizar o custo de aplicações VoD utilizando a
arquitetura P2P-Cloud CDN. Nesta arquitetura, somente a empresa provedora do vídeo
sob demanda pode disponibilizar arquivos na rede. Para minimizar o custo do aluguel de
servidores da nuvem são propostas três categorias de heurísticas que visam determinar a
melhor quantidade de máquinas alugadas do provedor de nuvem computacional, levando
em conta o número de usuários no sistema e de interrupções sofridas pelos usuários. As
heurísticas propostas focam na qualidade de experiência do usuário e não no uso dos
recursos de rede.
Como contribuições desta dissertação, elencamos a arquitetura P2P-Cloud CDN proposta, as heurísticas para alocação de máquinas na nuvem e um conjunto de protocolos
necessários para o funcionamento do sistema proposto. Além disso, uma breve discussão
de possíveis implementações eficientes deste sistema é apresentada.
Este trabalho se divide da seguinte forma. No Capítulo 2, são definidos os conceitos
básicos importantes para a dissertação. Seguido pelo Capítulo de trabalhos relacionados
(3), onde é realizada uma revisão da literatura e são apontados projetos relacionados com
1
https://media.netflix.com/en/company-blog/completing-the-netflix-cloud-migration
http://fernandorodrigues.blogosfera.uol.com.br/2016/03/11/governo-dilma-gasta-r-10-milhoes-paracriar-netflix-brasileiro-estatal/
2
CAPÍTULO 1. INTRODUÇÃO
14
o tema e suas principais diferenças.
O Capítulo 4 trata diretamente do sistema proposto, descrevendo os atores do sistema,
separação de camadas, fluxo e protocolos. Seguindo com a apresentação, o Capítulo 5
trata do modelo das heurísticas.
O Capítulo 6 define as simulações realizadas, enquanto que o Capítulo 7 apresenta
uma discussão dos resultados obtidos. E, finalmente, o Capítulo 8 conclui o trabalho,
resumindo os resultados obtidos, comparando-o com o intuito inicial e propondo trabalhos
futuros.
Capítulo 2
Conceitos básicos
Neste capítulo são definidos os conceitos básicos utilizados ao longo do texto: computação
em nuvem, protocolos P2P, Cloud CDN e P2P-Cloud CDN.
2.1
Computação em nuvem
A computação na nuvem permite que empresas e pessoas físicas aluguem máquinas e
serviços sem precisar lidar com o custo de comprar e gerenciar servidores e infraestrutura
computacional. Normalmente, os provedores de computação na nuvem cobram somente
pelo uso e permitem o aluguel de diversas máquinas, dando a impressão de infinidade de
recursos computacionais. Um exemplo de provedor de nuvem é a Amazon [2], que provê
tanto serviços, como recursos computacionais.
A computação na nuvem é normalmente dividida em IaaS (infraestrutura como serviço, do inglês Infrastructure as a Service), PaaS (plataforma como serviço, do inglês
Plataform as a Service) e SaaS (software como serviço, Software as a Service). Empresas
que provêem IaaS alugam seus servidores virtualizados para clientes. Já PaaS é fornecido
por empresas como Microsoft (Windows Azure [3]), Google (Google App Engine [1]) e
Heroku [6]. Essas empresas fornecem uma plataforma de desenvolvimento, facilitando
o desenvolvimento de aplicações e eliminando a necessidade de configuração de diversos
softwares, como banco de dados, servidores, gerentes de cache, entre outros. Os serviços
fornecidos por um provedor de SaaS por sua vez, são softwares fornecidos sem a necessidade de se configurar, pagando-se normalmente por uso ou por um custo fixo. Exemplos
de SaaS vão desde e-mails, como o GMail, até sistemas de vídeo, como o Netflix.
O aluguel por unidade de tempo de utilização em IaaS permite que as empresas utilizem somente o necessário para atender a demanda de um dado momento, aumentando ou
diminuindo o número de máquinas conforme os horários do dia ou período do ano. Por
exemplo, o provedor de infraestrutura nas nuvens Heroku disponibiliza diversos softwares
para serem utilizados em sua plataforma, entre eles o Adept Scale, que visa aumentar de
forma automática o poder computacional alugado no Heroku com base na demanda que
o sistema está recebendo[6]. Dessa forma não é necessário que o próprio usuário monitore
a demanda para balancear a infraestrutura alugada.
Um exemplo de uso de provedores de nuvem é o Netflix, serviço de VoD que mantém
15
CAPÍTULO 2. CONCEITOS BÁSICOS
16
uma base de filmes e seriados que podem ser requisitados por seus clientes. Para reproduzir
os vídeos são utilizadas instâncias de máquinas na nuvem da amazon [7], juntamente com
o Amazon Auto Scale (AAS). O AAS é um serviço disponibilizado na nuvem da Amazon
que controla o aluguel de máquinas a partir do número de requisições no momento. Os
clientes do Netflix assistem o vídeo por stream 1 na Internet, não podendo armazenar os
vídeos para assistirem desconectados.
Cada provedor de IaaS provê a alocação de máquinas em diferentes regiões por preços
diferentes. Por exemplo, na Amazon EC2 uma máquina na área central dos EUA é mais
barata que uma máquina no sudeste do Brasil.
Os principais provedores de nuvem incluem a Amazon e a Microsoft. Atualmente a
Amazon é a empresa com maior fatia do mercado 2 , seguida pela Microsoft. Ambas as
empresas oferecem máquinas virtuais de configurações variadas. As instâncias variam de
acordo com o poder computacional e a região escolhida. Ambas as empresas oferecem a
possibilidade de utilizar imagens de sistemas operacionais criadas pelos usuários.
Ambas as empresas não cobram pelo tráfego de entrada das instâncias, porém cobram
pela quantidade de gigabytes que saem das instâncias para fora da rede local. A principal
diferença entre as duas competidoras é que a Microsoft cobra diferentes valores dependendo do local da saída de dados (separando em basicamente três zonas, o Brasil sendo a
zona mais cara).
Neste trabalho é utilizado um IaaS como fonte das máquinas utilizadas no sistema
VoD. São considerados tanto o custo das máquinas, sendo cobrado por unidade de tempo
em que a máquina permanece ligada, como o custo de saída de dados da nuvem.
2.2
Protocolos P2P
Redes Peer-to-Peer são redes onde o paradigma de cliente-servidor é compartilhado pelos
nós da rede. Cada nó é responsável tanto por responder requisições de outros clientes na
rede, como agir como um cliente. Estas redes são amplamente utilizadas para compartilhar conteúdo, sejam filmes, seriados ou outros arquivos. Também é possível compartilhar
recursos computacionais, como no caso da freenet [4, 17], onde os usuários da rede compartilham espaço em disco para armazenar dados de forma anônima.
Os nós participantes são responsáveis pela configuração da rede overlay. A rede overlay
é uma rede montada virtualmente pelos nós para interligar todos os usuários (Figura 2.1).
A rede overlay deve conseguir manter os nós conectados, mesmo se algum dos nós vier
a sair, e deve ser eficiente para evitar gargalos por conta da rede física. Esta rede não
precisa ser parecida com a rede física e nós podem ser vizinhos na rede overlay mas não
na física e vice-versa.
Diversos sistemas de VoD utilizando protocolos P2P surgiram nos últimos anos, entre
eles o popcorn-time [8]. O popcorn utiliza uma modificação do protocolo bittorrent [5, 9]
para prover o vídeo requisitado pelo usuário. O protocolo bittorrent divide o arquivo
1
Stream de arquivos em geral, pode ser definido como o ato de receber ou enviar dados pela internet
por um fluxo contínuo, sem a necessidade de esperar a transferência do arquivo inteiro antes de usá-lo.
2
http://uk.businessinsider.com/why-amazon-is-so-hard-to-topple-in-the-cloud-and-where-everybodyelse-falls-2015-10
17
Figura 2.1: Exemplo de overlay de uma rede P2P: as conexões entre os nós não necessariamente refletem a conexão na rede física.
em diversas partes e requisita estes pedaços aos usuários que já têm o arquivo em seu
computador. Normalmente, o bittorent faz requisição dos pedaços (chunks) mais raros
primeiro, para evitar que os poucos nós que já obtiveram aquele chunck se desconectem
da rede e façam com que seja impossível o término da transferência do arquivo. Essa
abordagem, apesar de boa para arquivos, é ruim para streams de vídeo [30, 24]. Uma
das modificações que o popcorn-time implementa envolve a requisição dos chunks. Ao
invés de requisitar os raros primeiro, ele procura requisitar os chunks sequencialmente [5].
Outras pequenas modificações no protocolo podem ser implementadas, como por exemplo
em [32], onde os nós da rede também reportam sua capacidade de upload para o tracker
a fim de medir a quantidade deste recurso computacional disponível na rede.
Como as máquinas dos usuários são utilizadas como cliente e servidor, o serviço é
composto por máquinas e redes heterogêneas não sendo possível afirmar se os nós da rede
permanecerão por um longo tempo ligados ou serão desligados em poucos segundos. Além
disso, não se pode contar que ao sair do sistema os usuários irão enviar uma mensagem
avisando aos outros participantes para removê-lo de suas listas de IPs.
O sistema P2P é utilizado neste trabalho como uma forma auxiliar de se distribuir
o conteúdo dos vídeos. Desta forma, sua única responsabilidade é diminuir a banda de
saída dos servidores da nuvem, mas não necessariamente substituí-los.
2.3
Cloud-CDN
Com o advento da computação nas nuvens, a construção de um CDN sem o alto custo de
operar um data center geograficamente distribuído é possível. Estes CDNs, em oposição
ao CDN tradicional, são definidos em [14] como Cloud-CDN, onde os usuários podem
18
Figura 2.2: Arquitetura do MetaCDN.org [12]
construir seu CDN global simplesmente se tornando consumidores de diversos provedores
de armazenamento na nuvem. A arquitetura do sistema MetaCDN.org (Figura 2.2), descrito em [14] demonstra a capacidade do Cloud-CDN de se adaptar a diversos provedores,
deixando transparente o uso em conjunto destes. Além disso, o Cloud-CDN pode escolher
qual o provedor mais barato, capaz de cumprir o SLA de uma certa região. Porém esta
escolha não é trivial, pois há a necessidade de se considerar tanto o preço para transferir
o dado para o usuário, como o preço da duplicação dos dados entre os provedores (custo
de se transferir o arquivo entre os servidores e custo de armazenamento) [14].
Como consumidor de provedores de armazenamento na nuvem, o Cloud-CDN pode
tirar vantagem dos preços oferecidos por diferentes provedores, a fim de reduzir sua própria
despesa. Com o poder de escalar de acordo com a demanda provida pela computação nas
nuvens, Cloud-CDNs podem ajustar o preço a ser cobrado de seus clientes de acordo com
a demanda requisitada por eles [14].
Por outro lado, são necessárias estratégias para o gerenciamento de máquinas na nuvem
conforme a demanda. Alugar máquinas somente nos períodos de alta demanda pode levar
o sistema a deixar de responder alguns usuários, pois iniciar uma máquina na nuvem
pode levar de segundos a minutos, dado a necessidade de requisitar a máquina e instalar os
softwares para o funcionamento da máquina no sistema. Além disso, há a possibilidade do
provedor não ter máquinas disponíveis em uma certa região. Para a redução do tempo de
instalação dos programas necessários, é possível utilizar imagens de sistema operacionais
customizadas para o Cloud-CDN.
2.4
P2P-Cloud CDN
A união da rede P2P e de provedores Cloud para a criação de um CDN é chamada de
P2P-Cloud CDN [21]. Esses sistemas utilizam-se da alta escalabilidade, redundância e
19
Figura 2.3: Arquitetura de um sistema P2P-Cloud CDN: o usuário u (círculo rosa) faz
requisições para o grupo de usuários U (círculo verde) e para o CDN (retângulo azul). As
duas fontes compartilham o arquivo b (arquivo de vídeo) simultaneamente com u.
distribuição geográfica da nuvem computacional para prover um CDN de menor custo,
se comparado com o custo de um CDN tradicional. Além disso, possibilita que os usuários compartilhem entre si os arquivos de vídeo, o que minimiza o custo da banda de
saída dos servidores da nuvem. Dessa forma, a nuvem (por sua característica estável)
pode orquestrar o envio dos arquivos da rede P2P para os usuários e prover o próprio
arquivo caso a demanda do arquivo não seja suprida pela rede P2P. Por outro lado, a
rede P2P pode focar em prover os arquivos aos usuários, por sua característica natural
de compartilhamento de recursos.
Com a combinação de um CDN e uma rede P2P, um usuário u que deseje um vídeo b
requisitará ao CDN o arquivo. O CDN por sua vez, iniciará a transferência dos dados, e
também enviará uma lista contendo o endereço de outros usuários U assistindo ao mesmo
vídeo. O usuário, pode então requisitar trechos do arquivo b para todos os usuários de
U (Figura 2.3). Quanto mais pedaços ele requisitar do conjunto U , menor será o custo
dos servidores CDN para enviar aquele arquivo, porém pela característica instável da rede
P2P, o vídeo b pode ser transferido mais lentamente. Nesta dissertação apresentamos uma
arquitetura P2P-Cloud CDN e propomos heurísticas que visam minimizar o custo final
do sistema, sem denegrir a qualidade de experiência do usuário.
Capítulo 3
Trabalhos Relacionados
No problema de alocação de recursos em P2P-Cloud CDN, o custo está correlacionado
com a qualidade de serviço, pois além de não deixar os clientes em inanição, é necessário
prover uma vazão que dê ao usuário uma boa experiência. Geralmente há um compromisso
entre custo e QoS.
Para cumprir com o QoS, os autores de [14] criaram algumas heurísticas focadas em
replicar os arquivos entre os diversos provedores de armazenamento nas nuvens, a fim de
manter o SLA baseado na distância do usuário ao servidor da nuvem. Estas heurísticas
levam em consideração o orçamento do usuário e as regiões onde o cliente pretende que
o arquivo seja acessado. Para otimizar o custo neste caso, além do custo das máquinas
alugadas, é necessário adicionar o custo do upload e download de cada instância. Para
isto, [14] utiliza nas heurísticas o custo de se replicar os dados entre os provedores, além
da distância do usuário ao provedor.
Os autores de [14] não citam o funcionamento ou o desempenho dessas heurísticas,
porém focam em seu artigo nas abstrações criadas pelo serviço MetaCDN.org, que visa
ser um ponto central de comunicação para desenvolvedores que queiram usar diversos provedores de armazenamento na nuvem sem a necessidade de aprender e utilizar diferentes
SDKs.
Já o Netflix, contrata três diferentes CDNs (Akamai, LimeLight e Level-3) e utiliza
o protocolo DASH (Dynamic Streaming over HTTP) [10]. O DASH é um protocolo,
onde cada vídeo é salvo com diferentes qualidades e é dividido em pequenos “chunks”
(segmentos de vídeo de alguns segundos). O cliente requisita um chuck por vez. A cada
download o cliente decide qual a qualidade do chunk da próxima requisição.
O Netflix ainda possui um software para prever picos de uso chamado Scryer [7]. A
ideia do sistema é prever quando haverá um aumento de audiência, para que o Netflix
possa alugar novos servidores na nuvem da Amazon a fim de suprir estes usuários sem
degradar seu serviço. Exceto em dias especiais como feriados ou em grandes eventos, os
acessos ao Netflix seguem um padrão. O Scryer então se baseia no padrão do passado para
tentar prever os acessos do futuro, aumentando ou diminuindo a quantidade de servidores.
O Scryer é utilizado em conjunto com o Amazon Auto Scale (AAS) [7]. O AAS tem
como foco aumentar a quantidade de servidores na nuvem da Amazon quando o sistema começa a receber uma quantidade de requisições parametrizável. O AAS funciona
perfeitamente, mas as máquinas do Netflix demoram de 10 a 45 minutos para iniciar
20
CAPÍTULO 3. TRABALHOS RELACIONADOS
21
[7]. Aumentar a quantidade de máquinas somente quando o sistema começa a receber
muitas requisições pode fazer com que alguns usuários não tenham o QoS esperado, principalmente em picos repentinos. Por isso o Scryer é tão importante: ao tentar prever
a demanda, é possível iniciar as máquinas em um tempo hábil, evitando degradação do
serviço.
Em experimentos feitos pelos autores de [10], foi constatado que o Netflix escolhe um
CDN para o usuário e só o substitui caso não seja possível cumprir nem com o QoS para
baixa resolução. Esta escolha permanece a mesma durante semanas, até mesmo se o
usuário acessar sua conta de lugares afastados, parecendo não levar em conta a posição
geográfica do usuário, pois dois usuários vizinhos podem estar se alimentando de dois
CDNs diferentes. Por isso, em [10] os autores propuseram um sistema, onde o reprodutor
de vídeo estima qual CDN está melhor logo no começo do vídeo e faz com que o usuário
fique alocado a ele.
No artigo [11] é utilizado um “Layered streaming”. Layered streaming, como por exemplo o Scalable Video Coding (SVC), separa o vídeo em diferentes camadas. Se o usuário
requisitar todas as camadas, ele terá um vídeo na melhor qualidade disponível, porém
se requisitar somente a primeira, terá a mais baixa do sistema. Partindo do pressuposto
que a banda de entrada/saída dos usuários tem um grande impacto na qualidade de sistemas de stream utilizando P2P, o artigo descreve um sistema de leilão para adquirir
estas camadas do vídeo, visando otimizar o uso da banda de entrada/saída dos usuários,
maximizando a escolha dos chunks.
Os autores de [11] também supõem a utilização de uma categoria especial de peers,
chamada de upstream peers, que são responsáveis por servir os downstream peers. Os
downstream peers “competem” pela banda de saída do upstream, oferencendo uma certa
quantia de “dinheiro virtual ” para eles. Cada peer tem um orçamento para definir a
máxima oferta. Para satisfazer uma qualidade mínima, todos os nós tem direito ao layer
básico, ofertando mais dinheiro para conseguir um vídeo em maior definição. Com este
modelo de leilão, foi observada uma maior capacidade de utilização da banda de saída dos
nós da rede P2P. Apesar do presente trabalho não utilizar o esquema de leilões, considera
alguns critérios para a utilização da banda de saída dos nós. Apenas nós selecionados
efetivamente colaboram com o stream como se fossem um servidor da nuvem, enquanto
que os demais colaboram com os últimos pedaços, porém em caso de perda de pacotes
deste último, o stream não é afetado.
Em [21], é definido que a prioridade de um sistema de VoD com assistência de peers é
economizar a banda de saída dos servidores. Por isso o servidor deve ser usado somente
para suprir a demanda que os peers não são capazes de responder. Utilizando a política
de water-leveling, o sistema conseguiu uma eficiência próxima do limitante inferior de
banda para o problema utilizando servidores próprios. O water-leveling visa equalizar
a quantidade de conteúdo pré-alocado para todos os nós da rede. Por exemplo, se um
nó tem uma quantidade menor de arquivo que os demais – pois acabou de entrar no
sistema –, os servidores irão se focar neste nó. Quando o nó alcançar a mesma quantidade
de bytes no arquivo que os demais, os servidores voltam a servir normalmente todos os
peers, tentando sempre manter o equilíbrio. Com dados de nove meses de uso do website
MSN Vídeos, os autores simularam a utilização do website utilizando uma rede P2P para
22
auxiliar o envio de dados, utilizando a política water-leveling. Enquanto que o pico do
sistema sem P2P chegou a utilizar 1.5 Gbps de banda do servidor, o sistema com P2P
utilizou cerca de 0.6 para os arquivos.
Os autores de [21] também levantam a necessidade do P2P levar em consideração a
posição geográfica dos usuários para ser amigável com provedores de internet (ISP, Internet
Service Provider). O tráfego que cruza diferentes ISPs gera um custo para ambos os lados,
enquanto que o tráfego dentro da própria rede do ISP não. Este tipo de sistema diminui
a utilização de infraestrutura dos ISPs para a distribuição de conteúdo, mas por outro
lado torna o compartilhamento dos usuários mais difícil, já que uma região com poucos
usuários não se beneficiará da rede P2P como uma região mais populosa. Porém, mesmo
este cenário se beneficia da rede P2P, diminuindo a utilização dos servidores.
Ao invés de todos os nós trocarem os arquivos, é possível eleger super nós (por alguma
característica dos clientes, como idade do nó no sistema, banda de saída e entrada, entre
outros). Esses super nós seriam responsáveis por repassar dados para os nós comuns.
Além disso, é possível distribuir o controle do sistema P2P entre os super nós, fazendo
com que eles sejam responsáveis por pequenos sub-grupos [29]. Em [29], os autores tentam
identificar o tráfego gerado por superpeers em uma rede P2P privada como o KaAza. Dado
que em muitos sistemas, o usuário não é notificado que seus recursos computacionais estão
sendo utilizados de uma maneira mais agressiva para alimentar a rede. O trabalho foca
em heurísticas para verificar o uso de CPU e de rede para classificar peers como ordinários
ou super peers.
Sistemas VoD implementados usando somente a rede P2P dividem o arquivo de vídeo
em segmentos, que são distribuídos entre os nós da rede. Neste ambiente um dos requerimentos mais importantes é ser eficiente em descobrir quais usuários tem certos segmentos
de vídeo [33]. Em[33], é proposto um sistema dinâmico e distribuído para a busca de
meta-dados sobre o vídeo (juntamente com os segmentos) em um Cloud-P2P VoD. Para
isso divide o sistema em duas partes: a nuvem, responsável pela busca de meta-dados do
vídeo e a rede P2P responsável pela busca e envio de segmentos de vídeo. O estudo se
difere principalmente por utilizar nós da rede P2P que já obtiveram todo o arquivo como
trackers, enquanto que nesta dissertação o tracker é um nó estático da nuvem. Outro
ponto de divergência está na utilização da nuvem: o presente trabalho utiliza a nuvem
para coordenar os nós da rede P2P além da responsabilidade de colaborar com o stream,
enquanto que [33] mantém somente os meta-dados necessários armazenados na nuvem. A
arquitetura de [33] se mostrou eficiente para a busca de pedaços aleatórios do arquivo na
rede P2P. Por outro lado, pode causar um aumento no tempo de resposta nos servidores
de stream, caso o número de trackers não seja bem manejado.
Em [26, 27], os autores estudaram a sinergia entre CDN e redes P2P para entregar
vídeos em um sistema similar ao Youtube. Os autores demosntraram que 60% de todas as
requisições poderiam ser resolvidas somente pela rede P2P. Em [26], os autores estudaram
o papel de peers estáveis na disponibilidade do conteúdo. Usuários reproduzindo listas de
vídeos eram marcados como estáveis e os usuários utilizando o sistema de recomendação
como instáveis. Usando estas duas categorias, as requisições respondidas pelo CDN podiam ser reduzidas em até 60%. Em [27], utilizando uma rede P2P menos eficiente, onde
os peers eram responsáveis pelo mecanismo de pesquisa, 20% das requisições podiam ser
23
respondidas somente pelos peers.
A LiveSky [35] utiliza de uma arquitetura similar a desta dissertação para transmitir
eventos ao vivo [35]. O sistema em produção utiliza uma rede CDN auxiliada por uma
rede P2P. Apesar de não usar um provedor de nuvem para adquirir novas máquinas, a
LiveSky endereça pontos chaves da arquitetura P2P-Cloud CDN, como:
• Prover uma boa qualidade de serviço para o usuário, garantido o início da transmissão o mais rápido possível, poucas interrupções, etc.
• Problemas bem conhecidos de sistemas P2P, como a baixa qualidade da transmissão,
taxa de banda de saída e entrada heterogênea, diferente taxas de contribuição entre
os usuários.
O CDN em [35] é separado em três componentes: (i) O Centro de Controle, (ii) o
balanceador de carga por DNS e (iii) o servidor de cache. O terceiro item é responsável
pela distribuíção do conteúdo aos usuários. Os usuários se dividem em usuários legados
(sem o componente de P2P) e usuários com o LiveSky habilitado, que se beneficiam da
rede P2P. Os usuários da rede P2P são organizados em forma de árvore. É considerado que
todos os usuários no mesmo nível da árvore recebem um determinado pedaço ao mesmo
tempo. O CDN alimenta a raiz da árvore e os usuários são responsáveis por repassar o
conteúdo aos demais níveis. Para a avaliação do sistema os autores de [35] utilizaram o 17
Congresso do Partido Comunista Chinês. No ponto de pico da transmissão, havia 145.000
clientes. A contribuição para o envio dos dados foi de 35 Gbps partindo dos nós do CDN
e 17 Gbps dos nós da rede P2P.
Em [34] são simulados cenários de Cloud-P2P CDN utilizando o framework OMNeT++. A arquitetura apresentada é parecida com a deste trabalho, porém não é levado
em conta o custo de se transferir dados da nuvem, somente o número de máquinas alocadas
na nuvem. Também não considera o uso de nós da rede P2P em diferentes papéis, como
superpeers. Além disso, a definição de qualidade de serviço é diferente. Enquanto neste
trabalho consideramos o número de interrupções durante a visualização do vídeo, em [34]
é considerado a latência do playback, o delay ponto a ponto (quanto tempo demora para
um dado ser transferido), o número de distorção (número de chunks que um usuário não
pode visualizar no tempo correto) e tempo para início do vídeo. Pelo foco da dissertação
estar no nível de aplicação e não de rede, não são considerados fatores como latência nas
heurísticas.
Os trabalhos aqui citados, se aproximam do presente trabalho, porém apresentam
diferenças tanto no tema de estudo, como na arquitetura empregrada. O artigo [11]
se diferencia por não utilizar a nuvem ou outro servidor próprio para auxiliar o envio
de vídeos. O sistema estudado em [10] da empresa Netflix, não utiliza a nuvem como
CDN, somente provedores tradicionais de CDN. Enquanto que em [14] é desenvolvido
um sistema de Cloud-CDN, porém sem a utilização da rede P2P para minimizar o custo
dos servidores, assim como [7]. A camada de coordenação de servidores nas nuvens visa
replicar os dados entre diferentes provedores, de acordo com o SLA e custos máximos
definidos para a solução. Em [14] são descritas algumas heurísticas para este problema.
Porém o problema difere do nosso por não precisar levar em consideração a taxa de upload
Caractéristicas
P2P
CDN ou Nuvem?
Conteúdo ao vivo?
24
Tabela 3.1: Comparação entre as arquiteturas
Proposta
Sim
Nuvem
Não
Netflix
Não
CDN/Nuvem
Não
LiveSky
Sim
CDN
Sim
MetaCDN.org Simulação com o MSN videos [21] Popcorn-time
Não
Sim
Sim
Nuvem
CDN
Nenhum
Não
Não
Não
da rede P2P. Assim, o custo de nossa proposta tende naturalmente a ser menor, já que
é possível provar trivialmente que a banda de saída de nossos servidores diminui sempre
que a banda de compartilhamento da rede P2P aumenta. Já em [21] é utilizada uma
rede P2P para auxiliar o servidor no stream de vídeos, mas não é levado em conta o QoS
necessário para o usuário. O trabalho em [31] utiliza a nuvem apenas como auxiliar da
rede P2P, ao invés de utilizar a rede P2P apenas para reduzir o custo da nuvem. Os
autores de [26, 27] se focam no estudo dos nós estáveis da rede, enquanto esta dissertação
estuda o efeito da alocação de servidores no stream de vídeo. E [33] utiliza provedores
de nuvem somente para auxiliar na busca por meta-dados na rede (como transcrição do
vídeo, título e palavras-chaves). Os principais trabalhos relacionados podem ser vistos na
tabela 3.1.
Capítulo 4
O sistema
Neste capítulo a arquitetura do sistema proposto é introduzida, com uma breve definição dos atores do sistema, juntamente com a divisão dos componentes e os protocolos
utilizados.
4.1
Atores do sistema
Os atores do sistema são separados em três grandes grupos com suas próprias divisões.
Servidores da nuvem, que são alugados de provedores, usuários requisitando os vídeos e
superpeers, usuários que colaboram de forma mais efetiva no compartilhamento de dados.
4.1.1
Provedor do sistema de vídeo sob demanda
No sistema proposto na dissertação, o único ator capaz de disponibilizar vídeos é a empresa
provedora do VoD. Agindo como o Netflix, onde a empresa faz acordos comerciais com
estúdios e emissoras de TV para disponibilizar o vídeo em seu próprio sistema. Usuários
não são capazes de enviar seus próprios arquivos para a rede.
4.1.2
Servidores da Nuvem
As máquinas alocadas na nuvem (S) são dividas em duas categorias. Os trackers (um
por região) e os servidores responsáveis pela transmissão do vídeo. A máquina alocada
para o tracker é alugada por todo o período que o sistema está online, enquanto que as
máquinas responsáveis pela transmissão do vídeo são alocadas de acordo com as estratégias
adotadas.
É possível utilizar um serviço como o Simple Storage System (S3) da Amazon para
armazenar todos os vídeos disponíveis no CDN. Como a transferência dentro da própria
rede da Amazon é gratuita, a transferência para as máquinas virtuais seriam gratuitas,
sendo cobrado somente o custo do armazenamento e do envio dos vídeos ao S3. A máquina
virtual ao iniciar, poderia requisitar ao S3 o conteúdo. Caso um usuário requisite um
pedaço do arquivo que a máquina ainda não tem em disco, a máquina provocaria uma
exceção (page-fault) e redireciona a requisição diretamente para o S3.
25
CAPÍTULO 4. O SISTEMA
26
Figura 4.1: Usuário u recebe pedaços de Chunk em round-robin dos Servidores a, b e dos
Superpeers l, m.
Porém neste trabalho não se considera a cópia do arquivo entre a fonte (por exemplo
o S3) e as máquinas alugadas, sendo considerado que a máquina ao iniciar já estará
com o vídeo em seu sistema de armazenamento interno. Além disso para simplificar o
problema, é utilizado somente um tipo de instância (processador, quantidade de memória
e armazenamento interno).
O custo neste trabalho considera tanto o preço do aluguel das máquinas como a transferência de dados para o usuário, sendo os preços baseados na Amazon EC2.
4.1.3
Usuários
Os usuários (U ) do sistema colaboram com a transmissão de dados assim que obtiverem os primeiros chunks do vídeo. Ao fazerem a requisição ao tracker requisitando um
filme, eles obtêm como resposta os endereços de IP dos servidores e usuários capazes
de compartilhar o vídeo. O próprio usuário requisita para toda a lista de IPs os pedaços necessários, utilizando round-robin(Figura 4.1, onde o usuário u começa requisitando
ao servidor a passando para b e aos superpeers l, m, em cada turno, respectivamente).
Enquanto que servidores entregam os chunks em ordem cronológica, os demais usuários
que estão fornecendo os chunks entregam de trás para frente. Dessa forma o progresso
sequencial do vídeo não é afetado caso os usuários deixem o sistema repentinamente ou
sejam sobrecarregados com requisições.
4.1.4
Superpeers e organização dos usuários
Os superpeers (P ) neste sistema são usuários que colaboram com o sistema da mesma
forma que servidores (compartilhando os pedaços em ordem cronológica). Superpeers são
divididos em dois grupos. Os seeders, usuários que tem o arquivo de vídeo completo em
seu sistema de armazenamento e os superpeers escolhidos por mecanismos de gerência do
sistema para colaborar com o sistema. Este sistema de gerência ordena os usuários em
ordem decrescente de tempo de entrada no sistema e escolhe os primeiros da lista. Os
superpeers são escolhidos dentre os usuários que já baixaram mais de 30 chunks pelas
heurísticas sempre que necessário.
Como usuários que estão há mais tempo no sistema também são aqueles que estão
perto do final do vídeo, uma outra estratégia poderia dar preferência aos usuários que
estão no tempo médio do vídeo dentre todos os usuários daquele vídeo, assim eles teriam
27
em seu dispositivo de armazenamento uma quantidade maior de segmentos de vídeo que a
média dos usuários e ainda permaneceriam no sistema por um período maior que usuários
que já estão no fim do vídeo.
Um superpeer não pode ser “rebaixado” ao papel de peer uma vez escolhido. Porém
o usuário ainda pode se desconectar da rede, fazendo com que o número de superpeers
possam variar em sistemas reais. Nas simulações é considerado que os superpeers são nós
estáveis e permaneceram no sistema até o final.
A lista de superpeers, assim como de todos os usuários participantes da rede P2P, é
mantida em servidores da nuvem (chamados de Trackers). Esses servidores são responsáveis por notificar os outros usuários da presença de um novo superpeer, mantendo assim
os superpeers apenas como uma fonte para o arquivo sem delegar a responsabilidade por
manter meta-dados do sistema. Quando um usuário finaliza o recebimento do vídeo, ele
avisa o Tracker, que passa a considerá-lo como superpeer.
Utilizando os superpeers apenas como canais de distribuição de conteúdo, ao invés
de terminais inteligentes, eliminamos a necessidade de criar estratégias para eliminar a
latência inicial da busca por meta-dados na rede P2P. Por exemplo, em [33] é descrito
um sistema onde os próprios nós da rede P2P agem como tracker e são os responsáveis
por encontrar meta-dados sobre os arquivos multimídia armazenado nos nós, pois não é
possível saber ante-mão quais os vídeos disponíveis na rede. Desta forma há a necessidade
de organizar os peers em árvores AVL e tabelas hash distribuídas (Distributed Hash
Tables, DHT) ou utilizar outros tipos de algoritmos para recuperar esses meta-dados.
Desta forma, a arquitetura de [33] não mantém um único ponto de falha, enquanto que
a arquitetura aqui proposta mantém uma dependência das instâncias de máquinas no
provedor de nuvem. Também em [18] é dito que uma desvantagem da utilização do P2P
em comparação a arquiteturas cliente-servidor utilizando unicast decorre da maior latência
para o início da exibição de um vídeo, dado a necessidade de se trocar mensagens para
descobrir quais outros usuários possuem o conteúdo desejado. Como neste trabalho essa
informação é armazenada centralmente no Tracker, não é necessária a troca de informações
iniciais, removendo está latência inicial.
4.2
Divisão do sistema
A primeira requisição do usuário é feita para o tracker regional. O tracker é responsável por
manter uma lista de todos os usuários conectados no sistema e dos servidores disponíveis.
É neste servidor que o banco de dados é alocado e é o ponto central de comunicação.
Qualquer outro componente que precise armazenar ou coletar dados terá que conversar
com o tracker. O tracker responde a requisições de usuários pelos filmes com duas listas
de IPs, uma com os servidores da nuvem e superpeers e a outra com usuários que estão
ativos e assistindo ao mesmo filme (Figura 4.2).
A transmissão inicial do arquivo multimídia é realizada por máquinas alocadas na
nuvem. Estas máquinas são responsáveis somente pelo envio do arquivo e respondem as
requisições por chunks dos usuários, sem conter nenhum tipo de lógica interna.
As estratégias apresentadas nesta dissertação, precisam de algumas informações para
28
Figura 4.2: Fluxo do Tracker ao receber uma requisição do usuário.
decidir a ação a ser feita. Estas informações e coordenação das estratégias é realizada
pelo componente de monitoramento, que inclui um banco de dados onde há salvo o número de usuários no sistema, número de servidores, número de interrupções no vídeo
causado pela falha em conseguir os dados necessários para aquele momento de exibição e número de supeerpeers. As interrupções (Di) são calculadas pelos próprios usuários. As interrupções são computadas numa escala de x minutos e ocorrem quando
chunks_recebidos ⇥ tamanho_chunk é menor que QoE_KBP S ⇥ playback_window,
onde chunks_recebidos é o número de chunks recebidos cujo o prazo de playback está
na janela deslizante atual e QoE_KBP S é a quantidade em kilobytes de dados que
precisa ser entregue por segundo para evitar uma interrupção. playback_window é a
diferença de tempo entre o momento atual e o inicio da transmissão. Na Figura 4.3
é possível ver a representação visual desse cálculo, onde o usuário (a) não sofre interrupção em seu vídeo, dado que a quantidade de chunks recebidos (chunks_recebidos) é
maior que QoE_KBP S ⇤ playback_window considerando somente os chunks anteriores
a playback_window, enquanto que o usuário (b) sofre uma interrupção.
O número de interrupções de cada usuário é enviada para o tracker, que agrega todos
os valores. O fluxo do componente pode ser visto na imagem 4.4.
4.3
Protocolos
Para simplificar as simulações realizadas com as heurísticas propostas, foram criados
dois protocolos para a transmissão do vídeo. Os servidores e superpeers utilizam-se de
um protocolo onde o cliente não precisa enviar todo o estado da transmissão, bastando
enviar uma mensagem com o identificador do chunk necessário, como na estrutura JSON:
“{identificador: 10}”. Como resposta, o usuário recebe em binário o chunk requisitado.
Já no caso da comunicação entre os peers, é necessário que o requisitante envie o
29
Figura 4.3: Representação visual do cálculo das interrupções. Onde playback_window
representa um intervalo de tempo, e QoE_KBP S ⇤ playback_window todos os chunks
que deveriam ter sido visualizados pelo usuário até aquele instante.
Figura 4.4: Fluxo do sistema de monitoramento.
30
estado atual do seu “mapa de chunks” (um vetor binário onde cada posição representa se
o usuário recebeu ou não o respectivo chunk), para que o peer consiga enviar o primeiro
pedaço em ordem inversamente cronológica. A resposta do peer para a requisição é o
chunk em formato binário.
Do lado do usuário, são utilizados dois componentes: o orquestrador e o monitor.
O Orquestrador é responsável por requisitar os pedaços do arquivo de vídeo para os
servidores e outros usuários da rede P2P (utilizando o protocolo descrito acima). Já o
Monitor é responsável por monitorar as interrupções e enviar ao Tracker o estado atual
do usuário.
O Tracker contém seis métodos, todos relacionados com o estado do sistema:
• requisitar_f ilme: Este é o ponto inicial do sistema. O aplicativo do usuário ao
acessar o sistema do provedor de vídeo chama este método passando seu próprio IP
e o identificador único do filme. Retorna uma lista de IPs de usuários assistindo o
mesmo filme, servidores e superpeers.
• adicionar_servidor: Sempre que um servidor é ligado, este método é chamado
para o adicionar à lista de servidores disponíveis. Este método recebe uma lista de
identificadores únicos dos filmes disponíveis no servidor, juntamente com o IP do
servidor.
• remover_servidor: Método chamado quando um servidor é desligado, recebendo
como parâmetro o IP do servidor a ser desligado.
• listar_servidores: Retorna o IP de todos os servidores ligados.
• listar_superpeers: Retorna o IP de todos os superpeers.
• estatisticas: Este método é chamado pelo componente de monitor para salvar no
banco de dados do sistema o estado da execução do vídeo de um usuário. Recebe
como parâmetros o endereço IP do usuário, quantidade de interrupções e quantidade
de segmentos de vídeo disponíveis no sistema de armazenamento do usuário.
• obter_estatisticas: Recebe o IP do usuário como parâmetro e retorna a quantidade
de interrupções e quantidade de segmentos de vídeo disponíveis no sistema de armazenamento do usuário e se o usuário é ou não um superpeer. A chamada também
pode ser feita sem o IP do usuário, passando o identificador de um filme. Neste
caso, o método retorna o número absoluto de interrupções de todos os usuários de
um dado filme.
• usuarios_assistindo: Recebe como parâmetro o identificador de um filme e retorna
o IP de todos os usuários o assistindo.
Em um fluxo normal de funcionamento do sistema, o usuário requisita o vídeo utilizando o método requisitar_f ilme do Tracker. Com a lista de IPs o usuário requisita os
segmentos do filme para os servidores, superpeers e usuários. A cada monitoramento, o
Monitor instalado no computador do usuário chama estatisticas para enviar seu estado
atual.
31
A heurística chama obtere statistica com o identificador do filme para obter o número
total de interrupções e listar_servidores e listars uperpeers para o número de servidores e
superpeers, respectivamente. Com essa informação, a heurística toma a decisão de alugar
ou liberar servidores (chamando adicionar_servidores ou remover_servidores, respectivamente). Para a criação de novos superpeers, o sistema chama usuarios_assistindo e
seleciona do resultado aqueles usuários que devem se tornar superpeers.
Capítulo 5
Modelo
Nas seções seguintes o problema da gerência de VMs em Cloud-P2P CDN é formalizado
e também são apresentadas as três categorias de heurísticas propostas.
5.1
Redução do custo
A utilização de um P2P-Cloud CDN no lugar de um Cloud CDN puro para a distribuição
de vídeo sob demanda é motivada principalmente pela redução de custo do primeiro. Esta
redução de custo pode ser alcançada utilizando como principal meio de envio de dados a
rede P2P. Entretanto, dada a natureza heterogênea dos nós na rede P2P, existem grandes
chances da frequência de pacotes ser afetada drasticamente. Torna-se, então, necessário
alocar a quantidade certa de banda da rede P2P e da nuvem para otimizar o custo, sem
grande impacto na qualidade de serviço fornecida pelo sistema.
Este problema de minimizar o custo pode ser reduzido ao problema definido como “the
optimal bandwidth allocation problem”, OBAP, descrito em [25]. Considere um sistema
com I arquivos, onde cada arquivo i pode ser requisitado por um usuário u. Quando um
usuário u requisita o arquivo, o servidor envia o arquivo a uma taxa de upload si , e todos
os usuários que também têm aquele arquivo em seu dispositivo de armazenamento enviam
m
P
a uma taxa di . OBAP define que é necessário maximizar D
,
sendo
D
=
di , onde m é
S
o número de usuários baixando o mesmo conteúdo e S =
m
P
i=1
i=1
si , onde S é a alocação de
servidores na nuvem para suprir a demanda dos usuários.
O custo de uma solução implementada utilizando nuvem computacional pode variar
de acordo com o provedor de serviço utilizado. Como o foco do CDN são aplicações de
alta entrada e saída de dados, este trabalho leva em consideração o preço das máquinas
necessárias para a utilização do CDN e controle dos nós na rede P2P, além do custo de
download e upload dos arquivos a fim de sincronizar diferentes nós e distribuir o arquivo
ao usuário final. Para este fim, a equação 5.1 define o custo Ps de uma máquina alugada
na nuvem, onde Cqty é a quantidade de dados enviados pela nuvem, Cprice o preço do
envio de dados pelo provedor, Rprice é o preço de se alugar uma máquina por uma hora e
Tp é a quantidade de horas que a máquina foi alugada.
32
CAPÍTULO 5. MODELO
33
Figura 5.1: Fluxo da arquitetura do sistema.
Ps = Cqty ⇤ Cprice + Rprice ⇤ Tp
(5.1)
O custo total do sistema (P r) é dado pela equação 5.2.
size(S)
Pr =
X
Ps
(5.2)
s=1
As heurísticas aqui apresentadas não levam em conta o preço momentâneo – custo
das máquinas alugadas somada a quantidade de dados enviados aos usuários – do sistema
como parâmetro de entrada, mas somente a qualidade de serviço (número de interrupções
percebidas pelo usuário ao ver o vídeo). Sendo P r uma variável utilizada somente para a
avaliação da eficiência das heurísticas.
A coordenação dos servidores nas nuvens (replicar dados, direcionar o usuário para o
melhor provedor levando em consideração SLA e custo) é um problema NP-difícil [14] e
por isso não se espera ter alocação ótima de servidores nas nuvens.
Por fim, o fluxo do sistema proposto pode ser visto na Figura 5.1. Quando um usuário
(u) requisita um arquivo, o sistema repassa essa informação para a heurística, juntamente
com uma lista de todas as máquinas virtuais disponíveis e lista de usuários que requisitaram o mesmo arquivo (U ). A heurística por sua vez calcula se deve alocar novos recursos
na nuvem, levando em conta os dados passados e as interrupções na execução do vídeo
observadas até o momento, e retorna com uma lista de servidores (S) e usuários que
podem compartilhar o arquivo (U ).
A arquitetura apresentada aqui e os métodos reativo e proativo resultaram em uma
publicação [22].
CAPÍTULO 5. MODELO
5.2
34
Heurísticas
As heurísticas aqui apresentadas têm 4 métodos principais. CriarServidores, CriarSuperpeers,
DesligarSevidores e AtualizarDados. Todos eles recebem como parâmetros o número
atual de interrupções do vídeo sendo considerado, quantidades correntes de servidores, clientes e superpeers e comparam com os valores da última observação. AtualizarDados é o
último método a ser chamado e atualiza os dados antigos com os novos. CriarServidores
e CriarSuperpeers podem ser chamados em paralelo, porém caso seja decidido criar novos
servidores, DesligarSevidores não é chamado.
As heurísticas são utilizadas de acordo com o algoritmo 1, onde um dos quatro principais métodos são chamados na linha 7, enquanto que na linha 6 é feita uma contabilização
do número de interrupções observadas até o momento, juntamente com a quantidade de
usuários ativos no sistema.
Algorithm 1 Algoritmo de provisionamento de servidores na nuvem
1: para todo Mi
vídeos faça
2:
enquanto usuários assistindo Mi > 0 faça
3:
para todo TMi
torrent do filme Mi faça
4:
Inicia contador t e espera até t = x
5:
Contabiliza número de usuários e interrupções
6:
Chama heurística passando o estado atual do sistema
7:
Modifica a quantidade de máquinas virtuais e superpeers de acordo com a
saída da heurística
8:
Heurística salva o estado atual do sistema. (AtualizarDados)
9:
fim para todo
10:
fim enquanto
11: fim para todo
As heurísticas são dividias em três grupos: as proativas, que visam alocar máquinas
quando o número de usuários é alterado; as reativas, que reagem a interrupções na exibição do vídeo; e os métodos ingênuos, criados para compreender melhor o resultado das
heurísticas nas simulações. As duas categorias de heurísticas (proativas e reativas) alteram lentamente a alocação de servidores e o número de superpeers, seguindo a ideia de
heurísticas como water-leveling [21], que evita mudanças drásticas a fim de evitar alterações bruscas que resulte em super ou subprovisionamento. As duas categorias fazem isso
aumentando no máximo em 50% os recursos disponíveis, como detalhado nas subseções a
seguir.
5.2.1
Heurísticas Proativas
As heurísticas proativas agem sem que uma interrupção necessariamente tenha ocorrido.
Para isso, tentam antecipar a ocorrência de interrupções reagindo à entrada e saída de
usuários.
Esta estratégia só aluga servidores quando o número de usuários torna-se maior que o
número de servidores por uma porcentagem de y%. Quando isso ocorre, novos servidores
são alugados de acordo com a equação 5.3.
CAPÍTULO 5. MODELO
35
S = So + N S ⇥ k
(5.3)
Onde S representa o novo número de servidores, So é o número de servidores atual, N S é
o número de novos usuários assistindo o vídeo desde o último relatório de monitoramento
e k é um parâmetro da heurística. Nesta implementação, N S é um valor incrementado
pelo Monitor toda vez que um usuário entra no sistema.
A variável y mantem a proporcionalidade de servidores por usuários controlada, evitando um aumento constante e desproporcional na quantidade de servidores. Pode-se
dizer que essas heurísticas mantém y% do número de usuários em servidores.
Nas heurísticas proativas, quando o número de usuários aumenta, o número de superpeers é redefinido pela equação 5.4, onde Po é o número atual de superpeers e b é um
parâmetro variado nos subtipos das heurísticas proativas, discutidos no fim desta seção.
P = Po + S ⇥ b
(5.4)
A expressão S ⇥ b representa a quantidade de superpeers a serem criados em relação
ao número de servidores. Por exemplo, dado b = 0.1, se no momento de ingresso de novos
usuários no sistema, há 100 servidores ativos (S = 100), serão alocados 10 novos superpeers. Dessa forma o sistema tenta manter uma certa proporcionalidade entre superpeers
e servidores.
Para desligar servidores, as estratégias proativas tomam decisões sob duas circunstâncias: i) o número de usuários caiu ou ii) o número de usuários está estável. Na primeira
situação, a decisão de desligar servidores é tomada baseada na equação 5.5.
S = So
(LS ⇥ h + P ⇥ r)
(5.5)
onde h e r são parâmetros da heurística e podem variar de 0 a 1, LS é o número de
peers que deixaram o sistema desde o último monitoramento e P é o número atual de
superpeers. Assim LS ⇤ h representa a porcentagem de usuários que deixaram o sistema:
se h = 0.5 e LS = 100, 50 servidores seriam desligados por essa expressão. Por outro lado,
P ⇤ r aumenta a quantidade de servidores desligados a cada aumento de superpeers no
sistema. Dessa forma as heurísticas tentam balancear o número de servidores baseado na
taxa de saída dos usuários e no aumento da rede P2P, já que os dois fatores potencialmente
aliviam a carga de requisições recebidas pelos servidores.
No caso de um congelamento na quantidade de usuários, a decisão de desligar os
servidores é feita pela equação 5.6.
S = So
P ⇤z
(5.6)
onde z é um parâmetro da heurística (variando entre 0 e 1) e P é o número atual de
superpeers, fazendo com que em caso de estabilização da entrada de usuários, o número
de servidores seja desligado somente considerando uma porcentagem do número de superpeers.
Foram criadas quatro variações da heurística proativa, através de valores nos parâmetros k, b, z. A nomenclatura dessas estratégias segue a variável y (i.e, quando o número
CAPÍTULO 5. MODELO
36
de usuários supera os servidores alugados por y%):
• Proativa 10: y = 10%,k = 0.1, h = 0.03, r = 0.01, z = 0.01 e b = 0.03.
• Proativa 20: y = 20%, k = 0.2, h = 0.03, r = 0.01, z = 0.01 e b = 0.01.
As heurísticas Proativa 10, 20 e 30 mantêm uma proporcionalidade nos parâmetros y,
k, enquanto que a Proativa 50 é uma cópia da Proativa 30, alterando somente k. h e r
são mantidos como valores baixos para evitar que em um momento a heurística decida
alugar mais servidores e no momento seguinte desalocar um número maior de servidores,
podendo jamais sair desse ciclo. A Proativa 10 é a única a alterar o valor de b, e por
conta disso acaba se apoiando de uma maneira maior nos superpeers. Com o parâmetro
z maior que as demais, a Proativa 30 e 50 acabam desligando mais servidores quando
usuários param de entrar no sistema e já existe uma quantidade maior de superpeers.
5.2.2
Heurísticas Reativas
As heurísticas reativas reagem a interrupções sofridas pelos usuários, atuando na criação/liberação de recursos conforme o informe dos usuários. Essas heurísticas aumentam o
número de servidores considerando duas variáveis: o número de interrupções e o número
de peers. Se o número de interrupções aumenta, a heurística reativa aumenta o número
de superpeers utilizando a equação 5.7
Pnew = Po + S ⇥ b
(5.7)
onde Po representa o número de superpeers obtido pelo monitoramento do sistema na
última janela temporal e b é um parâmetro da heurística. Da mesma forma que as
heurísticas proativas, as heurísticas reativas tentam aumentar o número de superpeers
proporcionalmente ao número de servidores (expressão S ⇤ b). Na alocação de servidores,
a heurística utiliza o número de usuários que entraram no sistema e uma certa porcentagem
dos servidores já alocados (So ⇥ r)
Se o número de interrupções se mantém o mesmo, os servidores são desligados e a
nova quantidade de servidores (Snew ) é determinada utilizando a Equação 5.8.
Snew = So
(So ⇥ h + U ⇥ r)
(5.8)
onde U é o número atual de peers (usuários assistindo o filme), enquanto h e r são
parâmetros da heurística.
Toda vez que o número de interrupções não é alterado, as equações 5.8 e 5.7 são
utilizadas para aumentar o número de superpeers e desligar servidores.
Definimos um limiar V para o aumento do número de interrupções. Caso o número
de interrupções supere V , o novo número de servidores será definido de acordo com a
equação 5.9.
CAPÍTULO 5. MODELO
37
Snew = So + So ⇤ c
(5.9)
onde c é um parâmetro da heurística, que varia de 0 a 1, e So é o número atual de
servidores O número atual de superpeers (P ) é mantindo intacto.
Definimos um segundo limiar y, que estabelece uma porcentagem máxima em que a
quantidade de peers pode superar a quantidade de servidores. Caso ambos os limiares y
e V sejam violados no sistema, o número de servidores é modificado utilizando a equação
5.10.
Snew = So
U ⇥ U + So ⇥ r
(5.10)
onde U é a diferença entre o número atual de usuários e o número de usuários coletados
na última janela temporal e r é um parâmetro do sistema. Nesse caso, a heurística utiliza
tanto o número de usuários que entraram no sistema quanto uma certa porcentagem dos
servidores já alocados (So ⇥ r).
Foram testados diferentes parâmetros associados com a heurística reativa. As heurísticas reativas são nomeadas de acordo com a variável b. Estas heurísticas reorganizam os
servidores e superpeers de acordo com:
• Reativa 0.05: As variáveis de controle são configuradas para b = 0.05, c = 0.01,
h = 0.01, r = 0.02. Adicionalmente, quando o número de servidores aumenta,
V é dobrado, para reduzir a chances de alugar novos servidores em caso de novas
interrupções na próxima janela. O número de superpeers é limitado a 5% do número
de peers, mas seeders são ilimitados.
• Reativa 0.01: As variáveis tem o valor b = 0.01, c = 0.01, h = 0.01, r = 0.01. V
tem valor 10. Superpeers são limitados a 5% dos peers.
• Reativa 0.02: As variáveis tem o valor: b = 0.02, c = 0.01, h = 0.01, r = 0.01.
Assim como a Reativa 0.01, está heurística mantem o valor constante de V em 10,
porém o número de superpeers é aumentado para 50% de todos os peers.
5.2.3
Métodos ingênuos
Para comparar as heurísticas aqui analisadas, foram implementadas duas estratégias ingênuas. A primeira mantém um número constante de servidores (10 servidores) durante
todo o experimento. A segunda aluga um servidor para cada novo usuário no sistema. Os
dois métodos tornam um usuário um superpeer somente quando ele termina de receber
todo o arquivo.
Capítulo 6
Simulações
Os cenários utilizados na simulação utilizam somente um tracker e um provedor de nuvem. O custo de se alugar um servidor e transferir conteúdo foram baseados no provedor
Amazon.
Sistemas P2P apresentam duas importantes características (i) escalabilidade e (ii) dinamismo. Para as simulações foi escolhida a utilização do Peersim – um ambiente escalável de simulação que permite a definição de diferentes cenários. No Peersim, é possível
implementar o protocolo de comunicação entre os nós da rede, utilizando uma API prédefinida e até mesmo podendo ser alocada em uma implementação real. Além disso, ele
provê uma série de módulos pré-desenvolvidos que podem ser combinados de diferentes
maneiras, provendo flexibilidade na configuração e utilização de diversos cenários. A rede
P2P é modelada como uma coleção de nós, onde cada nó é associado a uma série de
protocolos. A simulação é regulada por inicializadores e controladores que permitem que
eventos possam ser introduzidos na simulação ou ativados em diferentes pontos temporais pré-definidos. Foi utilizada como base das simulações a ferramenta arenbm 1 (que
utiliza o Peersim [28]). Este trabalho assume nas simulações que as máquinas são ligadas
e preparadas para responder as requisições no momento em que são alugadas. Durante
a simulação, j usuários entram no sistema, enquanto que g usuários o deixam a cada x
unidades de tempo, seguindo a distribuição de Pareto(f (x; 1.5, 1000000000)). Usuários
param de entrar no sistema após um certo número de usuários acessarem o sistema. Os
superpeers que irão responder a requisições de um certo usuário são escolhidos aleatoriamente.
A banda de entrada dos usuários é fixa em 8Mbps. Este número foi escolhido por
ser a velocidade mais comum nos EUA de acordo com experimentos práticos 2 . Outros
parâmetros do sistema são: (i) a banda de saída necessária para cumprir a qualidade de
experiência do usuário (i.e. qualidade do filme); (ii) tamanho dos pedaços transferidos;
(iii) tamanho total do arquivo do filme transferido.
As simulações começam com 10 servidores, sendo alugados de acordo com as heurísticas
apresentadas na sessão anterior. Foi analisado como as interrupções afetam os usuários
durante as simulações. Primeiramente foi testado como as heurísticas se comportavam
com diferentes valores para seus parâmetros ( k, b, c, h, r, z para as proativas e k,
1
2
github.com/guthemberg/arenbm
http://www.speedtest.net/awards/us
38
CAPÍTULO 6. SIMULAÇÕES
39
b, c, h, r para as reativas). As que obtiveram melhores resultados foram analisadas
mais profundamente com diferentes cenários. Todas as simulações utilizam os valores
Rprice = 0.052 e Cprice = 0.090, baseados na Amazon AWS. Baseado no resultado das
simulações, foi criada uma heurística híbrida, utilizando-se dos melhores comportamentos
das duas categorias.
6.1
Cenários
Foram realizados 5 simulações com diferentes parâmetros para as heurísticas. Estes cenários são separados em três categorias:
I cenário básico com todas as heurísticas propostas;
II duas simulações com as melhores heurísticas da categoria I, o primeiro utilizando
2000 usuários ativos no sistema e o segundo aumentando a taxa de saída dos usuários
para 8Mbps (por consequência fazendo com que os superpeers se comportem da
mesma forma que os servidores), mas reduzindo o número de usuários para 1000
novamente;
III cenários com a heurística híbrida que foi criada baseada no melhor comportamento
da heurísticas proativa e reativa. A primeira simulação utilizando 2000 usuários e a
segunda com um cenário parecido ao utilizado em [34], a fim de comprar os resultados
obtidos.
Os resultados estão descritos nas subseções a seguir.
6.1.1
Cenário básico
Nesta simulação, o arquivo de filme foi dividido em 1400 pedaços de 512 KB cada. O
vídeo é um filme em alta-definição (1280X720) com uma taxa de 2400 kbps. Cada usuário
tem 250 Kbps de banda de saída e 8 Mbps de banda de entrada. Cada ponto nos gráficos são “snapshots” de diferentes métricas em pontos temporais diferentes na simulação.
Assim, os gráficos demonstram as evoluções tanto da métrica, quanto do tempo durante
as simulações.
Os gráficos apresentam os resultados para diferentes algoritmos de alocação e as estratégias ingênuas. Os rótulos Proativa 10, Proativa 20, Proativa 30, Proativa 50 representam as heurísticas proativas com o parâmetro y igual a 10, 20, 30 e 50, respectivamente.
De forma similar, os rótulos Reativa 0.01, Reativa 0.02, and Reativa 0.03 representam as
heurísticas reativas com o parâmetro b igual a 0.01, 0.02 e 0.03, respectivamente.
A Figura 6.1a mostra que o número de usuários cresce em contraste com o número
de servidores durante a simulação. A heurística reativa tende a aumentar o número
de servidores constantemente, se comparada à proativa, exceto pela Reativa 0.01 cujos
parâmetros forçam o aluguel de servidores no final da simulação. A Proativa 50 é a
heurística com o menor número de servidores alugados no final da simulação.
Apesar das heurísticas reativas alugarem mais servidores durante a simulação, em
geral, elas não foram capazes de reduzir o número de interrupções, como mostrado em 6.1b.
40
O custo total destas heurísticas foram maiores que as proativas, dado ao grande número
de máquinas virtuais utilizadas, mas ao mesmo tempo, obtiveram números parecidos de
interrupções. Comparando somente as heurísticas reativas, Reativa 0.05 teve o melhor
comportamento, sendo capaz de reduzir o número de interrupções, enquanto mantém um
custo aceitável.
6.1.2
Melhores heurísticas
Em geral, as simulações iniciais sugeriram que as estratégias proativas propostas (alugar
novas máquinas antes que ocorram interrupções) geram menores custos. Para se aprofundar na análise do comportamento das heurísticas, foram escolhidas as que obtiveram
melhores resultados (Proativa 50, 20 e 10 e Reativa 0.05) para serem simuladas em um
ambiente com requisitos de 5000 kbps de QoE. Como os usuários compartilham dados
entre eles mesmos, no primeiro teste aumentamos o número de usuários para 2000 para
ver como o custo se comportaria com o aumento de usuários. A Figura 6.2 apresenta os
resultados para este novo cenário.
A Reativa 0.05 teve o maior custo (Figura 6.2b), porém resultou em um número
menor de interrupções. Por outro lado, a Proativa 10 manteve baixo o custo e o número
de interrupções, resultando em um comportamento melhor que a Reativa 0.05. A Proativa
50 também manteve custos baixos, mas um número maior de interrupções. Importante
notar que o custo não dobrou se comparado ao experimento anterior, o que seria de se
esperar em um sistema Cloud-CDN caso não houvesse o auxílio de uma rede P2P.
Um resultado interessante é que o número de servidores com 1000 usuários e 2000
usuários, mesmo com uma necessidade maior de banda de saída, é similar. Pelos resultados, o aumento de número de superpeers, parece implicar em um número menor de
interrupções. Importante notar também, que a Reativa 0.05 tem um número maior de
servidores durante quase toda a simulação (Figura 6.2a), o que ajuda a evitar interrupções. De fato, a heurística Proativa 50, alugando mais servidores a cada lote, teve um
pico de 111 servidores ligados por volta de 3.5 horas após o início da simulação, reduzindo
após isso para 89 servidores e finalizando a simulação com 93. Por outro lado que a Proativa 10 (que aluga menos servidores a cada lote), obteve 154 servidores ligados em 3.3
horas após o início, reduzindo a 130 no último momento da simulação em 5.4 horas. Já
a Reativa obteve no máximo 364 servidores alugados simultaneamente (por volta de 1.3
horas), reduzindo para 346 no momento final da simulação (após 3.8 horas do início da
simulação). Resultados para esse cenário são mostrados na Figura 6.3.
Um terceiro cenário foi simulado, para entender melhor o comportamento das heurísticas frente a um aumento da banda de saída dos usuários. Esse cenário utilizou 1000
usuários e banda de saída de 8 MBps. Dessa forma, tanto o usuário como a nuvem mantém
a mesma taxa.
Com esta mudança, o custo das estratégias proativas foram reduzidas se comparadas
com a Figura 6.1. Como os usuários ajudam de maneira mais efetiva (praticamente
como se fossem um servidor da nuvem), o sistema pode responder de maneira gratuita às
requisições de maneira mais rápida, reduzindo o custo associado com a transferência de
dados da nuvem. Considerando que os usuários também terminam a transferência antes
(a) Usuários versus servidores.
(b) Interrupções versus custo.
Figura 6.1: Resultados das simulações.
41
Figura 6.2: Simulação com 2 mil usuários.
42
43
conforme observado na Figura 6.3, é possível reduzir o custo associado com o aluguel de
servidores.
6.2
Heurística Híbrida
Na maioria dos cenários a estratégia proativa se comportou melhor que a reativa. Por
outro lado, a heurística Reativa 0.05 manteve um número baixo de interrupções durante
parte das simulações. Assim, juntando os pontos fortes das duas estratégias, simulamos
alguns cenários com uma heurística Híbrida. Esta terceira categoria de estratégia aluga
máquinas nos provedores de nuvem toda vez que um usuário acessa o sistema, seguindo
os parâmetros da heurística Proativa 50 e aumenta o número de superpeers seguindo uma
mescla entre a Proativa 50 e a Reativa 0.05. Esta mescla se dá utilizando o Algoritmo
2, aumentando o número de superpeers tanto na entrada de novos usuários quanto no
aumento do número de interrupções.
Algorithm 2 Algoritmo utilizado na heurística híbrida para aumentar o número de superpeers
1: V = 10
2: se o número de interrupções atuais somado a V é maior que o número de interrupções
anterior e o número de superpeers é menor que 5% do número de usuários no sistema
então
3:
V =V ⇤2
4:
Aumenta o número de superpeers com 20% do número de servidores atuais
5: senão
6:
se Número de usuários aumentou então
7:
Aumenta o número de superpeers com 10% do número de servidores atuais
8:
fim se
9: fim se
Já para liberar instâncias previamente alugadas, a heurística híbrida utiliza o algoritmo
3. Esse algoritmo também é uma mistura entre as heurísticas Proativa 50 e a Reativa
0.05, dando preferência ao comportamento da heurística proativa.
Algorithm 3 Algoritmo utilizado na heurística híbrida para diminuir o número de servidores
1: se o número de usuários aumentou e 10% do número de usuários é menor que o número
de servidores então
2:
Diminui o número de servidores utilizando a fórmula 5.5 (com os valores da Proativa 50)
3: senão
4:
se o número de interrupções atuais somado a V é maior que o número de interrupções anterior então
5:
Diminui o número de servidores utilizando a fórmula 5.8
6:
fim se
7: fim se
Figura 6.3: Simulação com número maior de banda de saída dos usuários.
44
45
O número de superpeers é baseado primeiramente na heurística reativa e somente se
não houver interrupções é utilizada a equação da heurística proativa (levando em consideração o número de usuários entrando no sistema). Já para diminuir o número de
servidores a heurística híbrida faz o contrário: primeiramente verifica se o número de
usuários aumentou e como segunda regra utiliza as interrupções. A ordem das regras se
dá pelo fato de que caso haja um número grande de interrupções acontecendo, aumentar o
número de fontes disponíveis pode ajudar a estabilizar o sistema. Por outro lado, desligar
servidores quando novos usuários começam a acessar o sistema pode causar uma queda
na qualidade de experiência dos usuários.
6.2.1
Simulação com 2000 usuários
A avaliação da heurística híbrida foi feita utilizando o mesmo cenário da seção 6.1.2. O
cenário emula cerca 2000 usuários ativos no sistema, com 5000 kbps de QoE com usuários
compartilhando o arquivo (com 1400 pedaços de 512KB) com uma banda de saída de 250
Kbps (mesmos parâmetros do cenário básico inicial).
A Figura 6.4 apresenta os resultados da heurística híbrida neste cenário. Não só esta
heurística consegue ser um pouco mais barata que a Proativa 50, mas mantém um número
menor de interrupções ao final da simulação (Figura 6.4a). Outra importante métrica é o
tempo necessário para o fim da simulação (onde todos os usuários têm todo o arquivo em
seus sistemas de armazenamento). A heurística Híbrida leva mais tempo que a Reativa
0.05, mas menos tempo que a Proativa 50 (Figura 6.4b).
A diferença de tempo entre as heurísticas Híbrida e Proativa 50 é de 54.6 minutos,
enquanto que o custo é somente de 3.66 unidades monetárias. Portanto, apesar de parecer
que a Híbrida é só um pouco melhor que a Proativa 50 (considerando a quantidade de
interrupções/custo), na realidade os resultados diferem também no custo e na duração da
simulação. Por um valor mais baixo, é possível entregar todo o arquivo aos usuários uma
hora mais rápido. A estratégia ingênua de utilizar um servidor por usuário também teve
uma diferença pequena na quantidade de horas gasta para entregar todo o arquivo que a
heurística Híbrida, porém teve um custo final de 255.52 contra 36.32 da Híbrida.
6.2.2
Simulação com vídeos de 12800 Kbps de SLA
Utilizando um cenário parecido ao simulado em [34], com 12800 Kbps necessários para
suprir um segundo de vídeo, com cada chunk com 512KB e banda de saída para os usuários
de 1Mbps e de entrada 8Mbps com 5 mil usuários no sistema, a heurística híbrida mostrou
resultados semelhantes. Enquanto que [34] consegue manter um SLA de cerca de 98%
de chunks sendo entregues no prazo correto, a heurística híbrida alcança número similar
(98.4%), mantendo 10 servidores no final da simulação, enquanto que [34] utiliza no
máximo 4 servidores durante toda a simulação, finalizando ela com apenas 2. De fato,
estressando mais o cenário e diminuindo pela metade o tamanho do arquivo (fazendo com
que mais nós possam colaborar como superpeer), o número de servidores reduz para 5
ao final. Com um arquivo três vezes maior que o arquivo simulado em [34], o número de
servidores ao final da simulação é 14 (Figura 6.5).
(a) Interrupções versus Custo
(b) Horas para terminar a simulação.
Figura 6.4: Simulação com a estratégia Híbrida com 2000 usuários.
46
47
(a) Interrupções versus Custo
Figura 6.5: Simulação com cenário similar ao de [34], utilizando a heurística Híbrida com
arquivos de diferente tamanhos.
Capítulo 7
Discussão
Nesta seção são discutidas as possibilidades para se implementar um sistema VoD real
utilizando as heurísticas propostas. A discussão leva em consideração diversas estratégias
disponíveis na literatura, dada a extensão de pequenos fatores que podem contribuir
ou denegrir a qualidade do sistema, como políticas de requisições de pedaços do filme,
alocação de máquinas propriamente dita, provedor de nuvem e serviços disponíveis e
gerenciamento dos usuários. Considerando a diversividade de cada ponto, a discussão
visa justificar as escolhas feitas e ao mesmo tempo mostrar outras opções e discutir os
fatores positivos e negativos de cada uma.
7.1
Heurísticas e estratégias auxiliares
Nesta subseção são discutidos os resultados das heurísticas juntamente com estratégias
auxiliares disponíveis na literatura que poderiam melhorar o resultado final.
7.1.1
Estratégias auxiliares
A estratégia híbrida combina aspectos da proativa e reativa. Alugar máquinas de forma
proativa quando o usuário entra no sistema se demonstrou mais eficiente que aguardar
interrupções acontecerem para reduzir o número de interrupções e manter um baixo custo
de aluguéis de máquinas virtuais que alugar sempre que há uma interrupção o que torna
o sistema instável.
Este comportamento de alugar máquinas antes de uma perda de qualidade (e aumento
de interrupções) é similar ao aplicado pelo Netflix [7]. Tentar prever o aumento de usuários
e alugar servidores antes que os usuários acessem o serviço poderia resultar em um menor
número de interrupções, porém num maior custo final.
Além de alugar máquinas previamente a uma perda de qualidade (ou ainda do aumento
de usuários), é possível também “alimentar” a rede P2P com os arquivos em momentos de
inatividade. Em [16] é estudado um sistema de IPTV sobre uma rede P2P e é utilizada a
estratégia de “prefetching” (alimentar a rede P2P com os arquivos de vídeo antes mesmo
que eles requisitem, para que quando um usuário requisite o vídeo, a rede P2P seja capaz
de o prover por completo desde o momento da requisição), chamada Zebra. De maneira
geral o algoritmo escolhe os vídeos mais populares e o divide em segmentos na rede P2P
48
CAPÍTULO 7. DISCUSSÃO
49
uniformemente. O artigo mostrou resultados positivos quando ao uso dessa estratégia. De
forma intuitiva, quanto antes os nós obtiverem todo o arquivo, mais rápido são capazes
de o prover para seus vizinhos. Essa estratégia poderia ser utilizada em conjunto com
as heurísticas, onde os nós que recebessem os segmentos poderiam agir como superpeers
mais rapidamente.
7.1.2
Resultados das simulações
A heurística reativa tende a alugar mais servidores, mesmo as interrupções sendo causadas
pela falta de banda de entrada dos usuários e não de saída dos servidores. Isto fica claro
ao ver os resultados da estratégia que aluga um servidor por usuário. Mesmo esta obteve
resultados similares às heurísticas.
No artigo [34] é observado que o aumento na taxa de upload do sistema como um
todo resulta em uma melhor qualidade de serviço, onde o cenário somente com entrada
de usuários obtém melhores taxas de playback do que o cenário onde usuários deixam o
sistema constantemente. Isto é reforçado no cenário aqui apresentado onde à banda de
saída dos usuários é similar à da nuvem. Na possibilidade de uma maior estabilidade
por parte dos usuários, alocar menos máquinas e distribuir uma maior quantidade de
responsabilidade na transmissão de dados na rede P2P pode trazer bons resultados.
As heurísticas proativas e reativas terminam a transmissão do arquivo para todos os
usuários em aproximadamente 5 horas, enquanto que a estratégia de manter um número
fixo de servidores leva cerca de 30 horas. Pode-se comparar o resultado dessa estratégia
com o prefetching. Dado que as heurísticas são capazes de alimentar a rede P2P rapidamente, os usuários são capazes de compartilhar o artigo com seus pares mais cedo,
aumentando o número de fonte para todos os segmentos do vídeo e aliviando a carga de
requisições para os servidores da nuvem.
7.1.3
Superpeers
Ao aumentar o número de superpeers, o sistema também se torna de certa forma mais
instável. Tanto por depender de velocidades menores para servir os dados, como pela
instabilidade dos nós da rede P2P. Não há garantias que os superpeers permaneçam no
sistema até o final da transmissão. Uma possível solução é oferecer incentivos financeiros, como em [36, 15], para que os usuários ao serem escolhidos para serem superpeers
permaneçam no sistema.
O incentivo oferecido em [36] é focado principalmente em combater o compartilhamento ilegal dos vídeos. O modelo se baseia no fato de que a demanda por um conteúdo é
transiente e todo conteúdo eventualmente estará disponível de forma gratuita em redes de
compartilhamento ilegal. O incentivo tenta compartilhar o lucro do sistema com os “early
adopters” (os primeiros usuários a testar o sistema), dividindo o lucro em porcentagens
de acordo com o compartilhamento (seeder) dos usuários. Desta forma, os superpeers não
seriam mais considerados “uma fonte gratuita de compartilhamento”, como foi feito em
nossas simulações, mas poderiam agir de forma mais confiável.
7.2
50
Possíveis implementações
Apesar das simulações serem próximas de um ambiente real, pequenos detalhes são omitidos. É necessário, ao implementar as heurísticas aqui descritas, ajustar detalhes na
arquitetura, principalmente em relação ao funcionamento da alocação de máquinas. Nas
subsessões a seguir são discutidos possíveis métodos de implementação.
Na implementação discutida não são considerados vídeos ao vivo, somente a empresa
pode disponibilizar vídeos no sistema e não são consideradas estratégias para criptografar
ou manter o vídeo seguro.
7.2.1
Provedor IaaS
Entre os diversos provedores disponíveis, as discussões sobre a implementação do sistema
focará no provedor de nuvem Amazon AWS. A AWS disponibiliza diversos serviços na
nuvem, inclusive infraestrutura. Este serviço é nomeado EC2 1 . Uma das características
deste sistema é a possibilidade de criar imagens do sistema operacional do usuário (AMI,
Amazon Machine Image) e utilizá-la por padrão quando o usuário requisita uma nova
máquina. No caso de um sistema de VoD, nesta imagem podem ser inseridos tanto os
programas necessários para o sistema funcionar, como os vídeos disponíveis. Outra opção
seria alocar uma máquina e instalar todos os programas necessários, o que poderia elevar
o tempo necessário para ter a máquina disponível para o sistema. Indiferente da opção
escolhida, não existem SLA do tempo necessário para a instância ser disponível 2 .
Um ponto não abordado nas simulações, por ter um custo constante, é o local de
armazenamento da mídia que será reproduzida pelos usuários. O provedor AWS oferece
um serviço chamado de S3 3 , onde é possível armazenar arquivos. Este serviço é cobrado
tanto pelo tamanho dos arquivos armazenados, como pela quantidade de requisições de
dados. Os servidores poderiam iniciar sem nenhum dado em seu disco de armazenamento
e fazer requisições para o S3 toda vez que o usuário pedisse um arquivo que não está
no disco (como uma espécie de page-fault). Desta forma seria possível reduzir o custo
do envio de dados do S3, caso alguns filmes não sejam requisitados para um grupo de
máquinas.
Poderia ser utilizada também uma máquina do EC2 para armazenar estes filmes,
fazendo a mesma função do S3, com a diferença que transferência de dados dentro da
própria rede do EC2 (máquina para máquina) é gratuita. Porém, o armazenamento de
dados seria limitado ao tamanho de disco da instância, o que poderia ser resolvido com
um grupo de máquinas dedicadas a isto, gerando um custo maior dado a diferença de
preço entre o serviço S3 e o aluguel de máquinas.
Por fim, pode-se criar uma AMI com todos os vídeos disponíveis, eliminando a necessidade de utilizar uma fonte central para alimentar as máquinas. Para isto é necessário
utilizar o serviço EBS (Elastic Block Store 4 ), que indiretamente utiliza o S3 como dispositivo de armazenamento a ser utilizado pela máquina virtual. As desvantagens desta
1
https://aws.amazon.com/ec2/pricing/
https://aws.amazon.com/ec2/sla/
3
https://aws.amazon.com/s3/pricing/
4
http://aws.amazon.com/ebs/pricing/
2
51
opção incluem o custo para o armazenamento da AMI e o custo do espaço utilizado por
cada máquina (dado que todas as máquinas terão todos os vídeos, incluindo aqueles pouco
requisitados).
A estratégia de manter uma AMI é mais eficiente em relação a manter as máquinas virtuais sincronizadas com a mesma versão e facilita a manutenção, por isso seria a
estratégia utilizada.
7.2.2
Alocação de máquinas
É possível utilizar as heurísticas propostas neste trabalho para a tomada de decisão quanto
ao número de instâncias a serem alugadas do EC2.
A heurística funcionaria da mesma forma que nas simulações com peersim. A diferença é que o número de servidores a serem alocados/desalocados seria repassado para
o SDK da Amazon. Como a heurística utiliza a diferença entre os usuários entre dois
momentos de monitoramento, tanto o monitoramento como a decisão da heurística deverão ser executados de 15 em 15 minutos. Esse número influencia diretamente o custo e
qualidade do serviço ofertado e precisa ser otimizado de acordo com o sistema (média de
entrada de usuários por minuto) e levar em consideração a média de tempo para alocar
uma máquina da AWS.
Ao iniciar novas máquinas também é necessário decidir se será preciso avisar aos usuários sobre a existência desses servidores: para que eles possam fazer requisições a novas
máquinas, ou se estas máquinas ficarão esperando novos usuários entrarem no sistema
para efetivamente começarem a colaborar com o sistema. Nesta implementação, sempre
que novas máquinas fossem alocadas, o Tracker avisaria aos usuários para requisitarem
novamente os IPs das máquinas que estão disponíveis.
Outro ponto a ser levado em consideração é que a cobrança pelo aluguel das máquinas
na Amazon é feita por hora. Caso uma máquina seja alocada e desligada após somente 15
minutos, será cobrado uma hora inteira. Uma maneira de evitar a cobrança da máquina
por momentos que ela não foi utilizada é: desligar máquinas que estão há mais tempo no
sistema (i.e. maquinas ligadas há 50 minutos ao invés de 2 minutos). Outra estratégia é
marcar a máquina como "desligada", mas só efetivar o desligamento no minuto 59, e caso
essa máquina venha a ser necessária, seu desligamento pode ser cancelado.
7.2.3
Requisitando o arquivo
Os usuários recebem uma lista com todos os servidores disponíveis e com todos os usuários. Em seguida, requisitam para cada um deles o chunk necessário usando uma política
de Round-Robin para balancear as requisições. Este funcionamento é parecido com o
protocolo BitTorrent, onde os peers são os responsáveis por requisitar o chunk de seus
pares (também conhecido como mesh-pull [20]). Como os outros peers podem não ter
todo o arquivo em seu disco, o usuário envia junto com a requisição um vetor de mesmo
tamanho dos chunks do arquivo, notificando se já o tem em seu disco ou não. Como esta
informação muda constantemente, é necessário que a cada requisição o usuário reenvie este
vetor. Isto é necessário pois os peers enviam os dados em ordem cronologicamente inversa.
52
Figura 7.1: Exemplo da escolha do segmento de vídeo a ser enviado pelo usuário (a) ao
usuário (b).
Por exemplo, dado um usuário (b) que requisita um segmento de vídeo para (a) – Figura
7.1 –, (b) necessita saber todos os chunks já recebidos por (a) para enviar o primeiro
segmento que difere. Em outras palavras, dado dois conjuntos Sa = {1, 2, 4, 5, 7, 8, 9, 10}
e Sb = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, representando os chunks recebidos por (a) e (b), respectivamente, o segmento a ser enviado é definido pelo maior número de Sa Sb (nesse caso
6).
Para requisitar chunks aos servidores e superpeers, o cliente envia somente o identificador do chunk necessário.
Uma alternativa a esse sistema seria o usuário se conectar com os servidores e peers,
e estes enviarem os chunks conforme acharem melhor. Este esquema é conhecido como
tree-push P2P [20, 23] (Figura 7.2). Nesses sistemas, os peers são estruturados como
uma árvore, onde cada nó pai é responsável por enviar os chunks aos seus nós filhos
automaticamente [23]. O ponto fraco desta organização é o tempo para se refazer a
árvore quando nós deixam o sistema [23]. Em sistemas com usuários estáveis, é possível
utilizar esta estrutura para otimizar o envio de segmentos de vídeo, porém em sistemas
como o simulado neste trabalho onde os usuários debandam constantemente, o tempo
para refazer a árvore acaba prejudicando o desempenho do sistema.
Há estudos sobre arquiteturas híbridas de push-pull, unificando as vantagens dos dois
sistemas, mas mesmo estas contém problemas, como por exemplo colisão de chunks (um
nó receber múltiplas vezes o mesmo chunk) [23].
Outro ponto a ser discutido para a implementação é a escolha do chunk a ser enviado
na rede P2P. Em nossas simulações utilizamos a ordem cronológica inversa para o envio
de chunks na rede P2P. Outras opções seriam “aleatória”, “cronológica” e por raridade
na rede [30]. A escolha por raridade é comum no protocolo bitTorrent, pois aumenta
a diversidade de chunks na rede. Por isso seguir a ordem cronológica pode reduzir a
diversidade temporal e espacial dos pedaços do arquivo [30].
53
Figura 7.2: Exemplo de rede overlay utilizando tree-push P2P.
Em [30] são estudadas as diversas escolhas quanto a requisição de chunks no sistema
e a com maior desempenho (progresso do stream) no modelo apresentado é a “In-order”
(ordem cronológica). Porém, o fator “in-order” faz com que usuários antigos do sistema
recebam mais requisições que os novos, por possuírem uma maior quantidade de chunks
a serem requisitados. Como resultado, esses usuários mais novos podem consumir toda a
banda de saída dos usuários antigos em sistemas puramente P2P, atrapalhando o progresso
dos usuários de idade média que dependem diretamente desses usuários. Analisando o
sistema “in-order”, o artigo [30] verificou que o progresso do stream está relacionado com
a idade do usuário. Usuários mais novos tem mais opções de peers para requisitarem o
conteúdo, enquanto que estas opções diminuem conforme o usuário permanece no sistema.
Em [30] o progresso do stream é definido como o produto do progresso de download
(a taxa que os chunks são obtidos com sucesso da rede P2P) e do progresso sequencial
(a “utilidade” dos pedaços adquiridos para o stream) [30]. O progresso do download é
principalmente influenciado pela população de usuários, e taxas de banda de saída e
entrada do sistema, política de requisição de chunks e quantidade de chunks na mídia.
Enquanto que o progresso sequencial é influenciado principalmente pelos dois últimos
itens. Desta forma fica claro que mesmo utilizando a política de escolher os chunks baseado
na raridade para evitar a diminuição dos problemas relacionados a idade do usuário, o
progresso sequencial pode ser afetado, por exemplo se em sucessivas requisições o usuário
requisitar somente pedaços não necessários para os próximos segundos de reprodução.
Com a escolha das políticas de requisição de segmentos de vídeos utilizadas nas simulações, podemos afirmar que a rede P2P no sistema ajuda somente no progresso do download
e não no progresso sequencial (por causa da política de ordem cronológica inversa). Desta
forma, ela ajudaria na diminuição do custo de forma direta, mas no progresso sequencial
somente quando o usuário necessitasse daquele chunk, que dependendo do tamanho do
vídeo e da quantidade de tempo de exibição pode acontecer somente horas depois.
7.2.4
54
Saída e entrada de usuários no sistema
Usuários de redes P2P podem deixar o sistema mesmo antes de terminarem a reprodução
do conteúdo, fazendo com que o número de superpeers possa ser reduzido em momentos
inoportunos e sem aviso. Isso gera dois problemas: (i) manter a qualidade do sistema,
mesmo com uma alta debanda de superpeers e (ii) descobrir quando um superpeer deixou
o sistema.
Para lidar com a saída dos usuários sem notificação podem ser utilizados protocolos
que enviem mensagens a cada período de tempo para todos os usuários, perguntando se
eles estão ativos. Em caso de não haver respostas, o servidor pode excluir o IP daquele
usuário de seu banco de dados. O servidor pode então avisar todos os usuários para
não requisitarem mais dados daquele IP. Dada a alta quantidade de usuários, isso pode
gerar alguma sobrecarga no servidor. Uma segunda opção seria os próprios usuários ao
não receberem um número sequencial de respostas de um IP, o excluírem de sua lista e
requisitarem o servidor de fazer o mesmo. Dada a natureza assíncrona do sistema, pode
ser necessário utilizar algum protocolo de consenso. Nas simulações, o Tracker funciona
como um oráculo, sendo capaz de saber se um usuário deixou o sistema e renovar a
lista de todos os usuários automaticamente não contabilizando o tempo gasto com esta
sincronização.
Poderia ser utilizado por exemplo o protocolo heartbeat. Neste protocolo, o usuário
envia periodicamente um sinal ao Tracker para notificar que ainda está ativo no sistema,
caso o Tracker não receba a mensagem, ele colocaria o usuário na lista de inativos.
Quanto a manter a qualidade do sistema mesmo com a saída dos superpeers, é possível prever, dado o histórico dos usuários, quando haverá um número maior de superpeers
no sistema e quando eles se desconectarão como no sistema do Netflix. Nesse caso seria
necessário somente balancear o número de servidores de acordo com o resultado da predição. Outra opção (utilizada nas simulações) é balancear a quantidade de servidores toda
vez que os superpeers debandam o sistema (como as heurísticas fazem quando usuários
comuns deixam o sistema).
Capítulo 8
Conclusões
Utilizar a computação na nuvem em aplicações de transmissão de vídeo se tornou um
tópico de interesse recentemente. Este tipo de serviço envolve a alocação de recursos
dedicados a operações em tempo (semi-)real, requerendo novos tipos de estratégias para
alocar recursos. Por outro lado, protocolos P2P (centralizados em recursos pertencentes ao usuário) têm sido utilizados frequentemente nesta área para a redução de custos.
Foi descrito neste trabalho como redes P2P e a nuvem pública podem ser combinadas,
dinamicamente, para reduzir custos, enquanto mantêm o requerimento de QoS.
A união de protocolos P2P com modelos de cliente e servidor tem sido utilizada em
ambientes reais por diversas empresas, como o próprio governo brasileiro que anunciou
recentemente a criação de um sistema VoD estatal utilizando redes P2P e CDN. Essa
mescla entre P2P e Cloud para sistemas de vídeo sob demanda levanta dois tipos de
problema: a otimização da utilização dos recursos da nuvem e o controle de qualidade do
sistema.
Dois tipos de estratégia têm sido utilizadas para a criação deste tipo de sistema,
(i) onde a rede P2P atua como principal forma de transmissão e servidores na nuvem
são utilizados somente em casos extremos e (ii) onde a nuvem é o ator principal na
transmissão, utilizando os nós da rede P2P como auxiliares afim de reduzir o número de
servidores necessário.
O sistema aqui proposto utiliza a segunda categoria de sistema, utilizando inclusive
da nuvem para coordenar a rede P2P, mantendo os endereços IPs dos usuários em um
ponto centralizado, chamado de Tracker. Esta centralização facilita o controle da rede,
mas cria um único ponto de falha no sistema. Também é utilizada uma categoria especial
de usuários, nomeados “superpeers”. Estes usuários atuam como servidores, enviando os
dados em ordem “cronológica” para outros usuários, enquanto os demais nós da rede P2P
compartilham o arquivo de trás para frente.
Entre as diversas políticas de requisição de chunks existentes para os servidores, foi
utilizada a ordem cronológica (“in-order”) como política nas simulações. Esta política
facilita o progresso sequencial da reprodução, porém pode sobrecarregar os usuários antigos, enquanto atrapalha usuários que estão em um tempo médio no sistema. No caso das
simulações, este efeito não ocorre, dado que esta requisição é feita somente a servidores
da nuvem ou superpeers, que são capazes de suprir todos as categorias de usuários. A
política de requisição para os demais usuários do sistema é a ordem cronológica inversa,
55
CAPÍTULO 8. CONCLUSÕES
56
fazendo com que todos os usuários sejam capazes de colaborar com a transmissão sem
afetar diretamente a qualidade do sistema, dado que o progresso sequencial do sistema
não é afetado.
O serviço proposto depende das heurísticas para balancear o número de máquinas
necessárias para suprir os nós da rede P2P tentando escolher o número ideal de superpeers
para maximizar a vazão de dados, enquanto miniminiza o custo. Neste trabalho foram
propostas três categorias diferentes de heurísticas: (i) Proativa: que envolve a alocação
de máquinas da nuvem e aumento do número de superpeers quando usuários entram no
sistema; (ii) Reativa: onde alocação ocorre somente quando interrupções na transmissão
acontecem; (iii) Híbrida: que combina ambas as estratégias.
A estratégia (i) é de certa forma parecida com a estratégia utilizada pelo Netflix, pois
visa reagir a possíveis problemas na qualidade de serviço antes delas acontecerem. Por outro lado o Netflix se baseia no comportamento prévio dos usuários para prever a demanda
de cada horário, a estratégia proativa utiliza a diferença no número de usuários para mudar a quantidade de máquinas alocadas. Por outro lado (ii) tenta somente balancear o
sistema baseado nos problemas enfrentados no monitoramento anterior, não reduzindo o
custo como (i). A terceira categoria de estratégia é uma mescla entre as duas anteriores,
utilizando a estratégia proativa como principal forma de alocação de servidores e a reativa
para aumentar a quantidade de superpeers.
Para comparar as heurísticas foram implementadas algumas estratégias “inocentes”,
como utilizar um servidor por usuário ou um número fixo de servidores. A primeira estratégia mostrou-se barata, mas ineficiente para manter uma boa qualidade de experiência e
a segunda deveras mais cara e incapaz de manter uma qualidade tão boa quanto a melhor
estratégia proposta, como pode ser visto nos resultados obtidos em simulações.
Em nossos testes, a heurística híbrida foi capaz de combinar os melhores aspectos das
heurísticas reativas e proativas, resultando em um sistema de menor custo que consegue
manter uma baixa quantidade de interrupções se comparada com as demais. A estratégia
de alugar servidores quando usuários entram no sistema é mais efetiva que reagir a interrupções, mas transformar usuários em superpeers somente quando o sistema está estável
é uma estratégia melhor para evitar interrupções.
As três categorias de heurísticas se mostraram mais eficientes que as estratégias ingênuas como alocar uma máquina para cada usuário ou manter a quantidade de máquinas
estático. De forma intuitiva é possível enxergar que manter o número de máquinas estático e em um baixo número terá um custo menor, porém aumenta drasticamente o tempo
necessário para suprir todos os usuários da rede se comparada com as demais estratégias.
Alocar uma máquina para cada usuário resulta em um custo alto de recursos do provedor de nuvem e não resulta em menor número de interrupções se comparado à heurística
Reativa 0.05, por exemplo. Esta diferença se dá principalmente pelo número de superpeers das heurísticas, que acabam barateando o sistema (diminuindo a vazão de dados da
nuvem) e por criarem mais fontes de dados para o sistema.
Nos experimentos aqui citados, aumentar a banda de saída/entrada dos usuários fez
com que o custo do sistema barateasse, dado que usuários podem contribuir mais efetivamente com a transmissão de dados, reduzindo custos da transferência da nuvem. Nos
cenários onde a nuvem e os usuários tinham a mesma taxa de transferência, o custo foi
CAPÍTULO 8. CONCLUSÕES
57
cortado drasticamente. Por outro lado, dada a natureza heterogênea de redes P2P, não é
possível assumir este tipo de requisito para sistemas reais.
Foram discutidas as possibilidades para a implementação de um sistema real, revisando
a literatura. Para isto, foi utilizado o modelo de provedor em nuvem da Amazon AWS,
alocando máquinas com imagens pré-definidas pelo usuário e calculando o custo utilizando
tanto o aluguel da máquina como a transferência de dados para fora da nuvem. Quanto
às variantes do protocolo, foram discutidas algumas alternativas disponíveis na literatura,
como por exemplo o mesh-push ou versões mistas de push e pull. Essas variantes apesar
de terem um bom desempenho, consomem uma quantidade de tempo maior toda vez que
usuários deixam o sistema, por ser necessário reconstruir a rede overlay em formato de
árvore.
Por fim, é possível afirmar que a utilização de redes P2P pode de fato vir a reduzir
o custo da transmissão de vídeos sob demanda, sem um alto nível de degradação na
qualidade do serviço ofertado. Se preparar para um aumento de demanda (como o Netflix
faz) é mais eficiente que reagir a instabilidades e aumentar o número de superpeers somente
quando o sistema atinge uma certa estabilidade resultou em melhores resultados nas
simulações apresentadas.
Como trabalho futuro, as heurísticas podem ser implementadas com arcabouços utilizados por sistemas reais, a fim de verificar o tempo gasto para a sincronização dos peers
e testar a qualidade de experiência do usuário. Além disso, em um sistema real, seria
possível medir o tempo médio que uma máquina leva para ser alocada no sistema e diferentes latências de rede dependendo da região onde a máquina é alocada. As heurísticas
também podem ser alteradas para simulações com diferentes provedores, para além de escolherem a quantidade necessária de instâncias, também levarem em consideração o preço
dos provedores e região. Ainda, um estudo aprofundado sobre heterogeneidade da largura
de banda de saída dos usuários pode trazer a necessidade de novas heurísticas. Também pode-se adicionar técnicas de aprendizado de máquina nas heurísticas para utilizar
o histórico do uso do sistema para prever a quantidade correta de servidores necessários.
Referências Bibliográficas
[1] App Engine run your applications on a fully-managed platform-as-a-service (paas)
using built-in services. https://cloud.google.com/appengine/. Acessado: 201501-17.
[2] AWS
what
is
cloud
computing.
what-is-cloud-computing. Acessado: 2015-01-10.
[3] Azure microsof’s cloud computing platform.
en-us/. Acessado: 2015-01-17.
http://aws.amazon.com/
http://azure.microsoft.com/
[4] Freenet. https://freenetproject.org/. Acessado: 2015-01-10.
[5] Github popcorntime-app. https://github.com/era/popcorn-app/tree/master/
node_modules/peerflix. Acessado: 2015-01-10.
[6] Heroku adpet scale. https://addons.heroku.com/adept-scale?utm_campaign=
category&utm_medium=dashboard&utm_source=addons. Acessado: 2015-01-10.
[7] Netflix scryer: Netflix’s predictive auto scaling engine.
http://techblog.
netflix.com/2013/11/scryer-netflixs-predictive-auto-scaling.html. Acessado: 2015-01-09.
[8] Popcorn Time. https://popcorn-time.se/. Acessado: 2015-01-10.
[9] RT USA popcorn time, a new streaming bittorrent site, takes on netflix. http://rt.
com/usa/popcorn-time-streaming-bittorrent-netflix-234/. Acessado: 201501-19.
[10] V.K. Adhikari, Yang Guo, Fang Hao, M. Varvello, V. Hilt, M. Steiner, and Zhi-Li
Zhang. Unreeling netflix: Understanding and improving multi-cdn movie delivery.
In INFOCOM, 2012 Proceedings IEEE, pages 1620–1628, March 2012.
[11] Abbas Bradai and Toufik Ahmed. Differenciated bandwidth allocation in P2P layered
streaming. CoRR, abs/1401.6132, 2014.
[12] James Broberg, Rajkumar Buyya, and Zahir Tari. Creating a ‘cloud storage’ mashup
for high performance, low cost content delivery. In George Feuerlicht and Winfried
Lamersdorf, editors, Service-Oriented Computing – ICSOC 2008 Workshops, volume
5472 of Lecture Notes in Computer Science, pages 178–183. Springer Berlin Heidelberg, 2009.
58
REFERÊNCIAS BIBLIOGRÁFICAS
59
[13] John F. Buford, Ken Kerpez, Yuanqiu Luo, Dave Marples, and Stan Moyer. NetworkAware Peer-to-Peer (P2P) and Internet Video. International Journal of Digital Multimedia Broadcasting, 2010:1–2, 2010.
[14] Fangfei Chen, K. Guo, J. Lin, and T. La Porta. Intra-cloud lightning: Building cdns
in the cloud. In INFOCOM, 2012 Proceedings IEEE, pages 433–441, March 2012.
[15] Yih-farn Chen, Yennun Huang, Rittwik Jana, Hongbo Jiang, and Michael Rabinovich. When is P2P Technology Bene fi cial for IPTV Services ?
[16] Yih-Farn Chen, Yennun Huang, Rittwik Jana, Hongbo Jiang, Michael Rabinovich,
Jeremy Rahe, Bin Wei, and Zhen Xiao. Towards capacity and profit optimization
of video-on-demand services in a peer-assisted IPTV platform. Multimedia Systems,
15(1):19–32, jun 2008.
[17] Ian Clarke, Oskar Sandberg, Brandon Wiley, and TheodoreW. Hong. Freenet: A distributed anonymous information storage and retrieval system. In Hannes Federrath,
editor, Designing Privacy Enhancing Technologies, volume 2009 of Lecture Notes in
Computer Science, pages 46–66. Springer Berlin Heidelberg, 2001.
[18] Diego Sanchez Gallo. Arquitetura de IPTV com Suporte à Apresentação Deslocada
no Tempo Baseada em Distribuição Peer-to-Peer Arquitetura de IPTV com Suporte
à Apresentação Deslocada no Tempo Baseada em Distribuição Peer-to-Peer. 2009.
[19] Seton Hall and Camille Marie Johnson. Cutting the Cord : Leveling the Playing
Field for Virtual Cable Companies. 2014.
[20] X. Hei, C. Liang, J. Liang, Y. Liu, and K. W. Ross. A measurement study of a
large-scale p2p iptv system. IEEE Transactions on Multimedia, 9(8):1672–1687, Dec
2007.
[21] Cheng Huang, Jin Li, and Keith W. Ross. Can internet video-on-demand be profitable? SIGCOMM Comput. Commun. Rev., 37(4):133–144, August 2007.
[22] Elias De O Granja Jr, Luiz F Bittencourt, Ioan Petri, Omer F Rana, and César A V
Melo. Managing QoS Constraints in a P2P-Cloud Video on Demand System. In
Proceedings of IEEE 2016 CLOUD, pages 4–7.
[23] C. Y. Keong, P. K. Hoong, and C. Y. Ting. Efficient hybrid push-pull based p2p
media streaming system. In Parallel and Distributed Systems (ICPADS), 2011 IEEE
17th International Conference on, pages 735–740, Dec 2011.
[24] Ken Kerpez, Yuanqiu Luo, and Frank J. Effenberger. Bandwidth reduction via
localized peer-to-peer (p2p) video. International Journal of Digital Multimedia Broadcasting, 2010, 2010.
[25] Zhenhua Li, Tieying Zhang, Yan Huang, Zhi-Li Zhang, and Yafei Dai. Maximizing
the bandwidth multiplier effect for hybrid cloud-p2p content distribution. pages
20:1–20:9, 2012.
REFERÊNCIAS BIBLIOGRÁFICAS
60
[26] Cesar A. V. Melo, Jhonathan Araujo Oliveira, and Nelson L. S. da Fonseca. Promotion of content availability by playlist viewers in CDN-P2P systems. In Proceedings
of IEEE ICC 2013, pages 2298–2302, 2013.
[27] Cesar A. V. Melo, Jhonathan Araujo Oliveira, and Gustavo B. Figueiredo. Towards
peer-assisted video on demand system: Building helpful overlays. In Proceedings of
IEEE LATINCOM 2015, 2015.
[28] Alberto Montresor and Márk Jelasity. PeerSim: A scalable P2P simulator. In Proc.
of the 9th Int. Conference on Peer-to-Peer (P2P’09), pages 99–100, Seattle, WA,
September 2009.
[29] Dj Oneil, Hun Jeong, Kang Jinoh, and Kim Donghyong Kwon. Transport layer
identification of p2p super nodes.
[30] K. N. Parvez, C. Williamson, Anirban Mahanti, and Niklas Carlsson. Analysis of
bittorrent-like protocols for on-demand stored media streaming. In In Proc.of the
2008 ACM SIGMETRICS Int. Conf, pages 301–312, 2008.
[31] Amir H. Payberah, Hanna Kavalionak, Vimalkumar Kumaresan, Alberto Montresor, and Seif Haridi. CLive: Cloud-assisted P2P live streaming. 2012 IEEE 12th
International Conference on Peer-to-Peer Computing, P2P 2012, (i):79–90, 2012.
[32] Michael Piatek, Colin Dixon, Arvind Krishnamurthy, and Thomas Anderson. Liveswarms: Adapting bittorrent for end host multicast.
[33] Vladimir Rocha, Fabio Kon, and Raphael Cobe. A hybrid cloud-P2P architecture
for multimedia information retrieval on VoD services. Computing, 98(1):73–92, 2016.
[34] Mehdi Seydali Seyfabad. Virtual Machine Allocation in P2P-Cloud Live Video Straming. 2015.
[35] Hao Yin, Xuening Liu, Tongyu Zhan, Vyas Sekar, Feng Qiu, Chuang Lin, Hui Zhang,
and Bo Li. Design and Deployment of a Hybrid CDN-P2P System for Live Video
Streaming : Experiences with LiveSky. pages 25–34.
[36] If You, Beat Em, and Join Em. Incentives for P2P-Assisted Content Distribution: If
You Can’t Beat ’Em, Join ’Em. pages 1–20.
[37] Jian Zhao, Chuan Wu, and Xiaojun Lin. Locality-aware streaming in hybrid p2pcloud cdn systems. Peer-to-Peer Networking and Applications, pages 1–16, 2013.

Elias de Oliveira Granja Junior Heurísticas para

Transcrição

Documentos relacionados

A Nuvem do não saber

Tutorial de Nuvem de Palavras Elaborado por Martha F. Prado

Apresentação do PowerPoint

shop control 9.2.10 – 24/05/2016

a bandeira da pirataria

Instâncias gerenciadas e servidores bare-metal na nuvem

NetApp - DataFabric - A Nuvem Hibrida

COLETANEA DE ADIVINHAS

S-NPP - Sigma

Dica de Segurança de P rocesso