Ingénierie des réseaux

Ce document traite des méthodes d’accès au canal dans les réseaux de communication, en particulier les réseaux utilisant des supports partagés. Il s’adresse aux étudiants en ingénierie des réseaux ou aux chercheurs souhaitant comprendre les principes fondamentaux des protocoles d’accès au canal, leurs performances et leurs mécanismes de gestion des collisions.

Contexte des liaisons réseau

Les réseaux utilisent deux types principaux de liaisons :

• Liaisons point-à-point : un émetteur communique directement avec un récepteur. Ces liaisons sont généralement bidirectionnelles et faciles à exploiter car le support de transmission est dédié.
• Liaisons multipoints : plusieurs équipements partagent un même support de transmission, ce qui nécessite des méthodes d’accès pour gérer la communication simultanée.

Un exemple courant de support partagé est le Wi-Fi, où plusieurs stations utilisent la même fréquence et le même canal pour transmettre des données.

Problématique des méthodes d’accès au canal

Dans un réseau à support partagé, les ressources sont limitées et doivent être partagées entre plusieurs utilisateurs. Une forte charge sur le canal peut entraîner un rendement très faible, notamment à cause des collisions entre transmissions simultanées.

Taxonomies des méthodes d’accès au canal

Classification selon le mode d’accès

• Accès aléatoire : les stations émettent sans autorisation préalable, ce qui engendre des contentions et des collisions.
• Accès déterministe : un mécanisme désigne la station autorisée à émettre, par exemple selon un ordre Round Robin. Ce mode nécessite une synchronisation stricte entre les stations.

Classification selon l’approche de contrôle

• Approche centralisée : un nœud primaire attribue les droits d’accès au canal.
• Approche distribuée : tous les nœuds participent de manière égale au contrôle d’accès.

Protocoles ALOHA

Le protocole ALOHA a été développé pour permettre la réservation de chambres d’hôtels à Hawaï en utilisant les ondes radio. L’idée principale était que tous les utilisateurs transmettent librement sur une même fréquence, ce qui provoque des collisions.

Le principe de base est que chaque nœud transmet dès qu’il a un message, sans coordination préalable. En cas de collision, les messages sont perdus et doivent être retransmis après un délai aléatoire.

Évaluation d’ALOHA

On cherche à mesurer l’efficacité du canal, c’est-à-dire le pourcentage de trames transmises sans collision.

Hypothèses :

• Nombre infini d’utilisateurs.
• Une trame envoyée quand le support est libre est reçue correctement.
• Les trames suivent un processus de Poisson.

Soit :

• T : durée moyenne d’une trame (taille moyenne / débit).
• g : nombre moyen de trames émises par seconde.

La probabilité d’émettre k trames pendant une durée T est donnée par la loi de Poisson :

Pk(T) = (gT)^k / k! × e^(-gT)

Pour qu’une trame émise à l’instant t soit reçue sans collision, aucune autre trame ne doit être émise pendant l’intervalle [t - T, t + T], soit une période de 2T.

La probabilité de succès est donc :

P_succes = P0(2T) = e^(-2gT)

On définit :

• S = s × T : nombre moyen de trames émises correctement par durée de trame.
• G = g × T : nombre moyen de trames émises par durée de trame.

La relation entre S et G est :

S = G × e^(-2G)

Le trafic maximal est atteint pour G = 0,5, donnant :

S = 1/(2e) ≈ 0,184

Ce qui signifie que le canal est utilisé efficacement à environ 18 % dans le meilleur des cas.

ALOHA Slotté (discrétisé)

Pour améliorer ALOHA, le temps est divisé en intervalles fixes (slots) de durée T. Les stations doivent synchroniser leurs horloges et ne peuvent émettre qu’au début d’un slot.

Cette méthode réduit la période de vulnérabilité de 2T à T, ce qui améliore l’efficacité :

S = G × e^(-G)

Protocoles CSMA (Carrier Sense Multiple Access)

Le protocole CSMA consiste à écouter le canal avant de transmettre :

• Si le canal est libre, la station émet.
• Si le canal est occupé, la station attend.

Ce protocole ne supprime pas totalement les collisions à cause du délai de propagation du signal entre stations.

Durée de vulnérabilité

La période pendant laquelle une collision peut survenir est égale au temps de propagation maximal entre deux nœuds éloignés.

Cas des petites trames

Si la durée d’émission E d’une trame est inférieure à deux fois le délai de propagation τ (E < 2τ), certaines stations peuvent ne pas détecter la transmission d’autres stations, provoquant des collisions non détectées.

Pour éviter cela, la durée d’émission doit être au moins égale à 2τ. Si nécessaire, on ajoute des bits de bourrage pour allonger la trame.

Variantes du CSMA

• CSMA non persistant : si le canal est occupé, la station attend un temps aléatoire avant de réécouter.
• CSMA persistant : la station écoute continuellement le canal et émet dès qu’il est libre, augmentant le risque de collision mais réduisant le temps d’attente.
• CSMA p-persistant : le temps est divisé en intervalles. Si le canal est libre, la station émet avec une probabilité p, sinon elle attend un autre intervalle.

CSMA/CD (Collision Detection)

Le CSMA/CD est la méthode la plus utilisée dans les réseaux Ethernet. Il combine l’écoute du canal avant et pendant l’émission pour détecter les collisions :

• Si une collision est détectée, la station arrête immédiatement l’émission et envoie une séquence de brouillage pour avertir les autres stations.
• La retransmission est différée après un délai aléatoire.

Condition de détection de collision

La station émettrice doit écouter le canal pendant au moins deux fois le temps maximum de propagation entre deux stations. Cette période, appelée tranche canal, dure 51,2 μs.

Exemple de détection de collision

Si la station A commence à émettre à t=0 et la station B commence à émettre à t = RTT/2 - ε (où ε est un petit délai), B n’a pas encore reçu le premier bit de A. La collision sera détectée si A émet encore lorsque le premier bit de B lui parvient.

Algorithme de retransmission : Binary Exponential Backoff (BEB)

Après une collision, chaque station attend un délai aléatoire avant de réémettre, ce délai étant choisi dans un intervalle qui double à chaque collision successive :

• Initialement, n = 0.
• Après chaque collision, n = n + 1.
• Si n < 16, la station attend K × (2 × τ) secondes, où K est un entier aléatoire dans {0, 1, ..., min(2^n - 1, 1023)}.
• Si n ≥ 16, la transmission est abandonnée et la couche supérieure est informée.

Exercice : Évaluation du BEB

Question : Une trame subit 15 collisions consécutives et est transmise avec succès à la 16e tentative. Combien de temps en moyenne la station a-t-elle attendu ?

Correction : La durée moyenne d’attente est 0 + MAX/2 = 183 μs (avec MAX = 2 × 51,2 μs × 1023).

Question : Dans un réseau IEEE 802.3, deux stations A et B ont chacune une trame à transmettre simultanément, provoquant une collision. Quelle est la probabilité qu’elles abandonnent après un nombre excessif de collisions ?

Correction : La probabilité d’abandon est la multiplication des probabilités d’échec à chaque tentative, soit ½^105.

Les réseaux IEEE 802.11 et CSMA/CA

Le protocole CSMA/CA (Collision Avoidance) est utilisé dans les réseaux Wi-Fi pour éviter les collisions :

• Les stations attendent un temps d’interframe (DIFS) avant de transmettre.
• Un mécanisme de backoff (BO) est utilisé, avec une fenêtre de contention (CW) qui varie entre 1 et 1023 slots.
• Le backoff est décrémenté uniquement lorsque le canal est libre.

Problème de la station cachée

Lorsque deux stations A et C transmettent simultanément à une station B sans se détecter mutuellement, leurs transmissions interfèrent au niveau de B, provoquant une collision.

Solution RTS/CTS

Pour résoudre ce problème, un mécanisme de réservation est utilisé :

• La station émettrice envoie un message RTS (Request To Send).
• La station réceptrice répond par un CTS (Clear To Send).
• Les autres stations, informées de la durée de la transmission via RTS/CTS, maintiennent un temporisateur (NAV : Network Allocation Vector) et s’abstiennent de transmettre pendant cette période.

Débit réel dans IEEE 802.11

Quelques paramètres temporels :

• DIFS = 50 μs
• Durée moyenne de backoff = 15,5 × 20 μs = 310 μs
• SIFS = 10 μs
• Durée d’une trame de 1500 octets avec overhead MAC et synchronisation physique :
• À 2 Mbps : 6328 μs
• À 11 Mbps : 1308 μs
• Durée d’un acquittement (ACK) : 304 μs

Durée utile de la trame :

• 6000 μs à 2 Mbps
• 1091 μs à 11 Mbps

Durée totale (trame + overhead + DIFS + backoff + SIFS + ACK) :

• 7001 μs à 2 Mbps
• 1937 μs à 11 Mbps

Débit maximal effectif :

Débit nominal	Capacité max	Débit maximal
2 Mbps	0,85	1,7 Mbps
11 Mbps	0,56	6,19 Mbps

Glossaire des termes clés

• Liaison point-à-point : connexion directe entre un émetteur et un récepteur.
• Liaison multipoint : support partagé entre plusieurs équipements.
• ALOHA : protocole d’accès aléatoire où les stations transmettent librement, avec retransmission en cas de collision.
• Slot (créneau) : intervalle de temps fixe utilisé dans ALOHA slotté pour synchroniser les transmissions.
• CSMA : méthode d’accès multiple avec écoute du canal avant émission.
• CSMA/CD : CSMA avec détection de collision et arrêt immédiat de l’émission en cas de collision.
• Binary Exponential Backoff (BEB) : algorithme d’attente aléatoire exponentielle après collision pour éviter les retransmissions simultanées.
• CSMA/CA : CSMA avec évitement de collision, utilisé dans les réseaux Wi-Fi.
• RTS/CTS : mécanisme de réservation pour éviter le problème des stations cachées.
• NAV (Network Allocation Vector) : temporisateur indiquant la durée pendant laquelle une station doit s’abstenir de transmettre.
• DIFS, SIFS : intervalles de temps entre trames pour gérer l’accès au canal.

Points clés à retenir

• Les supports partagés nécessitent des méthodes d’accès pour gérer les collisions et optimiser l’utilisation du canal.
• Le protocole ALOHA est simple mais peu efficace, amélioré par la version slottée.
• CSMA réduit les collisions en écoutant le canal avant d’émettre, mais ne les élimine pas totalement.
• CSMA/CD détecte les collisions pendant l’émission et arrête rapidement la transmission pour économiser la bande passante.
• L’algorithme BEB permet de gérer efficacement les retransmissions après collision.
• Dans les réseaux Wi-Fi, CSMA/CA et les mécanismes RTS/CTS permettent d’éviter les collisions, notamment dues aux stations cachées.
• Le débit réel dans IEEE 802.11 est inférieur au débit nominal à cause des overheads et des mécanismes de contrôle d’accès.