Les ponts et commutateurs:
Apprentissage et
suppression de boucles
(algorithme du Spanning Tree)
Alain AUBERT
[email protected] 0
Les ponts:
précurseur des switch
1
Les fonctions d'un pont
• Pont: équipement de couche 2
• Pont relie des segments réseaux (domaines de collision séparés)
entre eux:
• Exemple: pont à 2 ports (pont 1)
1 segment= 1domaine de collision
1 Hub
Les fonctions d'un pont
• Fonction correspondant à celle de la couche réseau,
mais n’utilisent pas de données propre à cette
couche, mais celle de la couche MAC (adresses
universelles).
• Leur fonction principale est de transmettre ou non
(fonction de filtrage) des trames sans modification
de leur contenu LLC et de leur adresses
universelles.
• Ils ont deux utilités:
— augmentation de la bande passante de chaque segment en
limitant les paquets transmis sur segment.
— augmentation quasi indéfinie de la taille d’un réseau local sans
problème de couche MAC (collision...). Pour cela les ponts
stockent et réémettent les paquets en ne tenant compte des
contraintes MAC que sur chaque segment.
3
Le pont de base
• C’est un pont reliant deux ou plusieurs segments distincts. Chaque
segment est relié a un port du pont.
• Fonction de stockage (éviter les collisions d’un segment vers
l’autre) mais pas de fonction de filtrage
• Le stockage temporaire permet de lever les contraintes de longueur,
mais il n’y a pas d’augmentation possible du trafic global.
Segment S1 Segment S2
Le pont de base
Segment S1
M1 M2 M3 t
Segment S2
M1 M3 M2 t
Emission Emission
M1 sur S1 M2 sur S1
Le pont réémet M2 a été stocké par
M1 sur S2 le pont car M3
occupait S2, puis il
est réémis sur S2
5
Les pont intelligents
• Ajout d’une fonction de filtrage des trames locales pourra
permettre d’augmenter le trafic global.
• Le pont doit donc reconnaître les trames destinées à l’extérieur
du segment émetteur.
• Comment fait-il ? mécanisme d'apprentissage
Fonction de filtrage
Segment S1 Segment S2
Ponts intelligents:
mécanisme d'apprentissage
• Chaque pont possède une mémoire cache de stockage
(mémoire remise à jour régulièrement). Cette mémoire contient
une base de données constituées :
— des adresses universelles,
— du numéro du port de connexion correspondant,
— de la date de dernier accès.
• Cette mémoire cache est initialement vide.
• Le pont écoute en mode promiscuous (il écoute tout) les
trames transmises.
• Pour une trame donnée, le pont enregistre son adresse source
et le port de réception (s’ils ne sont pas déjà définis), il met à
jour le champ correspondant au moment d’arrivée.
• Il recherche dans sa mémoire cache si l’adresse destination
existe :
— si oui, il envoie la trame sur le port associé, ou la détruit si le port
associé est le même que celui d’émission (trafic local). Ceci réalise la
fonction de filtrage.
— si non, il envoie la trame sur tous les ports sauf sur celui de réception. 7
Ponts intelligents:
mécanisme d'apprentissage
M1 M2 M3 M4
P1 P2
B
P3
M5
• M1 → M2 • P1 → P2 et P3 • M1 – Port 1
• M2 → M3 • P1 → P2 et P3 • M2 – Port 1
• M3 → M1 • P2 → P1 • M3 – Port 2
• M3 → M4 • P2 → P1 et P3 • Mise à jour date M3
• M4 → M3 • P2 → détruit • M4 – Port 2
• M1 → M2 • P1 → détruit • Mise à jour date M1
• M1 → M5 • P1 → P2 et P3 • Mise à jour date M1
• M5 → M1 • P3 → P1 • M5 – Port 3
Ports de réception et Contenu mémoire 8
Transmission trame
de … vers d'émission cache du pont
Les commutateurs ou
switch
9
Caractéristiques d'un switch
• Un switch est un pont intelligent multiports
• Utilisés dans les réseaux dits Ethernet commuté ou
Switch Ethernet
• Il permet de commuter la trame envoyée sur le bon
port de destination si la table de commutation (ou
table MAC) est renseignée
• Le temps de commutation est fixe
10
Caractéristiques d'un switch
• 2 modes de fonctionnement
— « à la volée » (Cut through): sans attendre la vérification du
CRC , le switch commute la trame sur le bon port de destination
– Ne permet pas de vérifier la validité des trames et peut
provoquer la commutation de trames erronées qui seront
transmises au destinataire
— Store and forward: mémorise les trames et vérifie le CRC avant
de les commuter
– Temps de transfert plus long et proportionnel à la longueur
de la trame
– La diminution du rapport coût/performance
11
Mécanisme d’apprentissage
construction de la table de commutation
Table de
commutation
(ou table MAC)
12
Mécanisme de commutation de trames
Table de
commutation
13
Suppression de boucles
Algorithme du Spanning Tree
14
Introduction
• Le protocole Spanning Tree (STP) est un protocole de
couche 2 (liaison de données) conçu pour les
commutateurs et les ponts.
• La spécification de STP est définie dans le document
IEEE 802.1d. Sa principale fonction est de s'assurer qu'il
n'y a pas de boucles dans un contexte de liaisons
redondantes entre des matériels de couche 2.
• STP détecte et désactive des boucles de réseau.
• Il permet de faire en sorte que des matériels compatibles
avec le standard ne fournissent qu'un seul chemin entre
deux stations d'extrémité.
STP
Topologie physique avec boucles Topologie logique sans boucles
sous forme d’un arbre 15
Problématique
• Ajout d'un pont redondant pour la fiabilité
• Sans STP (Spanning Tree) trois problèmes peuvent survenir :
— 1. Des tempêtes de broadcast
— 2. Une instabilité des tables MAC
— 3. Transmission de trames multiples
16
Problématique
• Des tempêtes de broadcast :
— Lorsque des trames de broadcast sont envoyées (FF-FF-FF-FF-FF-FF
en destination), les switchs les renvoient par tous les ports. Les trames
circulent en boucles et sont multipliées.
— Les trames n'ayant pas de durée de vie (TTL comme les paquets IP),
elles peuvent tourner indéfiniment.
17
Problématique
• Une instabilité des tables MAC :
— Quand une trame, même unicast, parvient aux switches connectés en
redondance, le port du switch associé à l'origine risque d'être erroné. Une
boucle est susceptible d'être créée.
— PC1 envoie une trame au PC2. Les deux commutateurs reçoivent la trame sur
leur port 0/2 et associent ce port à l'adresse mac de PC1. Si l'adresse de PC2
est inconnue, les deux commutateurs transfèrent la trame à travers leur port
0/1. Les commutateurs reçoivent respectivement ces trames inversement et
associent l'adresse MAC de PC1 au port 0/1. Ce processus peut se répéter
indéfiniment.
18
Problématique
• Transmission de trames multiples : dans un réseau commuté redondant, il
est possible pour une unité d’extrémité de recevoir plusieurs trames.
— Supposez que l'adresse MAC du PC2 ait été supprimée par les deux commutateurs, à
cause d'un dépassement du temps de rafraîchissement.
— Supposez également que le PC1 dispose encore de l’adresse MAC du PC2 dans sa
mémoire cache ARP et envoie une trame unicast au PC2.
— Le PC2 reçoit la trame, car il figure sur le même segment que le PC1.
— Le commutateur SW1 ne dispose pas de l’adresse MAC du PC2 et diffuse donc la trame
sur ses ports. Le commutateur SW2 ne connaît pas non plus le port du PC2. Il diffuse la
trame qu’il a reçue et le PC2 reçoit donc plusieurs copies de la même trame. Cela est le
résultat d’opérations inutiles sur toutes les unités.
19
Algorithme du Spanning Tree:
exemple d'application
20
Identification des différents domaines de collisions
• Chaque Hub non cascadé forme un domaine de
collision.
• Les hubs cascadés forment un seul domaine de
collision.
• Il y a donc 4 domaines de collision.
• Noms :
— Hub1 segment 1 S1
— Hub2 et Hub3 segment 2 S2
— Hub4 segment 3 S3
— Hub5 et Hub6 segment 4 S4
21
Objectif de l’algorithme de Spanning Tree
Pont racine
0
0 Port racine
10
10 10
10
10
10
10
Port désigné
10
Port alternatif
1. Déterminer le pont racine
2. Déterminer les ports racines
3. Déterminer les ports désignés et alternatifs 22
Objectif de l’algorithme de Spanning Tree
Pont racine
0
0 Port racine
10
10 10
10
10
10
10
Port désigné
10
Port alternatif
1. Déterminer le pont racine
2. Déterminer les ports racines
3. Déterminer les ports désignés et alternatifs 23
Le protocole 802.1d:
Arbre de recouvrement (Spanning Tree)
• Pour cela, sur chaque pont est implanté le protocole spanning tree
(SPT) normalisé par l'IEEE sous la norme 802.1d.
• Le protocole Spanning Tree (STP) est un protocole de couche 2
(liaison de données) conçu pour les commutateurs et les ponts.
• Le protocole spanning tree doit supprimer les chemins redondants
en construisant un arbre à partir d'un graphe cyclique. Ce protocole
doit être implanté sur chaque pont.
• Pour le mettre en œuvre, les ponts vont s'échanger des trames
BPDU (Bridge Protocol Data Unit) de 34 octets. Ces trames
sont adressées en multicast, seuls les ponts les liront.
STP
Topologie physique avec boucles Topologie logique sans boucles
sous forme d’un arbre 24
Messages du protocole 802.1d:
BPDU
• Les ponts vont s’envoyer mutuellement des messages
entre eux
• Le protocole 802.1d utilise des messages (trames
BPDU) contenant l'information suivante:
— Root ID (R): identification actuelle du pont racine
— Cost (C) : Coût du lien de plus faible coût entre le pont qui
transmet le message et la racine
— Transmitting ID (T): identification du pont qui transmet le
message
• Ces messages sont envoyés en multicast [adresse : all
bridges]
25
Interprétation de deux messages 802.1d
• R= identification du pont racine
• C= Coût
• T= Identification du pont qui transmet le message
• Le message Mi[R=Pi,C=Ci, T=Ti] est meilleur que
Mj[R=Pj,C=Cj, T=Tj] si
— Pi<Pj
— Pi=Pj et Ci<Cj
— Pi=Pj et Ci=Cj et Ti<Tj
26
Objectif de l’algorithme de Spanning Tree
Pont racine
0
0
10
10 10
10
10
10
10
10
1. Déterminer le pont racine
2. Déterminer les ports racines
3. Déterminer les ports désignés et alternatifs 27
Fonctionnement du protocole:
1. Détermination du pont racine
• Au démarrage, chaque pont se considère comme la racine et
transmet un message 802.1d avec un coût de 0 sur tous ses
ports
R=P1, C=0, T=P1]
R=P1, C=0, T=P1]
R=P3, C=0, T=P3]
R=P4, C=0, T=P4] R=P2, C=0, T=P2]
R=P3, C=0, T=P3]
R=P4, C=0, T=P4]
R=P2, C=0, T=P2]
R=P5, C=0, T=P5]
R=P5, C=0, T=P5]
28
Fonctionnement du protocole:
1. Détermination du pont racine
• Si un pont reçoit sur un port un meilleur message 802.1d
que celui qu'il transmettait, il arrête de transmettre le
message 802.1.d qu'il transmettait
• Dans un réseau la racine est le pont avec le plus petit
identificateur
• Chaque pont peut déterminer quelle est la racine en
analysant tous les messages 802.1d reçus
29
Fonctionnement du protocole:
1. Détermination du pont racine
• P1 n'a pas reçu de meilleur message sur un de ses ports que celui qu'il
émettait. P1 continue à émettre son message 802.1d ([R:=P1, C=0,
T=P1]).
P1 se considère comme le pont racine.
• P2 a reçu un meilleur message sur son port P2S2 ([R:=P1, C=0, T=P1]),
il cesse d'émettre son message 802.1d ([R:=P2, C=0, T=P2])
P2 considère que P1 est le pont racine.
• P3 a reçu un meilleur message sur son port P3S2 ([R:=P1, C=0, T=P1]),
il cesse d'émettre son message 802.1d ([R:=P3, C=0, T=P3])
P3 considère que P1 est le pont racine.
• P4 a reçu un meilleur message sur son port P4S1 ([R:=P1, C=0, T=P1]),
il cesse d'émettre son message 802.1d ([R:=P4, C=0, T=P4]
P4 considère que P1 est le pont racine.
• P5 a reçu un meilleur message sur son port P5S3 ([R:=P2, C=0, T=P2]) il
cesse d'émettre son message 802.1d ([R:=P5, C=0, T=P5])
P5 considère que P2 est le pont racine. 30
Objectif de l’algorithme de Spanning Tree
Pont racine
0
0 Port racine
10
10 10
10
10
10
10
10
1. Déterminer le pont racine
2. Déterminer les ports racines
3. Déterminer les ports désignés et alternatifs 31
Fonctionnement du protocole:
2. Détermination des ports racines
• Le port racine d'un pont est le port qui se trouve topologiquement le plus
proche de la racine.
C’est le port qui a reçu le meilleur message 802.1d ( )
• P2 a reçu un meilleur message sur son port P2S2
([R:=P1, C=0, T=P1])
• P3 a reçu un meilleur message sur son port P3S2
([R:=P1, C=0, T=P1])
• P4 a reçu un meilleur message sur son port P4S1
([R:=P1, C=0, T=P1])
• P5 a reçu un meilleur message sur son port P5S3
([R:=P2, C=0, T=P2])
32
Objectif de l’algorithme de Spanning Tree
Pont racine
0
0 Port racine
10
10 10
10
10
10
10
Port désigné
10
Port alternatif
1. Déterminer le pont racine
2. Déterminer les ports racines
3. Déterminer les ports désignés et alternatifs 33
Fonctionnement du protocole:
3. Détermination des ports désignés et alternatifs
• Seul le pont P qui se considère comme le pont
racine transmet son message 802.1d [R:=P, C=0,
T=P]).
Dans notre cas, c’est P1
• Les autres ponts lisent le message 802.1d sur le port
racine et le retransmettent sur l'autre port en
modifiant
— le transmetteur (T)
— le coût (C= C reçu + coût du port racine du pont où le message
a été reçu)
34
Fonctionnement du protocole:
3. Détermination des ports désignés et alternatifs
• P1 transmet un nouveau message 802.1d sur S1 et S2
— M_P1S1(R=P1,C=0,T=P1)
— M_P1S2(R=P1,C=0,T=P1).
• Le pont 2 retransmet le message
— M_P2S3(R=P1,C=10,T=P2)
• Le pont 3 retransmet le message
— M_P3S3(R=P1,C=10,T=P3)
• Le pont 4 retransmet le message
— M_P4S4(R=P1,C=10,T=P4)
• Le pont 5 retransmet le message
— M_P5S4(R=P1,C=20,T=P5)
— A ce moment là, P5 considère que P1 est le pont racine
35
Fonctionnement du protocole:
3. Détermination des ports désignés et alternatifs
• Les ports du Pont Racine sont par définition désignés
• Lorsqu'un pont reçoit un meilleur message sur un port non
racine que celui qu'il transmet, il considère ce port comme
un port alternatif.
• Lorsqu'un pont ne reçoit pas un meilleur message sur un
port non racine que celui qu'il transmet, il considère ce port
comme un port désigné.
36
Fonctionnement du protocole:
3. Détermination des ports désignés et alternatifs
• Pont P2:
— P2 transmet sur P2S3 le M_P2S3(R=P1,C=10,T=P2)
— P2 reçoit sur P2S3 le M_P3S3(R=P1,C=10,T=P3)
— Donc P2 ne reçoit pas un meilleur message: il considère donc
que son port P2S3 est un port désigné
• Pont P3:
— P3 transmet sur P3S3 le M_P3S3(R=P1,C=10,T=P3)
— P3 reçoit sur P3S3 le M_P2S3(R=P1,C=10,T=P2)
— Donc P3 reçoit un meilleur message: il considère donc que
son port P3S3 est un port alternatif
• Pont P4:
— P4 transmet sur P4S4 le M_P4S4(R=P1,C=10,T=P4)
— P4 reçoit sur P4S4 le M_P5S4(R=P1,C=20,T=P5)
— Donc P4 ne reçoit pas un meilleur message: il considère
donc que son port P4S4 est un port désigné
• Pont P5:
— P5 transmet sur P5S4 le M_P5S4(R=P1,C=20,T=P5)
— P5 reçoit sur P5S4 le M_P4S4(R=P1,C=10,T=P4)
— Donc P5 reçoit un meilleur message: il considère donc que
son port P5S4 est un port alternatif 37
Récapitulatif:
Rôles des ports
• Vis-à-vis des messages 802.1d
— Port racine (Root)
– port via lequel on reçoit les messages provenant de la racine
par le plus court chemin
– un port racine ne transmet pas de messages 802.1d mais les
lit
– un seul port racine par switch
— Port désigné (Desgn)
– port via lequel le pont retransmet les messages 802.1d reçus
de la racine
– message 802.1d transmis par un pont:
– racine actuelle, identification du pont, coût jusqu'à la racine
– un port est désigné si le message qu'il transmet est meilleur
que le meilleur message qu'il reçoit
38
— Port alternatif (Altn): reçoit uniquement les message. 802.1d
Différents états STP d’un port
Cinq états de ports peuvent rencontrés sur un port STP. Chaque
état comporte un délai:
• Etat « Blocking » (sur port alternatif)
— Rejette toutes les trames de données venant du segment attaché
— Rejette toutes les trames de données venant d'un autre port de
transfert
— N'intègre aucune emplacement de station dans sa MAC table (il n'y pas
d'apprentissage)
— Reçoit les BPDUs et les transmet à son système
— N'envoie pas de BPDUs reçus de son système
• Etat « Listening » (sur port racine ou désigné)
— Rejette toutes les trames de données venant du segment attaché
— Rejette toutes les trames de données venant d'un autre port de
transfert
— N'intègre aucune emplacement de station dans sa MAC table (il n'y pas
d'apprentissage)
— Reçoit les BPDUs et les transmet à son système (port racine)
— Envoie les BPDUs reçus de son système (port désigné) 39
—
Différents états STP d’un port
• Etat « Learning » (sur port racine ou désigné)
— Rejette toutes les trames de données venant du segment attaché
— Rejette toutes les trames de données venant d'un autre port de transfert
— Intègre les emplacements de station dans sa MAC table (apprentissage)
— Reçoit les BPDUs et les transmet à son système
— Envoie les BPDUs reçus de son système
• Etat « Forwarding » (sur port racine ou désigné)
— Commute toutes les trames de données venant du segment attaché
— Commute toutes les trames de données venant d'un autre port de
transfert
— Intègre les emplacements de station dans sa MAC table (apprentissage)
— Reçoit les BPDUs et les transmet à son système
— Envoie les BPDUs reçus de son système
• Etat « Disabled »
— Cet état est similaire à l'état « blocking » sauf que le port est considéré 40
physiquement non opérationnel (shut down ou problème physique).
Changement d'états d’un port
— L'age maximal de 20 secondes par défaut est le temps maximal avec que
STP effectue de nouveaux calculs quand une interface ne reçoit plus de
BPDUs.
— Le temps de forwarding de 15 secondes par défaut est le temps de
passage d'un état "listening" à "learning" et de "learning" à "forwarding".
Aussi, la fréquence d'envoi de BPDUs Hello est de 2 secondes par
défaut.
41
Algorithme du Spanning Tree
sur les switch CISCO
42
ID d’un switch
• Le switch racine sera le point central de l'arbre STP.
• Le switch qui aura l'ID la plus faible sera celui qui sera élu racine.
• L'ID du switch comporte deux parties, d'une part, la priorité (2 octets) et,
d'autre part, l'adresse MAC (6 octets). La priorité 802.1d est d'une valeur de
32768 par défaut (ce sont des multiples de 4096 sur 16 bits). Par exemple,
un switch avec une priorité par défaut de32768 (8000 Hex) et une adresse
MAC 00 :A0 :C5:12:34:56, prendra l'ID 8000:00A0 :C512:3456.
• On peut changer la priorité d'un switch avec la commande :
(config)#spanning-tree [vlan vlan-id] priority priority
• Sur un switch racine, tous les ports sont des ports désignés, autrement dit,
ils sont en état « forwarding », il envoient et reçoivent le trafic. 43
Coût des ports
• La commande de configuration est :
(config-if)#spanning-tree cost cost
44
Quelques commandes IOS CISCO
• Pour le diagnostic :
#show spanning-tree [?]
• Désactivation de STP :
(config)#no spanning-tree vlan vlan-id
• Priorité du switch :
(config)#spanning-tree [vlan vlan-id] priority priority
• Coût et priorité d'un port :
(config-if)#spanning-tree [vlan vlan-id] cost cost
• Paramètres de timing :
(config)#spanning-tree [vlan vlan-id] max-age seconds
6 à 200 secondes
(config)#spanning-tree [vlan vlan-id] forward-time seconds
4 à 200 secondes
(config)#spanning-tree [vlan vlan-id] hello-time seconds
45
1 à 10 secondes
