ar-tema3

Vista previa del material en texto

1908 – Arquitectura de Redes
Tema 3. IP Multicast
Pedro M. Ruiz
<pedrom@um.es>
Francisco J. Ros
<fjros@um.es>
3º Grado en Ingeniería Informática – 2011/2012
Organización del tema
� Introducción a IP Multicast
� Direccionamiento y control de ámbito
� Protocolos de gestión de grupos
� Encaminamiento Multicast
– Árboles multicast y multicast forwarding
– Protocolos en modo denso (DVMRP, PIM-DM)
– Protocolos en modo disperso (PIM-SM)
� Encaminamiento multicast entre dominios
2Arquitectura de Redes - Universidad de Murcia
Organización del tema
� Introducción a IP Multicast
� Direccionamiento y control de ámbito
� Protocolos de gestión de grupos
� Encaminamiento Multicast
– Árboles multicast y multicast forwarding
– Protocolos en modo denso (DVMRP, PIM-DM)
– Protocolos en modo disperso (PIM-SM)
� Encaminamiento multicast entre dominios
3Arquitectura de Redes - Universidad de Murcia
Contextualización
� Hasta ahora hemos asumido comunicaciones 
desde un emisor a un receptor
– Encaminamiento (IP)
– Control de flujo y de errores (TCP)
� En esta lección, introduciremos el caso de un 
emisor, que desea enviar la misma información a 
múltiples destinos
– Caso 1: multi-unicast. Una sesión con cada destino.
– Caso 2: broadcast. Datos a todos los nodos.
¿Es posible conseguir algo mejor?
4Arquitectura de Redes - Universidad de Murcia
¿Qué es multicast?
Host
Router
Unicast
Host
Router
Multicast
5Arquitectura de Redes - Universidad de Murcia
Ventajas e inconvenientes
� Ventajas
– Reducción del consumo de ancho de banda
– Reducción de la carga en servidores
– Reducción de la carga en la red
� Inconvenientes
– Transmisión no fiable basada en UDP
– Congestión de la red al no usar el slow-start de TCP
6Arquitectura de Redes - Universidad de Murcia
El modelo IP Multicast
� S. Deering, RFC 1112: “Host Extensions for 
Multicast Support”
� No existe requisito alguno para transmitir multicast
� Los receptores deben unirse al grupo multicast 
para recibir los datagramas
� Los routers “conspiran” para hacer que los 
datagramas lleguen de los emisores a los 
receptores
7Arquitectura de Redes - Universidad de Murcia
Modelo IP Multicast
Hosts
Routers
Protocolos entre Hosts y Routers (IGMP)
Protocolos de Enrutamiento 
Multicast (PIM, DVMRP, MBGP,...)
8Arquitectura de Redes - Universidad de Murcia
Organización del tema
� Introducción a IP Multicast
� Direccionamiento y control de ámbito
� Protocolos de gestión de grupos
� Encaminamiento Multicast
– Árboles multicast y multicast forwarding
– Protocolos en modo denso (DVMRP, PIM-DM)
– Protocolos en modo disperso (PIM-SM)
� Encaminamiento multicast entre dominios
9Arquitectura de Redes - Universidad de Murcia
Direcciones IP Multicast
� Clase D: 224.0.0.0 - 239.255.255.255
� Algunas direcciones reservadas (IANA)
– 224.0.0.0/24: link-local
�224.0.0.1 (todos los hosts), 224.0.0.2 (todos los routers 
multicast), …
– 224.0.1.0/24: reservadas para distintos protocolos
�224.0.1.1 (NTP, Network Time Protocol), …
– etc
� Direcciones privadas para ámbito local
– 239.0.0.0/8
� Otras usadas dinámicamente
10Arquitectura de Redes - Universidad de Murcia
IP Mcast vs. Link Mcast
48 bits
Prefijo
25 bits
23 bits
01-00-5e-7f-00-01
32 bits
1110
239.255.0.1
28 bits
5 bits perdidos
11Arquitectura de Redes - Universidad de Murcia
Cálculo de MAC Mcast
Ethernet y FDDI
Dada IPmcast, MAC corresondiente es 
(0x0000IPmcast & 0x0000007FFFFF) | 0x01005E000000
229.12.10.93
0000E5C0A05D
AND 0000007FFFFF
00000040A05D
OR 01005E000000
01005E40A05D
12Arquitectura de Redes - Universidad de Murcia
Ejemplo de mapping incompleto
224.1.1.1
224.128.1.1
225.1.1.1
225.128.1.1
.
.
.
.
.
.
238.1.1.1
238.128.1.1
239.1.1.1
239.128.1.1
0x0100.5E01.0101
32:1
13Arquitectura de Redes - Universidad de Murcia
Direcciones Reservadas
� 224.0.3/24 - 238.255/16: Para cualquier grupo de 
ámbito mundial
� 239.255/16: Para grupos locales a una 
organización
Control de Ámbito
14Arquitectura de Redes - Universidad de Murcia
Scoping
� TTL Scoping
– Consiste en limitar el alcance de un paquete en base al campo TTL 
del datagrama IP.
� Administrative Scoping
– Consiste en reservar determinados rangos de direcciones multicast 
para sólo sean distribuidos internamente. Los routers multicast se 
encargarán de no distribuir los datagramas con esas direcciones 
como destinos.
15Arquitectura de Redes - Universidad de Murcia
TTL Scoping
Dante
RedIRIS
UM
TTL
>128
TTL
64
TTL
32
TTL
16
16Arquitectura de Redes - Universidad de Murcia
Administrative Scoping
239.0.0.0/8
239.128.0.0/16
Univ. Murcia Univ. Carlos III
RedIRIS
17Arquitectura de Redes - Universidad de Murcia
Arquitectura General
Hosts
Routers
Protocolos entre Hosts y Routers (IGMP)
Protocolos de Enrutamiento 
Multicast (PIM, DVMRP, BGMP,...)
¿Qué ocurre si no todos los
routers soportan
multicast?
¿Qué ocurre si no todos los
routers soportan
multicast?
18Arquitectura de Redes - Universidad de Murcia
MBone
� Backbone Multicast experimental de Internet
� Utilizado por multitud de aplicaciones de 
transmisión de audio y vídeo multidestino en 
tiempo real
� Red virtual construida sobre la Internet para 
soportar tráfico multicast
– Islas multicast unidas mediante túneles o bien con 
routing nativo (DVMRP)
� Inútil cuando todos los routers de Internet soporten 
multicast
19Arquitectura de Redes - Universidad de Murcia
Túneles Multicast
Red no
Multicast
Red Multicast
Red Multicast
Tunel
Dir. IP unicast
Dir. IP multicast Datos
� Permiten la interconexión de islas multicast a través 
de redes no multicast:
� Encapsulación de IP sobre IP
20Arquitectura de Redes - Universidad de Murcia
UR1 UR2
Multicast
Router 1
Multicast
Router 2
Sender 1
Paquete de datos
encapsulado
Unicast Routers
Multicast Router 
1 encapsula 
paquetes 
multicast para 
receptores fuera 
de la red 
mediante el uso 
de paquetes 
unicast IP-in-IP .
Network 1
Receiver
Network 2
Multicast 
Router 2 
desencapsula 
paquetes IP-in-
IP y lo difunde 
a la red local
Multicast Tunneling
¿Como hacer que el control de
ámbito basado en TTL se
ajuste al acuerdo general
ante la presencia de túneles?
¿Como hacer que el control de
ámbito basado en TTL se
ajuste al acuerdo general
ante la presencia de túneles?
21Arquitectura de Redes - Universidad de Murcia
Control de Ámbito con Túneles
� Cada túnel se configura con un valor llamado TTL
� A su vez, el datagrama multicast tiene un valor de TTL en 
la cabecera, que denominaremos TTLmcast
� Al enviar un datagrama por una interfaz correspondiente a 
un túnel
– TTLmcast -= TTL
– Si TTLmcast <= 0, descartar datagrama
� Por cada salto real, el TTL que se decrementa es el del 
paquete unicast, por lo que el reenvío unicast no afecta a 
los cálculos
22Arquitectura de Redes - Universidad de Murcia
Ejemplo de Control de Ámbito basado en 
TTL con Túneles
Red no
Multicast
Univ. 1
RedIRIS
TTL=16
Red no
Multicast
Univ. 2
Local=16
Nacional = 32
23Arquitectura de Redes - Universidad de Murcia
Organización del tema
� Introducción a IP Multicast
� Direccionamiento y control de ámbito
� Protocolos de gestión de grupos
� Encaminamiento Multicast
– Árboles multicast y multicast forwarding
– Protocolos en modo denso (DVMRP, PIM-DM)
– Protocolos en modo disperso (PIM-SM)
� Encaminamiento multicast entre dominios
24Arquitectura de Redes - Universidad de Murcia
Contextualización
Hosts
Routers
Protocolos entre Hosts y Routers (IGMP)
Protocolos de Enrutamiento 
Multicast (PIM, DVMRP, MBGP,...)
� Modelo IP multicast
25Arquitectura de Redes - Universidad de Murcia
Internet Group Management Protocol 
(IGMP)
� Tres versiones diferentes
– IGMPv1
�Operación básica con limitaciones
– IGMPv2
�Mejora los aspectos referentes al abandono de un grupo
�Genera cuestiones de interoperabilidad
– IGMPv3
�Aporta posibilidad de unirse sólo a determinadas fuentes de un 
grupo multicast26Arquitectura de Redes - Universidad de Murcia
IGMPv1
� Internet Group Management Protocol (RFC 1112): protocolo 
de comunicación entre hosts y routers para la gestión de 
grupos multicast
� Mensajes IGMP encapsulados sobre IP (tipo 0x02 y TTL=1):
� IGMP no es parte integral de IP
� Formato:
IGMP
Cab. IP Datagrama IPDatos
Mensaje IGMP
ChecksumVers Reserv.Tipo
Dirección clase D
16 310 4 8 Tipo Mensaje
1 query (consulta router)
2 report (respuesta hosts)
27Arquitectura de Redes - Universidad de Murcia
IGMPv1 - Unión al grupo
Host 1 Host 2 Host 3
Envía IGMP
Report al grupo
224.5.5.5
224.5.5.5
� Para unirse al grupo, el host envía un IGMP 
Report a la dirección IP Multicast a la que desea 
unirse de forma asíncrona. 
28Arquitectura de Redes - Universidad de Murcia
IGMPv1 - General Queries
� El router, para determinar si siguen quedando 
miembros de un determinado grupo envía General 
Queries periódicamente a AllHosts
Host 1 Host 2 Host 3
Envía Report 
algrupo 224.5.5.5
Envía Report 
al grupo 224.2.0.1
Envía periódicamente 
IGMP Queries al grupo 
224.0.0.1
224.2.0.1
224.2.0.1
224.5.5.5224.2.0.1
29Arquitectura de Redes - Universidad de Murcia
IGMPv1 - Mantenimiento del grupo
� El router envía consultas periódicas (60 seg.)
� Sólo responde un miembro por grupo, ¿por qué?
– host inicia un timer entre 0 y MRT (10 seg por defecto)
– cancela timer si recibe Report de otro host
– envía Report si el timer expira
Host 1 Host 2
Host 3
Envía Report
al 224.5.5.5
Envía Report
al 224.2.0.1
Envía periódicamente
IGMP Query al 224.0.0.1
224.2.0.1
224.2.0.1
224.5.5.5224.2.0.1
Report a
224.2.0.1
suprimido 
Report a
224.2.0.1
suprimido 
30Arquitectura de Redes - Universidad de Murcia
IGMPv1 - Abandonar grupo
� Hosts abandonan el grupo sin avisar
� Router sigue preguntando
� No se recibe ningún IGMP Report
� El grupo expira (a los 3 Query intervals)
Host 1 Host 2 Host 3
Envía periódicamente 
IGMP Queries al grupo 
224.0.0.1
MRT
Gen. Query Gen. Query Gen. Query Gen. Query
Latencia Leave
Problema:
Suelen pasar 3 minutos hasta
que deja de inyectarse tráfico
innecesario
Problema:
Suelen pasar 3 minutos hasta
que deja de inyectarse tráfico
innecesario
31Arquitectura de Redes - Universidad de Murcia
IGMPv2
� Definido en el RFC 2236
� Añade nuevas funcionalidades
– Group Specific Queries
– Leave Group Message
– Mecanismo de Querier Election
– Query-Interval Response Time
� Además, es compatible con IGMPv1
32Arquitectura de Redes - Universidad de Murcia
Formato de paquetes IGMPv2
� Type:
– 0x11 = Membership Query
– 0x12 = Version 1 Membership Report
– 0x16 = Version 2 Membership Report
– 0x17 = Leave Group
� MRT (Max Response Time)
– Máximo tiempo sin enviar una respuesta en unidades de 1/10 segs (default=10 seg)
� Group Address
– Es el grupo multicast. 
– (0.0.0.0) para General Queries
Group Address
7 15 31
Type MRT Checksum
33Arquitectura de Redes - Universidad de Murcia
IGMPv2 - Unión Inicial al grupo
Host 1 Host 2 Host 3
Envía IGMP
Report al grupo
224.5.5.5
224.5.5.5
� Para unirse al grupo, el host envía un IGMP 
Report a la dirección IP Multicast a la que 
desea unirse de forma asíncrona(similar a 
IGMPv1)
155.54.1.10 155.54.1.11 155.54.1.12
34Arquitectura de Redes - Universidad de Murcia
IGMPv2 - Querier Election
Host 1 Host 2 Host 3
� Inicialmente el router asume que es Querier
� El router con menor IP se erige como Querier
� Los otros routers quedan como non-Querier
– Si no escuchan al Querier durante 2 General Query Interval 
(2 x 125 = 250 seg) se reinicia elección
155.54.1.10 155.54.1.11 155.54.1.12
A B
155.54.1.1 155.54.1.2
QueryQuery
IGMP
Querier
IGMP
Non-Querier
35Arquitectura de Redes - Universidad de Murcia
IGMPv2 - Mantenimiento del grupo
� El router envía general queries periódicas
� Responde un miembro por grupo
� Los otros miembros evitan responder
Host 1 Host 2
Host 3
Envía Report
a 224.5.5.5
Envía Report
a 224.2.0.1
Envía periódicamente
IGMP Query a 224.0.0.1
224.2.0.1
224.2.0.1
224.5.5.5224.2.0.1
Report a
224.2.0.1
suprimido 
Report a
224.2.0.1
suprimido 
IGMPv2
36Arquitectura de Redes - Universidad de Murcia
Report a
224.5.5.5 
Leave a 
224.0.0.2 
IGMP Group Specific
Query a 224.5.5.5
IGMPv2 - Abandonar grupo
� El Host 2 envía un mensaje Leave a 224.0.0.2 
(AllMcastRouters)
� El router envía un Group Specific Query a G
� Responde otro interesado ⇒ G activo
� Los otros miembros evitarían responder
Host 1 Host 2
Host 3
224.5.5.5 224.5.5.5
IGMPv2
37Arquitectura de Redes - Universidad de Murcia
IGMPv2 - Abandonar grupo
Leave a
224.0.0.2 
IGMP Group Specific
Query a 224.5.5.5
� El Host 3 envía el mensaje Leave
� El router envía un Group Specific Query a G
� MRT = 1 seg, expiración más rápida que en IGMPv1
� Si no hay respuesta tras 2 intentos ⇒ G no activo
� El grupo G expira
Host 1 Host 2
Host 3
224.5.5.5
IGMPv2
38Arquitectura de Redes - Universidad de Murcia
Interoperabilidad
IGMPv1-v2
v1 Report
a 224.5.5.5 
IGMPv1 General
Query a 224.0.0.1
� Cuando el router implementa IGMPv1:
– Los hosts deben enviar IGMPv1 Reports
– Los hosts podrían no enviar IGMPv2 Leaves
Host 1 Host 2
Host 3
224.5.5.5
IGMPv1
IGMPv2
39Arquitectura de Redes - Universidad de Murcia
Interoperabilidad
IGMPv1-v2
v1 Report
a 224.5.5.5 
IGMPv1 General 
Query a 224.0.0.1
� Cuando algún host usa IGMPv1:
– El router activa un temporizador asociado a haber un host IGMPv1 
para el grupo 224.5.5.5
– Ignora todos los IGMPv2 Leaves para ese grupo hasta que el 
temporizador anterior expira
Host 1 Host 2
Host 3
224.5.5.5
IGMPv2
IGMPv1
40Arquitectura de Redes - Universidad de Murcia
Interoperabilidad
IGMPv1-v2
� Cuando conviven routers IGMPv1-v2:
– Hay que configurar el router IGMPv2 para que actúe como IGMPv1
Host 1 Host 2
Host 3
IGMPv2 IGMPv1
41Arquitectura de Redes - Universidad de Murcia
IGMPv3
� Actualmente RFC 3376
� Permite hacer (S,G) Joins y Prunes
– Llamado “source filtering”
– Requisito para soportar Source-Specific Multicast
(SSM)
– Permite incluir o excluir fuentes específicas
� Primeras implementaciones surgieron con
– Linux 2.3.99
– IOS 12.1 (3) T 
� Actualmente ampliamente soportado
42Arquitectura de Redes - Universidad de Murcia
IGMPv3
H1
224.1.1.1
IP Orig: 155.54.1.10
Grupo: 224.1.1.1
IP Orig: 163.117.1.10
Grupo: 224.1.1.1
IGMPv3 Membership Report
INC 224.1.1.1 155.54.1.10
El host H1 quiere
recibir el tráfico 
dirigido a 224.1.1.1
de la fuente 155.54.1.10
y no de otra fuente
43Arquitectura de Redes - Universidad de Murcia
Router R3 puede podar
para no recibir el tráfico
de la fuente 163.117.1.10
R3
R1 R2
Organización del tema
� Introducción a IP Multicast
� Direccionamiento y control de ámbito
� Protocolos de gestión de grupos
� Encaminamiento Multicast
– Árboles multicast y multicast forwarding
– Protocolos en modo denso (DVMRP, PIM-DM)
– Protocolos en modo disperso (PIM-SM)
� Encaminamiento multicast entre dominios
46Arquitectura de Redes - Universidad de Murcia
Elementos del Routing Mcast
� Árboles de distribución multicast
� Multicast Forwarding
� Tipos de algoritmos de routing multicast 
intradominio
– Algoritmos modo dense
– Algoritmos modo sparse
– Algortimos híbridos
47Arquitectura de Redes - Universidad de Murcia
Árboles Multicast: Definiciones
� Sea G=(V,E,w) un grafo que representa una red de 
comunicaciones, tal que V es el conjunto de nodos, E es el 
conjunto de enlaces y w:E→R+ es la función de coste de 
cada enlace
� Árbol multicast
– Dado un conjunto S⊆V de fuentes y un conjunto R⊆Vde receptores, 
un arbol múlticast es un subgrafo conexo T=(V’,E’) G, tal que 
�S⊆V’, 
�R⊆V’,
�|E’| = |V’|-1
� Coste de un árbol multicast
– Dado un árbol multicast T se define su coste C(T) como
– C(T) = ∑w(e) ∀e∈E’
48Arquitectura de Redes - Universidad de Murcia
Ejemplo: S={A}, R={E,F}
Receptor 1
Notación: (S, G)
S = Fuente
G = Grupo
8
9
3
7
6
7
5
5 5
6
Receptor 2
Fuente
Coste = ∑wi = 8+5+6+5= 24
A
B
C
D
E
F
G
49Arquitectura de Redes - Universidad de Murcia
Árboles de Distribución Multicast
� Árboles multicast de coste mínimo (Steiner)
– Son los más eficientes
– Muy complejos de calcular (NP-completo)
� Árboles de camino más corto (SPT)
– Unión de caminos más cortos a cada destino
� Árboles compartidos (ST)
– Existe un router central de encuentro entre emisores y receptores
– Unidireccionales o Bidireccionales
50Arquitectura de Redes - Universidad de Murcia
Shortest Path Tree (SPT)
Receptor 1
E
BA D F
Fuente
Notación: (S, G)
S = Fuente
G = Grupo
C
Receptor 2
51Arquitectura de Redes - Universidad de Murcia
Shared Distribution Tree (ST)
Receptor 1
B
E
A D (Raíz 
Compartida)
F
Fuente 1 Notación: (*, G)
* = Cualquier fuente
G = Grupo
C
Receptor 2
Fuente 2
52Arquitectura de Redes - Universidad de Murcia
Comparativa de árboles de distribución
� Source Path Trees/Shortest Path Trees
– Representan el camino más corto hasta la fuente y son 
por lo tanto los más óptimos en retardo.
– Sin embargo, requieren mantener mayor estado 
(memoria) por lo que son menos escalables. O(SxG)
� Shared Trees 
– Son soluciones subóptimas pero sin embargo sólo 
requieren O(G) memoria por lo que son más escalables.
53Arquitectura de Redes - Universidad de Murcia
Ejemplo
Encontrar SPT y ST centrado en C
Receptor 1
Notación: (S, G)
S = Fuente
G = Grupo
8
9
3
7
6
7
5
5 5
6
Receptor 2
Fuente
SPT = {AB,AC,BF,CE}
Coste = ∑wi = 9+8+7+5 = 29
A
B
C
D
E
F
G
ST = {AC,CD,DF,CE}
Coste = ∑wi = 8+5+1+5 = 24
¿Es alguno de estos árboles
el de mínimo coste?
54Arquitectura de Redes - Universidad de Murcia
Minimum Steiner Tree (SMT)
Receptor 1
Notación: (S, G)
S = Fuente
G = Grupo
8
9
3
7
6
7
5
5 5
6
Receptor 2
Fuente
Coste = ∑wi = 9+3+6+5 = 23
A
B
C
D
E
F
G
55Arquitectura de Redes - Universidad de Murcia
¿Cómo se construyen los Árboles de 
Forma Distribuída?
� La construcción del árbol de distribución es lo que 
diferencia unos protocolos de routing de otros
� PIM
– Usa la tabla de routing unicast junto a los mensajes 
Join/Prune/Graft
� DVMRP
– Usa la tabla de routing multicast junto con un mecanismo llamado 
Poison-Reverse
� MOSPF
– Mecanismo basado en el estado de enlace
� CBT
– Tabla unicast más mensajes Join/Prune/Graft
56Arquitectura de Redes - Universidad de Murcia
Multicast Forwarding
� Una vez el árbol está construido, hay que enviar los 
datagramas (multicast forwarding)
� El routing multicast funciona al revés que el routing unicast
– El routing unicast se preocupa del destino del paquete
– El routing multicast se preocupa del origen del paquete
� Por lo tanto, el routing multicast usa el llamado “Reverse 
Path Forwarding” (RPF)
57Arquitectura de Redes - Universidad de Murcia
Reverse Path Forwarding
� El router sólo reenvía datagramas recibidos en la 
interfaz que él usaría para llegar a la fuente
� Para comprobarlo:
– Chequea la tabla de rutas según el protocolo de routing 
usado:
�DVMRP usa una tabla de routing multicast
�PIM usa la tabla unicast... etc.
– Si el datagrama llegó por el interfaz apropiado, la 
comprobación de RPF es exitosa 
– En caso contrario, el RPF check se considera fallido
58Arquitectura de Redes - Universidad de Murcia
Forwarding basado en RPF
� Una vez el árbol está construido, el router almacena la lista 
de interfaces de salida para el grupo G 
– Outgoing Interface List (OIL)
� Si el RPF Check falla, el datagama se descarta
� Si RPF Check es exitoso y TTL > 0, se envía una copia del 
paquete cada una de las interfaces en el OIL
� Este algoritmo garantiza que la interfaz de entrada nunca 
está en la OIL
59Arquitectura de Redes - Universidad de Murcia
E0
S2
S0
S1
Tabla routing mcast
Red Interfaz
151.10.0.0/16
198.14.32.0/24
204.1.16.0/24
S1
S0
E0
E0
S2
S0
S1
Tabla routing mcast
Red Interfaz
151.10.0.0/16
198.14.32.0/24
204.1.16.0/24
S1
S0
E0
Paquete desde
151.10.3.21
Paquete desde
151.10.3.21
Ejemplo de RPF Check
60Arquitectura de Redes - Universidad de Murcia
Multicast Forwarding-TTL’s
� Una interfaz puede configurarse con un “TTL 
threshold”
� Un datagrama se reenviará por un determinado 
interfaz si cumple las siguientes condiciones:
– El datagrama ha pasado el RPF Check
– La interfaz está en el Outgoing Interface List
– El TTL del datagrama es mayor que el threshold de esa 
interfaz
� Este mecanismo se emplea para hacer el TTL 
Scoping
61Arquitectura de Redes - Universidad de Murcia
Tipos de algoritmos de routing multicast 
� Algoritmos de tipo “Dense-Mode”
– Comportamiento de tipo inundación y poda
– Funcionan mejor cuando hay mucha probabilidad de 
que haya receptores interesados
� Algoritmos de tipo “Sparse-Mode”
– Comportamiento de tipo “explicit join”
– Funcionan mejor cuando los receptores son escasos y 
se encuentran muy dispersos
� Algoritmos híbridos
– MOSPF inunda información de routing, no tráfico 
multicast
62Arquitectura de Redes - Universidad de Murcia
Algoritmos Dense-Mode
� Asumen que va a haber mucha densidad de 
miembros para los grupos multicast
– Filosofía: Enviar tráfico a todos los posibles receptores y 
esperar a que avisen los que no estén interesados
– Las redes que no tienen miembros para ese grupo 
envían mensajes de “Prune” para podar esas ramas del 
árbol
– Hay un mecanismo de injerto (Graft) para volver a 
incorporar ramas al árbol con baja latencia
– Ventaja: Usa SPT y por lo tanto construye árboles 
óptimos
– Inconveniente: No escalable. Soft-state O(SxG)
63Arquitectura de Redes - Universidad de Murcia
Algoritmos Sparse-Mode
� Asume que los miembros del grupo están muy 
dispersos en una gran región
– El tráfico sólo llega a los receptores cuando éstos 
explícitamente lo solicitan
– Los “Joins” se propagan desde los receptores hasta el 
Core (CBT) o el Rendezvous Point (PIM)
– Dos tipos de Join (Sólo PIM-SM)
�(S,G) Join
�(*,G) Join
– Ventaja: más escalable y mejor aprovechamiento del 
ancho de banda
– Inconveniente: árboles no siempre óptimos
64Arquitectura de Redes - Universidad de Murcia
Ejemplos de protocolos
� Modo denso
– DVMRP
– PIM-DM
– MOSPF
� Modo disperso
– PIM-SM
– CBT
65Arquitectura de Redes - Universidad de Murcia
Organización del tema
� Introducción a IP Multicast
� Direccionamiento y control de ámbito
� Protocolos de gestión de grupos
� Encaminamiento Multicast
– Árboles multicast y multicast forwarding
– Protocolos en modo denso (DVMRP, PIM-DM)
– Protocolos en modo disperso (PIM-SM)
� Encaminamiento multicast entre dominios
66Arquitectura de Redes - Universidad de Murcia
Resumen de DVMRP
� RFC 1075
� Funciona en modo denso
– Inundación y poda
– Mantiene una tabla de routing multicast usada para hacer los RPF 
checks
� Shortest Path Trees
� Basado en vector de distancias
– Similar a RIP
– Infinito=32 saltos
– Usa máscaras de subred en los anuncios de rutas
– Usa mecanismo de Poison-Reverse
� Información de routing viaja en mensajes IGMP
IP (Protocol 2) IGMP (tipo 0x13) Paquetes DVMRP
67Arquitectura de Redes - Universidad de Murcia
Paquetes DVMRP
� DVMRP Probes
– Se usan para descubrir vecinos
� DVMRP Reports
– Se usan para el intercambio de rutas
� DVMRP Prunes
– Para podar ramas sin receptores
� DVMRP Grafts
– Para injertar ramas previamente podadas
� DVMRP Graft Ack’s
– Para asentir los mensajes de Graft
68Arquitectura de Redes - Universidad de Murcia
Descubrimiento de vecinos
en DVMRP
mrouted
mrouted
DVMRP1
DVMRP2
Neighbor Probe de DVMRP1
Neighbor List = NULL
Neighbor Probe
Neighbor List = 155.54.1.2
155.54.1.2
155.54.1.1
Neighbor Probe
Neighbor List = NULL
Neighbor Probe
Neighbor List = 155.54.1.1
Todos los mensajes Neighbor Probe se transmiten por multicast 
al grupo 224.0.0.4 “All-DVMRP Routers”
69Arquitectura de Redes - Universidad de Murcia
Intercambio de rutas DVMRP
mrouted
mrouted
DVMRP1
DVMRP2
155.54.1.2
155.54.1.1
if0
if0
if1
if1
Rutas DVMRP
Red Metr.If
Rutas DVMRPRed Metr.If
130.206.0.0/16 1 3
163.117.1.0/16 1 5
130.206.0.0/16 1 6
192.121.1.0/16 1 4� Estado inicial
– Los routers aún no han intercambiado rutas
– Cada router tiene dos interfaces if0 e if1
70Arquitectura de Redes - Universidad de Murcia
Intercambio de rutas DVMRP
mrouted
mrouted
DVMRP1
DVMRP2
155.54.1.2
155.54.1.1
if0
if0
if1
if1
Rutas DVMRP
Red Metr.If
Rutas DVMRP
Red Metr.If
130.206.0.0/16 1 3
163.117.1.0/16 1 5
130.206.0.0/16 0 4
192.121.1.0/16 1 4� Si la ruta ya es conocida y la métrica 
nueva es mejor se actualiza
� Si la ruta es nueva, se actualiza
Route Report
130.206.0.0/16 M=3
163.117.1.0/16 M=5
Recibe R. Report y actualiza tabla
163.117.1.0/16 0 6
71Arquitectura de Redes - Universidad de Murcia
Intercambio de rutas DVMRP
mrouted
mrouted
DVMRP1
DVMRP2
155.54.1.2
155.54.1.1
if0
if0
if1
if1
Rutas DVMRP
Red Metr.If
Rutas DVMRP
Red Metr.If
130.206.0.0/16 1 3
163.117.1.0/16 1 5
130.206.0.0/16 0 4
192.121.1.0/16 1 4� Utiliza Poison Reverse (Metric = Metric 
+32) para indicar DVMRP2 usa al 
propio DVMRP1 para esas fuentes
� Recordar que ∞ = 32 en DVMRP
Route Report
130.206.0.0/16 M=36
192.121.1.0/16 M=4
163.117.1.0/16 M=38
Envía R. Report
163.117.1.0/16 0 6
72Arquitectura de Redes - Universidad de Murcia
Intercambio de rutas DVMRP
mrouted
mrouted
DVMRP1
DVMRP2
155.54.1.2
155.54.1.1
if0
if0
if1
if1
Rutas DVMRP
Red Metr.If
Rutas DVMRP
Red Metr.If
130.206.0.0/16 1 3
163.117.1.0/16 1 5
130.206.0.0/16 0 4
192.121.1.0/16 1 4� DVMRP1 actualiza las rutas. En este 
caso sólo necesita añadir la última 
entrada.
Envía R. Report
163.117.1.0/16 0 6
192.121.1.0/16 0 5
73Arquitectura de Redes - Universidad de Murcia
Intercambio de rutas DVMRP
mrouted
mrouted
DVMRP1
DVMRP2
155.54.1.2
155.54.1.1
if0
if0
if1
if1
Rutas DVMRP
Red Metr.If
130.206.0.0/16 0 4
192.121.1.0/16 1 4� DVMRP1 vuelve a enviar las rutas 
actualizadas y de nuevo usando el 
Poison Reverse donde corresponda.
Route Report
130.206.0.0/16 M=3
192.121.1.0/16 M=37
163.117.1.0/16 M=5
163.117.1.0/16 0 6
Rutas DVMRP
Red Metr.If
130.206.0.0/16 1 3
163.117.1.0/16 1 5
192.121.1.0/16 0 5
74Arquitectura de Redes - Universidad de Murcia
Árboles de distribución DVMRP
Fuente
Receptor 2Receptor 1
BA
Unicast
Route Report
Poison Reverse
A B
C D
H I
E
F
G
75Arquitectura de Redes - Universidad de Murcia
Árboles de distribución DVMRP
Se forman usando la mejor métrica
DVMRP hasta la fuente. Para ello el 
router padre se fija en el Poison Reverse
Red Origen
BAA B
C D E
F
G
1 1 1
2
2
35
3 36
36
2
3434
En caso de empate se elige el router con 
menor dir IP
En nuestro ejemplo: IP(D)<IP(C)<IP(B)<IP(A)
76Arquitectura de Redes - Universidad de Murcia
Árboles de distribución DVMRP
Árbol de distribución resultante 
Fuente
BAA B
C D E
F
G
77Arquitectura de Redes - Universidad de Murcia
Árboles de distribución DVMRP
BAA B
C D E
F
G
1.Se construye un árbol para cada fuente
2. Seguimos suponiendo que
IP(D)<IP(C)<IP(B)<IP(A)
1
2
Fuente 2
3
3
4
4
4
437
36
5
36
35
34
34
78Arquitectura de Redes - Universidad de Murcia
Árboles de distribución DVMRP
BAA B
C D E
F
G
Árbol resultante
1
Fuente 2
79Arquitectura de Redes - Universidad de Murcia
DVMRP Forwarding
E0
S2
S0
S1
Tabla routing mcast
Red Interfaz
151.10.0.0/16
198.14.32.0/24
204.1.16.0/24
S1
S0
E0
E0
S2
S0
S1
Tabla routing mcast
Red Interfaz
151.10.0.0/16
198.14.32.0/24
204.1.16.0/24
S1
S0
E0
Paquete desde
151.10.3.21
Paquete desde
151.10.3.21
mrouted
mrouted
Metric
4
3
10
Red
4
3
10
80Arquitectura de Redes - Universidad de Murcia
DVMRP Forwarding en redes de 
medio compartido
� Para evitar duplicados, se 
elegirá un “Designated 
Forwarder” (DF) entre B y C
� Se elige el de mejor 
métrica a la red origen
– En este caso, como ambos 
comparten red tendrán a 
misma métrica.
– Tal y como vimos, en tal caso 
DVMRP elige el de dirección IP 
menor
A
B C
Anuncio de rutas
Red a anunciar
1 1
2
2
DVMRP Pruning
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
Árbol de distrib.
Tráfico mcast
Mensajes prune
82Arquitectura de Redes - Universidad de Murcia
DVMRP Pruning
Fuente
Receptor 1
BAA B
C D E
F
G
Prune
(S,G)
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
Prune
El router C no es el DF para la red 
del receptor. Luego asume que 
no tiene receptores interesados y 
envía un Prune (S,G) hacia B.
IP(D)<IP(C)
83Arquitectura de Redes - Universidad de Murcia
DVMRP Pruning
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
Como consecuencia del mensaje
prune, el router B deja de hacer 
forwarding de los datagramas de 
S al grupo G.
84Arquitectura de Redes - Universidad de Murcia
DVMRP Pruning
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
De nuevo F y G envían el mensaje 
Prune(S,G) para dejar de recibir 
tráfico no deseado.
Prune
(S,G)
Prune
(S,G)
85Arquitectura de Redes - Universidad de Murcia
DVMRP Pruning
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
Ahora el router E deja de hacer 
forwarding de esos datagramas 
en el interfaz hacia F y G pero 
sólo para la fuente S
86Arquitectura de Redes - Universidad de Murcia
DVMRP Pruning
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
Ahora, como E tampoco tiene 
receptores interesados, vuelve a 
enviar el mensaje de pruning a su 
vecino hacia S
Prune
(S,G)
87Arquitectura de Redes - Universidad de Murcia
DVMRP Pruning
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
D hace la poda y ahora sólo llega 
tráfico donde es requerido. Notar que 
el árbol sigue estando establecido y 
el proceso de forwarding hace que 
sólo llegue trafico a ciertas redes
88Arquitectura de Redes - Universidad de Murcia
DVMRP Grafting
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
Un nuevo receptor se une al grupo 
multicast desde la red del router G
Receptor(G)
Graft
89Arquitectura de Redes - Universidad de Murcia
DVMRP Grafting
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
Como el estado está ya creado en 
todos los routers, E sólo necesita 
enviar un Graft Ack a G y un Graft a 
su vecino hacia la fuente para 
restabler el árbol de distribución.
Receptor(G)
Graft
Graft-Ack
90Arquitectura de Redes - Universidad de Murcia
DVMRP Grafting
Fuente(S)
Receptor(G)
BAA B
C D E
F
G
Ahora D envía el Graft-Ack con lo que 
el árbol queda completamente 
restablecido sin tener que volver a 
calcular la tabla de routing.
Receptor(G)
Graft-Ack
91Arquitectura de Redes - Universidad de Murcia
Resumen de PIM-DM
� RFC 3973 (PIMv2 – DM)
� Muy similar a DVMRP excepto en que no dispone de tablas de routing 
multicast ni de mensajes de routing
� Shortest Path Trees
� También utiliza inundación (Flood) y poda (Prune)
� Soporta también un mecanismo de injerto (Graft)
� Usa mensajes Assert para establecer el DF
� Los mensajes PIMv1 viajan en paquetes IGMP
� Los de PIMv2 sobre IP con protocolo 103
– PIMv2 tiene algunas extensiones a los mensajes v1
92Arquitectura de Redes - Universidad de Murcia
Mensajes PIM-DM
� Hello
� Join/Prune
� Graft/Graft-Ack
� Assert
93Arquitectura de Redes - Universidad de Murcia
Cabecera PIM
� PIM Ver
� Version = 1 ó 2
� Type:
– 0 = Hello
– 1 = Register (sólo PIM-SM)
– 2 = Register-Stop (sólo PIM-SM)
– 3 = Join/Prune
– 4 = Bootstrap (sólo PIM-SM)
– 5 = Assert
– 6 = Graft
– 7 = Graft-ACK
– 8 = Candidate RP Adv (sólo PIM-SM)
– 9 = State refresh
94Arquitectura de Redes - Universidad de Murcia
PIM
Ver
Type Reserved
7 1530 4 8
Checksum
16 31
Funcionamiento de 
PIM-DM
� Descubrimiento de vecinos
� Forwarding
� Pruning
� Grafting
� Mecanismo Assert
� Mantenimiento del estado
95Arquitectura de Redes - Universidad de Murcia
Descubrimiento de vecinos en PIM
PIM Hello
Router 1 PIM-DM
155.54.1.1
Router 2 PIM-DM
155.54.1.2
PIM Hello
Todos los mensajes PIM Hello se transmiten por multicast al grupo 224.0.0.13 
(AllPIMRouters) con TTL=1 cada 30 seg (por defecto).
En PIM-DM, cualquier interfaz por la que hemos oído algún vecino se añade 
automáticamentea la lista de interfaces de salida (“oilist”).
96Arquitectura de Redes - Universidad de Murcia
Forwarding en PIM-DM
Paquetes Multicast
(155.54.12.1,224.2.2.2)
A
B
Las interfaces del router se añaden a la lista de interfaces de salida (“oilist”) 
si:
• Se escuchó un vecino PIM en el interfaz.
• Algún host se ha unido al grupo multicast en esa interfaz.
• El router se ha configurado manualmente para que se una al grupo.
El funcionamiento del router consiste en inundar el tráfico multicast por
todas las interfaces que estén en la “oilist”
S0 S1
S2
97Arquitectura de Redes - Universidad de Murcia
Pruning en PIM-DM
Paquetes Multicast
(155.54.12.1,224.2.2.2)
A
B
1. A inicialmente está inundando las interfaces de la “oilist”.
2. B envía el mensaje de PIM Prune (S,G) a A para dejar de recibir el 
tráfico.
3. A poda la interfaz S2 para (S,G).
S0 S1
S2Prune
(S,G)
98Arquitectura de Redes - Universidad de Murcia
Retardo al podar con 
PIM-DM en LANs
A
B C
S0 S1
E0
E0 E0
E1 E1
- El router B envía un Prune (S,G) porque no tiene interesados.
- Cuando A recibe el Prune(S,G) de B, planifica la realización de la poda 
para dentro de 3 seg. Así da tiempo a otros posibles interesados.
- En este caso C tiene interesados, oye el Prune de B, y envía un Join para 
evitar que A pode (Prune Override).
- Como A recibe el Join de C, cancela la poda que tenía planificada.
Problema: alto retardo de poda cuando hay muchas LAN en cascada.
Prune
(S,G)
Join
(S,G)Me esperaré 
3 seg por si 
aún queda algún 
interesado
99Arquitectura de Redes - Universidad de Murcia
PIM-DM Grafting
Paquetes Multicast
(155.54.12.1,224.2.2.2)
A
B
Como el router B desea unirse después de haber estado unido 
previamente, en lugar de enviar un Join, envía un Graft que permite 
restablecer el árbol de distribución de un modo más eficiente.
Esto hace que A envíe un Graft-Ack y restablezca el interfaz S2 a modo 
Forward/Dense.
S0
S1
S2Graft
(S,G) Graft ACK
100Arquitectura de Redes - Universidad de Murcia
Mecanismo de Assert en PIM
S0 S0
E0 E0Assert
<dist,metric>
Assert
<dist,metric>
El problema se detecta cuando un router recibe un datagrama (S,G) por un 
interfaz que él tiene en la OIList correspondiente en la tabla de forwarding.
� tráfico duplicado en la LAN a través de A y B.
Solución: Los routers implicados envían un mensaje PIM Assert
Todos comparan los valores de distancia administrativa y métrica.
Gana el router con la mejor tupla <distancia,métrica>.
En caso de empate en tupla, gana el router con la mayor dirección IP.
Los routers que pierden podan esa interfaz.
101Arquitectura de Redes - Universidad de Murcia
A B
Mantenimiento del estado en PIM-DM
� El estado se mantiene en base al comportamiento “inundación y poda”
– Conforme se van recibiendo datagramas multicast, el temporizador de la 
entrada (S,G) de la tabla de forwarding se resetea a 3 minutos.
– Cuando, ese temporizador expira, la entrada se elimina de la tabla de 
forwarding.
� El estado de poda expira cada 3 min. Esto causa que pasado ese 
tiempo se vuelva a inundar y podar.
102Arquitectura de Redes - Universidad de Murcia
Repaso de PIM-DM
Fuente
Receptor 2Receptor 1
D F
I
B
C
A
E
G
H
Unicast
Datos
Control
103Arquitectura de Redes - Universidad de Murcia
Repaso de PIM-DM
Primero inundamos y creamos 
estado de forwarding en todos
los enlaces.
Fuente
Receptor 2Receptor 1
D F
I
B
C
A
E
G
H
104Arquitectura de Redes - Universidad de Murcia
Repaso de PIM-DM
Prune al vecino que no
pasa el RPF Check.
Fuente
Prune
Receptor 2Receptor 1
D F
I
B
C
A
E
G
H
105Arquitectura de Redes - Universidad de Murcia
Repaso de PIM-DM
C y D envían mensajes Assert
para determinar el DR para esa
LAN. C gana.
Fuente
Asserts
Receptor 2Receptor 1
D F
I
B
C
A
E
G
H
106Arquitectura de Redes - Universidad de Murcia
Repaso de PIM-DM
I se poda del árbol.
El Prune de E se ignora.
G no poda porque H hace Join.
Fuente
Prune
Receptor 2Receptor 1
Join Override
Prune
D F
I
B
C
A
E
G
H
107Arquitectura de Redes - Universidad de Murcia
Repaso de PIM-DM
Fuente
Graft
Receptor 2
Receptor 3
Receptor 1
Nuevo receptor, I envía un Graft.
D F
I
B
C
A
E
G
H
108Arquitectura de Redes - Universidad de Murcia
Repaso de PIM-DM
Fuente
Receptor 2
Receptor 3
Receptor 1
D F
I
B
C
A
E
G
H
109Arquitectura de Redes - Universidad de Murcia
Organización del tema
� Introducción a IP Multicast
� Direccionamiento y control de ámbito
� Protocolos de gestión de grupos
� Encaminamiento Multicast
– Árboles multicast y multicast forwarding
– Protocolos en modo denso (DVMRP, PIM-DM)
– Protocolos en modo disperso (PIM-SM)
� Encaminamiento multicast entre dominios
110Arquitectura de Redes - Universidad de Murcia
Idea General de PIM-SM
� RFC 4601
� Objetivo: evitar inundación periódica de la red
– Se elige un router que actúa como punto de encuento (RP: 
Rendezvous Point) para el grupo multicast
– Las fuentes se registran en el RP
– Los receptores se unen hacia el RP
RP
111Arquitectura de Redes - Universidad de Murcia
Resumen de PIM-SM
� Modelo “Explicit Join”
– Los receptores deben unirse al RP
– Los emisores se registran ante el RP
– El tráfico fluirá por el árbol compartido (ST, RPT) hacia los lugares 
donde explícitamente se hayan unido receptores
– Los routers hoja pueden unirse al árbol más corto a la fuente (SPT) 
si el ratio de paquetes multicast se considera suficiente
� El proceso de RPF Check depende del tipo de árbol
– Para Shared Tree (RPT) se usa la dirección del RP
– Para el Shortest Path Tree (SPT) se usa la dirección de la fuente
112Arquitectura de Redes - Universidad de Murcia
Resumen de PIM-SM
� Sólo puede elegirse un RP para un determinado grupo en 
un instante dado
� El RP puede configurarse estáticamente o aprenderse 
dinámicamente con:
– Auto-RP (Protocolo propietario de Cisco)
– PIMv2 Candidate RP Advertisements
� Los datos se envían basándose en el estado (S,G) del 
SPT. Si este estado no existe entonces se usa el estado 
(*,G) del árbol compartido (RPT).
113Arquitectura de Redes - Universidad de Murcia
Mensajes PIM-SM
� Hello
� Join/Prune
� Graft/Graft-Ack
� Assert
� Register
� Register-Stop
114Arquitectura de Redes - Universidad de Murcia
Funcionamiento de 
PIM-SM
� Descubrimiento de vecinos
� Joining en PIM-SM
� Registering en PIM-SM
� SPT-Switchover en PIM-SM
� Pruning en PIM-SM
� Mantenimiento del estado en PIM-SM
� Forwarding en PIM-SM
115Arquitectura de Redes - Universidad de Murcia
Descubrimiento de vecinos en PIM-SM
PIM Hello
Router 1 PIM-SM
155.54.1.1
Router 2 PIM-SM
155.54.1.2
PIM Hello
Todos los mensajes PIM Hello se transmiten por multicast al grupo 224.0.0.13 
(AllPIMRouters) con TTL=1 cada 30 seg (por defecto).
Establecen relaciones de vecindad: sólo se procesan mensajes PIM que lleguen de 
vecinos.
En LANs se selecciona un router designado (DR). Si el DR expira, se elige un 
nuevo DR.
• Si hay una fuente en la LAN, sólo el DR se registra en el árbol multicast
• Evitamos establecer caminos paralelos por los que enviaría tráfico duplicado
Elegido 
DR
116Arquitectura de Redes - Universidad de Murcia
Joining en PIM-SM
RPT
� Los nodos hoja envían Joins (*,G) hacia el RP
– Los Joins se envían salto a salto hacia el RP usando la 
tabla de rutas unicast
– Los Joins se envían al grupo multicast AllPIMRouters
� Cada router en el camino va creando estado de 
forwarding (*,G)
– Si no existía estado (*,G), se crea y se envía un Join en 
cascada de tipo (*,G) hacia el RP
– En caso contrario, ya hemos llegado al árbol 
compartido. Fin del proceso.
117Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
Receptor 1
Fuente
Receptor 2
Enlace
Datos
Control
BA DRP
EC
118Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
Receptor 1 se une al grupo 
G.
C crea el estado (*, G), envía
un Join (*, G) hacia el RP.
Join
Receptor 1
Fuente
Receptor 2
BA DRP
EC119Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
Receptor 1
Fuente El RP crea el estado (*, G) 
en la interfaz del Join.
Receptor 2
BA DRP
EC
120Arquitectura de Redes - Universidad de Murcia
Registering en PIM-SM
� Los emisores envían tráfico multicast sin 
necesidad de unirse al grupo
� El DR local, enviará por unicast estos paquetes 
multicast hacia el RP
– En concreto, el paquete multicast se encapsula dentro 
de un mensaje Register
� Cuando el RP recibe los mensajes Register
– Desencapsula el paquete multicast
– Lo envía por el árbol compartido
– Envía un (S,G) Join hacia el DR de la fuente para 
construir un SPT entre la fuente y el RP
121Arquitectura de Redes - Universidad de Murcia
Registering en PIM-SM
� Cuando el DR local del emisor recibe el (S,G) Join
– El SPT entre la fuente y el RP ya está construido
– Empieza a enviar tráfico por el SPT
– Pero temporalmente sigue transmitiendo con PIM Registers
� Cuando el RP empieza a recibir tráfico por el SPT envía un 
Register-Stop en unicast a ese router
� Cuando el DR local del emisor recibe el Register-Stop
– Deja de encapsular tráfico en mensajes Register
– El tráfico ahora sólo fluye por el SPT
122Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
Receptor 1
Fuente La fuente empieza a enviar datos y
A envía mensajes Register al RP.
Receptor 2
PIM-Register
BA DRP
EC
123Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
El RP desencapsula los mensajes Register
y envía los datos por el Shared Tree.
Además envía Join (S,G) hacia el DR de la 
fuente.
Join Join
Receptor 1
Fuente
Receptor 2
BA DRP
EC
124Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
El RP envía un Register-Stop al DR 
de la fuente tan pronto como recibe 
los datos nativamente.
Register-Stop
Receptor 1
Fuente
Receptor 2
BA DRP
EC
125Arquitectura de Redes - Universidad de Murcia
SPT-Switchover en PIM-SM
� Mecanismo para obtener árboles de distribución mas 
eficientes
� Se establece un SPT-Threshold entre 0 e infinito
– 0 = Cambiar a un SPT inmediatamente
– Infinito = Nunca cambiar a un SPT
� Si el tráfico recibido en kbps de una determinada fuente S 
para un determinado grupo G supera el SPT-Threshold, 
entonces se envía un (S,G) Join
– La ventaja es un árbol de distribución óptimo respecto al camino 
más corto
– El inconveniente es la reducción de escalabilidad al tener que 
almacenar la tabla de forwarding más entradas
126Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
C envía un Join (S, G) hacia la 
fuente para recibir el tráfico por 
un árbol más eficiente: el 
Shortest Path Tree (SPT).
(S, G) Join
Receptor 1
Fuente
Receptor 2
BA DRP
EC
129Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
A crea estado (S,G) para enviar 
el tráfico multicast a C. Éste 
recibiría el flujo por duplicado 
(SPT y RPT).
Receptor 1
Fuente
Receptor 2
BA DRP
EC
130Arquitectura de Redes - Universidad de Murcia
Pruning en PIM-SM
� Se usa para frenar flujo innecesario de datos no 
requeridos
– RPT Pruning
– SPT Pruning
131Arquitectura de Redes - Universidad de Murcia
RPT Pruning
� Cuando un flujo multicast deja de ser deseado, el 
host envía a su router local un IGMP Leave
� El router, al recibirlo, elimina la interfaz de la “oilist”
correspondiente al grupo
– Si la “oilist” para (*,G) se queda vacía, el router envía un 
(*,G) Prune a su vecino en el RPT
– Este proceso continúa hasta llegar al RP o a algún otro 
router que tiene interfaces no podadas en la “oilist”
132Arquitectura de Redes - Universidad de Murcia
SPT Pruning
� Cuando un flujo multicast deja de ser deseado, el 
host envía a su router local un IGMP Leave
� El router, al recibirlo, elimina la interfaz de la “oilist”
correspondiente al grupo
– Si la “oilist” para (S,G) se queda vacía, el router envía 
un (S,G) Prune a su vecino en el RPT
– Este proceso continúa hasta llegar al RP o a algún otro 
router que tiene interfaces no podadas en la “oilist”
� Un router también envía un (S,G) Prune con el bit 
RP activo para podar en el RPT tras hacer 
switchover al SPT
133Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
Cuando C recibe los datos 
nativamente, envía un Prune (S,G) al 
RPT. A su vez, el RP borra la entrada 
(S,G) asociada y envía un Prune hacia 
el DR de la fuente.
(S, G) Prune - RP Bit
(S, G) Prune
Receptor 1
Fuente
Receptor 2
BA DRP
EC
134Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
El receptor 1 sólo recibe el flujo 
multicast por el SPT.
Receptor 1
Fuente
Receptor 2
BA DRP
EC
135Arquitectura de Redes - Universidad de Murcia
Mantenimiento del estado en PIM-SM
� Los PIM Joins/Prunes se envían periódicamente a 
los vecinos
– Los Joins refrescan el estado de forwading en los 
vecinos
– Los Prune refrescan el estado de pruning en los vecinos
� Los paquetes multicast recibidos van inicializando 
los temporizadores asociados a las entradas (S,G)
136Arquitectura de Redes - Universidad de Murcia
Forwarding en PIM-SM
Router 1
155.54.1.1
Router 2
155.54.1.2
El RPF Check depende del árbol de distribución
Shared Tree (RPT) se usa la dirección del RP
Source Tree (SPT) se usa la dirección de Emisor
Hacia RP (10.1.5.1)
S0 S1
E0
E0
E1
SPT
(155.54.12.1,224.2.2.2)
RPT
(155.54.12.10,224.2.2.2)
Route Iface
10.1.5.0/24
10.1.2.0/24
155.54.0.0/16
S0
E0
S1
137Arquitectura de Redes - Universidad de Murcia
Forwarding en PIM-SM
Router 1
155.54.1.1
Router 2
155.54.1.2
•Los paquetes se distribuyen por todas las interfaces que estén 
en la “oilist”
•Una intefaz se añade a la “oilist” en PIM-SM para un 
determinado grupo multicast cuando: 
Un vecino PIM se une al grupo en esa interfaz
Un host en ese interfaz se ha unido al grupo
La interfaz se configuró manualmente para unirse al grupo
Hacia RP (10.1.5.1)
S0 S1
E0
E0
E1
SPT
(155.54.12.1,224.2.2.2)
RPT
(155.54.12.10,224.2.2.2)
Receptor A
(*,224.1.1.1)
138Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
Continuación
El Receptor 2 se une.
E crea el estado de forwarding (*,G) y 
envía un Join de tipo (*,G) hacia el RP.
(*, G) Join
Receptor 1
Fuente
Receptor 2
BA DRP
EC
139Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
Continuación
C añade el enlace hacia E a la “oilist” 
tanto para los datos de de (*, G) como 
para los de (S, G). A partir de este 
momento los datos ya le llegan a E.
Receptor 1
Fuente
Receptor 2
BA DRP
EC
140Arquitectura de Redes - Universidad de Murcia
Ejemplo PIM-SM
Continuación
Una nueva fuente empieza a emitir.
D envía Registers, RP envía Joins.
RP reenvía los datos a los receptores
mediante el árbol compartido.
Fuente 2
Register
Receptor 1
Fuente
Receptor 2
BA DRP
EC
141Arquitectura de Redes - Universidad de Murcia
Organización del tema
� Introducción a IP Multicast
� Direccionamiento y control de ámbito
� Protocolos de gestión de grupos
� Encaminamiento Multicast
– Árboles multicast y multicast forwarding
– Protocolos en modo denso (DVMRP, PIM-DM)
– Protocolos en modo disperso (PIM-SM)
� Encaminamiento multicast entre dominios
142Arquitectura de Redes - Universidad de Murcia
Contextualización
� Hemos estudiado diferentes esquemas de encaminamiento 
multicast (intra-dominio)
– Modo denso: DVMRP, PIM-DM
– Modo disperso: PIM-SM
� Cuestión: ¿Es posible/deseable aplicar estos protocolos 
a nivel global de Internet?
SA 109 SA 207
SA 217
SA 76
SA 96
?
143Arquitectura de Redes - Universidad de Murcia
Carencias para routing global
� DVMRP y PIM-DM no sirven por su propio carácter Denso
� Otras soluciones como MOSPF requieren almacenar 
demasiado estado en los routers y enviar muchos LSA
� Protocolo en modo disperso como PIM-SM o CBT están 
basados en la idea de un RP por grupo
– un solo RP no escala a nivel global
– un ISP no quiere depender del RP de otro ISP
144Arquitectura de Redes - Universidad de Murcia
PIM-SM/MBGP/MSDP
� Soluciónmás usada actualmente.
� En cada dominio o SA se usa cualquier protocolo de 
enrutamiento. Actualmente el más usado PIM-SM.
� Con MBGP se intercambian informes sobre las redes a las 
que este SA puede llegar vía multicast.
� Con MSDP se intercambia la información sobre los 
emisores entre SAs.
� SOLUCIÓN POCO ESCALABLE al aumentar #fuentes
145Arquitectura de Redes - Universidad de Murcia
MBGP
Aclaraciones
� BGP4+ y MBGP son lo mismo.
� ¡No significa Multicast BGP!. Significa Multiprotocol 
extensions to BGP4, RFC 2858.
� No confundir MBGP con BGMP (Border Gateway Multicast 
Protocol, RFC 3913).
� MBGP no es específico para multicast. También puede 
usarse con otros protocolos como IPv6 o IPX.
� MBGP es capaz de interoperar con BGP4 y anteriores.
146Arquitectura de Redes - Universidad de Murcia
MBGP
Nuevos atributos
� MP_REACH_NLRI: Multiprotocol Reachable NLRI
(Network Level Reachability Information)
– Usado para anunciar a un peer una red alcanzable y el “next hop” a 
usar, de forma independiente del protocolo de red
� MP_UNREACH_NLRI: Multiprotocol Unreachable NLRI
– Usado para descartar determinadas rutas a destinos, de forma 
independiente del protocolo de red
� En el contexto de multicast, usamos MBGP para
– anunciar redes alcanzables vía multicast
– indicar el next hop a utilizar en el RPF check
147Arquitectura de Redes - Universidad de Murcia
MBGP
Funcionalidad
� MBGP no crea estado, los árboles multicast se construyen 
usando PIM-SM
� Un mensaje MP_REACH_NLRI sirve para decir a nuestros 
peers: “Tengo un camino para llegar a las fuentes multicast 
que haya en las redes que se indican en este mensaje”
� Cuando a un router le llega un Join (*,G) o (S,G) para un 
grupo con fuentes multicast en otros dominios se usa la 
información proporcionada por MBGP para saber el “next 
hop” router al que tiene que enviar el Join para construir el 
árbol entre dominios que llegue a esa fuente
¿Cómo saber si hay fuentes en otros dominios?
148Arquitectura de Redes - Universidad de Murcia
MSDP
� RFC 3618
� Multicast Source Discovery Protocol
� No existe un RP raíz. Cada dominio tiene el suyo. 
– No hace falta que varios dominios coadministren una 
nube tipo sparse
�Identificar Cand-RPs
�Hacer el mapping entre grupo multicast y RP
– Evitar dependencias de terceras partes
149Arquitectura de Redes - Universidad de Murcia
MSDP
Funcionamiento
� En cada dominio se configura alguno de los Cand-RP 
como MSDP agent
� Comunicación con TCP entre MSDP agent y sus MSDP 
peers por el puerto 639
� Cuando el MSDP agent detecta una nueva fuente envía un 
SA-message a todos sus MSDP peers accesibles 
directamente
� Inundación de mensajes MSDP:
– Los MSDP peers que reciben el mensaje hacen un RPF-check. 
Esto trata de evitar ciclos.
– Si pasa el RPF-check entonces hace un peer-RPF flooding
�Envía mensaje a todos sus peers excepto del que lo recibió
150Arquitectura de Redes - Universidad de Murcia
MSDP
Funcionamiento
� Si en un dominio el MSDP peer tiene creado estado de 
forwarding para algún miembro del grupo en su dominio, 
envía un Join hacia la fuente anunciada en el SA-message. 
Si no, ignora el mensaje.
� Si el SA-message llevaba consigo datos y hay miembros 
interesados, el RP los encamina por el árbol de distribución 
multicast.
� Una vez que los receptores reciben los datos pueden optar 
por pasarse al SPT según define PIM-SM.
151Arquitectura de Redes - Universidad de Murcia
MSDP
SA-message: Source Advertisement
RP Address
Reserved
Group Address
Source Address
Entry countCrtl info + Data LenType=1
SPref Len
Ctrl Info Len = Longitud de la información de control en el mensaje
Data Len 
= 0 -> No hay datos encapsulados
<> 0 -> distancia hasta el campo de tamaño total del 
paquete IPv4 encapsulado 
SPrefix Len = Longitud de la máscara asociada a la Source Address,
debe ser obligatoriamente 32
152Arquitectura de Redes - Universidad de Murcia
Ejemplo
PIM-SM/MBGP/MSDP
R
R
S
RP/MSDP/
BR
BR
RP/
MSDP
RP/
MSDP
BR
R
R
RP/
MSDP
BR
R
153Arquitectura de Redes - Universidad de Murcia
AS#1 AS#2
AS#3AS#4
Tenemos dos receptores en el AS1, que mandan IGMP report.
Ejemplo
PIM-SM/MBGP/MSDP
R
R
S
RP/MSDP/
BR
BR
RP/
MSDP
RP/
MSDP
BR
R
R
RP/
MSDP
BR
R
154Arquitectura de Redes - Universidad de Murcia
AS#1 AS#2
AS#3AS#4
Routers mandan PIM Join (*,G) al RP local, que crea estado de forwarding en
la red.
Ejemplo
PIM-SM/MBGP/MSDP
R
R
S
RP/MSDP/
BR
BR
RP/
MSDP
RP/
MSDP
BR
R
R
RP/
MSDP
BR
R
155Arquitectura de Redes - Universidad de Murcia
AS#1 AS#2
AS#3AS#4
Fuente S envía tráfico, su DR local envía un PIM-Register.
Ejemplo
PIM-SM/MBGP/MSDP
R
R
S
RP/MSDP/
BR
BR
RP/
MSDP
RP/
MSDP
BR
R
R
RP/
MSDP
BR
R
156Arquitectura de Redes - Universidad de Murcia
AS#1 AS#2
AS#3AS#4
Como hay receptores locales, el RP se une a la fuente con un PIM-Join. Manda el
tráfico desencapsulado a los receptores. Anuncia la nueva fuente al MSDP peer.
Ejemplo
PIM-SM/MBGP/MSDP
R
R
S
RP/MSDP/
BR
BR
RP/
MSDP
RP/
MSDP
BR
R
R
RP/
MSDP
BR
R
157Arquitectura de Redes - Universidad de Murcia
AS#1 AS#2
AS#3AS#4
MSDP peer hace RPF check de la fuente que se anuncia en el mensaje SA. Al
unirse los receptores se crea estado de forwarding en AS2 (igual en AS3).
Ejemplo
PIM-SM/MBGP/MSDP
R
R
S
RP/MSDP/
BR
BR
RP/
MSDP
RP/
MSDP
BR
R
R
RP/
MSDP
BR
R
158Arquitectura de Redes - Universidad de Murcia
AS#1 AS#2
AS#3AS#4
Como el MSDP-SA pasó el RPF check, el MSDP peer manda un Join al RP del AS1.
MSDP peer del AS2 inunda el mensaje MSDP-SA al resto de sus MSDP peers.
Ejemplo
PIM-SM/MBGP/MSDP
R
R
S
RP/MSDP/
BR
BR
RP/
MSDP
RP/
MSDP
BR
R
R
RP/
MSDP
BR
R
159Arquitectura de Redes - Universidad de Murcia
AS#1 AS#2
AS#3AS#4
De nuevo el RP envía el Join al RP original del AS1, y se crea también el árbol
entre AS2 y AS3.
Ejemplo
PIM-SM/MBGP/MSDP
R
R
S
RP/MSDP/
BR
BR
RP/
MSDP
RP/
MSDP
BR
R
R
RP/
MSDP
BR
R
160Arquitectura de Redes - Universidad de Murcia
AS#1 AS#2
AS#3AS#4
Igual que antes pero tras hacer el receptor de AS3 un SPT-switchover.
Bibliografía
� Básica
– Comer cap. 17
– Williamson, “Developing IP multicast networks Vol I”, 
Cisco Press, 2000, cap. 1-3 y 5-7.
� Complementaria
– J. Crowcroft et. al. “Internetworking multimedia”, Morgan 
Kaufman, 1999
– B. Cain, et. al. “Internet Group Management Protocol, 
Version 3”, IETF RFC 3376, Octubre 2002 
161Arquitectura de Redes - Universidad de Murcia