Routing technology based on virtualization software-defined networking concept
One of the main characteristics of the digital revolution is the acceleration of change. The technologies that have fueled the digital revolution over the past decades are experiencing increasingly rapid innovation cycles. For today, a substantial growth of amount of users, devices, applications and...
Gespeichert in:
| Datum: | 2024 |
|---|---|
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2024
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/655 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-655 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/32/9d0b6e4fe83dcbccd8bee8b09f69d832.pdf |
| spelling |
pp_isofts_kiev_ua-article-6552025-02-15T14:58:03Z Routing technology based on virtualization software-defined networking concept Технологія маршрутизації на основі концепцій віртуалізації та програмно-конфігурованих мереж Kravchenko, Yu.V. Herasymenko, K.V. Starkova, O.V. Bulgakova, A.Y. Routing method; static routing; dynamic routing; NFV; SDN UDC 004.942 Метод маршрутизації; статична маршрутизація; динамічна маршрутизація; NFV; SDN УДК 004.942 One of the main characteristics of the digital revolution is the acceleration of change. The technologies that have fueled the digital revolution over the past decades are experiencing increasingly rapid innovation cycles. For today, a substantial growth of amount of users, devices, applications and traffic has presented new challenges to service providers. The SDN paradigm emerged to address some of these emerging challenges. SDN simplifies network management and allows automated network configuration on demand with optimal use of network resources. The work is devoted to the present networks research and the identification of opportunities for the implementation of virtualization of network functions in the context of SDN and NFV concepts. Because these are two new technological trends that are transforming network management. Together, they simplify the provisioning of network resources and provide greater network flexibility.Prombles in programming 2024; 2-3: 343-350 На сьогоднішній день через значне збільшення кількості користувачів, пристроїв, програм і трафіку перед постачальниками послуг постали нові виклики. Парадигма SDN (програмно-конфігурована мережа) виникла для вирішення деяких із цих нових проблем. SDN спрощує керування мережею та дозволяє автоматизовано конфігурувати мережу на вимогу з оптимальним використанням мережевих ресурсів. Робота присвячена дослідженню сучасних мереж та виявленню можливостей реалізації віртуалізації мережевих функцій у контексті концепцій SDN та NFV, адже це дві нові технологічні тенденції, які трансформують мережевий менеджмент. Разом вони спрощують надання мережевих ресурсів і забезпечують більшу гнучкість мережі. Цей підхід створює динамічні, гнучкі та масштабовані мережі, які використовують віртуалізовану інфраструктуру сучасних центрів обробки даних.Prombles in programming 2024; 2-3: 343-350 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2024-12-17 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/655 10.15407/pp2024.02-03.343 PROBLEMS IN PROGRAMMING; No 2-3 (2024); 343-350 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2024); 343-350 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2024); 343-350 1727-4907 10.15407/pp2024.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/655/707 Copyright (c) 2024 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-02-15T14:58:03Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
Routing method static routing dynamic routing NFV SDN UDC 004.942 |
| spellingShingle |
Routing method static routing dynamic routing NFV SDN UDC 004.942 Kravchenko, Yu.V. Herasymenko, K.V. Starkova, O.V. Bulgakova, A.Y. Routing technology based on virtualization software-defined networking concept |
| topic_facet |
Routing method static routing dynamic routing NFV SDN UDC 004.942 Метод маршрутизації статична маршрутизація динамічна маршрутизація NFV SDN УДК 004.942 |
| format |
Article |
| author |
Kravchenko, Yu.V. Herasymenko, K.V. Starkova, O.V. Bulgakova, A.Y. |
| author_facet |
Kravchenko, Yu.V. Herasymenko, K.V. Starkova, O.V. Bulgakova, A.Y. |
| author_sort |
Kravchenko, Yu.V. |
| title |
Routing technology based on virtualization software-defined networking concept |
| title_short |
Routing technology based on virtualization software-defined networking concept |
| title_full |
Routing technology based on virtualization software-defined networking concept |
| title_fullStr |
Routing technology based on virtualization software-defined networking concept |
| title_full_unstemmed |
Routing technology based on virtualization software-defined networking concept |
| title_sort |
routing technology based on virtualization software-defined networking concept |
| title_alt |
Технологія маршрутизації на основі концепцій віртуалізації та програмно-конфігурованих мереж |
| description |
One of the main characteristics of the digital revolution is the acceleration of change. The technologies that have fueled the digital revolution over the past decades are experiencing increasingly rapid innovation cycles. For today, a substantial growth of amount of users, devices, applications and traffic has presented new challenges to service providers. The SDN paradigm emerged to address some of these emerging challenges. SDN simplifies network management and allows automated network configuration on demand with optimal use of network resources. The work is devoted to the present networks research and the identification of opportunities for the implementation of virtualization of network functions in the context of SDN and NFV concepts. Because these are two new technological trends that are transforming network management. Together, they simplify the provisioning of network resources and provide greater network flexibility.Prombles in programming 2024; 2-3: 343-350 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2024 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/655 |
| work_keys_str_mv |
AT kravchenkoyuv routingtechnologybasedonvirtualizationsoftwaredefinednetworkingconcept AT herasymenkokv routingtechnologybasedonvirtualizationsoftwaredefinednetworkingconcept AT starkovaov routingtechnologybasedonvirtualizationsoftwaredefinednetworkingconcept AT bulgakovaay routingtechnologybasedonvirtualizationsoftwaredefinednetworkingconcept AT kravchenkoyuv tehnologíâmaršrutizacíínaosnovíkoncepcíjvírtualízacíítaprogramnokonfígurovanihmerež AT herasymenkokv tehnologíâmaršrutizacíínaosnovíkoncepcíjvírtualízacíítaprogramnokonfígurovanihmerež AT starkovaov tehnologíâmaršrutizacíínaosnovíkoncepcíjvírtualízacíítaprogramnokonfígurovanihmerež AT bulgakovaay tehnologíâmaršrutizacíínaosnovíkoncepcíjvírtualízacíítaprogramnokonfígurovanihmerež |
| first_indexed |
2025-07-17T10:08:07Z |
| last_indexed |
2025-07-17T10:08:07Z |
| _version_ |
1850411327298732032 |
| fulltext |
343
Програмування для комп'ютерних мереж та інтернет
УДК 004.942 http://doi.org/10.15407/pp2024.02-03.343
Ю. В. Кравченко, К. В. Герасименко, О. В. Старкова, А. Ю. Булгакова
ТЕХНОЛОГІЯ МАРШРУТИЗАЦІЇ НА ОСНОВІ
КОНЦЕПЦІЙ ВІРТУАЛІЗАЦІЇ ТА ПРОГРАМНО-
КОНФІГУРОВАНИХ МЕРЕЖ
На сьогоднішній день через значне збільшення кількості користувачів, пристроїв, програм і трафіку
перед постачальниками послуг постали нові виклики. Парадигма SDN (програмно-конфігурована ме-
режа) виникла для вирішення деяких із цих нових проблем. SDN спрощує керування мережею та до-
зволяє автоматизовано конфігурувати мережу на вимогу з оптимальним використанням мережевих
ресурсів.
Робота присвячена дослідженню сучасних мереж та виявленню можливостей реалізації віртуалізації
мережевих функцій у контексті концепцій SDN та NFV, адже це дві нові технологічні тенденції, які
трансформують мережевий менеджмент. Разом вони спрощують надання мережевих ресурсів і забез-
печують більшу гнучкість мережі. Цей підхід створює динамічні, гнучкі та масштабовані мережі, які
використовують віртуалізовану інфраструктуру сучасних центрів обробки даних.
Ключові слова: Метод маршрутизації, статична маршрутизація, динамічна маршрутизація, NFV, SDN
Yu. V. Kravchenko, K. V. Herasymenko, O. V. Starkova, A. Y. Bulgakova
ROUTING TECHNOLOGY BASED
ON VIRTUALIZATION SOFTWARE-DEFINED
NETWORKING CONCEPTІ
One of the main characteristics of the digital revolution is the acceleration of change. The technologies that
have fueled the digital revolution over the past decades are experiencing increasingly rapid innovation cycles.
For today, a substantial growth of amount of users, devices, applications and traffic has presented new chal-
lenges to service providers. The SDN paradigm emerged to address some of these emerging challenges. SDN
simplifies network management and allows automated network configuration on demand with optimal use of
network resources.
The work is devoted to the present networks research and the identification of opportunities for the imple-
mentation of virtualization of network functions in the context of SDN and NFV concepts. Because these are
two new technological trends that are transforming network management. Together, they simplify the provi-
sioning of network resources and provide greater network flexibility.
Keywords: Routing method, static routing, dynamic routing, NFV, SDN
Вступ
Мережеві технології розвиваються
досить швидкими темпами. Це пов'язано з
широким використанням інформаційних
технологій та телекомунікаційних систем
та мереж в різних сферах людського життя.
Зазвичай для виконання своїх функцій на
мережевих пристроях реалізовувалися ста-
ндартні протоколи та сервіси [1]. Але з ча-
сом виявились їхні недоліки та невідповід-
ність сучасним викликам мереж (зростаюча
кількість користувачів, сервісів, пристроїв і
каналів зв’язку, вимоги до мереж) [2]. Нові
тенденції в розвитку мереж також з'явилися
в напрямку реалізації концепції програмо-
ваних мереж SDN і віртуалізації мережевих
функцій. Тож постало завдання вдоскона-
лення існуючих і створення принципово
нових протоколів і технологій, здатних по-
вністю задовольнити потреби перспектив-
них інформаційних комунікаційних мереж
і систем [3, 4].
Зростаюче використання віртуаліза-
ції мережевих функцій є одним із основних
факторів, що сприяють прийняттю SDN.
Технології SDN і NFV доповнюють одна
одну, при цьому NFV пропонує набагато бі-
© Ю. В. Кравченко, К. В. Герасименко, О. В. Старкова, А. Ю. Булгакова, 2024
ISSN 1727-4907. Проблеми програмування. 2024. №2-3
344
Програмування для комп'ютерних мереж та інтернет
льше послуг, які обробляються в SDN. Тоді
як NFV зосереджується на вдосконаленні
фактичних мережевих служб, які регулю-
ють потоки даних, SDN зосереджується на
площині керування [5].
Тому метою роботи було розроб-
лення середовища (системи моделювання)
для реалізації різноманітних мережевих фу-
нкцій і протокольних рішень. У майбут-
ньому це дозволить проводити експериме-
нтальні дослідження, а в перспективі впро-
ваджувати розроблені технології та прото-
коли в контексті SDN [2, 3].
1. Технологія маршрутизації на
основі концепцій
NFV та SDN
В основу роботи покладено маршру-
тизатор – традиційний мережевий прист-
рій. Основні функції маршрутизатора – це
вибір оптимальних маршрутів у віддалені
мережі, заповнення таблиці маршрутизації
та пересилання пакетів між мережами [5].
В процесі маршрутизації маршрути-
затори розглядають кілька альтернативних
маршрутів для досягнення одного пункту
призначення. Ці альтернативи є результа-
том резервування, вбудованого в більшість
проєктів мереж.
Для розроблення системи моделю-
вання були використані:
− мова програмування Python;
− модулі ipaddress, threading,
socket, json, tabulate (для Python).
Операція моделювання маршрутиза-
торів складається з багатьох об'єктів, які
взаємодіють один з одним [2].
Об’єкт Simulation потрібен для збе-
рігання об’єктів маршрутизатора. Він може
запускати всі маршрутизатори разом за до-
помогою методу start_routers і виводити
таблицю інтерфейсу зі статусами та іншою
інформацією про об’єкти інтерфейсу
print(simulation).
Рис. 1. Клас Simulation
Маршрутизатор є основним об'єк-
том моделювання. У ньому зберігаються ін-
терфейси, необхідні для обміну інформа-
цією між маршрутизаторами. Маршрутиза-
тор також додає до пам’ті таблицю марш-
рутизації та інші дані про маршрутизатор.
Рис. 2. Клас Router
Об'єкт Router має такі публічні ме-
тоди: set_protocol, необхідний для встанов-
лення об'єкта протоколу динамічної марш-
рутизації, який буде працювати на маршру-
тизаторі; has_ip, потрібний для перевірки
наявності певної IP-адреси в роутері, який
передано методу; message_to_interface, не-
обхідний для надсилання повідомлення з
певного інтерфейсу [6]. Потрібно передати
номер інтерфейсу, з якого буде відправлено
повідомлення, і саме повідомлення;
message_to_ip, необхідний для надсилання
повідомлення на певну IP-адресу. Слід пе-
редати IP-адресу і саме повідомлення, яке
буде відправлено. Потім маршрутизатор
345
Програмування для комп'ютерних мереж та інтернет
спробує знайти шлях для надсилання в під-
ключених інтерфейсах або таблиці маршру-
тизації; message_to_broadcast, який потрі-
бен для надсилання повідомлення на широ-
комовний порт. Усі інтерфейси з однако-
вою широкомовною адресою отримають це
повідомлення; set_default_route, який пот-
рібен для встановлення маршруту за замов-
чуванням. Необхідно передати IP-адресу і
номер інтерфейсу, з якого здійснюється до-
ступ до мережі, і метрику. Метрика потрі-
бна, щоб знайти найшвидший спосіб наді-
слати повідомлення; add_route, необхідний
для встановлення маршруту до певної ме-
режі [2-6]. Потрібно відправити IP-адресу
та маску підмережі для віддаленої мережі, а
також IP-адресу та н
омер інтерфейсу, з якого здійснюється дос-
туп до віддаленої мережі, і метрику; start,
який необхідний для запуску маршрутиза-
тора. Після цього маршрутизатор починає
слухати широкомовний порт і працювати
протокол динамічної маршрутизації.
Об’єкт Interface — це інтерфейс ма-
ршрутизатора, який може взаємодіяти з ін-
шими інтерфейсами для обміну даними.
Рис. 3. Клас Interface
Він має такі методи: get_ip, який
повертає IP-адресу інтерфейсу; get_conn,
який повертає об’єкт з’єднання інтерфейсу
з іншим інтерфейсом; connect_to_router,
який запускає серію дій для встановлення
з'єднання з іншим інтерфейсом;
wait_connection, який починає чекати
відповіді від іншого інтерфейсу для
підтвердження встановлення з'єднання;
accept_connection, який підтверджує
підключення до іншого інтерфейсу;
listen_conn, який очікує встановлення
з'єднання з іншим інтерфейсом.
Для встановлення з'єднання між
двома інтерфейсами необхідно:
1. Викликати метод інтерфейсу
connect_to_router на першому інтерфейсі та
передати IP-адресу віддаленого
інтерфейсу, до якого створюється
з’єднання [7, 8]. Після цього перший
інтерфейс очікує на встановлення
з'єднання.
2. Викликати метод accept_connection
на другому інтерфейсі, до якого
підключений перший інтерфейс, і передати
адресу першого інтерфейсу, який хоче
підключитися, і його порт для підключення
інтерфейсів (local_port) [4-8].
RoutingProtocol – це абстрактний
клас для створення протоколів динамічної
маршрутизації, він визначає основні
методи, які повинні бути присутніми у всіх
протоколах динамічної маршрутизації.
RIP – це об’єкт, створений для
демонстрації організації та роботи
протоколів динамічної маршрутизації в
моделюванні. Він має наступні методи:
new_message, необхідний для обробки
отриманого повідомлення, адресованого
протоколу динамічної маршрутизації;
get_routing_table_to_send, який необхідний
для обробки таблиці маршрутизації для її
подальшої відправки іншим
маршрутизаторам; send_route, необхідний
для відправки таблиці маршрутизації,
підготовленої методом
get_routing_table_to_send, з усіх
інтерфейсів маршрутизатора (всім сусідам
по мережі); бігун, який потрібен для
відправлення повідомлень кожні n секунд;
start, необхідний для запуску протоколу для
роботи. Після виконання запускається цикл
за допомогою методу runner, який надсилає
таблицю маршрутизації всім сусідам
маршрутизатора в мережі кожні n секунд.
2. Тестування роботи
розробленої технології
маршрутизації
Для старту симуляції, потрібно ство-
рити всі необхідні об'єкти. Щоб створити
списки з об’єктів інтерфейсу, потрібно пе-
редати такі параметри, як номер інтер-
фейсу, порт інтерфейсу, порт ширини
346
Програмування для комп'ютерних мереж та інтернет
смуги інтерфейсу та об’єкт IPv4Interface
для запису IP-адреси.
Далі потрібно викликати метод
об’єкта симуляції, який створить і додасть
маршрутизатори до симуляції. Для цього
вам потрібно передати назву маршрутиза-
тора та інтерфейсів, створених на поперед-
ньому кроці [4-8]. Можна створити скільки
завгодно маршрутизаторів, але потрібно
подумати про створення інтерфейсів, тому
що симуляція буде працювати правильно
лише з правильно створеними парамет-
рами, коли жодні дані, крім широкомов-
ного порту, не повторюються між інтерфей-
сами.
Після цього ми запускаємо всі мар-
шрутизатори і викликаємо метод
message_to_broadcast на всіх маршрутиза-
торах. Це необхідно для автоматичного під-
ключення інтерфейсів з одним і тим же ши-
рокомовним портом один до одного.
Для обміну інформацією між марш-
рутизаторами симуляція використовує про-
грамний інтерфейс для забезпечення об-
міну даними між процесами (сокети) [4-8].
Для роботи сокетів потрібні мере-
жеві порти, тому під час симуляції їх потрі-
бно вказати для кожного інтерфейсу. Со-
кети використовуються замість другого рі-
вня моделі OSI і дозволяють створювати
сокет-з'єднання між двома програмними
об'єктами та обмінюватися даними між
ними [4-8].
В об’єкті інтерфейсу є широкомовні
сокети, які слухають і передають дані на
один порт.
Під час створення з’єднання між
двома інтерфейсами ми створюємо сокет
між портами цих інтерфейсів – з’єднання,
яке дозволяє надсилати дані з будь-якого з
цих двох інтерфейсів і отримувати їх на ін-
шому інтерфейсі.
Процес підключення інтерфейсів до
розетки – підключення може виглядати так:
1. Є кілька маршрутизаторів, деякі з ін-
терфейсів яких використовують один і той
самий широкомовний порт. Як у прикладі з
наступного рисунка.
Рис. 4. Стан перед початком утворення
сокетів – з’єднань
2. Далі один із інтерфейсів надсилає
повідомлення широкомовному сокету про
те, що він хоче встановити з’єднання.
3. Далі інший інтерфейс отримує це
повідомлення і, якщо він вільний, тобто ще
не підключений до іншого інтерфейсу, від-
повідає згодою.
4. Після цього створюється з’єднання
на кожному інтерфейсі (сокет). Відтепер ці
інтерфейси з’єднані один з одним і можуть
обмінюватися даними через створений со-
кет – з’єднання.
Усі надіслані дані інкапсулюються в
аналогові пакети, які виглядають так:
− Пакет для звичайного повідомлення
через сокет - з'єднання виглядає так:
data_packet = {"src_ip": "ip", "dst_ip":
"ip", "data": "message"}
− Пакет для широкомовного повідом-
лення, виглядає так: broadcast_packet =
{"src_ip": "ip", "src_port": "port", "data":
"message"}
У протоколі динамічної маршрути-
зації RIP дані упаковані в такий пакет:
rip_packet = {'type': 'RIP', 'routing_table':
None}
Коли з'єднання встановлено між
двома інтерфейсами, повідомлення може
бути надіслано з певного інтерфейсу, потім
це повідомлення буде отримано на іншому
інтерфейсі та, за необхідності, оброблено
[4-8].
На даний момент немає додатків, які б
дозволяли писати власні алгоритми динамі-
чної маршрутизації мовою програмування
Python. Для підключення власного коду як
протоколу динамічної маршрутизації до си-
муляції, мають бути виконані наступні
умови: створений клас динамічної маршру-
тизації має успадковуватись від абстракт-
ного класу RoutingProtocol; створений клас
повинен мати два методи, які абстрактно
347
Програмування для комп'ютерних мереж та інтернет
визначені в класі RoutingProtocol. Можна
взяти створений клас RIP як приклад і на-
писати свої протоколи на його основі.
Практичне дослідження
розробленої технології
маршрутизації
Практичне значення розробленої те-
хнології маршрутизації полягає в можливо-
сті впровадження результатів моделювання
(математичного, імітаційного) за допомо-
гою розробленої технології. Це дозволяє
практично реалізувати перспективні ме-
тоди маршрутизації, не змінюючи реальні
протокольні рішення (що мають досить ба-
гато недоліків і не відображають особливо-
стей сучасних мереж, тобто є застарілими).
Як приклад моделі маршрутизації
можна використати вирішення задачі мар-
шрутизації з метрикою протоколу RIP у фо-
рмі задачі булевого програмування з вико-
ристанням засобів пакета Matlab [9].
Постановка задачі маршрутизації
виглядає наступним чином. Дано:
− кількість вузлів у мережі (m);
− кількість каналів зв’язку в мережі
(n);
−
− вузол-відправник пакетів;
− вузол-одержувач пакетів;
− інтенсивність трафіку (r), що надхо-
дить до мережі;
− пропускні здатності каналів зв’язку;
− метрики каналів зв’язку (f).
Необхідно визначити:
− "найкоротший" шлях від вузла-відп-
равника до вузла-одержувача через канал
зв'язку модельованої мережі в межах обра-
ної метрики;
− сформувати залежність кількості
шляхів, що використовуються в процесі ма-
ршрутизації, від щільності трафіку, що на-
дходить до мережі;
− пропускну здатність напрямку зв'я-
зку від вузла-відправника до вузла-одержу-
вача відповідно до обраної моделі маршру-
тизації.
Опис задачі маршрутизації як за-
дачі булевого програмування, викорис-
товуючи метрики протоколу RIP v.1
Кількість каналів зв’язку в мережі
(n) визначає розмір вектора x, координати
𝑥𝑥𝑖𝑖,𝑗𝑗 якого частку трафіку в каналах зв'язку
між i-м та j-м вузлами. Розмір метричного
вектора f також відповідає кількості каналів
зв’язку в мережі (n), а його координати 𝑓𝑓𝑖𝑖,𝑗𝑗
характеризують метрику каналів зв’язку
між i-м та j-м вузлами.
Для реалізації маршрутизації на ко-
ординати вектора x накладаються наступні
обмеження
𝑥𝑥𝑖𝑖,𝑗𝑗 ∈ {0,1} (𝑖𝑖, 𝑗𝑗 = 1, 𝑚𝑚̅̅ ̅̅ ̅̅ ; 𝑖𝑖 ≠ 𝑗𝑗), (1)
тобто змінна 𝑥𝑥𝑖𝑖,𝑗𝑗 може приймати тільки два
значення:
− 1, якщо трафік проходить через канал
(i,j);
− 0, в іншому випадку.
Булеве значення змінної (1) гарантує
відсутність відхилень у потоках вздовж ме-
режевого шляху, тобто, весь трафік переда-
ється по єдиному шляху.
У першому випадку кожному каналу
зв’язку присвоюється метрика, рівна 1
(𝑓𝑓𝑖𝑖,𝑗𝑗 = 1, ; 𝑖𝑖, 𝑗𝑗 = 1, 𝑚𝑚̅̅ ̅̅ ̅̅ ; 𝑖𝑖 ≠ 𝑗𝑗), що відпові-
дає знаходженню шляху з мінімальною кі-
лькістю ретрансляцій (fval) між заданою па-
рою вузлів, як у протоколіv.1.
У процесі розв’язання задачі марш-
рутизації необхідно забезпечити виконання
умов захисту потоку для кожного вузла ме-
режі і для мережі в цілому
{
∑ 𝑥𝑥𝑖𝑖,𝑗𝑗𝑗𝑗:(𝑖𝑖,𝑗𝑗) − ∑ 𝑥𝑥𝑗𝑗,𝑖𝑖𝑗𝑗:(𝑗𝑗,𝑖𝑖) = 1 − для вузла-відправника
∑ 𝑥𝑥𝑖𝑖,𝑗𝑗𝑗𝑗:(𝑖𝑖,𝑗𝑗) − ∑ 𝑥𝑥𝑗𝑗,𝑖𝑖𝑗𝑗:(𝑗𝑗,𝑖𝑖) = 0 − для транзитних вузлів
∑ 𝑥𝑥𝑖𝑖,𝑗𝑗𝑗𝑗:(𝑖𝑖,𝑗𝑗) − ∑ 𝑥𝑥𝑗𝑗,𝑖𝑖𝑗𝑗:(𝑗𝑗,𝑖𝑖) = −1 − для вузла-одержувача
(2)
Крім умови збереження потоку (2)
повинна також виконуватися умова уник-
нення перевантаження тракту зв'язку
𝑟𝑟 ∙ 𝑥𝑥𝑖𝑖,𝑗𝑗 ≤ 𝑐𝑐𝑖𝑖,𝑗𝑗 𝑖𝑖, 𝑗𝑗 = 1, 𝑛𝑛̅̅ ̅̅ ̅, 𝑖𝑖 ≠ 𝑗𝑗, (3)
де 𝑐𝑐𝑖𝑖,𝑗𝑗 – пропускна здатність каналу
зв’язку між i-м та j-м вузлами.
Розв’язання задач маршрутизації в
сучасних мережних протоколах, як пра-
вило, зводиться до розв’язання задачі по-
шуку найкоротшого шляху в мережі, яка
визначає структуру системи зв’язку. Задача
пошуку найкоротшого шляху в мережі фо-
рмується як задача булевого програму-
вання, для її розв’язання використовувався
інструментарій «Optimization Toolbox» па-
348
Програмування для комп'ютерних мереж та інтернет
кета MatLab, представлений підпрограмою
«bintprog».
За змістом рівняння (1), під час роз-
в'язання задачі булевого програмування не-
обхідно мінімізувати цільову функцію, ви-
ражену у лінійній формі min
𝑥𝑥
𝑓𝑓𝑡𝑡 𝑥𝑥 при вико-
нанні ряду умов, представлених у вигляді
обмежень рівнянь і нерівностей
𝐴𝐴 ∙ 𝑥𝑥 ≤ 𝑏𝑏; 𝐴𝐴𝐴𝐴𝐴𝐴 ∙ 𝑥𝑥 = 𝑏𝑏𝐴𝐴𝐴𝐴, де f, x, b,
beq – вектори, A і Aeq – матриці відповідної
розмірності.
Середовище MatLab допускає насту-
пні основні синтаксичні варіанти команд
виклику підпрограми «bintprog»:
1. [𝑥𝑥, 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓] = 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏(𝑓𝑓, 𝐴𝐴, 𝑏𝑏) –
розв’язок 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 = min
𝑥𝑥
𝑓𝑓𝑡𝑡 𝑥𝑥 при 𝐴𝐴 ∙ 𝑥𝑥 ≤ 𝑏𝑏.
2. [𝑥𝑥, 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓] =
𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏(𝑓𝑓, 𝐴𝐴, 𝑏𝑏, 𝐴𝐴𝐴𝐴𝐴𝐴, 𝑏𝑏𝐴𝐴𝐴𝐴) – розв’язок
𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 = min
𝑥𝑥
𝑓𝑓𝑡𝑡 𝑥𝑥 при 𝐴𝐴𝐴𝐴𝐴𝐴 ∙ 𝑥𝑥 = 𝑏𝑏𝐴𝐴𝐴𝐴. У випа-
дку, якщо умов у вигляді нерівностей не-
має, то A=[] та b=[].
Для опису задачі маршрутизації у
формалізмі середовища MatLab умова збе-
реження потоку (2) повинна бути виражена
у вигляді векторної матриці: 𝐴𝐴𝐴𝐴𝐴𝐴 ∙ 𝑥𝑥 = 𝑏𝑏𝐴𝐴𝐴𝐴.
Таким чином матриця Aeq має розмірність
𝑚𝑚 × 𝑛𝑛, а її координати набувають значення
{−1; 0; 1} наступним чином
(𝑗𝑗 = 1,𝑚𝑚̅̅ ̅̅ ̅̅ , 𝑏𝑏 = 1, 𝑛𝑛̅̅ ̅̅ ̅):
𝑓𝑓𝑗𝑗𝑗𝑗 = 1, якщо i-й канал зв'язку йде
від із j-го вузла;
𝑓𝑓𝑗𝑗𝑗𝑗 = −1, якщо i-й канал зв'язку вхо-
дить у j-й вузол;
𝑓𝑓𝑗𝑗𝑗𝑗 = 0 , якщо i-й канал зв'язку не су-
проводжує j-й вузл.
Розмір вектора beq відповідає кіль-
кості вузлів у мережі (m), а його координати
генеруються наступним чином (𝑗𝑗 = 1,𝑚𝑚̅̅ ̅̅ ̅̅ ):
𝑏𝑏𝐴𝐴𝐴𝐴𝑗𝑗 = 1, якщо i-й вузол є відправ-
ником пакетів;
𝑏𝑏𝐴𝐴𝐴𝐴𝑗𝑗 = −1, якщо i-й вузол є одержу-
вачем пакетів;
𝑏𝑏𝐴𝐴𝐴𝐴𝑗𝑗 = 0, якщо i-й вузол є ретранс-
лятором.
Умови (3) також повинні бути вира-
жені у вигляді векторної матриці з нерівні-
стю 𝐴𝐴 ∙ 𝑥𝑥 ≤ 𝑏𝑏.
Приклад метричної задачі марш-
рутизації для протоколу RIP v.1, складе-
ної та розв’язаної в середовищі Matlab.
Нехай структура мережі та пропус-
кна здатність каналів зв’язку показані на
рис.5. Загальне число вузлів у мережі дорі-
внює п'яти (m = 5), а кількість каналів
зв’язку – шести ( n = 6). Тоді вузол-відпра-
вник пакетів – 1, а вузол-приймач – 5.
Рис. 5. Приклад змодельованої ме-
режевої структури
Сформуємо вектор x і вектор метрик
f :
𝑥𝑥 =
[
𝑥𝑥1,2
𝑥𝑥1,3
𝑥𝑥2,3
𝑥𝑥2,5
𝑥𝑥3,4
𝑥𝑥4,5]
𝑓𝑓 =
[
𝑓𝑓1,2𝑓𝑓1,3
𝑓𝑓2,3
𝑓𝑓2,5
𝑓𝑓3,4
𝑓𝑓4,5]
=
[
11
1
1
1
1]
.
Сформулюємо умови збереження
потоку вузлів мережі (2):
{
𝑥𝑥1,2 + 𝑥𝑥1,3 = 1;
−𝑥𝑥1,2 + 𝑥𝑥2,3 + 𝑥𝑥2,5 = 0;
−𝑥𝑥1,3 − 𝑥𝑥2,3 + 𝑥𝑥3,4 = 0;
−𝑥𝑥3,4 + 𝑥𝑥4,5 = 0;
−𝑥𝑥2,5 − 𝑥𝑥4,5 = −1.
Сформуємо матрицю Aeq і вектор
beq:
𝐴𝐴𝐴𝐴𝐴𝐴 =
[
1 1 0 0 0 0
-1 0 1 1 0 0
0 -1 -1 0 1 0
0 0 0 0 -1 1
0 0 0 -1 0 -1]
; 𝑏𝑏𝐴𝐴𝐴𝐴 =
[
10
0
0
-1]
.
Сформалізуємо умови запобігання перева-
нтаженню каналів зв’язку (3):
{
𝑏𝑏 ∙ 𝑥𝑥1,2 ≤ 𝑐𝑐1,2;
𝑏𝑏 ∙ 𝑥𝑥1,3 ≤ 𝑐𝑐1,3;
𝑏𝑏 ∙ 𝑥𝑥2,3 ≤ 𝑐𝑐2,3;
𝑏𝑏 ∙ 𝑥𝑥2,5 ≤ 𝑐𝑐2,5;
𝑏𝑏 ∙ 𝑥𝑥3,4 ≤ 𝑐𝑐3,4;
𝑏𝑏 ∙ 𝑥𝑥4,5 ≤ 𝑐𝑐4,5.
Сформуємо матрицю A і вектор b
349
Програмування для комп'ютерних мереж та інтернет
𝐴𝐴 =
[
𝑟𝑟 0 0 0 0 0
0 𝑟𝑟 0 0 0 0
0 0 𝑟𝑟 0 0 0
0 0 0 𝑟𝑟 0 0
0 0 0 0 𝑟𝑟 0
0 0 0 0 0 𝑟𝑟]
; 𝑏𝑏 =
[
10
0
0
-1]
.
У наведеному вище прикладі текст
програми виглядає так, як показано на
рис.6.
Результати розрахунків наводяться у
вікні команд (рис.6). Згідно з результатами
розрахунків, "довжина" найкоротшого
шляху дорівнює 2 ( fval = 2), а 𝑥𝑥1,2 = 1 і
𝑥𝑥2,5 = 1, тому можна зробити висновок, що
він проходить через вузли 1, 2 та 5 (рис. 7).
На рис.7 показано інтенсивність трафіку,
що проходить через канал зв'язку.
Рис. 6. Текст програми у вікні редагування
М-file Editor
В результаті необхідно побудувати
графік кількості шляхів (K), що використо-
вуються у процесі маршрутизації, як фун-
кції від інтенсивності трафіку, що надхо-
дить до мережі (r). На графіку також необ-
хідно вказати, які шляхи використову-
ються при якій інтенсивності трафіку. Та-
кож варто експериментально визначити
пропускну здатність у напрямку зв'язку від
вузла-відправника до вузла-одержувача
відповідно до реалізованої моделі маршру-
тизації.
Рис. 7. Результати розрахунків у вікні ко-
манд «Comand Window»
Реалізація вказаної моделі маршру-
тизації за допомогою математичного пакету
MatLab та розробленої технології показали
аналогічні результати маршрутизації.
Висновки
На завершення можна зробити ви-
сновок, що наукові та технічні досягнення
в SDN приносять користь як підприємствам
центрів обробки даних, так і дослідникам,
які пропонують нові мережеві механізми та
протоколи, дозволяючи їм проводити більш
реалістичні експерименти.
Емуляція мережевих пристроїв та їх-
ніх функцій дозволяє розробляти та зміню-
вати наші власні стандарти, що дає нам бі-
льше гнучкості у проєктуванні корпоратив-
них та глобальних мереж. У цій статті було
створено метод розробки нових і модифіка-
ції існуючих мережевих функцій, а також
перевірене середовище для тестування са-
мостійно створених протоколів динамічної
маршрутизації.
У статті описана повна послідов-
ність роботи з моделювання, яка дозволяє
перевірити протоколи динамічної маршру-
тизації, написані мовою програмування
Python, у будь-якій мережі з будь-якою кі-
лькістю маршрутизаторів і з’єднань між
ними. Також вказана модель на основі про-
токолу RIP була реалізована за допомогою
350
Програмування для комп'ютерних мереж та інтернет
математичного пакету MatLab, що підтвер-
дило результати маршрутизації, отримані
за допомогою розробленої технології мар-
шрутизації на основі мови програмування
Python.
Література
1. Network routing: algorithms, proto-
cols, and architectures / Medhi D., Ra-
masamy K. San Francisco: Kaufmann
Publishers is an imprint of Elsevier,
2007. – 824 p.
2. Software-defined networking (SDN): a
survey. [web source] - Access mode:
https://onlineli-
brary.wiley.com/doi/epdf/10.1002/sec.
1737
3. Network Functions Virtualization
(NFV). [web source] - Access mode:
https://www.etsi.org/technologies/nfv
4. Creating a simple router simulation us-
ing Python and sockets. [web source] -
Mode of access:
https://medium.com/swlh/creating-a-
simple-router-simulation-using-py-
thon-and-sockets-d6017b441c09
5. Exploring the Functions of Routing.
[web source] - Access mode:
https://www.learn-
cisco.net/courses/icnd-1/lan-connec-
tions/functions-of-routing.html
6. Use Container lab to emulate open-
source routers. [web source] – Access
mode: https://www.brianlinklet-
ter.com/2021/05/use-containerlab-to-
emulate-open-source-routers/
7. Starkova, O., Herasymenko K., Nikol-
chev K., Bulgakova A. Virtualization
And Programmability In Modern Net-
works In The Context Of SDN Con-
cept. 2022 IEEE 4rd International Con-
ference on Advanced Trends in Infor-
mation Theory, ATIT 2022 – Proceed-
ings, pp. 204 - 207.
8. Starkova, O., Herasymenko K., Nikol-
chev K., Kravchenko O., Bulgakova A.
Implementation Of Advanced Routing
Methods Based On The SDN Concept
And OS Linux. 2022 IEEE 4rd Interna-
tional Conference on Advanced Trends
in Information Theory, ATIT 2022 –
Proceedings, pp. 244 - 248.
9. М.В. Семеняка, О.В. Лемешко, О.В.
Старкова «Методичні вказівки до
лабораторних робіт з дисципліни
"Системи комутації та розподілу ін-
формації. Частина 2"», Харків:
ХНУРЕ, 2014. 92 с.
Одержано: 12.02.2024
Внутрішня рецензія отримана: 19.02.2024
Зовнішня рецензія отримана: 08.03.2024
Про авторів:
1Кравченко Юрій Васильович,
Доктор технічних наук,
професор
https://orcid.org/0000-0002-0281-4396
2Герасименко Костянтин Васильович,
Кандидат технічних наук,
https://orcid.org/0000-0002-9545-5272
3Старкова Олена Володимирівна,
Кандидат технічних наук,
https://orcid.org/0000-0001-8985-2442
4Булгакова Анна Юріївна,
студентка
Місце роботи авторів:
Київський національний університет
ім. Тараса Шевченка,
факультет інформаційних технологій
Тел. (+38) (044) 481-45-07
E-mail: fit@knu.ua,
Сайт: https://fit.knu.ua/
|