Épreuve de Réseaux Locaux et Interconnexion

r

R1

b P3

r

b

R2

r

d

d

b

P4 d

H6

H2

H3

H4

H5

a) Donnez le résultat du STP : quel est le pont racine, et pour chaque pont, quel est l’état de

chaque interface : racine, désignée ou bloquante. Justifiez votre réponse. 2 points

Le résultat est montré ci-dessus. P1 ayant la meilleure identité est la racine. P2 et P4 étant à même distance de la racine P1, et P2 meilleure identité, P2 est désigné vers R1 et P4 bloquant. Pour P3, le chemin par P3P4 est plus court (coût 38) que celui par P3R1 (coût 119) ou P3R2, donc P3P4 est racine et P3R1 et P3R2 sont bloquants b) En situation stable, combien de messages STP sont-ils reçus à chaque période par chaque

pont ? 1 point

Un pont reçoit un BPDU par l’interface racine et un par chaque interface bloquante. Donc les nombres sont P1 : 0, P2 : 1, P3 : 3, P4 : 2.

c) Quel est le chemin emprunté par une trame envoyée de H3 à H4 ? Est-ce le chemin le plus

court dans le graphe du réseau ? 1 point

Le chemin est R1 - P2 – P1 – P4 – R2. Ce chemin est de coût 238, alors que le chemin le plus court serait R4-P3-R2 avec un coût de 200. Mais ce chemin n’est pas dans l’arbre STP. d) On suppose que les couples de machines suivants communiquent : H2-H3, H3-H4, H1-H6, H3-H6, H7-H8, de plus toutes les machines communiquent avec Internet. Quel est le contenu de la table de forwarding de chacun des ponts ? 2 points

Au minimum, la table de forwarding d’un pont contient une entrée pour l’adresse H s’il est sur le chemin (dans le spanning tree) entre H et une autre machine avec laquelle elle communique. Au maximum elle contient les adresses mac de chaque machine qui communique car les premières rames sont diffusées suivant l’arbre (en gras les entrées obligatoires) : P1 H1, H2, H3 : P1-P2, H4, H5, H6 : P1-P4, H7 : P1-H7, H8 : P1-H8, G1 : P1-G1 P2 H1 : P2-H1, H2, H3 : P2-R2, H4, H5, H6, H7, H8, G1 : P2-P1 P3 H1, H2, H3, H4, H5, H6, H7, H8, G1 : P3-P4 P4 H1, H2, H3, H7, H8, G1 : P4-P1, H4, H5 : P4-R2, H6 : P4-H6

e) Quel est le débit maximal disponible entre chacun de ces couples ? 1 point On suppose que le débit maximal disponible est celui du lien le plus faible entre les deux nœuds. Débits en Mb/s). H2-H3 : 10, H3-H4 : 10, H1-H6 : 100, H3-H6 : 10, H7-H8 : 100. Les débits vers Internet (G1) sont de 10 pour H2, H3, H4, H5 et de 100 pour les autres. f) De façon générale, en gardant les coûts et priorité par défaut, existe-t-il des graphes de réseau tels que le STP sélectionne un chemin limité à 10 Mb/s entre deux machines alors qu’il existe un chemin à 100 Mb/s, un chemin à 1 Gb/s ? Justifiez. 2 points

Si un chemin contient un lien à 10 Mb/s, son coût est au minimum de 100. Un chemin de n liens à 100M a un coût de n*19, donc pour que le chemin à 10M soit choisi, il faut n*19 > 100, soit n > 5. Si deux ponts A et G sont reliés directement par un lien à 10M et aussi par 6 liens à 100M, A-B- C-D-E-F-G et par exemple si A est racine, G choisira son interface G-A comme port racine. Le principe est le même pour le Gb/s, mais cette fois on doit avoir n*4 > 100, donc n > 25, ce qui est pratiquement impossible. g) On branche maintenant une nouvelle machine H9 sur le pont/commutateur P3 et on suppose que la première communication réseau de H9 se fait avec un serveur situé sur Internet. Décrire les trames qui circulent et l’évolution des tables de forwarding de chaque pont. 1 point

H9 détermine que son correspondant n’est pas dans son sous-réseau (grâce à la configuration de l’interface) et connaît l’adresse IP du routeur par défaut, G1 mis pas son adresse ethernet. Donc H9 envoie en broadcast une requête ARP à destination de G1. Cette trame de broadcast est diffusée dans tout l’arbre, et donc tous les ponts apprennent l’adresse Mac de H9 par l’interface du spanning tree qui mène vers H9. Par exemple P1 ajoute H9 : P1-P4. Ensuite G1 répond à la requête Arp , et cette trame circule suivant P1-P4-P3 (chaque pont connaissant maintenant H9). Les paquets IP envoyés par H9 à destination d’internet seront contenus dans des trames ethernet à destination de G1 dont H9 et les ponts connaissent maintenant la localisation.

h) On suppose que le lien P1-P2 est coupé. Décrivez une évolution possible de l’arbre et son état final. Approximativement, au bout de combien de temps l’arbre est-il stabilisé ? les communications précédentes rétablies ? Quelles communications sont-elles les plus défavorisées par la nouvelle configuration ? Justifiez. 2 points Après au plus 20s (cache des BPDU), P2 invalide le BPDU reçu par P2-P1. Comme il ne reçoit aucun autre BPDU, il passe racine et envoie des BPDU, notamment vers P3 et P4. P4, qui a toujours un chemin vers la racine P1, passe son interface P4-R1 en désigné et envoie un BPDU. P2 le reçoit, choisit P1 comme racine et P2-R1 comme port racine. Pendant ce temps, P3 peut lui aussi déclarer son port P3-R1 racine, mais le repassera en bloqué à réception du BPDU de P4. Au final, les changements sont donc pour P2, P2-P1 passe en désigné et P2-R1 en racine, pour P4, P4- R1 passe en désigné. L’arbre est reconstruit après environ 20s (délai cache), ensuite l’interface P4-R1 ne propage les données qu’après le « forwarding delay » soit 15s. Certaines communications sont donc coupées

pendant plus de 35s (H1 vers Internet par exemple). Ensuite certaines communications ont un débit disponible potentiel qui passe de 100 à 10M : H1-G1, H1-H6. i) L’administrateur réseau constate que le lien P1-P2 est moins fiable que les autres. Comment peut-il configurer les priorités des ponts et/ou des ports pour que le réseau soit le plus stable possible ? Donnez la configuration, l’arbre obtenu, et ce qui se passe en cas de coupure du lien P1-P2. 1 point

Si on donne une meilleure priorité à P4 qu’à P1, ce sera P4 la racine, et l’interface P4-R1 sera désignée et P2-R1 bloquante : dans ce cas seules les communications avec H1 sont perturbées par une coupure de P1-P2, et chacun garde le même débit qu’avec la solution par défaut. Une autre possibilité est de changer en plus le coût du lien P1-P2, par exemple > 100. Dans ce cas, P2 choisira P2-R1 comme port racine (et P2-P1 bloquant) : le lien P1-P2 n’est plus utilisé du tout, donc aucune perturbation en cas de coupure. L’inconvénient c’est que toutes les communications de H1 sont à 10M.

Partie II

On considère un réseau de type ethernet-CSMA/CD.

a) Comment un émetteur détecte-t-il une collision ? Un récepteur détecte-t-il les collisions ?

1 point

Un émetteur détecte une collision si pendant l’émission le signal émis est différent du signal présent sur le support. Un récepteur n’a pas réellement besoin de détecter les collisions. Néanmoins une collision se traduit par une trame erronée, normalement un fragment de trame plus court que la plus petite trame légale, ce qui est détectable par le récepteur. b) Dans un réseau à 10 Mb/s, quelle est la durée d’émission d’une trame minimale ? Quel est le temps d’attente maximal avant l’émission réussie d’une trame ? Justifiez votre calcul. Même question dans un réseau à 100 Mb/s. 2 points

Une trame de 64 octets à 10 Mb/s est émise en 64 * 8 / 10 µs = 51,2 µs = t. A noter qu’une trame maximale de 1514 octets est émise en T = 1514 * 8 /10 = 1211,2 µs. Le délai maximal est composé de l’attente que le canal soit libre, l’émission (CSMA persistant), la détection de collision, l’attente d’un délai aléatoire, puis recommencer jusqu’à la 16ème tentative. Le temps d’attente aléatoire à la ième tentative vaut au pire (2i – 1) t pour i < 11 puis 1023 t pour 10 < i < 17 ce qui donne au total 9174 t. Le temps de détection des 16 collisions peut prendre 16*t, et le temps d’attente avant émission peut prendre 16 trames maximales, soit 16 T. Au total 9190t + 16T soit environ 490 ms. A noter qu’en théorie une collision peut se produire à la 16ième tentative et la trame n’est pas transmise du tout. c) On suppose que deux émetteurs E1 et E2 sont entrés en collision pendant leurs k premières tentatives d’émission d’une trame. Pendant la k+1ième tentative ils entrent en collision entre eux et avec un nouvel émetteur E3. A la tentative suivante, est-ce que les 3 émetteurs auront la même chance d’émettre ? comment cela évolue-t-il en fonction de k ? Est-ce équitable ? 2 points

E1 et E2 vont tirer un nombre aléatoire entre 0 et 2k – 1, alors que E3 va tirer entre 0 et 1 et a donc plus de chance d’avoir le nombre le plus petit. L’avantage de E3 croît quand k augmente. Ce mécanisme n’est pas équitable puisque le dernier venu a plus de chance d’émettre que les précédents d) Dans un réseau ethernet pourquoi n’y a-t-il pas de problème de « terminal caché » ? 1

point

Le réseau étant en bus, le signal arrive à toutes les autres stations, avec un certain affaiblissement. Les limites imposées sur les longueurs de câbles font que l’affaiblissement est minime et n’empêche pas chaque station de capter toutes les autres. En ne respectant pas les limites sur ces longueurs, le problème pourrait se produire. e) La norme ethernet 10 Giga n’a pas prévu de mode CSMA/CD. Quel serait l’ordre de

grandeur de la taille d’un tel réseau ? Justifiez votre réponse. 1 point

Si on conserve les mêmes tailles de trames minimales, le temps aller-retour devrait être inférieur à 51,2 ns , donc même si les délais ne provenaient que de la propagation du signal (à 300 000 km/s), la distance serait limitée à 300 000 km/s * 51,2 ns /2 soit environ 8,5 m.

Partie III

On considère un anneau à jeton, où R est un paramètre connu de toutes les stations, D le débit de l’anneau, L la longueur (supposée fixe) d’une trame, et T le temps de propagation du signal autour de l’anneau. On note time la fonction qui rend l’heure actuelle. L’algorithme d’utilisation du jeton est le suivant :

Lors arrivée d’un jeton

dispo := R – (time – dernier) ; Ntrame := si dispo > L/D alors dispo ÷ L/D sinon 1 finsi tant que trame_à_émettre et Ntrame > 0

émettre trame ; Ntrame := Ntrame -1

émettre jeton ; dernier := time

On appelle rendement du réseau la fraction du temps utilisée pour l’émission de trames de données, et temps d’accès le temps d’attente avant de pouvoir émettre une trame de données.

a) Quel est le temps de rotation maximal du jeton ? 2 points Si R est petit (par exemple < T), dispo est toujours négatif et donc Ntrame =1, ce qui veut dire qu’à chaque tour au pire chaque station émet une trame et le temps de rotation est alors N L/D + T. Si par contre R est assez grand, une station peut garder le jeton et envoyer Ntrame trames. Le temps de rotation sera alors environ R + N L/D (si le jeton est « en retard », dispo < L/D chaque station peut quand même envoyer une trame). b) Si une seule station a des trames à émettre, quel débit peut-elle atteindre en fonction de

R, T, L et D ? Comment le rendement évolue-t-il en fonction de R ? 1 point

Le jeton met un temps T pour revenir à la station active puisque les autres stations ne le capturent pas. Donc dispo = R-T et Ntrame = (R-T) ÷ L/D. Le débit est de Ntrame * L / (Ntrame*L/D +T) soit environ D (1 – T/R). Donc le débit obtenu augmente avec R, et tend vers D quand R est très grand par rapport à T, ce qui veut dire que le rendement tend vers 1 : le temps d’attente du jeton devient négligeable, beaucoup de trames étant émises par tour. c) Si toutes les stations ont des trames à émettre, quel est le rendement ? le temps d’accès le

pire ? 1point

Le nombre de trames émises par tour est le même que précédemment, donc le débit global et le rendement son identiques. Le temps d’accès le pire est inférieur à R + (N-2) L/D (l’anneau est « rempli » par la station 1 pendant au plus R-T, les stations 2, …, N-1 peuvent encore émettre une trame, la station N a donc attendu R-T + T + (N-2) L/D). On observe que ce temps d’accès augmente avec R

d) Quelles sont les propriétés de l’algorithme ci-dessus par rapport à l’algorithme à jeton

de base où le détenteur du jeton peut émettre un nombre fixe de trames ? 1 point

Dans l’algorithme de base si un émetteur peut émettre K trames, alors soit on choisit K petit ce qui donne un bon temps d’accès mais un rendement faible quand il y a un seul émetteur, soit on choisit K grand pour améliorer le rendement, mais alors le temps d’accès grandit très vite si toutes les actions sont actives : proportionnel à KN. Le temps d’accès augmente avec le nombre de stations actives. Dans l’algorithme du sujet, le nombre de trames émises par tour est partagé sur toutes les stations actives.