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
1-p
0
1
1-q
q
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 n2, 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 Erros
Jussara M. Almeida
Junho 2005
• Digital Fountain:
Base
– 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 Broadcast
1.
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 viceversa
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