Épreuve de Réseaux Locaux et Interconnexion

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 linterface 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 nest pas dans larbre 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 dun pont contient une entr e pour ladresse H sil 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 larbre (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 nSuds.

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

quil 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 n19, donc pour que le chemin 10M soit choisi, il faut n19 > 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 nest pas dans son sous-r seau (gr ce la configuration de

linterface) et conna t ladresse 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 larbre, et donc tous les ponts apprennent ladresse Mac de H9 par linterface 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 dinternet 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 larbre et son tat

final. Approximativement, au bout de combien de temps larbre 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 .

Larbre est reconstruit apr s environ 20s (d lai cache), ensuite linterface P4-R1 ne propage les

donn es quapr 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) Ladministrateur 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, larbre 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 linterface 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 quavec 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 nest plus utilis du tout,

donc aucune perturbation en cas de coupure. Linconv nient cest 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 na 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 dune trame minimale ? Quel

est le temps dattente maximal avant l mission r ussie dune 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 quune trame

maximale de 1514 octets est mise en T = 1514 * 8 /10 = 1211,2 s.

Le d lai maximal est compos de lattente que le canal soit libre, l mission (CSMA persistant), la

d tection de collision, lattente dun d lai al atoire, puis recommencer jusqu la 16 me tentative.

Le temps dattente 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 dattente avant mission peut prendre 16 trames maximales, soit 16 T. Au total

9190t + 16T soit environ 490 ms. A noter quen th orie une collision peut se produire la 16i me

tentative et la trame nest 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 dune 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 davoir le nombre le plus petit. Lavantage de E3 cro t quand k augmente. Ce

m canisme nest pas quitable puisque le dernier venu a plus de chance d mettre que les

pr c dents

d) Dans un r seau ethernet pourquoi ny 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 laffaiblissement est minime et

nemp 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 na pas pr vu de mode CSMA/CD. Quel serait lordre de

grandeur de la taille dun 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

lanneau, L la longueur (suppos e fixe) dune trame, et T le temps de propagation du signal autour de

lanneau. On note time la fonction qui rend lheure actuelle. Lalgorithme dutilisation du jeton est le

suivant :

Lors arriv e dun 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 dacc s le temps dattente 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 / (NtrameL/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 dattente 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 dacc 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 dacc s le pire est inf rieur R + (N-2) L/D (lanneau 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 dacc s

augmente avec R

d) Quelles sont les propri t s de lalgorithme ci-dessus par rapport lalgorithme jeton

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

Dans lalgorithme de base si un metteur peut mettre K trames, alors soit on choisit K petit ce qui

donne un bon temps dacc 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 dacc s grandit tr s vite si toutes

les actions sont actives : proportionnel KN. Le temps dacc s augmente avec le nombre de

stations actives. Dans lalgorithme du sujet, le nombre de trames mises par tour est partag sur

toutes les stations actives.