SD_aula_07_Multicast

Prévia do material em texto

Universidade Federal de Ouro Preto
Instituto de Ciências Exatas e Aplicadas - ICEA
Professor: Theo Lins
Disciplina: SD
Comunicação
1
Capítulo 4
Comunicação Multicast – Camada de Rede
Diferente da comunicação broadcast, onde todos os nós de uma rede 
recebem um pacote, na comunicação multicast o pacote é entregue a 
apenas um subgrupo de nós na rede
Na Internet, o identificador único que representa um grupo de 
destinatários é um grupo multicast classe D
 Como endereçar os pacotes dentro do subgrupo? 
 Como fazer o gerenciamento dos nós do subgrupo? 
 Como os nós da rede interagem para entregar um datagrama multicast a todos os 
membros do grupo?
Comunicação Multicast – Camada de Rede
Todo o gerenciamento é feito pelo Protocolo de 
Gerenciamento de Grupo da Internet (IGMP)
 Opera entre o host e o roteador diretamente conectado a 
ele
Comunicação Multicast – Camada de Rede
O IGMP provê os meios para que um host informe ao roteador 
conectado a ele que uma aplicação que está funcionando no host quer 
se juntar a um grupo multicast
Dado que o escopo de interação do IGMP é limitado a um host e seu 
roteador conectado, um outro protocolo deve ser usado para 
coordenar os roteadores multicast por toda a Internet 
(PIM,DVMRP,MOSPF)
 Investimento em infra-estrutura, gerenciamento
 ISPs se mostravam relutantes em suportar multicasting
Comunicação Multicast – Camada de Aplicação
 Já que o multicast na camada de rede é extremamente custoso em 
questões de investimento, por que não transferir esta funcionalidade 
para a camada de aplicação?
Comunicação Multicast – Camada de Aplicação
 
Com o advento das aplicações P2P:
 Novas técnicas de gerenciamento de redes de sobreposição (overlays) foram 
propostas
 Juntamente com as técnicas de gerenciamento, diversos algoritmos para difusão 
das mensagens (ou conteúdo) também foram propostos 
Comunicação Multicast – Camada de Aplicação
 Idéia Básica:
 Nós se organizam em uma rede de sobreposição, usada para disseminar 
informações para os seus membros
 Os roteadores da rede física NÃO fazem parte do overlay de difusão das 
informações
 Conexões entre nós no overlay podem cruzar vários enlaces físicos!
Comunicação Multicast – Camada de Aplicação
Questões principais:
 
 Como construir o overlay para obter robustez, diminuir o atraso de difusão 
(explorando, por exemplo características dos peers ou de localização geográfica) 
 Como difundir o conteúdo de maneira eficiente
Comunicação Multicast – Overlay
 
 
 
Estruturas possíveis:
Árvore: Um único caminho entre cada par de nós.
 Reorganização da estrutura a cada entrada/saída de um nó
 Baixa resiliência: a saída de um nó desconecta outros nós
Mesh: Neste tipo de orvelay, os nós se organizam em uma malha, com 
a existência (com grande probabilidade), de vários caminhos entre 
pares de nós
 Alta resiliência
Comunicação Multicast – Overlay
 
 
 
Árvore
Construir uma árvore qualquer não é uma tarefa crítica!
Construir uma árvore eficiente é uma tarefa crítica!
Problema: roteamento lógico versus roteamento físico
Comunicação Multicast – Overlay
 
 
 
Qualidade da Árvore
 Estresse de enlace: Quantas vezes uma mensagem atravessa o mesmo enlace? 
Exemplo: mensagem de A a D atravessa Ra,Rb duas vezes
 Penalidade de atraso relativo: Razão entre o atraso entre dois nós na sobreposição 
e o atraso que esses dois nós sofreriam na rede subjacente. Exemplo: mensagens 
de B a C possuem um atraso de 71 no overlay, mas de 47 no nível de rede, que 
gera uma penalidade de 1.51
 Custo da árvore: parâmetro de medição global, relacionado com a minimização dos 
custos agregados de enlaces. Exemplo: atraso entre dois nós finais → spanning 
tree
Comunicação Multicast – Overlay
 
 
 
Mesh
 Diferentes grafos podem ser usados
 Grafos aleatórios: Nenhum tipo de informação é usado para contruir topologias 
mais eficientes
 Grafos “com inteligência”: Neste caso, podemos considerar informações como 
banda dos nós ou localização geográfica (através do RTT, por exemplo) para 
construção da topologia
Comunicação Multicast – Overlay
 
 
 
 Mesh
 Grafos aleatórios também sofre de perda de desempenho (roteamento lógico 
versus roteamento físico)
 Usuário: maior atraso para entrega do conteúdo
 ISP: envio desnecessário de conteúdo via outros ISPs
Resultado 2: Construção do Overlay (Lobb et al, 2009)
Problema: Contruir o overlay de difusão da informação de maneira a 
explorar os peers com grande banda de upload, diminuindo o tempo 
para difusão da informação
 Idéia Básica: Peers com alta banda são “empurrados” para perto da 
fonte, criando um “backbone” de difusão da informação
Característica importante: A banda de upload dos peers é estimada 
indiretamente, considerando o total de chunks enviados até o instante 
de tempo atual
Adaptando o Overlay... (I)
O algoritmo é realizado independentemente por cada peer p
A cada x chunks, o peer p ajusta a sua vizinhança aumentando-a ou 
diminuindo-a.
A decisão de crescimento ou diminuição é baseada na fração dos links 
de saída utilizados
Adaptando o Overlay...(II)
O que fazer?
1) Se, durante x, p enviou pelo menos um chunk a um grande número 
de vizinhos, assumimos que p pode “alimentar” mais vizinhos e uma 
fração de novos peers, vizinhos dos vizinhos, são acrescentados a 
vizinhança de p
2) Caso contrário, se p enviou chunks a uma fração pequena de 
vizinhos, a vizinhança de p é diminuída
Simulação
1) O overlay é formado por 10,000 peers, com quatro classes 
diferentes
 Classe 1 – 10% - 5Mbs +- 10%
 Classe 2 – 40% - 1Mbs +- 10%
 Classe 3 – 40% - 0.5Mbs +- 10%
 Classe 4 – 20% - 0Mbs
2) Fonte é um peer especial, com 5.5Mbs de banda de upload. Um 
total de 10.000 chunks é “empurrado” através do overlay
Questões
Já que o algoritmo é adaptativo, ele converge?
Como os peers se conectam? Existe preferência entre os peers, para a 
construção da vizinhança?
Qual o desempenho comparado com a topologia aleatória?
Convergência
Vizinhos em cada Classe
Comunicação Multicast – Difusão de Dados
 
 
 
Protocolos Epidêmicos
 Propagar as informações rapidamente entre um grande conjunto de nós usando 
somente informações locais
 Não existe nenhum componente centralizado para gerenciar a difusão da 
informação
Comunicação Multicast – Difusão de Dados
 
 
 
Questões importantes:
 Qual o conteúdo a ser enviado?
 Qual nó escolher para entregar o conteúdo
Resultado 1: Algoritmos de Escalonamento (Silva et al, 2008)
O Sistema:
Peers possuem banda de download infinita e banda de upload finita
Cada peer gerencia:
 Uma lista de vizinhos, para troca de chunks
 Uma janela de chunks que podem ser distribuídos aos vizinhos
Cada peer decide qual o chunk e qual o vizinho baseado somente em 
informações locais
Objetivos
Problema: Encontrar estratégias para disseminar chunks e selecionar 
os vizinhos que tornem o sistema eficiente (baixo retardo, baixa 
perdas)
 Ideia Básica: Dado que a banda de upload é limitada, a capacidade de 
upload determina o desempenho do sistema.
 
Explorar, da melhor maneira possível, a banda de upoload dos peers
Bandwidth-Aware
Explorar a banda de upload da melhor maneira possível: Fazer com 
que os peers contribuem com a difusão do conteúdo baseado na 
banda de upload de cada um.
Seleção de um peer antes do envio de um chunk: enviar o chunk ao 
vizinho com maior taxa de upload
Descrição do Sistema
(1) Chunks possuem tamanho constante L
(2) Peer p tem banda de upload u(p)
(3) Cada peer possui uma lista dos vizinhos e conhece a banda de 
upload de cada um
(4) Cada peer possui uma pequena janela deslizante w
(5) Cada peer sabe o conteúdo da janela dos vizinhos
Descrição do Sistema (cont.)
(6) A topologia é descrita por um grafo aleatório, onde as arestas são 
definidas aleatoriamente
(7) Cada peerseleciona k vizinhos aleatórios
(8) Churning não é levado em consideração
Bandwidth-Aware
Cada peer decide localmente
 O chunk a ser distribuído
 O vizinho que receberá o chunk
Escolha do chunk
 O chunk escolhido é o último gerado pela fonte (maior identificador) – latest chunk 
first proposto por Fabien et al.
Escolha do vizinho
 Bandwidth-aware
Bandwidth-Aware (cont.)
Qual a estratégia?
 Selecionar o peer com a probabilidade proporcional a sua banda de upload
Bandwidth-aware tende entregar o chunk aos peers que contribuem 
mais significantemente ao processo de difusão
 Chunk j é enviado ao peer p somente se este não o tem
 Se o chunk j não pode ser enviado, o próximo chunk na janela é escolhido
Simulação
(1) Simulação dividida em duas fases: geração da topologia e disseminação 
dos chunks
(2) Chunks são gerados a uma taxa de 1 chunk/s com tamanho de L = 0.3 Mb
(3) Upload da fonte de informação = 1 Mbps
(4) Peers são divididos em 3 classes
 P1 com taxa de upload [0.18,0.22] Mbps
 P2 com taxa de upload [0.3,0.4] Mbps
 P3 com taxa de upload [3,4] Mbps
Simulação (cont.)
 
Medidas de desempenho
 Retardo: Intervalo de tempo entre a geração do chunk na fonte e a chegada do 
mesmo no peer; valor médio e a distribuição do 99-ésimo percentile para todos os 
peers
Perdas: Porcentagem de chunks perdidos
Melhoria do valor médio do 99-ésimo percentile e a porcentagem de 
perdas
Bandwidth-Aware vs Aleatório
Objetivo: Comparar Bandwidth-Aware com a seleção aleatória de um 
peer
Overlay com 1,000 peers
 7% em P3 – alta banda de upload
 27% em P1 – baixa banda de upload
25 topologias diferentes, escolhidas aleatoriamente
200 chunks são distribuídos e w = 5
Bandwidth-Aware vs Aleatório (cont.)
35
Por que o desempenho de B têm uma grande melhoria?
 Na estrutura da topologia, peers com maior banda de upload são vizinhos da fonte 
ou estão a poucos passos.
Clusterização virtual!!