A dynamic shortest path tree (SPT) algorithm for a router determines a new
SPT for a root node in response to a link-state or other network topology
change. The dynamic SPT algorithm determines the new SPT as an
optimization problem in a linear programming framework based in an
existing SPT in the router. The dynamic SPT algorithm emulates maximum
decrement of a ball and string model by iteratively selecting nodes of the
existing SPT for consideration and update of parent node, child nodes, and
distance attributes based on the maximum decrement. For the maximum
decrement, a node in the existing SPT is selected by each iteration based
on the greatest potential decrease (or least increase) in its distance
attribute. The ball and string model that may be employed for the dynamic
SPT algorithm represents a network of nodes and links with a ball
representing a node and a string representing a link or edge. The length
of a string is defined by its link's weight. The set of strings connecting
the balls defines a path between the root node and a particular node. The
shortest path is the path defined by the strings from a root node to a
particular node that are tight. For the dynamic SPT algorithm, an increase
(or decrease) in an edge weight in an existing SPT corresponds to a
lengthening (or shortening) of a string. By sequentially pulling balls
away in a single direction from the ball of the root node, the new SPT
becomes defined by the balls and tight strings.
Un algorithme dynamique de l'arbre de chemin le plus court (SPT) pour un couteau détermine un nouveau SPT pour un noeud de racine en réponse à un lien-état ou à tout autre changement de topologie de réseau. L'algorithme dynamique de SPT détermine le nouveau SPT comme problème d'optimisation dans un cadre de programmation linéaire basé dans un SPT existant dans le couteau. L'algorithme dynamique de SPT émule la décroissance maximum d'un modèle de boule et de corde en choisissant itérativement les noeuds du SPT existant pour la considération et la mise à jour du noeud de parent, des noeuds d'enfant, et des attributs de distance basés sur la décroissance maximum. Pour la décroissance maximum, un noeud dans le SPT existant est choisi par chaque itération basée sur la plus grande diminution potentielle (ou moindre augmentation) de son attribut de distance. Le modèle de boule et de corde qui peut être utilisé pour l'algorithme dynamique de SPT représente un réseau des noeuds et des liens avec une boule représentant un noeud et une corde représentant un lien ou un bord. La longueur d'une corde est définie par le poids de son lien. L'ensemble de cordes reliant les boules définit un chemin entre le noeud de racine et un noeud particulier. Le chemin le plus court est le chemin défini par les cordes d'un noeud de racine à un noeud particulier qui sont serrées. Pour l'algorithme dynamique de SPT, une augmentation (ou la diminution) d'un poids de bord dans un SPT existant correspond à rallonger (ou à raccourcir) d'une corde. En tirant séquentiellement des boules loin dans une direction simple de la boule du noeud de racine, le nouveau SPT devient défini par les boules et les cordes serrées.
