Алгоритми маршрутизації в мережах, Детальна інформація

Основний алгоритм, що будує PATHS з нуля, починає додавання систем з найвигіднішими маршрутами з оглядом на PATHS (не може існувати коротшого маршруту до SELF ). Потім визначається TENT використовуючи локальні таблиці з відомостями про сусідні вершини.

Система не може бути розміщеною в PATHS до тих пір, поки не доведено, що не існує маршруту, коротшого за даний. Коли система N розміщується в PATHS, перевіряється ціна маршруту до кожної вершини M сусідньої до N через саму вершину N. Цей маршрут визначається як сума ціни маршруту до N та ціни ділянки NM. Якщо розміщений в TENT та нове значення буде більшим, маршрут ігнорується.Якщо розміщений в TENT та нове значення буде меншим, старий запис заміщується новим. Якщо розміщений в TENT та нове значення таке ж саме як те, що вже є в TENT то набір {Adj(M)} встановлюється як поєднання старого запису (того, що міститься в TENT) та нового - {Adj(N)}. Якщо M не знаходиться в TENT, то даний маршрут додається в TENT.

Потім алгоритм знаходить триплети in TENT з мінімальним x.

2.2.2. Реалізація алгоритму відкриття найкоротшого шляху в DUAL IS-IS середовищі

Крок 0: Встановимо TENT та PATHS як пусті. Встановимо tentlength в 0.

(tentlength – це довжина шляху досліджуваних елементів TENT.)

1) Додамо до PATHS, де SELF – початкова система, W –спеціальна величина, що визначає трафік до SELF що пройдений, включаючи внутрішній процес.

2) Тепер загрузимо TENT локальними даними шляхів (Кожен запис в TENT має бути визначений як маршрутизатор або кінцева система OSI, щоб дозволити правильну перевірку в Кроці 2).

Для всіх суміжних вершин Adj(N) на всіх можливих каналах:

d(N) = ціна маршруту, що проходить через (N)

Adj(N) = кількість вершин сусідніх N.

3) Якщо триплет в TENT, то

Якщо x = d(N), то {Adj(M)} := {Adj(M)} U {Adj(N)}.

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

5) Якщо x < d(N), нічого.

6) Якщо x > d(N), видалити з TENT і додати триплет .

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

8) Тепер додаються системи, для яких локальний маршрутизатор не має суміжних вершин, але вони згадані в сусідніх псевдовершинах LSP. Суміжність для таких систем визначається маршрутизатором.

9) Для всіх широковєщательних каналів в активному стані, знайти псевдовершину LSP для цього каналу. Якщо така існує, для всіх сусідів N, про які згадувається на цій вершині і не визначені в TENT, додати запис:

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)}.