Protocoles d’accès aux réseaux locaux de PC

Dans un établissement d’une entreprise, les micro-ordinateurs sont connectés à un réseau (le " réseau local de PC " ou RLPC ; en anglais LAN pour " Local Area Network "). Ces micro-ordinateurs peuvent sur le RLPC communiquer entre eux, avec des serveurs de mémoire et de traitement, des imprimantes, des routeurs (serveurs de communication) leur permettant d’accéder au reste du monde.

Pour faire communiquer des ordinateurs, on peut imaginer une commutation de circuit comme pour le téléphone : la communication entre deux ordinateurs aurait lieu sur un circuit établi et réservé à la demande.

Des raisons économiques militent cependant pour d’autres choix qui ont donné naissance à des réseaux comme " Ethernet " ou " Token Ring ". Leur principe est que tous les ordinateurs émettent leurs trames sur un même canal de transmission, et que les destinataires reconnaissent les trames qui les concernent.

Les ordinateurs qui communiquent sur un RLPC sont alors dans la même situation que des personnes placées dans une même pièce et entretenant plusieurs conversations à la fois. Les protocoles se distinguent par la façon dont ils règlent les problèmes que cela pose : comment distribuer le droit à la parole ? comment faire si deux personnes parlent ensemble, ce qui empêche de comprendre ce qu’elles disent ? peuvent-elles continuer à parler lorsque cette " collision " se produit, ou doivent-elles se taire dès qu’elles s’aperçoivent du problème ? les performances permises par chaque protocole dépendent des règles adoptées.

Largeur de bande, débit utile et " overhead "

Le canal de transmission se caractérise par sa " largeur de bande ", qui s’exprime dans le cas d’un signal numérique par un débit en bits ou en octets par seconde(1). Sur un réseau Ethernet, le débit le plus courant est de 10 Mbit/s (mais nous verrons que des versions plus rapides existent).

Selon le protocole, une trame peut mesurer de 72 à 1518 octets. La durée d’émission de la trame est fonction inverse du débit sur le réseau. Le " débit utile " est égal au nombre de bits que le réseau peut transmettre par seconde sans collision : c’est une fraction du débit total. Pour calculer la durée d’un transfert de fichier il faut soustraire à ce débit utile l’" overhead " provoqué par le découpage du fichier en trames ainsi que par l’adjonction au contenu utile des adresses et contrôles. De tout cela découle que le débit utilisable pour transporter du contenu n’est qu’une fraction du débit physique offert par le réseau. Cette fraction sera d’autant plus élevée que le protocole est plus performant.

On peut représenter mathématiquement les performances de chaque protocole en partant des lois probabilistes des files d’attente. Appelons " durée de trame " la durée (fonction inverse du débit) de l’émission d’une trame par un ordinateur, et notons G le nombre moyen de trames émises pendant une durée de trame. Supposons que le nombre des trames émises pendant une durée de trames obéit à la loi de Poisson, qui rend compte des processus d’arrivée dans une file d’attente. La probabilité que le nombre des trames émises pendant une durée de trames soit égal à k est alors :

(1) P(k) = G^k e^–G / k!

Nous présenterons ci-dessous les deux protocoles de transmission sur réseau local qui ont été historiquement les premiers : " Aloha " et " Aloha discrétisé ". Etant simples, ils ont l’avantage de se représenter facilement sous forme mathématique ; la démarche qui a permis de passer du premier au second est un bon exemple du type de raisonnement que font les concepteurs de protocoles.

Nous présenterons ensuite les protocoles qui leur ont succédé et qui sont utilisés aujourd’hui.

Aloha

Le premier protocole de réseau local, nommé " Aloha ", a été mis au point en 1970 par Abramson à l’université d’Hawaï. Il voulait assurer la communication entre des établissements de l’université situés sur des îles éloignées les unes des autres.

Le principe de ce protocole est que tous les ordinateurs émettent en même temps, reçoivent en même temps, donc communiquent en même temps sur la même bande de fréquence. Il s’agit donc d’une conversation à plusieurs, principe opposé à celui de la commutation qui procède en allouant à chaque conversation des ressources cloisonnées les unes par rapport aux autres.

L’émetteur découpe le message en trames comportant l’adresse du récepteur et un numéro d’ordre. Les ordinateurs reçoivent toutes les trames émises sur le réseau et trient celles qui leur sont destinées en lisant les adresses. Le destinataire reconstitue le message en ouvrant ces trames pour en extraire le contenu et le ranger dans l’ordre après celui des trames précédentes.

Cependant si deux ordinateurs émettent une trame en même temps, il y a collision : le signal émis dans la bande de fréquence est incompréhensible. Il faut alors réémettre.

En supposant que le nombre d’ordinateurs soit grand, la probabilité pour qu’il n’y ait pas de trame émise pendant la durée t est P(0). Il résulte de (1) que :

(2) P(0) = e^–G

La probabilité pour que deux événements indépendants se produisent étant égale au produit de leurs probabilités, la probabilité pour qu’il n’y ait pas de trame émise pendant deux durées t successives est [P(O)]², soit e^–2G.

Notons S le nombre moyen de trames " utiles ", c’est-à-dire émises sans collision. Comme il y a en moyenne G trames émises par durée de trame, on a :

(3) S = Ge^–2G

La forme de cette fonction est indiquée par le graphique ci-dessous ; S atteint son maximum, égal à 0,18, pour G = 0,5.

Rendement du protocole Aloha

Cette fonction mérite un examen attentif. Lorsque G est très petit, c’est-à-dire lorsque le nombre de trames émises par durée de trame est très faible, S est égal à G : le réseau n’étant pas encombré, les trames passent sans collision.

Si G croît, la probabilité des collisions augmente. S devient inférieur à G.

Le maximum de S est atteint lorsque G = 0,5, c’est-à-dire lorsque les ordinateurs émettent en moyenne une trame pour deux durées de trames. Alors S = 0,18 : en moyenne seules 36 % (= 0,18 / 0,50) des trames émises passent sans collision. Le nombre de trames utiles par durée de trame étant 0,18, le réseau peut véhiculer des données pendant 18 % du temps d’utilisation. Ce taux de 18 % est un maximum : le débit disponible pour le transport des données est égal au plus à 18 % du débit physique du réseau.

Si G croît au delà de 0,5, le nombre de collisions croît encore et le nombre de trames utiles décroît. Pour des valeurs importantes de G, S est très faible : le nombre de collisions est tellement grand que le nombre des trames utiles devient très petit.

NB : certains s’étonnent que S ne devienne pas nul lorsque G > 1, puisque alors il y a plus d’une trame émise par durée de trame. G est un nombre moyen, et pendant certaines durées de trame il peut y avoir moins d’une trame émise même si G > 1.

Aloha discrétisé

En 1972, Roberts mit au point une version perfectionnée du protocole Aloha : une horloge installée sur le réseau émet un signal à la fin de chaque durée de trame. Un ordinateur n’a le droit d’émettre qu’au reçu du signal de l’horloge : au lieu d’émettre une trame dès qu’il en a envie, il doit donc attendre le prochain signal d’horloge. Une collision se produira si deux ordinateurs ont eu envie d’émettre pendant une même durée de trame, car ils émettront ensemble au reçu du signal d’horloge.

On trouve dans ce cas :

(4) S = Ge^–G

Le maximum de S est atteint pour G = 1 et il vaut 0,37.

Rendement comparé d’Aloha et Aloha discrétisé

" Aloha discrétisé " est deux fois plus efficace qu’" Aloha ", puisqu’il permet d’utiliser 37 % du débit physique du réseau.

Carrier Sense Multiple Access (CSMA, 1975)

Avec Aloha, l’ordinateur émet une trame dès qu’il en ressent le besoin. Or il est possible d’éviter certaines collisions si l’on fait en sorte que chaque ordinateur écoute ce qui se passe sur le réseau avant d’émettre et évite d’émettre lorsque le réseau est occupé : c’est comme si, dans une conversation à plusieurs, la règle était que lorsque quelqu’un parle les autres se taisent.

On distingue plusieurs types de protocoles CSMA, tous plus efficaces que les protocoles Aloha :

CSMA persistant 

L’écoute est continue, et l’ordinateur émet dès que le réseau est disponible. Ce protocole présente toutefois un défaut : il y aura collision si deux ordinateurs ont attendu ensemble que le réseau soit disponible, parce qu’ils émettront chacun une trame en même temps.

CSMA non persistant

L’ordinateur qui a trouvé le réseau occupé reprend son écoute après un délai aléatoire. Ceci permet de corriger le défaut précédent.

CSMA p-persistant

Le temps est divisé en intervalles, comme " Aloha discrétisé ". Si un ordinateur veut émettre, il écoute pour savoir si le réseau est encombré. Il émet avec une probabilité p si le réseau est libre, et reporte l’émission à un intervalle suivant avec une probabilité 1 – p. Le processus continue jusqu’à ce que la trame soit émise.

Carrier Sense Multiple Access with Collision Detection (CSMA-CD)

Lorsqu’il y a collision, les dessins de trames se superposent dans l’espace hertzien et engendrent un signal incompréhensible pour les récepteurs. La détection de collision vise à limiter la durée de ce phénomène. L’émetteur écoute ce qui se passe sur le réseau, et si une collision se produit il interrompt immédiatement l’émission de la trame.

Un réseau sur lequel est utilisé un protocole CSMA-CD est donc nécessairement dans l’une des trois situations suivantes :

• Silence :
• une trame est en cours de transmission :
• une collision est en cours :

On peut donc représenter l’état d’un tel réseau dans le temps par un dessin du type suivant, qui montre que les intervalles de collision sont brefs :

Ethernet

Le réseau Ethernet utilise un protocole CSMA-CD.

Tout appareil connecté au réseau est appelé " nœud ", qu’il s’agisse d’un poste de travail, d’un serveur (de fichier, d’impression, de communication etc.) ou d’une imprimante.

Chaque nœud est équipé d’une carte Ethernet installée sur l’un de ses slots d’extension. Chaque carte a une adresse sur le réseau. Les cartes Ethernet des nœuds sont raccordées chacune par un coupleur (" transceiver ") à une ligne de transmission appelée " bus "(2).

Quand un nœud veut envoyer des données à un autre nœud, sa carte écoute le bus pour s’assurer qu’aucun signal n’est en cours de transmission ; si le réseau est silencieux, elle émet sa trame sur le bus.

La trame comprend les adresses de l’émetteur et du destinataire, les données à transmettre, enfin des octets servant à la détection d’erreur.

Chaque nœud examine l’adresse du destinataire. Si la trame ne lui est pas destinée, il l’ignore. Si la trame lui est destiné, il lit les données, vérifie qu’il n’y a pas eu d’erreur, et envoie un accusé de réception à l’émetteur qui peut alors envoyer la trame suivante.

Si deux nœuds émettent un message simultanément, la collision entre les trames provoque un signal d’interférence qui se propage sur le bus et qui est reconnu par les émetteurs. Le premier émetteur détectant la collision émet un signal signalant celle-ci aux autres nœuds. Les transmissions sont alors arrêtées ; les nœuds qui veulent émettre doivent attendre une durée aléatoire avant de chercher à émettre de nouveau. Le processus se répète jusqu’à ce qu’un nœud puisse émettre sa trame sans qu’il y ait collision.

Protocoles sans collision

Une autre astuce pour améliorer le rendement du réseau, c’est de faire en sorte qu’il ne puisse jamais se produire de collision. Le droit à émettre est un " jeton " qui circule entre les ordinateurs, et que chacun peut utiliser à tour de rôle : c’est comme si, dans une conversation à plusieurs, on faisait un " tour de table ". Le réseau doit alors supporter les délais dus à la circulation du droit à émettre.

Basic Bit-Map

On passe les ordinateurs en revue pendant une période de contention durant laquelle ceux qui souhaitent émettre sont notés. Puis chaque candidat à l’émission émet une trame, dans l’ordre des demandes.

Token Ring

Supposons les ordinateurs rangés sur un réseau circulaire. Un jeton passe d’un ordinateur à l’autre, et le détenteur du jeton a le droit d’émettre une trame s’il en a besoin.

Les nœuds du réseau Token Ring sont connectés par un adaptateur à un bus en forme de boucle. Un bref message, le jeton (" token "), circule continuellement sur cette boucle. Chaque adaptateur lit le jeton à son passage.

Le réseau ne peut transporter qu’un seul message à la fois. Le nœud qui veut émettre modifie le code du jeton pour signaler qu’il est utilisé et lui ajoute une trame comportant l’adresse du destinataire plus quelques octets servant à la détection d’erreur. Pour éviter la dégradation du signal due à la transmission, chaque nœud comporte un répéteur régénérant la trame au passage.

Chaque nœud examine le jeton lorsqu’il le reçoit pour lire l’adresse du destinataire. Le nœud à qui la trame est destinée en fait une copie et la renvoie sur le réseau. La trame revient à l’émetteur qui la supprime et remet en circulation un jeton signalant que le réseau est libre.

Token Bus

Un protocole analogue peut être utilisé même si les ordinateurs ne sont pas rangés en cercle : il suffit que le jeton passe d’un ordinateur à l’autre selon un ordre régulier (" Token Bus ").

Domaine d’utilisation des divers protocoles

Ethernet a été inventé par Robert Metcalfe et David Boggs chez Xerox en 1973. Sa version 1 a été mise au point par Xerox, Intel et Digital en 1980 et utilisée par l’industrie aéronautique : Boeing a monté sur cette base son réseau TOP (" Technical and Office Protocol ").

Cependant sur un réseau Ethernet la durée d’attente d’une trame est variable puisqu’elle dépend d’une loi de probabilité. Le caractère aléatoire du délai d’émission n’est pas gênant dans l’industrie aéronautique, ni dans les applications bureautiques où la production ne supporte pas des contraintes strictes de temps réel. Par contre elle est gênante dans l’industrie automobile où ce sont des automates qui communiquent et où les contraintes de temps réel sont fortes.

General Motors avait besoin de majorer les délais de transmission des commandes vers les robots. La technique du bus à jeton a été mise au point pour éviter les collisions et maîtriser les délais (réseau MAP, pour " Manufacturing Automation Protocol ").

Enfin IBM a mis au point l’anneau à jeton Token Ring en 1985

Ces trois techniques ont été proposées aux organismes de normalisation qui n’ont pas voulu choisir entre elles puisqu’elles répondaient à des besoins différents. Ils les ont donc laissé cohabiter. On utilise donc aujourd’hui ces trois protocoles sur les RLPC :

• Ethernet, norme IEEE 802.3 de 1983 (origine : Xerox, puis DEC),
• Bus à jeton (Token Bus), norme IEEE 802.4 (origine : General Motors)
• Anneau à jeton (Token Ring), norme IEEE 802.5 (origine : IBM).

En pratique Ethernet s’impose aujourd’hui sur les RLPC à utilisation bureautique, Token Ring ou Token Bus étant utilisés pour des applications industrielles.

___________