Cours

Calcule la distance minimale d’un chemin à la (aux) source(s)
- source = destination des paquets
- next-hop
  Une annonce = un vecteur de distance X annonce : \forall S d_{s}(X)

Évènement : annonces/pertes/démarrage (tardif) d’un routeur
Non optimal :
- d_{B}(A) : 7 et non 3
- d_{D'}(A) : \infty et non 1
- d_{E}(A) : 10 et non 6
Plusieurs scénarios possibles :
- Jamais d’annonce de D vers A \ra l’algorithme n’est probablement pas fini de s’être exécuté
\text{nh}\_{D}(C) = B et pas A qui n’a pas annoncé d\_{D}(A) = 1 mais d\_{D}(A)=\infty (autre \text{nh} évidents)
Les affectations de d_{S(Y)} sont :
- init : d_{S}(Y) = \infty
- ensuite : d_{S}(Y) = \text{min}(d_{S}(Y)\text{, autre chose})
- La 2ᵉ ne peut que diminuer
Longueurs positives donc initialiser d_{S}(S) = 0 garantie que d_{S}(S) = \text{dist}(S, S) = 0
Hypothèse : d_{A_{k}}(A_{i}) = \text{dist}(A_{k}, A_{i}) pour i \geqslant 2, montrez que d_{A_{K}}(A_{1}) = \text{dist}(A_{k}, A_{1})
Que veut d_{A_{k}}(A_{1}) quand A_{2} annonce à A_{1} ?
1. d_{A_{k}} = \text{dist}(A_{k}, A_{1}) OK
2. d_{A_{k}} > \text{dist}(A_{k}, A_{1}) OK, alors on compare d_{A_{k}}(A_{1}) et donc mise à jour et convergence
3. d_{A_{k}} < \text{dist}(A_{k}, A_{1}) impossible car : invariant :
  - d_{S}(Y) est la longueur d’un chemin (donc > \text{dist}(S, Y))
  - d_{S}(Y) est celui qui suit les \text{nh} : Y, \text{nh}\_{S}(Y), \text{nh}\_{S}(\text{nh}\_{S}(Y)), \dots, \text{nh}\_{S}^{(k)}(Y), S
Oui c’est embêtant

a.
b.
c.