Université BORDEAUX 1 U.F.R. Mathématiques et Informatique
Epreuve de J.Bétréma 26 janvier 2001


Maîtrise d'Informatique
Télé-informatique

Durée: 2 heures
Tous documents interdits.

Avertissement : il n'est pas recommandé de chercher forcément à tout traiter : des réponses superficielles rapportent peu de points.

Un corrigé est disponible en fin de document.

1. Protocoles

Robert, passionné d'informatique, est tout fier de montrer à Julie qu'on peut, par des manipulations savantes du lecteur de courrier, afficher l'intégralité des en-têtes d'un message, par exemple :
Received: from equinoxe.math.unicaen.fr (equinoxe.math.unicaen.fr [193.55.129.28])
	by batman.labri.u-bordeaux.fr (8.8.7/8.8.7) with ESMTP id NAA12850;
	Tue, 16 Jan 2001 13:58:52 +0100 (MET)
Received: from soir.unicaen.fr (soir.math.unicaen.fr [193.55.129.52])
	by equinoxe.math.unicaen.fr (Postfix) with SMTP
	id B02E510F02; Tue, 16 Jan 2001 13:54:58 +0100 (CET)
Received: by soir.unicaen.fr (SMI-8.6/SMI-SVR4)
	id NAA16632; Tue, 16 Jan 2001 13:54:56 +0100
[etc.]
"Tu vois, dit-il à Julie, tu peux ainsi voir tous les routeurs IP traversés par ton email !" Julie, plus réfléchie, ne répond rien, mais pense que Robert n'a rien compris aux protocoles et à leur empilement.
  1. Expliquer le raisonnement de Julie. Détailler en particulier la position des en-têtes SMTP dans un paquet IP.
  2. Qui sont les intermédiaires (puisque ce ne sont pas les routeurs IP) qui ont ajouté au message original les trois en-têtes ci-dessus ?
  3. Détailler les champs de l'en-tête d'un paquet IP que vous êtes capables d'expliquer de mémoire.

2. Collisions

On considère un réseau local 802.3 (Ethernet), dans lequel le signal électrique se propage à la vitesse de 200 000 km/sec, et de débit 100 Mbits/sec. La station A commence à émettre une trame à l'instant t0 = 0.
  1. Soit une station B, distante de 200 mètres de A ; cette station peut commencer à son tour à émettre jusqu'à l'instant t1 = 1 μs. Expliquer pourquoi.
  2. On suppose que B commence effectivement à émettre à l'instant t1 - ε ; à quel instant t2 la station A détectera-t-elle une collision ? Combien d'octets a-t-elle transmis ?
  3. Sachant que 64 octets est la taille minimale d'une trame 802.3, on en déduit une distance maximale entre deux stations, pour que le protocole fonctionne correctement. Expliquer pourquoi, et calculer cette distance maximale.
  4. Le temps est divisé en tranches de durée τ , et on rappelle qu'après détection d'une collision, une station interrompt immédiatement sa transmission, laisse s'écouler aléatoirement 0 ou 1 tranche de temps (période dite de contention), puis réémet sa trame dès que le canal est libre.
    1. Montrer que si la durée τ d'une tranche de temps est légèrement inférieure à 2 μs, il existe un scénario où les stations A et B choisissent un nombre aléatoire différent (parmi 0 et 1), et où pourtant les trames réémises entrent à nouveau en collision.
    2. En utilisant la question 3, calculer la valeur minimale de τ pour que le protocole fonctionne correctement.
    3. On suppose τ fixé à la valeur calculée à la question précédente (valeur qui figure dans la norme 802.3) ; il y a donc exactement une chance sur deux pour que se produise une nouvelle collision entre les trames réémises par A et B. Expliquer l'algorithme utilisé dans ce cas, et calculer la probabilité pour qu'au moins quatre émissions (y compris la tentative initiale) soient nécessaires au bon acheminement des trames, dans le cas où seules les stations A et B sont actives.

3. Correction d'erreurs

On considère le code de Hamming qui ajoute à un message de 4 chiffres binaires b1 , b2 , b3 , b4 les 3 chiffres de contrôle c1 , c2 , c3 définis par :

On reçoit le mot 1,0,0,1,0,0,1 et on suppose que le canal de transmission a déformé au plus un chiffre binaire. Quel est le message qui a été émis ? Même question si l'on reçoit 1,1,0,1,1,0,1.

4. Routage

On considère le réseau ci-contre, et on suppose qu'on utilise le routage par informations sur les états des liens (algorithme utilisé sur Internet).
  1. De quels noeuds du réseau (routeurs) A reçoit-il des paquets d'information pour construire sa table de routage ? Quand reçoit-il ces paquets ?
  2. Schématiser ces paquets d'information reçus par A, et expliquer comment ce routeur construit sa table de routage.
  3. Quelle est la difficulté principale à résoudre pour rendre cet algorithme opérationnel ?

Corrigé

1. Protocoles

  1. Le protocole SMTP est situé deux couches au-dessus du protocole réseau IP. Un courrier électronique est encapsulé, pendant son transport, dans un paquet TCP, lui-même encapsulé dans un paquet IP. Un routeur IP n'a donc pas accès à l'en-tête SMTP du message, et inversement, lorsque le message est remis à un agent de courrier, il a été débarrassé de ses enveloppes TCP et IP.
  2. Les intermédiaires sont les serveurs de courrier qui ont relayé l'expédition du message.
  3. L'en-tête standard (ie. sans option) d'un paquet IP comporte cinq mots de 32 bits, dont deux pour les adresses source et destination. Les autres champs importants indiquent la version du protocole, la taille de l'en-tête, la fragmentation, et la durée de vie du paquet. Dans IPv4, un champ contient un code détecteur d'erreur, calculé uniquement sur l'en-tête.

2. Collisions

  1. Le signal émis par la station A n'atteint B qu'à l'instant t1 = 1 μs. Jusque là, le bus apparaît libre pour B, qui peut donc émettre.
  2. La station A détectera la collision à l'instant t2 = t1 - ε + t1, puique le temps de propagation du signal de B vers A est égal au temps t1 de propagation du signal de A vers B. Soit t2 = 2 t1 - ε = 2 - ε μs.

    Une station transmet 100 bits par μs, donc A a tranmis un peu moins de 200 bits avant de détecter la collision, soit un peu moins de 25 octets.

  3. Le protocole exige, pour fonctionner correctement, qu'une collision soit détectée par une station émettrice avant que la totalité de la trame soit émise. 64 octets, soit 512 bits, sont émis en 5.12 μs, et la question précédente montre que le temps nécessaire à la détection d'une collision est au pire celui d'un aller-retour du signal entre les deux stations les plus éloignées. La distance maximale est donc de 512 mètres (résultat numérique qu'on peut déduire sans effort de la question précédente : si une distance de 200m permet l'émission de 200 bits avant détection d'une collision, une distance de 512m permet l'émission de 512 bits).
    1. B détecte la collision à l'instant t1 = 1 μs, et A à l'instant t2 = 2 - ε μs. Si A choisit de réémettre immédiatement, le signal émis par A arrive en B à l'instant t3 = 3 - ε μs, supérieur à t1 + τ si τ < 2 - ε μs. Donc B, dans ce cas, croit le bus libre après avoir laissé s'écouler une tranche de temps, et l'on se retrouve dans la situation de la question 1.
    2. Si deux stations sont séparées de 512m (distance maximale calculée à la question 3), la question précédente et une règle de trois montrent que la valeur minimale pour τ (valeur qui assure qu'un choix aléatoire différent, avant retransmission, de la part des deux stations, évite une nouvelle collision) est de 5.12 μs.
    3. Il y a une chance sur deux pour que se produise une nouvelle collision entre les trames réémises par A et B ; dans ce cas, chaque station laisse s'écouler aléatoirement 0, 1, 2 ou 3 tranches de temps avant de réémettre (si le bus est libre). La probabilité d'une nouvelle collision est donc de 1/4. Finalement, la probabilité pour qu'au moins quatre émissions (y compris la tentative initiale) soient nécessaires au bon acheminement des trames, est de 1/2 (échec de la première réémission) * 1/4 (échec de la seconde réémission), soit 1/8.

      Note : cette formulation de la solution suppose qu'on est dans le scénario de la question 2, et donc que la première émission a provoqué une collision. On peut aussi appeler p la probabilité (inconnue) de cette collision initiale, et répondre p/8. D'autre part si on interprète la valeur demandée comme la probabilité d'avoir au moins quatre retransmissions, la réponse devient 1/2*1/4*1/8=1/64, car la probabilité d'échec de la troisième retransmission est 1/8.

3. Correction d'erreurs

On reçoit le mot b1b2b3b4c1c2c3 = 1001001, et on recalcule les chiffres de contrôle, soit :

c'1 = b2 + b3 + b4 = 0 + 0 + 1 = 1

c'2 = b1 + b3 + b4 = 1 + 0 + 1 = 0

c'3 = b1 + b2 + b4 = 1 + 0 + 1 = 0

Le syndrome (différence entre les chiffres de contrôle recalculés et les chiffres de contrôle reçus) vaut donc 1,0,1 ; comme c'est la seconde colonne de la matrice, c'est le chiffre b2 qui est faux, le message émis est 1101.

Si l'on reçoit 1101101, les chiffres de contrôle recalculés valent 001 (voir cas précédent !), donc le syndrome vaut 1,0,0, ce qui signifie que l'erreur porte sur le chiffre de contrôle c1. Le message émis est le même que précédemment.

4. Routage

  1. A reçoit des paquets d'information, à intervalles réguliers (par exemple tous les quarts d'heures), de tous les noeuds du réseau.
  2. Chaque paquet d'information décrit les liens du noeud émetteur (et non sa table de routage complète). Schématiquement :
    Source : B
    LienCoût
    A 4
    C 2
    F 6
    Source : C
    LienCoût
    B 2
    D 3
    E 1
    Source : D
    LienCoût
    C 3
    F 7
    Source : E
    LienCoût
    A 5
    C 1
    F 8
    Source : F
    LienCoût
    B 6
    D 7
    E 8

    La station A utilise ces informations pour reconstruire la topologie du réseau, et calcule sa table de routage par un algorithme de plus court chemin.

  3. Cet algorithme est beaucoup plus robuste que celui où une station exploite les tables de routage des ses voisines. Il demande par contre plus de calculs de la part de chaque station, et la difficulté principale à résoudre pour rendre cet algorithme opérationnel est le contrôle de la diffusion par inondation des paquets d'information. A cet effet, les paquets comportent un champ "âge", qui permet de les éliminer du réseau après une période donnée, et de faire le tri entre informations fraîches et informations périmées.