Distance vector: differenze tra le versioni

Versione delle 11:38, 20 giu 2007

Versione attuale delle 13:39, 16 feb 2023

(40 versioni intermedie di 29 utenti non mostrate)

Riga 1:

{{F|protocolli di rete|maggio 2012|Questa voce manca completamente di fonti}}

{{S|informatica}}

{{S|protocolli di rete}}

[[ImmagineFile:routers.jpg|thumb|262pxupright=1.2|Schema di una sottorete]]

IlIn routing[[informatica]] e [[telecomunicazioni]], l'[[instradamento]] '''Distancedistance Vectorvector''' (routing basato sul vettore delle distanze), noto anche come '''routing di '''Bellman-Ford''' perché basato sull'[[algoritmo di Bellman-Ford|omonimo algoritmo]], è un tipo di algoritmo di '''[[routing dinamico']]'', che tiene conto del carico istantaneo della rete.

Questo opera in modo tale che ogni nodo conosca, sulla base di misure effettuate, il ritardo o la distanza che lo separa dai suoi nodi adiacenti e quindi comunicandogli periodicamente queste informazioni. Combinando i dati ricevuti da ciascun router si riesce a creare e a tenere sempre aggiornata una tabella, ossia un vettore, nel quale è specificata la stima del minor tempo o della minore distanza associata ad ogni destinazione, e quale sia la linea che conduce a questa.

Un processo di aggiornamento è riportato qui di seguito:

Si consideri una sottorete come in figura. Si supponga che F abbia stimato i ritardi dai routers vicini C,I,G ed E.

#C sa di poter raggiungere A in 5 msec , quindi F che ha calcolato un ritardo da C di 2 msec, sà di poter raggiungere A tramite C in 5+2=7 msec

#E sa di poter raggiungere A in 2 msec , quindi F che ha calcolato un ritardo da E di 3 msec, sà di poter raggiungere A tramite E in 2+3=5 msec

#G sa di poter raggiungere A in 3 msec , quindi F che ha calcolato un ritardo da G di 3 msec, sà di poter raggiungere A tramite G in 3+3=6 msec

#I sa di poter raggiungere A in 6 msec , quindi F che ha calcolato un ritardo da I di 1 msec, sà di poter raggiungere A tramite I in 6+1=7 msec

Il valore migliore è 5, quindi F crea nella sua tabella di routing un valore associato ad A registrando il ritardo pari a 5 msec e la linea di trasmissione E. Quindi, al contrario di altri algoritmi tra i quali il [[Link State]], il Distance Vector non fa conoscere a ciascun router la topologia dell'intera rete, ma solo dei suoi vicini. Questo porta ha diverse problematiche, tra le quali il problema del conto all'infinito.

==Caratteristiche==

Mentre gli algoritmi di tipo [[link state]] prevedono che ogni [[router]] sia informato dei cambiamenti occorsi nell'intera topologia della rete, i protocolli basati su distance vector - come [[Routing Information Protocol|RIP]] ed [[Interior Gateway Routing Protocol|EIGRP]] - sono invece più leggeri: ogni router misura la [[Distanza (matematica)|distanza]] (secondo una metrica che può includere vari fattori) che lo separa dai nodi adiacenti ricevendo i dati dai router vicini. A partire da tali dati, utilizzando l'[[algoritmo di Bellman-Ford]], il router costruisce una tabella che associa ad ogni destinazione conosciuta:

* la stima della distanza che lo separa dalla destinazione

* il primo passo del percorso calcolato

Periodicamente poi il router aggiorna le misure di distanza dai router adiacenti e comunica la propria tabella ai vicini. Dopo sufficienti scambi di informazioni, ciascun router potrà avere una riga per ogni altro nodo nella rete.

== Esempio ==

Necessario (da aggiornare):

SiUn processo di aggiornamento è riportato qui di seguito: si consideri una sottorete come in figura. Si supponga che F abbia stimato i ritardi dai routersrouter vicini C, I,G ede EG.

#Algoritmo Bellman-Ford con relativa descrizione

# C sa di poter raggiungere A in 5 msec ,ms; quindi F, che ha calcolato un ritardo da C di 2 msecms, sàsa di poter raggiungere A tramite C in 5+2=7 msec ms.

#Problematiche relative al distance vector (COUNT TO INFINITY)

#E G sa di poter raggiungere A in 23 msec ,ms; quindi F, che ha calcolato un ritardo da EG di 3 msecms, sàsa di poter raggiungere A tramite EG in 23+3=56 msecms.

#G I sa di poter raggiungere A in 36 msec ,ms; quindi F, che ha calcolato un ritardo da GI di 31 msecms, sàsa di poter raggiungere A tramite GI in 36+31=67 msecms.

Il valore totale migliore è 6, quindi F crea nella sua tabella di routing un valore associato ad A registrando il ritardo pari a 6 ms e la linea di trasmissione G.

== Problemi ==

Ogni router memorizza solo il primo passo dei percorsi che ha nella tabella. Questo implica che se A pubblica un percorso verso C, i vicini di A non possono sapere se sono stati inclusi da A nel percorso calcolato. Quindi:

* possono formarsi cicli

* quando si interrompe un collegamento si può avere una situazione di ''count-to-infinity''

Una parziale soluzione sono le tecniche di ''[[Split horizon]]'' e di ''[[Poison reverse]]'', che evitano di pubblicizzare le route attraverso le stesse interfacce di rete da cui hanno ricevuto le stime originali. L'introduzione di tempi di attesa prima di aggiornare una route scoraggia la formazione di cicli. Protocolli come [[EIGRP]] e [[DSDV]] evitano del tutto la formazione di cicli scambiando ulteriori informazioni.

=== Count-to-infinity ===

Si supponga di avere una rete "lineare" A-B-C-D-E-F e che si interrompa il collegamento con A. Al momento di aggiornare la propria tabella, B noterà che non può più raggiungere A tramite il suo collegamento diretto. Tuttavia C (che è ancora inconsapevole della situazione) sta dichiarando di poter raggiungere A in due passi; B riterrà quindi di poter raggiungere A in tre passi tramite C.

Questa situazione può propagarsi sulla rete generando stime di distanza sempre maggiori.

== Voci correlate ==

* [[Router]]

* Algoritmi basati su [[link state]]

#* [[Algoritmo di Bellman-Ford con relativa descrizione]]

{{Portale|telematica}}

[[Categoria:Protocolli di routing]]

[[Categoria:Algoritmi di rete]]