Protocolli e architetture di instradamento/Instradamento multicast

Il multicast è la possibilità di trasmettere la medesima informazione a più utenti finali senza essere costretti ad indirizzare questi ultimi singolarmente e senza avere, quindi, la necessità di duplicare per ciascuno di essi l'informazione da diffondere.

L'instradamento multicast si occupa di decidere e propagare le informazioni necessarie per inoltrare i pacchetti multicast al di fuori delle reti locali fra più multicast router (mrouter) interconnessi nella rete:

1. determinazione dell'esistenza di ricevitori su un particolare segmento di LAN: nel caso non esistano ricevitori, non è il caso di inoltrare quei pacchetti sulla LAN → le reti che non hanno ricevitori vengono tagliate dall'albero (pruning);
2. propagazione dell'esistenza e della localizzazione dei ricevitori nell'intera rete IP: l'instradamento multicast deve tenere traccia della localizzazione dei vari ricevitori, creando un "albero ricoprente", detto albero di distribuzione, in modo da minimizzare i costi e recapitare i pacchetti a tutti;
3. trasmissione e inoltro dei dati: i trasmettitori generano i pacchetti con un indirizzo di destinazione particolare multicast, e gli mrouter li inoltrano lungo l'albero di distribuzione fino ai ricevitori.

Gli algoritmi di instradamento multicast usano due tipi di alberi di distribuzione:

• albero specifico della sorgente (RPB, TRPB, RPM, Link State): c'è un albero per ogni mittente → i percorsi sono ottimali, ma l'aggiornamento è più complesso;
• albero condiviso (CBT): c'è un albero per ogni gruppo multicast, valido per tutti i mittenti → l'aggiornamento è più semplice, ma i percorsi non sono ottimali.

Algoritmi di instradamento multicast

• flooding selettivo
• Distance Vector:
  • reverse path forwarding (RPF)
  • reverse path broadcasting (RPB)
  • truncated reverse path broadcasting (TRPB)
  • reverse path multicasting (RPM)
• Link State
• core-based tree (CBT)
• gerarchici

Instradamento multicast Distance Vector

Reverse path forwarding

Quando un router riceve un pacchetto multicast, lo invia su tutte le altre interfacce, a patto che quella da cui è arrivato sia sul cammino più breve tra il router e la sorgente.

Problemi

• traffico: carica la rete in modo inaccettabile:
  • nessun albero di instradamento: su una LAN possono transitare più copie dello stesso pacchetto se due router collegati alla LAN hanno la stessa distanza minima dalla sorgente;
  • nessun pruning: il pacchetto viene sempre distribuito su tutti i link, senza tenere conto del fatto che ci siano ascoltatori o meno;
• rete simmetrica: considera il costo del percorso inverso dal router alla sorgente, che potrebbe essere diverso dal costo del percorso dalla sorgente al router per la presenza di link unidirezionali.

Reverse path broadcasting

Si costruisce un albero ricoprente di distribuzione basato sulla sorgente (nodo radice), e i pacchetti raggiungono tutte le destinazioni passando sui rami di quest'albero:

• interfaccia padre: l'interfaccia a distanza minore verso la sorgente, da cui vengono ricevuti i pacchetti dai livelli superiori;
• interfacce figlie: le altre interfacce del router, su cui vengono inviati i pacchetti verso i sottoalberi (eventuali pacchetti ricevuti vengono sempre scartati).

Su una LAN transita una sola copia dello stesso pacchetto: tra i router aventi interfacce figlie sulla LAN, il router che ha distanza inferiore verso la sorgente viene eletto come il router designato per quel link (in caso di costo uguale, viene presa l'interfaccia con indirizzo IP più basso).

Problemi

• traffico: carica la rete in modo inaccettabile:
  • nessun pruning: il pacchetto viene sempre distribuito su tutti i link, senza tenere conto del fatto che ci siano ascoltatori o meno;
• rete simmetrica: considera il costo del percorso inverso dal router alla sorgente, che potrebbe essere diverso dal costo del percorso dalla sorgente al router per la presenza di link unidirezionali.

Truncated reverse path broadcasting

Gli host interessati inviano dei membership report per iscriversi al gruppo multicast → i router invieranno i pacchetti multicast solo agli host interessati, ed elimineranno dall'albero i rami su cui non è stato ricevuto alcun membership report (pruning).

Sfortunatamente l'albero di distribuzione dipende, oltre che dalla sorgente, anche dal gruppo multicast, risultando in requisiti di banda per i report e di memoria dei router nell'ordine del numero totale di gruppi moltiplicato per il numero totale di possibili sorgenti → per ridurre i requisiti di banda e di memoria, vengono eliminate dall'albero solo le LAN foglie che non hanno ascoltatori: una LAN foglia è una rete non usata da alcun altro router per raggiungere la sorgente multicast.

Come determinare se una certa LAN è una LAN foglia? Nell'orizzonte limitato con poisoned reverse, le destinazioni raggiunte attraverso il link sul quale l'annuncio è inviato vengono poste con distanza pari a infinito: se almeno un router a valle propaga la entry relativa alla sorgente in esame con distanza infinita, allora quel router usa quel link come strada più breve per raggiungere la sorgente → quel link non è una foglia, e quindi potrebbero esserci delle LAN foglie più a valle con degli ascoltatori.

Problema

Non è possibile eseguire il pruning di interi sottoalberi, ma sono eliminate solo le LAN foglie → sui nodi interni dell'albero viaggia del traffico inutile.

Reverse path multicasting

È possibile eseguire il pruning di un intero sottoalbero:

1. il primo pacchetto inviato dalla sorgente viene propagato secondo l'algoritmo TRPB;
2. se il primo pacchetto raggiunge un router collegato solo a LAN foglie prive di ascoltatori per quel gruppo, il router invia un messaggio di non-membership report (NMR) al router padre;
3. se il router padre riceve dei messaggi NMR da tutti i suoi figli, genera a sua volta un messaggio NMR verso il padre.

I messaggi NMR hanno validità limitata: quando scade il timeout, viene adottato nuovamente l'algoritmo TRPB. Quando in un ramo potato si aggiunge un ascoltatore per quel gruppo, il router invia al nodo padre un messaggio di membership report per attivare rapidamente il ramo dell'albero senza aspettare il timeout.

Problemi

• broadcast storm periodici: sono dovuti all'algoritmo TRPB a ogni scadenza del timeout;
• scalabilità: è critica, perché ogni router deve tenere molte informazioni per ogni coppia (sorgente, gruppo).

Instradamento multicast Link State

Grazie alla mappa completa della rete costruita da un protocollo di instradamento (unicast) di tipo LS, ogni router è in grado di calcolare l'albero di distribuzione da ogni sorgente verso ogni potenziale ricevitore.

Non è più necessario il "flood and prune", ma ogni router è in grado di determinare autonomamente se si trova lungo l'albero di distribuzione:

1. in una LAN foglia priva di ascoltatori, un host comunica di essere interessato al gruppo;
2. il router collegato invia in flooding un pacchetto LS che annuncia l'esistenza di un LAN con ascoltatori e la sua posizione all'interno della rete;
3. gli altri nodi della rete memorizzano il pacchetto LS e lo propagano a loro volta in flooding a tutta la rete;
4. quando il primo pacchetto della trasmissione arriva ad un router, prima di poterlo inoltrare deve calcolare l'albero dei cammini minimi per sapere se si trova lungo l'albero di distribuzione e, in caso affermativo, su quali link deve inoltrare il pacchetto;
5. per i pacchetti successivi questo calcolo non è più necessario in quanto l'informazione si troverà in cache.

Problemi

• l'instradamento del primo pacchetto di una trasmissione può richiedere parecchio tempo: ogni router deve calcolare l'albero dei cammini minimi per la coppia (sorgente, gruppo);
• risorse di memoria: ogni sorgente ha un albero distinto verso ogni destinazione → è presente nella tabella di instradamento una entry per ogni coppia (sorgente, gruppo) attiva;
• risorse della CPU: l'esecuzione dell'algoritmo di Dijkstra per il calcolo dell'albero di instradamento è pesante per i router.

Instradamento multicast con algoritmo core-based tree

L'albero di distribuzione multicast è unico per tutto il gruppo multicast e indipendente dalla sorgente (albero condiviso). Il core router è il router principale dell'albero di distribuzione.

Costruzione dell'albero

1. un host segnala al suo router periferico (leaf router) che vuole agganciarsi al gruppo multicast (sia come ricevitore sia come trasmettitore);
2. il router periferico invia un messaggio di Join Request al core router;
3. i router intermedi che ricevono il messaggio di Join Request marcano l'interfaccia dalla quale è arrivato il messaggio come una delle interfacce da usare per l'inoltro dei pacchetti multicast per quel gruppo;
4. quando il core router riceve il messaggio di Join Request, anch'esso marca quell'interfaccia per l'inoltro e la segnalazione si ferma.
   Nel caso in cui il messaggio raggiunga un router che fa già parte dell'albero, la segnalazione si ferma prima di raggiungere il core router, e all'albero precedente viene aggiunto un nuovo ramo.

Inoltro dei dati

1. un membro del gruppo invia semplicemente il pacchetto in multicast;
2. il pacchetto viene inoltrato prima lungo il ramo dalla sorgente al core router, poi sui rami dal core router agli altri membri del gruppo: ogni router che riceve il pacchetto, compreso il core router, lo invia su tutte le interfacce appartenenti a quel gruppo multicast definite nella fase di costruzione dell'albero (tranne quella da cui il pacchetto è arrivato).

Vantaggio

• scalabilità: poche informazioni di stato nei router.

Svantaggi

• utilizzo di "stati forti": il core router è fisso, e non vengono inviati periodici messaggi di refresh sullo stato dei gruppi multicast → poco adatto a situazioni altamente variabili;
• il core router è un singolo punto di guasto (anche se si può eleggere un altro router);
• la posizione del core router influenza pesantemente le prestazioni dell'algoritmo: il core router può diventare un collo di bottiglia perché tutto il traffico passa attraverso di esso;
• i percorsi non sono ottimizzati: l'albero di distribuzione non è costruito in base alla posizione della sorgente, ma tutti i membri del gruppo possono essere sorgenti.

Instradamento multicast gerarchico

Per l'instradamento inter-dominio sono necessari algoritmi di tipo gerarchico: la complessità degli algoritmi tradizionali (e le informazioni di stato da tenere) non permettono la scalabilità all'intera Internet.

In generale, entrano in gioco le politiche di instradamento, e gli "host" sono sostituiti dai "domini":

• instradamento non gerarchico: l'host X vuole ricevere i gruppi A, B e C;
• instradamento gerarchico: il dominio Y vuole ricevere i gruppi A, B e C.