Sistemas Multimédia Distribuídos Computação em Sistemas Distribuídos IST – MEIC 2002/2003 Pedro António M5157

Sistemas Multimédia DistribuídosSistemas Multimédia Distribuídos

Computação em Sistemas DistribuídosIST – MEIC2002/2003

Pedro António M5157

Pedro António M5157 Computação em Sistemas Distribuídos2002/2003

2

ConteúdoConteúdo

Características dos Sistemas MultimédiaAudio, Video, ...

Entrega de dados em Tempo-Real, no momento certo

Gestão da Qualidade de Serviço (QoS)Negociação e Garantias de QoS

Controlo de Admissão

Formato do tráfegoLeaky bucket

Token bucket

Gestão de RecursosEscalonamento de recursos

Adaptação à QoSScaling

Filtragem


3

Palavras ChavePalavras Chave


4

Sistema Multimédia DistribuídoSistema Multimédia Distribuído

WAN

LAN

LAN

Arquitectura típicaProcessamento de streams de dados (audio, video)Transferência da origem (câmara, microfone)Entrega/Consumo no destino (ecrã, coluna)


5

Sistemas MultimédiaSistemas Multimédia

Dados MultimédiaStreams contínuas de dados

Video e Audio digital

Exemplos de Aplicações de Multimédia Distribuídas:

BD de Video

Telefone via Internet

Video-conferências

No entanto, a qualidade do audio e video nem sempre é satisfatória...

Redes actuais best-effortSem garantia de largura de banda ou latência

Viáveis nas redes e sistemas actuais!

1980 1990

remotelogin

networkfile access

high-qualityaudio

interactivevideo

insufficientresources

scarceresources

abundantresources

2000


6

Sistemas MultimédiaSistemas Multimédia

Exemplo de Aplicações Multimédia mais exigentes:Video conferência de larga escala

TV digital

TV interactiva

Sistemas de Vigilância

Exigências:Entrega a tempo das streams Multimédia

Streams de video e audio são consumidos em tempo real

Sistemas Multimédia são sistemas tempo realRealizar tarefas e devolver resultados de acordo com um escalonamento determinado exteriormente

Estão para além das capacidades das redes e tecnologias de SD actuais!


7

Sistemas Tempo-RealSistemas Tempo-Real

Exemplo de Aplicações Tempo-Real actuais:Aviação

Controlo de tráfego aéreo

Controlo de processos de produção

Área dos telefones

Não satisfazer os deadlines pode ser crítico em aplicações Multimédia

Serviço de video-on-demand

Aplicações de conferência

Medicina remota

- Qtd de dados reduzida!- Deadlines complicados são pouco frequentes!- Garantir que os requisitos para o pior caso são cumpridos!


8

Características dos dadosCaracterísticas dos dados

O utilizador tem a percepção de dados contínuos

Fluxo multimédiaTime-based (dados entregues nos momentos exactos)

Bulky (transferência de dados em grande quantidade)

Compressão (reduzir requisitos de largura de banda)10x ou 100x

GIF, TIFF, JPEG, MPEG-1, MPEG-2, MPEG-4

Codec (Coders/Decoders)Hardware (placas de video)

Software (maior flexibilidade)

MPEG (Moving Picture Experts Group)Compressão complexa; Descompressão mais simples


9


CompressãoProblema: Largura de Banda limitada

AudioQualidade de CD : 44100 amostras por segundo com16 bits por amostra, som stereo

44100*16*2 = 1.411 Mbps

Para uma música de 3 minutos: 1.441*180 = 254 Mb = 31.75 MB

VideoPara imagens 320*240 com 24-bit de cor

320*240*24 = 230KB/imagem

15 frames/seg: 15*230KB = 3.456MB

Video de 3 minutos: 3.456*180 = 622MB

FUNDAMENTAL A EXISTÊNCIA DE COMPRESSÃO!


10


Taxa de dados(aproximado)

Sample/frame frequência tamanho

Telefone 64 kbps 8 bits 8000/segSom CD 1.4 Mbps 16 bits 44,000/segTV video Standard (descomprimido)

120 Mbps até 640 x 480pixels x 16 bits

24/seg

TV video Standard (MPEG-1 comprimido)

1.5 Mbps variável 24/seg

HDTV video(descomprimido)

1000–3000 Mbps até 1920 x 1080pixels x 24 bits

24–60/seg

HDTV video(MPEG-2 comprimido)

10–30 Mbps variável 24–60/seg


11

Gestão QoSGestão QoS

Gestão da QoSGestão e atribuição de recursos de modo a oferecer garantias de entrega a tempo

Garantias que os recursos necessários vão ser atribuídos e escalonados nos momentos necessários


12


Gerir atribuição de recursosLargura de banda de rede

Recursos computacionais

Aspectos dinâmicos relacionados com a variação do número de participantes

Considerar diversas actividades paralelas (largura de banda video; conversação; processamento de texto; programa de desenvolvimento)

Requisitos específicos da MultimédiaSincronização do meio de diversas streams

Sincronização externa de video-conferência com outros dados (animações, simulações, whiteboards, documentos partilhados, etc.)


13


Responsabilidade do Gestor da QoSNegociação da QoS

Aplicações requisitam recursos

O gestor QoS concede-os caso estejam disponíveis

Caso contrário, tem de haver nova negociação

Controlo de admissãoAvaliação positiva Recursos reservados (Contrato de Recursos)

Contrato de Recursos: Recursos reservados; Tempo limite; etc.

Alterações notificação do gestor QoSDiminuição das necessidades Libertar Recursos


14

Negociação da QoSNegociação da QoS

Largura de BandaTaxa de fluxo de dados de um componente

LatênciaTempo necessário para a transferência dum elemento de dados individual numa streamDepende do volume de outros dados existentes no sistemas e de outras características de cargaJitter 1ª derivada da latência

Taxa de PerdasIntervalo de tempo no qual se espera que ocorra uma faltaEntregas tardias perdem o seu valorAbandonar os dados quando é impossível entregá-los a tempoAmbientes QoS geridos na perfeição não ocorrem perdasEntregas a tempo de todos os dados por vezes não é possível (reserva de recursos que excedem as necessidades)


15


Estes 3 parâmetros descrevem:As características das streams num determinado ambiente

Stream de video (aplicação de video conferência)LB média = 1.5Mbps; Atraso = 150ms; Perdas aceitáveis = 1 em 100

A capacidade dos recursos em transportar streamsRede

LB = 64Kbps; Algoritmo de queing – Atrasos < 10ms; Perdas < 1 em 106

Especificação dos parâmetros QoS para streamsEstabelecidos explicitamente

LB: 50 Mbps; Atrado: 150 ms; Perdas: < 1 em 103

Estabelecidos implicitamenteA LB da rede resulta da compressão da saída de uma câmara


16


Especificação da Largura de BandaProblemas

Compressão depende do conteúdo

Diferentes padrões de tráfego (caracterizar Burstiness)

Especificar valores máximos, médios e mínimos

BurstinessParâmetro adicional, para além da taxa e do tamanho dos dados

N.º máximo de elementos que podem chegar antes do tempo

Quantidade de espaço do buffer para evitar perdas

Modelo LBAP (linear-bounded arrival processes)N.º máximo de mensagens numa stream durante um intervalo de tempo t = Rt + B (R – taxa; B – burstiness)


17


Especificação da LatênciaStreams

O processamento de uma frame de uma stream deve acompanhar a taxa de chegada de frames

Exceder a capacidade do buffer

Aplicações de video-conferênciaEvitar atrasos inferiores a 150 ms (percepção humana de conversação)

Aplicação de stored videoResposta a comandos 500 ms

JitterVariação no período entre a entrega de 2 frames adjacentes

Manter uma taxa regular sem variações

Resolvido utilizando buffers


18


Especificação da Taxa de PerdasMais difícil de especificar

Resultados probabilisticosBuffer overflow

Mensagens atrasadas

Cálculos baseados em piores casos

Diferenciar aplicações com a mesma LB e a mesma Latência


19


Formação de TráfegoUso de buffers de saída de modo a suavizar o fluxo de dados

A LB fornece uma aproximação do padrão de tráfegoQuanto mais se aproximar da descrição, melhor se consegue tratar o tráfego

Inserir buffer na origem para estabilizar a LB

Token generator


20


Leaky bucketElimina padrão de tráfego bursty

O tamanho do buffer define a quantidade máxima que uma stream pode estar segura sem perder elementos

Taxa de saída inferior a um valor máximo

A LB é delimitada em qualquer intervalo de tempo

Token bucketTolera bursts maiores quando o tráfego está inactivo

Tokens gerados a uma taxa constante

Tokens removidos após o envio

Dados de tamanho S podem ser enviados se existirem S tokens no balde


21


Especificação de fluxo Flow spec – conjunto de parâmetros QoS

Exemplos:RFC 1363 – 11 valores de 16-bit LB, Atraso, Perdas

SRP – burstiness workahead

RFC 1190 – Protocolo ST-II (Internet Stream Protocol)


22


Procedimentos de Negociação da QoSOs componentes de uma stream podem encontrar-se em vários nós (de um Sistema Multimédia Distribuído)

Necessário um gestor de QoS em cada nó

Origem DestinoA origem inicia a negociação enviando um flow spec para o gestor QoS em cada nó

O gestor QoS verifica a disponibilidade dos recursos numa BD

Se existirem outros sistemas envolvidos na aplicação, o flow spec é encaminhado para o próximo nó onde residem os recursos

O flow spec percorre todos os nós até ao destino final

Se o sistema conseguir oferecer a QoS requisitada é enviada uma notificação de volta para a origem

Negociações concorrentes...


23


Procedimentos de Negociação da QoSNecessidades de QoS dinâmicas das aplicações

Em vez de um valor booleano (Sim/Não)Especificar um valor desejado e o pior valor para cada parâmetro QoS

Destinos heterogéneosInapropriado atribuir os mesmos valores de QoSO destino deve receber o melhor QoS possível

Protocolos de Negociação Iniciados pelo EmissorSRP (Scalable Resource Reservation Protocol)ST-II (Internet Stream Protocol)RCAP (Real-time Channel Administration Protocol)

Protocolos de Negociação Iniciados pelo ReceptorRSVP (Resource Reservation Protocol)


24

Controlo de AdmissãoControlo de Admissão

Controlar o acesso a recursos:Evitar o seu carregamentoProteger de pedidos que não conseguem satisfazer

Violação da garantia de QoS negar pedidosUm esquema de Controlo de Admissão é baseado em conhecimento de:

Capacidade total do sistemaCarregamento gerado pela aplicação

Os requisitos de LB especificados pela aplicação:Máxima, Mínima e/ou Média

Recursos com pontos de acesso distribuídos (LAN)Entidade de controlo de admissão centralAlgoritmo de controlo de admissão distribuído


25

Controlo de AdmissãoControlo de Admissão

Reserva de Largura de BandaRequisitar Largura de Banda máxima para uso exclusivo

Utilizado por aplicações que não se conseguem adaptar a diferentes níveis de QoS

Possibilidade de desperdícios de LBPedidos cancelados embora pudessem ser satisfeitos

Multiplexagem estatísticaSub-utilização de recursos... permitir acessos em excesso!

Não é baseado no pior caso Garantias estatísticas ou fracas

No entanto, podem provocar a falha de um serviço de qualidade

Hipótese:Quando uma stream envia uma quantidade grande de dados, existe outra que envia uma quantidade pequena de dados


26

Gestor de QoSGestor de QoS

Aplicação especifica a necessidade QoS ao gestor da QoS

Sim Não

Sim Não

Flow spec

Contrato de Recursos

Controlo de Admissão Negociação QoS

O gestor da Qos avalia as novas necessidades e avalia os recursos disponíveis.

SUFICIENTE?

Reservar recursos requisitados

Permitir a execução da aplicação

A aplicação executa-se com os recursos contratados

Negociar com a aplicação a redução de recursos necessários. ACORDO?

Não permitir que a aplicação se execute

A aplicação notifica ao gestor da QoS do aumento das necessidades


27

Gestão de RecursosGestão de Recursos

Gestão de RecursosRecursos suficientes Desempenho

Disponibilidade dos recursos Escalonamento

Escalonamento de RecursosAtribuição de recursos por prioridade

Capacidade de resposta

Imparcialidade

Deadlines na entrega de dados Multimédia

Algoritmos de escalonamento tempo-real

ClassesStreaming Stored Audio and Video

Streaming Live Audio and Video

Real-Time Interactive Audio and Video


28

Gestão de RecursosGestão de Recursos

Escalonamento de RecursosEscalonamento justo

ImparcialidadePrevenir mau funcionamento (consumo excessivo de LB)Round-robin Aplicado a streams da mesma classe

Mesma LB a cada stream

EDF (Earliest-deadline-first)Um deadline associado a cada um dos items de trabalhoO item com o deadline mais cedo vai primeiroEscalonamento óptimo na atribuição de um único recurso

Escalonamento RM (rate-monotonic)Prioridades de acordo com a taxa da streamEscalonamento óptimo para situações de LB até 69%A restante LB pode ser atribuída a aplicações não tempo-real


29

Adaptação à QoSAdaptação à QoS

Adaptação às alterações do nível de QoSDesempenho

Diversos níveis de qualidade da apresentação

Deitar fora pedaços de informaçãoSom amostras independentes (podem ser identificadas)

VideoMotion JPEG Frames independentes

MPEG Frames dependentes (processo de codificação)

LB insuficiente + Não deitar fora dados = Mais atrasosInaceitável em aplicações interactivas


30


Se a adaptação for realizada no destino da streamA carga em qualquer recurso congestionado no sistema não é reduzida e a sobrecarga persiste

ScalingAdaptar uma stream à LB disponível no sistema antes de entrar num recurso congestionado

Adapta-se melhor quando as streams são amostras

Codificar, comprimir, descomprimir, descodificar


31


Diferentes métodos de scaling e diferentes granularidades (Video)

TemporalReduzir resolução, diminuir n.º de frames por intervalo de tempo

EspacialReduzir o n.º de pixels em cada imagem

FrequênciaAlterar o algoritmo de compressão aplicado à imagem

AmplitudeReduzir a profundidade da cor de cada pixel

Espaço de coresReduzir o n.º de entradas no espaço de cores

Utilizar combinações destes métodos se necessário!


32


Sistema com ScalingProcesso monitor no destinoProcesso scaler na origemFuncionamento

Monitorização de tempos de chegada de mensagens numa stream no processo monitorMensagens atrasadas indicam congestionamento (no monitor)O monitor envia de uma mensagem “scale-down” à origemA origem reduz a LB da streamApós um certo período de tempo, a origem aumenta a scale da streamSe o congestionamento persistir, o monitor detecta o atraso e diminui o scaling da stream

Problemas desta abordagemScale-ups desnecessáriosOscilações no sistema


33


Ilustração

Monitor(Destino)

Scaler(Origem)

Streams

Scale-down

Reduz LB

Aumenta LB(Scale-up)


34


ScalingAs mensagens de “scale-down” são passadas à origem

Assim, todos os destinos ficam com a qualidade degradada

No entanto, alguns destinos não teriam problemas em tratar a stream original

FiltragemOferecer a melhor QoS possível a cada destino aplicando o scaling em cada nó relevante

Conjunto hierárquico de sub-sistemasFiltrar perto da origem Origem

Destino

LB Elevada LB MédiaLB Baixa


35

Caso de Estudo – TigerCaso de Estudo – Tiger

Servidor de ficheiros video – Tiger

Microsoft Research Labs

ObjectivosVideo-on-demand para um número elevado de utilizadores

Filmes pagos

BD de filmes

Disponibilidade e Resposta rápida

Filmes com grande popularidade

QoSFrames a uma taxa constante

Jitter – quantidade disponível de buffer no cliente

Taxa de perdas reduzida


36


Objectivos (Cont.)Escalável e Distribuído

Arquitectura extensível

Suportar até 10 mil clientes em simultâneo

Hardware de custo reduzidoUtilizar PCs existentes

Tolerância a faltasNão notificar degradações após falhas (de um único servidor)

Balanceamento da carga pelos servidores

Transferência de streams com LB elevada de discos para a rede


37


ArquitecturaPCs normais; Placas de rede Ethernet e ATM

Controlador: Pedidos dos clientes; Gestão do escalonamentoControlador

Cub 0 Cub 1 Cub 2 Cub 3 Cub n

ATM switching network

Distribuição de video para os clientes

Start/StopPedidos cliente

Largura de banda de rede baixa

Largura de banda

0 n+1 1 n+2 2 n+3 n+4 n 2n+13


38


ArmazenamentoCarga

Várias streams do mesmo filme

Streams de diversos filmes

Cada filme está distribuído em vários discosA falha de um disco falta de uma sequência de todos os filmes

StripingFilme dividido em blocos (1 segundo; ~500KB)

Conjunto de blocos distribuído por vários discos (7 mil 2 horas)

MirroringDividir cada bloco em várias partes (secundárias)

Estas partes são distribuídas (factor decluster = 4 a 8)Tolerância a faltas


39


Escalonamento distribuídoLista de slots (bloco do filme)

Ler do disco e colocá-lo na rede ATM

1 slot por cada potencial cliente (viewer)

EstadosEndereço do cliente; Ficheiro que está a ler o filme; Posição no ficheiro; Número de sequência; Informação

slot 0viewer 4

slot 1free

slot 2free

slot 3viewer 0

slot 4viewer 3

slot 5viewer 2

slot 6free

slot 7viewer 1

block play time Tblock service

time t

state state state state state

2 1 0


40


QoS garantida pelos protocolos de rede ATMCliente – buffer suficiente para armazenar os 2 primeiros blocos

Um bloco que está a ser mostradoOutro que está a chegar pela rede

Resultados obtidos1º protótipo desenvolvido em 19945 PCs Pentium 133MHz; 48MB RAM; 3 discos 2GB SCSI; rede ATM; Windows NT68 clientes1 falha de um PC (3 discos) taxa de perdas = 0.02%

Expansão possível estimada1000 cubs 30 a 40 mil clientes


41

ReferênciasReferências

Coulouris, Dollimore and Kindberg; “Distributed Systems: Concepts and Design”; Edition 3, © Addison-Wesley 2001

Capítulo 15: Distributed Multimedia Systems

Documents

Sistemas Multimédia Distribuídos Computação em Sistemas Distribuídos IST – MEIC 2002/2003 Pedro António M5157