Papers
A Buffer-Based Approach to Rate Adaptation: Evidence from a Large Video Streaming Service
Te-Yuan Huang, Ramesh Johari, Nick McKeown, Matthew Trunnell, Mark Watson · ACM SIGCOMM 2014, 2014
O problema: escolher a taxa de vídeo sem estourar o buffer
Nos serviços de streaming descritos no paper, cada vídeo é codificado em várias taxas (tipicamente de 235 kb/s, definição padrão, até 5 Mb/s, alta definição) e guardado em servidores como arquivos separados. O cliente (TV, console, navegador etc.) decide qual taxa baixar a cada trecho, observando a rede e estimando a capacidade disponível; esse processo é chamado de seleção adaptativa de taxa, ou ABR. Um algoritmo ABR tenta atender dois objetivos ao mesmo tempo. O primeiro é maximizar a qualidade, escolhendo a maior taxa que a rede sustenta. O segundo é minimizar os rebuffers, as paradas de reprodução que ocorrem quando o buffer de reprodução esvazia. Cada objetivo isolado é trivial: transmitir sempre na taxa máxima dá a melhor qualidade, mas arrisca muitos rebuffers; transmitir sempre na taxa mínima quase elimina rebuffers, mas entrega qualidade baixa. A dificuldade está em obter bom desempenho nas duas métricas juntas. O cliente requisita chunks de vídeo de duração fixa (quatro segundos no serviço estudado), e quanto maior a taxa, maior o chunk em bytes. O buffer é medido em segundos de vídeo e drena a um segundo por segundo; se o algoritmo pede taxa acima da capacidade, o buffer encolhe até a reprodução congelar.
Por que estimar a banda é frágil
A abordagem corrente, segundo o paper, é estimar a capacidade futura a partir do que se observou no passado e escolher a taxa com base nisso. Em rede estável isso funciona, mas em ambientes de vazão muito variável a estimativa precisa fica difícil. Os autores mostram um trace real de um player da Netflix em que a vazão medida por chunk oscila entre cerca de 17 Mb/s e 500 kb/s. A variação tem várias causas possíveis, como interferência de WiFi, congestionamento na rede, no cliente ou no servidor. Os autores definem variação como a razão entre o percentil 75 e o 25 da vazão (5,6 nesse trace) e informam que aproximadamente 10% das sessões têm ao menos essa variação. Muitos algoritmos tentam compensar aplicando um fator de ajuste, função do nível do buffer, sobre a estimativa: mais agressivo com buffer cheio, mais conservador com buffer quase vazio. A análise do paper mostra o limite disso: para garantir que não haja rebuffer, o fator precisa ser menor que a pior razão entre capacidade real e estimada. No trace citado essa razão chega a 0,03, e o fator teria de ser 0,03 ou menos, resultando numa taxa de apenas 3% da que uma estimativa correta permitiria. Um exemplo da Netflix mostra o erro oposto: o cliente superestimou a banda, continuou pedindo taxa alta e ficou parado por 200 segundos, num caso em que a capacidade nunca ficou abaixo da taxa mínima.
A ideia central: a taxa como função do nível do buffer, com reservatório
A inversão proposta é tratar o buffer, e não a estimativa de banda, como ponto de partida. O argumento é que o buffer é exatamente a variável de estado que o algoritmo precisa controlar. Um algoritmo é chamado de baseado em buffer quando escolhe a taxa como função do nível atual de ocupação, por meio de um mapa de taxa que vai da taxa mínima (buffer vazio) à máxima (buffer cheio). Sob suposições idealizadas (chunks infinitesimais, qualquer taxa disponível, codificação em taxa constante, vídeos infinitos), os autores resumem uma prova: qualquer mapa contínuo, estritamente crescente na faixa intermediária e preso nas duas pontas (taxa mínima com buffer zero, máxima com buffer cheio) evita rebuffers desnecessários e, quando a capacidade fica sempre entre a taxa mínima e a máxima, faz a taxa média acompanhar a capacidade média. A razão do primeiro resultado é que, enquanto a capacidade não cair abaixo da taxa mínima, o buffer começa a crescer antes de esvaziar. No mundo real, com chunks finitos, o mapa é deslocado para a direita, criando um reservatório: com o buffer dentro dele, pede-se sempre a taxa mínima. Depois vem a área de cushion, onde a taxa sobe, e uma região superior onde já se pede a taxa máxima. No primeiro algoritmo, o BBA-0, o reservatório era fixo em 90 segundos, o cushion tinha 126 segundos e o buffer total era de 240 segundos.
VBR e a fase de início: onde a estimativa ainda ajuda
O BBA-0 funcionou, mas deixou dois problemas. Primeiro, vídeos reais são codificados em taxa variável (VBR): a taxa nominal é uma média, e o tamanho dos chunks varia bastante dentro da mesma taxa. Para isso, o BBA-1 calcula o reservatório dinamicamente a partir do tamanho dos chunks futuros (olhando 480 segundos adiante, o dobro do buffer, e limitando o reservatório entre 8 e 140 segundos) e troca o mapa de taxa por um mapa de chunks, que limita o tamanho máximo do próximo chunk conforme o buffer. Segundo, no início da sessão o buffer está vazio e quase não carrega informação sobre a rede; o BBA-1, só no reservatório, pede a taxa mínima e fica conservador demais. O BBA-2 acrescenta uma estimativa simples nessa fase: só olha a vazão do último chunk e sobe de taxa se o chunk baixou muito mais rápido do que o tempo de reprodução. O limiar começa em oito vezes mais rápido e diminui linearmente conforme o cushion enche. Assim que o mapa de chunks sugere uma taxa maior, ou o buffer passa a cair, o BBA-2 volta a ser puramente baseado em buffer. Os autores comparam isso à partida lenta (slow start) do TCP: no começo o estado não diz nada sobre a rede, mas o aumento de taxa precisa ser controlado para não causar rebuffers.
Resultados em produção e a lição do paper
Os experimentos rodaram no player de navegador da Netflix, em testes A/B com mais de meio milhão de usuários reais cada, em três continentes, durante fins de semana entre maio e setembro de 2013. Cada grupo foi comparado ao algoritmo padrão da Netflix na época (Control), que escolhia a taxa principalmente por estimativa de capacidade, e a um grupo que sempre pedia a taxa mínima, usado como limite inferior empírico de rebuffers. Pela diferença entre Control e esse limite, os autores concluem que 20 a 30% dos rebuffers podem vir de má escolha de taxa. O BBA-0 teve taxa de rebuffer 10 a 30% menor que o Control, mas entregou taxa de vídeo cerca de 100 kb/s menor no horário de pico e 175 kb/s menor fora dele. O BBA-1 melhorou a taxa de rebuffer em 20 a 28% no pico; o BBA-2 manteve 10 a 20% de melhora no pico, com taxa de vídeo praticamente indistinguível do Control e, excluindo os dois primeiros minutos, em geral maior. A variante BBA-Others, que suaviza as trocas de taxa, reduziu rebuffers em 20 a 30% frente ao Control. A conclusão: a estimativa de capacidade é desnecessária no regime estável, mas útil no início; e o ônus da prova fica com quem projeta o algoritmo e quer adicionar complexidade.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.