Unicast vs Multicast
Unicast
Host
Router
Multicast
Host
Router
1
Se gli host non sono collegati
tramite una rete broadcast (i.e.
ethernet), le operazioni di replica
possono essere particolarmenti
pesanti (tipicamente hw based);
se si pensa ad apparati di
accesso Internet si possono avere
anche decine di migliaia di host
Sorgente
multicast
Rete IP
multicast
IGMP
I router di accesso
gestiscono le richieste di
connessione ai gruppi da
parte degli host (IGMP)
I Router della rete multicast hanno
il compito di gestire il protocollo
per la creazione dell’albero di
distribuzione e il forwarding dei
pacchetti multicast
2
Indirizzi multicast
• Gruppo di indirizzi IP riservato per identificare i
gruppi multicast
–224.0.0.0–239.255.255.255
• Indirizzi di classe D;
–I bit più alti sono: “1110”
• Sottogruppo di indirizzi multicast riservati:
224.0.0.0–224.0.0.25:
–224.0.0.1 Tutti gli host di una sottorete
–224.0.0.2 Tutti i router di una sottorete
–224.0.0.5|6 OSPF
3
Mapping tra indirizzi multicast e ethernet
2^5 = 32 ind. Mcast mappati sullo stesso ind. ethernet
224-239
1
224
1110
0 1
0
138
10
0000
0
0000
5
Prefisso 24 bit IEEE
dedicato al multicast
E
0
1010
00
0000
1
0000
A 0
0000
0
0001
0
1
Ind. mcast
Ind. Ethernet
23 bit utilizzati per il
mapping
Riservato usi futuri
4
IGMP
 Fa parte del protocollo IP
 3 messaggi
 Membership Query
 Il router designato invia query verso 224.0.0.1 (tutti gli host
della rete) con timetolive = 1 (il messaggio non va oltre la rete
locale)
 Su una LAN c’è un solo router “designato”
 “Query interval” viene scelto considerando le necessità di
interazione (tempo di zapping) e di limitazione del traffico di
segnalazione
 Membership Report
 Inviato dagli host (prima di inviare una risposta gli host
aspettano un tempo casuale: se si accorgono che un altro host
ha già inviato un report, desistono)
 Il report può essere “spontaneo”; ciò accade quando l’host si
connette ad un gruppo multicast la prima volta
Leave
5
Pacchetti IGMPv2
7
Type
15
Max. Resp.
Time
31
Checksum
Group Address
Type:
0x11 = Membership Query
0x12 = Membership Report (v.1)
0x16 = Membership Report (v.2)
0x17 = Leave
Max. Resp. Time
tempo max entro cui il router si aspetta una risposta
viene usato dagli host come limite max nella scelta
random del tempo di risposta (Default = 10 secs)
Group Address:
Indirizzo del gruppo multicast
(0.0.0.0 indica una query di tipo generale…any group)
6
Join asincrona
1.1.1.10
H1
1.1.1.11
224.1.1.1
1.1.1.12
H2
H3
Report
1.1.1.1
rtr-a
•
•
•
•
H2 effettua una join asincrona
Invia un report senza aver ricevuto una query
Riduce la latenza (query cicliche)
Rtr-a mantiene attivo il gruppo fino allo scadere di un timer che
viene resettato da successivi nuovi report
7
Meccanismo di elezione
1.1.1.10
1.1.1.11
1.1.1.12
H1
H2
H3
Query
1.1.1.2
IGMP
Non-Querier
1.1.1.1
IGMP
Querier
IGMPv2
rtr-b
Query
rtr-a
• Inizialmente tutti i router inviano query
• Ogni router legge le query inviate dagli altri host
• Il router con l’IP più basso viene eletto (gli altri non inviano più
query)
• Se scade un time-out (router eletto non ha inviato query) riparte
il processo di elezione (meccanismo di recovery)
8
Soppressione delle risposte
1.1.1.10
224.1.1.1
H1
1.1.1.11
224.1.1.1
H2
1.1.1.12
224.1.1.1
X
Suppressed
H3
X
Report
Suppressed
1.1.1.1
Query
• Il router invia query periodiche
• Gli host settano un timer tra [0,max resp timer]
• Se scade il timer invia il report; se invece riceve un report sopprime il
timer e non invia alcun report
• Nella figura, H1 e H3 non inviano report
9
Leave
1.1.1.10
1.1.1.11
224.1.1.1
1.1.1.12
224.1.1.1
H3
H2
H1
Leave to
#1 224.0.0.2
Report to
#3 224.1.1.1
1.1.1.1
rtr-a
Group Specific
Query to 224.1.1.1
#2
• H2 lascia il gruppo; manda un messaggio Leave relativo al gruppo
224.1.1.1 a tutti i router della rete (224.0.0.2)
• Il router manda una query specifica verso tutti gli host che sono in
ascolto su 224.1.1.1
• H3 che è ancora in ascolto manda un report su 224.1.1.1
• Il router continua ad inviare traffico sul gruppo 224.1.1.1
10
Leave …continua
H1
224.1.1.1 1.1.1.12
H3
1.1.1.11
H2
Leave to
#1 224.0.0.2
rtr-a
Group Specific
Query to 224.1.1.1
#2
• L’ultimo host attivo sul gruppo manda un Leave
• Il router invia una query specifica
• Scade il max-resp-timer
• Il router cancella il gruppo
11
IGMP v3
Source = 1.1.1.1
Group = 224.1.1.1
Source = 2.2.2.2
Group = 224.1.1.1
R2
R1
• H1 vuole ricevere
il gruppo da S =
1.1.1.1 ma non da
S = 2.2.2.2
R3
• R3 può effettuare
il prune della
sorgente S =
2.2.2.2
IGMPv3:
Join 1.1.1.1, 224.1.1.1
Leave 2.2.2.2, 224.1.1.1
H1
12
Flooding del traffico multicast su apparati di
livello 2 (e.g. switch)
PIM
• Gli apparati di livello 2 tipicamente non
sanno come trattare il traffico multicast e si
limitano ad effettuare un broadcast verso tutte
le interfacce.
Multicast M
13
Trattamento del traffico multicast su apparati di
livello 2 (e.g. switch)
• Gli apparati di livello 2 (e.g. switches) devono
essere “IGMP” aware.
PIM
• I pacchetti IGMP vengono intercettati da
hardware specializzato ASICs (IGMP snooping)
• Lo switch deve esaminare i messaggi IGMP
Report e Leave associandogli alle specifiche
porte
• Inoltre deve effettuare il “Proxy” dei messaggi
verso il router ( possibilmente filtra i messaggi,
join successivo al primo, leave quando ci sono
altri host in ascolto sul gruppo)
IGMP
IGMP
14
Algoritmi di routing multicast
• Flooding: inoltrno dei pacchetti ricevuti su tutte le interfacce
quando il pacchetto è ricevuto per la prima volta
– Non prevede l’utilizzo di alcun protocollo di instradamento
– Non utilizza le informazioni sull’attività degli host
– Richiede di tener traccia di tutti i pacchetti ricevuti
• Spanning tree
– Consente di trasmettere il traffico multicast senza incorrere in loop
– Non utilizza le informazioni sull’attività degli host
– Utilizzo non ottimizzato della rete
• Reverse Path Forwarding (spiegato in dettaglio in seguito)
• Shortest path tree
15
Protocolli multicast
• Prevedono lo scambio di opportuni messaggi tra i router;
tali messaggi forniscono le informazioni necessarie al
trattamento dei pacchetti multicast agli algoritmi di
instradamento
• Tipi di protocollo multicast: PIM (Protocol Indipendent
Multicast)
•Indipendent perché utilizza le informazioni di routing fornite da protolli
di unicast esterni qualsiasi
•PIM Dense Mode
•PIM Sparse Mode
• I concetti su cui si basa sono:
–Multicast Distribution Trees
–Multicast Forwarding
16
Multicast Distribution Trees
Shortest Path o Source Distribution Tree
Source
Notation: (S, G)
S = Source
G = Group
A
B
C
Receiver 1
F
D
E
Receiver 2
17
Multicast Distribution Trees
Shared Distribution Tree
Sorgente 1
Notation: (*, G)
* = All Sources
G = Group
A
B
C
Ricevitore 1
D
F
(Shared Root)
Sorgente 2
E
Ricevitore 2
18
Forwarding Multicast
 Logica inversa rispetto al Routing Unicast
Routing Unicast analizza IP_Destinazione
Routing Multicast analizza IP_Source e applica
il “Reverse Path Forwarding”:
 IP_source è l’indirizzo da cui proviene la
trasmissione multicast
IP_destinazione è il gruppo multicast
 RPF: consente di evitare le duplicazioni scegliendo
l’interfaccia da cui ricevere il traffico multicast (su tutte
le altre è scartato); l’interfaccia scelta è quella che si
userebbe per inviare traffico verso la sorgente (tabella
di routing unicast)
19
RPF
Sorgnte mcast
151.10.3.21
S0
S1
Router con comportamento anomalo
Mcast Dist. Tree
Pacchetti Mcast
S2
E0
RPF Check Fallisce: il
traffico è scartato
20
Check RPF che fallisce
X
Pacchetto multicast con
IP sorgente 151.10.3.21
S0
RPF Check Fails!
Multicast Route Table
Network
Interface
151.10.0.0/16
S1
198.14.32.0/24 S0
204.1.16.0/24
E0
S1
S2
E0
Pacchetto arrivato da una interfaccia
sbagliata (verrà scartato)
21
Check RPF che ha successo
Pacchetto multicast con
IP sorgente 151.10.3.21
S0
S1
S2
E0
Multicast Route Table
Network
Interface
151.10.0.0/16
S1
198.14.32.0/24 S0
204.1.16.0/24
E0
Il pacchetto arriva dall’interfaccia
corretta e viene forwardato su tutte le
altre interfacce (distribution tree)
22
Tipi di protocollo multicast
• Differiscono dal modo in cui costruiscono e gestiscono il distribution
tree (DT)
• Dense-mode (si assume un’alta densità di ricevitori)
 Inizialmente effettua il flooding, i router non interessati chiedono di
essere rimossi dal DT (prune)
 quando un ramo viene tagliato viene più inviato traffico
 dopo un tempo prestabilito, il ramo tagliato riceve nuovamente traffico e il
router deve eventualmente richiedere il prune
• Sparse-mode (si assume che solo alcune zone saranno interessate alla
trasmissione)
 I router interessati devono fare richiesta esplicita (join) per essere aggiunti
al DT
 Usa lo shared distribution tree ma al superamento di soglie prefissate i
router possono comandare la costruzione di un source distribution tree
23
Pacchetti PIM Join/Prune
Sia il DM sia lo SP usano pacchetti di segnalazione per aggiungere o
togliere dei rami dal distribution tree; tali pacchetti contengono un
elenco di gruppi multicast (multicast group) ciascuno dei quali
contiente a sua volta una lista di sorgenti su cui fare Join o Prune
Gruppo n
JOIN ( Sorgente 1, Sorgente 2,…) ----- (S;G)
Gruppo k
PRUNE ( *, RP)
---- (*,G)
Gruppo m
JOIN (*, RP)
---- chiede che la Join venga propagata fino
allo shared root/rendevouz point
(per default sarebbe propagata fino
alla sorgente)
24
PIM DM: flooding
Pacchetto multicast
(128.9.160.43, 224.2.127.254)
S0
S3
“rtr-a” inoltra il traffico (S, G)
su tutte le interfacce (tranne
quella da cui lo ha ricevuto)
S1
rtr-a
S0
rtr-b
E1
A questo punto su rtr-a esistono due entry: per (*, G) e (S, G)
• (*, 224.2.127.254) con interfacce di uscita S1 e S3
• (128.9.160.43, 224.2.127.254) con interfacce di uscita S1 e S3
La entry, (*, G) è creata appena si riceve un pacchetto da qualsiasi sorgente
per G opprure quando si riceve una richiesta di connessione al gruppo
25
(JOIN IGMP) da un host locale
PIM DM: prune
S0
S3
S1
rtr-a
Prune (S,G)
S0
rtr-b
E1
Rtr-b non ha ricevitori, quindi invia un messaggio di prune (S,G)
A questo punto su rtr-a nella entry (128.9.160.43, 224.2.127.254)
l’interfaccia S0 viene messa in stato di prune; ma è solo sospesa per un
tempo fissato (e.g 3 min) dopo di che ritorna in stato di forward
26
PIM DM: Grafting
Pacchetti (S,G)
S0
3 PIM Graft-ACK
2
PIM Graft
E0
S1
rtr-a
4
E0
rtr-b
E0
rtr-c
E1
A
E1
IGMP Join 1
1• A invia una JOIN per il gruppo G.
• “rtr-b” invia un messaggio PIM Graft per il gruppo (S,G) verso
2
rtr-a
3
• “rtr-a” invia un riscontro (PIM Graft-Ack)
4
• “rtr-a” inizia a tramettere il traffico per (S,G).
27
PIM SM: Forwarding
RP
(10.1.5.1)
Shared Tree
Pacchetti Multicast
(128.9.160.1, 224.1.1.1)
S1
S0
rtr-a
Source Tree
Pacchetti Multicast
(128.9.160.43, 224.1.1.2)
E0
E0
rtr-b
E1
Route
10.1.5.0/24
10.1.2.0/24
128.9.0.0/16
Intfc
S0
E0
S1
Tabella di routing unicast
• Nel protocollo Sparse mode il check RPF usa:
• l’indirizzo del RP, nel caso di shared trees
• l’indirizzo sorgente nel caso di shortest-path tree
28
PIM SM: Forwarding
 Quando un router riceve un pacchetto multicast per il gruppo G lo
inoltra su un’altra interfaccia se:
 ha ricevuto un pacchetto di JOIN PIM per il gruppo G su quella
interfaccia da un router adiacente
 un host su quella interfaccia ha inviato una richiesta IGMP per il
gruppo G
Al contrario del dense mode, i router PIM-SM assumo che non ci sono
ricevitori interessati al gruppo in assneza di JOIN esplicite
 Al contrario del DM, i router a valle del RP rispetto alla sorgente non si
devono preocuppare dell’indirizzo sorgente dei pacchetti multicast perché
tutto il traffico passa per i RP (infatti il check RFP è fatto sull’indirizzo IP del
RP)
I router a valle del RP mantengono lo stato (*,G)
I router tra la sorgente e il RP mantengono lo stato (S,G)
29
PIM SM: costruzione del distribution tree
(caso in cui il ricevitore si registra per primo su RP)
Il router sorgente invia il primo
pacchetto multicast che riceve in un
pacchetto unicast di registrazione
verso RP (register);
S
RS
R1
Quando RP riceve il primo
pacchetto multicast completa
il processo di registrazione
RP
RP chiede
di costruire
I router
sul percorso
S-RPil DT
join(S,G) la join e creano
intercettano
R2
le entry (S,G) mettendo in
stato di forward l’interfaccia
invia una join (*,G)
da cui è arrivata laR4
join
verso RP
R4 crea l’entry (*,G) e
mette in forward
l’interfaccia verso RCR
R3
R4
RECEIVER
I router R3, R2 intercettano
le join e creano le entry
(*,G) mettendo le interfacce
da cui ricevono la join in
stato di forward
Il ricevitore chiede di
ascoltare il gruppo (*,G)
tramite messaggio IGMP;
30
PIM SM: creazione del distribution tree
(caso in cui la sorgente si registra per prima su RP)
S
RS
R1
4 RP manda un messaggio prune (S,G)
verso
lo stato
ignora(*,G)
in quanto
3.R1
RP(che
non però
ha uno
e quindi
anch’esso
ha il gruppo G attivo
scarta non
il pacchetto
RP
RP(*,G)
inviae (S,G)
un msg
register
1. S invia il2.primo
RS crea lo5stato
e incapsula
il
pacchetto mcast
pacchetto
mcast
in a
unRS
messaggio
stop
6 RS riceve
il register
stop e nonunicast
inoltraPIM register
Inverso
questo
momento R1 vede attivo il gruppo (S,G)
più iRP
pacchetti mcast ricevuti da S in
perché ha ricevuto un prune da RP ma non ha
pacchetti
unicast
register
(RS
non
è R4
interfacce
attive,
anche
RP
ha
il gruppo
(S,G)
ma un
78RP
riceve
un di
PIM
join
(*,G)
da
RP
cerca
tutte
le
entry
(S,G)
e
invia
Fino
anello
questo
momento
RS ha
attivato lo
stato
di(non
registering)…cancella
nonpiù
interfacce
attive
cigruppo
sono
ricevitori
(RCR
ha
chiesto
il
G)
join
le sorgentietrovate
stato
(S,G)
è inverso
statotutte
“registering”
non
loPIM
stato
(S,G)
connessi)
ha interfacce di forward attive poiché non
ha ricevuto nessuna join
R4
Receiver
R2
R3
R2-R3,R4
intercettano la
join e creano il
distribution
tree
31
PIM SM: pruning del distribution tree
S
RS
R1
RP
R2 intercetta il messaggio,
l’interfaccia
dal DT
R3rimuove
intercetta
il messaggio
RCR lascia
il inoltra
gruppo ilGmessaggio
(leave IGMP);
ma non
prune
e rimuove
l’ interfaccia
R4 cancella l’interfaccia verso RCR dal
dal DT
ouil del gruppo G.
Poiché non ha altre interfacce
Poiché R4 non ha altre interfacce attive
attive inoltra il messaggio di
per il gruppo G, invia un messaggio di
prune verso RP
prune (*,G) verso il RP
R2
Rec. 2
R3
R4
R4 ha un solo ricevitore attivo sul
gruppo G
Receiver
32
Source Specific Multicast
• Utilizzato quando le sorgenti sono poche e
ben definite (e.g. head end di trasmissioni
TV)
• Prevedono l’utilizzo del protocollo IGMP
v3
• Permette una notevole semplificazione dei
processi dei router
33