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

to TENT, where:

d(N) = ціна проміжку .

Adj(N) = кількість вершин, що стоять на шляху до заданого маршрутизатора.

10) Перейти в Крок 2.

Крок 1: Визначити нульовий PDU в LSP ситеми, щойно доданої в PATHS

1)dist(P,N) = d(P) + metric.k(P,N) для кожного сусіда N (як для кінцевої системи, так і для маршрутизатора) системи P.

2) Якщо dist(P,N) >максимальної ціни проміжку, нічого.

3) Якщо є в PATHS, нічого.

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.