Universit Louis Pasteur Matrise IUP GMIDpartement d'Informatique Rseaux Haut Dbit et Multimdia

Session de mars 2001 CORRIG1) On considre le rseau suivant o les Ri sont des routeurs et les Mi des stations. On dfinitle cot d'envoi d'un paquet d'une source S vers N destinataires comme la somme pour toutlien l du nombre de paquets mis sur l. Par exemple le cot d'envoi d'un paquet unicast de M1 M2 est 4 (1 paquet transmis successivement sur 4 liens).

M1 R1 R2 R3 M2

M5 R4 R5M3

R6 M4

I1 I2

I3

a) Si on ne dispose pas de routage multicast, on peut envoyer un paquet N rcepteursen l'envoyant N fois en unicast. Quel est le cot pour envoyer un paquet de M1 augroupe G = {M2, M3, M4} ?

Le cot est de 4 + 4 + 4 = 12.b) On suppose maintenant qu'on utilise un routage multicast en mode dense comme

PIM-DM. Quel est l'arbre multicast utilis quand M1 envoie un paquet ? Quelle estla table de routage multicast de R3 ? Quel est le cot ? On distinguera le cas o M1envoie son premier paquet vers G et le cas des paquets suivants. Existe-t-il un arbremulticast de cot moindre ?

M1 R1 R2 R3 M2

M5 R4 R5M3

R6 M4

Arbre de diffusion, les artes R4-R6 et ventuellement R3-R5 et R5-R3 sont lagues aprs lepremier paquet. Le cot est de 8 aprs lagage. La table de routage de R3 contient une entrede type [(S=M1, G), iif=I1, oif={I2}].L'arbre suivant a un cot moindre (7) :

M1 R1 R2 R3 M2

M5 R4 R5M3

R6 M4

c) On suppose maintenant qu'on utilise le routage multicast en mode pars PIM-SM,avec le mme groupe G. Pour les 3 choix de point de rendez-vous (RP) R1, R3, R6,donnez l'arbre multicast obtenu, et le cot lorsque M1 envoie un paquet G. Quelleest la table de routage multicast de R3 ? Mme question si c'est M3 qui envoie lepaquet.

M1 R1 R2 R3 M2

M5 R4 R5M3

R6 M4

RP= R1. Le cot est de 7 plus le chemin depuis la source vers R1(1 pour M1, 3 pour M3). Latable de routage de R3 contient une entre [(*, G), iif=I1, oif={I2}]. Si R1 envoie un RegisterStop vers M3, une branche (M3,G) est construite vers R1 et le cot devient 7 pour la sourceM3.

M1 R1 R2 R3 M2

M5 R4 R5M3

R6 M4

RP=R3. Le cot est de 4 plus le chemin depuis la source vers R3 (3 pour M1, 2 pour M3). Latable de routage de R3 contient une entre [(*, G), iif=0, oif={I2,I3}]. Aprs un Register Stopde R3 vers M3, la tabel de R3 contiendrait en plus une entre [(M3,G), iif=I3, oif={I2}], et lecot serait de 4.

M1 R1 R2 R3 M2

M5 R4 R5M3

R6 M4

RP=R6. Le cot est de 6 plus le chemin depuis la source vers R6 (3 pour M1, 3 pour M3). Latable de routage de R3 contient une entre [(*, G), iif=I3, oif={I2}]. Aprs un Register Stopde R6 vers M1 et M3, le cot serait de 8 pour M1 et 6 pour M3.

2) On dispose de commutateurs ethernet relis un rseau ATM par une interface(uplink) ATM. Ces commutateurs disposent ventuellement d'une fonction de routageIP.a) On dsire transmettre des donnes entre deux de ces commutateurs. Quelles sont les

protocoles envisageables ? On pourra s'inspirer des matriels utiliss en TP.On peut envisager :- du bridging point point (PtoP) configur manuellement entre deux commutateurs

ethernet via un PVC ou un SoftPVC,- utiliser Classical IP over ATM (CLIP) en activant le routage sur les commutateurs, ainsi

qu'un serveur ATM-Arp pour le LIS,- LANE en mettant tous les commutateurs dans un ELAN et en activant un LECS, un

LES/BUS, et un LEC sur chaque commutateur.b) On dsire maintenant connecter un grand nombre de tels commutateurs travers

ATM. Quelles sont les solutions encore envisageables et pourquoi ?La premire solution n'est pas extensible grande chelle. Les deux autres sont plusextensibles, ventuellement en crant plusieurs Lis ou plusieurs ELAN.

3) On rappelle l'algorithme du seau fuite ou Leaky Bucket LB avec incrment I etcapacit L+I :Algorithme LB(I, L) :Initialement X=0, LCT = 0 o X est le contenu du seau et LCT la date de la dernire cellule conformeArrive d'une cellule au temps t:

X' := X - (t - LCT)Si X' < 0 alors X':= 0Sinon si X' > L alors exit cellule non conforme

finsiFinsiLCT := tX := X'+ I/* la cellule est conforme */

On supposera que les cellules non conformes sont limines (perdues).a) Quand L est nul, quel est l'intervalle minimal entre l'arrive de deux cellules, et le

dbit maximal sans perte ? On appliquera le rsultat au cas d'une liaison 155 Mb/savec I = 10 s.

Aprs chaque cellule conforme le seau contient I, donc la cellule conforme suivante ne peutarriver qu'aprs un dlai I. Le dbit maximal sans perte est donc d'une cellule tous les I, soit

1/I cellules/s ou 424/I b/s. Application numrique : I = 10 s et donc dbit maximal = 53 * 8 /10 s = 42,4 Mb/s. La liaison 155 Mb/s ne peut donc pas tre sature.

b) On suppose maintenant L non nul. Quel est le dbit maximal D possible sur unegrande priode de temps ? Quel est le nombre N de cellules successives qui peuventtre envoyes un dbit 2D sans tre limines ? Appliquer au cas L=100 s et I= 10s.

Sur une grande priode, on ne peut pas envoyer plus d'une cellule par intervalle I, le dbitmaximal sans perte est donc le mme que prcdemment. On peut le voir en considrant quele seau est incrment de I chaque arrive, et dcrment d'au plus tn - tn-1 l'arrive de lacellule n. Il contient donc au moins n*I -(tn-t0) et ceci doit tre infrieur L pour que la cellulesoit conforme. La borne suprieure du dbit tend donc vers 1/I quand n augmente. A un dbit2D, les cellules arrivent intervalle I/2. Aprs la nime cellule le seau contient (n-1)*I/2 +I .Elle sera non conforme si le seau contient plus que L+I, donc si n > N = 2L/I +1.Application L=100 s et I= 10 s : N = 21, la 22me cellule est limine.

c) Combien de temps doit-il s'couler au minimum entre deux telles rafales de Ncellules pour qu'aucune cellule ne soit limine ?

Aprs une rafale maximale de 2L/I + 1 cellules dbit 2D, le seau contient L + I, il est doncvide aprs un temps L + I (110 s dans notre exemple).