Le Spanning Tree Protocol (aussi appelé STP) est un protocole réseau permettant de déterminer une topologie réseau sans boucle (appelée arbre) dans les LAN avec ponts. Il est défini dans la norme IEEE 802.1D et est basé sur un algorithme décrit par Radia Perlman (en) en 1985.
Les réseaux commutés de type ethernet doivent avoir un unique chemin entre deux points, cela s'appelle une topologie sans boucle. En effet, la présence de boucle génère des tempêtes de diffusion qui paralysent le réseau. Cependant, un bon réseau doit aussi inclure une redondance pour fournir un chemin alternatif en cas de panne d'une liaison ou d'un commutateur. L'algorithme de « spanning tree minimum » garantit l'unicité du chemin entre deux points du réseau en affectant un port dédié (root port), celui qui a le chemin le plus court vers le root bridge, à chaque segment du LAN (domaine de collision).
Réseau commuté ayant convergé. BP=Blocked Port, RP=Root Port, DP=Designated Port
Une topologie sans boucle ressemble à un arbre et à la base de chaque arbre, on trouve ses racines (roots). Dans un réseau commuté, le root bridge (commutateur maître) est déterminé par l'algorithme du spanning tree. Chaque commutateur a une adresse MAC et un numéro de priorité paramétrable (0x8000 par défaut), ces deux nombres constituant l'identification du bridge (nommée BID). Le BID est utilisé pour élire le root bridge en fonction des numéros de priorité, en cas d'égalité, l'adresse MAC la plus basse l'emporte, et comme toutes les adresses MAC sont uniques, il existera toujours un root bridge unique. Les autres commutateurs du réseau vont alors calculer la distance la plus courte vers le root bridge en utilisant le « coût » le plus faible vers celui-ci, ce coût dépendant de la bande passante des liens vers celui-ci. En général, l'administrateur du réseau configure la priorité du root bridge le plus opportun en fonction de la topologie particulière du réseau, ainsi que la priorité d'un autre commutateur qui deviendra root bridge en cas de défaillance du root bridge principal.
Un root port est un port qui sera utilisé pour transmettre les données (par opposition à un port bloqué). Chaque commutateur doit avoir un seul root port. L'élection d'un root port est effectuée d'après les champs path cost et port ID d'un paquet BPDU. En cas d'égalité, c'est le port ayant le port ID le plus faible qui sera élu. Un port bloqué peut émettre et recevoir des paquets BPDU. Les autres ports d'un commutateur sont des designated ports, ce sont eux qui transmettent les paquets BPDU.
Les BID et autres informations du protocole spanning tree sont transportés dans des unités de trames de données spéciales nommées BPDU (Bridge Protocol Data Units). Les BPDU sont échangées régulièrement (toutes les deux secondes) et permettent aux commutateurs de garder une trace des changements sur le réseau afin d'activer ou de désactiver les ports requis. Quand un commutateur ou un pont est raccordé au réseau, il commence par envoyer des BPDU afin de déterminer la topologie du réseau, avant de pouvoir commencer à transférer des données.
Il existe trois types de BPDU :
Les BPDU sont envoyés sur l'adresse multicast 01:80:C2:00:00:00.
Les port des commutateurs ou STP est actifs sont dans l'un des états suivants :
Le délai de transition entre les modes Listening vers Learning et Learning vers Forwarding est nommé forward delay, il est fixé par le root bridge et vaut 15 secondes par défaut.
Quand un client tel qu'un ordinateur, une imprimante ou un serveur est connecté au réseau, son port se mettra automatiquement d'abord en mode listening puis en mode learning, avant de se mettre en mode forwarding.
Pour raccourcir le délai de 50 secondes inhérent à la connexion d'un nouveau périphérique, le Rapid STP a été développé et standardisé par la norme IEEE 802.1w qui permet à un port de commutateur de passer directement en mode forwarding.
Il est également possible d'exclure certaines portes du fonctionnement de Spanning Tree, pour autant que l'on soit sûr qu'aucune boucle n'est possible sur ceux-ci.
L'algorithme original de Spanning Tree a été décrit par Radia Perlman alors employée par Digital Equipment Corporation, il est nommé DEC STP. En 1990, l'IEEE publié le premier standard 802.1D basé sur le travail de Perlman. Des versions ultérieurs sont publiées en 1998 et 2004.
Il existe certaines différences entre DEC STP et 802.1D qui peuvent causer des problèmes d'interopérabilité.
Les évolutions STP tentent d'améliorer certains aspects de STP, notamment :
En 1998, l'IEEE publie le document 802.1w qui accélère la convergence du protocole STP après un changement de topologie. Il est inclus dans standard IEEE 802.1D-2004. Tandis que le STP classique peut prendre de 30 à 50 secondes pour converger après un changement de topolgie, RSTP est capable de converger en 3 fois la valeur du délai Hello (6 secondes par défaut).
États des ports RSTP
Le fonctionnement général de RSTP est semblable à celui du STP classique. Les différences sont les suivantes :
Quand plusieurs VLAN existent dans un réseau ethernet commuté, STP peut fonctionner de façon indépendante sur chacun des VLAN séparément. Ce mode de fonctionnement a été baptisé PVST(+) par Cisco. C'est le mode par défaut sur les commutateurs de la marque. Il s'agit d'un développement propriétaire qui est également pris en charge par certains fournisseurs concurrents.
PVST fonctionne uniquement avec Cisco Inter-Switch Link (ISL). PVST+ est utilisé avec dot1q.
Le Multiple Spanning Tree Protocol (MSTP), défini dans la norme IEEE 802.1s puis inclus dans IEEE 802.1Q-2003, est une extension de RSTP dans laquelle une instance de RSTP existe par groupe de VLAN.
Disposer de plusieurs instances de STP permet de mieux utiliser les liaisons dans le réseau, si la topologie STP est différente pour certains groupes de VLAN. Contrairement à PVST, il n'est cependant pas nécessaire de disposer d'une instance par VLAN, ceux-ci pouvant être très nombreux, les VLAN étant groupés.
MSTP a été inspiré par le protocole de Cisco Multiple Instances Spanning Tree Protocol (MISTP).
MSTP est compatible avec les ponts RSTP, le format de BPDU étant le même.