Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab
У статті пропонується метод моделювання процесу маршрутизації в телекомунікаційній мережі на
 базі методу динамічного програмування, досліджено застосування методу при моделюванні маршрутизації
 за одним критерієм оптимальності (пропускна здатність каналу) та за двома критеріями (про...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/7895 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab / Н.Б. Репнікова, К.С. Дорошенко, О.О. Жуковський // Штучний інтелект. — 2009. — № 2. — С. 63-68. — Бібліогр.: 1 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860248520707014656 |
|---|---|
| author | Репнікова, Н.Б. Дорошенко, К.С. Жуковський, О.О. |
| author_facet | Репнікова, Н.Б. Дорошенко, К.С. Жуковський, О.О. |
| citation_txt | Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab / Н.Б. Репнікова, К.С. Дорошенко, О.О. Жуковський // Штучний інтелект. — 2009. — № 2. — С. 63-68. — Бібліогр.: 1 назв. — укр. |
| collection | DSpace DC |
| description | У статті пропонується метод моделювання процесу маршрутизації в телекомунікаційній мережі на
базі методу динамічного програмування, досліджено застосування методу при моделюванні маршрутизації
за одним критерієм оптимальності (пропускна здатність каналу) та за двома критеріями (пропускною
здатністю та ступенем надійності).
|
| first_indexed | 2025-12-07T18:39:37Z |
| format | Article |
| fulltext |
«Штучний інтелект» 2’2009 63
2Р
УДК 621.39:681.5
Н.Б. Репнікова, К.С. Дорошенко, О.О. Жуковський
Національний технічний університет України «КПІ», м. Київ
Метод моделювання процесу
маршрутизації в ІР-мережі за допомогою
мови програмування MatLab
У статті пропонується метод моделювання процесу маршрутизації в телекомунікаційній мережі на
базі методу динамічного програмування, досліджено застосування методу при моделюванні маршрутизації
за одним критерієм оптимальності (пропускна здатність каналу) та за двома критеріями (пропускною
здатністю та ступенем надійності).
Однією з найважливіших задач управління, які розв’язуються в телекомуніка-
ційних мережах, є задача маршрутизації – вибору шляху для інформаційних пакетів,
які надходять у вузол мережі. Маршрутизатор має обрати оптимальний шлях для кож-
ного вхідного пакету інформації, причому оптимальність шляху може визначатися як
одним критерієм, так і кількома. Найбільш використовуваним критерієм оптималь-
ності є так звана «ціна» маршруту, яка є величиною, обернено пропорційною до про-
пускної здатності каналу зв’язку. Обернено пропорційний зв’язок між пропускною
здатністю та ціною маршруту зводить задачу вибору оптимального маршруту для ін-
формаційного пакету до задачі пошуку маршруту мінімальної ціни.
Ціна маршруту між двома сусідніми вузлами мережі обчислюється як округлене
до цілого числа відношення деякого великого числа (наприклад, 108) до пропускної
здатності каналу, вираженої у бітах за секунду. Число, відносно якого розраховується
ціна маршруту, обирається таким чином, щоб ціна каналу з найбільшою пропускною
здатністю дорівнювала 1.
Знаходження оптимального маршруту може виконуватись за допомогою різних
алгоритмів. Так, наприклад, широко розповсюджений протокол OSPF використовує
алгоритм Дійкстри для знаходження оптимального шляху. Нижче пропонується роз-
в’язання задачі маршрутизації за допомогою методу динамічного програмування [1].
Розглянемо приклад телекомунікаційної мережі, яка складається з семи вузлів
(маршрутизаторів), які з’єднані між собою каналами різної пропускної здатності (рис. 1).
100 Мбіт/сек
FastEthernet
Рисунок 1 – Схема мережі
Репнікова Н.Б., Дорошенко К.С., Жуковський О.О.
«Искусственный интеллект» 2’2009 64
2Р
Після перетворення величин пропускних здатностей у ціни каналів схема набу-
де іншого вигляду (рис. 2).
1 1
Рисунок 2 – Схема мережі, представлена у вигляді графа
Для розв’язання задачі маршрутизації інформаційного пакету, наприклад, від
вузла 1 до вузла 7, потрібно описати отриманий граф матрицею сполучень:
999 1 781 391 999 999 999
1 999 999 999 1 999 999
781 999 999 999 48 781 999
391 999 999 999 48 781 999
999 1 48 48 999 999 1
999 999 781 781 999 999 48
999 999 999 999 1 48 999
C
,
де числами 999 позначені неіснуючі сполучення у графі.
Метод моделювання процесу маршрутизації в телекомунікаційній мережі на базі
методу динамічного програмування реалізовано у вигляді програми середовища MATLAB.
Подавши матрицю С на вхід розробленої програми, отримаємо
result(1) =
CurrentVertex: 1
NextVertex: 2
Cost: 1
result(2) =
CurrentVertex: 2
NextVertex: 5
Cost: 1
result(3) =
CurrentVertex: 5
NextVertex: 7
Cost: 1
Отриманий результат буде занесений в таблицю маршрутизації на вузлі 1 і бу-
де застосовуватись для всіх пакетів, адресованих у вузол 7. Маршрутизатор виконає
Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови...
«Штучний інтелект» 2’2009 65
2Р
аналогічні розрахунки для всіх вузлів призначення, які наявні в його базі топології
мережі, побудувавши таким чином таблицю маршрутизації.
Для перевірки результату, отриманого за допомогою розробленої програми, було
використано пакет OPNet, призначений для моделювання телекомунікаційних мереж.
Модель мережі в OPNet наведена на рис. 3.
Рисунок 3 – Модель мережі в пакеті OPNet
Для моделювання вузлів мережі були використані узагальнені блоки ethernet4_
slip8_gtwy, які можуть моделювати роботу довільного ІР-маршрутизатора. Зв’язки
між вузлами мережі змодельовані за допомогою каналів РРР (Point-to-Point Protocol).
Для задання ціни каналу, яка враховується при моделюванні процесу прийняття рі-
шення про маршрутизацію пакетів, використовується атрибут Reference Bandwidth.
На відміну від розробленої програми, пакет OPNet використовує число 1010 як
основу для розрахунку цін каналів. Ця відмінність не повинна впливати на результат
моделювання, оскільки співвідношення між цінами каналів у заданій моделі не змі-
няться.
Для знаходження оптимального (у сенсі швидкості передачі даних) шляху між
вузлами «node_0» та «node_6», які відповідають вершинам 1 та 7 графа, зображеного
на рис. 2, було задано напрям руху трафіка (traffic demand) від вузла «node_0» до вузла
«node_6».
Після запуску моделювання було отримано наступний результат:
Path #1
node_0 --> node_6 Campus Network.node_0
Campus Network.node_0 <-> node_1 Campus Network.node_1
Campus Network.node_1 <-> node_4 Campus Network.node_4
Campus Network.node_4 <-> node_6 Campus Network.node_6
Для пари вузлів «node_0» та «node_6» було обрано шлях node_0 -> node_1 ->
node_4 -> node_6, який збігається зі шляхом, отриманим за допомогою розробленої
програми.
Репнікова Н.Б., Дорошенко К.С., Жуковський О.О.
«Искусственный интеллект» 2’2009 66
2Р
В ситуації, коли маршрутизатор працює одночасно з кількома різними протоко-
лами маршрутизації, для вибору маршрутів використовується додатковий критерій
оптимальності – так звана «адміністративна відстань» (administrative distance), яка
характеризує ступінь надійності отриманого маршруту. Адміністративна відстань є
числовим параметром, який може приймати значення від 0 до 255. Ці значення при-
своюються різним протоколам маршрутизації, причому протоколи, від яких маршрути от-
римують найбільшої достовірності, мають менші значення адміністративної відстані.
Значення 0, 1 та 255 мають окрему роль. Адміністративну відстань вважають рівною
нулю для маршрутів, кінцева адреса яких належить інтерфейсу, який безпосередньо
з’єднаний з даним вузлом мережі. Такі маршрути є найбільш надійними, оскільки
маршрутизатор завжди має найбільш актуальну інформацію про працездатність ка-
налів, які зв’язують його з іншими вузлами мережі. Адміністративною відстанню, яка
дорівнює одиниці, позначаються статичні маршрути – тобто такі, які були введені
адміністратором в таблицю маршрутизації вручну. Значення «255» використовується
для маршрутів, походження яких невідоме. Такі маршрути взагалі не розглядаються
маршрутизатором при виборі шляху для інформаційних пакетів, навіть якщо такий
маршрут є єдиним відомим. Стандартні значення адміністративної відстані для деяких
інших протоколів наведені у табл. 1.
Таблиця 1 – Адміністративні відстані протоколів
Назва протоколу Значення
відстані
Сумарний маршрут EIGRP 5
BGP, який працює поза рамками автономної
системи 20
EIGRP, який працює в рамках автономної
системи 90
IGRP 100
OSPF 110
IS-IS 115
RIP 120
EGP 140
ODR 160
EIGRP, який працює поза рамками автономної
системи 170
BGP, який працює в рамках автономної
системи 200
Причиною різниці в достовірності маршрутів є особливості організації різних
протоколів маршрутизації, а не їх недоліки. Так, наприклад, маршрути, отримані за
протоколом RIP (Routing Information Protocol), вважаються менш достовірними за
отримані за протоколом OSPF тому, що протокол RIP обирає маршрути, використо-
вуючи кількість вузлів на шляху як критерій оптимальності, не беручи до уваги про-
пускну здатність каналів між вузлами.
Адміністративна відстань протоколів не є жорстко заданим параметром, і адмі-
ністратор мережі може змінювати її, якщо потрібно надати перевагу маршрутам одного
або кількох протоколів.
При побудові таблиці маршрутизації адміністративна відстань вважається більш
важливим критерієм, ніж всі інші. Так, маршрутизатор відразу виключає з розгляду
маршрути невідомого походження. Для подальшого аналізу та вибору оптимального
маршруту застосовуються критерії, специфічні для використовуваного протоколу марш-
рутизації (наприклад, пропускна здатність каналів зв’язку).
Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови...
«Штучний інтелект» 2’2009 67
2Р
Для того, щоб описана вище програма могла розв’язувати задачу маршрутизації
з використанням двох критеріїв оптимальності, до формату вхідних даних та алго-
ритму основної процедури потрібно ввести деякі зміни.
Вхідними даними програми будуть дві матриці: матриця сполучень, яка місти-
тиме інформацію про ціни каналів зв’язку між вузлами мережі, та матриця адмініст-
ративних відстаней, яка відображатиме інформацію про протоколи маршрутизації, що
використовуються у мережі.
В алгоритм основної процедури програми потрібно додати урахування адмініст-
ративної відстані при обчисленні значення критерію оптимальності, та перевірку, яка
дозволить виключати з розгляду маршрути, які мають адміністративну відстань, що
дорівнює 255, тобто мають невідоме походження.
Для перевірки правильності роботи програми після внесених змін можна моди-
фікувати схему мережі (рис. 4) таким чином, щоб зменшити вплив пропускної здатності
каналів на вибір оптимального маршруту (рис. 5).
Після внесення змін у мережі з’явилися два шляхи, які відносно мало відрізняю-
ться за пропускною здатністю – один з них проходить через вузли 1 – 3 – 5 – 7,
другий – через вузли 1 – 4 – 5 – 7. Для того, щоб перевірити вплив адміністративної
відстані на вибір оптимального шляху, вважатимемо, що інформацію про канали між
вузлами 1 – 3 та 3 – 5 було отримано за протоколом RIP, а про всі інші – за протоко-
лом OSPF. Така зміна має привести до того, що канали 1 – 3 та 3 – 5, незважаючи на
їх більшу пропускну здатність, матимуть в цілому більше значення критерію оптималь-
ності, ніж канали 1 – 4 та 4 – 5.
Рисунок 4 – Модифікована схема мережі
64
Рисунок 5 – Модифікована схема мережі після перетворення
пропускних здатностей в ціни каналів
Репнікова Н.Б., Дорошенко К.С., Жуковський О.О.
«Искусственный интеллект» 2’2009 68
2Р
Як було вказано вище, вхідними даними програми будуть дві матриці – матриця
сполучень С, що містить інформацію про ціни каналів, та матриця адміністративних
відстаней D:
999 391 48 64 999 999 999
381 999 999 999 48 999 999
48 999 999 999 48 781 999
64 999 999 999 64 781 999
999 48 48 64 999 999 64
999 999 781 781 999 999 48
999 999 999 999 64 48 999
C
999 110 120 110 999 999 999
110 999 999 999 110 999 999
120 999 999 999 120 110 999
110 999 999 999 110 110 999
999 110 120 110 999 999 110
999 999 110 110 999 999 110
999 999 999 999 110 110 999
D
Результатом виконання програми буде наступний маршрут:
result(1) =
CurrentVertex: 1
NextVertex: 4
Cost: 174
result(2) =
CurrentVertex: 4
NextVertex: 5
Cost: 174
result(3) =
CurrentVertex: 5
NextVertex: 7
Cost: 174
В результаті додання адміністративної відстані, як критерію оптимальності, шлях
1 – 3 – 5 – 7 перестав бути оптимальним, незважаючи на більшу пропускну здатність
каналів, які до нього входять.
Таким чином, запропонований метод моделювання процесу маршрутизації на ба-
зі динамічного програмування дозволяє вирішувати двокритеріальну задачу (пропускна
здатність та ступінь надійності) та обирати оптимальний шлях для кожного вхідного
пакету інформації.
Література
1. Чураков Е.П. Оптимальные и адаптивные системы : учеб. пособие для вузов / Чураков Е.П. – М. :
Энергоатомиздат, 1987. – 256 с.
Стаття надійшла до редакції 03.03.2009.
|
| id | nasplib_isofts_kiev_ua-123456789-7895 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:39:37Z |
| publishDate | 2009 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Репнікова, Н.Б. Дорошенко, К.С. Жуковський, О.О. 2010-04-20T13:05:15Z 2010-04-20T13:05:15Z 2009 Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab / Н.Б. Репнікова, К.С. Дорошенко, О.О. Жуковський // Штучний інтелект. — 2009. — № 2. — С. 63-68. — Бібліогр.: 1 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7895 621.39:681.5 У статті пропонується метод моделювання процесу маршрутизації в телекомунікаційній мережі на
 базі методу динамічного програмування, досліджено застосування методу при моделюванні маршрутизації
 за одним критерієм оптимальності (пропускна здатність каналу) та за двома критеріями (пропускною
 здатністю та ступенем надійності). uk Інститут проблем штучного інтелекту МОН України та НАН України Алгоритмическое и программное обеспечение Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab Article published earlier |
| spellingShingle | Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab Репнікова, Н.Б. Дорошенко, К.С. Жуковський, О.О. Алгоритмическое и программное обеспечение |
| title | Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab |
| title_full | Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab |
| title_fullStr | Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab |
| title_full_unstemmed | Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab |
| title_short | Метод моделювання процесу маршрутизації в ІР-мережі за допомогою мови програмування MatLab |
| title_sort | метод моделювання процесу маршрутизації в ір-мережі за допомогою мови програмування matlab |
| topic | Алгоритмическое и программное обеспечение |
| topic_facet | Алгоритмическое и программное обеспечение |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/7895 |
| work_keys_str_mv | AT repníkovanb metodmodelûvannâprocesumaršrutizacíívírmerežízadopomogoûmoviprogramuvannâmatlab AT dorošenkoks metodmodelûvannâprocesumaršrutizacíívírmerežízadopomogoûmoviprogramuvannâmatlab AT žukovsʹkiioo metodmodelûvannâprocesumaršrutizacíívírmerežízadopomogoûmoviprogramuvannâmatlab |