Алгоритми маршрутизації в мережах

d(N) повинне бути меншим ніж dist(P,N), або N не повинне бути в PATHS. За бажанням можна зробити додаткову перевірку чи є d(N) меншим за dist(P,N).

4) Якщо триплет в TENT, тоді:

a) Якщо x = dist(P,N) тоді {Adj(N)}:= {Adj(N)} U {Adj(P)}.

b) Якщо N – маршрутизатор або кінцева система OSI, і більше не існує суміжних вершин {Adj(M)}, то видалимо надлишкову вершину.

c) Якщо x < dist(P,N), нічого.

d) Якщо x > dist(P,N), видалити з TENT, та додати

5) Якщо не в TENT, додати в TENT.

Крок 2: Якщо TENT пустий, зупинитися. Інакше:

1) Знайти елемент , з мінімальним x таким чином:a)Якщо елемент <*,tentlength,*> залишився в TENT в списку для tentlength, вибрати цей елемент. Якщо в списку існує більше одного елементу, вибрати один з цих елементів для системи, що є псевдовершиною, вибрати ту, що не є псевдовершиною. Якщо більше нема елементів в списку для tentlength, збільшити tentlength і повторити Крок 2.

b)Видалити з TENT.

c) Додати в PATHS.

d) Якщо система тільки що додана в PATHS – кінцева система, то перейти в Крок 2. Інакше : перейти в Крок 1.

Позначення:

PATHS – представляє ациклічний граф найкоротших шляхів від системи S. Він представляється як набір триплетів , де N ідентифікатор системи. d(N) загальна відстань від N до S).

{Adj(N)} –набір працюючих сусідів S, що їх можна використати N. Якщо система є в PATHS, шляхи, що відповідають цьому місцю є найкоротшими.

TENT – список триплетів у вигляді , де N, d(N) та {Adj(N)} відповідають визначеним в PATHS.

TENT може бути інтуітивно представлений як місце системи в PATHS. Іншими словами, триплет в TENT говорить, що, якщо N є в PATHS, d(N) відповідає x, але N не може бути розміщене в PATHS поки не доведено, що не існує шляхів, коротших за x .

Так само в TENT значить, що якщо N є в PATHS, тоді d(N) буде дорівнювати x для маршрутів, що проходять через суміжну вершину A або через суміжну вершину B.

Запропоновано в реальній реалізації таблиці TENT проводити сортування за характеристикою d(N).

3. Висновки

Маршрутизаційні алгоритми реалізовані на різних типах мереж від локальних до глобальних. Широко розповсюдженим є демон Routed з дистриутиву університету Каліфорнії в Берклі він реалізований в протоколі RIP. Також велике значення мають реалізації алгоритму відкриття найкоротшого маршруту для подвійного середовища OSI та TCP/IP в плані знаходження маршрутів між інтер-автономними системами та маршрутизаторами TCP/IP архитектури.