En réalité, personne ne dispose d'une carte complète et précise d'Internet, et cela n'est absolument pas nécessaire pour le routage. Ce qui importe, c'est que chaque routeur connaisse l'état de ses voisins immédiats et puisse indiquer la direction à prendre pour chaque information transmise, sans avoir connaissance de l'ensemble du chemin à parcourir. Mais comment s'assurer qu'il indique la bonne direction ? Cela est rendu possible grâce à un algorithme, par lequel chaque routeur, dès qu'il est informé d'un changement d'état chez l'un de ses voisins immédiats, informe à son tour les autres voisins de ce changement. Ces derniers pourront éventuellement modifier la direction qu'ils indiqueront aux futurs messages. Ainsi, l'information sur les changements du réseau se propage progressivement, et en temps réel, chaque routeur adapte sa table de routage en conséquence.
L'algorithme ci-dessus résume, d'une manière simplifiée, l'adaptation de la table de routage d'un routeur lorsque celui-ci est informé qu'un routeur voisin, nommé M, est en panne, inaccessible ou a été supprimé. La procédure décrite est mise en œuvre pour une destination donnée notée X.