Devoir Surveillé : Réseaux Locaux

Questions indépendantes

Question 1 - Détection d'erreurs et de collisions

Lorsqu'une trame subit une collision, le signal sur le support physique est altéré.

Le récepteur détecte que la trame est erronée en effectuant deux vérifications à la réception :

• Le contrôle de la taille de la trame (qui risque d'être incomplète, formant ce qu'on appelle un fragment de collision ou "runt").
• Le contrôle du FCS (Frame Check Sequence), c'est-à-dire la somme de contrôle ajoutée à la fin de la trame. En cas de collision, le calcul du FCS sur les données reçues ne correspondra pas à celui contenu dans la trame.

L'émetteur, en revanche, n'utilise pas ce procédé pour se rendre compte de la collision. Dans un réseau Ethernet (CSMA/CD), l'émetteur écoute le support pendant qu'il transmet. Il utilise le mécanisme de détection de collision (CD - Collision Detection) en observant les variations de tension sur le câble. S'il détecte un signal supérieur à ce qu'il a lui-même émis, il en déduit immédiatement qu'une collision a eu lieu, sans avoir besoin de lire le FCS.

Question 2 - Transmission Full Duplex

La transmission duplex intégrale (full duplex) permet à une station d'émettre et de recevoir simultanément.

Dans les réseaux Ethernet filaires, ceci est rendu possible en utilisant un support physique dédié par sens de transmission (par exemple, des paires torsadées distinctes pour l'émission et la réception) sur des liaisons point à point. C'est le cas des liaisons DTE-DTE (ordinateur à ordinateur), DTE-SWITCH (ordinateur à commutateur) ou SWITCH-SWITCH. Puisqu'il n'y a qu'un seul équipement à chaque extrémité de ces canaux dédiés, aucune collision physique ne peut se produire. Le mécanisme CSMA/CD devient alors inutile et est désactivé.

Pour les réseaux sans fil WiFi, la transmission full duplex n'est pas possible de cette manière. Le canal hertzien (l'air) est par nature un support multipoint partagé par l'ensemble des stations présentes dans la cellule. Une station ne peut pas émettre et recevoir en même temps sur la même bande de fréquences sans que son propre signal d'émission n'écrase les signaux beaucoup plus faibles qu'elle tente de recevoir. Le recours à une méthode d'accès (CSMA/CA) reste donc obligatoire.

Exercice 1 - Méthode CSMA/CA en WiFi

Impossible à résoudre - Données manquantes

Il est impossible de répondre à cet exercice. L'énoncé indique "comme le montre la figure ci-dessous, nous supposons que...", mais la figure décrivant l'état initial des stations (le moment où A, B et C souhaitent transmettre, ainsi que leurs fenêtres de contention respectives) est absente du document fourni. Sans connaître les instants d'arrivée des trames ni les valeurs aléatoires tirées initialement, nous ne pouvons pas déterminer l'évolution des temps de Backoff (BO) ni identifier les collisions.

Exercice 2 - Étude comparative des Backoffs Ethernet et WiFi

Partie I - Cas d'un réseau Ethernet

L'algorithme utilisé est le BEB (Binary Exponential Backoff). Après n collisions, une station tire un délai aléatoire dans l'intervalle [0 .. 2ⁿ - 1].

Question 1 - Délais aléatoires après la première collision

Les stations A et B viennent de subir leur toute première collision pour les trames A1 et B1 (n = 1). L'intervalle de tirage pour les deux stations est [0 .. 2¹ - 1], soit [0 .. 1]. Les deux stations généreront donc une valeur dans le même intervalle : [0 .. 1].

Question 2 - Probabilité de succès de la station A

Pour que A émette A1 avant B1 sans subir de collision, il faut que le délai choisi par A soit strictement inférieur à celui de B. Les tirages possibles pour le couple (A, B) sont : (0,0), (0,1), (1,0) et (1,1). Chaque issue a une probabilité de 1/4. Le seul cas où A gagne sans collision est si A tire 0 et B tire 1. La probabilité est donc : P(A=0) × P(B=1) = 1/2 × 1/2 = 1/4.

Question 3 - Délais aléatoires après la collision entre A2 et B1

La station A vient de subir sa première collision pour sa nouvelle trame A2 (n = 1). Son intervalle est donc [0 .. 1]. La station B, en revanche, vient de subir une deuxième collision consécutive pour sa trame B1 (n = 2). Son intervalle s'agrandit de manière exponentielle : [0 .. 2² - 1], soit [0 .. 3].

Question 4 - Probabilité de succès de A2 face à B1

La station A tire dans {0, 1} et la station B tire dans {0, 1, 2, 3}. A gagne si son délai est strictement inférieur à celui de B. Nous pouvons calculer cette probabilité de deux manières (qui mènent au même résultat) :

Méthode directe (addition des cas gagnants pour A) : P(A gagne) = P(A=0) × P(B>0) + P(A=1) × P(B>1) P(A gagne) = (1/2 × 3/4) + (1/2 × 2/4) = 3/8 + 2/8 = 5/8

Méthode par le complémentaire (énoncée dans le corrigé source) : On calcule 1 moins la probabilité que B gagne ou qu'il y ait collision. P(A gagne) = 1 − [ P(B=0) + P(A=1 et B=1) ] P(A gagne) = 1 − (1/4 + 1/8) = 1 − 3/8 = 5/8

Question 5 - Probabilité de succès de A3 face à B1

Cette fois, A subit sa première collision pour la trame A3 (n = 1) et tire dans l'intervalle [0 .. 1]. La station B subit sa troisième collision pour la trame B1 (n = 3) et tire dans l'intervalle [0 .. 2³ - 1], soit [0 .. 7].

En utilisant la méthode directe : P(A gagne) = P(A=0) × P(B>0) + P(A=1) × P(B>1) P(A gagne) = (1/2 × 7/8) + (1/2 × 6/8) = 7/16 + 6/16 = 13/16

(Via le complémentaire : 1 − [ 1/8 + (1/2 × 1/8) ] = 1 − 3/16 = 13/16).

Question 6 - Interprétation (Effet de capture)

On observe que plus la station B perd et subit des collisions, plus son intervalle de tirage s'agrandit, ce qui diminue ses chances de gagner à la tentative suivante. À l'inverse, la station A transmet de nouvelles trames avec un intervalle initial très petit. La probabilité que A gagne augmente à chaque fois (1/4, puis 5/8, puis 13/16). La station A finit par monopoliser le support physique. Ce phénomène caractéristique d'Ethernet est appelé l'effet de capture du canal.

Partie II - Cas d'un réseau WiFi

Question 7 - Émission de A2 après le succès de A1

La station A ne peut pas tenter d'émettre A2 immédiatement après le succès de A1. Dans la norme WiFi (CSMA/CA), pour éviter qu'une station ne monopolise le canal, une station qui vient de réussir une transmission et qui a une autre trame en attente est obligée d'effectuer un nouveau Backoff (tiré dans la fenêtre initiale [0 .. 31]) avant de pouvoir émettre.

Question 8 - Probabilité de succès de B1 face à A2

Avant l'émission de A1, B avait tiré un délai de 1×T et A un délai de 0×T. Pendant l'émission de A, le compteur de B est suspendu. Il reste donc à B un délai de 1×T à écouler. Pour émettre A2, A doit tirer un nouveau backoff dans l'intervalle [0 .. 31]. Pour que B1 puisse être réémise sans collision avant A2, il faut que le délai restant de B (1×T) soit strictement inférieur au nouveau délai tiré par A. La valeur tirée par A doit donc être comprise entre 2 et 31 inclus. Il y a 30 valeurs gagnantes possibles sur les 32 de l'intervalle. La probabilité est donc : P(BackoffA > 1) = 30/32.

Question 9 - L'effet de capture dans le WiFi

La conclusion de la question 6 ne s'applique pas au réseau WiFi. Contrairement à Ethernet, dans CSMA/CA, une station qui réussit sa transmission (A) doit tirer un nouveau backoff complet, tandis que la station perdante (B) conserve son backoff restant (qui est devenu très petit). De plus, en cas de collision, les deux stations augmentent simultanément la taille de leur intervalle, ce qui maintient une certaine équité. Le mécanisme figeant le compteur de la station perdante garantit que celle-ci finira par avoir l'accès prioritaire au canal, empêchant ainsi l'effet de capture.

Méthode

Pour réussir les exercices sur les protocoles d'accès au support (MAC), voici la marche à suivre :

1. Identifier le protocole : Est-ce Ethernet (CSMA/CD) ou WiFi (CSMA/CA) ? Les mécanismes de gestion des collisions (BEB) sont radicalement différents.
2. Suivre l'historique par station : Le nombre de collisions n est une variable locale à chaque trame pour chaque station. Maintenez à jour la valeur de n et l'intervalle [0 .. 2ⁿ - 1] pour la station A et la station B indépendamment.
3. Réinitialisation : N'oubliez pas qu'en cas de transmission réussie d'une trame, le compteur de collisions retombe à n = 0 pour la trame suivante de cette même station.
4. Calcul des probabilités : Utilisez l'univers des tirages. Si A tire dans un ensemble de taille X et B dans un ensemble de taille Y, l'univers comporte X × Y cas équiprobables. Comptez les cas où la valeur de A est strictement inférieure à la valeur de B (succès de A), les cas d'égalité (collision), ou utilisez l'événement contraire pour simplifier vos calculs.
5. Gestion du Backoff en WiFi : Souvenez-vous de la règle d'or du CSMA/CA : le temps s'écoule pour tout le monde (les compteurs décrémentent quand le canal est libre), et en cas de succès, un post-backoff est obligatoire pour la trame suivante.