Université de Manouba                              Année Universitaire 2006-2007

Ecole Nationale des Sciences de                               Semestre 1

L'Informatique                                                                      Date : 07-12-2006

 

Matière : TFM                                                              Enseignant : Pr. Abdelfettah Belghith

Classe : 1113 et Mastère                                             Durée : 2H Doc.: autorisés

Barème : 8+6+6=20                                                     Nombre de pages 4

 

 

 

Examen Final

 

Considérons le réseau Abilene qui est un domaine faisant partie du projet Internet2 et reliant les universités américaines. Pour les besoins d'une application multimédia distribuée, nous désirons mettre en place des routes respectant des contraintes de qualité de service données.

 

A. Présenter en fonction du type de l'application (unicast ou multicast) et en fonction des contraintes (une ou plusieurs et additives ou minmax), les différentes approches possibles pour résoudre un tel problème (le problème de calcul de chemin vers la ou les destinations éventuelles) en spécifiant les hypothèses de chacune de ses approches et en présentant les arguments nécessaires.

 

B. Considérons le réseau abilene tel qu'il est représenté dans le document ci-contre (à remettre obligatoirement). Ce réseau est composé de 11 routeurs et de 14 liens où chaque lien est caractérisé par deux métriques additives indépendantes.

1. Exécuter l'algorithme TAMCRA (k=2) permettant de calculer les chemins du nœud source ni vers tous les noeuds du réseau sachant que les limites à respecter sont 15 et 14 respectivement pour la première et la deuxième contrainte. Pour répondre à cette question, on vous demande de remplir le document ci-contre (réponse B-1) en respectant les directives suivantes :

·  Un tableau de 3 colonnes est associé à chaque noeud. La première colonne est réservée pour le numéro de l'étape d'exécution, la deuxième et la troisième colonne sont utilisées pour stocker les deux *Variables de l'algorithme (le noeud prédécesseur et le coût induit par l'utilisation de ce noeud).

·  On vous demande de remplir les lignes nécessaires de chaque tableau en spécifiant le numéro de chaque étape. La justification du résultat trouvé pour chaque étape doit être explicitée sur la copie, en précisant pour chaque étape le raisonnement et les calculs qui ont abouti au noeud et au coût correspondant.

·  NB : Un document dont les tableaux sont remplis sans les justifications

nécessaires ne sera pas pris en compte.

·  II est nécessaire de présenter à la fin les chemins trouvés du noeud source ni vers tous les noeuds du réseau.

2. Exécuter l'algorithme SAMCRA en remplissant le document (réponse B-2) et en respectant les mêmes contraintes et les mêmes directives présentées dans la question précédente.

3. A partir des résultats trouvés dans 1 et 2, énoncer le principe du sous optimalité en l'argumentant avec l'exemple utilisé.

4. Enoncer le principe de la dominance et présenter. à partir des calculs faits en (1) ou en (2) un cas de son utilisation.

 

C. Supposant que l'application à exécuter est une application multicast et que les membres intéressés par cette session sont les noeuds no, n2, n6, n7 et ns.

1. Exécuter l'algorithme MAMCRA en utilisant les résultats trouvés précédemment. Il est nécessaire de justifier pas à pas le déroulement de l'algorithme et de présenter à la fin la structure de routage trouvée. (Contraintes à respecter 15 et 14)

2. Arrive-t-on à enlever tous les cycles ? Justifier.

3. Supposant que la bande passante disponible sur tous les liens est de 20 Mbit/s, quel est l'effet d'avoir une application nécessitant 10 Mbit/s ou 15 Mbit/s sur la structure de routage finale.