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

Алгоритми вектору відстані основані на обміні малої кількості інформації. Кожний об’єкт (шлюз або хост), що приймає участь в маршрутизації, має тримати інформацію про всі комп’ютери системі. Кожний запис в таблиці маршрутизації включає наступний шлюз, на який дані, напрямлені до об’єкту, мають бути відправлені. До того ж він має містити значення, що характеризує загальну відстань до об’єкту. Відстань - це узагальнена характеристика, що може відображати швидкість передачі даних, грошову вартість передачі тощо. Алгоритми вектору вістані дістали свою назву від того, що вони можуть обчислити оптимальний маршрут коли змінюється лише список відстаней. Крім того, має місце обмін маршрутизаційною інформацією між безпосередньо зв’язаними об’єктами, тобто елементами спільної мережі. Записи в таблиці маршрутизації мають містити таку інформацію про комп’ютер-отримувач:

•адреса : в 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: Алгоритм відкриття найкоротшого шляху