R seaux Mobiles
Chap4: Techniques dacc s multiple dans le wi
Rhouma Rhouma
https://sites.google.com/site/rhoouma
cole Sup rieure d conomie lectronique
2eme ann e Master Pro MBDS
1 / 52
Plan
1 Architecture wi
2 CSMA/CA
3 DCF : CSMA/CA
4 CSMA/CA avec RTS/CTS
5 Exercices dapplications
2 / 52
Plan
Architecture wi
1 Architecture wi
2 CSMA/CA
3 DCF : CSMA/CA
4 CSMA/CA avec RTS/CTS
5 Exercices dapplications
3 / 52
Mode infrastructure
Architecture wi
4 / 52
Mode Ad hoc
Architecture wi
chaque machine peut changer des informations avec nimporte
quelle autre machine sans AP.
Chaque noeud du r seau peut servir de routeur lorsque deux
machines ne peuvent se joindre directement
5 / 52
autre exemple Ad hoc : Bluetooth
Architecture wi
ds Blutooth : reseau = piconet
celui qui initie la communication est le maitre. l autre objet
communiquant = esclave
g a : liaison point point avec un maitre et un esclave
g b : plusieurs mobiles (8 au max) constitue un piconet dans lequel le
maitre communique avec un esclave
g c : si plusieurs piconets se trouvent ds la meme zones, ils peuvent
tre interconnect s pour former un scatternet (10 piconets au max)
6 / 52
Bande occup e par wi
Architecture wi
En 1985 les autorit s de r gulation ont autoris lutilisation de la bande des
2,4 GHz (ISM) pour des applications avec un acc s libre sans licence,
condition que les dispositifs mis en oeuvre respectent les exigences
suivantes :
puissance d mission limit e, la limite tant plus basse en ext rieur
insensibilit aux perturbations par lutilisation dune technique
d talement de spectre
7 / 52
Bande occup e par wi : ce qui se passe reelement
Architecture wi
ex : dans la France
Wi : seuls 4 canaux sur 13 sont disponibles, pas dautorisation
n cessaire pour une utilisation en indoor si la puissance reste inf rieure
100 mW
Bluetooth : 79 canaux, pas dautorisation n cessaire pour une utilisation
en indoor si P < 10 mW, et en outdoor avec P < 4mW
8 / 52
Plan
CSMA/CA
1 Architecture wi
2 CSMA/CA
3 DCF : CSMA/CA
4 CSMA/CA avec RTS/CTS
5 Exercices dapplications
9 / 52
Techniques dacc s en wi
CSMA/CA
De nombreux clients tentent dacc der un seul canal de mani re
non coordonn e.
Toute transmission de toute station peut tre entendu par les
autres stations
Si deux ou plusieurs stations mettent en m me temps, une
collision se produit
diff entre erreurs r guli res et collisions :
Les erreurs de transmissions affectent seulement une seule station
les collision affectent plus quune station
Les retransmission peuvent re-entrer en collision de nouveau
M me si le premier bit dune trame entre en collision avec le dernier
bit dune trame, alors les deux trames sont d truites
10 / 52
La couche MAC IEEE802.11
CSMA/CA
Deux modes sont d nis :
1 DCF(Fonction de Coordination Distribu e). Bas e sur CSMA avec
deux extensions :
CSMA/CA : Carrier Sense Multiple Access / Collision Avoidance
R servation du canal avec RTS/CTS
= Collisions possibles (en DCF)
= Appropri e la transmission de donn es (sans QoS)
= Utilisable en modes ad-hoc et en mode infrastructure.
2 PCF(Point Coordination Function / Fonction de Coordination
Centralis e)
Bas e sur linterrogation p riodique des stations par lAP
Sans collisions
Appropri e au services temps r el
Publicité
Utilisable seulement en mode infrastructure
Donc :
= Mode ad-hoc : Uniquement DCF
= Mode Infrastructure : peut utiliser DCF et PCF
11 / 52
Plan
DCF : CSMA/CA
1 Architecture wi
2 CSMA/CA
3 DCF : CSMA/CA
4 CSMA/CA avec RTS/CTS
5 Exercices dapplications
12 / 52
CSMA/CA
DCF : CSMA/CA
Une station voulant transmettre coute le support, et sil est
occup , la transmission est diff r e
Si le support est libre pour un temps sp cique (appel
Distributed Inter Frame Space : DIFS), alors la station est
autoris e transmettre
Pour r duire la probabilit davoir deux stations entrant en collision
car ne pouvant pas sentendre lune lautre, le standard d nit :
le m canisme de Virtual Carrier Sense (sensation virtuelle de
porteuse) via lindicateur NAV (Network Allocation Vector)
et un m canisme de contention.
13 / 52
Espaces temps d ni par Wi-Fi
DCF : CSMA/CA
Le standard d nit 4 types despace en entre deux trames, utilis s pour leurs
diff rentes propri t s :
le SIFS (Short Inter Frame Space) de 28 s est utilis pour s parer les
transmissions appartenant a un m me dialogue (par exemple Fragment-ACK).
Cest le plus petit cart entre deux trames et il y a au plus une seule station
autoris e a transmettre apr s cet intervalle
le PIFS (Point Coordination IFS) de 78 s est utilise par le Point dacc s pour
obtenir lacc s au support avant nimporte quelle autre station
le DIFS (Distributed IFS) de 128 s est lintervalle utilise par une station voulant
commencer une nouvelle transmission
le EIFS (Extended IFS) est lintervalle le plus long utilis par une station recevant
un paquet quelle ne comprend pas. Ceci permet d viter que la station qui ne
comprend pas linformation de dur e ne provoque de collision avec un futur
paquet
14 / 52
M canisme de Contention
DCF : CSMA/CA
A la n de la transmission dun paquet de donn es, le support
redevient libre, et il est possible que deux stations d marrent un
change simultan ment. = La norme IEEE802.11 a mis en
place une temporisation al atoire appel e contention ou backoff.
chaque station choisit un nombre al atoire entre 0 et N et attend
ce nombre de slots avant dacc der au support.
le back off est exponentiel, cest- -dire qu chaque fois quune
station entre en collision, le temps dattente augmente
exponentiellement.
lalgorithme de backoff exponentiel est ex cut quand une station
veut mettre et que le support est occup ou apr s chaque
transmission ou retransmission r ussie
ce m canisme nest pas utilis quand la station d cide de
transmettre un nouveau paquet et que le support a t libre pour
un temps sup rieur au DIFS.
la d tection de collision est d tect par non-r ception dACK.
15 / 52
fen tre de contention : CW (Contention Window
DCF : CSMA/CA
TBackoff = Rand[0, CW ] Ts avec CW = 2k 1
CW : double apr s chaque collision.
dans 802.11a et g : CWmin = 15, CWmax = 1023 ;
dans 802.11b : CWmin = 31, CWmax = 1023
Ts : Time slot. Varie de norme en norme : Dans 802.11a : 9 s /
802.11b : 20 s / 802.11g : 10 s
16 / 52
exemple de transmission en DCF
DCF : CSMA/CA
17 / 52
exemple de DCF avec CSMA/CA pur
DCF : CSMA/CA
18 / 52
D bit effectif
DCF : CSMA/CA
Le d bit effectif dune transmission est inf rieur au d bit de la
couche physique (11 Mb/s ou 54 Mb/s) cause des en-t tes des
trames et des d lais dattente lors des transmissions (DIFS,
Backoff, acquittements).
D bits effectifs pour un datagramme IP
19 / 52
Plan
CSMA/CA avec RTS/CTS
1 Architecture wi
2 CSMA/CA
3 DCF : CSMA/CA
4 CSMA/CA avec RTS/CTS
5 Exercices dapplications
20 / 52
Faiblesses de CSMA/CA
CSMA/CA avec RTS/CTS
risque que le temps de backoff soit le meme pour deux stations
Probl me de station cach
21 / 52
CSMA/CA avec RTS/CTS
22 / 52
Publicité
CSMA/CA avec RTS/CTS
23 / 52
exemple CTS/RTS avec CSMA/CA
CSMA/CA avec RTS/CTS
Echange RTS/ CTS (Request To Send/Clear To Send) pour une
trame donn es.
Envoi de RTS avec dur e de r servation
Acquis via CTS apr s SIFS (avec dur e de r servation)
Utilisation des silences courts SIFS (l change est prioritaire)
Acquittement positif ACK obligatoire.
M canisme d coute virtuelle (indicateur NAV (Network Allocation
Vector)) pour une autre station) :
Les autres stations connaissent la dur e distribu e via RTS and
CTS
24 / 52
CSMA/CA + RTS/CTS
CSMA/CA avec RTS/CTS
une station voulant mettre transmet dabord un paquet de
contr le court (risque de collision faible) appel RTS (Request To
Send), qui donnera la source, la destination, et la dur e de la
transaction
la station destination r pond (si le support est libre) avec un
paquet de contr le de r ponse appel CTS (Clear To Send), qui
inclura les m mes informations sur la dur e
apr s r ception de CTS, la station peut transmettre ses donn es,
dont la bonne r ception est conrm e par un paquet ACK
(Acknowledge)
les diff rents noeuds mettent alors en oeuvre un m canisme de
contention (retard de dur e al atoire) lissue duquel le noeud au
retard le plus faible peut envoyer ses donn es
Ce m canisme de contention permet au point dacc s de distribuer
des priorit s aux diff rentes stations du r seau.
25 / 52
CSMA/CA + RTS/CTS
CSMA/CA avec RTS/CTS
26 / 52
trames sp ciaux de WiFi
CSMA/CA avec RTS/CTS
27 / 52
Les stations cach es
CSMA/CA avec RTS/CTS
dans un r seau radio, la port e limit e des interfaces pose le
probl me des stations cach es accessibles par certaines interfaces et
inaccessibles dautres.
28 / 52
Les stations cach es
CSMA/CA avec RTS/CTS
Dans lexemple, la station n 3 est une station cach e pour la n 1.
Pour viter les collisions, la technique utilis e est la suivante :
la station n 1 voulant mettre transmet le paquet court de contr le
RTS, qui donnera la source, la destination, et la dur e de la
transaction.
la station n 2 r pond (si le support est libre) avec un paquet de
contr le de r ponse CTS qui inclura les m mes informations sur
la dur e
toutes les stations recevant soit le RTS ou le CTS et en particulier
la n 3 sauront ainsi que le support radio est occup et arr teront
d mettre pendant la dur e indiqu e dans le paquet RTS
Gr ce au fait que le RTS et le CTS sont des trames courtes, le
nombre de collisions est r duit.
29 / 52
Exemple d changes
CSMA/CA avec RTS/CTS
30 / 52
Brouillage
CSMA/CA avec RTS/CTS
les brouillages (four micro ondes par exemple) emp chant la bonne
r ception dun paquet de donn es sont g r s par le protocole MAC de
la fa on suivante :
la station mettrice sait que la transmission ne sest pas bien
effectu e si elle ne re oit pas de paquet ACK
elle renvoie alors le m me paquet, apr s un temps de contention
al atoire
ce m canisme se reproduit jusqu la r ception dun ACK, qui
valide la transmission et permet lenvoi du paquet suivante
31 / 52
Fragmentation des paquets
CSMA/CA avec RTS/CTS
pour viter de ralentir la transmission par la perte de longs paquets,
ceux-ci sont divis s en paquets plus courts, qui ont une meilleure
probabilit d tre transmis par radio sans pertes.
32 / 52
exemple
CSMA/CA avec RTS/CTS
33 / 52
Plan
Exercices dapplications
1 Architecture wi
2 CSMA/CA
3 DCF : CSMA/CA
4 CSMA/CA avec RTS/CTS
5 Exercices dapplications
34 / 52
Exercice 1 : R servation ou non ?
Exercices dapplications
Une station A envoie a 1 Mbps un ux de trames contenant chacune
1500 octets de donn es utiles a une station B. On donne :
la p riode de contention (Backoff) est en moyenne de 20 s ;
temps de propagation n gligeable
linformation pure de 1500 octects contient aussi les donn es
Publicité
dentete et CRC de taille 34 octects
trame CTS et ACK ont une taille de 14 octects
trame RTS a une taille de 20 octects
dans chaque trame MAC (donn e ou RTS ou CTS ou ACK), des
donn es de synchronisation de 24 octects sont aussi envoy s
35 / 52
On demande :
Exercices dapplications
1 dessiner un sch ma montrant les phases denvoie de donn es o on utilise la technique
RTS/CTS en tenant compte du backoff, espaces inter-frames (DIFS, SIFS,..)
2 calculer donc le temps n cessaire pour transmettre une trame sans collision
3
faire de m me dans le cas sans RTS/CTS
4 calculer donc le temps n cessaire pour transmettre une trame sans collision
5 calculer aussi le d bit effectif pour chaque cas.
6 d terminer donc lefcacit du canal avec et sans le m canisme RTS/CTS. On estime
quaucune trame nest perdue. Quel est la solution la plus efcace cot d bit et efcacit si
la probabilit de collision est minimale.
Lorsque le m canisme RTS/CTS nagit pas, seulement les trames de donn es peuvent
tre perdues ; lorsquil agit, seules les trames RTS peuvent tre corrompues. Il faut 20 s
pour d tecter labsence dune trame (CTS ou ACK), apr s quoi un d lai de DIFS est
introduit. On supposera p2 n gligeable.
7 simuler maintenant le cas de collision dans CSMA/CA + RTS/CTS
8 calculer donc le temps de de mauvaise transmission quon va appeler TRTS
9 simuler le cas de de collision dans CSMA/CA sans RTS/CTS
10 calculer donc le temps de de mauvaise transmission quon va appeler Tdata
11 Calculer donc le temps de retransmission probabilistique pour les deux cas.
12 si la probabilit de collision p= 0.2, quel sera le d bit effectif ?
13 d duire la probabilit de perte de trame p a partir de laquelle le m canisme RTS/CTS est
avantageux.
36 / 52
Solution exercice 1
Exercices dapplications
Transmission dun paquet CSMA/CA+RTS/CTS
TDIFS = 128 s ; TSIFS = 28 s ; TBO = 20 s
TrRTS = 192 s + 20 8/106s = 352 s
TrACK = TrCTS = 192 s + 14 8/106s = 304 s
TrData = 192 s + (1500 + 34) 8/106s = 12, 464 ms
Temps de transmission CSMA/CA + RTS/CST est :
T = TDIFS + 3 TSIFS + TBO + TrRTS + TrCTS + TrData + TrACK = 13558 s
37 / 52
Question 3 et 4
Exercices dapplications
Transmission dun paquet CSMA/CA pur
Temps de transmission CSMA/CA pur est :
T = TDIFS + TSIFS + TBO + TrData + TrACK = 12846 s
38 / 52
Question 5 et 6
Exercices dapplications
D bit effectif = quantit dinformation utile / Temps de transmission
CSMA/CA + RTS/CTS :
Deff = (1500 8)/(13558 s) = 885 Kbps
CSMA/CA pur :
Deff = (1500 8)/(12846 s) = 934 Kbps
Efcacit = (d bit effectif / d bit brut) 100%
CSMA/CA + RTS/CTS : Efcacit = 885 Kbps/1 Mbps = 88.5 %
CSMA/CA + RTS/CTS : Efcacit = 934 Kbps/1 Mbps = 93.4 %
On conclut que le lien wi est mieux utilis en CSMA/CA pur quen
CSMA/CA+RTS/CTS dans les situations normales (peu de collision).
39 / 52
Question 7 et 8
Exercices dapplications
Mauvaise transmission dun RTS :
TRTS = TDIFS + TBO + TrRTS + TSIFS + 20 s = 548 s
40 / 52
Question 9 et 10
Exercices dapplications
Mauvaise transmission dune donn e :
Tdata = TDIFS + TBO + Trdata + TSIFS + 20 s = 12660 s
41 / 52
Question 11
Exercices dapplications
temps de retransmission dun paquet avec RTS/CTS
Soit p la probabilit de collision
CSMA/CA avec RTS/CTS :
T = (1 p) 13558 (pas de retransmission)
+(1 p) p(TRTS + 13558) (1 retransmission)
+(1 p) p2(2 TRTS + 13558) (2 retransmission)
+(1 p) p3(3 TRTS + 13558) (3 retransmission)
...
puisque p2 est negligeable et de meme pn, on a :
T = 13558 + 548 p
42 / 52
Question 11
Exercices dapplications
temps de retransmission dun paquet sans RTS/CTS
CSMA/CA sans RTS/CTS :
T (cid:48) = (1 p) 12846 (pas de retransmission)
+(1 p) p(Tdata + 12846) (1 retransmission)
+(1 p) p2(2 Tdata + 12846) (2 retransmission)
+(1 p) p3(3 Tdata + 12846) (3 retransmission)
...
puisque p2 est n gligeable et de meme pn, on a :
T (cid:48) = 12846 + 12660 p
43 / 52
Question 12
Exercices dapplications
probabilit de collision p =0.2
CSMA/CA + RTS/CTS : T = 13558 + 548 p = 13667.6 s
D bit effectif :
Publicité
Deff = (1500 8)/(13667.6 s) = 878 Kbps < 885 Kbps
uniquement chute de d bit de 0.7%
CSMA/CA pur : T (cid:48) = 12846 + 12660 p = 14112 s
D bit effectif :
Deff = (1500 8)/(14112 s) = 850 Kbps (cid:28) 934 Kbps norme
chute de d bit de 9%
44 / 52
Question 13
Exercices dapplications
T = T (cid:48) ssi pcollision = 0.059 (cid:39) 0.06%
La courbe CSMA/CA pur est meilleur que CSMA/CA+RTS/CTS si p est
faible.
Mais d s que p soit sup rieur pcollision, le temps CSMA/CA pur
augmente exponentiellement par rapport CSMA/CA+RTS/CTS.
Si p > pcollision il faut donc utiliser la solution CSMA/CA+RTS/CTS
45 / 52
Exercice 2
Exercices dapplications
Soit un r seau WiFi de d bit 54 Mbps comportant 5 stations A, B, C, D
et E. Appliquez la m thode dacc s du WiFi et repr sentez lordre
dacc s par un sch ma en sachant que :
Chaque station envoie une seule trame (toutes les trames durent
6 slots et tiennent compte implicitement des trames RTS et CTS
et ACK)
Lespace inter-trames dure 1 slot
Les stations d cident d mettre aux instants en s :
A t = 0 ; B t = 2 ; C t = 4 ; D t = 1 et E t = 13.
Pour simplier, le backoff des stations sera comme suit pour
chaque station : tA = [0, 3, 7, 2] ; tB = [6, 7, 5, 1] ; tC = [2, 4, 6, 1]
slots ; tD= [4, 2, 5, 1] slots et tE = [4, 2, 1, 0] slots
on suppose quun slot dure 200 s, et que la trame contient 2000
octets ( a inclut les donn e pures+trames
RTS+CTS+Ack+synchro). Calculer le d bit effectif pour chaque
station.
46 / 52
Exercices dapplications
47 / 52
Solution
Exercices dapplications
Une station avant d mettre sassure que le canal est libre en l coutant et quaucune
station cach e nest en train d mettre (gr ce au NAV Network Allocation Vector).
Si ces conditions sont r unies elle met, sinon elle tire au hasard un temps dattente et ne
pourra mettre qu lexpiration de ce temps. Ce temps dattente repr sente le temps
pendant lequel la station doit constater que le canal est libre avant d mettre si durant
cette attente une autre station prend la main et met lattente est interrompue et reprise
la n de cette mission.
Enn, apr s chaque mission il y a un temps dattente inter-trame respect par toutes les
stations et appel DIFS.
48 / 52
calcul de d bits
Exercices dapplications
DA =
DB =
DC =
DD =
DE =
2000 8
= 13.3 Mbps
2000 8
200 6 1060
(6 5+4+(2+2+2+1)2) 200 106 = 2 Mbps
(6 2+1+24) 200 106 = 7.27 Mbps
(6 3+2+(2+2)1) 200 106 = 3.47 Mbps
(6 4+3+(2+2+2)13) 200 106 = 4 Mbps
2000 8
2000 8
2000 8
On voit bien la diff rence entre le d bit th orique de 54 Mbps et les
d bits r els des stations. il y a aussi des diff rences entre les d bits
r els de chaque station par rapport aux autres stations.
49 / 52
Exercice 3
Exercices dapplications
Si on veut d ployer le WIFI au sein dun campus pour quil couvre tout
le campus.
Expliquer les tapes ainsi que les pr cautions que vous devez
suivre.
Quels sont les canaux a utiliser ?
Faites un sch ma des zones de recouvrement. Rappelons quil y
a 13 canaux disponibles et que la fr quence centrale dun canal
"i" est loign e de 5 MHz (dans les deux sens) des deux canaux
voisins (c-a-d, i-1 et i+1). De plus, les canaux doivent etre
espac s de 25 a 30 MHz pour ne pas interferer.
50 / 52
Solution exercice 3
Exercices dapplications
On doit faire attention ce que deux points dacc s utilisant les
m mes canaux naient pas des zones d mission qui se
recoupent ce qui engendrerait des distorsions du signal risquant
de perturber la transmission.
Il est recommand ne pas avoir deux points dacc s utilisant les
m mes canaux proches lun de lautre.
les canaux du wi sont 14 canaux de 22 MHz espac lun lautre
de 5 MHz.
51 / 52
Exercices dapplications
voici une bonne s lection des canaux wi :
voici une mauvaise conguration :
52 / 52