Upload
internet
View
104
Download
0
Embed Size (px)
Citation preview
Distribuição de Mídia Contínua
Recuperação de Erros
Jussara M. Almeida
Junho 2005
Qualidade do Video e Audio• Afetada pela perda de pacotes e atrasos na
rede
• Uso de buffers no cliente minimiza impacto dos atrasos na rede
• E quanto a perda de pacotes?
– Mecanismos de controle de taxa de transmissao: minimiza mas nao elimina perda
– Automatic Repeat Request (ARQ): retransmissao
• Aumenta latencia: inadequado para aplicacoes ao vivo
– Forward Error Correction (FEC): envio de informacao redundante
• Nao altera latencia, mas aumenta consumo de banda
Forward Error Correction• Compromisso:
– Enviar grande quantidade de informacao redundante aumenta a probabilidade de recuperacao frente a perdas
– Porem aumenta o consumo de banda na rede e, consequentemente, a taxa de perdas
• Logo: mecanismo de FEC tem que ser acoplado a um esquema de controle de taxa de transmissao.
• Alem disto, a quantidade de informacao redundante que deve ser enviada depende:
– Caracteristicas do processo de perdas de pacotes no momento
– Restricoes de atraso entre servidor e cliente
– Qualidade da informacao redundante
Problema• Dados a taxa total que o servidor pode
suportar transmitir e o atraso maximo suportado pelo cliente, determinar a combinacao de informacao principal e informacao redundante que prove a melhor qualidade de audio percebida pelos usuarios
• Objetivo: utilizar metricas subjetivas de qualidade de audio
– Simplesmente taxa de perda de pacotes nao e suficiente
– EX: 10 perdas de 1 pacote cada espacadas vs. 1 perda de 10 pacotes consecutivos
Modelo de Perda de Pacotes
• Area de pesquisa ativa
• Modelo mais simples: modelo de Gilbert de 2 estados
p
q
1-q1-p10
Probabilidade de perda = p / (p+q)
Modelo de FEC 1 - mais simples• Inclui no pacote n+1, em adicao aos frames
correspondentes, informacao sobre o pacote n que pode ser usado para reconstruir (uma aproximacao) do pacote n
– Esquema aprovado pelo IETF: informacao redundante e uma codificacao com bitrate mais baixa do pacote n.
– Surpreendentemente, a qualidade subjetiva do audio reconstruido com este metodo foi avaliada como muito boa
– Mecanismo suporta recuperacao de perdas isoladas
• Se 2 pacotes consecutivos sao perdidos nao e possivel recuperar informacao sobre um deles
Modelo de FEC 2• Inclui no pacote n+1, em adicao aos frames
correspondentes, informacoes redundantes sobre os pacotes n e n-1, ou sobre os pacotes n, n-1 e n-2, ou sobre os pacotes n-1 e n-3, etc
– Mecanismo suporta recuperacao de perdas em rajadas
• Informacao redundante de um pacote e espalhada por multiplos pacotes
– Quanto mais info redundante e adicionada, maior o numero de pacotes perdidos que poderao ser reconstruidos
– Problema: quantidade de informacao redundante depende do processo de perda na rede no momento em questao
Modelo de FEC 3 • Algoritmo adaptativo simples
– Precisa saber o beneficio que cada informacao extra fornece para escolher a combinacao perfeita
– Para estimar este beneficio, usa o modelo de Gilbert para perdas de pacotes:
• Ausencia de FEC
– Probabilidade de perda: 1 = p / (p+q)
• FEC com pacote n contendo info sobre pacote n-1
– Probabilidade de perda pos reconstrucao: 2 = p (1-q) / (p+q)
2/1 = (1-q):
– Se q = 0.7 (tipico), reducao na perda de 70%
Modelo de FEC 3
Modelo de FEC 3 • Algoritmo adaptativo simples
– Tendo uma taxa de perda de pacotes alvo como objetivo basta que o servidor escolha o metodo de redundancia que leve a taxa de perdas mais proxima do objetivo
– Precisa saber p e q
• Cliente pode medir e retornar em campos livres do RTCP
• Assume que processo de perda e Bernoulli: p + q = 1. Taxa de perdas (p / p+q) observada e igual a p.
Modelo de FEC 3 • Exemplo
Modelo de FEC 3 • Desvantagens
– Algoritmo minimiza taxa media de perdas (apos reconstrucao), que nao necessariamente implica melhor qualidade de audio
• EX: qualidade seria pobre se qualidade da info usada para reconstrucao e baixa
– Adicionar info redundante aumenta demanda por banda: precisa acoplar algoritmo a um mecanismo de controle de transmissao
• Objetivo e que servidor dinamicamente ajuste a taxa de transmissao e a quantidade de info redundante enviada para minimizar a perda percevida pelos clientes
Modelo de FEC 4 • Modelo de otimizacao conjunto para otimo FEC
e taxa de transmissao
• Seja f(x): qualidade de um audio com taxa x
• Sejam 0 e 1 as probabilidades de um pacote
ser recebido e ser perdido, respectivamente
– Calculadas de uma cadeia de Markov
• Seja um esquema de FEC que envia K copias de cada pacote (K-1 redundantes + 1 principal)
• Seja ainda T o atraso maximo entre enviar a primeira e a ultima copia de um pacote
Modelo de FEC 4 • Questao 1: Dados que vamos transmitir k copias de
cada pacote e o atraso maximo T, como devemos espacar as copias de forma a maximizar a probabilidade de que pelo menos uma copia seja recebida?
– Seja p11(t) a probabilidade de que o processo de perdas esteja no estado 1 (perda) no instante t + , dado que ele estava no estado 1 no instante
– Probabilidade de perder TODAS as K copias de um pacote
Modelo de FEC 4 • Questao 1: Dados que vamos transmitir k copias de
cada pacote e o atraso maximo T, como devemos espacar as copias de forma a maximizar a probabilidade de que pelo menos uma copia seja recebida?
• Solucao otima: as K copias devem ser igualmente espacadas no intervalo [0,T]
Modelo de FEC 4 • Questao 2: Dado que K copias serao transmitidas
igualmente espacadas no intervalo de tamanho T, quais as taxas de codificacao a serem usadas para cada copia, a fim de maximizar a qualidade de audio, sujeito a restricoes na taxa maxima
– Informacao principal deve ser codificada usando a maior taxa possivel
– A ultima copia deve ter maior taxa que todas as outras copias
• Algoritmo heuristica para alocacao de taxas discretas
– Confuso
Avaliacao • Impacto da funcao de qualidade de audio
– f0(x) = x
• Solucao otima sempre aloca a taxa maxima para a informacao principal e nao envia nenhuma info redundante
– f1(x): baseada na razao sinal/ruido
– f2(x): baseada no mean opinion score (MOS) (subjetivo)
– f3(x) = 1 para x 0 e f3(0) = 0
• Funcao e maxima se pelo menos alguma informacao e recebida, independente da qualidade dela: minimiza taxa de perdas, enviando muita info redundante
Avaliacao • Impacto da funcao de qualidade de audio
Avaliacao • Funcionamento
(T=4)
• Encontra combinacao otima de info redundante ao inves de pegar uma combinacao fixa que leva a uma taxa alvo– Leva em consideracao banda disponivel e perdas ocorridas no
momento e restricao de atraso
Avaliacao
• Funcao que leva a melhor qualidade percebida e a f2(x), baseada nos MOS scores
• Pouca diferenca entre usar f0 (sem FEC) e otimizar f1 (signal/noise ratio)
– Otimizar para SNR leva a qualidade pobre
Avaliacao • Impacto de T (ou numero de copias
redundantes)
Avaliacao • Impacto de T (ou numero de copias
redundantes)
– Adicionar 1 copia (adicionar info redundante em pacote n sobre pacote n-1) melhora significativamente qualidade
• Exceto para f1 (signal/noise ratio) que e proxima de f0 (sem FEC)
– Observar diminishing returns: adicionar pouca quantidade de redundancia ja leva a maioria do beneficio provido por FEC
– Notar variacao da qualidade com a funcao utilizada
• Necessidade de escolher f cuidadosamente
Distribuição de Mídia Contínua
Protocolos de Transmissao com
Recuperação de ErrosJussara M. Almeida
Junho 2005
Base• Digital Fountain:
– Download com recuperação de erros
– Erasure codes
– Alta latência inicial
• Transmissão sob demanda com compartilhamento de fluxos
– Periodic Broadcast, Patching, Bandwidth Skimming
– Recuperação de erros: local error concealment
• Adequado para baixas taxas de perdas
– Dificil extensão para recuperação de outras perdas
• Transmissão de pacotes o mais tarde possível
Base• Novos protocolos baseados em periodic
broadcast (Harmonic Broadcast)
– Cada segmento recebido inteiramente antes de playback
– Extensão para uso de erasure code: fácil
– Mas:
• Cliente tem que escutar todos segmentos simultaneamente (b=5,10) :
• Grande quantidade de buffer no cliente
Revisão• Skyscraper Broadcast (b = 2)
– Parametros: # e tamanho dos segmentos
Revisão• Harmonic Broadcast
– Divisão do arquivo em segmentos de tamanho iguais, segmento k transmitido a taxa 1/k
– Clientes escutam todos segmentos simultaneamente, comeca a tocar cada segmento depois de recebe-lo inteiramente
– Alta latência, alto b
Revisão• Bandwidth Skimming
– Closest Target (b=2), Partition (b < 2)
Revisão• Bandwidth Skimming
Revisão• Banda do Servidor para Protocolos com d
> 0
Revisão• Banda Media do Servidor Minima:
Objetivo• Novos protocolos baseados em periodic broadcast
e bandwidth Skimming com as características:
– Conveniência: baixa latência (dentro de limite)
– Tolerância a taxas de perdas e heterogeneidade
– Confiabilidade: recuperação de erros se taxa de perda acumulada dentro de um limite pre-definido
– Eficiência: mínimo feedback do cliente, mínima quantidade de dados para clientes
– Mídia de Alta Qualidade: max taxa de transmissão do cliente limitada (eg: 25% maior que taxa de playback)
– Escalabilidade: demanda por banda do servidor próxima da mínima
• Espaço de Trabalho: Fig 4
Recuperação de Perdas• Três classes de estratégias:
– Erasure code (FEC)
– Retransmissão via unicast
– Retransmissão via multicast
• Análise qualitativa:
– Complexidade de implementação:
• (De)codificação X implosão de retransmissão/feedback
– Latência inicial:
• Mesma magnitude esperada em todas estratégias• Mais facilmente estimada para erasure code
Recuperação de Perdas– Escalabilidade:
•Retransmissão via multicast :
– Alguns clientes podem receber dados desnecessários
•Erasure code: – Um dado redundante usado para recuperar
perdas diferentes – Maior escalabilidade esperada
Recuperação de Perdas• Escalabilidade: avaliação analítica
– Retransmissão via multicast: solução numérica
Recuperação de Perdas• Escalabilidade: avaliação analítica
Reliable Periodic Broadcast1. Optimized Periodic Broadcast:
– Max progressão de tamanhos de segmentos para:• Taxa de transmissão de cada segmento: r ( r
< 1)• Número de fluxos simultâneos cliente pode
escutar: s – Cliente recebe cada segmento inteiramente
antes de tocá-lo– Recuperação de perdas local– Min latência para banda do servidor fixa ou
vice-versa– Objetivo: explorar trade-offs para b = r*s < 2
Reliable Periodic Broadcast
2. Basic Reliable Periodic Broadcast:– Recuperação de perdas com erasure code– Taxa de perda acumulada ao final de
cada segmento p
3. Reliable Periodic Broadcast:– Rajadas: maior taxa de perdas nos primeiros
segmentos
4. Heterogeneidade de clientes e transmissão com perdas maiores que o limite pre-definido p
Optimized Periodic Broadcast• Perda de pacotes: local error concealment
• Segmento inteiramente recebido antes de iniciar visualização
• Protocolo:
Optimized Periodic Broadcast• Protocolo:
– Novo cliente imediatamente começa a escutar os primeiros s fluxos – Quando primeiro segmento completamente recebido:
• Cliente inicia visualização e • Começa a receber segmento s+1
• Max progressão dos tamanhos dos segmentos:
– r = 1:
– r < 1:
– Extensões para incluir overhead de decodificação e de estabelecer conexão multicast
Optimized Periodic Broadcast• Desempenho:
Optimized Periodic Broadcast• Desempenho:
– Banda do servidor :
• Optimized PB competitivo com Skyscraper apesar de exigir recebimento total de cada segmento antes de visualização
• Menor r melhor desempenho
– Menor latência para banda fixa ou menor banda para latência fixa
– Frequência de Multicasts :
• Lower bound: 1/(x+d)
• Dados no mesmo segmento transmitidos na mesma freq.
• Menor r, maior k, menor tamanho do segmento
Basic Reliable Periodic Broadcast
• Cada segmento transmitido como digital fountain usando erasure code
Basic Reliable Periodic Broadcast
• Cada segmento transmitido como digital fountain usando erasure code
– Sem limites de segmentos
– Poucas perdas no início levam a início dos próximos segmentos mais cedo e permite mais perdas no final (desde que acumulada esteja limitada a p
• Premissa: taxa de perda de pacotes acumulada ao final do recebimento de cada pacote limitada a p
Basic Reliable Periodic Broadcast
• Nova progressão de segmentos
– a = 1/(1-p) : # pacotes recebidos
– a pode incluir acréscimo devido a redundancia
• p=0.2 e eficiência de decodificação = 1.05: p = 1.05*1.25 = 1.3125
Basic Reliable Periodic Broadcast
• Desempenho do Basic RPB:
Basic Reliable Periodic Broadcast
• Desempenho do Basic RPB:
Basic Reliable Periodic Broadcast
• Desempenho do Basic RPB:
– Tradeoff entre latência e banda para perda fixa.
– Menor r, maior desempenho (diminishing returns)
– Mas menor r, maior # segmentos, segmentos menores, menor overhead de decodificação.
• Extensão para rajadas de perdas:
– Segmentos iniciais, menores, mais afetados
– Parâmetro a = 1/1 – p * eficiência de decodificação
– Segmentos iniciais tem valores de a maiores
Basic Reliable Periodic Broadcast
• Max perda permitida para diferentes posições do arquivo usando valores de a variáveis:
Heterogeneidade de Clientes
• Soluções:
– Simulcast: diversas versões do objeto
– Codificação em camadas
• Pode-se acomodar heterogeneidade de clientes (limitada) com o RPB:– Explorar trade-offs entre latência, taxa de
perdas e taxa de transmissão para cliente
– Políticas específicas: future work
Reliable Bandwidth Skimming
• Transmissão em dois fluxos a taxa total 1/(1-p)
– Primário, a taxa 1
– Secundário a taxa p/(1-p): deslocado no tempo para prover melhor proteção contra rajadas
• Merges ocorrem como no BWSkim básico entre fluxos primários e entre fluxos secundários.
Reliable Bandwidth Skimming• Desempenho
RPB vs. RBS
• RBS:
– Banda de servidor é função da carga (se carga leve, demanda pequena)
– Suporte para interatividade
• RPB:
– Um pouco mais eficiente com respeito a quantidade de dados recebidos por cada cliente
– Mais tolerante a rajadas de perdas sem interrupção