Ingénierie des réseaux

– Trames générées suivent le processus de Poisson

03/10/17

13

Rappel : variable aléatoire

● Une variable aléatoire est une fonction qui

associe un nombre réel x à la réalisation d’un

événement aléatoire

● Ainsi, la taille de la première personne qui

rentrera en classe est une variable aléatoire,

tout comme la durée d’une communication

téléphonique qui s’établit.

03/10/17

14

Rappel : loi de Poisson de

paramètre λ

● Notons ce résultat remarquable : dans le cas

d’une variable obéissant à une loi de Poisson de

paramètre λ , sa moyenne et sa variance sont

égales, et égales à λ .

03/10/17

15

Évaluation d'Aloha

● T: durée de trame

– Temps moyen nécessaire à la transmission d’une trame

(taille moyenne / débit )

● Soit g : le nombre moyen de trames émises par secondes

● Comme l’émission des trames respecte une loi de Poisson.

La probabilité d’émettre k trames pendant une durée T

(notée Pk(T)) :

03/10/17

)(

TP

k



=

k

(

)

gT

!

k

-



gT

e

16

Évaluation d'Aloha

Une trame est brouillé si plusieurs autres stations émettent pendant la

transmission

t-T

t

t+T

Si une trame est émise à l’instant t, pour qu’il y ait succès, il faut qu’il

n’y ait aucune autre transmission pendant la période [t-T, t+T]

c’est-à-dire la probabilité qu’il n’y ait aucune transmission pendant une

période de 2T

03/10/17

17

Évaluation d'Aloha

La probabilité qu’il n’y ait aucune transmission pendant une période de

2T, d’où

P

succes



)2(

TP

0

2

gT



e

t-T

03/10/17

t

t+T

18

Évaluation d'Aloha

● Soit s : le nombre moyen de trame émises correctement.

● Rappelons que g : le nombre moyen de trames moyen

émises par secondes (g>s)

● La probabilité de succès Psucces peut également s'exprimer

par Psucces = s/g

03/10/17

19

Évaluation d'Aloha

● Si nous normalisons les durée on obtient :

– S = s.T : le nombre moyen de trame émise correctement

par durée de trame

– et G = g.T : le nombre moyen de trame émise par durée

de trame

– À l'évidence G > S

● On obtient S/G= e-2G → S = G x Psucces

03/10/17

20

Évaluation d'Aloha

● La relation entre le trafic effectivement

écoulé S et la charge global des stations G

s'exprime par la formule : S= G x e-2G

03/10/17

21

Évaluation d'Aloha

● La relation entre la charge globale des

stations (G) et le trafic effectivement écoulé

(S) :

– Le trafic maximum est obtenu pour G =0.5 avec

S = 1/(2e) = 1.84

– Le mieux que l'on puisse espérer correspond à

une occupation du canal de l'ordre de 18 %

03/10/17

22

Alhoa Slotté ou discrétisé

● Améliorations apportées à l'Aloha:

– On divise le temps en intervalle répétitifs (les slots)

de durée constante = durée de la trame T

– Les utilisateurs doivent synchroniser leurs horloges !

– Les stations doivent attendre le début du prochain

slot avant de pouvoir transmettre

– La période de vulnérabilité est réduite de 2T à T

● S = G x e-G

03/10/17

23

Alhoa Slotté ou discrétisé

03/10/17

24

Protocoles CSMA

03/10/17

25

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

26

03/10/17

signal par un autre nœud.

CSMA : cas des petites trames

A

B

C

D

03/10/17

27

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

03/10/17

28

CSMA : cas des petites trames

Durée d’émission = E < 2 x τ

A

B

C

D

Max Durée de propagation = τ

03/10/17

2 x τ

29

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

03/10/17

30

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

03/10/17

31

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 carte 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.

03/10/17

32

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.

03/10/17

33

CSMA

03/10/17

34

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

03/10/17

35

CSMA/CD

03/10/17

36

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.

03/10/17

37

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

03/10/17

38

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

A

A

A

Collision

détectée

B

B

B

03/10/17

39

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 à

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

03/10/17

40

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)

03/10/17

41

Exercices : Évaluation du BEB

Question I :

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 en moyenne 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

03/10/17

42

Exercices : Évaluation du BEB

● Correction Question I

La moyenne c’est :

0+MAX/2 = 183 µs

03/10/17

43

Exercices : Évaluation du BEB

Question II :

On considère un réseau local de type IEEE 802.3 sur lequel deux

stations A et B ont chacune une unique trame à transmettre. La

retransmission en cas de collision est effectuée selon l'algorithme BEB.

Toutes les autres stations n’ont aucune trame à transmettre. Les deux

stations décident d'envoyer leur trame en même temps ce qui provoque

une première collision. On suppose donc, dans tout l’exercice, que la

première collision a eu lieu avec une probabilité égale à un.

Quelle est la probabilité pour que ces deux stations (A et B)

abandonnent à cause d’un nombre de collisions successives

excessif ?

03/10/17

44

Exercices : Évaluation du BEB

● Correction Question II

½1 ½2 ½3 …. ½10 ½10 ½10 ½10 ½10 * ½10 =

½1+2+3+4+5+6+7+8+9+6*10 = ½105

1ère tentative : {0,1} → 1/21/2 + 1/21/2 = 2/4 = 1/2

2ème tentative : {0,1,2,3} → 1/41/4 + 1/41/4 + 1/41/4 +1/41/4 = 4/16 = 1/4 = 1/2²

3ème tentative : {0,1,2,3,4,5,6,7} → 1/81/8 + 1/81/8 + 1/81/8 + 1/81/8 + 1/81/8 + 1/81/8 +

1/81/8 + 1/81/8 = 8/64 = 1/8 = 1/2³

…..

03/10/17

45

Les réseaux IEEE 802.11

03/10/17

46

CSMA/CA : sans collision

DATA

A

B

ACK

BO

DIF

S

SIF

S

• 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

03/10/2017

47

DATAACKCSMA/CA:

procédure du Backoff

● Cwmax ← 31

● If ( due to timeout)

– CWmax ← CWmax * 2 // Cwmax = 1023

• Else

– Wait (Channel == IDLE)

– Wait DIFS

– cw ← Random[1,CWmax]

– While (Channel == IDLE)

• cw ← cw – 1

• If (cw = 0) Return

03/10/2017

48

CSMA/CA : fenêtre de contention

03/10/2017

49

CSMA/CA : avec collision

DATA

Coll

isio

n

BO

SIF

S

NO

AC

K

SIF

S

NO

AC

K

DATA

DATA

BO

BO

DIF

S

BO

DIF

S

A

B

C

03/10/2017

50

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

03/10/2017

51

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

BO

DIF

S

SIF

S

SIF

S

CTS

ACK

A

B

Réservation

03/10/2017

52

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

03/10/2017

53

Débit réel d'IEEE 802.11

●

Intertrame pour accès distribué (DIFS) = 50µs

● Durée moyenne de backoff (tirage de CW entre 0 et 31 slots) = 15.5*20µs = 310µs

● Durée du paquet de 1500 octet de donnée avec 34 octet d'overhead MAC et 192

de synchronisation physique (192bit envoyés à 1 Mbps)

– à 2Mbps : (1534*8)/2Mbps + 192 = 6328µs

– À 11Mbps (1534*8)/11Mbps + 192 = 1308µs

● SIFS = 10µs

● Ack de 14 octets à 1Mbps + synchronisation physique de 192µs soit 304µs

03/10/2017

54

Débit réel d'IEEE 802.11

Trame partie utile (1500 octets)

6000µs (2Mbps)

1091µs (11Mbps)

DIFS

50 µs

Backoff

310 µs

Trame avec overhead phy et mac

6328 µs (2Mbps)

1308 µs (11Mbps)

SIFS

10 µs

Ack

Phy et mac

304 µs

Durée Utile = 6000µs (2Mbps) / 1091µs (11Mbps)

Durée Totale = 7001µs (2Mbps) / 1937µs (11Mbps

03/10/2017

55

Débit réel d'IEEE 802.11

Débit nominal

Capacité

maximale

Débit maximal

2Mbps

11Mbps

0.85

0.56

1.7Mbps

6.19Mbps

03/10/2017

56

The END

03/10/2017

57