Spanning tree (networking)

Diagramma di una rete di media complessità, notare l'assenza di percorsi ciclici

In telecomunicazioni e informatica lo spanning tree è un protocollo di comunicazione standard 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 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. Le risorse utilizzate da questo protocollo sono minori rispetto a quelle utilizzate da PVST(proprietario Cisco), RST, Rapid PVST(proprietario Cisco), MSTP, ma ha una convergenza più lenta ed inoltre crea un'unica istanza che si occupa contemporaneamente di tutte le VLAN non sfruttando a pieno le funzionalità della rete. Il protocollo STP è utilizzato solo nelle reti Lan, ovvero le reti locali.

Lo scopo del protocollo STP è quello di eliminare "virtualmente" tutti i percorsi che sono considerati "non primari". Se non ci fosse il protocollo STP, ci sarebbero tanti cavi ridondanti che verrebbero considerati primari e darebbero vita ad un loop infinito. Quindi, il protocollo STP individua il percorso (cavo) principale e assegna a tutti gli altri percorsi lo stato "locked", ovvero bloccato. Se per un qualsiasi motivo il cavo primario o percorso primario smettesse di funzionare, il protocollo STP interverrebbe facendo una riconfigurazione della rete e assegnando lo stato Blocked al percorso che oramai non è più funzionante e assegnando lo stato primario ad un percorso alternativo. In aggiunta, lo stato Locked permette di bloccare (virtualmente) solo quel percorso per un periodo di tempo e che questo procedimento avviene solo ed esclusivamente alla parte logica della rete Lan.

Il protocollo STP (802.1d) e i messaggi BPDU

Al momento dell'avvio di una rete LAN tutti gli switch ritengono di essere root bridge ovvero si auto eleggono radice dell'albero. A conseguenza di ciò ogni switch invierà a tutti i propri vicini una BPDU contentente un valore, chiamato BridgeID, che ne rappresenta la sua priorità. Se uno switch riceve una BPDU con un valore di priorità maggiore del proprio allora rinuncia al ruolo di root bridge. Il risultato sarà che tutti gli switch tranne uno rinunciano e quindi l'elezione del root bridge sarà conclusa. Nel momento in cui la rete è stabile (convergenza conclusa) nessuno switch tranne il root invierà BPDU. Solo nel caso in cui ci sia un cambiamento di topologia uno switch non root genererà una BPDU per segnalare il cambio di topologia.

Il valore di priorità di uno switch è dato da un valore di 10 byte di cui 6 byte di MAC address e 4 di priorità (i bit più significativi). Pertanto la priorità di uno switch è configurabile per ogni switch ma, se non fatto da un operatore, gli switch avranno un loro valore di priorità che, se uguale, farà vincere lo switch con il MAC address di valore inferiore. Il valore numerico inferiore ha priorità più alta in una rete STP.

Nel momento in cui il root bridge è stabilito ogni switch mette con il ruolo di blocked tutte le porte alternative per raggiungere il root bridge, scartate in quanto con priorità inferiore. La priorità di una porta viene calcolata in base alla velocità del link ad essa collegata e ad un valore di PortID.

I BPDU contengono informazioni per:

• eleggere i designated switch, ovvero lo switch più vicino alla root.
• scegliere per ogni switch la root port.
• calcolare il percorso più breve da ogni switch alla root.

Ogni porta dello switch si può trovare in uno dei seguenti stati:

• listening: lo switch non è in grado di comunicare con gli altri switch ma può solo ricevere
• learning: lo switch crea una tabella di bridging ma non può ne comunicare e ne ricevere
• forwarding: lo switch può sia ricevere che comunicare
• disabled: lo switch viene disabilitato dall'amministratore.

Le modifiche che sono apportate dallo switch vengono rilasciate dopo 30/50 secondi e questo porta ad una perdita di tempo e a tempi di convergenza inferiori. Per ovviare a questi problemi, si è deciso di ricorrere ad un metodo alternativo, ovvero passare direttamente da blocked a forwarding.

Limiti delle LAN complesse

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 i 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

In una rete locale complessa, è necessario che ci siano dei collegamenti ridondanti al fine di aumentare la robustezza della rete stessa, 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, denominate alternate port (dall'inglese: porta alternativa)(AP).

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 (AP) 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 ricoprente.

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 (più veloci), ma talvolta la scelta di collegamenti da mantenere attivi è inadeguata alle caratteristiche della rete o del traffico che la attraversa. Configurando opportuni parametri (come per esempio la priorità) 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

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. Nel caso di STP 802.1d il tempo di convergenza può arrivare a 50 secondi partendo da un minimo di 30;
• il protocollo di spanning tree genera a sua volta traffico sulla rete, che può contribuire alla sua saturazione, anche se è un problema oggi secondario per via della larghezza di banda delle reti moderne;
• 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:

• PVST proprietario Cisco, con supporto delle VLAN, che genera una istanza di STP per ogni singola VLAN;
• Rapid Spanning Tree (Rapid STP) 802.1w: provvede a ripristinare la topologia di rete nel minor tempo possibile (massimo 6 secondi) ma non supporta le VLAN;
• Rapid PVST+ proprietario Cisco, che aggiunge il supporto per le VLAN a Rapid STP;
• Multiple Spanning Tree (MST) 802.1s che standardizza il supporto alle VLAN estendendo Rapid STP permettendone l'utilizzo in grandi reti;
• Shortest Path Bridging (SPB) 802.1aq

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:

• IRF di Hewlett Packard
• Hiper-Ring di Hirschmann
• EAPS di Extreme Network
• Resilient Packet Ring di Nortel Networks
• Media Redundancy Protocol (MRP), standard IEC 62439

Per le vecchie 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

• Architettura delle reti di elaboratori

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sullo Spanning tree

Collegamenti esterni

• (EN) Denis Howe, spanning tree algorithm, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• (IT) Gianrico Fichera, Algoritmi STP.

Controllo di autorità	GND (DE) 7647999-7