Spanning Tree

Littéralement « arbre recouvrant ». Méthode de routage utilisée dans les ponts entre réseaux locaux, notamment de type Ethernet. Elle utilise un principe d’apprentissage par lequel chaque noeud, en observant l’adresse des trames qui lui sont envoyées, reconstitue peu à peu l’arborescence du sous-réseau qui le concerne.
Le protocole « spanning tree « a été développé par le comité IEEE 802.1, dans le but d’interconnecter tout type de réseau, et ce quelle que soit la topologie utilisée. Le but de ce protocole est de construire un arbre qui
recouvre tout le réseau, pour que tout point du réseau soit accessible à partir de toutes les feuilles de l’arbre.
Sur un réseau local commuté, les segments sont souvent connectés entre eux de façon redondante afin d’obtenir une plus grande tolérance aux pannes, c’est ce qu’on appelle une architecture maillée. Le problème majeur de ces chemins redondants pour accéder à une même destination est la création de boucles. Or, au niveau 2, il n’est pas possible de détecter et d’éliminer une trame qui boucle (au niveau 3, c’est le TTL qui s’en charge). Ces boucles deviennent bloquantes pour le réseau en saturant la bande passante.
Le but du spanning tree est de détecter les boucles et de les supprimer en désactivant certaines interfaces de certains ponts afin d’obtenir une architecture arborescente du réseau local. Ainsi, à un instant donné, il
n’existe qu’un seul chemin entre segments distants. Les ports qui créent des boucles sont mis dans l’état « blocking « , c’est à dire dans un état passif, à l’exception des paquets BPDU (Bridge Protocol Data Unit), paquets échangés par les ponts et contenant les informations nécessaires au bon déroulement de l’algorithme du spanning tree.
Principe de fonctionnement :

• Election d’un pont racine sur tous les LAN, pour établir à partir de celui-ci un arbre recouvrant, sans boucles. A sa mise sous tension ou bien lorsqu’il est isolé, tout pont considère qu’il est lui-même le pont racine. Il émet  donc périodiquement (toutes les 2s) des trames en diffusion sur les réseaux auxquels il est raccordé, indiquant qu’il est racine, et précisant son identificateur sur 8 octets. Cet identificateur est composé de 2 octets de priorité (fixé par l’administrateur) et des 6 octets de l’adresse MAC « la plus faible « du pont. Le pont élu est celui de plus haute priorité, c’est à dire ayant l’identificateur le plus faible. Chaque fois qu’un pont reçoit une BPDU d’un pont racine qui lui est supérieur, il cesse de s’annoncer en tant que pont racine et répercute les messages annonçant le nouveau pont racine.
• Calcul de la distance entre le pont racine et les autres ponts.
• Election d’un pont désigné sur chaque LAN (le plus proche de la racine en terme de coûts), et désactivation de certains ports des autres ponts.
• Choix d’un port racine sur chaque pont désigné.

Les ports racines sont ceux qui sont du côté du pont racine, les autres ports sont les ports désignés. Sur chaque réseau éloigné (auquel le pont racine n’est pas directement connecté), les ponts vont s’informer mutuellement de l’identificateur du pont qu’ils ont élu racine, et du coût du chemin proposé vers ce pont racine. Le choix se porte sur le pont qui propose le chemin le moins coûteux. Ce coût (Path cost) est normalement la somme de l’inverse des débits des réseaux traversés, soit encore proportionnel à la somme des délais d’émission.
Les autres ponts vont placer leur port dans un état passif (blocking) de manière à éliminer les boucles. Dans le cas d’un litige, lorsque des ponts proposent le même « Path Cost », la décision se fait par rapport à l’identificateur des ponts. Dans le cas où un pont aurait luimême plusieurs ports connectés au réseau, le port de plus faible identificateur est choisi.
Le spanning tree, spécification de l’IEEE 802.1d, est un protocole de niveau 2 du modèle OSI (couche liaison de données). Il est employé sur les réseaux d’entreprise pour permettre aux ponts et commutateurs de communiquer entre eux pour découvrir et circonvenir les boucles physiques d’un même réseau.
Ce protocole spécifie un algorithme que les commutateurs utilisent pour créer une topologie logique sans boucle basée sur un arbre de recouvrement unique dit »spanning tree « . Cet arbre est construit à partir d’un commutateur racine appelé root bridge. Chaque commutateur va alors calculer le plus court chemin vers le root bridge et modifier l’état de ces ports (état bloqué ou passant) pour éviter les éventuelles boucles et repérer les chemins redondants. La construction de l’arbre s’effectue grâce à l’échange de messages appelé BPDU (Bridge Protocol Data Unit) à intervalles réguliers entre tous les commutateurs tournant STP sur une adresse multicast de niveau MAC. A chaque changement de topologie du réseau, ajout d’un nouveau switch, défaillance d’un lien, l’arbre STP est recalculé, il y a donc reconfiguration des ports des commutateurs évitant ainsi les pertes de connectivité et la création d’éventuelle boucle.
Pour chaque vlan est associé une instance de STP, on parle alors de PVST (Per Vlan Spanning Tree). On peut avoir une seule instance STP pour l’ensemble des Vlans, qui est moins gourmand en charge CPU sur les commutateurs ainsi qu’en bande passante sur les liaisons inter-swicthes, alors que le PVST permet une plus grande latitude dans la gestion du spanning tree.

• Le bridge id

Chaque commutateur possède un identifiant unique appelé »bridge id « . Cet identificateur est l’association de deux éléments :

• Le bridge priority : c’est en entier codé sur 2 octets variant de 0 à 65535. Sur les catalysts CISCO,

la valeur de bridge priority est définie par défaut à 32768.

• L’adresse MAC codée sur 6 octets. Le commutateur gère un pool d’adresse MAC et s’y attribue une adresse MAC par vlan.

La valeur de bridge id est très importante dans le STP car il permet à l’algorithme de STP de déterminer le root bridge, la racine de l’arbre STP. Le root bridge est l’élément central du spanning tree et contrôle l’arbre qui permet d’éviter des boucles. Il donc important de normaliser ce paramètre. Comme il y a une instance STP par vlan, un switch peut avoir un rôle de root bridge pour un vlan donné et pour un autre vlan ne pas avoir ce rôle. Un switch va donc posséder plusieurs valeurs de bridge id.

• Le port cost

Ce paramètre est un entier codé sur 2 octets variant de 1 à 65535 qui permet d’associer à chaque port un coût de transmission des trames. Ce coût est basé sur le média utilisé ou la bande passante, plus une liaison sera rapide, plus son coût sera petit. Le port ayant le coût le plus petit sera préféré. Il est calculé par défaut à l’aide de la formule suivante : 1000 / le débit du média utilisé en Mbit/s
Cependant, cette règle n’est plus valable pour les liens supérieurs à 10 Mbps.
L’IEEE préconise l’utilisation des valeurs suivantes. Ces valeurs sont celles à respecter lors de l’implémentation de STP.

Ce paramètre sert également au calcul du chemin le plus court vers le root bridge ou le root path cost.
Du fait d’avoir une instance STP par vlan, le port du switch peut très bien avoir un coût différent par vlan.

• Le port priority

En plus d’attribuer au port un coût, on peut lui spécifier une priorité. A coût égal, cette priorité permettra de spécifier le port qui sera chargé de transmettre les trames. Ce rôle sera tenu par le port ayant la priorité la
plus petite. Si tous les ports ont la même valeur de port priority, c’est le port qui possède le plus petit identifiant, port Id qui sera choisi.
Les valeurs port priority sont comprises entre 0 et 63. La valeur par défaut est 32.
Pour favoriser l’utilisation d’un port à un autre (lorsque le coût est identique) la valeur doit être inférieure à 32.
La préconisation est donc de diviser par 2 le port priority, permettant ainsi d’intercaler d’autres ports entre ces 2 priorités.
Du fait d’avoir une instance STP par vlan, le port du switch peut très bien avoir une priorité différente par vlan.

• L’algorithme Spanning Tree

Tous les switchs tournant STP s’échangent des messages BPDUs à intervalle régulier.
Ces messages BPDUs contiennent les informations suivantes :

• Root BID : le Bridge ID du swich considéré comme Root Bridge
• Root Path Cost : Le coût du chemin pour atteindre le root bridge à partir du port d’émission
• Sender BID : Le bridge Id du switch envoyant le BPDU
• Port Id : l’identifiant du port qui émet le BPDU

L’algorithme STP se décompose en trois phases :

• L’élection du root bridge
• L’élection des root ports
• L’élection des Designated Ports
• L’élection de root bridge

Au démarrage, chaque switch se considère comme le root bridge.
Ils émettent donc un BPDU contenant dans le champ Root BID leur valeur de Bridge Id. Quand un switch reçoit un BPDU, il compare sa valeur Bridge ID avec la valeur Root Bid reçue. Si la valeur reçue est plus petite, il garde en mémoire cette valeur et transmet des BPDUs en conséquence. Au final, le switch, possédant la plus petite valeur de bridge id, sera désigné Root Bridge. Si plusieurs switchs possèdent la même valeur de bridge id, le critère de choix retenu est l’adresse MAC. Le switch possédant la plus petite adresse MAC sera alors désigné root bridge. Il est possible de prendre en compte d’autres paramètres pour désigner le root bridge.
Pour un réseau donné, Il n’existe qu’un seul root bridge. Tous les ports du root bridge sont dits »designated ports  » qui sont généralement dans l’état »forward « . Dans cet état, le port peut transmettre et recevoir du trafic. Le root path cost associé à chaque port du root bridge vaut zéro.

• L’élection des root port

Une fois le root bridge désigné, tous les non root bridges vont calculer pour chacun de leurs ports le coût du chemin pour atteindre le root bridge.
Il n’y a qu’un root port par switch. Le port possédant le plus petit chemin pour atteindre le root bridge ou »root path cost « , sera désigné »root port « .
Si plusieurs ports possèdent le même »root path cost « , le critère de sélection est :

• Le cost port : le port ayant le coût le plus petit sera choisi. En cas d’égalité, la décision s’effectuera en fonction du port priority.
• Le port priority : le port ayant la plus petite priorité sera choisi. En cas d’égalité, le choix s’effectuera en fonction port id.
• Le port Id : le port ayant le plus petit port Id sera choisi.

Les ports des switchs directement connectés au root bridge seront les roots ports.
Le root port est dans l’état »forward « .

• L’élection des designated ports

Une fois le root port désigné, chaque switch va transmettre dans ses BPDUs le root path cost de son root port.
Sur le segment, le port qui sera désigné comme designated port sera celui qui émet un BPDU contenant le meilleur root path cost, donc le plus petit. Pour un segment, il n’y a qu’un seul designated port. Si plusieurs ports émettent sur le segment un root path cost identique, le critère de sélection est :

• Le sender bridge id : le port du switch possédant la plus petite valeur de bridge id sera choisi. En cas d’égalité, le choix s’effectuera sur la valeur de port cost,
• Le port cost : le port possédant la plus petite valeur de port cost sera choisi. En cas d’égalité, la décision se fera en fonction du port priority.
• Le port priority : le port ayant la priorité la plus petite sera choisi. S’il y a toujours égalité, il y aura comparaison du port id.
• Le port Id : le port ayant le plus petit port Id sera choisi.

Les ports dits »designated ports  » sont dans l’état »forwarding « , le trafic peut être reçu et émis par ce port. Les autres ports seront des non designated port et seront mis dans l’état »blocking  » aucun trafic ne passera par
ces ports, ils écouteront seulement le BPDU.
Le root bridge est le switch D car il possède la valeur de bridge id la plus petite. Donc tous ses ports sont dits designated port. Le port du switch C qui est directement connecté au root bridge. Il est donc le root port du switch C. Même chose pour le switch B.
Le port 1/1 et le port ½ du switch A ont le même root path cost qui vaut 8. Ils ont le même port cost et le même port priority la décision s’effectue donc au niveau du port id. le port 1/1 est donc le root port du switch A.
Détermination du Designated port sur la liaison switch A-C : Le meilleur root path cost du switch A est 8, le meilleur root path cost du switch C est 4 donc le port du switch C sera le DP. Détermination du Designated port sur la liaison switch A-B : Le meilleur root path cost du switch A est 8, le meilleur root path cost du switch B est 4 donc le port 1/1 du switch B sera le DP et le port 1/2 du switch A sera bloqué.

• Etat des ports

En mode normal, un port peut être dans l’état »blocking  » ou l’état »forwarding « . Lors d’un changement de topologie réseau, un port dans l’état »blocking  » peut passer à l’état »forwarding « . Seulement, ce changement d’état ne se fait pas immédiatement. Le changement d’état s’effectue de la manière suivante :

• Etat blocking : le port reste environ 20 secondes dans l’état »blocking « . Dans cet état, le port ne laisse passer aucun trafic mais continue d’écouter les BPDUs. Ensuite, il passe dans l’état »listening « .
• Etat listening : Le port dans cet état, il écoute l’ensemble des trames mais ne transmet toujours pas de trames. Il reste dans cet état 15 secondes (valeur par défaut du timer fwdelay), puis passe dans l’état »learning « .
• Etat learning : Dans cet état, le port scrute les trames pour remplir sa table de MAC adresses mais il ne transmet aucune trame. Cette phase dure environ 15 secondes (valeur par défaut du timer fwdelay). A la fin de cette phase d’apprentissage, le port passe dans l’état »forwarding « .
• Etat forwarding : le port continue à remplir sa table MAC adresse et transmet les trames.

Par défaut, le passage de l’état »blocking  » à l’état »forwarding  » prend 50 secondes. Ce temps peut être diminué pour améliorer la convergence STP en jouant sur la valeur des timers STP ou bien en activant sur
les ports différents mode comme le mode portfast.
Mettre un port dans le mode »portfast  » permet à celui-ci de passer de l’état »blocking  » à l’état l’état »forwarding  » sans passer par les états intermédiaires »listening  » et »learning « . Cette fonction doit être activée de préférence sur les ports connectés directement à des hosts. Cependant si le host est un hub, un concentrateur ou un swich, une boucle temporaire peut être créée. Ce mode est à utiliser à bon escient.Ce mode n’est pas supporté par les liens trunks.