Sperimentazione Multicast sulla MAN toscana.

Sperimentazione Multicast sulla MAN toscana.

A cura di Luca Saletti & Paola Bianco.

Cap. 2) Il Multicast

Cosa è il multicast routing
Il flooding
Tecniche Shortest Path Tree (SPT)
Tecniche ad albero condiviso (Shared Tree)
Considerazioni e differenze fra le due filosofie

COSA È IL MULTICAST ROUTING.

Per multicast routing si intende tutto ciò che riguarda l'istradamento per le comunicazioni multipunto-multipunto, unipunto-multipunto, multipunto-unipunto. Negli anni passsati e fino ai nostri giorni la maggior parte delle applicazioni in rete si sono basate su istradamento di tipo punto-punto (unicast). A tale scopo si sono sviluppati protocolli di istradamento efficienti, stabili che possano ovviare a poblemi dovuti a cambiamenti della topologia della rete e di calcolare i cammini più brevi dalla stazione trasmittente a quella ricevente.
A fianco di questo si sono sviluppate negli anni (il primo esperimento concreto risale al 1988) applicazioni multicast, tipo video/audio conferenze, con collegamenti di tipo multipunto-multipunto. Trasmissioni di questo tipo, però, hanno esigenze completamente diverse, che gli attuali protocolli unicast non riescono a supportare senza andare incontro a sprechi di risorse non indifferenti.

Concettualmente infatti un istradamento multicast può essere fatto replicando (da parte del sorgente) un pacchetto informativo per il numero dei riceventi e dando ad ogni pacchetto l'indirizzo del proprio destinatario.
Questo comporta che sull'intero albero di distribuzione dei datagrammi le risorse utilizzate vengano moltiplicate per il numero dei riceventi; un simile approccio però si rivela in tutta la sua fragilità quando si pensa all'impiego di una rete su scala continentale piuttosto che mondiale o su collegamenti che non garantiscono un'alta disponibilità di banda.
Nasce allora l'idea di riuscire a sfruttare in modo ottimale le risorse di rete con protocolli di routing di tipo multicast, in grado di non far collassare un link qualora questo sia interessato da un traffico di tipo multicast, e mediante router dedicati (MRouter) in grado di supportare gli indirizzi di gruppi piuttosto che di singoli HOST.

Esistono varie filosofie di istradamento per il traffico multicast:

copertura di tutti i link della rete,
creazione di alberi ottimali di consegna
creazione di alberi condivisi.

IL FLOODING.

Si tratta del più semplice concetto di istradamento multicast, (in realtà è paragonabile ad un broadcast). Ogni router che riceve un pacchetto lo reistrada su tutte le interfacce ad eccezione di quella di provenienza; si suppone ovviamente che su ogni pacchetto vi siano dei flag in grado di segnalare se quel pacchetto è già stato replicato da quel router, evitando una ripetizione incontrollata.
È ovvio che un istradamento dei pacchetti di questo tipo riesce a coprire l'intero grafo della rete. Con questo accorgimento siamo riusciti ad eliminare il problema del replicamento incontrollato dei pacchetti ma si interessano anche link che nulla hanno a che fare con il traffico multicast.
Un problema di questo tipo rende di fatto il flooding applicabile solo a reti di piccole dimensioni.

TECNICHE SHORTEST PATH TREE (SPT)

Si tratta di tecniche in grado di ottimizzare il percorso fra il nodo sorgente ed il gruppo ricevente, di queste consideriamo le tecniche:

ad albero di copertura,
Reverse Path Broadcast e la sua versione Trunacate,
Reverse Path Multicast.

ALBERO DI COPERTURA.

Si tratta di un algoritmo in grado di coprire interamente i nodi interessati al traffico nell'albero di istradamento. Esistono poi molti esempi ed algoritmi in grado di costruire, dato un grafo, un albero di copertura minimo, fra cui quello di Dijkstra è senz'altro il più famoso.
Si riesce in questo modo ad ottimizzare il cammino dei pacchetti. Il problema principale è che la radice dell'albero è congestionata da traffici di questo tipo. Nel caso di trasmissioni punto-multipunto il cambio frequente della sorgente (come può avvenire in certe applicazioni) porta ad avere una notevole mole di calcoli da eseguire per l'aggiornamento della topologia con un necessario impiego di banda addizionale per la segnalazione. Sono richieste inoltre notevoli quantità di memoria per mantenere attivi gli stati sui router impegnati.

REVERSE PATH BROADCAST (RPB).

Si tratta di una variante rispetto all'albero di copertura, poichè prevede la creazione di un singolo albero specifico per ogni sorgente. In questo caso ci sono più radici virtuali sull'albero di distribuzione e si riesce a evitare la concentrazione di traffico nell'intorno dell'unica root riuscendo poi a minimizzare il numero degli stati da tenere attivi sui router e il traffico di segnalazione per la riorganizzazione della topologia al cambio della sorgente.
La costruzione di ogni albero di copertura è piuttosto semplice: ogni router è a conoscenza di quale interfaccia fra le proprie porti al cammino più breve verso la sorgente: se il paccetto arriva su quell'interfaccia allora esso viene replicato su tutte le interfacce (tranne quella di provenienza) altrimenti il datagramma viene scartato.

Il mecanismo in questione impedisce il replicarsi dei datagrammi anche se, non esistendo un meccanismo di filtraggio in grado di associare una sorgente ad un gruppo ricevente, non si riesce a discriminare l'appartenenza di un host ad un gruppo o ad un altro; questo comporta che il traffico diretto verso un gruppo possa essere in realtà istradato verso link non interessati alla sessione.

TRUNCATE REVERSE PATH BROADCAST (TRPB).

Viene introdotto il concetto di filtro: ogni router utilizza alcune funzionalità dell'IGMP per evitare di trasportrare datagrammi di un gruppo su reti che non contengano ascoltatori attivi.

L'esempio è riportato nella figura soprastante. Dalla sorgente arrivano datagrammi del gruppo G1. Questi vengono inviati all'interfaccia I2. Non vengono inviati all'interfaccia I3 dato che non vi sono ascoltatori attivi per quel gruppo. Vengono inviati all'interfaccia I4 solamente se questa porta ad un router che la considera il collegamento padre per la coppia sorgente, G1.
Il beneficio di utilizzare il TRPB rispetto al RPB è molto limitato dato che permette di salvare la banda laddove è più disponibile, ovverosia sulle reti locali, mentre non permette di risparmiare la banda dei link tra reti differenti in quanto costruisce rami dell'albero di copertura che possono portare a reti senza utenti attivi per i gruppi convogliati.

REVERSE PATH MULTICAST (RPM).

Si tratta di un ulteriore miglioramento del TRPB. Questa volta vengono coinvolti nella sessione di trasmissione solo i gruppi realmente attivi. adesso quando un router riceve un pacchetto per un gruppo a lui "figlio" ripete il datagramma su tutti i router a lui prossimi secondo la filosofia del TRPB.
Si evitano dunque i nodi che si sa non essere coinvolti nel collegamento.
Se un router non ha ascoltatori sotto di sé allora comunica al router immediatamente "a monte" un messaggio di taglio (PRUNE MESSAGE) in modo da essere cancellato dall'interfaccia uscente.

Il valore del taglio è a tempo e dunque se questo non viene rinnovato il router "a monte" (upstream router) invia nuovamente su tutte le interfaccie a valle i pacchetti informativi. Questo comporta che periodicamente, se i prune-messages non vengono rinnovati, si abbia sull'intero albero un traffico multicast.
La filosofia di taglio viene applicata ricorsivamente sui router a monte qualora si presentino le condizioni.

TECNICHE AD ALBERO CONDIVISO (SHARED TREE)

CORE BASED TREE (CBT)

La filosofia che sta dietro è completamente diversa da quelle fino ad ora viste.
Non si trata più di avere un albero minimo di distribuzione per ogni coppia (sorgente,gruppo) quanto piuttosto di creare alberi minimi attorno a router dedicati detti Core-Router (CR).
I nodi dedicati formano degli alberi che hanno i CR come radice: non è necessario che questi siano o sender o receiver, è necessario però che abbiano funzionalità multicast.
Una volta costruito l'albero minimo di consegna dei pacchetti ogni router può fare richiesta di adesione o di sconessione dall'albero inviando un messaggio di join o di prune a router a monte, e questo reistraderà la richiesta fino a raggiungere il Core-Router a lui più vicino.

Durante la consegna del messaggio (join o prune) i router intermedi settano le proprie interfacce al fine di rendere possibile la consegna dei pacchetti.

La differenza ora sta nel fatto che se una sorgente non sta all'interno del'albero di distribuzione può mandare comunque del traffico incapsulato in tunnel verso l'MRouter più vicino. Una simile strategia permette di risparmiare memoria sullo stato a bordo dei router poichè si devono tenere informazioni riguardo al fatto che un gruppo sia connesso o meno e non riguardo alla topologia della rete.

Ovviamente questo approccio per quanto risolutivo di molti problemi porta in sé degli inconvenienti intrinseci:

il traffico è addensato intorno ai Core-Router,
l'albero di distribuzione non è ottimale, cosa che potrebbe essere deleteria per molti tipi di applicazioni.

CONSIDERAZIONI E DIFFERENZE FRA LE DUE FILOSOFIE.

Le differenti filosofie hanno inconvenienti e vantaggi diversi (se non quasi opposti) che si addattano a situazioni con esigenze distinte.La figura che segue mostra come la filosofia della creazzione degli alberi ottimi sia inefficiente su reti che si estendono su larga area.

Come si è visto una simile filosofia si comporta inviando in broadcast (o in multicast molto "allargato") tutti i pacchetti informativi fino a che i gruppi non interessati alla sessione non inviano un messaggio di taglio.
Su reti tipo WAN o anche internetwork un simile meccanismo finisce per intasare tutti i collegamenti con traffico inutile di segnlazione necessario per riorganizzare periodicamente l'intero albero. Con un meccanismo di questo tipo sul quale si basa ad esempio il famoso e usatissimo DVMRP (http//:telemat.die.unifi.it/book/MBone/....) quando A inizia a trasmettere i suoi pacchetti vangono inviati in broadcast all'intera rete. Successivamente tutti i siti che non sono interessati alla sesione di trasmissione inviano un prune message e la situazione si stabilizza creando un albero di consegna come mostrato nella figura di seguito.
Periodicamente però quando i messaggi di taglio scadono A invia nuovamente il suo traffico su tutta la rete.

Con la creazione di un Core-Based-Tree (CBT) un problema di questo tipo non esiste; supponendo che A sia il Core-Router e viene creato un CBT come in figura.

Un simile albero viene usato anche dal traffico che va da B a C: il traffico dunque si concentra sulla linea in grassetto e c'è da notare che questo non è la via più breve (o che comporta il minore ritardo) fa sorgente e ricevente.

È importante conoscere ora il tipo di degradazione delle prestazioni che un albero condiviso dà rispetto a quello specifico.
Una prima stima è quella di considerare nel caso medio un ritardo pari a due volte quello ottenibile con l'olbero ottimale. Per comprendere al meglio il funzionamento di un simile comportamento è stato simulato un algoritmo di CBT su una serie di grafi scelti in maniera casuale. è stato poi misurato il ritardo all'interno di grafi con nodi aventi il numero di interfacce differenti. Sono poi state simulate le condizioni su un 500 grafi di 50 nodi con gruppi di 10 elementi.
Come si può notare dalla figura sottostante il rapporto fra il ritardo dovuto al CBT e quello dovuto al SPT non è mai superiore a 1.4.

Si possono notare anche valori inferiori all'unità ma ciò è dovuto alla distribuzione delle probabilità che non è simmetrica: la linea continua sta ad indicare il valore medio.

Si vede subito allora come per applicazioni interattive sia consigliabile laddove possibile una filosofia SPT.

Altro problema importante riguarda la concentrazione del traffico sui link: sono state eseguite questa volte misurazioni su reti di 50 nodi con 300 gruppi attivi, ognuno dei quali composto da 40 membri di cui 32 anche trasmittenti. Sono stati poi misurati flussi di traffico sui vari link e riportati in un grafico in funzione delle interfacce dei nodi. La figura sottostante mostra l'andamento delle distribuzioni di probabilità.
si nota cone la concentrazione dei flussi sia molto più elevata nella filosofia shared piuttosto che in quella ottima.

Nonostante gli inconvenienti dovuti al ritardo che una filosofia tipo CBT introduce questa è in grado di ridurre drasticamente il numero degli stati a bordo dei router, cosa estremamente gradita quando si ha a che fare con applicazioni non critiche.

ultimo aggiornamento 10-07-1997