PROTOCOLLI
MULTICAST
Dario Maggiorini
[email protected]
MULTICAST
Nuovo modello di comunicazione
Trasmissione di dati punto-multipunto
Definisce gruppi dinamici
Nuove tipologie di
comunicazione
Diffusione dati “pubblici”
Video broadcasting
Radio su Internet
Teleconferenza
Comunicazione punto-multipunto
Molti … ma non tutti
Gruppi dinamici
Si introduce la nozione di “gruppo multicast”
E’ possibile aggiungersi o togliersi in
qualunque momento dal gruppo
Questa dinamicita’ permette di continuare ad
operare anche con interruzioni del servizio di
rete
Cosa deve fare un protocollo
multicast
Costruire un albero di distribuzione dei dati
(routing)
Garantire l’arrivo delle informazioni a
destinazione
Gestire i gruppi
Livelli ISO-OSI
per il multicast
network
3
IP multicast
data link
2
LAN multicast
physical link
1
link layer multicast
Tecnologie di rete e multicast
nativo
Alcune tecnologie supportano multicast in
maniera nativa
Ethernet
Altre invece non lo supportano affatto
Token ring
FDDI
Altre ancora hanno bisogno di supporti esterni
ATM
Diventa compito del livello di routing
multicast mascherare queste situazioni in
maniera trasparente
ethernet
token
ring
ATM
Multicast
Server
Multicast routing
Vuol dire costruire l’albero piu’ “conveniente” per
la distribuzione dei dati nella rete data la sorgente
e i destinatari da raggiungere
Esistono algoritmi specializzati
Shortest path
Minimum cost
Constrained tree
Multicast routing
Shortest path tree
Distant vector
Link state
Minimum cost tree
Minimum spanning tree
Minimum steiner tree
Constrained tree
Multicast routing
Altre cose di cui tenere conto
La topologia di rete
La distribuzione geografica degli utenti (tutti)
La densita’ degli utenti sul “territorio”
La tecnologia di rete e la distribuzione degli
utenti influenzano pesantemente le strategie
utilizzate per la sua costruzione
?
Disposizione degli utenti e tecniche di
distribuzione dei dati
Individuiamo due tecniche
Data replication
su un punto di distribuzione “replico” i dati e
mando un pacchetto separato ad ogni destinatario
Flooding
mando pacchetti broadcast per servire tutti gli
utenti in “un colpo solo”
IP multicast
Si definisce una classe di indirizzi virtuali
detta “classe D”
Ad ogni indirizzo in classe D corrisponde
un multicast group
E’ compito di chi riceve richiedere
l’iscrizione ad un gruppo
Il managing dei gruppi e degli alberi viene
fatto con un protocollo esterno: IGMP
Indirizzi in classe D
Contengono il valore 1110 in corrispondenza
dei 4 bit piu’ significativi
1110 0000 0000 0000 0000 0000 0000 0000
1110 1111 1111 1111 1111 1111 1111 1111
Distribuzione locale di
IP multicast
Ci si appogga su frame Ethernet
E’ possibile utilizzare questi ultimi sia in
modalita’ broadcast the multicast
IP multicast e ethernet multicast
Occorre mappare un indirizzo in classe D su di un
indirizzo MAC multicast.
Questo pero’ non e’ possibile, dato il range dei
multicast MAC
01:00:5e:00:00:00
01:00:5e:07:ff:ff
IP multicast e Ethernet multicast
Si e’ scelto allora di mappare solo un sottoinsieme di indirizzi
IP
1110 xxxx
x
yyy yyyy
yyyy yyyy
yyyy yyyy
0000 0000
0101 1110
0
yyy yyyy
yyyy yyyy
yyyy yyyy
MAC
0000 0001
E’ compito del modulo software che gestisce IP filtrare
pacchetti destinati alle sottoreti “duplicate”
IP multicast
distribuzione su piu’ sottoreti
L’albero di distribuzione viene creato attraverso
un algoritmo chiamato reverse path forwarding
(RPF)
La distribuzione su ogni singola sottorete viene
fatta secondo criteri locali.
Nel caso di Ethernet multicast sono i vari router
che si occupano di riassegnare gli accoppiamenti
di indirizzi MAC-IP
Reverse path forwarding
Si punta a costruire un albero dove la distanza in
termini di hop tra sorgente e destinazione sia
minima
Per fare questo si ricorre al flooding e lo si limita
applicando la seguente regola su ogni router
se un pacchetto viene ricevuto su di una interfaccia
che il router utilizza per mandare pacchetti a chi
spedisce, solo allora il pacchetto verra’ ridistribuito
sulle tutte altre interfacce, altrimenti verra’ scartato
Reverse path forwarding
Utilizza le informazioni di routing unicast gia’
note
Costruisce un nuovo albero ad ogni pacchetto (si
adatta alle interruzioni di rete)
Non tiene in considerazione i gruppi, questo lo
rende piu’ un algoritmo per la costruzione di un
“broadcast tree”
IGMP
Internet Group Management Protocol
E’ un protocollo di contrattazione usato tra un host
ed il suo router
Un host informa il router di voler far parte di un
certo multicast group
Il router memorizza solo informazioni locali alla
sua sottorete
In tale modo il router diventa responsabile del
gruppo all’interno della sottorete
IGMP
Il router manda periodicamente dei broadcast sulla
rete IGMP Host-membership Query
Se ci sono host iscritti ad un qualsiasi gruppo
questi aspettano un tempo casuale e poi mandano
un messaggio IGMP Host-membership Report al
loro gruppo
IGMP
Questo ha due finalita’:
Il router (che e’ iscritto a tutti i gruppi) sa che ci sono
degli iscritti a un certo gruppo
Gli altri host appartenenti allo stesso gruppo resettano i
loro timer riducendo il carico di rete
Truncated broadcasting
Utilizza le informazioni di raccolte da IGMP e
migliora le prestazioni di RPF introducendo la
nozione di gruppo nel flooding controllato
Un pacchetto viene trasmesso su di una
sottorete se e solo se vi sono host appartenenti
a quel gruppo
Algoritmi di routing a livello di rete
Distance vector Multicast Routing Protocol
(DVMRP)
Hierarchical DVMRP (H-DVMRP)
Multicast Open Shortest Path First (MOSPF)
Protocol Independent Multicast (PIM)
Hierarchical PIM (H-PIM)
Core-Based Tree (CBT)
Ordered CBT (OCBT)
Border Gateway Multicast Protocol (BGMP)
Multicast Backbone of the Internet (MBONE)
DVMRP
Distance Vector Multicast Routing Protocol
Si basa sul concetto di “distance vector” come il
RIP (Routing Information Protocol)
Implementa truncated broadcasting utilizzando un
meccanismo detto pruning
DVMRP
Siccome ogni router ha informazioni sulle
appartenenze ai vari gruppi e’ in grado di
determinare se un pacchetto in arrivo e’ utile o meno
alla sua sottorete
Se non ci sono iscrizioni al gruppo indicato viene
mandato un messaggio prune ai router limitrofi
Tale messaggio non viene mandato sull’interfaccia
corrispondente al percorso verso la sorgente, a meno
che lo stesso messaggio non venga ricevuto su tutte
le altre interfacce
PIM
Protocol Independent Multicast
E’ in grado di funzionare utilizzando un qualunque
protocollo di routing unicast come supporto
Puo’ essere utilizzato per routing sia inter-domain
che extra-domain
Se usato come extra-domain allora riesce ad
interoperare con qualsiasi altro protocollo usato
inter-domain
PIM
Distingue tra nodi a sola ricezione e nodi a solo
invio
Prevede due modalita’ di funzionamento:
Sparse Mode (PIM-SM)
Dense Mode (PIM-DM)
PIM: DM e SM
DM: progettato ed ottimizzato per reti densamente
popolate da utenti di un certo gruppo, viene fatto
uso di flooding
SM: progettato per reti scarsamente popolate, si
utilizza data-replication
La modalita’ di funzionamento e’ impostata al
setup della rete, non esistono ancora metodi per
passare dinamicamente da una all’altra
PIM – elementi costitutivi
Randezvous point (RP)
E’ il punto di ingresso all’albero di distribuzione, sia per
iscriversi a un gruppo che per inviare dati
E’ relativo a uno specifico gruppo multicast
Esiste solo in SM
Ridistribuisce i dati tramite un albero monodirezionale
Designed router (DR)
E’ il router direttamente connesso con l’host che invia dati
Generalmente, e’ comune a tutta la sottorete
PIM – elementi costitutivi
Last Hop Router (LHR)
Il router direttamente connesso con l’host che riceve i
dati
Si occupa della distribuzione multicast sulla sottorete di
destinazione
In generale per le LAN DR coincide con LHR, ma
questo non e’ necessariamente sempre vero
Boot Strap Router (BSR)
Il router rsponsabile della creazione dei DR e dei RP
PIM – elementi costitutivi
BSR
s1
r0
multicast
DR1
LHR1
s2
r1
DR2
RP
s3
r2
LHR2
DR3
r3
s4
LHR3
DR4
r4
s5
unicast
r6
r5
PIM - creazione dell’albero
Lato ricevente
Un host notifica al suo DR che intende partecipare
a un certo gruppo
Il DR rintraccia il RP opportuno per quel gruppo
Il DR manda un messaggio di Join al RP
Il percorso effettuato dal messaggio di join nei
router intermedi determina il ramo dell’albero di
distribuzione dal RP alla sottorete (LHR) di cui fa
parte l’host che si e’ iscritto
PIM - creazione dell’albero
lato sorgente
Un host notifica al suo DR che intende partecipare
a un certo gruppo
Il DR rintraccia il RP opportuno per quel gruppo
Il DR forwarda il messaggio di Register dell’host
al RP
Il RP riceve il messaggio e valuta se esiste gia’ un
albero di distribuzione per il gruppo a cui fa
riferimento l’host che vuole trasmettere
PIM - creazione dell’albero
lato sorgente
Se tale albero non esiste
viene creato un albero avente come radice il RP e come
foglie tutti gli host in ascolto
Viene forwardato su tutto l’albero il pacchetto di
Request
I router per cui il pacchetto transita creano all’interno
delle loro tabelle delle entry di collegamento diretto tra
LHR del ricevente e DR della sorgente
Alla creazione di tale entry i riceventi mandano un
messaggio di Join verso la sorgente
Il risultato di questo e’ la “trasformazione” dell’albero
avente radice il RP con un albero a cammino minimo
tra il DR e gli LHR
PIM - gestione dell’albero
L’albero di distribuzione di un certo gruppo deve
rimanere stabile anche in caso di:
Cambiamenti della topologia di rete
Cambiamenti di stato di un host improvvisi (crash e
reboot)
Cambiamenti di stato di un router
Timeout
PIM - gestione dell’albero
Per garanire questo PIM basa il suo funzionamento
su stati software sui router
Periodicamente vengono inviati messaggi di Join e
Prune per evitare timeout sulle tabelle
Allo scadere di un timeout un ramo dell’albero che
non si e’ mai “fatto sentire” viene eliminato dalle
tabelle di distribuzione
PIM – distribuzione dei dati
Quando un pacchetto contenente informazioni
arriva ad un router (DR) questo cerca nell’ordine
una delle seguenti corrispondenze all’interno delle
sue tabelle:
Una entry con riferimento alla sorgente e al gruppo
Una entry con riferimento al gruppo e una qualsiasi
sorgente
Una entry con riferimento ad un RP corrispondente
all’indirizzo di destinazione e qualsiasi sorgente e
gruppo
In caso di esito negativo il pacchetto viene scartato
PIM – distribuzione dei dati
In caso di esito positivo
Viene presa in considerazione la entry trovata
Se l’interfaccia dalla quale ci si aspettava i dati
corrisponde con quella da cui effettivamente il
pacchetto e’ arrivato questo viene instradato
sull’interfaccia di uscita in tabella
In caso contrario viene scartato
NOTA: le cose si complicano parecchio se un
pacchetto viene instradato mentre si compie la
transizione di stato dell’albero
PIM – reti ad accesso multiplo
una serie di accorgimenti deve essere presa se
esistono piu’ accessi concorrenti alla rete
Elezione esplicita del DR responsabile per una
sottorete
Un sistema per la determinazione di cammini unici
quando piu’ di un percorso e’ disponibile
Soppressione di messaggi Join e Prune nel caso vi
siano messaggi di controllo duplicati
HPIM
Hierarchical PIM
Viene utilizzato per sopperire a problemi di cui
PIM e’ affetto in caso distribuzione non ottimale
dei RP
Nel caso di utenti molto sparsi il PIM potrebbe
scegliere RP non ottimali
I dati seguono lo stesso percorso dei pacchetti di
controllo, nel caso di percorsi non ottimali tra RP
questo peggiora le performances anche nel
trasferimento dei dati
HPIM
I RP vengono organizzati in una gerarchia
attribuendo ad ognuno un numero (livello).
Piu’ alto il livello e piu’ grande e’ l’area competente
ad un RP
I DR sono considerati essere RP di livello 0
HPIM
Nel momento in cui un host chiede di far parte di un
certo gruppo vi richiesta di Join viene fatta risalire
fino al RP di livello massimo, dopo di che si instaura
tra i RP intermedi un sistema come quello tra DR e
LHR per la creazione di percorso ottimale dei dati
MBone
Multicast Backbone of the Internet
E’ una rete vituale che affronta il problema di
fare multicast su Internet in un momento in cui
non tutti i router installati sono in grado di
supportare multicast
MBone
Vengono costruite delle “isole” periferiche dove
multicast viene supportato con un qualsiasi
protocollo noto
La comunicazione tra le varie isole avviene
attraverso dei collegamenti (tunnel) nei quali viene
fatto circolare multicast IP incapsulato in IP classico
L’accoppiamento piu’ utilizzato e’ multicast IP o
DVMRP per isole piccole e PIM-SM per isole
medio-grandi
MBone
MRouter
isole multicast
Internet
unicast
?
tunnel
backup tunnel
Mbone - MRouter
E’ il punto terminale di un tunnel
Si occupa di decapsulare il protocollo multicast da
IP unicast e distribuirlo sulla rete locale
Puo’ essere realizzato in due modi
Un host su cui gira un software chiamato mrouted
Un apparecchiatura di rete in grado di gestire tunnel di
Mbone tramite software interno
Mbone - topologia
Si compone di un misto di topologie stellari e ad
albero
Le reti cosiddette “regionali” sono collegate da
una ragnatela fitta e caotica di tunnel
Internamente una rete regionale e’ normalmente
organizzata ad albero
All’interno delle reti regionali vi sono delle isole
piu’ piccole delle singole organizzazioni,
tipicamente organizzate con topologia stellare