Introduction aux
réseaux
Chapitre V:
Les méthodes d’accès
au canal
ESEN
Université De La Manouba
Contexte
● Les réseaux utilisent des liaisons
– Point-à-point
– Multipoints
● Les liaisons point-à-point :
– un émetteur ← → un récepteur
– Généralement bidirectionnel
– Facile à exploiter : support de transmission dédié
● Les liaisons multipoints :
– Permettent de joindre plusieurs équipement à la fois
– Support de transmission partagé
09/03/15
2
Exemple : Wi-Fi
Supports partagés
09/03/15
3
Problématique : Méthode d’accès
au canal
Supports de
transmission
Ressources
partagées
Forte charge
Rendement
très faible
09/03/15
4
Taxonomies des méthodes
d'accès au canal
Classification 1
accès aléatoire
qui ne nécessite
pas une autorisation
préalable (contention)
accès déterministe
un mécanisme permet de
désigner la station qui peut
émettre (ex. : Round Robin)
09/03/15
5
Taxonomies des méthodes
d'accès au canal
Classification 2
approche centralisée
seul un nœud primaire
attribue des droits d'accès
approche distribuée
les nœuds participent
de la même façon
aux contrôles d'accès
09/03/15
6
Protocoles CSMA
09/03/15
7
CSMA
● CSMA : Carrier Sense Multiple Access → Accès multiple avec écoute de la
porteuse.
● La station écoute le support physique pour déterminer si une autre station
transmet une trame de données (niveau déterminé de tension électrique ou de
lumière).
– Si tel n'est pas le cas (donc s'il n'y a pas eu de signal), elle suppose qu'elle
peut émettre.
● Ceci n'élimine pas la possibilité de collision étant donné le délai de
propagation
● On définit la période de vulnérabilité comme étant le temps de propagation
d'un signal entre les nœuds les plus éloignés
– Durant cette période une carte réseau peut ne pas détecter l'émission d'un
09/03/15
Publicité
signal par un autre nœud.
8
CSMA : cas des petites trames
A
B
C
D
09/03/15
9
CSMA : cas des petites trames
● Dans cet exemple, la station A a émis correctement son message
– C le reçoit correctement
– Par contre, ni D ni B ne le recevront à cause de la collision
● De même pour le message de B
– Il est reçu par D
– mais pas par C ou A
● En agrandissant artificiellement la taille de la trame, pour que la
durée d’émission soit supérieure à deux fois le délais de
propagation, ce phénomène ne peut pas se produire
09/03/15
10
CSMA : cas des petites trames
Durée d’émission = E < 2 x τ
A
B
C
D
Max Durée de propagation = τ
09/03/15
2 x τ
11
CSMA : cas des petites trames
A
B
C
D
Dans cet exemple, la durée minimale d’émission est
supérieur à 2 fois le délais de propagation
09/03/15
12
CSMA : cas des petites trames
● Il faut que TOUTES les stations soient dans le même état
● La durée d’émission doit être d’au moins 2 fois la durée de
propagation du signal
● Si la trame est trop courte, il faut ajouter des bits de
bourrage
● La topologie doit être limitée pour éviter des durées de
propagation qui forcerait à allonger la longueur des trames
09/03/15
13
CSMA
● CSMA non persistant :
– Lorsque le canal est occupé, une carte désirant émettre un message
reprend l'écoute du canal après un temps aléatoire (cette procédure
est réitérée jusqu'à ce que le canal soit libre).
● CSMA persistant :
– Lorsque le canal est occupé, une carter désirant émettre un message
poursuit l'écoute du canal jusqu'à ce qu'il soit libre et émet ensuite son
message.
– Si une collision se produit, les stations attendent un temps aléatoire
avant de retransmettre.
– Par rapport à la méthode précédente, cette méthode réduit les temps
de non-utilisation du support mais augmente la probabilité de collision.
09/03/15
14
CSMA
● CSMA p-persistant :
– Le temps est divisé en intervalles, comme " Aloha
discrétisé ".
– Si une carte veut émettre, il écoute pour savoir si le
réseau est occupé.
– Emme émet avec une probabilité p si le réseau est libre
(sinon il continue à écouté jusqu'à ce qu'il soit libre), et
reporte l’émission à un intervalle suivant avec une
probabilité 1 – p.
– Le processus continue jusqu’à ce que la trame soit émise.
09/03/15
Publicité
15
CSMA
09/03/15
16
CSMA/CD
● C'est la méthode la plus utilisée
– Écoute du canal avant l'émission
– Écoute pendant l'émission pour déterminer s'il y a eu collision
– Le signal émis est comparé au signal sur la ligne
● Si une collision s'est produite
– La carte abandonne l'émission et envoie une séquence de bits, appelée
séquence de brouillage
– Objectif: faire persister la collision et assurer que les autres coupleurs se sont
rendu compte de la collision
● L'émission sera reprise après un temps aléatoire
09/03/15
17
CSMA/CD
09/03/15
18
CSMA/CD
● Contrairement aux méthodes précédentes
l’émetteur s'assure du bon déroulement de
l'émission sans attendre un acquittement
mais par détection ou non, de collision.
● L'avantage est de pouvoir abandonner
l'émission dès qu'une collision est détectée
et de ne pas attendre d’acquittement.
09/03/15
19
Condition de détection de
collision
● L'émetteur devra rester à l'écoute du canal pendant
une période (tranche canal) au minimum égale à deux
fois le temps maximum de propagation d'un signal
entre deux cartes réseaux.
● La durée d'une tranche canal (fenêtre de collision) est
de 51.2 μs.
● Au-delà de cette période, l'émetteur est sure qu'il n'a
pas subi de collision et qu'il n'en subira pas
09/03/15
20
Condition de détection de
collision
t=0
A commence à
émettre
t= RTT/2-ε
B commence à
émettre
B n’a pas encore
reçu le 1er bit de A
Comme A ne peut
détecter une
collision que
pendant qu’il
émet, il faut qu’il
émette encore
lorsque le 1er bit
de B lui parvient
09/03/15
A
A
A
Collision
détectée
B
B
B
21
Collision détectéeCSMA/CD algorithme de
retransmission
● Si l’émission suit directement la collision, elle va se reproduire
systématiquement
● Binary exponential backoff (BEB) : mis en œuvre dans chaque
station
– Après une collision, choisir un temps aléatoire d’attente avant d’essayer à
Publicité
nouveau
● Objectifs
– Empêcher les stations ayant participé à la collision de réessayer au même
moment
– Adapter dynamiquement le temps moyen d’attente au nombre de stations
09/03/15
22
Algorithme du BEB
● Début : n = 0
● Lorsqu’une collision a lieu en essayant d’émettre la trame :
– Comptabiliser la collision : n = n + 1
● Si n < 16, alors :
– Attendre K x (2 τ) secondes, où K est un entier tiré au hasard de
{0, 1, …, min(2n – 1;210 - 1)
– Émission de la trame (retour au pas 1 de l’algorithme CSMA/CD)
● Sinon :
– Informer la couche supérieure de l’échec
● Abandonner (fin)
09/03/15
23
Les réseaux IEEE 802.11
09/03/15
24
CSMA/CA : sans collision
DATA
A
B
ACK
DI
FS
B
O
SI
FS
• SIFS(short inter frame space):10 µs
• Slot Time:20 µs
• DIFS(distributed inter frame space):50 µs
• DIFS=SIFS+ 2 × slot time
• BO: backo variable
ff
• CW is in units of slot time / CWmax:1023
09/03/2015
25
DATAACKCSMA/CA:
procédure du Backoff
● Cwmax
31←
● If ( due to timeout)
– CWmax
CW←
max * 2 // Cwmax = 1023
• Else
– Wait (Channel == IDLE)
– Wait DIFS
– cw
max]
Random[1,CW
←
– While (Channel == IDLE)
←
• cw
cw – 1
• If (cw = 0) Return
09/03/2015
26
CSMA/CA : fenêtre de contention
09/03/2015
27
CSMA/CA : avec collision
BO
DATA
Co
lli
si
on
DATA
SI
Publicité
FS
N
O
A
C
K
SI
FS
N
O
A
C
K
DI
FS
B
O
DI
FS
B
O
A
B
C
DATA
BO
09/03/2015
28
DATADATADATAProblème de la station cachée
(hidden node)
A
B
C
Collision
• A envoie à B
• C envoie à B
• A et C ne « écoutent » pas
• Interférence au niveau de B → Collision
09/03/2015
29
CollisionSolution: RTS/CTS
• Mécanisme de réservation
• Avant de transmettre des données, échanger
RTS/CTS
– RTS: Request to Send
– CTS: Clear to Send
RTS
DATA
DI
FS
B
O
SI
FS
SI
FS
CTS
ACK
A
B
Réservation
09/03/2015
30
DATAACKRTSCTSRéservationVirtual Carrier Sens
• Inclure l’information « durée de la
transmission » dans le RTS/CTS
• Les stations maintiennes un temporisateur
égale à cette durée
– NAV: Network allocation vector
• If NAV > 0 ne pas envoyer des trames même si
le canal est libre
09/03/2015
31
The END
09/03/2015
32