Distribuição de Mídia Contínua
Transmissão
Jussara M. Almeida
Março 2004
Transmissão de Mídia Contínua
• Transmissão de Fluxos Independentes
– Unicast
Servidor
Origem
Transmissão de Mídia Contínua
• Transmissão de Fluxos Independentes
– Unicast
– Crescimento linear na demanda por largura de
banda do servidor e da rede
– Baixa escalabilidade
• Ex: 1 arquivo MPEG de 1 hora: 1.5 Mbps
1500 fluxos simultâneos : 2.25 Gbps
Transmissão de Mídia Contínua
• Transmissão com Compartilhamento de Fluxos
– Multicast : um único fluxo enviado para múltiplos clientes
• A nível de protocolo de rede IP ou a nível de aplicação
Fluxo multicast
Servidor
Origem
roteador
Transmissão de Mídia Contínua
• Transmissão com Compartilhamento de Fluxos
– Multicast : um único fluxo enviado para múltiplos clientes
• A nível de protocolo de rede IP ou a nível de aplicação
Fluxo unicast
Servidor
Origem
roteador
Transmissão de Mídia Contínua
• Transmissão com Compartilhamento de Fluxos
– Redução significativa na demanda por largura de banda
– Melhora QoS (qualidade observada pelos clientes)
– Classificação
• Cliente recebe apenas 1 fluxo vs. múltiplos fluxos
simultâneos
– Demanda por largura de banda do cliente
• Difusão vs. técnicas orientadas às requisições dos clientes
– Distribuição sob demanda verdadeira
– Escalabilidade e desempenho sob cargas variadas
Dados recebidos
pelos clientes
Batching
Fluxo multicast
com objeto
requisitado por r0-r3
r0
r1
r2 r3
Janela
batching
Tempo
Batching
• Cliente recebe apenas um fluxo
• Método genérico utilizado em conjunto com outras
técnicas
– Transmissão orientada pelas requisiçoes dos clientes
– Às vezes em conjunto com técnicas baseadas em difusão
• Introdução de atrasos de partida adicionais
• Nao provê distribuição sob demanda verdadeira
Piggybacking
• Mudança dinâmica da taxa de transmissão
e exibição para permitir que um fluxo
possa alcançar e se juntar a outro fluxo
• Baseado em stream merge
Piggybacking
Dados recebidos
pelos clientes
Servidor
retarda s0
Stream
merge
s0
s1
Servidor
acelera s1
Tempo
r0
r1
Piggybacking
• Provê vídeo sob demanda verdadeiro
• Cliente escuta/recebe apenas um fluxo
• Não introduz atrasos adicionais na partida
• Requer hardware especialiado para suportar
mudanças dinâmicas na velocidade do canal
• Eficiência limitada pela mudança máxima
tolerada por um usuário (± 5%)
Periodic Broadcast
• Vídeos são transmitidos periodicamente
– novo fluxo a cada  minutos
• Batching de clientes
–  = batching interval
– Latência observada pelo cliente:  (Pior caso)
• Não provê video sob demanda verdadeiro
• Largura de banda fixa, independente da carga
– Eficiente para taxa de chegada de requisições alta
• Diversas otimizacões do protocolo base
– Pyramid Broadcast, Permutation-Based Pyramid Broadcast
– Skyscraper Broadcast
Periodic Broadcast
• Batching de clientes
T
0
...
...
...
...
...
• reserva K canais para cada “hot” “popular”
– novo fluxo multicast do arquivo a cada T/K unid. de tempo
E.x., K=25: maxima latência 0.04T
– Demanda por largura de banda do servidor é independente da
demanda pelo arquivo (carga)
• Outros arquivos: batching sob demanda (FCFS)
Pyramid Broadcast
• Divide cada video em K segmentos de tamanhos crescentes
– D1, D1, 2D1, 3D1 …,  > 1 (crescimento geométrico)
• Largura de banda total B dividida em K canais lógicos
• Canal i transmite ith segmento de cada video, em round
robin a uma taxa B/K (>> taxa de visualização, b)
• Cliente contacta servidor e recebe uma programação de
quando deve se conectar em cada canal
– O download do segmento i pode começar assim que
cliente começa a visualizar segmento i-1
– Cliente recebe em no máximo 2 canais simultâneos
• Visualiza os dados recebidos em 1 canal
• Armazena dados recebidos no outro canal no disco
Pyramid Broadcast
• Latência do cliente diminui com B (bom!!)
– Se B alto suficiente, pode ter a video sob demanda
verdadeiro
• Alta demanda por largura de banda no cliente
– b + 2B/K
• Alta demanda por espaço no cliente
– Precisa armazenar ate 84% do video
Permutation-Based Pyramid Broadcast
• Mesmo princípio do Pyramid Broadcast
• Mas:
– cada canal lógico e dividido em P subcanais para cada
video
– Cada segmento i de um video é transmitido nos subcanais
de i a cada Di/P minutos à taxa B/KPM
• M = # videos
• Redução na demanda por largura de banda e disco
– Redução limitada na demanda por espaço
• progressão geométrica
• Método mais complexo e com latência mais alta
Skyscraper Broadcast
• Divisão da largura de banda total B em B/b canais
• Atribuição de K canais para cada video
– K = B/bM, onde M = # videos
• Cada video é dividido em K segmentos com
tamanhos crescentes seguindo a progressão:
– 1, 2, 2, 5, 5, 12 ,12 ,25, 25, 52, 52, …
• Parâmetro W : restrição no tamanho máximo de
um segmento
– Quanto maior W maior a demanda por espaço no cliente
– Quanto menor W, maior D1, maior latência
Skyscraper Broadcast
• Clientes recebem segmentos em transmission groups
– Cada grupo: segmentos consecutivos com mesmo tamanho
• Tres rotinas :
– Carregador de grupos pares (Even Loader)
– Carregador de grupos impares (Odd Loader)
– Visualizador
• Cada carregador recebe os segmentos dentro de um
grupo em sequência
• Carregador par e impar podem receber
simultaneamente, armazenando dados em buffer local
– Pergunta óbvia: qual o tamanho máximo deste buffer?
• Recebimento de dados sem jitter
Skyscraper Broadcast
Channel 0
1
2
3
4
5
6
7
...
...
...
...
...
...
...
...
• Clientes são agrupados hierarquicamente durante
transmissão (compartilhamento)
– K = 8, tamanhos dos segmentos: 1,2,2,6,6,12,12,12
– W = 12
Latência máxima D1 = T/53  0.02T
Skyscraper Broadcast
• Alocação estática de canais para cada video
• Se popularidade alta: ótimo!!
– Grande economia na largura de banda
• Mas e se popularidade varia com o tempo?
Dynamic Skyscraper
Dynamic Skyscraper Broadcast
• Transmissão “sob demanda”
Channel 0
1
2
3
4
5
6
7
...
...
...
...
...
...
...
...
• skyscraper transmission clusters
- sequências que compartilham o mesmo segmento no canal K
- largura = W (em cada canal)
- cada cluster pode transmitir um arquivo diferente
(sob demanda)
Dynamic Skyscraper Broadcast
• Largura de banda do servidor:
– Total de C canais e N objetos
– Divisão de C canais em N grupos, de K canais cada
– Cada grupo de K canais, uma progressão de tamanhos de
segmentos limitada por W (igual a static skyscraper)
• Diferencial: Alocacão dinâmica dos canais para
diferentes videos
– Cada transmission cluster alocado para um objeto
diferente em resposta às requisições dos clientes
– Todas as sequências no mesmo cluster transmitem
segmentos do mesmo arquivo
Dynamic Skyscraper Broadcast
• Transmission cluster: (exemplo no paper)
– Contém todos os segmentos nos canais 1..k-1 que
compartilham cada segmento transmitido no canal k
• Um novo cluster no canal 1 a cada W slots
– Não usa nenhum período no canal 1..k-1 que faça parte da
primeira sequência de segmentos do próximo cluster
• Alguns segmentos nao pertencem a nenhum
transmission cluster
– Ex: Segmento com tracejado em diagonal no canal 0
• Depende da progressão de tamanhos de segmentos
– Diferentes progressões podem levar a desempenho
melhor: evita desperdício de banda
Dynamic Skyscraper Broadcast
• N grupos de K canais
• Cada grupo, sequência de transmission groups
• Transmission groups em diferentes grupos são persistently
staggered
– Novo transmission group a cada  = W x T1 / N (latência)
– Escalonamento de transmission group : FCFS (FIFO)
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Dynamic Skyscraper Broadcast
• Otimização: temporary channel stealing
– Requisição para objeto Oi na fila a espera de um
segmento livre no primeiro canal do transmission
group alocado para Oi
– Um segmento livre no canal 1 transmission group
alocado para Oj pode ser temporariamente
alocado pra transmitir Oi (atender requisição
pendente)
Dynamic Skyscraper Broadcast
• Nova progressão de tamanhos:
– 1, 2, 2, 4, 4, 8, 8, 16, 16 ….
– Provê transmissão do arquivo inteiro sem jitter
– Clientes recebem no máximo 2 canais simultaneamente
• Clientes que só têm banda suficiente pra receber 1 canal
também são atendidos (1a sequência de segmentos)
– Nao acarreta desperdício de banda
• Todos segmentos são utilizados para transmissão
• Todos os transmission groups têm largura W
– Demanda por espaço no cliente: O(W)
• 1o cliente recebe segmentos sem necessidade de buffer
• Clientes que recebem o último broadcast do 1o segmento,
recebem este segmento W-1 unidades de tempo depois do 1o
cliente e compartilham transmissão do último segmento (canal K)
Dynamic Skyscraper Broadcast
• Progressões alternativas:
– 1, 2, 2, 6, 6, 12, 12, 24, 24 ….
– 1, 2, 2, 6, 6, 12, 12, 36, 36 ….
– Crescimento mais rápido : melhor desempenho
(menor latência)
– Cliente tem que receber no máximo 3 canais
simultaneamente
Compartilhamento de Fluxos: Técnicas
Orientadas às Requisições dos Clientes
• Patching e Hierarchical Stream Merging
• Princípio comum:
– Cliente escuta a mais de um fluxo simultaneamente
– Dados recebidos em um fluxo são visualizados
imediatamente
– Dados recebidos no outro fluxo são armazenados para
visualização futura
• Requer buffer no cliente
• Provê video sob demanda verdadeiro
– Superior a Periodic Broadcast e metodos Skyscraper
Patching
• Motivação:
– Prover video sob demanda verdadeiro
• Latência do cliente tem que ser bem pequena
(ou nula)
– Reduzir demanda por largura de banda do
servidor
• Resolver o problema de gargalo na rede
(network-I/O bottleneck)
• Cada fluxo multicast tem que servir um grande
número de usuários
Patching
• Um fluxo multicast transmite:
– Arquivo inteiro: fluxo regular
– Prefixo: fluxo patch
Dados recebidos
pelos clientes
Cliente c1 recebe fluxo patch
ao mesmo tempo que escuta
fluxo regular.
Depois de t1-t0, os dois clientes
receberam os mesmos dados.
Fluxo patch e finalizado
t0
r0
t1
r1
Tempo
Patching
• Projeto do cliente e do servidor (paper)
• Questão chave:
– Quando iniciar novo fluxo regular?
• Variações
– Greedy Patching:
• Somente quando não houver nenhum ativo
(Agressivo)
– Grace Patching:
• Quando prefixo perdido pelo cliente maior que
buffer local
• Comparação (paper)
Early Merging/
Hierarchical Multicast Stream Merging
• Objetivo: criar merge trees eficientes (minimiza
demanda por largura de banda)
– Cliente escuta, simultaneamente, um fluxo com o
prefixo do arquivo e um fluxo anterior (fluxo alvo)
– Pergunta: Como escolher o fluxo alvo para cada novo
cliente? (multiplos merges possiveis)
• Stream Merging Otimo
– Solucao offline: Programacao dinamica
– Solucao online: computa arvore de custo minimo para os
fluxos ativos a cada chegada de uma nova requisicao
• Complexidade de tempo: cubica no # de requisicoes
• Complexidade de espaco: quadratica
Early Merging
• Intuicao: realizar, primeiramente, os merges que
puderem ser feitos primeiro
• Principios
– Decisao do fluxo alvo para um cliente (ou grupo de clientes)
deve ser feita quando o cliente chega ou quando ele faz um
merge com um outro fluxo.
– Cliente deve escutar o fluxo alvo ate que o merge seja
realizado com sucesso ou ate que ele seja preemptado por
um (grupo de) cliente que chegou depois dele
– Se preemptado, o cliente tem que jogar for a (ignorar)
todos os dados recebidos no seu fluxo alvo corrente,
escolher um novo fluxo alvo e recomecar a armazenar
dados no buffer local, recebidos no novo fluxo alvo.
• Early Merging = Hierarhical Multicast Stream Merging
Variantes do
Hierarchical Multicast Stream Merging
• Early Reachable Merge Target (ERMT):
– Fluxo alvo de um cliente: fluxo mais proximo com o qual
ele pode realizar o merge se nao for preemptado, no
futuro.
– Precisa “simular” evolucao do sistema
• Simple Reachable Merge Target (SRMT):
– Fluxo alvo de um cliente: fluxo mais proximo alcancavel se
cada fluxo correntemente ativo terminar no seu merge
point corrente.
– Ignora novos fluxos criados apos um merge
Variantes do
Hierarchical Multicast Stream Merging
• Closest Target (CT)
– Fluxo alvo: fluxo mais proximo ainda ativo no sistema.
– Politica mais simples
– Surpreendentemente, desempenho muito proximo de
ERMT e otimo
Escalabilidade dos Protocolos
• Limite Inferior para servico imediato
– Processo de chegada Poisson, largura de banda do cliente infinita
– Demanda por largura de banda do servidor : ln (N+1)
• Optimized Grace Patching
– Janela de patching otima
– Demanda por largura de bandado servidor:
B  2N  1 1
– One N = # de chegadas de clientes por playback
• Dynamic Skyscraper
– Partitioned Dynamic Skyscraper
– Demanda por largura de banda do servidor: O(k  ln(N)), 2  k  3
Escalabilidade dos Protocolos
• HMSM
– Calculado via simulacao
– Demanda por largura de banda do servidor: B = 1.62 ln(N/1.62 + 1)
– Muito proximo do otimo
Comentarios Finais
• Bandwidth Skimming:
– HMSM para clientes com largura de banda limitada
• Cliente pode escutar a 1.2 fluxos
• Interatividade:
– Muito pouco explorada
– Skyscraper: aplicacao dificil
– Patching e HMSM:
• Aplicacao direta
• Mas alguns resultados de simulacao com cargas reais
mostram que escalabilidade de HMSM e Patching cai muito
– Novas propostas para Patching e HMSM a caminho