Лемешко Олександр Віталійович, Єременко Олександра Сергіївна, Євдокименко Марина Олександрівна

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

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

Ключові слова: мережа, відмовостійкість, багатоадресна маршрутизація, резервування, оптимізація

Lemeshko Oleksandr, Yeremenko Oleksandra, Yevdokymenko Maryna

Fault-tolerant multicast routing in infocommunication network with path and bandwidth protection

The article presents and investigates a flow-based mathematical model of fault-tolerant multicast routing. Under the proposed mathematical model, the technical task of fault-tolerant multicast routing was reduced to the Boolean programming optimization problem. The mathematical model was based on linear optimality criterion and constraints represented by the conditions of single-path routing, flow conservation, multicast connectivity, and prevention of overload and looping. The routing variables that guided the multicast routing process were Boolean. The optimal primary and backup paths are calculated by implementing path and bandwidth protection schemes within the model for each multicast flow. The restrictions on routing variables introduced into the model were responsible for protecting the route and bandwidth. The optimality criterion in determining the optimal and backup multicast paths at the level of routing metrics considered the network topology and links bandwidth. The additive nature of the criterion focused on finding paths that included a minimum number of communication links. According to the selected routing metric, a feature of the model is to ensure priority in assigning the primary route of the path that had a shorter «length» than the backup path. The analysis of the obtained solutions confirmed their operability under the specified protection scheme’s implementation and their optimality according to variants of the used routing metrics. The proposed mathematical model can be used to develop the fault-tolerant multicast routing protocols of multimedia flows.

Keywords: network, fault-tolerance, multicast routing, redundancy, optimization