Működési alapelv:
A routerek minden elérhető célra (gép vagy hálózat) nyilvántartják, hogy a legjobb úton milyen irányban milyen távolsággal érhető el az adott cél (távolságvektor).
A szomszédos forgalomirányítók ezen információkat meghatározott időközönként kicserélik egymással.
Az új információk birtokában a routerek ellenőrzik, hogy szükséges-e változás valamelyik eddig ismert legjobb úttal kapcsolatban. (Található-e az eddig ismertnél jobb útvonal?)
Definíció: d(i, j) jelölje az i és j entitások közvetlen elérési költségét (közvetlen távolságát):
Definíció: D(i, j) jelölje az i és j entitások legrövidebb úton történő elérésének távolságát:
| A minimumot elegendő a szomszédos k entitásokra számítani. |
| D(i, j) számítási formulájának helyessége indukcióval bizonyítható. |
Routing tábla felépítés (Bellman-Ford algoritmus).
Kiindulási helyzet:
Minden i entitás ismeri a d(i, k) távolságot minden k szomszédjára vonatkozóan.
Legyen továbbá
Működési algoritmus (tetszőleges i → j (i ≠ j) útra vonatkoztatva):
Az i entitás minden k szomszédjától megkapja a D(k, j) értéket.
A k szomszédtól érkezett D(k, j) értéket felhasználva az i entitás kiszámítja a Xi,k,j = d(i,k) + D(k, j) értéket.
Ha a kapott Xi,k,j érték kisebb, mint az eddig ismert D(i, j), akkor a j entitás i-ből aktuálisan az új minimumot szolgáltató k szomszédon keresztül lesz elérhető, a már kiszámított Xi,k,j értéket használva D(i, j) metrika értékként.
Egy meghatározott ciklusidő eltelte után folytassuk az 1. lépésnél.
Bellmann és Ford bebizonyította, hogy az eljárás véges sok lépés után az optimális utat szolgáltatja (ezért szokás ezt a módszert Bellman-Ford algoritmusnak is nevezni).