Réseaux

Spanning Tree Algorithm

Réseaux : Spanning Tree Algorithm
Sommaire

1. Généralités sur STA

2. Création d'une topologie

3. Messages BPDU

4. Etats des ports

2
Réseaux : Spanning Tree Algorithm
Généralités sur STA

STP est un protocole de gestion de couche 2, qui fournit

des chemins redondants dans un réseau tout en évitant
les boucles de routages.

Tous les protocoles STP utilisent un algorithme qui calcule

le meilleur chemin sans boucle à travers le réseau.

Le protocole STP utilise un algorithme distribué qui

sélectionne un pont d'un réseau connecté de manière
redondante comme la racine d'un arbre associé à la
topologie courante.

STP assigne des rôles à chaque port selon la fonction du

port dans la topologie courante.
3
Réseaux : Spanning Tree Algorithm
Généralités sur STA

Les rôles sont les suivants :

• Root - un port unique d'acheminement pour la topologie

spanning tree ;

• Designated - un port d'acheminement pour chaque

segment du LAN commuté ;

• Alternate - un port bloqué fournissant un chemin de

réserve vers le port Root dans le spanning tree ;

• Backup - un port bloqué dans une configuration

loopback

4
Réseaux : Spanning Tree Algorithm
Généralités sur STA

Les commutateurs qui ont ces fonctions assignées à leurs

ports sont appelés root ou commutateur désigné.

Dans les réseaux Ethernet, un seul chemin actif peut

exister entre deux stations.

Plusieurs chemins actifs entre des stations cause

inévitablement des boucles dans le réseau.

Lorsque les boucles surviennent, certains commutateurs

reconnaissent une même station sur plusieurs ports.

Cette situation entraîne des erreurs au niveau de

l'algorithme d'expédition et autorise la duplication de
trames qui seront expédiées.
5
Réseaux : Spanning Tree Algorithm
Généralités sur STA

L'algorithme spanning tree fournit des chemins redondants

en définissant un arbre qui recense tous les commutateurs
dans un réseau étendu et force ensuite certains chemins
de données à être à l'état bloqués.

À intervalles réguliers, les commutateurs dans le réseau

émettent et reçoivent des paquets spanning tree qu'ils
emploient pour identifier le chemin.

6
Réseaux : Spanning Tree Algorithm
Généralités sur STA

Si un segment de réseau devient inaccessible ou si les

coûts spanning tree change, l'algorithme reconfigure la
topologie spanning tree et rétablit la liaison en activant le
chemin de réserve.

Les opérations spanning tree sont transparentes pour les

stations d'extrémités, qui ne détectent pas s'ils sont
connectés à un segment de réseau local simple ou à un
réseau local commuté à segments multiples.

7
Réseaux : Spanning Tree Algorithm
Création d'une topologie

Tous les commutateurs dans un LAN étendu participant

dans un arbre 'spanning' assemblent des informations sur
les autres commutateurs du réseau.

Ces informations sont échangées sous forme de

messages appelés messages BPDU (Bridge Protocol Data
Unit).

8
Réseaux : Spanning Tree Algorithm
Création d'une topologie

Cet échange de message aboutit aux actions suivantes :

● Un commutateur root unique est élu pour la topologie

réseau spanning tree ;

● Un commutateur désigné est élu par segment de LAN

commuté ;

● Toutes les boucles dans un réseau commuté sont

éliminées en plaçant des ports redondants de
commutateur à l'état Backup ;

● Tous les chemins non nécessaires pour joindre le

commutateur root depuis n'importe où dans le réseau
commuté sont placés en mode STP bloqué.
9
Réseaux : Spanning Tree Algorithm
Création d'une topologie

La topologie d'un réseau commuté actif est déterminée par

les éléments suivants :

● L'identifiant unique associé à chaque commutateur

(l'adresse MAC du commutateur) ;

● Le coût du chemin vers le root associé avec chaque

port du commutateur ;

● L'identifiant du port (l'adresse MAC du port) associé

avec chaque port du commutateur.

10
Réseaux : Spanning Tree Algorithm
Création d'une topologie

Dans un réseau commuté, le commutateur root est le

centre logique de la topologie spanning tree.

Le protocole spanning tree utilise les BPDU pour élire le

commutateur root et le port root pour le réseau commuté,
aussi bien que le port root et le port désigné pour chaque
segment commuté.

11
Réseaux : Spanning Tree Algorithm
Création d'une topologie

Comment un commutateur devient-il Root ?

Si tous les commutateurs sont activés avec la configuration

par défaut, le commutateur avec la plus petite adresse MAC
dans le réseau devient le commutateur root.

Cependant, en raison du modèle de trafic, de nombreux

ports d'acheminements ou types de lignes, le commutateur
promis 'root' n'est peut-être pas idéal.

Un commutateur peut être désigné pour devenir le

commutateur root en augmentant sa priorité (c'est en fait,
diminuer la priorité numérique) sur le commutateur choisi.

12
Réseaux : Spanning Tree Algorithm
Création d'une topologie

Cette opération entraîne la création d'une nouvelle

topologie et fait du commutateur choisi le commutateur root.

Il est également possible de changer la priorité d'un port

afin qu'il soit le port root.

Quand la topologie spanning tree est basée sur des

paramètres par défaut, le chemin entre la source et les
stations de destinations dans un réseau commuté
pourraient ne pas être idéales.

En connectant des ports à haute vitesse à un port qui a un

nombre plus élevé que le port root actuel cela peut
entrainer un changement de port root.

Le but est d'établir la liaison la plus rapide au port root. 13

Réseaux : Spanning Tree Algorithm
Messages BPDU

Les messages BPDUs (Bridge Protocol Data Units)

contiennent:
● des informations de configuration sur le commutateur en

train de transmettre ;
● la priorité de commutateur ;

● la priorité de port ;

● le coût du port ;

Chaque configuration BPDU contient ces informations :

● l'identificateur unique du commutateur considèré comme

'root' ;
● le coût du chemin vers le root jusqu'au port émetteur ;

● l'identificateur du port émetteur ;

14
Réseaux : Spanning Tree Algorithm
Messages BPDU

Le commutateur envoie la configuration BPDU pour

communiquer et calculer la topologie spanning tree.

Une trame MAC transmettant un BPDU envoie l'adresse du

groupe de commutateurs à l'adresse de destination.

Tous les commutateurs connectés au réseau local sur

lequel la trame est transmise reçoivent le BPDU.

Les BPDUs ne sont pas directement expédiés par le

commutateur, mais le commutateur utilise l'information
contenue dans la trame pour calculer un BPDU, et si il y a
des changements topologiques, le commutateur effectue
une transmission BPDU.
15
Réseaux : Spanning Tree Algorithm
Messages BPDU

Un échange BPDU permet d'obtenir les éléments suivants :

● Si un commutateur est élu commutateur root ;

● La plus petite distance vers le commutateur root est

calculée pour chaque commutateur ;

● Un commutateur désigné est sélectionné. C'est le

commutateur le plus près du commutateur root, par
lequel les trames seront expédié vers le root;

● Un port pour chaque commutateur est sélectionné. C'est

le port qui fournira le meilleur chemin du commutateur
vers le commutateur root ;

● Les ports incluent dans le STP sont sélectionnés. 16

Réseaux : Spanning Tree Algorithm
Etats des ports

Des changements topologiques peuvent se produire dans

les réseaux commutés suite au changement d'état d'une
ligne (de up à down et inversement).

Quand un port qui ne participait à la topologie passe

directement à l'état d'acheminement, cela peut créer des
boucles de données temporaires.

Les ports doivent attendre la nouvelle information de

topologie pour se propager par les commutateurs dans le
LAN avant qu'ils ne puissent commencer à acheminer les
trames.

17
Réseaux : Spanning Tree Algorithm
Etats des ports

Les ports doivent permettre à la durée de vie des trames

d'expirer pour les trames qui ont été expédiés en utilisant
l'ancienne topologie.

L'étude immédiate des entrées après un changement de

topologie empêche un flood excessif.

Chaque port d'un commutateur est à l'un de ces états :

● Blocage ;

● Ecoute ;

● Apprentissage ;

● Acheminement ;

● Désactivation.

18
Réseaux : Spanning Tree Algorithm
Etats des ports

Un port change d'état comme suit :

● De l'Initialisation au Blocage ;
● Du Blocage à l'Ecoute ou à la Désactivation ;

● De l'Ecoute à l'Apprentissage ou à la Désactivation ;

● De l'Apprentissage à l'Acheminement ou à la

Désactivation.

19
Réseaux : Spanning Tree Algorithm
Etats des ports

Si la configuration est correcte, chaque port se stabilise à

l'état d'Acheminement ou de Blocage.

Quand l'algorithme spanning tree place un port dans l'état

d'Acheminement, les éléments suivant surviennent :

1.Le port est mis à l'état d'Apprentissage et attend

l'information du protocole qui lui indique de se mettre à
l'état Bloqué ;
2.Le port attend l'expiration du timer protocole qui met le
port à l'état d'Apprentissage ;
3.A l'état d'Apprentissage, le port continu de bloquer
l'acheminement des trames et apprend où se situe les
stations pour la base de données d'Acheminement ;
4.L'expiration du timer protocole met le port à l'état
d'Acheminement, où l'Apprentissage et l'Acheminement 20
sont activés.
Réseaux : Spanning Tree Algorithm
Etats des ports: bloqué

Un port à l'état bloqué ne participe pas à l'Acheminement

des trames.

Après initialisation, un BPDU est envoyé à chaque port du

commutateur.

Un commutateur se considère comme root jusqu'à se qu'il

échange des BPDUs avec les autres commutateurs.

Cet échange détermine lequel jouera réellement le rôle de

commutateur root.

Si il y a uniquement un commutateur dans le réseau, il n'y a

pas d'échange et le délai d'acheminement expire.

Après l'initialisation d'un commutateur, les ports sont 21

toujours à l'état Bloqués.
Réseaux : Spanning Tree Algorithm
Etats des ports: bloqué

Un port à l'état Bloqué effectue les actions suivantes :

● Abandonne les trames reçues du segment au quel le

port est attaché ;
● Abandonne les trames commutées depuis un autre port

pour l'Acheminement ;
● N'inclut pas les adresses des stations dans la base de

données des adresses ;

● Reçoit les BPDUs et les dirige vers le module système ;

● Ne transmet pas le BPDUs reçus du module système ;

● Reçoit et répond aux messages de gestion du réseau.

22
Réseaux : Spanning Tree Algorithm
Etats des ports: bloqué

23
Réseaux : Spanning Tree Algorithm
Etats des ports: écoute

L'état d'Écoute est le premier état de transition dans lequel

un port se trouve après l'état Bloqué.

Le port entre dans cet état quand le protocole spanning tree

détermine que le port devrait participer à l'Acheminement
des trames.

L'apprentissage est désactivé à l'état d'Écoute.

24
Réseaux : Spanning Tree Algorithm
Etats des ports: écoute

Un port à l'état d'Ecoute effectue les actions suivantes :

● Abandonne les trames reçues du segment au quel le

port est attaché ;
● Abandonne les trames commutées depuis un autre port

pour l'Acheminement ;
● N'inclut pas les adresses des stations dans la base de

données des adresses ;

● Reçoit les BPDUs et les dirige vers le module système ;

● Traite les BPDUs reçus du module système ;

● Reçoit et répond aux messages de gestion du réseau.

25
Réseaux : Spanning Tree Algorithm
Etats des ports: écoute

26
Réseaux : Spanning Tree Algorithm
Etats des ports: apprentissage

Un port à l'état d'Apprentissage se prépare à participer à

l'acheminement des trames.

Le port entre dans l'état d'apprentissage à partir de l'état

d'Écoute et effectue les actions suivantes:

● Abandonne les trames reçues du segment au quel le

port est attaché ;
● Abandonne les trames commutées depuis un autre port

pour l'Acheminement ;
● Inclut les adresses des stations dans la base de

données des adresses ;

● Reçoit les BPDUs et les dirige vers le module système ;

● Reçoit, traite et transmet les BPDUs reçus du module

système ;
● Reçoit et répond aux messages de gestion du réseau. 27
Réseaux : Spanning Tree Algorithm
Etats des ports: apprentissage

28
Réseaux : Spanning Tree Algorithm
Etats des ports: acheminement

Le port entre dans l'état d'acheminement à partir de l'état

d'apprentissage.

Un port à l'état d'acheminement effectue les actions

suivantes :

● Achemine les trames reçues du segment au quel le port

est attaché ;
● Achemine les trames commutées depuis un autre port

pour l'Acheminement ;
● Inclut les adresses des stations dans la base de

données des adresses ;

● Reçoit les BPDUs et les dirige vers le module système ;

● Traite les BPDUs reçus du module système ;

● Reçoit et répond aux messages de gestion du réseau.

29
Réseaux : Spanning Tree Algorithm
Etats des ports: acheminement

30
Réseaux : Spanning Tree Algorithm
Etats des ports: désactivé

Un port à l'état Désactivé ne participe pas à l'acheminement

des trames ou dans le STP.

Un port Désactivé effectue les actions suivantes :

● Abandonne les trames reçues du segment au quel le

port est attaché ;
● Abandonne les trames commutées depuis un autre port

pour l'Acheminement ;
● N'inclut pas les adresses des stations dans la base de

données des adresses ;

● Reçoit les BPDUs mais ne les dirige pas vers le module

système ;
● Ne reçoit pas les BPDUs du module système pour la

transmission ;
● Reçoit et répond aux messages de gestion du réseau. 31
Réseaux : Spanning Tree Algorithm
Etats des ports: désactivé

32