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.

Gli stati che uno switch può assumere grazie al protocollo STP e i messaggi BPDU

Gli switch di una rete Lan sono in grado di mandare dei messaggi detti BPDU (Bridge Protocol Data Unit); questi ultimi sono trasmessi a tutte le porte degli switch per eleggere un root bridge, ovvero la radice principale dell'albero gerarchico che verrà creato dopo che l'STP agirà.

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, 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:

• Shortest Path Bridging (SPB) 802.1aq
• Multiple Spanning Tree (MST) 802.1s
• Rapid Spanning Tree (RST) 802.1w: provvede a ripristinare la topologia di rete nel minor tempo possibile (nell'ordine di qualche secondo).

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 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) spanning tree algorithm, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL

Controllo di autorità	GND (DE) 7647999-7