Flooding
In informatica il flooding è un protocollo di instradamento usato dai router che inoltrano un pacchetto in ingresso su tutte le linee ad eccezione di quella da cui proviene. Ogni pacchetto in arrivo viene inoltrato su ogni linea di uscita eccetto quella da cui è arrivato. Questo algoritmo genera un vasto numero di pacchetti duplicati; in effetti, un numero infinito, a meno di non prendere qualche misura per fermare il processo.
Per evitare l'invio infinito di pacchetti duplicati si possono utilizzare due accorgimenti:
- contatore di salto: si inserisce nel pacchetto un contatore da decrementare ad ogni nuovo router attraversato. Idealmente il valore di tale contatore deve essere uguale al percorso minimo fra sorgente e destinazione ma non conoscendo la topologia della rete si può assegnare un valore uguale al diametro della rete.
- numero di sequenza: ogni router deve conoscere la presenza degli altri router e per ogni router dovrà solo controllare che il pacchetto proveniente da quello abbia un numero sequenza maggiore del precedente. Per evitare la crescita all'infinito si adotta una soglia k che riassume la ricezione di tutte le sequenze fino ad appunto k. Raggiunta la soglia il numero si azzera.
Utilizzo
Il flooding può tornare utile in applicazioni militari dove non è tollerato il malfunzionamento di un router durante il percorso di inoltro.
Ha utilizzi pratici anche nelle reti wireless dove tutti i messaggi trasmessi da una stazione possono essere ricevuti da tutte le altre che si trovano nel suo campo.
Può essere utilizzato, infine anche come metrica di confronto per altri algoritmi di routing: il flooding segue sempre il percorso più breve poiché utilizza ogni possibile percorso in parallelo, ne segue che nessun altro protocollo riesce ad ottenere ritardi inferiori.
È un protocollo di routing molto semplice da implementare e con limitate necessità di elaborazione da parte dei router; il problema associato è dovuto al fatto che esso va ad utilizzare la capacità trasmissiva della rete in maniera ridondante utilizzando un numero di link che cresce allontanandoci dal router iniziale e aumentando quindi le probabilità di congestione di rete.
Flooding selettivo
In questa variante i router non spediscono ogni pacchetto in arrivo in ogni linea di uscita, ma solo su quelle linee che vanno approssimativamente nella giusta direzione. Ha poco senso spedire un pacchetto diretto ad ovest in una linea diretta a est, a meno che la topologia sia estremamente particolare.