Examen 18 dec 2015

Examen 18 dec 2015

by Eliott Adrien Rene Mea -
Number of replies: 1

Bonjour, 

dans la question n°3 du quiz de l'examen de 2015, la complexité du calcul de la table de routage est RN. Pourtant, n'a-t-on pas appris en cours que la complexité pour N routeurs du calcul du plus court chemin entre un point du réseau et de tous les autres est de N^2 ? Pourquoi cela ne s'applique-il pas à la table de routage (proposition 3) ?

In reply to Eliott Adrien Rene Mea

Re: Examen 18 dec 2015

by Jean-Cédric Chappelier -

vous confondez deux choses :

  • les algorithmes de plus court chemin (vus dans la leçon I.2); qui calculent effectivement un/les plus courts chemins (= le résultat est le/les chemin(s) complets) par exemple (que vous citez) entre 1 noeud et tous les autres ;
  • l'algorithme de calcul de la table de routage IP (vu en leçon III.3); qui fournissent à chaque noeud/routeur le moyen d'envoyer le paquet par le plus court chemin; mais le chemin lui-même n'est pas calculé : on ne le « sort » pas de l'algorithme (ce serait le chemin parcouru par le paquet, mais on ne le mémorise pas).
    Si l'on voulait avoir tous les plus courts chemins vers tous les autres noeuds il faudrait, par exemple, envoyer un paquet à chacun : d'où un facteur N en plus.