1 cours réseaux chapitre 3 la couche liaison. 2 La couche liaison Objectifs, la détection et la correction d'erreurs, le contrôle de flux, les protocoles

1

cours réseaux chapitre 3

la coucheliaison

2

La couche liaison

Objectifs,la détection et la correction d'erreurs,le contrôle de flux,les protocoles élémentaires,un exemple de protocole : HDLC et les LAP x.

Les réseaux locaux :le contrôle d'accès au canal de transmission,les protocoles de gestion d'accès,les normes des réseaux locaux et métropolitains,les ponts.

3

Constitution d’une liaison de données

ETTD AETCD

ETTD BETCD

support detransmission

circuit de données niveau 1 :RTC, RNIS, lien direct, ...

techniques de transmission

terminal

ouordinateur modem modem

con

trôl

eur

de

com

mu

nic

atio

n

con

trôl

eur

de

com

mu

nic

atio

n

Liaison de données - niveau 2

terminal

ouordinateur

4

La couche liaison du modèle OSI

application

présentation

session

transport

réseau

liaison

physique

7

6

5

4

3

2

1

ISO 8886 & UIT X212

LAP-B CSMA/CD jeton ...

• gestion de la liaison de données• données en trames de données• transmission des trames en séquence• gestion des trames d’acquittement• reconnaissance des frontières de trames reçues

• détection et reprise sur erreur• régulation du trafic• gestion des erreurs

• procédures de transmission

5

La couche liaison des modèles IEEE & OSI

couche LLCcouche MAC

couche physique

2

1

LLC = Logical link protocol- contrôle la qualité de la transmission- assure la liaison de données- offre une interface de service à la couche

3 catégories de service1 - sans connexion et sans accusé de réception2 - sans connexion et avec accusé de réception3 - orienté connexion et avec accusé de réception

MAC = Media access control- contrôle la méthode d’accès au support physique

blocs de données = trames

trains de bits

réseau3

couche réseau3 paquets

6

Protocoles de liaison de données : exemples

BSC Binary synchronous control

SDLC Synchronous data link control (SNA)

HDLC High level data link control

- une normalisation ISO- de nombreuses variantes :

Ethernet IEEE 802.3FDDI IEEE 802.4Token ring IEEE 802.5IsoEthernet IEEE 802.9WLAN sans fil IEEE 802.11Ethernet 100VG IEEE 802.12

7

Protocole de liaison orienté caractère

Données à transmettre (hexadécimal) : 31 03 32 10 4D 10

les mêmes en codage ASCII : 1 ETX 2 DLE M DLE

l’émission des données sans mécanisme de transparence : STX 1 ETX 2 DLE M DLE ETX

l’émission des données avec mécanisme de transparence :DLE STX 1 ETX 2 DLE DLE M DLE DLE DLE ETX

8

Protocole de liaison orienté compteur de caractères

Données à transmettre (hexadécimal) : 41 56 65 7F 03 58 ……..

données émises : 7F 05 41 56 65 7F 03 7F 05 58 ……..

7F : délimiteur de trame ; 05 : nombre de caractères / trame

données reçues : 7F 03 41 56 65 7F 03 7F 05 58 ……..interprétation : 41 56 65 7F 05 58

bruit sur le circuit

9

Protocole de liaison orienté bit

fanion de début = fanion de fin de trame = 01111110

données à transmettre (binaire) : 0110 1111 1100 101

= 1 fanionSi dans la trame, il y a 6 bits à ‘1’ consécutifs :

alors insertion d’un ‘0’ après les 5 premiers ‘1’

d’où la trame réellement émise :01111110 0110 1111 1010 0101 01111110

10

contrôle d’erreur - contrôle de flux

Contrôle d’erreur : stratégies variables• problème inexistant ou non traité• codes correcteurs d’erreur

informations redondantes autosuffisantes• codes détecteurs d’erreur

informations redondantes suffisantesretransmissions

Contrôle de flux : stratégies variables• problème inexistant ou non traité• régulations données à l’émetteur

+ permissions données par le récepteur• tenir compte de la gestion des pertes et des erreurs

11

Principe général de la détection d’erreurs

information à transmettre

algorithmede calcul

comparaisoninformationredondante

trame émise

trame reçue

Calcul à l’émission Vérification à la réception

12

Contrôle d’erreur : détection des erreurs

• contrôle de la parité

• parité paire (even) ou impaire (odd)

• erreur non détectée si un nombre pair de bits sont inversés

• CRC (Cyclic Redundancy Check Codes) : code redondant cyclique

• utilise un code binaire dynamique dépendant des données

• Il peut détecter :

– toutes les erreurs de longueur < au degré du polynôme générateur.

– une partie des salves d’erreurs de longueur égale au degré.

– une partie des salves d’erreurs de longueur > r + 1.

– toutes les combinaisons d’erreurs de poids impair si le polynôme correspond à un mot-code de poids pair.

13

Parité

0 1 1 0 0 1 0 1

Exemple d’un bit de parité impaire :

+ 1

Nombre de bits à 1 = 4

nombre de bits à 1 = 5 / nombre impair

- rendement médiocre- suppose une distribution uniforme des erreurs

14

Code à redondance cyclique : CRC

PDU : packet data unit

SDU CRC

Le SDU est mis sous la forme d’un polynôme M(x) :M(x) = mn xn + .. + m1 x1 + m0

exemple : SDU = 1 1 0 1 0 M(x) = x4 + x3 + xG(x) = polynôme générateur : de degré d

exemple de G(x) : x16 + x12 + x5 + xM(x) = G(x) * Q(x) + R(x) (à réaliser en binaire)R(x) = le reste de la division polynomiale de xd * M(x) par G(x).

CRC = R(x)

à l’émission, le bloc transmis : M’(x) = xd * M(x) - R(x)à la réception : M’(x) est divisé par G(x) :

le reste de la division est nulle s’il n’y a pas d’erreur.

15

Exemple de calcul de CRC

SDU1001 000 101110110010 10 00 10 11 00 110 reste

PDU ou message émis1001 110

G(x) = x3+x+1 d = 3

SDU1011 0001 000 101110110000 1 000

1 011 0 011 reste

PDU ou message émis1011 0001 011

16

Les protocoles d’échange de trames

Les protocoles élémentaires :- 1 : monodirectionnel utopique- 2 : monodirectionnel «envoyer et attendre»- 3 : monodirectionnel sur canal bruité

Les protocoles avec fenêtre d’anticipation :- 1 : de largeur 1 (sans erreur)- 2 : de largeur n (sans erreur)- 3 : avec détection d’erreur, stratégie ‘ Go-back-N ’- 4 : avec détection d’erreur, stratégie ‘ rejet sélectif ’

Exemple : HDLC

17

Les protocoles de contrôle d’erreur

ARQ : Automatic Repeat Request

• communication monodirectionnelle sur canal bruité

• acquittement positif avant retransmission

• détection des erreurs

• accusé de réception : ACK / NACK

• temporisateur, n° de trame

E R

ACK

NACK

18

Protocole «envoyer et attendre »

ARQ : Automatic Repeat RequestE R

attentesans

réémission

PDU-DATA1

PDU-ACK

A-réveil

D-réveilPDU-DATA2

Time-out :A = armerD = désarmerS = sonne

A-réveil

S-réveil PDU-DATA2

attenteavec

réémission

19

Protocoles avec fenêtres d’anticipation (1)

0*

1

234

5

6

7 0

234

5

6

7 0

1

234

5

6

7

0*

1

234

5

6

7 0

1

234

5

6

7

Emetteur

Récepteur

initialementaprès envoi1ère trame

après réception1ère trame

après réception1er acquittement

I0

RR1

1

0

1

234

5

6

7

0

234

5

6

7

1

0

1

234

5

6

7

*Tailles des fenêtres : en émission = 1, en réception = 1

I0 = trame d’information n°0 RR1 = trame d’acquittement n°1 (acquitte les trames I de n° <1)

20

Protocoles avec fenêtres d’anticipation (2)

0

234

5

6

7 0

1

234

5

6

7

0

1

234

5

6

7 0

1

234

5

6

7

Emetteur

Récepteur

I0

RR1

I1 I2

RR2 RR3

1

234

5

6

7 0

0

1

234

5

6

7 0

1

234

5

6

7

0

1

234

5

6

70

1

234

5

6

7


21

Protocole à fenêtre et erreur de transmission : Go-back-N (1)

0

234

5

6

7

0

1

234

5

6

7

Emetteur

Récepteur

I0 I1 I2

REJ0 RR1

1

234

5

6

7 0 0

1

234

5

6

7

I1

0

1

234

5

6

7 0

1

234

5

6

7

I0

0

1

234

5

6

7 0

1

234

5

6

7

I1


REJ0 = trame de rejet n°0 (rejet de toutes les trames I de n° <=0)

22

Protocole à fenêtre et erreur de transmission : Go-back-N (2)

E RPDU-DATA1

PDU-ACK2

PDU-DATA2

PDU-DATA3

délivre DATA1*

ne délivre pas

PDU-ACK2

PDU-DATA4ne délivrepas

PDU-ACK2S (DATA2)A (DATA2)

PDU-DATA2

délivre DATA2

PDU-ACK3D (DATA2)A (DATA3)

PDU-DATA3

PDU-DATA4

délivre DATA3

délivre DATA4

D (DATA3)A (DATA4)

PDU-ACK4

PDU-ACK5

Time-out :A = armerD = désarmerS = sonne

D (DATA1)A (DATA2)

A(DATA1)

D (DATA4)


*le niveau 2 délivre au niveau 3 les données DATA1 encapsulées dans la trame PDU-DATA1

23

Protocole à fenêtre et erreur de transmission : rejet sélectif

0

234

5

6

7

0

1

234

5

6

7

Emetteur

Récepteur

I0 I1 I2

SREJ0 RR3

1

234

5

6

7 0 0

1

234

5

6

7

I3I0

0

1

234

5

6

7

RR00

1

234

5

6

7


SREJ0 = trame de rejet sélectif n°0 (rejet de la seule trame I de n° <=0)

24

Régulation = contrôle de flux

Débit émission ? : ni trop lent, ni trop rapide

Lieu de régulation ? : - de bout en bout : couche transport,- dans la couche liaison

Classes de régulation ? : - boucle ouverte : initiative à la source,- boucle fermée : initiative au puits,- mode hybride.

Fenêtre de contrôle de flux :une fenêtre contient les paquets émis non encore acquittés ; si la fenêtre est pleine, le débit est ralenti ;on mélange les solutions aux problèmes du contrôle d’erreur et du contrôle de flux.

Contrôle de flux par le débit : contrôle direct du débit à la source ; problème : besoin d’horloge très précise, mais pas de couplage contrôle d’erreur / contrôle de flux

25

Contrôle de flux « On/Off »

Emetteur Récepteur

X-OnX-Off

- Le récepteur envoie un signal X-Off lorsque sa file d’attente est pleine.- L’émetteur stoppe son émission s’il reçoit X-Off.- Le récepteur envoie un signal X-On lorsque sa file d’attente n’est plus pleine- L’émetteur reprend sa transmission s’il reçoit X-On

26

Performance «envoyer et attendre »

E R

T-trameDATA

ACK

T-propagation

taux occupation : T-propagation

T-trame

L * DN * V

taux utilisation : T-trame

2T-propagation + T-trame 12 * Alpha + 1L = distance

D = débitN = longueur de trameV = vitesse de propagation

U =

Alpha = (L/V) / (N/D)

Alpha =

U =

T-propagationAlpha =T-trame-(ACK0)

27

Exemples de taux d’utilisation «envoyer et attendre »

• Lien court, débit moyen• distance L = 1 Km

• vitesse de propagation V = 200 000km/s : 1 km en 5 s

• longueur de trame N = 4 000 bits

• débit D = 10 Mbit/s

• T-trame = 4 / 10 000 = 400 s

• Alpha = 5 / 400 = 0.012 / U = 0.98

• Lien long, bas débit• T-propagation = 270 ms

• débit D = 56 Kbit/s / T-trame = 4 / 56 = 71 ms

• Alpha = 270 / 71 = 3.8 / U = 0.12

28

Performances des fenêtres glissantes - N

E R

T-trameDATA

T-propagation

Taux utilisation :

T-trame 2 * T-propagation + T-trame

N2 * Alpha+1

U = N *

U = si U<1, 1 sinon

N = taille de la fenêtre

T-propagationT-trame-ACK(0)

29

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

Tampon émetteur :

Tampon récepteur :

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

trames à transmettre

trames à acquitter

Contrôle de flux à fenêtre glissante (1)

30

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

0,1,2

ACK 3

ACK 7

3,4,5,6

Contrôle de flux à fenêtre glissante (2)

31

High level data link control : HDLC (1)

La famille HDLC– SDLC Synchronous Data Link Control, IBM

– HDLC : ISO

– LAP B, Link Access Procedure Balanced : X.25

– LAP D, LAP canal D RNIS

– LAP F, LAP relais de trames

– LAP M, LAP pour modems : V.42

– LAP X, LAP liaison half duplex télex

– PPP, Point-to-Point Protocol : internet

– LLC, Logical Link Control : IEEE 802.2

32

HDLC (2) : généralités et protocoles

Les modes de communication :

- multipoint- point à point- à l’alternat

Les modes de fonctionnement :- ARM (Asynchronous Response Mode) : 1 maître, 1 (des) esclave(s)- ABM (Asynchronous Balanced Mode) : banalisé (symétrique)

Le service :

- fiable- orienté connexion

Les 3 protocoles :

- l’ouverture de la connexion- la fermeture de la connexion- l’échange de trames d’information et de trames de contrôle

33

HDLC (3) : les formats de trame

fanionadresse contrôle d’erreurDonnées : SDUfanion commande

8 bits8 bits 16 bits0 taille 81448 bits 8 bits

délimiteur de trame / synchronisation0 1 1 1 1 1 1 0

distingue un émetteur/récepteur en multipoint ou la commanded’une réponse en point-à-point

x16+x12+x5+1

34

HDLC (4) : les types de trames

fanionadresse contrôle d’erreurdonnéesfanion commande

8 bits8 bits 16 bits0 taille 81448 bits 8 bits

type sensnom de la trame numérotation

informationsupervisionsupervisionsupervisionsupervisioncommandecommandecommandecommande

envoiréponseréponseréponseréponseenvoienvoi

réponseréponse

I = information - PRR = prêt à recevoir 1 trame I - P/FREJ = rejet de trame I - P/FSREJ = rejet sélectif de trame I - P/FRNR = non prêt à recevoir 1 trame I- P/FSARM/SABM = commande d’ouverture PDISC = commande de fermeture PUA = accusé de réception - FCMDR = trame de rejet de commande - F

oui : N(R), N(S)oui : N(R)oui : N(R)oui : N(R)oui : N(R)

nonnonnonnon

une trame de supervision acquitte les trames I de n° < N(R)bit P/F (poll / final ) = 1 si réponse immédiate attendue

N(R), N(S) :3 bits mode normal,7 bits mode étendu

35

HDLC (5) : paramètres, trames et variables

Les paramètres du protocole :

- le délai de garde (temporisation de retransmission)ex. : 100 ms à 48 Kbit/s - 1,6 s à 2,4 Kbit/s

- le délai d’acquittement d’une trame- le nombre maximal de ré-émissions (ex. : 3, 10, 20)- la taille d’une trame (ex. : 1064, 2104, 8232)- la valeur du crédit à l’émission = taille de fenêtre (ex. : 1, 7)

Les 3 types de trames :

- information (I) avec 2 numéros : 1 à l’émission N(S), 1 d’acquittement N(R)- supervision (4 ) : avec un numéro d’acquittement N(R)- commande (4 ) : avec un numéro d’acquittement N(R)

Les variables des entités du protocole :

V(S) = n° de la prochaine trame I à émettreV(R) = n° de la prochaine trame à recevoirDN(R) = n° du dernier acquittement reçu ; K = taille de la fenêtre émission

Invariant en émission : DN(R) < V(S) <= DN(R) +KInvariant en réception : si N(S) reçu = V(R) alors Ack (avec taille fenêtre=1)

36

HDLC (6) : exemple n°1

Transmission sans erreur en mode ARM (Asynchronous Response Mode)

SARM, P

UA, F

I0

I1, PRR2, P/F

DISC, PUA, F

station primaire station secondaire

37


Transmission avec erreur en mode ARM

SARM, P

UA, F

I0

I1, P

RR2, P/F

DISC, PUA, F

station primaire station secondaire

perteA (réveil)

S (réveil) I1, P

38

Transmission avec contrôle d’erreur

et de flux en mode ABM

(AsynchronousBalanced Mode)

t

2 réémissions

UA (A, F)SABM (A, P)

I (A, N(R)=2, N(S)=0)I (A, N(R)=2, N(S)=1 , P)

I (A, N(R)=2, N(S)=2 , P)

I (A, N(R)=3, N(S)=3)I (A, N(R)=3, N(S)=4 , P)

REJ (A, N(R)=3)I (A, N(R)=3, N(S)=5 , P)

RR (A, N(R)=5 , P/F)

station primaire B

SABM (B, P)

UA (B, F)I (B, N(R)=0, N(S)=0)I (B, N(R)=0, N(S)=1, P)

RR (B, N(R)=2 , P/F)

I (B, N(R)=3, N(S)=2)

I (B, N(R)=5, N(S)=3)I (B, N(R)=5, N(S)=4 , P)

I (B, N(R)=6, N(S)=3)I (B, N(R)=6, N(S)=4 , P)

station primaire AHDLC (8) : exemple n°3

perdu

39


I (B, N(R) = , N(S) = , P = )

I (B, N(R) = , N(S) = , P = )

I (A, N(R) = , N(S) = , F = )

I (B, N(R) = , N(S) = , P = )

I (B, N(R) = , N(S) = , P = )

I (B, N(R) = , N(S) = , P = )

REJ (A, N(R) = , F = )

I (B, N(R) = , N(S) = , P = )

I (B, N(R) = , N(S) = , P = )

I (A, N(R) = , N(S) = , P = )

I (B, N(R) = , N(S) = , P = )

I (A, N(R) = , N(S) = , F = )

À compléter …

erreur CRC

station primaire B V(R) = 0 ; V(S) = 0station primaire A V(R) = 0 ; V(S) = 0

t

40

Les réseaux locaux de données

- Introduction aux réseaux locaux (RLE, LAN)- Techniques d’allocation des canaux de communication- Techniques et Protocoles de gestion d’accès

Aloha, CSMA, autres protocoles …

- Les normes IEEE des LAN- Les réseaux locaux filaires

(Ethernet, 802.2, 802.3, …)

- Interconnexion des réseaux locaux- Les LAN(s) virtuels

- Les réseaux locaux sans fil - Wireless LAN(802.11, WiFi, HiperLan, …)

- Les réseaux personnels sans fil - Wireless PAN(802.15, Bluetooth, Zig Bee, …)

41

Modèle

Application

Présentation

Session

Transport

Réseau

Liaison

Physique

LLC

MAC

couche physique

unité de raccordement

802 . 2

médium

802 . 3ou...

42

Aloha versus Hawaï

* 1 fréquence partagée* émission-réception radio de données numériques* 1200 bits/s* collisions possibles

N. Abramson, 1970

43

Réseau local : à l’origine, Ethernet

1970 : mise au point dans les

laboratoires du XEROX PARC

1976 : R. Metcalfe & D. Boggs

1980 : XEROX Ethernet V1, spécifications

1982 : Ethernet V2 / DIX Ethernet (DEC+Intel+Xerox)

1985: IEEE 802 Technical Committee, standard 802.3

DIX : - câble coaxial épais 10base5

- Ethernet : « le » réseau local

- normalisation IEEE 802.3

- une méthode d’accès de référence : CSMA / CD

« Accès multiple et écoute de porteuse, avec détection de collision »

44

Ethernet : buts et principes à l’origine (1)

- un service de base, peu d’options, simplicité, faible coût- pas de priorité, chacun peut « parler »- débit : 10 Mbit/s- performances peu dépendantes de la charge

Ce qui n’était pas dans les buts à l’origine :- full duplex, contrôle d’erreur- sécurité, confidentialité, protection contre les malveillants- vitesse variable

Support de transmission :- segment = bus = câble coaxial = support passif- ni boucle, ni sens de circulation- mode diffusion- transmission en bande de base

Raccordement au câble : le « transceiver » : émetteur & récepteur

Tout équipement Ethernet a une adresse unique au monde

45

Modèle OSI et Ethernet à l’origine

couche réseau couche liaison couche physique

LLC MAC

802.2 802.3

carte coupleurEthernet

Câble transceiverbus destation

Câb

le c

oaxi

al

10ba

se5

Drop câbleAttachement Unit Interface - AUI4 à 5 paires torsadéeslongueur max de 50 mprise AUI 15 broches

TransceiverMedium Attachement Unit - MAUcode Manchesterdétection des collisions

46

Principes à l’origine (2)

• sur le câble, circulent des suites d’éléments binaires : des trames

• à un instant donné, une seule trame circule sur le câble- pas de multiplexage en fréquence- pas de full duplex

• une trame émise par un équipement est reçue par tous les transceivers du segment Ethernet

• une trame contient les adresses de l’émetteur et du destinataire :si une trame lui est destinée (@DEST = mon @)

alors il la prend et la délivre à la couche supérieure

sinon, il n’en fait rien.

47

Principes à l’origine (3)

* l’ancêtre : Aloha- tout le mode a le droit d’émettre quand il veut,- beaucoup de collisions.

* les améliorations : CSMA (Carrier Sense Multiple Access).Une station qui veut émettre :- regarde si le câble est libre,- si oui, elle envoie sa trame,- si non, elle attend que le câble soit libre.- encore des collisions, mais moins nombreuses.

* quand 2 stations émettent en même temps, il y a collision :- les trames concernées sont inexploitables- les stations concernées détectent la collision- les stations réémettent leur trame ultérieurement

* Ethernet est un réseau probabiliste, sans station centrale, ni priorité, ni prévention contre une station malveillante.

48

Techniques d’allocation des canaux de communication

Allocation statique : multiplexage en fréquence ?multiplexage temporel synchrone ?

Allocation dynamique :- modèle de station :

N stations indépendantespas de nouvelle émission si la précédente n’est pas réussie

- présomption de canal unique :toute station peut émettre

- présomption de collision (optimiste) :émission + détection de collision + réémission

- modalité de transmission :n’importe quand ou slot de temps

- utilisation de la porteuse :détection de porteuse ou pas d’écoute préalable

non adapté

49

Protocoles de gestion d’accès

Protocoles ALOHA : 2 versions- ALOHA pur- ALOHA discrétisé

Protocoles CSMA : diverses versions- CSMA 1-persistant (CSMA / CD Collision Detection)- CSMA non persistant- CSMA p-persistant

Autres protocoles :- sans collision- à contention limitée (CSMA / CA Collision Avoidance)- multiplexage en longueur d’onde- (sans fil)- (radio-cellulaire numérique)

50

Le protocole Aloha pur (1)

Durée de trame = temps moyen nécessaire à la transmission d’une trame standard de taille fixeS = nombre moyen de trames générées par durée de trameGénération de nouvelles trames : distribution de Poisson, nombre d’utilisateurs

si S > 1 : problème ; si 0 < S < 1 : réaliste, satisfaisantk = nombre de tentatives de transmission de trames (les nouvelles et les anciennes) par durée de trame : distribution de Poisson

G = nombre moyen de tentatives de transmission de trames par durée de trame G S ; à faible charge : S voisin de 0 ;

à forte charge beaucoup de collisions G >> SP0 = probabilité de transmission correcte d’une trame (pas de collision)S = G * P0Pr [k] = probabilité pour que k trames soient générées pendant un temps égal à la durée de trame Pr [k] = (Gk * e-G) / k!

51

Le protocole Aloha pur (2)

période de vulnérabilité de la trame

T0 T0+t T0+2t T0+3t temps

Collision avec la début de la trame

Collision avec la fin de la trame

* : pas d’écoute préalable

*

*

52

Le protocole Aloha discrétisé

Notion de slot de temps :durée du slot = durée de trame

Mise en oeuvre : horloge marquant le début du slot

Durée de période de vulnérabilité de = 1 slot

Probabilité P0 pour qu’il n’y ait pas d’autre trafic pendant le slot utilisé par la trame est P0 = e-G donc :

S = G * e-G

Probabilité pour que l’émission d’une trame nécessite k tentatives :soit (k-1) collisions + 1 tentative réussie

Pk = e-G * (1 - e-G )k-1

Performances (trafic écoulé) : Aloha discrétisé 2 fois meilleur qu’ALOHA pur

53

Les protocoles Aloha : comparaison

S = trafic écoulé

G = charge globale des

stations

0,40

0,30

0,20

0,10

0 0,5 1,0 1,5 2,0

ALOHA discrétisé :

S = G * e-G

ALOHA pur :

S = G * e-2*G

54

Les protocoles CSMA (1)

• Protocole à détection de porteuse

• CSMA 1-persistant : (exemple CSMA/CD)

station écoute le canal avant d’émettresi canal occupé alors attente active (= écoute du canal)sinon début transmission d’une trame

si détection de collisionalors début pause de durée variable ;

réémission (mêmes conditions qu’une émission) fin

fsifin

fsi

• Performances voisines de ALOHA discrétisé

55


• CSMA non-persistant :

station écoute le canal avant d’émettresi canal occupé alors attente passive

/* pas d’écoute permanente du canal */sinon début transmission d’une trame

si collision alors pause de durée variableet réémission

fsifin

fsi

• Station moins « pressée »• Meilleure utilisation du canal

56


• CSMA p-persistant :

si station prête à émettre alors écoute du canal ;si canal disponible en début de slot

alors transmission réussie avec probabilité = p ;(=> probabilité d’attente du slot suivant q = 1 - p)

si canal disponible en début de slot suivant alors mêmes probabilités (p et q) ;………...etc…tant que transmission non réussie

ou canal devenu occupé par une autre station.

si collision alors pause de durée variable ;réémission en début de slot si canal disponible

fsi

57

Les protocoles Aloha et CSMA : comparaison S

= tr

afic

éco

ulé

=no

mbr

e m

oyen

de

tram

es g

énér

ées

par

duré

e de

tram

e

G = nombre moyen de tentatives de transmission par durée de trame

1,00,90,80,70,60,50,40,30,20,1

0 1 2 3 4 5 6 7 8 9

ALOHA discrétisé

S

G

ALOHA pur

CSMA 1-persistant

CSMA 0,1-persistant

CSMA 0,5-persistant

CSMA 0,01-persistant

CSMA non-persistant

58

Les états du protocole CSMA/CD

trame trame trame trame

T0 : 2 stations émettent ...

période detransmission

période decontention

période d’oisiveté

temps

slots decontention

période decontention

slots decontention

59

Un exemple de protocole sans collision : le protocole à réservation Bit-Map

71 31

période decontention(8 slots)

temps

transmissionde trames

0 1 2 3 4 5 6 71 1

1 51temps

0 1 2 3 4 5 6 71

2temps

0 1 2 3 4 5 6 71

1 slot / station

60

Les collisions (1) : exemple

A B A B

A B A B

collision &

A B

propagation du signal sinistré

1 2

3 4

5

arrêt d’émission

arrêt d’émission

début d’émission

début d’émission

61

Les collisions (2) : domaine• Définition :

– segment sur lequel un ensemble de stations capturent les trames envoyées par une station émettrice

• Caractéristiques :

– tous les câbles, répéteurs et stations dans un même domaine de collision partagent la même référence temporelle.

– Si trop de collisions alors switch ou routeur

• Minimiser le temps pendant lequel une collision peut se produire :

– temps max de propagation d’une trame =

– temps aller et retour de la trame = 50 µs

– 50 µs , soit 63 octets environ : on fixe un Slot-time = 51,2 µs (64 octets)

• Pour respecter ce temps maximum, on limite :

– la longueur et le nombre de segments,

– le nombre de boîtiers traversés par une trame.

62

Les collisions (3) : à l’échange de trame

• A l’émission :• La couche LLC transmet une trame (= suite de bits) à la couche physique.• Pendant la durée de la transmission (slot-time = 512 bits), elle teste le signal « collision détection » que lui fournit la couche physique.• S’il y a collision, la station commence par renforcer cette collision en envoyant un flot de 4 octets (jam)

• A la réception :• pas de test du signal « collision détection »• longueur minimale d’une trame correcte : 72 octets,• longueur d’une trame sinistrée : 64 + 4 octets,• toute trame reçue de longueur < 72 octets est rejetée.

63

Le protocole CSMA/CD : 802.3 versus BEB

Reprise d’une transmission :

- type CSMA 1-persistant- si collision, arrêt immédiat de la transmission- avant de ré-émettre une station attend : r * 51,2 µs avec

r : entier, au hasard dans l’intervalle [0, 2k ]k : entier, minimum de n et de 10n : entier; nombre de ré-émissions déjà effectuées

- la station émet à nouveau- si la 15éme ré-émission échoue, la couche physique retourne « trop d’erreurs de collision » à la couche LLC- le nombre de retransmissions est limitée à 15

- algorithme du BEB : retransmission selon une loi exponentielle binairepas de garantie sur le temps maximal pour la transmission d’une trame.

64

Le protocole CSMA/CD : 802.3D versus DCR (1)

16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

MM M C

C

C C

C

CCTCV

TCV C

1°collision

DCR = Deterministic Collision Resolution

C = collisionTCV = tranche canal vide

M = message transmis avec succès

65


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

MM M C

C

C C

CCTCV

TCV C

2°collision



66


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

MM M C

C

C

CCTCV

TCV C

3°collision



67


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

MM M C

C

C

CTCV

TCV C

réémission



68


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M C

C

C

CTCV

TCV C

4°collision



69


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M C

C

C

CTCV

TCV M

réémission



70


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M C

C

C

CTCV

TCV M

réémission



71


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M C

C

C

CTCV

TCV

5°collision



72


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M C

C

C

TCV

TCV



73


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M C

C

C

TCV

6°collision



74


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M M

C

C

TCV

réémission



75


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M M

C

C

TCV

réémission



76


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M

C

TCV

7°collision

C



77


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M

CTCV

8°collision



78


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

M M

TCV

réémission



79


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1



M

TCV

réémission

80


16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

S = nombre de stationsTC = tranche canal

TCV = tranche canal videU = durée max. de transmission d’1 msg

TCV

borne supérieure du délai de transmission = S*(TC+U)-TC

81

La trame IEEE 802.3 / Ethernet (1)

802.3

Ethernet

Préambule SFD @DEST @SCE Type DATA CRCDATA

7 octets 1 octet 6 octets 6 octets 2 octets 46-1500 octets 4 octets

Préambule SFD @DEST @SCE Long DATA CRCDATA

7 octets 1 octet 6 octets 6 octets 2 octets 46-1500 octets 4 octets

Start Frame Delimitor

taille de la zone de données

dont bourrage (padding)séquence de contrôle

802.1p/q + 2 octets classe de service (priorité) - routage par la source -- identificateur de V(irtual)LAN -

82


Préambule de synchronisation (7 octets = 10101010)

SFD : 1 octet synchronisation : 10101011

@SCE : adresse de la source, 6 octets, donc 48 bits

@DEST : adresse de la destination, 6 octets

L/T : - pour 802.3, longueur du champ donnée en octets,

- pour Ethernet, il s’agit du protocole N+1

Data : données, de 46 (CSMA/CD) à 1500 octets

Padding pour les 46 octets

CRC : sur 4 octets (polynôme de degré 32)

Trame IEEE 802.3 :

Préambule SFD @DEST @SCE Long DATA CRCDATA

83


• Préambule :– 7 octets, 56 bits, schéma [10101010]

– durée de 5,6 µs, acquisition de la synchronisation bit

• Start Frame Delimiter [SFD] :– 1 bit utile, SFD = 10101011

– acquisition de la synchronisation caractère et de la synchronisation trame

• Adresses individuelle Ethernet / 802.3 :

– 6 octets (identification du fabriquant : (IEEE) + numéro de série ), 48 bits

• Adresse niveau MAC unique !

• Exemple matériel SUN : 08:00:20:c:a2:64

• Adresse de groupe :– Broadcast : FF:FF:FF:FF:FF:FF

– Multicast :

• le premier octet de l'adresse est impair

• de 01:00:5E:00:00:00 à 01:00:5E:7F:FF:FF multicast IP

84


• Padding :– complément à 64 octets de la taille totale de la trame dont la longueur des

données est inférieure à 46 octets

– Une trame est considérée comme valide si sa longueur est d’au moins 64 octets :

46 <= données + padding <= 1500

• Débit d’émission / réception : 10 Mbit/s– 10 bits / s

• Longueur totale des trames :– 26 octets réservés au protocole

– longueur minimale : 72 octets (dont 46 de DATA)

– longueur maximale : 1526 octets

85

Exemple de trame Ethernet (5)

00 AD 92 48 72 4500 00 0C 05 63 5808 00450000 29DB FB40 00FE067D CB81 6E 1E 1A81 6E 02 1102 8B02 036A 86 7B 57B6 B6 B0 20501024 0015 8900 000254 41 4D 49 46D7 87 6C A4

Adresse MAC source : 0:ad:92:48:72:45Adresse MAC destinataire : 0:0:c:5:63:58protocole IP / trame Ethernet

N-PDU (protocole IP)

T-PDU (protocole TCP)

padding pour atteindre 46 octetsCRC

86

Charge utile (MTU) - débit max.

• Maximum Transmissible Unit : RFC 1191

• Quelques exemples de MTU en octets :

– NetBIOS : 512 X25 : 576

– IEEE 802.2/3 : 1492 Ethernet V2 : 1500 PPP : 1500

– FDDI : 4352 Token Ring - 802.5 : 4464 Token Bus - 802.4 : 8166

• Débit maximum ou « throughput » en octet/s :

T = taille(MTU) / [taille(MTU) + taille (OH)] * (10/8) Moctet/s

OH = overhead = nombre d’octets contrôle + nombre d’octets inter-trames)

• Exemples :

– Ethernet V2 : OH = 38 MTU = 1500 T= 1,219 Moctets/s

OH = 38 MTU = 46 T = 0,685 Moctets/s

– 802.3 : OH = 46 MTU = 1492 T = 1,213 Moctets/s

OH = 46 MTU = 38 T = 0,565 Moctets/s

87

Interconnexion (1) :répéteurs

• Les répéteurs

– réception, amplification et transmission des signaux analogiques sur des supports physiques homogènes (niveau 1)

– fonctionnent au niveau bit

– augmentent la distance entre deux stations d’un réseau local

– se connectent comme une station / propagent les erreurs de collision

– protocole SNMP

– n’a pas d’adresse Ethernet

88

Interconnexion (2) : concentrateurs

Les concentrateurs - «hubs»

- «répéteurs» - «étoiles»– fonction de répéteurs multiports (niveau 1)

– concentration en étoile / bus Ethernet « concentré »

– permettent de faire des jonctions entre plusieurs supports physiques

– protocole SNMP (administration)

– 1 même domaine de collision

– n’a pas d’adresse Ethernet

89

Interconnexion (3) : ponts (1)

• Les ponts - bridges -

– fonctionne au niveau 2

– technologie de commutation (store and forward)

– les trames sont transférées d’un port à un autre en fonction des adresses MAC

– les segments rattachés à un pont sont dans des domaines de collision différents

MAC MAC

LLC LLC

MAC

LLC

MAC

LLC

N NT T

pont

90


• Les types de ponts– pont MAC : si les couches MAC sont compatibles, réseaux de même type

– pont LLC : remonte au niveau, encapsulation de la trame dans la couche MAC : réseaux différents

• Les ponts filtrants– isoler les trafics sur les sous-réseaux

– non-retransmission des trames erronées et des collisions

– pas de bouclage indéfini pour une trame sur un réseau interconnecté

• IEEE 802.1D/1990 : algorithme du spanning tree (arbre recouvrant)

• IBM (Token Ring) : algorithme de routage par la source

91


A B

C D

E F

pont 1

pont 2

port 1

port 2

port 1

port 2

réseau 1

réseau 2

réseau 3

92

Interconnexion (6) : Spanning Tree (1)

• permet de trouver un chemin dans un réseau constitué de plusieurs domaines de collisions

• chaque pont envoie un message multicast vers les autres ponts <identité racine*, coût, identité pont, n° port>

• chaque pont applique l’algorithme de Dijkstra et envoie une série de multicast

• sur chaque LAN, le pont de distance la plus petite avec la racine devient le pont désigné

IEEE 802.1d : algorithme du spanning tree (arbre recouvrant)

* vraie ou supposée

93


A

B

réseau 1

réseau 3

réseau 2

pont 1

pont 2

pont 3

pont 4

1

2

1 1

1

2

2

2

A

A

A

B

réseau 1

réseau 3

réseau 2

pont 1

pont 2

pont 3

pont 4

1

2

1 1

1

2

2

2

A

A

A A

* A B* ponts 1 & 3 notent position de A

* pont3 réseau 3* B* ponts 2 & 4 notent position A* mis en file attente vers réseau 2

Pontage redondant : Phase 2Pontage redondant : Phase 1

94


A

B

réseau 1

réseau 3

réseau 2

pont 1

pont 2

pont 3

pont 4

1

2

1 1

1

2

2

2

A

A

A A

A

B

réseau 1

réseau 3

réseau 2

pont 1

pont 2

pont 3

pont 4

1

2

1 1

1

2

2

2

A

A

A

A

* pont1 réseau 2* ponts 2 & 4 notent changement position A* mis en file attente vers réseau 3

* pont4 réseau 2* pont2 réseau 3* B* pont4 réseau 2 : pont1 & pont2


95


A

B

réseau 1

réseau 3

réseau 2

pont 1

pont 2

pont 3

pont 4

1

2

1 1

1

2

2

2

A A

AA

A

B

réseau 1

réseau 3

réseau 2

pont 1

pont 2

pont 3

pont 4

1

2

1 1

1

2

2

2

A A

AA

* B* ponts continuent à transmettre

* nb de copies de la trame émise par A prolifère ...* pontage redondant* éviter les boucles* extinction sélective des messages


96


réseau 1

réseau 2

pont 13

1

2

pont 15

1

2

13,0,13,1

13,0,13,2

15,0,15,1

15,0,15,2

meilleur

calculée

meilleur

calculée13,0,13,x 15,0,15,x

Ponts en parallèle : Phase 1Chaque pont se considère racine et émet le message : <id-pont, 0, id-pont, n°-port> sur ses 2 ports

97


réseau 1

réseau 2

pont 13

1

2

pont 15

1

2

13,0,13,1

13,0,13,2

13,1,15,1

13,1,15,2

meilleur

calculée

meilleur

calculée13,0,13,x 13,1,15,x

Ponts en parallèle : Phase 2pont 13 : statuquo pour sa configuration, les 2 messages de configuration reçus <15, 0, 15, 1> et <15, 0, 15, 2>sont plus grand que sa propre configurationpont 15 : port 1 meilleur pour aller à la racine ; meilleur = les 2 messages de configuration reçus sont meilleurs que ceux détenus initialement

13,0,13,1

98

Interconnexion (11) : Scanning Tree (7)

réseau 1

réseau 2

pont 13

1

2

pont 15

1

2

13,0,13,1

13,0,13,2

13,1,15,1

13,1,15,2

meilleur

calculée

meilleur

calculée13,0,13,x 13,1,15,x

Ponts en parallèle : Phase 3pont 13 : statuquopont 15 : port 2 désactivéplus de boucle sur le réseau

13,0,13,1

99


réseau 1

réseau 2

pont 41

2pont 1

1

2

meilleur

calculée

meilleur

calculée2,1,4,x 1,0,1,x

Interconnexion de 4 réseaux : Phase 1même instant de départ pour les 4 pontspont 1 : rien de mieux, se suppose toujours racinepont 2 : msg reçu <1,0,1,1> meilleurpont 3 : idpont 4 : 2 msgs reçus <2,0,2,1> & <3,0,3,2> meilleurs

pont 21

2

meilleurcalculée1,1,2,x

1,0,1,1

pont 31

2

meilleur

calculée1,1,3,x

1,0,1,2

meilleur

2,0,2,1

100


réseau 1

réseau 2

pont 41

2pont 1

1

2

meilleur

calculée

meilleur

calculée2,1,4,x 1,0,1,x

Interconnexion de 4 réseaux : Phase 2les ponts continuent à émettrepont 1 : msg émis vers tous ponts ; autres ponts émettent sauf vers la racineponts 2 & 3: même msg reçu du pont 1, raspont 4 : 2 msgs reçus <1,1,2,1> sur port1et <1,1,3,2> sur port2, port1 meilleur, conf. calculée <1,2,4,x> plus grand que msg reçu port2 ,port2 inhibé, plus de boucle

pont 21

2

meilleurcalculée1,1,2,x

1,0,1,1

pont 31

2

meilleur

calculée1,1,3,x

1,0,1,2

meilleur

1,0,2,1

101

Interconnexion (14) : commutateur (switch)

domaine de collision

fonctionne au niveau 2

102

Interconnexion (15) : routeurs

• Les routeurs– fonctionne au niveau 3

– technologies de routage :

• type « vecteur de distance »

• type « link state »

– gestion des tables de routage

– les segments rattachés à un pont sont dans des domaines de collision différents

• Les B-routeurs– pont et routeur à la fois

103

Interconnexion (16) : récapitulatif

données

datagrammes

trames

chaînes de bits

7

6

5

4

3

2

1

passerelle applicative, gateway

routeur, bridge-routeur

pont, bridge, commutateur, switch

répéteur, hub, concentrateur

104

Abréviations du comité IEEE 802.3 (1) : le 10 Mbit/s

10 base 5 : coaxial, 500 m / segment, 2.5 m min. entre 2 nœuds, diamètre 10 mm, couverture max. 2 500 m, nb nœuds max. / segment 100.

10 base 2 : coaxial, 185 m / segment, 0.5 m min. entre 2 nœuds, diamètre 5 mm, couverture max. 925 m, nb nœuds max. / segment 30.

10 base T : paire téléphonique, 100 m / segment en étoile, couverture max. 400 m, nb nœuds max. / segment 30.

10 base FL : 2 fibres optiques, 2 000 m / segment en étoile.

10 base FB : interconnexion entre hubs, transmission synchrone

(10 base FP) : (interconnexion par soudure de fibre)

105

Abréviations du comité IEEE 802.3 (2) : le 100 Mbit/s

Similitudes avec le 10 M bit/s sauf la topologie en bus

100 base TX : 2 paires torsadées duplex, catégorie 5

100 base T4 : 4 paires torsadées alternat, catégorie 3 à 5

100 base FX : 2 fibres optiques monomodes

connexion des stations via des hubs-répéteurs

106

Abréviations du comité IEEE 802.3 (3) : le 1 Gbit/s

1 000 base TX : 100 m, 4 paires torsadées non blindées duplex catégorie 5

1 000 base CX : 25 m, câble coaxial ou 2 paires torsadées blindées

1 000 base LX : 3 km, 2 fibres optiques monomode duplex

1 000 base SX : 500 m, 2 fibres optiques multimode duplex

107

La normalisation IEEE

Le comité IEEE 802 (début 02/1980) et ses sous-groupes :

802.1 = architecture générale du réseau, interconnexion, administration, VLAN

802.2 = sous-couche LLC, modes : connecté et non connecté

802.3 = LAN type Ethernet, CSMA/CD,

802.3u 100Mbits/s, 802.3z 1Gbits/s, 802.3ae 10Gbits/s

802.4 = LAN type bus à jeton, TokenBus

802.5 = LAN type anneau à jeton, TokenRing

802.5n 4 à 16Mbits/s, 802.5v 1Gbits/s

802.10 = protection, sécurité, gestion de clés

802.11 = WLAN réseau local sans fil, WiFi

802.11a 30Mbits/s, 802.11b 6Mbit/s, 802.11g 11Mbit/s

802.12 = LAN Ethernet 100VG

802.15 = WPAN réseau personnel/domestique sans fil, Bluetooth

108

Les VLANs (1)

Les réseaux locaux virtuels :• construit à l’aide de commutateurs dont on restreint les possibilités de commutation• définition de groupes (= domaine de broadcast), de membres de groupes• communication totale entre les membres d’un groupe• communication impossible entre membres de groupes différents

• un VLAN peut être défini par port, par adresse MAC, par adresse IP selon les switches).• un VLAN donne lieu à une administration•un VLAN peut être réparti sur plusieurs commutateurs reliés entre eux• entre VLAN, on fait toujours du routage, quelle que soit la configuration des commutateurs

109

Les VLANs (2)

routeur

switchswitch

VLAN 1VLAN 2

Trame Ethernet versus IEE-802.1p/q :champ : quel VLAN pour la trame ?champs complémentaires : routage par la source, type, gestion flux

110

Les réseaux locaux sans fil : motivations

• LAN = CSMA/CD– on émet aussitôt que le médium est libre

– on écoute le canal pour savoir s’il est libre

– 802.3

• Problèmes des réseaux sans fil– atténuation du signal : inversement proportionnel au carré de la

distance (zone d’interférence)

– les interférences ont lieu à la réception

• problème de la station cachée

• problème de la station exposée

111

Puissance des signaux

A CB

A et B émettent ; le signal B masque le signal de A.C ne peut recevoir A ; problème si A est une station de base...

112

Interférence entre stations

113

Station masquée

A envoie un message à B ; C souhaite émettre vers A ou B;C peut émettre car le canal est libre « CS »collision en B / A ne peut détecter « CD »A est masqué pour C

A B C

114

Station exposée

A B C

B envoie vers A et C souhaite émettre vers DC doit attendre car il détecte « CD »C est exposé à B

115

Méthodes d’accès

• SDMA - Space Division Multiple Access– l’espace est découpé en secteurs à l’aide d’antennes directives

– structure cellulaire

• FDMA - Frequency Division Multiple Access– fréquence affecté à un canal de communication

• statique (ex radio)

• GSM

• FHSS - Frequency Hopping Spread Spectrum

• TDMA - Time Division Multiple Access– allocation de la porteuse pendant un intervalle de temps

116

FDD / FDMA

• Exemple du GSM

124

124

124

124

124

124

960 MHz

935,2 MHz

915 MHz

890,2 MHz

200 KHz

20 MHz

117

TDD / TDMA

• Exemple DECT

1 2 3 11 12 1 2 11 2

t

3

Descente Montée

118

DAMA Demand Assigned Multiple Access

• Rappel efficacité ALOHA

– Aloha pur = 18% / Aloha discrétisé = 36%

• efficacité portée à 80% si réservation

– l’émetteur doit réserver un slot

– l’émission a lieu sans collision sur un slot réservé

• mais…

– la réservation prend du temps

• quelques exemples

– réservation-ALOHA (réservation explicite)

– réservation implicite PRMA

– réservation-TDMA

119

Réservation ALOHA

• Principe : 2 modes d’échange– de l’ALOHA pour la réservation

• collision possibles mais pour un nombre limité de slots

– puis utilisation du slot réservé pour une transmission sans risque de collision

– les stations doivent tenir à jour une liste cohérente de réservation de slots (pb de synchro)

A RR R A

120

Réservation implicite PRMA

• Packet Reservation Multiple Access– une trame est composée d’une séquence de slots

• on peut repérer un slot par son numéro d’ordre dans la trame

– les stations accèdent aux slots vides par ALOHA

– une fois que la station a acquis un nouveau slot

• le numéro du slot est conservé tant que la station doit émettre

DC A B A FAC A B AA

FB AAE FE B A DA

DC t

121

Réservation TDMA

• Reservation Time Division Multiple Access– une trame est une séquence de n « mini-slots » de réservation et de

m slots de données

– chaque station a son propre « mini-slot » et peut réserver k slots de données dans le trame (on a m = k*n)

– les autres stations peuvent prendre les slots de données non utilisés (round robin)

122

MACA

• Multiple Access Collision Avoidance– émission de messages particuliers pour éviter les collisions

• RTS - Request to Send : demande le droit d’émettre une donnée en envoyant ce paquet (court)

• CTS - Clear to Send : le récepteur de RTS renvoie le droit d’émettre

– Le paquet de signalisation contient:

• l ’adresse de l ’émetteur et du récepteur

• la taille des données à émettre

– DFWMAC (802.11) est une variante

123

MACA - station masquée

RTS

CTSCTS

A et C souhaitent envoyer un message à BA envoie un RTS le premierC attend après avoir entendu la réponse de B

124

MACA - station exposée

RTS

CTS

RTS

B souhaite envoyer un message à A, et C à un autre terminal X

C n’a pas à attendre un CTS de A donc peut converser avec X

125

DFWMAC / IEEE 802.11

idle

attentedroit

émission

attenteACK

paquet à émettre;RTS

Time-out;RTS

CTS;Paquet

ACKR-occupé

Time-outou NAK;

RTS

idle

attentepaquet

Paquet;ACK

Time-out;NACK

RTS;CTS

RTS;R-occupé

126

CDMA Code Division Multiple Access

• Principes– tous les terminaux peuvent émettre en même temps sur toute la bande

– chaque émetteur à un code « aléatoire » unique, le signal reçu est « XORé » avec ce code

– le récepteur peut isoler le signal émis s’il connaît le code émetteur

– 1 bit est découpé en plusieurs chips

• Avantages– toute la bande passante est disponible

– l’espace des codes > espace des fréquence

– le chiffrement est aisé

127

CDMA découpage en « chip »

128

CDMA Code Division Multiple Access

• Inconvénients– les signaux doivent avoir des puissances sensiblement équivalentes

– complexité importante des récepteurs

– vitesse de modulation liée au débit des chips et non des bits

129

CDMA exemple

A : émet un « 1 »code : 010011

Un chip à « 0 » = +1 et un chip à « 1 » = -1

+1 -1 +1 +1 -1 -1 B : émet un « 0 »code : 110101

+1 +1 -1 +1 -1 +1

Sur le support on obtient : +2 0 0 +2 -2 0

Réception du message de A (produit interne):

Réception du message de B:

2 + 0 + 0 + 2 + 2 + 0 = 6 « 1 »

-2 + 0 + 0 -2 -2 + 0 = -6

Réception du message de A:

« 0 »

130

CDMA - DSSS

• Direct Sequence Spread Spectrum• énergie du signal étalée dans une bande plus large

• échantillonnage à une fréquence plus élevée

• codes orthogonaux avec faible auto corrélation (décalage)

• Problèmes• les séquences ne sont pas rigoureusement orthogonales

• le contrôle de la puissance des signaux reçus est crucial

131

CDMA - FHSS

• Frequency Hopping Spread Spectrum• le fréquence de transmission est changée périodiquement selon

une séquence aléatoire

• Fast Frequency Hopping• quand il y a plus d’un saut en fréquence par symbole transmis

• Slow Frequency Hopping• quand un ou plusieurs symboles sont transmis sur un canal en

fréquence

f

t

132

SAMA Spread Alpha Multiple Access

• Motivations : Aloha peu efficace / CDMA complexe

• Principe : Etalement de spectre avec un seul code

1 1 0

0 1 0

collisions

1 1 00 1 0

t

t

t

t

X

Y

133

Hiérarchie des accès

répartition temps/fréquence

répartition par demande

avec contention sans conflit

accès aléatoire accès par réservation

répartition fixe

ex: TDD / FDD

ex: ALOHA, PRMA, CSMA

jeton, polling

ex: R-ALOHA

slot-time ou non

134

Accès selon le type de trafic

Type de trafic Type d'accès

Messages courts et envoyés

par rafales

Protocoles d'accès aléatoire

Messages longs, envoyés parrafales, nombre importantd'utilisateurs

Protocoles à réservation

Messages longs, envoyés parrafales, peu d'utilisateurs

Protocoles à réservation aveccanal TDMA pour la réservation

Trafic déterministe FDMA,TDMA,CDMA

135

Bilan SDMA / TDMA / FDMA / CDMA

SDMA TDMA FDMA CDMAprincipe Espace segmenté

en cellulesTemps segmenté enintervalles élémentaires

Bande passantesegmentée encanaux

Etalement duspectre par descodes orthogonaux

stations Une seulestation peut êtreactive

Les stations ont toute labande pendant un ST

Les stations ontleurs proprescanaux de manièreininterrompue

Toutes les stationssont actifs sur labande de manièreininterrompue

sélection Antennesdirectives

Synchro temporelle Filtrage fréquentiel Convolution decodes

pro Très simple Connu, numérique,flexible

Simple, connu,robuste

Flexible, bonneutilisation de labande

cons Non flexible Pb de synchro Non flexible, BPest chère

Récepteurscomplexes

Intérêt encombinaison

Standard dans lesréseaux fixes. En

Avec TDMA(frequency

Des difficultés, encombinaison avec

136

Les réseaux locaux sans fil - WLAN

• Wireless Local Area Network

• Avantages• très grande flexibilité dans la zone de couverture

• plus de problèmes de câblage (immeubles…)

• plus robuste

• Inconvénients• débit plus faible que les réseaux locaux câblés (1 à 11 Mb/s)

• déjà de nombreuses solutions propriétaires, les standards sont à la traîne (IEEE 802.11)

• pas de solution globale (règlements nationaux)

137

La technologie radio

• Technique– habituellement exploitation de la bande 2,4 GHz

• Avantages– expérience des WAN « mobiles »

– bonne couverture (traverse les murs, fenêtres)

• Inconvénients– très peu de licences

– compatibilité électro-magnétique

• Exemple– HIPERLAN / WaveLAN / Bluetooth

138

Une topologie de réseau « ad-hoc »

Mode point à point

• Pas d’infrastructures fixes

• Chaque nœud peut échanger des infos avec chaque autre nœud

• Routage dynamique

139

Une topologie de réseau « ad-hoc »

Routage dynamique: 3 types de protocoles

• Protocoles proactifs:

• stockage des routes identifiées dans une table de routage

• transmission de la table de routage aux autres nœuds

• important trafic de contrôle

• Protocoles réactifs:

• routes redéfinies à chaque fois

• pas de trafic de contrôle

• coût important en bande passante

• Protocoles hybrides

140

Une topologie de réseau à infrastructure

PA PA

PA

PA : Point d’accèsAP - Access PointMode cellule

• Points d’accès = répéteur pour le réseau sans fil

• Points d’accès = passerelle vers le réseau fixe

• Roaming : changer de cellule en gardant une liaison

141

802.11 - « infrastructure » WLAN

Système de distribution

PAPont

PA

LAN 802.x

EES

BSS1

BSS2

STA1

STA3STA2

STA : station

BSS : Basic Service Setgroupe de stations

utilisant la même fréquence

EES : Extented Service Setréseau logique formé parinterconnexion de WLAN

142

802.11 - pont

802.11 PHY

802.11 MAC

LLC

IP

802.3 PHY

802.3 MAC

LLC

IP

LLC

802.3 MAC

802.3 PHY

802.11 MAC

802.11 PHY

143

802.11 - couche physique (1)

• 2 Technologies : FHSS et DSSS

Méthode à séquence directe

• Division de la bande des 2.4 GHz en 14 canaux de 22 MHz

• Données envoyées sur plusieurs canaux en parallèles

Méthode à saut de fréquence

• Division de la bande des 2.4 GHz en 78 canaux de 1 MHz

• Saut de fréquence de l’émetteur

144

802.11 - couche physique (2)

• Transmission : Radio et Infrarouge

• 2 Technologies : FHSS et DSSS

– FHSS (Frequency Hopping Spread Spectrum)

• 1 Mbit/s, étalement et détection

• au minimum 2,5 hops par seconde

– DSSS (Direct Sequence Spread Spectrum)

• modulation DBPSK (Differential Binary Phase Shift Keying), pour 1 Mbit/s

• modulation DQPSK (Differential Quadrature …)

• les préambules et en-tête sont toujours transmis à 1Mbit/s, les données à 1 ou 2 Mbit/s

145

802.11 - CSMA / CA (1)

canal occupé trame suivante

DIFS

fenêtre de contentioncomposée de « slot time »

CSMA/CA : CSMA Collision Avoidance

Une station prête à émettre écoute le canal « CS »,Si la canal est libre depuis un temps IFS (selon le service) alorsla station peut émettresinon la station attend un temps IFS plus un temps de contentionaléatoire (« back-off time » multiple du temps d’un slot).Si une autre station émet pendant le temps du « back-off » alors lecompteur temporel est gelé.

146

802.11 - CSMA / CA exemple

DIFSA

B

C

D

E

canal occupé Back-off écoulé

Back-off restant

DIFS

147

802.11 - CSMA / CA (2) unicast

trame

ACK

trame

SIFS

DIFS

Emetteur

Récepteur

autres

Le récepteur d’une trame doit acquitter une réponse à l’émetteurcontrôle du CTS, attente du temps IFS minimal puis envoi d’un ACK

DIFS

148

802.11 - DFWMAC

RTS

CTS

trame

DIFS

SIFS

DIFS

E

R

autres

trame

ACK

NAV - CTSNAV - RTS

SIFS SIFS

« Carrier Sense » reporté

E envoie une trame RTS - Request To Send avec paramètresde réservation (temps d’accès).Si R est prêt, envoie d’un CTS - Clear To Send après un SIFS.E envoie la trame utile suivi d’un ACK de R si pas de collision, les autres stations attendent en fonction des paramètres de RTSet RST, NAV - Network Allocation Vector.

149

cours réseaux

Fin du chapitre 3

Documents

1 cours réseaux chapitre 3 la couche liaison. 2 La couche liaison Objectifs, la détection et la correction d'erreurs, le contrôle de flux, les protocoles