AVALIANDO O DESEMPENHO DE NOVAS VARIANTES DOS ALGORITMOS LRU E LFU PARA SERVIDOR PROXY VÍDEO SOB DEMANDA

  • Matheus Henrique Koch
  • Bruno Silveira Neves
Rótulo Taxa, acertos, Algoritmos, cacheamento, vídeo, Streaming, video, Least, Recently, Used, Frequently

Resumo

O relatório anual da empresa Cisco (20182023) transmite uma previsão do aumento de novos usuários de internet de 51% (~3,9 bilhões de usuários) para 66% (~5.3 bilhões de usuários) e também menciona que a velocidade média global de banda larga irá dobrar de 2018 para 2023. O Relatório Global de Fenômenos da Internet COVID-19 da Sandvine, apresenta que 57% do volume de tráfego global é composto por streaming de vídeo e indica que as aplicações de Vídeo sob Demanda tiveram um crescimento do ano 2019 para 2020. Com as informações fornecidas através destes relatórios, podemos concluir que o crescimento do uso da rede é iminente, e, sendo assim compreende-se que será necessário um aprimoramento das Redes de Distribuição de Conteúdo (Content Delivery Networks - CDNs). As CDNs são formadas por um conjunto de milhares de servidores de ampla variedade , distribuídos geograficamente pelo mundo, capazes de sustentar grandes cargas de trabalho em pontos críticos de tráfego. O conjunto de servidores de uma CDN armazena inteira ou parcialmente os conteúdos mais importantes de um acervo digital (como, por exemplo, os mais acessados, ou mais recentemente acessados), para diminuir o tráfego nos diferentes pontos da rede, já que a disponibilidade destes conteúdos em pontos estratégicos da CDN faz com que as requisições não necessitam ser transmitidas até o ponto de origem do conteúdo (o servidor primário). Neste contexto, os servidores proxies VoD, que são servidores desenvolvidos especificamente para distribuição de vídeo, exercem um papel fundamental nas CDN, pois eles implementam o armazenamento inteligente das porções mais relevantes do acervo de modo a abastecer as solicitações dos clientes em lugar do servidor primário. O servidor proxy VoD tem uma capacidade de armazenamento limitada e por isso é necessária uma política de substituição do conteúdo capaz de identificar e priorizar o armazenamento dos conteúdos que possibilita à CDN atender ao maior número possível de clientes simultâneos. Os algoritmos usados nos servidores proxies de VoD representam uma importante parte do desempenho desses servidores, pois impactam na taxa de acertos desses algoritmos, ou seja, reduz o número de requisições que necessitam acessar o ponto de origem do conteúdo. Neste contexto, o objetivo deste trabalho consiste em avaliar os benefícios produzidos pela modificação dos algoritmos Least Recently Used (LRU) e Least Frequently Used (LFU), buscando um aumento da taxa de acertos através da implementação de uma janela temporal fixa de análise. Os experimentos para avaliação dos algoritmos modificados foram conduzidos gerando diversos cenários representativos da carga exercida pelos clientes na rede. Estes cenários foram modelados usando o coeficiente Zipf para indicar a frequência dos vídeos e o coeficiente de Poisson para definir o comportamento do intervalo temporal entre chegadas sucessivas dos clientes. Em seguida, os algoritmos foram integrados a um simulador que avalia a taxa média de acerto dentro de um período definido. Foram implementados e avaliados neste trabalho os seguintes algoritmos Randon: LRU, LFU, FIFO (First In First Out), CC, CARTE (Current demAnd Rather Than futurE), além das duas variantes de LRU e LFU propostas neste estudo, denominadas WLRU (Windowing Least Recently Used) e WLFU (Windowing Least Frequently Used). Os algoritmos CC e CARTE foram usados também para validar o funcionamento do simulador, fazendo a comparação da taxa média de acertos produzida pela simulação destes algoritmos com aquela publicada em trabalhos da literatura. Para cada algoritmo, procedeu-se à execução de uma bateria de simulações alterando gradativamente e um a um os seguintes parâmetros: tamanho do armazenamento, largura da banda entre o proxy primário de conteúdo, o coeficiente Zipf e o coeficiente de Poisson. Os resultados encontrados demonstram que a integração de uma janela de tempo ao LRU não trouxe benefícios. Por outro lado, a aplicação da mesma janela ao LFU produziu uma melhora de mais de 20% na taxa de acertos em comparação com LFU clássico original em cenários com o coeficiente Zipf alto (0,75 a 1,0). Os algoritmos CC e WLFU demonstram resultados muito próximos, permitindo concluir que são algoritmos equivalentes no conjunto de testes realizados. Futuros experimentos e análises mais aprofundadas, possivelmente utilizando cenários de maior flutuação da carga de trabalho poderão contribuir para identificar cenários mais oportunos para cada um destes algoritmos. Observou-se ainda que o algoritmo CARTE sempre manteve uma taxa de acertos maior que a dos demais algoritmos, o que indica a possibilidade de execução de experimentos complementares a fim de se identificar possíveis aprimoramentos para o WLFU. Concluímos assim que, até o momento, WLFU aparenta ser um algoritmo promissor, no entanto, é necessário expandir os cenários de teste, para verificar a possibilidade de evidenciar ganhos complementares e melhorias.

Downloads

Não há dados estatísticos.
Publicado
2022-11-23
Como Citar
HENRIQUE KOCH, M.; SILVEIRA NEVES, B. AVALIANDO O DESEMPENHO DE NOVAS VARIANTES DOS ALGORITMOS LRU E LFU PARA SERVIDOR PROXY VÍDEO SOB DEMANDA. Anais do Salão Internacional de Ensino, Pesquisa e Extensão, v. 2, n. 14, 23 nov. 2022.