Comunicação Multicast: Fundamentos e Aplicações

Prévia do material em texto

Comunicação Multicast
por Marinho Barcellospor Marinho Barcellos
PIP/CA – PIP/CA – Programa Interdisciplinar de Pós-graduação em Computação AplicadaPrograma Interdisciplinar de Pós-graduação em Computação Aplicada
UNISINOS - São Leopoldo, RSUNISINOS - São Leopoldo, RS
Seminário de Capacitação Interna - RNPSeminário de Capacitação Interna - RNP
Dezembro de 2000Dezembro de 2000
Marinho Barcellos - PIP/CA - UNISINOS 2RNP2000
Sumário
• Fundamentos sobre IP Multicast
• IGMP - Internet Group Management Protocol
• Roteamento Multicast
• Mbone
• Tópicos avançados
• Comentários Finais
Fundamentos sobre IP Multicast
Marinho Barcellos - PIP/CA - UNISINOS 4RNP2000
Métodos de Envio
• Unicast
• Broadcast
• Multicast
• Anycast
Marinho Barcellos - PIP/CA - UNISINOS 5RNP2000
Vantagens de Multicast
• Broadcast desperdiça banda e é limitado a uma subrede
• Unicast envia dados várias vezes
• Multicast envia apenas uma vez
• Dados são eficientemente distribuídos por roteadores
• Árvore de distribuição multicast (MDT)
Marinho Barcellos - PIP/CA - UNISINOS 6RNP2000
Exemplo de Uso de Banda
Clientes
Ba
nd
a 
(M
bp
s)
14
2
1 100
servidor de vídeo
transmite stream de 128 kbps
unic
ast
multicast
Marinho Barcellos - PIP/CA - UNISINOS 7RNP2000
Limitações de IP Multicast
• Não suporta TCP, apenas UDP
• Entrega de pacotes não é confiável
• Duplicação de pacotes
• Congestionamento da rede (ausência de controle)
• É possível assinar grupo com taxa de transmissão
superior à capacidade existente
Marinho Barcellos - PIP/CA - UNISINOS 8RNP2000
Aplicações de Multicast
• Teleconferência multimídia (vários)
• Distribuição de dados (distribuição de software)
• Distribuição de dados em tempo real (mercado de ações)
• Jogos e simulações distribuídas
Marinho Barcellos - PIP/CA - UNISINOS 9RNP2000
IP Multicast
• Resultado de tese de doutorado de S. Deering, 1991
§ host membership protocol – IGMP
§ protocolo de roteamento que originou DVMRP
• Princípios
§ escalabilidade
§ separação entre controle de grupo e roteamento
• IP Multicast é descrito através de uma série de RFCs
§ RFC966, RFC988, RFC1054, RFC1075, RFC1112...
Marinho Barcellos - PIP/CA - UNISINOS 10RNP2000
Endereçamento IP Multicast
• Endereços unicast x multicast
• Endereços multicast (antiga classe D)
§ 1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx
§ 224.0.0.0 a 239.255.255.255
• Endereços reservados pela IANA
§ 224.0.0.0 a 224.0.0.255 = locais
§ 239.0.0.0 a 239.255.255.255 = escopo administrativo
§ 224.0.1.x = outros
Marinho Barcellos - PIP/CA - UNISINOS 11RNP2000
Endereçamento IP Multicast
• Endereços locais (224.0.0.x)
§ .1: all-hosts
§ .2: all multicast routers
§ .4: all DVMRP routers
§ .5: all OSPF routers
§ .6: OSPF designated routers
§ .13: all PIM routers
§ .15: all CBT routers
Marinho Barcellos - PIP/CA - UNISINOS 12RNP2000
Endereçamento Multicast MAC
• Endereços MAC freqüentemente incluem multicast
• Mapeamento entre endereços MAC multicast e IP
multicast
• Ethernet: 23 bits endereçamento MAC multicast (224/2)
• Mapeamento de 32 bits para 23: 25
<< Sumário <<
IGMP
Internet Group Management Protocol
Marinho Barcellos - PIP/CA - UNISINOS 15RNP2000
IGMP: Internet Group Management Protocol
• Protocolo para gerência de grupo
• Histórico
§ derivado do “Host Membership Protocol”
§ definido na RFC1112
§ aumentado mais tarde com novos protocolos
• Existem 3 versões de IGMP
§ IGMPv1 ainda é comum (Win95)
§ IGMPv2 é o padrão atual
§ IGMPv3 ainda é draft
Marinho Barcellos - PIP/CA - UNISINOS 16RNP2000
IGMP: Internet Group Management Protocol
• Roteador usa IGMP para controlar quais grupos estão
ativos na subrede
• Subrede deve possuir pelo menos 1 host interessado
• Um host interessado possui pelo menos 1 processo que
assinou grupo
Marinho Barcellos - PIP/CA - UNISINOS 17RNP2000
IGMP: Internet Group Management Protocol
• Mensagens do IGMP são transportadas em datagramas IP
• Mensagens locais (TTL=1)
• Formato do pacote (v1)
§ versão: 1
§ tipo: Membership Query, Membership Report
§ checksum
§ endereço de grupo
• Roteador designado: IGMP e encaminhamento à subrede
Marinho Barcellos - PIP/CA - UNISINOS 18RNP2000
IGMP: modelo query-response
• Determinar quais grupos estão sendo assinados
• Roteador designado envia Query periodicamente
• Host assinante envia um Report para cada grupo
assinado
• Roteador designado determina quais grupos estão sendo
assinados
Marinho Barcellos - PIP/CA - UNISINOS 19RNP2000
IGMP: supressão com atraso aleatório
• Implosão com muitos grupos ou muitos membros
• Mecanismo de supressão com atraso aleatório
• Basta o primeiro report de um host
Marinho Barcellos - PIP/CA - UNISINOS 20RNP2000
IGMP: entrada em grupo com join
• Problema na latência de entrada em grupo
• Host envia Report (join) quando grupo é assinado
• Roteador recebe Report e inclui grupo na lista de ativos
Marinho Barcellos - PIP/CA - UNISINOS 21RNP2000
IGMP: saída silenciosa
• Saída silenciosa quando host sai do grupo
• Roteadores mantém um contador para cada grupo
• Em 3 minutos, grupo é eliminado
• Enquanto isso, tráfego de grupo continua a ser
encaminhado
Marinho Barcellos - PIP/CA - UNISINOS 22RNP2000
Ilustração dos Intervalos no IGMPv1
latência de saída (3min)
Query interval
(60seg)
Query interval
(60seg)
Query interval
(60seg)
intervalo aleatório de resposta (10seg)
host deixa grupo
Marinho Barcellos - PIP/CA - UNISINOS 23RNP2000
IGMP versão 2
• RFC2236, IETF, 1997
• Correção de problemas detectados no IGMPv1
• Compatível com a primeira versão (interoperabilidade?)
• Principais modificações:
§ Leave
§ Query específica para um grupo
• Query interval alterado de 60seg para 125seg
Marinho Barcellos - PIP/CA - UNISINOS 24RNP2000
IGMPv2: saída de grupo otimizada
• Host envia Leave <grupo> para todos roteadores
• Roteador não sabe se este foi o último host no grupo
• Roteador envia Query <grupo> para o endereço <grupo>
com latência máxima de 1seg
• Caso ninguém responda
§ repete e em 2seg assume que não há mais membros
§ pára de encaminhar pacotes endereçados a <grupo>
• Latência de saída inferior a 3seg
Marinho Barcellos - PIP/CA - UNISINOS 25RNP2000
IGMP versão 3
• Incompleto
• Host pode selecionar tráfego específico por fonte
• Permite assinar um grupo mas restringir transmissor(es)
dentro do grupo
• Duas novas mensagens:
§ Inclusion Group-Source Report: acrescenta uma fonte
§ Exclusion Group-Source Report: exclui uma fonte
<< Sumário <<
>> mais informações sobre IGMPv2 >>
Marinho Barcellos - PIP/CA - UNISINOS 27RNP2000
IGMPv2: formato do pacote
• Formato do pacote (v2)
§ tipo/versão (0-7): Membership General Query, Membership Report v1,
Membership Group-Specific Query, Membership Report v2, Leave
Group
§ tempo máximo de resposta (8-15): tempo máximo de atraso aleatório,
em centenas de milisegundos
§ checksum (15-31)
§ endereço de grupo (32-63): endereço (grupo)
• Tempo máximo de resposta é usado para ajustar nível de
respostas
§ maior o valor, mais espalhadas tendem a ficar as respostas
§ crítico quando há muitos membros em uma rede
Marinho Barcellos - PIP/CA - UNISINOS 28RNP2000
IGMPv2: eleição de “perguntador”
• O roteador com menor IP deve ser eleito como o
“perguntador” (querier)
• Roteadores IGMPv2 enviam mensagem General Query
para “All-multicast-systems-group” (224.0.0.1)
• Roteador que recebe essa mensagem compara IP da
origem com o seu próprio
• Roteadores mantém um temporizador que é resetado a
cada General Query recebida (cada 125seg)
• Se o roteador eleitomorre, 250seg após um novo é eleito
<< Sumário <<
Roteamento Multicast
Marinho Barcellos - PIP/CA - UNISINOS 31RNP2000
Classes de Protocolos de Roteamento Unicast
protocolos de roteamento
estáticos dinâmicos
centralizados distribuídos
vetor de distâncias estado de link
Marinho Barcellos - PIP/CA - UNISINOS 32RNP2000
Classes de Protocolos de Roteamento Multicast
• Modelo Push x Modelo Pull
§ push: empurra e causa rejeição
§ pull: puxa tráfego multicast
protocolos de 
roteamento multicast
modo denso
(árvore baseada na fonte)
modo esparso
(árvore compartilhada, pull)
vetor de distâncias estado de link
Marinho Barcellos - PIP/CA - UNISINOS 33RNP2000
• Uma árvore para cada fonte Si que transmite ao grupo G
• Fonte S representa raiz da árvore multicast
• Cada pacote atravessa um link apenas uma vez
• Roteadores formam 1 árvore para cada par (Si, G)
• Animacoes\roteamento_arvore_baseada_fonte.swf
Árvore Multicast Baseada na Fonte
Marinho Barcellos - PIP/CA - UNISINOS 34RNP2000
Árvore Multicast Compartilhada
• Há apenas 1 árvore para todo o grupo
• Unidirecional: raiz é o “núcleo” do grupo multicast
§ todos os pacotes são enviados ao núcleo e após distribuídos
• Bidirecional: não há uma raiz
• Independe de quantos remetentes no grupo
• Animacoes\roteamento_arvore_compartilhada.swf
• Animacoes\roteamento_arvore_compartilhada-dois.swf
Marinho Barcellos - PIP/CA - UNISINOS 35RNP2000
Dois Caminhos...
>> determinação da árvore multicast:
menor caminho x custo global mínimo >>
...ou pular direto para...
>> principais protocolos de roteamento multicast >>
Determinação da Árvore Multicast
Qual o critério para determinar uma árvore multicast?
Marinho Barcellos - PIP/CA - UNISINOS 37RNP2000
Árvore de Caminho Mais Curto
• Objetivo: minimizar, individualmente, distância entre fonte
e cada receptor
• Equivalente a encontrar caminho mais curto para cada
par fonte-receptor
• Dois algoritmos:
§ Bellman-Ford
§ Dijkstra
Marinho Barcellos - PIP/CA - UNISINOS 38RNP2000
Árvore de Caminho Mais Curto
FON
RT1
RT3
RT5
RT6
RT9
RT11
R2
R3
R4
RT4
RT7
RT10 R6
R7
R5
R1
Rn
FON
RTn
Remetente
Receptor
Roteador
RT2
RT8
Marinho Barcellos - PIP/CA - UNISINOS 39RNP2000
Árvore de Custo Global Mínimo
• Objetivo: minimizar o custo total da árvore multicast
• Prioriza compartilhamento de caminhos
• Dois tipos de algoritmos
§ MST – Minimum Spanning Tree (árvore de expansão mínima)
§ Árvore de Steiner – problema NP-completo se links podem ter pesos
idênticos
Marinho Barcellos - PIP/CA - UNISINOS 40RNP2000
Árvore de Custo Global Mínimo
FON
RT1
RT3
RT5
RT6
RT9
RT11
R2
R3
R4
RT4
RT7
RT10 R6
R7
R5
RT2
RT8
R1
Rn
FON
RTn
Remetente
Receptor
Roteador
Marinho Barcellos - PIP/CA - UNISINOS 41RNP2000
Comparação entre Abordagens
Caminho mais longo (latência): 
Custo global (largura de banda): 
5
18
Caminho mais longo (latência): 
Custo global (largura de banda): 
7
15
FON
RT1
RT3
RT5
RT6
RT9
RT11
R2
R3
R4
RT4
RT7
RT10 R6
R7
R5
R1 RT2
RT8
FON
RT1
RT3
RT5
RT6
RT9
RT11
R2
R3
R4
RT4
RT7
RT10 R6
R7
R5
RT2
RT8
R1
Marinho Barcellos - PIP/CA - UNISINOS 42RNP2000
Principais Protocolos de Roteamento Multicast
• RPF - Reverse Path Forwarding
• DVMRP - Distance Vector Multicast Routing Protocol
• MOSPF - Multicast Open Shortest-Path First
• PIM/DM - Protocol-Independent Multicast/Dense Mode
• PIM/SM - Protocol-Independent Multicast/Sparse Mode
• CBT - Core-Based Trees
• Roteamento Multicast Inter-domínio
RPF: Reverse Path Forwarding
Marinho Barcellos - PIP/CA - UNISINOS 44RNP2000
RPF: Reverse Path Forwarding
• Utilizado bem no início, não é multicast, e sim broadcast
• Broadcast truncado
• Vantagem principal: uso da infra-estrutura unicast
• Controle de tráfego unicamente baseado em TTLs
Marinho Barcellos - PIP/CA - UNISINOS 45RNP2000
RPF: Reverse Path Forwarding
• Como evitar laços eternos na propagação de pacotes?
• Roteadores selecionam e descartam pacotes que não
vem do menor caminho até a fonte
Marinho Barcellos - PIP/CA - UNISINOS 46RNP2000
Exemplo de RPF: (roteador RT6)
FON
RT1
RT3
RT5
RT6
RT9
RT11
R2
R3
R4
RT4
RT7
RT10 R6
R7
R5
RT2
RT8
R1
Rn
FON
RTn
Fonte
Receptor
Roteador
Marinho Barcellos - PIP/CA - UNISINOS 47RNP2000
INUNDAÇÃO
Exemplo de RPF: (roteador RT6)
FON
RT1
RT3
RT5
RT6 R4
RT4
Rn
FON
RTn
subrede
fonte
subrede
destino
Roteador
DESCARTE
0eth0R4
3RT4FON
DISTNEXTDEST
Tabela de Roteamento
unicast em RT6
Pacote originário de FON chega via RT5
mas deveria ser RT4
Pacote originário de FON chega via RT4
corresponde ao menor caminho para FON
<< Protocolos de Roteamento <<
DVMRP: Distance Vector Multicast
Routing Protocol
Marinho Barcellos - PIP/CA - UNISINOS 50RNP2000
DVMRP: Distance Vector Multicast Routing Protocol
• Protocolo baseado em “vetor de distâncias”, similar à RIP
• Protocolo do tipo “denso”
• Protocolo do tipo “Flood-and-Prune”
• Primeiro protocolo de roteamento multicast, e mais
largamente suportado
• Infinito = 32 hops
Marinho Barcellos - PIP/CA - UNISINOS 51RNP2000
DVMRP: determinação de vizinhos
• Periodicamente, roteadores DVMRP verificam quais são
seus vizinhos
• Mensagem de sonda com lista de vizinhos enviada para
224.0.0.4
• Roteadores que recebem mensagem atualizam suas listas
• No próximo intervalo, roteador envia nova mensagem de
sonda com lista atualizada
Marinho Barcellos - PIP/CA - UNISINOS 52RNP2000
DVMRP: tabela de roteamento
• Informações de rota: Route Report periódicos
• Ajudam a montar na tabela uma árvore de broadcast
truncado
• Tabela é separada de unicast e usada para
§ construção de árvores de distribuição baseadas na fonte
§ encaminhamento de pacotes (verificação de RPF)
Marinho Barcellos - PIP/CA - UNISINOS 53RNP2000
DVMRP: formação da árvore com Prune
• Quando da primeira transmissão em uma rede fonte
• Inundação, adicionando entradas (Si, G) em roteadores
• Redução de tráfego baseado em processo de poda
• Processo é recursivo em direção à raiz
• Informação de poda expira, com nova inundação
Marinho Barcellos - PIP/CA - UNISINOS 54RNP2000
DVMRP: formação da árvore com Graft
• Caso subrede que foi “podada” de árvore (Si, G) passa a
assinar o grupo G
• Subrede precisa ser recolocada na árvore
• Evita atraso de minutos até nova inundação
• Roteadores enviam mensagem de Graft corrente acima
• Transmissão confiável (roteador retorna Graft-Ack)
Marinho Barcellos - PIP/CA - UNISINOS 55RNP2000
DVMRP: escalabilidade
• DVMRP utilizado na Mbone e intra-domínio
• Hop count máximo de 31
§ uso de túneis poderia aliviar
• Protocolo baseado em vetor de distâncias
§ mecanismo periódico de atualização de rota (60seg)
• DVMRP não é recomendado nem para intra-domínio
<< Protocolos de Roteamento <<
MOSPF: Multicast Open Shortest
Path First
Marinho Barcellos - PIP/CA - UNISINOS 58RNP2000
MOSPF: Multicast Open Shortest Path First
• Extensão do protocolo de roteamento unicast OSPF
• Protocolo baseado em estado de link (“link-state”)
• OSPFv2 – RFC2328
§ link-state: roteadores enviam LSAs (link-state announcements)
§ hierarquia de rede de dois níveis
§ área 0 (backbone) interliga todas as sub-áreas
§ roteadores inundam nas sub-áreas informações de estado de link
§ cada roteador mantém uma base de dados com um mapada rede
§ tabelas de roteamento são computadas com algoritmo de Dijkstra
§ roteadores especiais de borda conectam sub-áreas à área 0
Marinho Barcellos - PIP/CA - UNISINOS 59RNP2000
MOSPF: Multicast Open Shortest Path First
• RFC1584, “Multicast Extensions to OSPF”
• Roteamento multicast intra- e inter-área, além de inter-SA
• Group Membership Link-State Announcement
• Apenas roteadores designados geram LSAs
• Roteadores recebem LSAs sobre membros de grupos
Marinho Barcellos - PIP/CA - UNISINOS 60RNP2000
MOSPF: Algoritmo de Dijkstra
• Mesmo Algoritmo de Dijkstra (unicast), com raiz diferente
• Cálculo feito sob demanda, ao primeiro pacote, ou
§ quando a topologia muda, para todos os pares (Si, G), ou
§ quando a composição de grupo muda, apenas para (Si, G)
• Para um cada par (Si, G), um roteador
§ executa uma vez o algoritmo de Dijkstra para...
§ gerar uma árvore de expansão de menor caminho enraizada em Si
§ ...e utiliza tal árvore para encaminhamento de pacotes em suas
interfaces
Marinho Barcellos - PIP/CA - UNISINOS 61RNP2000
MOSPF: Roteamento Inter-área
• Inter-area multicast forwarder (ou MABR, multicast area
border routers)
• MABRs sabem quais grupos estão sendo assinados em
cada sub-área
• MABR resume informações de grupo e inunda nível 0
• MABR encaminha pacotes multicast entre sub-áreas
• MABR é incluído (via wildcard) em todas as árvores
geradas na sub-área
Marinho Barcellos - PIP/CA - UNISINOS 62RNP2000
MGMG MG MG
MOSPF: Roteamento Inter-área
MABR1 MABR2
ÁREA 1 ÁREA 2
ÁREA 0
backbone area
(S,G)
Marinho Barcellos - PIP/CA - UNISINOS 63RNP2000
MGMG MG MG
MOSPF: Roteamento Inter-área
MABR1 MABR2
ÁREA 1 ÁREA 2
ÁREA 0
backbone area
(S,G)
MASBR
external AS
(S, G)
Marinho Barcellos - PIP/CA - UNISINOS 64RNP2000
MOSPF: escalabilidade
• Vantagem de MOSPF: reage rapidamente
• MOSPF é utilizado em diversas redes hoje em dia
• Escalabilidade bastante limitada
§ demanda de processamento cresce muito com número de pares (S, G)
§ redes dinâmicas, ou com grupos dinâmicos, sobrecarregam roteadores
<< Protocolos de Roteamento <<
PIM/DM:
Protocol Independent Multicast
Dense Mode
Marinho Barcellos - PIP/CA - UNISINOS 67RNP2000
PIM: Protocol Independent Multicast
• PIM é independente de roteamento unicast IP
§ pode operar independentemente de protocolo de roteamento unicast
§ não emprega uma tabela de roteamento própria
§ utiliza tabela de roteamento unicast existente
Marinho Barcellos - PIP/CA - UNISINOS 68RNP2000
PIM/DM: modo denso
• Usa “flood-and-prune”, tal como DVMRP
• Diferença para DVMRP: inunda apenas vizinhos PIM
• Bom para redes com uma alta densidade de membros
• Descoberta de vizinhos com mensagens “hello”
§ cada 30seg envia para 224.0.0.2 (all-routers)
Marinho Barcellos - PIP/CA - UNISINOS 69RNP2000
PIM/DM: poda de ramos (pruning)
• Pacote de prune é enviado sempre que
§ tráfego chega em interface não RPF (exceto meio compartilhado)
§ roteador folha e nenhum receptor diretamente conectado
§ todos roteadores filhos enviaram prune
• Mecanismo PIM/DM asserts
§ quando há 2+ roteadores encaminhando pacotes em uma LAN
§ roteadores disputam quem deve encaminhar
§ perdedores fazem prune na interface
Marinho Barcellos - PIP/CA - UNISINOS 70RNP2000
PIM/DM: escalabilidade
• É superior ao DVMRP porque
§ não utiliza tabelas próprias de roteamento para fazer verificação RPF
§ não troca atualização de rota periodicamente
• Entretanto,
§ quantidade de estado: uma entrada (Si, G) para cada par fonte/grupo
§ mantém comportamento flood-and-prune
• Avanço recente proposto pelo IETF: State-Refresh
§ mensagens enviadas por roteadores fonte
§ refresca estado de prune nas interfaces (se houve tráfego em 3 min)
§ diminui comportamento flood-and-prune
<< Protocolos de Roteamento <<
PIM/SM:
Protocol Independent Multicast
Sparse Mode
Marinho Barcellos - PIP/CA - UNISINOS 73RNP2000
PIM/SM: modo esparso
• Modo esparso: receptores dispersos e modelo pull
• Motivação: construir árvore de distribuição multicast sem
o overhead de DVMRP ou PIM/DM (inundações)
• Continua necessário distribuir pacotes de maneira
eficiente através de uma árvore de distribuição multicast
Marinho Barcellos - PIP/CA - UNISINOS 74RNP2000
PIM/SM: modelo de join explícito
• Receptor envia mensagem de join para o nó raiz da árvore
(RP)
• Mensagem vai configurando, hop a hop, roteadores para
futuro encaminhamento de tráfego de grupo
• Mensagens de Prune são enviadas quando sai do grupo
• Diferença para DVMRP são as mensagens explícitas de
Join e Prune
Marinho Barcellos - PIP/CA - UNISINOS 75RNP2000
PIM/SM: join em árvore compartilhada
RECEPTOR 1
Grupo G
ROTA ROTC ROTRP
ROTC ROTE
ROTD
IGMP report
(*,G) Join
RECEPTOR 2
Grupo G
IGMP report
(*,G) Join
Árvore resultante
Marinho Barcellos - PIP/CA - UNISINOS 76RNP2000
PIM/SM: prune em árvore compartilhada
RECEPTOR 1
Grupo G
ROTA ROTC ROTRP
ROTC ROTE
ROTD
RECEPTOR 2
Grupo G
IGMP Leave G
(*,G) Prune
IGMP Query G
Árvore resultante
Marinho Barcellos - PIP/CA - UNISINOS 77RNP2000
PIM/SM: join em árvore baseada na fonte
RECEPTOR 1
Grupo G
ROTA ROTC ROTRP
ROTC ROTE
ROTD
(S1,G) Join
Árvore resultante
FONTE S1
Grupo G
IGMP report
(S1,G) Join
árvore de caminho mais curto
Marinho Barcellos - PIP/CA - UNISINOS 78RNP2000
PIM/SM: refrescamento de estado
• Estado nos roteadores é refrescado periodicamente
(1min)
• Roteador envia mensagem de Join para roteador pai
• Mensagem de Join contém uma lista
• Entradas (*,G) e (S,G) não atualizadas expiram em 3min
Marinho Barcellos - PIP/CA - UNISINOS 79RNP2000
PIM/SM: mensagens de registro de fonte
• Inicialmente, tráfego de uma fonte S1 deve ser enviado
para o RP, que o distribuirá via árvore compartilhada
• Para que o RP receba tráfego enviado ao grupo por S1
§ o primeiro roteador junto a S1 encapsula cada pacote enviado por S1
juntamente com uma mensagem de PIM Register
§ pacotes de Register com dados são enviados direto por unicast ao RP
§ RP desencapsula pacotes e verifica se existem receptores registrados
Marinho Barcellos - PIP/CA - UNISINOS 80RNP2000
PIM/SM: mensagens de registro de fonte
• Se há receptores registrados
§ RP então faz Join da árvore de menor caminho baseada em S1 para
receber tráfego de S1 nativamente
§ mensagens de Join passam de hop em hop configurando entradas
(S1,G) em roteadores entre o RP e S1
• RP envia mensagem de Register-Stop quando
§ RP começa a receber tráfego (S1,G) de maneira nativa, via árvore
baseada na fonte S1 – RP, ou
§ se RP não precisa do tráfego porque não há receptor registrado
Marinho Barcellos - PIP/CA - UNISINOS 81RNP2000
PIM/SM: exemplo de registro de fonte
RECEPTOR 1
Grupo G
ROTA ROTC ROTRP
ROTC ROTE
ROTD
RECEPTOR 2
Grupo G
FONTE S1
Grupo G
n x Register S,G
(S1,G) Join(S1,G) Join
Register-stop
Marinho Barcellos - PIP/CA - UNISINOS 82RNP2000
PIM/SM: exemplo com 2 fontes
RECEPTOR 1
Grupo G
ROTA ROTC ROTRP
ROTC ROTE
ROTD
RECEPTOR 2
Grupo G
FONTE S1
Grupo G
FONTE S2
Grupo G
(S1,G) SPT (S1,G) SPT
(*,G) RPT
(*,G) RPT
(S2,G) SPT
SPT – Shared-Path Tree
RPT – Rendesvouz-Point Tree
Marinho Barcellos - PIP/CA - UNISINOS 83RNP2000
PIM/SM: troca entre árvores (switchover)
• Roteador folha pode decidir trocar de tipo de árvore
§ de compartilhada (*,G) para árvore baseada na fonte (S,G)
• Roteadores são configurados com um threshold (valor
limite) que indica quando (vale a pena) efetuar a troca
• No caso de Cisco, valor default é 0 (troca imediatamente
após receber primeiros pacotes)
Marinho Barcellos- PIP/CA - UNISINOS 84RNP2000
PIM/SM: exemplo de switchover
RECEPTOR 1
Grupo G
ROTA ROTC ROTRP
ROTC ROTE
ROTD
RECEPTOR 2
Grupo G
FONTE S1
Grupo G
FONTE S2
Grupo G
(S1,G) SPT (S1,G) SPT
(*,G) RPT
(*,G) RPT
(S2,G) SPT
(S1,G) Join
(S1,G) Prune
(S1,G) SPT
(S1,G) Prune(S1,G) Prune
resultado final
Marinho Barcellos - PIP/CA - UNISINOS 85RNP2000
PIM/SM: escalabilidade
• Modelo de Join explícito (pull) tráfego multicast é melhor
restrito (!= flood-and-prune)
• Troca para árvore baseada na fonte elimina overhead de
enviar tráfego a um RP
• Configurabilidade – é possível alterar o threshold
• É a melhor escolha para roteamento intra-domínio,
segundo a Cisco
<< Protocolos de Roteamento <<
CBT: Core Based Trees
Marinho Barcellos - PIP/CA - UNISINOS 88RNP2000
CBT: Core Based Trees
• Trabalho em andamento: 3 versões incompatíveis entre si
• CBTv2 – RFC 2189
• Motivação fundamental para CBT
§ redução da quantidade de estado em roteadores – para O(G)
§ proporcional ao grupo, e não aos pares (S,G)
• CBT emprega
§ uma única árvore
§ compartilhada entre os membros de um grupo
§ bidirecional
Marinho Barcellos - PIP/CA - UNISINOS 89RNP2000
CBT: Core Based Trees
ROTX
M7
ROTY
ROTC
ROTA ROTB
ROTD ROTE ROTF ROTG
M1 M2 M3
M4
M6
M5
Marinho Barcellos - PIP/CA - UNISINOS 90RNP2000
CBT: Core Based Trees
• Como a árvore é bidirecional, tráfego não precisa ir antes
até o núcleo
• Diminui
§ latência em relação a árvore PIM/SM
§ estado e processamento em roteadores
• Roteadores que possuem fontes que não são membros
§ precisam encapsular seus pacotes e enviá-los ao Core ou outro nó
mais próximo que faça parte da árvore
• Distribuição de tráfego sub-optima
§ exemplo: adicionar fonte ligada ao roteador ROTG
Marinho Barcellos - PIP/CA - UNISINOS 91RNP2000
CBT: Core Based Trees
• Para entrar em grupo...
• Roteador folha envia Join em direção ao Core
• Pacote é encaminhado por roteadores CBT até encontrar
um roteador que pertença à árvore (o Core no pior caso)
• Esse roteador envia um Join-Ack de volta
Marinho Barcellos - PIP/CA - UNISINOS 92RNP2000
CBT: Core Based Trees
• Vantagem de CBT é a escalabilidade
• Desvantagens principal é a existência de um ponto
central de falha, o Core (núcleo)
• Também o aumento de latência, especialmente se locação
do Core é ruim
Marinho Barcellos - PIP/CA - UNISINOS 93RNP2000
Resumindo...
protocolos de 
roteamento multicast
modo denso
(árvore baseada na fonte)
modo esparso
(árvore compartilhada)
vetor de distâncias estado de link
DVMRP PIM-DM MOSPF PIM-SM CBT
<< Protocolos de Roteamento <<
Marinho Barcellos - PIP/CA - UNISINOS 95RNP2000
Outros Protocolos de Roteamento Multicast
• OCBT: Ordered Core base Trees
• H-DVMRP: Hierarchical DVMRP
• HPIM: Hierarchical PIM
Roteamento Multicast Inter-domínio
Marinho Barcellos - PIP/CA - UNISINOS 97RNP2000
Roteamento Multicast Inter-domínio
• Embora DVMRP seja usado no Mbone...
• Protocolos de roteamento vistos são apropriados para um
único domínio (detalhes)
• Necessário “colar” junto vários protocolos intra-domínio
• Inter-operação com protocolos DVMRP, PIM, CBT, MOSPF
• Domínio raiz?
Marinho Barcellos - PIP/CA - UNISINOS 98RNP2000
Roteamento Multicast Inter-domínio
• Protocolos inter-domínio
§ Multicast BGP (ou Multiprotocol BGP)
§ Multicast Source Discovery Protocol (MSDP)
• Grupo IETF Inter-domain multicast routing group
§ Border Gateway Multicast Protocol (BGMP)
§ Multicast Address Set Claim (MASC)
<< Sumário <<
Marinho Barcellos - PIP/CA - UNISINOS 100RNP2000
Deficiências Protocolos Atuais
• DVMRP
§ tráfego periódico de atualização de rotas
§ distância máxima em hops = 31
§ flood-and-prune: inundação periódica, tráfego de poda
§ estado em roteadores (árvore baseada na fonte)
• MOSPF
§ inundação a cada troca de composição de grupo
§ computação do algoritmo de Dijkstra sobrecarrega roteadores
§ estado em roteadores (mapa completo da rede e dos grupos)
• PIM-DM
§ flood-and-prune: inundação periódica, tráfego de poda
§ estado em roteadores (árvore baseada na fonte)
Marinho Barcellos - PIP/CA - UNISINOS 101RNP2000
Roteamento Multicast Inter-domínio
• PIM-SM
§ controle de grupo em RP mal localizado
§ dependendo, poden ser criadas muitas árvores baseadas na fonte
§ ISPs não querem depender de um RP localizado em outro ISP...
• CBT
§ potencial escolha de um RP ou Core ruim
§ concentração de tráfego no núcleo
• << protocolos inter-domínio <<
<< Sumário <<
Mbone - Internet Multicast Backbone
Marinho Barcellos - PIP/CA - UNISINOS 104RNP2000
Mbone: Multicast Backbone
• Subconjunto de roteadores e hosts interconectados
capazes de encaminhar tráfego multicast
• Histórico
§ início dos anos 90: criação da DARPA Testbed Network
§ Xerox, LBL, SRI, ISI, BBN, MIT, Delaware
§ Sun SPARC com routed e mrouted: IP multicast nativo (DVMRP)
§ 1992: IETF meeting, San Diego - transmissão do áudio do evento
• Em
§ 1997, 3.400 sub-redes com multicast habilitado
§ 1998, havia 7000 rotas DVMRP sendo anunciadas
• 50+% migrou para plataformas comerciais
Marinho Barcellos - PIP/CA - UNISINOS 105RNP2000
Mbone Viabilizou Multicast na Internet
• O Impasse, ou o problema do “ovo-e-da-galinha”
• Solução?
§ na periferia, interessados usam IGMP
§ estabelecimento manual de túneis IP entre estas subredes e
roteamento DVMRP
• Primeiro túnel: 1988, entre BBN (Boston) e Stanford
Marinho Barcellos - PIP/CA - UNISINOS 106RNP2000
Mbone e os Túneis
• Permitem multicast ao longo de uma rede que não
suporta multicast
• Ligam ponto-a-ponto dois roteadores que suportam IP
multicast
• Tipicamente daemon “mrouted” em estação de trabalho
• Limitação de tráfego: não encaminha se TTL < threshold
Tópicos Avançados
Marinho Barcellos - PIP/CA - UNISINOS 108RNP2000
Transmissão em Tempo Real
• RTP/RTCP – Real Time Protocol, Real Time Control
Protocol
§ unicast e multicast
§ framework para aplicações com tempo real “soft”
§ complementado por perfis
§ sincronização de streams de mídia através de timestamps
§ permite aos receptores monitorarem a qualidade de recepção
§ mecanismo de “feedback” que limita esse tipo de tráfego a 5% do total
• Aplicações de tempo-real usualmente
§ podem conviver com poucas perdas de pacotes
§ são sensíveis a atrasos na entrega de pacotes
Marinho Barcellos - PIP/CA - UNISINOS 109RNP2000
QoS – Quality of Service
• Garantir qualidade de serviço para fluxos de pacotes
• Reserva de banda
• RSVP – Resource Reservation Protocol
• IntServ – Integrated Services
§ guaranteed
§ controlled load
• DiffServ – Differenciated Services
• Protocolo de roteamento dirigido a QoS
Marinho Barcellos - PIP/CA - UNISINOS 110RNP2000
Multicast Confiável
• Transmissão de pacotes via IP multicast não é confiável
• Controle de congestionamento
• Para se inserir confiabilidade (controle de erro), quem
recebe pacote envia de volta um ACK (a la TCP)
• Problema de escalabilidade: processamento de ACKs,
quantidade de estado levam à implosão
• Disseminação confiável via protocolo multicast escalável
• Mecanismos de controle de congestionamento
<< Sumário <<
Comentários Finais
Marinho Barcellos - PIP/CA - UNISINOS 113RNP2000
Resumo
• Fundamentos de IP Multicast
• IGMP - Internet Group Management Protocol
• Roteamento Multicast
§ RPF
§ DVMRP
§ MOSPF
§ PIM/DM
§ PIM/SM
§ CBT
• Tópicos avançados
Marinho Barcellos - PIP/CA - UNISINOS 114RNP2000
Contatos
http://www.inf.unisinos.br/~marinho
marinho@exatas.unisinos.br
§ UNISINOS
§ PIP/CA – Programa de Pós-Graduação em Computação
Aplicada• Projeto sobre Protocolos Multicast para Disseminação Confiável
§ PRAV – Laboratório de Pesquisa de Redes de Alta
Velocidade
f i m