ЗАДАЧА ОПТИМІЗАЦІІЇ РОЗПОДІЛУ ПОТОКІВ НА ВІЛЬНО-ОРІЄНТОВАНОМУ ГРАФІ

Анотація

Об’єктом дослідження є процеси передавання цифрових потоків у програмно-конфігурованих телекомунікаційних транспортних мережах (SDN), що забезпечують гнучке управління трафіком та оптимізацію мережевих ресурсів. Предметом дослідження є методи та алгоритмічні підходи до оптимального розподілу цифрових потоків на вільно-орієнтованих графах із використанням принципів максимального потоку і мінімального транзиту. У роботі запропоновано модифікований ітерактивний алгоритм (МІА) для розв’язання задачі оптимізації цифрових потоків у програмно-конфігурованих мережах (SDN). Алгоритм базується на принципах мінімального транзиту та максимального потоку на вільно-орієнтованих графах. Подано опис програмної реалізації мовою Python, яка дозволяє автоматизувати процес обчислення пропускної здатності та розподілу трафіку. Алгоритм забезпечує одночасне обчислення максимально можливого потоку між полюсами S та T та оптимальний розподіл цього потоку між альтернативними ST‑шляхами з мінімальною кількістю проміжних вершин, реалізуючи принцип мінімального транзиту у поєднанні з принципом максимального потоку. У вихідних даних використовується нормалізований ST‑граф, у якому вершини V_n нумеруються натуральними числами від 1 до N, а ребра Р_k – від 1 до K; вершина V₁ ітерпретується як джерело S, а вершина з найбільшим номером – як стік T. Структура графа задається текстовим файлом graph.txt, де в першому рядку перелічені всі вершини, а в другому – непорожні ребра з їхніми вагами у форматі трійок (i, j, w). На основі цих даних алгоритм будує внутрішню модель мережі та послідовно виконує три основні блоки: 1) зчитування та валідація вхідного графа, 2) ітеративний пошук ST‑шляхів фіксованої довжини з рекурсивним оновленням залишкових пропускних здатностей, 3) обчислення глобального максимуму потоку f_max і формування матриці залишків, яка наочно відображає використання ресурсів мережі після роботи МІА.