Spanning tree (networking)

Da Wikipedia, l'enciclopedia libera.
Diagramma di una rete di media complessità, notare l'assenza di percorsi ciclici

Lo spanning tree è un algoritmo utilizzato per realizzare reti complesse (a Livello fisico) con percorsi ridondanti utilizzando tecnologie di Livello datalink (il livello 2 del modello OSI) come IEEE 802.2 o IEEE 802.11.

Lo spanningh tree e' un grafo con particolare struttura, non un algoritmo. Qui si confonde output dell'algoritmo con l'algoritmo stesso. [AD]

Lo spanning tree viene eseguito dai bridge e dagli switch, e mantiene inattive alcune interfacce in modo da garantire che la rete rimanga connessa ma priva di loop.

Limiti delle LAN complesse[modifica | modifica wikitesto]

Una LAN complessa può essere costituita da diversi segmenti di rete, connessi tra loro tramite dei bridge o switch, con il vincolo che la topologia di una LAN non contenga cicli, ovvero che tra ogni coppia di calcolatori esista un solo percorso.

Se così non fosse, alcuni pacchetti verrebbero replicati all'infinito sulla rete, con risultati disastrosi. Il bridge, infatti, conosce gli indirizzi MAC degli host connessi su ogni segmento, ma se riceve un pacchetto con destinazione sconosciuta, o un pacchetto broadcast, lo invia su tutti segmenti, tranne che su quello di provenienza. Se esiste un ciclo nella rete, il pacchetto raggiungerà nuovamente il segmento da cui è partito, venendo nuovamente replicato. Questo porterebbe alla proliferazione di infinite copie dello stesso pacchetto sulla rete, e quindi alla saturazione della rete stessa.

Una rete complessa priva di percorsi ridondanti è però estremamente fragile, perché il guasto di un solo bridge o collegamento la partiziona in due reti che non comunicano tra di loro.

Gestione della ridondanza attraverso lo spanning tree[modifica | modifica wikitesto]

In una rete locale complessa, è necessario che ci siano dei collegamenti ridondanti, ma che alcuni di questi siano mantenuti "fuori servizio" fino a quando non si rendono necessari per sopperire a guasti di altri collegamenti o bridge.

L'algoritmo di spanning tree è un algoritmo distribuito, che opera su tutti i bridge, facendo in modo che in ogni istante la rete sia connessa ma priva di cicli, ovvero che il grafo dei collegamenti disponibili sia "coperto" da un albero.

Ciò si ottiene mediante la creazione di una gerarchia di bridge. Un bridge viene individuato come radice dell'albero coprente ("root bridge"), e una parte dei collegamenti tra bridge disponibili viene messa in standby, portando in stato "BLOCKING" alcune delle porte dei bridge.

Nel caso in cui un nodo diventi irraggiungibile, oppure cambi il costo di connessione, il bridge cercherà di arrivare al nodo attivando i percorsi alternativi che sono in stand-by, ripristinando in questo modo la connettività completa della rete (se possibile).

In teoria dei grafi, questo problema è noto come Albero spanning.

Questo processo avviene periodicamente per cui, se si scollega un bridge o si interrompe un collegamento, si ricostruisce lo spanning tree e la rete continua a funzionare.

L'algoritmo tende automaticamente a mantenere in funzione i collegamenti di capacità superiore, ma talvolta la scelta di collegamenti da mantenere attivi è inadeguata alle caratteristiche della rete o del traffico che la attraversa. Configurando opportuni parametri sugli switch, è possibile influenzare sia la scelta del root bridge che la scelta dei collegamenti da mantenere in servizio.

Tale algoritmo è stato inventato da Radia Perlman e standardizzato in IEEE 802.1D.

Circolo vizioso in una LAN senza spanning tree
Spanning tree

Limiti e alternative[modifica | modifica wikitesto]

L'algoritmo di Spanning Tree permette di estendere reti locali mantenendo un buon grado di ridondanza, ma presenta alcuni limiti:

  • I tempi di convergenza, ovvero il tempo necessario al protocollo per reagire al guasto di un elemento della rete o al suo ripristino, tendono a crescere con il numero di switch coinvolti nel processo.
  • Il protocollo di spanning tree genera a sua volta traffico sulla rete, che può contribuire alla sua saturazione.
  • La capacità dei collegamenti lasciati in stand-by non può essere sfruttata (ovvero questi collegamenti sono usati come riserva fredda).

Per ovviare ai sopracitati limiti, sono stati sviluppate estensioni al protocollo di Spanning Tree originario. In particolare:

Alcuni produttori di apparati di networking hanno sviluppato sistemi alternativi e proprietari per superare i limiti imposti da spanning-tree nell'ethernet e raggiungere le caratteristiche di SDH in particolar modo per quanto riguarda classica configurazione ad anello. In questo ambito sono da citare:

Per le reti di tipo Token ring ed FDDI esiste un algoritmo specifico, alternativo a spanning tree, definito source routing.

Quando la rete cresce al punto di rendere eccessivamente problematici questi fattori, è spesso necessario segmentarla con l'aiuto di uno o più router, anche se questo comporta tipicamente la modifica degli indirizzi IP utilizzati dagli host sulla rete (rinumerazione).

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Telematica Portale Telematica: accedi alle voci di Wikipedia che parlano di reti, telecomunicazioni e protocolli di rete