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.
-
Expliquer le raisonnement de Julie.
Détailler en particulier la position des en-têtes SMTP
dans un paquet IP.
-
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 ?
-
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.
-
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.
-
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 ?
-
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.
-
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.
-
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.
-
En utilisant la question 3, calculer la valeur minimale
de τ pour que le protocole fonctionne correctement.
-
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).
-
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 ?
-
Schématiser ces paquets d'information reçus par A,
et expliquer comment ce routeur construit
sa table de routage.
-
Quelle est la difficulté principale à résoudre pour
rendre cet algorithme opérationnel ?
|
|
Corrigé
1. Protocoles
-
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.
-
Les intermédiaires sont les serveurs de courrier qui ont
relayé l'expédition du message.
-
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
-
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.
-
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.
-
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).
-
-
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.
-
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.
-
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
-
A reçoit des paquets d'information, à intervalles réguliers
(par exemple tous les quarts d'heures), de tous
les noeuds du réseau.
- Chaque paquet d'information décrit les liens
du noeud émetteur (et non sa table de routage complète).
Schématiquement :
Source : B
|
Source : C
|
Source : D
|
Source : E
|
Source : F
|
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.
-
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.