PROTOCOLLI MULTICAST Dario Maggiorini [email protected].

51
PROTOCOLLI MULTICAST Dario Maggiorini [email protected]

Transcript of PROTOCOLLI MULTICAST Dario Maggiorini [email protected].

Page 1: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

PROTOCOLLIMULTICAST

Dario Maggiorini

[email protected]

Page 2: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

MULTICAST

Nuovo modello di comunicazione

Trasmissione di dati punto-multipunto

Definisce gruppi dinamici

Page 3: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

Nuove tipologie di comunicazione

Diffusione dati “pubblici”Video broadcasting

Radio su Internet

Teleconferenza

Page 4: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

Comunicazione punto-multipunto

Molti … ma non tutti

Page 5: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 6: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

Cosa deve fare un protocollo multicast

Costruire un albero di distribuzione dei dati (routing)

Garantire l’arrivo delle informazioni a destinazione

Gestire i gruppi

Page 7: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

Livelli ISO-OSIper il multicast

data link 2 LAN multicast

network 3 IP multicast

physical link 1 link layer multicast

Page 8: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 9: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

Diventa compito del livello di routing multicast mascherare queste situazioni in maniera trasparente

ethernet

tokenringATM

MulticastServer

Page 10: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 11: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

Multicast routing

Shortest path tree

Distant vector

Link state

Minimum cost tree

Minimum spanning tree

Minimum steiner tree

Constrained tree

Page 12: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

Multicast routing

Altre cose di cui tenere conto

La topologia di rete

La distribuzione geografica degli utenti (tutti)

La densita’ degli utenti sul “territorio”

Page 13: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

La tecnologia di rete e la distribuzione degli utenti influenzano pesantemente le strategie utilizzate per la sua costruzione

??

Page 14: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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”

Page 15: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

IP multicast

Si definisce una classe di indirizzi virtuali detta “classe D”Ad ogni indirizzo in classe D corrisponde un multicast groupE’ compito di chi riceve richiedere l’iscrizione ad un gruppoIl managing dei gruppi e degli alberi viene fatto con un protocollo esterno: IGMP

Page 16: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

1110

1110

Page 17: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

Distribuzione locale di IP multicast

Ci si appogga su frame Ethernet

E’ possibile utilizzare questi ultimi sia in modalita’ broadcast the multicast

Page 18: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 19: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

IP multicast e Ethernet multicastSi e’ scelto allora di mappare solo un sottoinsieme di indirizzi

E’ compito del modulo software che gestisce IP filtrare

pacchetti destinati alle sottoreti “duplicate”

1110 xxxx x yyyy yyyyyyy yyyy yyyy yyyy

0000 0001 0000 0000 0101 1110 0 yyyy yyyyyyy yyyy yyyy yyyy

MAC

IP

Page 20: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

IP multicastdistribuzione 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

Page 21: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 22: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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”

Page 23: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

IGMPInternet 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

Page 24: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 25: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 26: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 27: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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)

Page 28: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

DVMRPDistance 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

Page 29: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 30: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

PIMProtocol 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

Page 31: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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)

Page 32: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 33: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 34: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 35: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

PIM – elementi costitutivi

RP

s1

s2

s3

s4

LHR1

DR2

DR3

DR4

s5

DR1

LHR3

LHR2

r1

r2

r6

r4

r5

r3

r0

unicast

multicast

BSR

Page 36: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

PIM - creazione dell’alberoLato 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

Page 37: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

PIM - creazione dell’alberolato 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

Page 38: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

PIM - creazione dell’alberolato sorgente

Se tale albero non esisteviene creato un albero avente come radice il RP e come foglie tutti gli host in ascoltoViene forwardato su tutto l’albero il pacchetto di RequestI router per cui il pacchetto transita creano all’interno delle loro tabelle delle entry di collegamento diretto tra LHR del ricevente e DR della sorgenteAlla creazione di tale entry i riceventi mandano un messaggio di Join verso la sorgenteIl risultato di questo e’ la “trasformazione” dell’albero avente radice il RP con un albero a cammino minimo tra il DR e gli LHR

Page 39: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 40: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 41: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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 gruppoUna entry con riferimento al gruppo e una qualsiasi sorgenteUna 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

Page 42: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

PIM – distribuzione dei dati

In caso di esito positivoViene presa in considerazione la entry trovataSe 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 tabellaIn caso contrario viene scartato

NOTA: le cose si complicano parecchio se un pacchetto viene instradato mentre si compie la transizione di stato dell’albero

Page 43: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

PIM – reti ad accesso multiplouna 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

Page 44: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

HPIMHierarchical 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

Page 45: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 46: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 47: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

MBoneMulticast 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

Page 48: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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

Page 49: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

MBone

?

MRouter

isole multicast

Internet unicast

tunnel

backup tunnel

Page 50: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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 modiUn host su cui gira un software chiamato mrouted

Un apparecchiatura di rete in grado di gestire tunnel di Mbone tramite software interno

Page 51: PROTOCOLLI MULTICAST Dario Maggiorini dario@dsi.unimi.it.

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