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


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

Durée: 3 heures
Tous documents interdits.

Attention: ne pas chercher à tout traiter. Le sujet est long pour vous permettre de faire un choix ! Une question traitée avec réflexion et bien rédigée rapporte beaucoup plus de points que deux questions bâclées. Une réponse superficielle est souvent fausse ou hors sujet, et ne rapporte aucun point.

Un corrigé est disponible en fin de document.

1. USB

La spécification USB (Universal Serial Bus, cf. http://www.usb.org/developers/docs/ ) décrit le protocole utilisé par un contrôleur USB (situé sur l'ordinateur hôte) pour lire des données émises par un périphérique (device). Le principe de base est le suivant:
  1. Le contrôleur émet (à destination du périphérique) un jeton (token) de type IN (input).
  2. Le périphérique répond par un paquet de données, de type DATA0 (paquet pair) ou DATA1 (paquet impair), de taille maximale 1024 octets.
  3. Le contrôleur émet un acquittement (type ACK).

Cette suite de trois échanges constitue une transaction (bulk transaction, dans le jargon USB). Le contôleur peut enchaîner autant de transactions que nécessaire (penser par exemple à la lecture des données en provenance d'un scanner).

Le premier octet de chaque paquet (jeton, données ou acquittement) est son PID, constitué du type du paquet, codé sur 4 bits, et de 4 bits redondants, inverses des précédents (il y a 15 types de paquets USB, mais cet exercice n'en utilise que 4: IN, DATA0, DATA1 et ACK). Voici la structure des paquets considérés dans cet exercice:

Les deux parties de cet exercice sont indépendantes.

Partie 1

Si le contrôleur, après émission du jeton, reçoit un paquet autre qu'un paquet de données valide (PID différent de DATA0 ou DATA1, ou bien CRC invalide), il l'ignore et redémarre la transaction, en émettant un nouveau jeton. D'autre part le contrôleur arme un temporisateur en début de transaction, et redémarre la transaction comme ci-dessus si le temporisateur expire (timeout).

Question 1.
Quel est l'événement qui peut provoquer l'expiration du temporisateur du contrôleur ?

Note : on suppose que le périphérique fonctionne correctement, et que la fonction invoquée possède des données à émettre; les autres cas (périphérique bloqué, pas de donnée disponible) sont prévus par le protocole, mais sortent du cadre de ce sujet.

Le périphérique garde en mémoire le paquet de données émis, jusqu'à réception d'un acquittement. S'il reçoit un nouveau jeton IN sans avoir reçu d'acquittement, il réémet le même paquet. Note : en l'absence d'acquittement, le périphérique ne prend jamais l'initiative d'une retransmission, il attend un nouveau jeton de la part du contrôleur.

Question 2.
Expliquer dans quelles conditions il peut arriver que le périphérique retransmette un paquet de données pourtant déjà reçu (correctement) par le contrôleur (duplication de paquet).

La question précédente montre que le contrôleur doit être en mesure de distinguer un paquet dupliqué et de resynchroniser les échanges. Le protocole est le suivant:

Question 3.
Quel doit être le comportement du contrôleur lorsqu'il reçoit un paquet de données dupliqué (par exemple de type DATA0 alors que CT=1) ?
Question 4.
Vérifier le bon fonctionnement du protocole en cas de "perte" d'un paquet de données, puis en cas de "perte" d'un acquittement. Dans chacun des cas, on commencera par indiquer précisément ce qui peut provoquer la "perte" du paquet.
Question 5.
Construire un scénario montrant qu'un tel protocole serait défaillant si le périphérique prenait l'initiative d'une retransmission, en l'absence d'acquittement (expiration d'un temporisateur) -- ce n'est pas le cas d'USB.

Partie 2

Le code détecteur d'erreurs utilisé à l'intérieur d'un jeton est un code cyclique, de polynôme générateur

g(x) = x5 + x2 + 1

Pour répondre aux questions suivantes, on pourra utiliser le fait que ce polynôme est irréductible, ou bien commencer par calculer explicitement une table des valeurs utiles de xi modulo g(x) (c'est un peu plus long, mais pas excessivement).

Question 6.
Montrer que ce code détecte toutes les erreurs simples.
Question 7.
Montrer que ce code détecte toutes les erreurs doubles dans un jeton (on rappelle qu'il y a seulement 11 bits à protéger).
Question 8.
Donner un exemple d'erreur triple non détectée.

2. TCP

On considère une session TCP unidirectionnelle, pendant laquelle l'extrémité A émet des segments, reçus et acquittés par l'extrémité B. Pour simplifier l'énoncé, on suppose que tous les segments sont de même taille, et sont numérotés séquentiellement à partir de zéro.

Question 1.
Expliquer comment sont numérotés en réalité les segments lors d'une vraie session TCP.

On rappelle que l'émetteur utilise une fenêtre coulissante, de taille

min (rw, cw) (rw = receiver window, cw = congestion window)

et l'on suppose dans la suite que rw garde une valeur élevée, si bien que la taille de la fenêtre vaut cw.

Question 2.
Comment l'émetteur connaît-il la valeur de rw ? Dans quelles conditions cette valeur reste-t-elle élevée?

L'algorithme de calcul de cw permet à l'émetteur de s'adapter au débit (a priori inconnu) du réseau. Dans cet exercice, le réseau est modélisé par une file d'attente, où entrent les segments émis par A, et d'où sortent les segments délivrés à B, au rythme d'un par unité de temps (qui peut être par exemple le dixième de seconde). Cette file d'attente est de longueur 4, tout segment entrant supplémentaire est détruit. Lorsque le réseau délivre un segment au récepteur B, à l'instant t, celui-ci émet un accusé de réception (ACK), dont le numéro est égal à celui du prochain segment attendu, et qui parvient à A à l'instant t+1. On ne considère que des scénarios sans perte d'accusé de réception.

Dans la première phase de l'algorithme, cw est initialisé à 2, et est incrémenté lors de chaque arrivée d'un acquittement positif, c'est-à-dire d'un accusé de réception dont le numéro est supérieur au précédent. Voici donc le début du scénario (dans chaque ligne, les événements sont ordonnés chronologiquement de gauche à droite: l'accusé de réception est reçu, puis la fenêtre est incrémentée, puis les segments sont émis, etc.):


Temps Numéro ACK reçu cw = taille fenêtre Segment(s) émis par A Segment reçu par B Numéro ACK émis File d'attente
0 - 2 0, 1 - - 0, 1
1 - 2 - 0 1 1
2 1 3 2, 3 1 2 2, 3
3 2 4 4, 5 2 3 3, 4, 5
Question 3.
Expliquer (par un argument simple) pourquoi A émet exactement deux segments à chaque arrivée d'un acquittement.
Question 4.
Quels sont le numéro et la date d'émission du premier segment détruit (par saturation de la file d'attente, de longueur maximale 4) ?
Question 5.
Poursuivre la simulation jusqu'à réception par A d'un ACK dupliqué, c'est-à-dire ayant même numéro que le précédent. En l'absence de temporisateur, que se passe-t-il ensuite ?

En fait A arme un temporisateur pour chaque segment émis, et on suppose, toujours pour simplifier, que la valeur du temporisateur est égale à

2 * rtt + 0.5

où rtt (round trip time) désigne la dernière mesure obtenue par A du temps d'aller-retour (différence entre la date d'arrivée de l'acquittement, et la date d'émission du segment).

Question 6.
Expliquer l'algorithme (non simplifié) de calcul de la valeur du temporisateur dans la réalité.
Question 7.
Construire un tableau donnant, pour chaque segment de numéro compris entre 0 et 11, sa date d'émission, la valeur du temporisateur, et la date d'acquittement. A quel instant un temporisateur expire-t-il, et quels sont le numéro et la date d'émission du segment concerné ?

Note: à l'instant 0 le temporisateur est initialisé à une valeur élevée (par exemple 10), sans importance pour cet exercice.

Après expiration du temporisateur d'un segment (timeout), l'émetteur désarme tous les temporisateurs, ramène la valeur de cw à 1, retransmet le segment, et fixe la valeur d'un seuil à la moitié de la valeur atteinte par cw lors du timeout. Lorsque cw atteint plus tard la valeur du seuil, il faut cw acquittements positifs (au lieu d'un seul) pour incrémenter cw d'une unité.

Question 8.
Poursuivre dans ces conditions la simulation à partir du timeout de la question précédente. Quels sont le numéro et la date d'émission du premier segment détruit dans cette nouvelle phase? A quel instant le timeout suivant survient-il, et quels sont le numéro et la date d'émission du segment concerné? Expliquer en quoi l'algorithme employé (incrémentation lente de la taille de la fenêtre, une fois le seuil atteint) rend l'émetteur A plus efficace qu'avant: comparer les situations lors du premier timeout (question précédente) et du second timeout (cette question).

Note: il est normal que la simulation obtenue diverge de celle de la question 5, obtenue sans prendre en compte le temporisateur.

3. Client/Serveur

DarkVador, hacker/geek renommé de la maîtrise informatique de Bordeaux, a réussi à se procurer la correction du sujet de l'examen Télé-informatique. Tout fier de sa trouvaille, il aimerait la diffuser discrètement à ses petits camarades, mais il ne fait aucune confiance à scp (c'est un hacker...). Pour cela, il leur a dit ceci à la sortie d'un cours: connectez-vous sur ma machine zx81.supercomputer.fr en scannant les ports actifs entre 1 et 5000 avec pour mot de passe TiTiTi. Sur le bon port, elle vous enverra la réponse Solution, puis le contenu de la solution, caractère par caractère.

BlueMoon est très impatient de récupérer la solution: il a commencé à écrire le programme suivant (les en-têtes include ont été enlevés):

static struct sockaddr_in adresse_distante;
static char
  buf [1024],
	machine_distante [] = "zx81.supercomputer.fr";

int main (void) {
    int sd, port_distant;
    struct hostent *host = gethostbyname (machine_distante);
		
    adresse_distante.sin_family = AF_INET;
    memcpy (&adresse_distante.sin_addr.s_addr,
      host->h_addr, host->h_length);
    for (port_distant = 1; port_distant < 5000; port_distant++) {
        sd = socket (PF_INET, SOCK_STREAM, 0);
        adresse_distante.sin_port = htons (port_distant);
        if (connect (sd, (struct sockaddr *) &adresse_distante,
          sizeof (struct sockaddr_in)) != -1) {
            write (sd, "TiTiTi", 6);
            read (sd, buf, 8);
            if (strncmp (buf, "Solution", 8) == 0) {
                // sauvegarde du corrigé dans un fichier
                // [...] code supprimé
                close (sd);
                return 1;
            }
        }
        close (sd);
    }
    return 0;
}
Question 1.
Expliquer ce que retourne la fonction gethostbyname, et décrire brièvement comment elle obtient ce résultat.
Question 2.
Ce programme lit et écrit dans la même socket: est-ce correct ?
Question 3.
Que se passe-t-il si le serveur a un port smtp actif ?

DarkVador ne veut pas que son serveur écoute en permanence sur le même port, pour ne pas risquer d'être repéré par un des enseignants du module. Ainsi si une machine demande à se connecter sur le port en écoute, sans donner le bon mot de passe, alors le serveur doit changer immédiatement de port. Si le mot de passe est correct, le serveur renvoie le mot Solution, puis le contenu du fichier texte solutionExam.txt.

Question 4.
Ecrire le squelette du serveur. Attention: seul un programme très clairement écrit et commenté rapportera des points. Il est hors de question, dans les conditions de l'examen, d'écrire un programme complet; indiquer seulement sa structure générale, et commenter clairement les instructions concernant les sockets.

Corrigé

1. USB

Partie 1

Question 1.
Le temporisateur du contrôleur expire lorsque le jeton est perdu (c'est-à-dire est altéré par une erreur de transmission); dans ce cas le périphérique ne répond pas.

Note 1 : lorsque c'est le paquet de données, émis en réponse par le périphérique, qui est altéré, le contrôleur reçoit un paquet invalide, et l'énoncé indique qu'il redémarre immédiatement la transaction, sans attendre l'expiration du temporisateur. C'est une particularité du protocole USB, d'autre protocoles ignorent systématiquement les paquets invalides (qui ne provoquent donc aucune réaction).

Note 2 : le protocole USB est un protocole de liaison (couche 2), donc répondre à cette question que le temporisateur expire "si le réseau est encombré", ou "si le périphérique ne répond pas assez vite", est une faute grave (confusion avec la couche transport). Les caractéristiques physiques du bus USB sont parfaitement spécifiées, et les durées de temporisation sont adaptées aux délais de transmission qui découlent de ces caractéristiques physiques.

Question 2.
Le périphérique retransmet un paquet de données pourtant déjà reçu (correctement) par le contrôleur (duplication de paquet), lorsque l'acquittement est perdu, c'est-à-dire n'est pas parvenu intact au périphérique.
Question 3.
Lorsque le contrôleur reçoit un paquet de données dupliqué (par exemple de type DATA0 alors que CT=1), il doit ignorer son contenu, mais émettre un acquittement, pour faire basculer DT, et resynchroniser ainsi les échanges.
Question 4.
La "perte" d'un paquet résulte d'une erreur de transmission, qui entraîne soit l'invalidité du PID (les 4 derniers bits ne sont pas les inverses des 4 premiers), soit, dans le cas d'un paquet de données, l'invalidité du code détecteur d'erreurs. En cas de perte d'un paquet de données, le contrôleur reçoit un paquet invalide, réémet un jeton IN, et reçoit alors une copie du paquet, comme souhaité :
Perte d'un paquet de données, cliquer pour agrandir

En cas de perte d'un acquittement, le contrôleur reçoit (lors de la transaction suivante) un paquet dupliqué, ignore son contenu, et réémet l'acquittement perdu :

Perte d'un acquittement, cliquer pour agrandir
Question 5.
Si le périphérique prenait l'initiative d'une retransmission, après expiration d'un temporisateur d'attente d'acquittement, le paquet de données retransmis pourrait "croiser" un nouveau jeton émis par le contrôleur, d'où une seconde retransmission qui pourrait à son tour "croiser" l'acquittement du paquet précédent; dans ce scénario le contrôleur et le périphérique restent désynchronisés :
Faille de protocole, cliquer pour agrandir

On peut objecter aussi, plus simplement, que des paquets ne peuvent "se croiser" (sans être altérés) que sur une liaison bidirectionnelle (full duplex), alors qu'un protocole basé sur des requêtes alternant avec des réponses peut fonctionner sur une liaison unidirectionnelle (half duplex).

Partie 2

Le code détecteur d'erreurs utilisé à l'intérieur d'un jeton est un code cyclique, de polynôme générateur

g(x) = x5 + x2 + 1

Comme le nombre de bits (adresse + CRC) est 16, il faut calculer les valeurs de xi modulo g(x), pour i compris entre 0 et 15. C'est facile, on multiplie à chaque fois la valeur précédente par x, et on remplace systématiquement x5 par x2 + 1, en effectuant toutes les additions modulo 2 :

1 x x2 x3 x4 x5 x6 x7 x8 x9
1 x x2 x3 x4 x2 + 1 x3 + x x4 + x2 x5 + x3 =
x3 + x2 + 1
x4 + x3 + x
x10 x11 x12 x13 x14 x15
x5 + x4 + x2 =
x4 + 1
x5 + x =
x2 + x + 1
x3 + x2 + x x4 + x3 + x2 x5 + x4 + x3 =
x4 + x3 + x2 + 1
x5 + x4 + x3 + x =
x4 + x3 + x2 + x + 1

Note mathématique : en élevant le dernier résultat au carré, on obtient :

x30 = x8 + x6 + x4 + x2 + 1 = (x3 + x2 + 1) + (x3 + x) + x4 + x2 + 1 = x4 + x

et en multipliant par x :

x31 = x5 + x2 = (x2 + 1) + x2 = 1

ce qui est normal, car le groupe des polynômes non nuls modulo g(x) comporte 31 éléments.

Question 6.
Une erreur simple (sur le bit numéro i) est toujours détectée, car les calculs préliminaires (ou un argument mathématique) montrent que xi modulo g(x) n'est jamais nul.
Question 7.
Une erreur double, portant sur les bits numéros i et j, est détectée à condition que

xi + xj modulo g(x)

ne soit pas nul ; or ce terme est nul si xi = xj modulo g(x), ce qui n'est pas vrai pour i et j distincts compris entre 0 et 15, d'après la table ci-dessus, qui montre que toutes les valeurs des xi sont distinctes.

Note 1 : les rares étudiants qui ont calculé les xi modulo g(x), comme le suggérait l'énoncé, se sont souvent contentés de 11 valeurs de i, alors qu'il faut poursuivre les calculs jusqu'à i = 15, car le bruit sur le bus peut altérer les bits de contrôle aussi bien que les bits de données !

Note 2 : beaucoup d'étudiants ont prétendu qu'un polynôme p(x) de poids pair ne peut pas être multiple de g(x), qui est de poids impair, car p(1) = 0 ne pourrait être multiple de g(1) = 1. Mais 0 est un multiple de 1 ! Certes 1 n'est pas multiple de 0, et l'argument est utilisé classiquement pour prouver qu'un polynôme générateur de poids pair permet de détecter toutes les erreurs de poids impair, mais 0 et 1 (pair et impair) ne sont pas interchangeables ici. D'ailleurs x31 = 1 modulo g(x), et donc une erreur double portant sur les bits 0 et 31 ne serait pas détectée; c'est la taille réduite de l'adresse (11 bits) qui rend le code utilisé efficace.

Question 8.
Une erreur simultanée sur les bits numéros 0, 2 et 5 (ou 1, 3 et 6, ou 2, 4 et 7, etc.) n'est pas détectée, par définition de g(x).

2. TCP

Question 1.
En réalité un segment TCP comporte le numéro (codé sur 32 bits) de son premier octet, et le numéro initial, lors de l'établissement de la connexion TCP, est choisi aléatoirement.
Question 2.
La valeur de rw est contenue dans l'en-tête de chaque segment émis par B, en particulier dans l'en-tête d'un accusé de réception. Elle reste élevée si le temps de traitement, par le destinataire, des segments reçus, est plus faible que le temps mis par le réseau pour délivrer les segments ; autrement dit si les segments sont délivrés rapidement à la couche au-dessus de la couche TCP. Dans ce cas, le buffer réservé aux segments reçus, mais pas encore traités, est toujours prêt à accueillir un nombre élevé de segments (ce buffer ne se remplit que si le débit du réseau augmente soudainement, ou si le destinataire B est accaparé par d'autres tâches, et dans ce cas B envoie des accusés de réception avec une valeur faible de rw, pour freiner l'émetteur).
Question 3.
A chaque arrivée d'un acquittement, l'émetteur A peut avancer sa fenêtre d'une unité, et donc émettre un nouveau segment, sans augmenter la charge du réseau, puisque l'acquittement reçu prouve qu'un segment a quitté le réseau. D'autre part dans cette partie de l'algorihtme (dite démarrage lent), l'arrivée d'un acquittement incrémente la taille de la fenêtre, et A est donc autorisé à émettre un second segment ; ce dernier par contre peut augmenter la charge du réseau, comme c'est le cas ici.
Question 4.
Suite du scénario :
Temps Numéro ACK reçu cw = taille fenêtre Segment(s) émis par A Segment reçu par B Numéro ACK émis File d'attente
3 2 4 4, 5 2 3 3, 4, 5
4 3 5 6, 7 3 4 4, 5, 6, 7
5 4 6 8, 9 4 5 5, 6, 7, 8
Le segment 9 est donc détruit après son émission à l'instant 5, car la file d'attente est pleine.

Note : certains étudiants ont pensé qu'à l'instant 4, après émission du segment 6, la file d'attente est pleine, et ne peut donc recevoir le segment 7 ; cette interprétation suppose qu'après émission des deux segments 6 et 7 par A, le segment 3 n'a pas encore quitté la file d'attente pour être délivré à B, ce qui est peu vraisemblable. Bien entendu, dans les conditions de l'examen, l'énoncé peut être considéré comme ambigü, et la réponse a été jugée correcte.

Question 5.
Suite de la simulation :
Temps Numéro ACK reçu cw = taille fenêtre Segment(s) émis par A Segment reçu par B Numéro ACK émis File d'attente
5 4 6 8, 9 4 5 5, 6, 7, 8
6 5 7 10, 11 5 6 6, 7, 8, 10
7 6 8 12, 13 6 7 7, 8, 10, 12
8 7 9 14, 15 7 8 8, 10, 12, 14
9 8 10 16, 17 8 9 10, 12, 14, 16
10 9 11 18, 19 10 9 12, 14, 16, 18
11 9 11 - 12 9 14, 16, 18
12 9 11 - 14 9 16, 18
13 9 11 - 16 9 18
14 9 11 - 18 9 -
15 9 11 - - - -

A l'instant 10, B reçoit le segment 10 au lieu du segment 9 attendu ; à l'instant 11, A reçoit donc un acquittement dupliqué, et n'émet aucun segment, puisque ni l'origine de la fenêtre ni sa taille ne sont modifiées.

Le phénomène se répète aux instants suivants, et la file d'attente se vide de ses paquets "inutiles". La connexion est alors bloquée : A garde les segments 9 à 19 dans sa fenêtre d'émission (de taille 11), et attend un acquittement positif ; B ne reçoit plus rien.

Note : certaines réalisations de TCP prévoient une retransmission après réception de trois acquittements dupliqués, ici le segment 9 serait donc réémis par A à l'instant 13.

Question 6.
En réalité, la valeur de rtt est estimée par un algorithme de vieillissement pondéré, qui consiste à mettre à jour en douceur cette estimation après chaque nouvelle mesure par :

rtt estimé := α (rtt estimé) + (1 - α) (rtt mesuré)

avec par exemple α = 7/8. D'autre part, par la même méthode, on estime l'écart moyen δ entre (rtt mesuré) et (rtt estimé) :

δ estimé := α (δ estimé) + (1 - α) | rtt mesuré - rtt estimé |

et la durée du temporisateur est fixée à :

(rtt estimé) + 4 (δ estimé)

Question 7.
Voici le tableau demandé :
Segment 0 1 2 3 4 5 6 7 8 9 10 11
Date émission 0 0 2 2 3 3 4 4 5 5 6 6
Temporisateur τ - - 4.5 4.5 6.5 6.5 4.5 4.5 6.5 6.5 6.5 6.5
Date d'acquittement 2 3 4 5 6 7 8 9 10 - - -

Par exemple pour calculer la valeur τ du temporisateur lors de l'émission du segment 8, on consulte sa date d'émission, soit 5, puis on considère la colonne dont le dernier élément ( ligne du bas ) vaut 5: c'est la quatrième colonne, qui indique qu'à l'instant 5 le segment 3, émis à l'instant 2, a été acquitté ; donc à l'instant 5, rtt = 5 - 2 = 3 d'où τ = 6.5 ; on trouverait de même rtt = 7 - 3 = 4 et τ = 8.5 pour le segment 12.

Ecrire que, pour le segment 8, rtt = 10 - 5 = 5 (date d'acquittement du segment 8 - date d'émission), et en déduire τ = 10.5, est absurde, car le temporisateur est armé lors de l'émission du segment, et à cet instant on n'en connaît pas la date d'acquittement ! On calcule τ à partir du dernier rtt mesuré, soit 3 (5 - 2 = date d'acquittement du segment 3 - date d'émission).

Ce tableau montre que, curieusement, c'est le temporisateur du segment 7 qui expire le premier, à l'instant 8.5 (alors que l'acquittement est tout près d'arriver, à l'instant 9). Cela montre au passage que le calcul de τ, qui ne tient compte dans cet exercice que du dernier rtt mesuré, est inadapté ; avec un algorithme correct (voir question précédente), ce serait le temporisateur du segment 9 (détruit à cause de la saturation du réseau) qui devrait expirer.

Note 1 : peu d'étudiants ont justifié leurs calculs, si bien que lorsque les résultats sont faux, il est impossible au correcteur de juger s'il s'agit d'une erreur de principe, ou d'une faute d'étourderie.

Note 2 : les rares étudiants qui ont remarqué que c'est le temporisateur du segment 7 qui expire le premier, ont bénéficié d'un important bonus.

Question 8.
Simulation obtenue en tenant compte du timeout survenu à l'instant 8.5, et en suivant à la lettre le calcul de la valeur τ du temporisateur :
Temps Numéro ACK reçu cw = taille fenêtre Segment(s) émis par A Segment reçu par B Numéro ACK émis File d'attente
5 4 6 8, 9
(τ = 6.5)
4 5 5, 6, 7, 8
6 5 7 10, 11
(τ = 6.5)
5 6 6, 7, 8, 10
7 6 8 12, 13
(τ = 8.5)
6 7 7, 8, 10, 12
8 7 9 14, 15
(τ = 8.5)
7 8 8, 10, 12, 14
8.5 - 1 7 (τ = 8.5) - - 8, 10, 12, 14
9 8 2 8, 9
(τ = 1.5!)
8 9 10, 12, 14, 8
10 9 3 10, 11
(τ = 2.5!)
10 9 12, 14, 8, 10
10.5 - 1 9 (τ = 2.5) - - 12, 14, 8, 10
11 9 1 - 12 9 14, 8, 10
12 9 1 - 14 9 8, 10
13 9 1 9 (τ = 2.5) 8 9 10, 9
14 9 1 - 10 9 9
15 9 1 - 9 10 -
15.5 - 1 9 (τ = 2.5) - - 9
16 10 2 10, 11
(τ = 1.5)
9 10 10, 11
etc.
Ce scénario illustre les ravages provoqués par l'expiration prématurée du temporisateur du segment 7 (instant 8.5) :

L'énoncé ne demandait pas la poursuite de la simulation au-delà du second timeout (instant 10.5), ici on va jusqu'à l'instant 16 pour montrer que le segment 9 est retransmis trois fois, et reçu deux fois par B !

Hélas ce scénario ne permet pas d'illustrer correctement l'algorithme TCP de prévention de congestion, avec ses deux phases séparées par un seuil (appliqué à la taille de la fenêtre). Voici un scénario corrigé, sans expiration prématurée de temporisateur (pour cela il faut lisser les variations de la durée de temporisation τ, comme c'est le cas en réalité, et supposer par exemple que les valeurs de τ aux instants 3, 4 et 5 sont respectivement 6.5, 5.5, 6.5 -- au lieu de 6.5, 4.5, 6.5) :

Temps Numéro ACK reçu cw = taille fenêtre Segment(s) émis par A Segment reçu par B Numéro ACK émis File d'attente
8 7 9 14, 15
(τ = 8.5)
7 8 8, 10, 12, 14
9 8 10 16, 17
(τ = 10.5)
8 9 10, 12, 14, 16
10 9 11 18, 19
(τ = 10.5)
10 9 12, 14, 16, 18
11 9 11 - 12 9 14, 16, 18
11.5 - 1
(seuil = 5)
9 (τ = 10.5) - - 14, 16, 18, 9
12 9 1 - 14 9 16, 18, 9
13 9 1 - 16 9 18, 9
14 9 1 - 18 9 9
15 9 1 - 9 10 -
16 10 2 10, 11
(τ = 9.5)
- - 10, 11
17 - 2 - 10 11 11
18 11 3 12, 13
(rtt = 2)
(τ lissé = 7.5)
11 12 12, 13
19 12 4 14, 15
(τ = 6.5)
12 13 13, 14, 15
20 13 5 (seuil atteint) 16, 17
(rtt = 2)
(τ lissé = 5.5)
13 14 14, 15, 16, 17
21 14 5.2 18 (τ = 6.5) 14 15 15, 16, 17, 18
22 15 5.4 19 (τ = 6.5) 15 16 16, 17, 18, 19
23 16 5.6 20 (τ = 8.5) 16 17 17, 18, 19, 20
24 17 5.8 21 (τ = 8.5) 17 18 18, 19, 20, 21
25 18 6 22, 23
(τ = 10.5)
18 19 19, 20, 21, 22
26 19 6.16 24 (τ = 10.5) 19 20 20, 21, 22, 24
27 20 6.33 25 (τ = 10.5) 20 21 21, 22, 24, 25
28 21 6.5 26 (τ = 10.5) 21 22 22, 24, 25, 26
29 22 6.66 27 (τ = 10.5) 22 23 24, 25, 26, 27
30 23 6.83 28 (τ = 10.5) 24 23 25, 26, 27, 28
31 23 6.83 - 25 23 26, 27, 28
32 23 6.83 - 26 23 27, 28
33 23 6.83 - 27 23 28
34 23 6.83 - 28 23 -
35 23 6.83 - - - -
35.5 - 1
(seuil = 3)
23 (τ = 10.5) - - 23
Commentaires :

Note : toute simulation raisonnable, même avec quelques détails faux, a été jugée correcte, et a rapporté plusieurs points. Aucun étudiant n'a remarqué les complications dues à l'expiration prématurée du temporisateur du segment 7, entre autres parce qu'une erreur fréquente a été de croire que la file d'attente se vide par miracle lorsque le temporisateur expire ! Erreur qui permettait heureusement de poursuivre une simulation intéressante, faisant intervenir la variable seuil.

3. Client/Serveur

Question 1.
La fonction gethostbyname retourne l'adresse IP d'une machine donnée par son nom; elle obtient ce résultat en faisant appel au résolveur de noms, qui interroge le serveur DNS local (si le résultat n'est pas déjà présent dans la mémoire cache du résolveur).
Question 2.
Ce programme lit et écrit dans la même socket, ce qui est tout à fait correct, car une socket TCP réalise une session TCP, qui est bi-directionnelle par définition.
Question 3.
Si le serveur a un port smtp actif (port 25), la connexion sur ce port réussit, mais le message d'accueil émis par le serveur ( "220 zx81.supercomputer.fr ESMTP" ) ne commence pas par "Solution", donc le test if (strncmp (buf, "Solution", 8) == 0) échoue, et le programme client passe directement à la dernière instruction de la boucle for, qui ferme la socket, avant de poursuivre les tentatives de connexion sur les ports suivants (26, 27, etc.)
Question 4.
Voici un squelette de serveur. Après création de la socket sd, il faut :

Bien entendu, dans les conditions de l'examen, on ne demandait pas aux étudiants de connaître par coeur les différents paramètres des fonctions bind, listen et accept.

static struct sockaddr_in
  adresse_client, adresse_serveur;
static char buf [1024];

void main (void) {
  int
    ta = sizeof (struct sockaddr_in),
    alarme, port_serveur, sd, sd2;
  
  adresse_serveur.sin_family = AF_INET;
  adresse_serveur.sin_addr.s_addr = htonl (INADDR_ANY);
  
  while (1) {
    sd = socket (PF_INET, SOCK_STREAM, 0);
    port_serveur = hasard (1, 5000);
    adresse_serveur.sin_port = htons (port_serveur);
    bind (sd, (struct sockaddr *) &adresse_serveur, ta);
    listen (sd, 10);
    alarme = 0;
    while (!alarme) {
      sd2 = accept (sd, (struct sockaddr *) &adresse_client, &ta);
      read (sd2, buf, 6);
      if (strncmp (buf, "TiTiTi", 6) == 0) {
        write (sd2, "Solution", 8);
        // lire le fichier solutionExam.txt
        // et l'écrire sur sd2
      }
      else
        alarme = 1;
      close (sd2);
    } // fin des connexions sur ce port    
    close (sd);
  } // fin de boucle infinie
}

Note : la gamme de ports choisie pour cet exercice (entre 1 et 5000) est évidemment irréaliste, et le programme ci-dessus risque de placer le serveur en écoute sur un port utilisé par un service classique, comme ftp ou smtp. Mais restreindre cette gamme à un intervalle plus réaliste, par exemple entre 2000 et 2100, aurait empêché de poser la question 3...