3 Маршрутизація у мережах

3.1 Мета заняття

Закріплення знань методів та алгоритмів маршрутизації у мережах на основі графових і матричних моделей їх топологій; набуття практичних навичок їхнього застосування при вирішенні відповідних задач.

3.2 Організація самостійної роботи студентів

3.2.1. Повторіть методи та алгоритми мережної маршрутизації за конспектом лекцій, літературою [1–4] і наведеними нижче основними теоретичними відомостями.

3.2.2. Дайте відповіді на контрольні запитання.

3.2.3. Розгляньте приклади розв'язання задач.

3.2.4. Розв'яжіть завдання.

3.3 Основні теоретичні відомості

Найпоширеніші методи та алгоритми маршрутизації як процесу вибору оптимальних згідно з певним критерієм шляхів доставки інформації між заданою парою пунктів мережі використовують поняття найкоротших шляхів, які мають мінімальну «вагу» (довжину, кількість транзитних ділянок (ранг), час доставки) або максимальні пропускну здатність, надійність і т.п.

Всі алгоритми вибору найкоротших шляхів базуються на очевидному твердженні: якщо найкоротший шлях від вершини до вершини графа мережі проходить через деяку проміжну вершину , то найкоротші шляхи та довжиною й відповідно є складовими частинами найкоротшого шляху довжиною .

3.3.1 Алгоритм Беллмана-Форда

Основна ідея алгоритму Беллмана-Форда полягає у тому, щоб знайти спочатку «вагу» найкоротших шляхів від вершини-витоку до інших вершин (стоків) за умови, що вони містять не більше однієї дуги, потім «ваги» найкоротших шляхів, за умови, що вони містять не більше 2 дуг і т.д. Найкоротший шлях, за умови, що він містить не більше дуг, називається найкоротшим -шляхом.

Нехай – «вага» найкоротшого -шляху від вузла-витоку до вузла . Вважатимемо, що для вершини «вага» =0 при всіх .

Покроковий опис алгоритму Беллмана-Форда має такий вигляд.

На початковому кроці алгоритму ( =0) встановлюється для всіх .

На наступних кроках алгоритму (при кожному >1) для всіх виконується ітерація Беллмана-Форда:

, (3.1)

де – «вага» дуги між вершинами й .

Алгоритм закінчує роботу, коли значення досягає номера останньої вершини , тобто у найгіршому разі, дерево найкоротших маршрутів має вигляд ланцюжка довжиною ( –1) дуг.

3.3.2 Алгоритм Дейкстри

Зміст алгоритму Дейкстри полягає у наступному. Якщо під час розв’язання задачі вибору найкоротшого шляху від вершини до вершини вже знайдено найкоротші шляхи до деяких вершин графа мережі, то на наступному кроці розв’язання має бути знайдено -у вершину, яка пов'язана з вершиною найкоротшим шляхом.

«Позначимо» вершину та вершин графа, знайдені на попередньому кроці, а також всі ребра, що складають найкоротші шляхи від вершини до цих вершин. Очевидно, що найкоротший шлях від вершини до наступної -ї вершини, який має бути вибраний, повинен проходити «позначеними» вершинами і бути продовженням найкоротшого шляху від вершини до однієї з «позначених» вершин. Тому з усіх «непозначених» вершин як -а може бути обрана лише та, що досяжна принаймні з однієї «позначеної» вершини з використанням шляху рангу 1. Із множини таких вершин залишається і «позначається» та вершина , від якої забезпечується найкоротший шлях до вершини . Якщо , то з тих же причин здійснюється пошук -ї вершини.

У ході виконання алгоритму Дейкстри кожній вершині надається вага , яка дорівнює довжині найкоротшого шляху від вершини до вершини . При цьому покроковий опис алгоритму має такий вигляд.

Крок 1. «Позначимо» вершину й надамо їй вагу , а вагу інших вершин приймемо рівними деякому максимально можливому значенню.

Крок 2. Приймемо .

Крок 3. Для кожної «непозначеної» вершини обчислимо нове значення ваги .

Крок 4. Перевіримо умову: вага менше її максимально можливого значення. Якщо ця умова виконується, то «позначаємо» вершину із мінімальним значенням і переходимо до кроку 5. У протилежному випадку алгоритм закінчує роботу, оскільки найкоротшого шляху від вершини до вершини у графі даної мережі не існує.

Крок 5. Приймемо .

Крок 6. Перевіримо умову: . Якщо ця умова виконується, то най-коротший шлях від вершини до вершини знайдено і до нього входять «позначені» вершини. У протилежному випадку переходимо до кроку 3.

Представлений алгоритм можна використовувати для знаходження найкоротших шляхів від деякої фіксованої вершини до всіх інших вершин, якщо на кроці 6 перевіряти, чи є «непозначені» вершини. За відсутності таких вершин алгоритм закінчує роботу. У протилежному випадку переходимо до кроку 3.

3.3.3 Алгоритм Флойда

Для графа мережі з вершинами алгоритм Флойда дозволяє одержати:

– дистанційну матрицю розмірністю , елементи якої визначають «ваги» найкоротших шляхів між довільними вершинами та ;

– маршрутну матрицю розмірністю , елементи якої визначають вершини, що входять у ці шляхи.

Принцип роботи цього алгоритму полягає у наступному. Спочатку за «вагу» найкоротшого шляху між довільними вершинами та приймається «вага» ребра , яке з'єднує ці вершини. Потім послідовно перевіряються всі інші (проміжні) вершини, що розташовані між і . Якщо «вага» шляху, що проходить через деяку проміжну вершину , менше попереднього значення, то змінній надається нове значення.

Для будь-яких трьох різних вершин , , сформульована умова може бути записана у вигляді нерівності трикутника

. (3.2)

Алгоритм Флойда дозволяє вирішити задачу визначення найкоротших шляхів між всіма вершинами графа мережі за ітерацій.

Позначимо символом оцінку «ваги» найкоротшого шляху з у , яка отримана на -й ітерації. Спосіб її отримання може бути описаний у вигляді тримісної операції:

. (3.3)

Якщо цю операцію виконувати для заданої пари вершин та й усіх інших вершин у порядку зростання номерів , то значення , отримане на останній ітерації, дорівнюватиме «вазі» найкоротшого шляху з вершини у вершину .

Операцію трикутника відповідно до виразу (3.3) потрібно виконувати лише з елементами матриці , які не належать головній діагоналі, базовому рядку і базовому стовпцю.

При одержанні оцінок елементів маршрутної матриці алгоритм починає роботу при . На -й ітерації оцінка може бути отримана зі співвідношення

(3.4)

Таким чином, на кожній -й ітерації ( ) виконується така процедура з використанням оцінок елементів дистанційної матриці , отриманих на попередній ітерації:

Крок 1. Виключимо з матриці елементи -го базового рядка та -го базового стовпця.

Крок 2. Для кожного елемента в інших рядках і стовпцях матриці , починаючи з першого в її лівому верхньому куті, перевіримо виконання нерівності (3.2) у формулі

(3.5)

Якщо нерівність (3.5) не виконується, виберемо нові значення й , після чого знову повторимо крок 2.

Якщо нерівність (3.5) виконується, надамо змінній значення , а змінній значення .

Після перевірки нерівності (3.5) для всіх значень та знову переходимо до кроку 1 і так продовжуємо до останньої -ї ітерації.

Номери вершин, що входять у найкоротший шлях від вершини до вершини :

визначаються елементами маршрутної матриці за правилом

3.3.4 Задача розміщення центрального вузла у централізованій топології мережі

Ця задача припускає, що відома топологія мережі у вигляді графа . Як центральний вузол мережі доцільно вибирати таку вершину з їхньої множини V, для якої сума «ваги» шляхів до всіх інших вершин є мінімальною. Така вершина графа називається його медіаною. Поняття медіани графа пов'язане з поняттями внутрішніх і зовнішніх передаточних чисел вершин і з поняттями внутрішньої й зовнішньої медіани графів. Внутрішнім передаточним числом деякої вершини називається величина, яка визначається у вигляді:

, (3.6)

де – довжина шляху, який починається у і закінчується у деякій вершині ; – «вага» вершини , що характеризує його значимість для мережі. Якщо всі вершини рівнозначні, то і їхні «ваги» є однаковими.

Зовнішнім передаточним числом вершини деякої вершини називається величина, яка визначається у вигляді:

, (3.7)

де – «вага» шляху з початком у і кінцем у .

Внутрішня медіана графа – вершина, для якої мінімальне внутрішнє передаточне число, а зовнішня – для якої мінімальне зовнішнє передаточне число.

Медіана графа – вершина, для якої мінімальна сума внутрішніх і зовнішніх передаточних чисел.

Для визначення передаточних чисел можна скористатися алгоритмом маршрутизації Флойда, який визначає дистанційну матрицю «ваг» найкоротших колій між вершинами . Потім обирається деякий рядок цієї матриці та кожне значення елемента цього рядка помножується на вагу вершини, що відповідає стовпцю, в якому перебуває цей елемент, і отримані добутки складаються. У результаті отримується внутрішнє передаточне число вершини, яка відповідає розглянутому рядку. Аналогічно за стовпцями матриці визначається зовнішнє передаточне число.