Реферат: Алгоритми маршрутизації в мережах
<N,d(N),{Adj(N)}> 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) Якщо <N,d(N),{Adj(N)}> є в PATHS, нічого.
d(N) повинне бути меншим ніж dist(P,N), або N не повинне бути в PATHS. За бажанням можна зробити додаткову перевірку чи є d(N) меншим за dist(P,N).
4) Якщо триплет <N,x,{Adj(N)}> в 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), видалити <N,x,{Adj(N)}> з TENT, та додати <N,dist(P,N),{Adj(P)}>
5) Якщо <N,x,{Adj(N)}> не в TENT, додати <N,dist(P,N),{Adj(P)}> в TENT.
Крок 2: Якщо TENT пустий, зупинитися. Інакше:
1) Знайти елемент <P,x,{Adj(P)}>, з мінімальним x таким чином:
a)Якщо елемент <*,tentlength,*> залишився в TENT в списку для tentlength, вибрати цей елемент. Якщо в списку існує більше одного елементу, вибрати один з цих елементів для системи, що є псевдовершиною, вибрати ту, що не є псевдовершиною. Якщо більше нема елементів в списку для tentlength, збільшити tentlength і повторити Крок 2.
b)Видалити <P,tentlength,{Adj(P)}> з TENT.
c) Додати <P,d(P),{Adj(P)}> в PATHS.
d) Якщо система тільки що додана в PATHS – кінцева система, то перейти в Крок 2. Інакше : перейти в Крок 1.
Позначення:
PATHS – представляє ациклічний граф найкоротших шляхів від системи S. Він представляється як набір триплетів <N,d(N),{Adj(N)}>, де N ідентифікатор системи. d(N) загальна відстань від N до S).
{Adj(N)} –набір працюючих сусідів S, що їх можна використати N. Якщо система є в PATHS, шляхи, що відповідають цьому місцю є найкоротшими.
TENT – список триплетів у вигляді <N,d(N),{Adj(N)}>, де N, d(N) та {Adj(N)} відповідають визначеним в PATHS.
TENT може бути інтуітивно представлений як місце системи в PATHS. Іншими словами, триплет <N,x,{A}> в TENT говорить, що, якщо N є в PATHS, d(N) відповідає x, але N не може бути розміщене в PATHS поки не доведено, що не існує шляхів, коротших за x .
Так само <N,x,{A,B}> в TENT значить, що якщо N є в PATHS, тоді d(N) буде дорівнювати x для маршрутів, що проходять через суміжну вершину A або через суміжну вершину B.
Запропоновано в реальній реалізації таблиці TENT проводити сортування за характеристикою d(N).
3. Висновки
Маршрутизаційні алгоритми реалізовані на різних типах мереж від локальних до глобальних. Широко розповсюдженим є демон Routed з дистриутиву університету Каліфорнії в Берклі він реалізований в протоколі RIP. Також велике значення мають реалізації алгоритму відкриття найкоротшого маршруту для подвійного середовища OSI таTCP/IP в плані знаходження маршрутів між інтер-автономними системами та маршрутизаторами TCP/IP архитектури.