Etablissement : UVT Module : Fondement des réseaux
Enseignant : Sahbi Bahroun Classe : 1 N2TR
TD : Méthode d’accès CSMA/CD
Exercice 1:
1
Soient A et B deux stations accrochées à un réseau Ethernet, et distantes de 1000m. Dans ce réseau
Ethernet, on transmet des trames de 512 bits sur une ligne de débit 10Mbits/s. La vitesse de propagation
dans le câble est de 220 000 km/s. La station A veut émettre une trame. Elle « écoute » le canal : il est
libre. Elle transmet. La station B a aussi des trames à transmettre?
1- Quel est le délai pendant lequel il y a risque de collision entre les trames émises par A et les trames
émises par B ?
2- Si la station B décide d'émettre 2,46 µs plus tard que la station A, quand la station A détectera-t-
elle la collision ? Combien de bits aura-t-elle transmis ?
3- Considérer deux stations A et B distantes de 14km. Ces deux stations émettent exactement en
même temps une trame de 512 bits. Quelles seront les conséquences ?
4- Les deux stations A et B sont maintenant éloignées d'une distance L à déterminer. Examiner le cas
où la station B émet juste avant que les bits émis par la station A ne lui parvienne. Quelle est la
distance L maximale admissible pour que la collision soit détectée par les machines (donc pour
qu'il n'y ait pas de perte de données).
5- Quelle longueur minimale doivent posséder les trames émises par chacune des machines pour qu'il
soit impossible de ne pas se rendre compte d'une collision (relation entre le temps d'émission et le
temps de propagation)?
Exercice 2:
On considère un réseau local IEEE 802.3. L’algorithme BEB pour la résolution des collisions est
utilisé. Le temps d’aller retour (tranche canal ou slot time) est de 51,2 microseconde. Une fois le canal
est libre une station doit attendre 9,6 microsecondes avant d’entamer l’émission d’une trame, ce temps
est négligé. La durée nécessaire pour détecter une collision est aussi négligée.
Le temps de détection de collision est égal à 1 slot (51.2 microseconde).
A l'instant t = 0 la station A acquiert la voie et commence à transmettre un message. A l'instant t = 3,
les stations B, C, et D décident de transmettre chacune un seul message. Puis, pendant toute la durée
considérée dans l'exercice aucune autre demande de transmission n'est soumise aux stations. Tous ces
messages sont de taille fixe et la durée de leur transmission est égale à 4 slots.
Dans l'exemple on considèrera que la fonction de tirage aléatoire rend successivement pour chaque
station les valeurs données par le tableau suivant :
B C D
1er tirage 1 0 0
2ème tirage 3 0 2
3 ème tirage 2 6 5
1- Compléter le diagramme suivant en indiquant pour chaque slot l'état de la voie. Un slot occupé par
la transmission d'un message correctement émis par la station A est représenté par "A". Un slot
occupé par une collision est représenté par "X". Un slot correspondant à une absence de
transmission est représenté par "—".
2- Calculer le taux d'utilisation de la voie sur la période allant de t = 0 à la fin de la transmission du
dernier message.
Exercice 3 :
1) Supposez que vous construisez un réseau CSMA/CD fonctionnant à 1 Gb/s sur un câble de 1 km de
longueur sans répéteur. La vitesse de propagation sur ce câble est de 200.000 km/s. Quelle doit
être la taille minimale des trames sur ce réseau ? Expliquez.
2) Est ce que la méthode d´accès CSMA/CD est déterministe ? Expliquez.
3) Quel problème peut surgir si la méthode d´accès CSMA/CD est utilisée par un réseau générant des
trames de courtes tailles ? Expliquez.
4) Après avoir détecté une collision, une station émettrice doit attendre un délai aléatoire avant de
retransmettre la trame. Le délai aléatoire est calculé selon la méthode BEB « Binary Exponential
Backoff ». Supposons qu’une trame subisse 15 collisions consécutives et qu'elle soit transmise avec
succès lors de la 16 ème tentative. Combien de temps, dans le pire cas, la station a-t-elle dû attendre
2
à cause des retards qu'impose la méthode BEB ?
Rappel: la durée d'une tranche canal (fenêtre de collision) est de 51.2 µs.
3
Etablissement : UVT Module : Fondement des réseaux
Enseignant : Sahbi Bahroun Classe : 1 N2TR
Correction TD : Méthode d’accès CSMA/CD
Exercice 1:
Soient A et B deux stations accrochées à un réseau Ethernet, et distantes de 1000m. Dans ce
réseau Ethernet, on transmet des trames de 512 bits sur une ligne de débit 10Mbits/s. La
vitesse de propagation dans le câble est de Vp=220 000 km/s. La station A veut émettre une
trame. Elle « écoute » le canal : il est libre. Elle transmet. La station B a aussi des trames à
transmettre.
1- Quel est le délai pendant lequel il y a risque de collision entre les trames émises par A et
les trames émises par B ?
C’est le temps pendant lequel les premiers bits envoyés par A n’ont pas encore atteint
B. C’est le temps de propagation
tp=distance/Vitesse de propagation =1000/220 000 000 = 4.54 10-6 s= 4,54µs entre A
et B car dans le pire des cas, A peut commencer à envoyer une trame à t=t1 et B peut
envoyer aussi juste avant la réception du signal de A ; soit pratiquement à t=t1+tp
Ainsi le risque de collision est pendant les 4,54 premiers µs de la transmission de A.
2- Si la station B décide d'émettre 2,46 µs plus tard que la station A, quand la station A
détectera-t-elle la collision ? Combien de bits aura-t-elle transmis ?
La collision se produira à mi-temps entre B et A+2,46µs
Le temps de la collision par rapport à B =(4,54-2,46)/2=1,04µs
Le temps de la collision par rapport à A=[(4,54-2,46)/2]+2,46=3,5µs
Pour détecter la collision, il faut que la collision se produise et que la collision se propage à
la vitesse de propagation et arrive au niveau de la station A.
A détecte la collision à t=3,5*2=7µs (2=temps aller retour)
Le nombre de bit transmis =débit*temps de transmission=10 * 106 *7 *10-6 =70 bits
A détecte la collision à t=2.46+tp=7µs
Elle aura transmis 10 * 106 *7=70 bits
Debit = nbredebits/temps temps = nbredebits/Debit
Temps de propagation = distance/vitesse
3- Considérer deux stations A et B distantes de 14km. Ces deux stations émettent exactement
en même temps une trame de 512 bits. Quelles seront les conséquences ?
Le temps d’injection (temps d’émission de la trame) est la durée pendant laquelle la
station A émets ses bits sur le canal
On a temps d’injection= 512/10 * 106 = 51,2µs
et tp= 14/220000=63,63µs. Donc, il y aura une collision mais puisque les stations
ont déjà terminé leurs envois, elles ne vont pas détecter qu’elles sont à l’origine de cette
collision. Donc pas de renvoi de la trame détruite par la collision.
Temps émission<temps de propagation les deux machines ne vont pas se rendre
compte qu’il y a une collision. Donc pas de renvoi de la trame
Principe du CSMA/CD Temps émission>=2*temps de propagation
Dans ce cas principe du CSMA/CD n’a pas été respecté
4- Les deux stations A et B sont maintenant éloignées d'une distance L à déterminer.
Examiner le cas où la station B émet juste avant que les bits émis par la station A ne lui
parvienne. Quelle est la distance L maximale admissible pour que la collision soit détectée
par les machines (donc pour qu'il n'y ait pas de perte de données).
4
Pour que les stations détectent la collision, il faut que tinj>=2*tp. Selon le cas décrit
(qui est le pire cas), au minimum tinj=2*tp
Comme tp=L/Vp
On a donc tinj=taille/debit
tinj=2*tp taille/debit=2*Lmax/Vp Lmax=(taille/debit)*Vp/2
Ainsi Lmax=tinj*Vp/2
AN : Lmax=(51,2 10-6 )*220 000 000/2 = 5632m
5- Quelle longueur minimale doivent posséder les trames émises par chacune des
machines pour qu'il soit impossible de ne pas se rendre compte d'une collision (relation
entre le temps d'émission et le temps de propagation)?
D’après la formule tinj>=2*L/Vp
Comme tinj=taille/débit
taillemin/debit=2*L/Vp
Ainsi taille/débit>=2*L/Vp
taille>=2*L*débit/Vp
Pour une taille minimale, l’inégalité devient une égalité taillemin=2*Lmax*débit/Vp
AN : taillemin=2*5632*10 106 /220 000 000=512bit=64octet
Exercice 2:
On considère un réseau local IEEE 802.3. L’algorithme BEB pour la résolution des collisions
est utilisé. Le temps d’aller retour (tranche canal ou slot time) est de 51,2 microseconde. Une
fois le canal est libre une station doit attendre 9,6 microsecondes avant d’entamer l’émission
d’une trame, ce temps est négligé. La durée nécessaire pour détecter une collision est aussi
négligée.
Le temps de détection de collision est égal à 1 slot (51.2 microseconde).
A l'instant t = 0 la station A acquiert la voie et commence à transmettre un message. A
l'instant t = 3, les stations B, C, et D décident de transmettre chacune un seul message. Puis,
pendant toute la durée considérée dans l'exercice aucune autre demande de transmission n'est
soumise aux stations. Tous ces messages sont de taille fixe et la durée de leur transmission est
égale à 4 slots.
Dans l'exemple on considèrera que la fonction de tirage aléatoire rend successivement pour
chaque station les valeurs données par le tableau suivant :
B C D
1er tirage 1 0 0
2ème tirage 3 0 2
3 ème tirage 2 6 5
3- Compléter le diagramme suivant en indiquant pour chaque slot l'état de la voie. Un slot
occupé par la transmission d'un message correctement émis par la station A est représenté
par "A". Un slot occupé par une collision est représenté par "X". Un slot correspondant à
une absence de transmission est représenté par "—".
A A A A X(B,C,D) X(C,D) X(B,C _ D D D D B B B B
C C C C
A t=0 A commence à emettre pendant 4 slots
At=3 B, C et D veulent emettre, elles ecoutent le canal, il est occupé, les 3 stations doivent
attendre la fin de la transmission de A
A t=4 B, C et D détectent le silence, chacune émet de son coté, elles vont causer une
collision X
5
En appliquant l’algorithme BEB, et d’après le tableau,
B va attendre un slot avant d’essayer de retransmettre
A t=5 : C et D vont attendre 0 slots, elles réémettent tout de suite, elles vont causer une 2
eme collision X
D va attendre 2 slots avant de réécouter le canal pour retransmettre
C va attendre 0 slot et retransmet au slot suivant
A t=6 C retransmet et B a terminé son attente, elle retransmet aussiCollision
B est à son 2eme tirage et attend 2 slots
C est à son 3eme tirage et attend 6 slots
A t=7 aucune station ne transmet, les 3 stations n’ont pas encore écoulé leurs temps BEB
A t=8 D transmet pendant 4 slots, alors que les 2 autres stations sont encore en attente
A t=12 B transmet pendant 4 slots, C’est encore en attente
A t=16 C transmet pendant 4 slots
4- Calculer le taux d'utilisation de la voie sur la période allant de t = 0 à la fin de la
transmission du dernier message.
Taux d’utilisation=temps théorique/temps total = 4trames*4slots/20slots=80%
Exercice 5 :
1) Supposez que vous construisez un réseau CSMA/CD fonctionnant à 1 Gb/s sur un câble de
1 km de longueur sans répéteur. La vitesse de propagation sur ce câble est de 200.000
km/s. Quelle doit être la taille minimale des trames sur ce réseau ? Expliquez.
Il faut pouvoir détecter les collisions : temps injection>=2 temps de propagation
Taille/débit>=2 distance/vitesse A.N : taille>= 2* 1000*109/2*108
2) Est ce que la méthode d´accès CSMA/CD est déterministe ? Expliquez.
Non. Un nœud peut ne pas envoyer sa trame (après 16 collisions, il abandonne).
3) Quel problème peut surgir si la méthode d´accès CSMA/CD est utilisée par un réseau
générant des trames de courtes tailles ? Expliquez.
6
Collisions non détectées
4) Après avoir détecté une collision, une station émettrice doit attendre un délai aléatoire
avant de retransmettre la trame. Le délai aléatoire est calculé selon la méthode BEB «
Binary Exponential Backoff ». Supposons qu’une trame subisse 15 collisions consécutives
et qu'elle soit transmise avec succès lors de la 16 ème tentative. Combien de temps, dans le
pire cas, la station a-t-elle dû attendre à cause des retards qu'impose la méthode BEB ?
Rappel: la durée d'une tranche canal (fenêtre de collision) est de 51.2 µs.
Intervalle de tirage : [| 0..2min(n,10)[| dans le pire cas, la station retire la plus grande valeur
pour chaque tirage temps pire cas =
(1+3+7+15+31+63+127+255+511+1023+1023+1023+1023+1023+1023)*51,2 µs.
