Реферат: Алгоритми маршрутизації в мережах
· адреса : в IP реалізації це має бути IP адреса хоста або мережі;
· шлюз : перший шлюз на цьому маршруті;
· інтерфейс : інтерфейс, що має бути використований, щоб досягти першого шлюза;
· ціна : число, що визначає відстань до комп’ютера-отримувача;
· таймер : проміжок часу з того моменту коли інформація була востаннє оновлена.
На додаток можуть бути додані різні флаги та інша інформація. Таблиця починається з опису об’єктів, що прямо під’єднані до системи. Вона оновлюється на основі інформації, що приходить від сусідніх шлюзів. Найважливіша інформація, якою обмінюються хости та шлюзи міститься в звітах оновлення. Кожний об’єкт, що бере участь в маршрутизації посилає звіти оновлення, що описують таблиці маршрутизації в тому стані, в якому вони знаходяться на даний момент. Можливо визначити оптимальний маршрут користуючись лише інформацією отриманою від сусідніх об’єктів.
Алгоритми вектору відстані базуються на таблиці даючи найкращий маршрут з міркувань ціни (будь-якої характериски,яку можна представити у вигляді суми ребер графу) . Формально, якщо вершини i та j сусідні, тоді ціна d(i,j) рівна ціні ребра між i та j. В нормальному випадку всі об’єкти на даній мережі однакові, d(i,j) однакове для всіх об’єктів даноі мережі і визначає ціну використовування цієї мережі. Щоб дістати ціну всього маршруту, потрібно додати ціни всіх ребер, що складають цей маршрут. Для зручності припустимо, що ціна – додатнє ціле. Нехай D(i,j) визначає ціну кращого маршруту з вершини i до вершини j. Вона має бути визначена для кожного ребра. d(i,j) визначатиме ціни окремих кроків. Формально, нехай d(i,j) визначає ціну маршруту, йдучи прямо з вершини i до вершини j. Це значення дорівнює нескінченності, якщо i та j не сусідні вершини. (Слід зауважити, що d(i,i) - нескінченність. Це так, якщо не брати до уваги, що вершина може мати пряме з’єднання до самої себе). Оскільки ціни адитивні, то можна показати отримання кращого маршруту так :
D(i,i) = 0, для всіх i
D(i,j) = min [d(i,k) + D(k,j)], інакше k
і найкращий маршрут той, що починається з вершини i до тих вершин k, для яких d(i,k) + D(k,j) мінімальне.
Ми можеме обмежити друге рівняння для тих k, що є сусідами i. Для інших d(i,k) нескінченність, тому вони не можуть дати мінімального значення.На основі цього можливо обчислити відстань. Об’єкт i примушує його сусідів k прислати ціну шляху до об’єкту призначення j. Коли i отримує ціну d(k,j) від всіх k, він додає d(k,j) до ціни шляху D(i,k). Потім і порівнює значення від всіх сусідів і вибирає найменше.
Реальні реалізації алгоритму запам’ятовують найкращу ціну й ідентифікацію сусіда, що її надіслав. Інформація заміщається, коли надсилається менша ціна. Це дозволяє обраховувати мінімум, не зберігаючи інформацію від всіх сусідів. Але в випадку, коли інформація надходить від об’єкта, що був записаний в таблиці як найкращий, інформація оновлюється в будь-якому випадку. Механізм визначення найкращого маршруту передбачає крах об’єкту на ділянці цього маршруту. В зв’язку з цим встановлено, що об’єкти мають відсилати оновлену інформаціію кожні 30 секунд. Якщо об’єкт, що дає кращу ціну, не відповідає протягом 180 секунд (враховується можливість втрати пакету), ціна шляху встановлюється в дуже велике значення.
2.2. OSPF, Dual IS-IS : Алгоритм відкриття найкоротшого шляху
2.2.1. Огляд алгоритму.
Алгоритм відкриття найкоротшого шляху використовується як в IP, так і в OSI середовищі. Він має складність О(N2 ).
Основний алгоритм, що будує PATHS з нуля, починає додавання систем з найвигіднішими маршрутами з оглядом на PATHS (не може існувати коротшого маршруту до SELF ). Потім визначається TENT використовуючи локальні таблиці з відомостями про сусідні вершини.
Система не може бути розміщеною в PATHS до тих пір, поки не доведено, що не існує маршруту, коротшого за даний. Коли система N розміщується в PATHS, перевіряється ціна маршруту до кожної вершини M сусідньої до N через саму вершину N. Цей маршрут визначається як сума ціни маршруту до N та ціни ділянки NM. Якщо <M,*,*> розміщений в TENT та нове значення буде більшим, маршрут ігнорується.Якщо <M,*,*> розміщений в TENT та нове значення буде меншим, старий запис заміщується новим. Якщо <M,*,*> розміщений в TENT та нове значення таке ж саме як те, що вже є в TENT то набір {Adj(M)} встановлюється як поєднання старого запису (того, що міститься в TENT) та нового - {Adj(N)}. Якщо M не знаходиться в TENT, то даний маршрут додається в TENT.
Потім алгоритм знаходить триплети <N,x,{Adj(N)}> in TENT з мінімальним x.
2.2.2. Реалізація алгоритму відкриття найкоротшого шляху в DUAL IS-IS середовищі
Крок 0: Встановимо TENT та PATHS як пусті. Встановимо tentlength в 0.
(tentlength – це довжина шляху досліджуваних елементів TENT.)
1) Додамо <SELF,0,W> до PATHS, де SELF – початкова система, W –спеціальна величина, що визначає трафік до SELF що пройдений, включаючи внутрішній процес.
2) Тепер загрузимо TENT локальними даними шляхів (Кожен запис в TENT має бути визначений як маршрутизатор або кінцева система OSI, щоб дозволити правильну перевірку в Кроці 2).
Для всіх суміжних вершин Adj(N) на всіх можливих каналах:
d(N) = ціна маршруту, що проходить через (N)
Adj(N) = кількість вершин сусідніх N.
3) Якщо триплет <N,x,{Adj(M)}> в TENT, то
Якщо x = d(N), то {Adj(M)} := {Adj(M)} U {Adj(N)}.
4) Якщо N – маршрутизатор або кінцева система OSI, і більше не існує суміжних вершин {Adj(M)} то видалимо надлишкову вершину.
5) Якщо x < d(N), нічого.
6) Якщо x > d(N), видалити <N,x,{Adj(M)}> з TENT і додати триплет <N,d(N),{Adj(N)}>.
7) Якщо <N,x,{Adj(M)}> не в TENT, то додати <N,d(N),{Adj(N)}> в TENT.
8) Тепер додаються системи, для яких локальний маршрутизатор не має суміжних вершин, але вони згадані в сусідніх псевдовершинах LSP. Суміжність для таких систем визначається маршрутизатором.