Broadcast routing

Broadcast Routing

Per alcune applicazioni, gli host hanno necessità di spedire messaggi a molto o addirittura a tutti gli altri host. Ad esempio, un servizio che distribuisce bollettini meteorologici, aggiornamenti sul mercato delle merci, o programmi radio dal vivo può funzionare meglio spedendo in broadcast a tutti gli host e lasciando che quelli che sono interessati possano leggere i dati.

La spedizione di un pacchetto a tutte le destinazioni simultaneamente è chiamato broadcasting: sono stati proposti molti metodi per realizzarlo.

Un metodo di broadcasting che non richiede particolari caratteristiche alla rete prevede che la sorgente spedisca un pacchetto a tutte le destinazioni. Questo metodo non solo spreca enormemente la banda disponibile, ma richiede anche che la sorgente abbia una lista completa di tutte le destinazioni. In pratica questa può essere l'unica possibilità, ma è il metodo meno desiderabile.

Un altro candidato ovvio è il flooding. Sebbene il flooding sia poco adatto per le comunicazioni ordinarie punto a punto, nel caso del broadcasting ci sono serie considerazioni a suo favore, in modo particolare se nessuno degli altri metodi descritti in seguito è applicabile. Il problema del flooding come tecnica di broadcasting è lo stesso che si presenta nel caso di comunicazioni punto a punto: genera troppi pacchetti e consuma troppa banda.

Un terzo algoritmo è il routing multidestinazione. Se viene usato questo metodo, ogni pacchetto contiene o una lista di destinazioni, oppure una mappa di bit che indica le destinazioni desiderate. Quando un pacchetto arriva a un router, il router controlla tutte le destinazioni per determinare l'insieme delle linee di output che devono essere usate (una linea di output è necessaria se appartiene al percorso migliore per almeno una delle destinazioni). Il router genera una nuova copia del pacchetto per ogni linea di output e include in ogni pacchetto solo le destinazioni che devono usare quella linea. In effetti, l'insieme delle destinazioni viene frazionato tra le linee di output. Dopo un numero sufficiente di salti, ogni pacchetto conterrà solo una destinazione e potrà essere trattato come un pacchetto normale.

Il routing multidirezionale è simile alla spedizione di pacchetti indirizzati separatamente, a parte il fatto che quando molti pacchetti devono seguire lo stesso itinerario, uno di essi paga il biglietto intero e gli altri seguono gratuitamente.

Un quarto algoritmo di broadcast rende esplicito l'uso del sink tree relativo al router che inizia il broadcast, o qualsiasi altro spanning tree conveniente. Uno spanning tree (albero di ricoprimento) è un sottoinsieme della rete che include tutti i router ma non contiene cicli. Se ogni router sa quale delle sue linee appartengono allo spanning tree, può copiare un pacchetto di broadcast in arrivo su tutte le linee appartenenti allo spanning tree eccetto quella di arrivo. Questo metodo utilizza molto bene la banda, generando in assoluto il numero più piccolo di pacchetti necessari a portare a termine il lavoro. L'unico problema è che ogni router deve conoscere qualche spanning tree affinché sia applicabile. Qualche volta questa informazione è disponibile (es. con il link state routing), ma qualche volta no (es. con distance vector routing).

Il nostro ultimo algoritmo di broadcast è un tentativo di approssimare il comportamento di quello precedente, anche quando i router non sanno nulla sugli spanning tree. Quando a un router arriva un pacchetto di broadcast, il router controlla se il pacchetto è arrivato nella linea normalmente utilizzata per spedire pacchetti verso la sorgente del broadcast. Se è così esiste una buona probabilità che lo stesso pacchetto di broadcast abbia seguito il percorso migliore dal router e sia quindi la prima copia che arriva al router. Se questo è il caso, il router inoltra copie di esso su tutte le linee eccetto quella di arrivo. Se viceversa, il pacchetto di broadcast è arrivato da una linea diversa da quella migliore per raggiungere la sorgente, il pacchetto viene scartato come probabile duplicato.

Un esempio è il reverse path forwarding (rispedizione sul cammino inverso). Il vantaggio principale consiste nell'essere ragionevolmente efficiente e facile da implementare. Non richiede né che i router conoscano gli spanning tree, né il carico aggiuntivo della lista di destinazioni o della mappa di bit in ogni pacchetto di broadcast come nell'indirizzamento multidestinazione. Non richiede nemmeno un meccanismo speciale per fermare il processo, come il flooding (o un contatore di salti in ogni pacchetto e una conoscenza a priori del diametro della rete, oppure una lista di pacchetti già visti per ogni sorgente).