аршрутизації заснований на мінімізації середньої затримки на всіх найкоротших маршрутах, причому визначення затримок на ділянках включає аналіз статичних характеристик мережі (топології і пропускних спроможностей каналів зв'язку) і характеру переданого трафіку (облік оптимальних показників затримок для різних видів трафіку ).
В алгоритмі передбачено механізми аналізу пропускних спроможностей каналів зв'язку з точки зору їх оптимальності, розрахунок оптимальної ваги шляхів на підставі цієї інформації та мінімізації функції затримки у мережі на підставі аналізу потоку за маршрутами, при якому розмір затримки міг би відповідати загальноприйнятим характеристикам передачі певних видів трафіку.
Алгоритм використовує принципи побудови найкоротших шляхів, які використовуються в алгоритмах Дейкстри і Беллмана-Форда, і способи визначення середньої затримки, традиційні для мереж з пакетною комутацією. Функціональна блок-схема алгоритму наведена на малюнку і включає наступні складові:
. Блок визначення оптимальних пропускних спроможностей - аналізує базову топологію мережі і визначає оптимальність пропускних спроможностей. На підставі отриманих даних підраховує вагу каналів зв'язки мережі для подальшого аналізу.
. Блок аналізу середнього часу затримки - відповідає за розрахунок середнього часу затримки в мережі на підставі оптимальних пропускних спроможностей і початкових потоків в мережі.
. Блок визначення маршрутів - відповідає за побудову найкоротших маршрутів між усіма вузлами мережі.
. Блок побудови допустимого потоку - забезпечує розподіл потоків по найкоротших шляхах.
. Блок мінімізації середньої затримки - забезпечує розрахунок девіації потоку на основі мінімізованої функції значення середньої затримки в мережі.
. Тіло алгоритму - об'єднує роботу кожного з блоків і забезпечує послідовне функціонування алгоритму.
Малюнок - блок-схема алгоритму
Сформулюємо завдання, які повинні бути вирішені за допомогою спроектованого алгоритму:
найбільш раціональне використання каналів для вирішення завдання використовуються такі прийоми:
а) аналіз пропускних спроможностей каналів зв'язку в мережі і розрахунок оптимальних міток;
б) використання альтернативних маршрутів;
в) розподіл трафіку між альтернативними маршрутами виходячи не зі співвідношення сумарних метрик маршрутів, а зі співвідношення максимальних метрик каналів даного маршруту;
г) вибір доступних для використання альтернативних маршрутів тільки за критерієм максимального часу передачі (маршрут може бути прийнятий до використання, якщо час передачі по маршруту не перевищує встановленого для даного типу трафіку максимально допустимого).
) дотримання вимог до параметрів мережної передачі.
Далі розглянемо прийоми вирішення зазначених завдань. Завдання дотримання вимог до параметрів мережної передачі вирішується таким способом:
а) мінімізація затримки передачі повідомлень в мережах складної топології;
б) мінімізація ВКВ затримки.
Зробимо оцінку оптимальності функціонування за алгоритмом.
Введемо позначення:
де і - номер пари вузол-адресат - вузол-одержувач; перший формула - потік пакетів, які надходять в і-ий канал; друга - потік пакетів, що надходять з вузла в мережу.
Навантаження і-ого каналу пакетами вважаємо за такою формулою:
де перший множник - середня довжина пакету, Di - пропускна здатність
і-ого каналу.
Середня кількість пакетів в і-му каналі становить:
Враховуючи загальну кількість вузлів в мережі, середня кількість пакетів у мережі в цілому складає:
Згідно з формулою Літтла
де Т - середня затримка в мережі. Таким чином, отримуємо формулу
Клейнрока для аналізу середньої затримки в мережі:
Отримана формула для оцінки часу затримки ефективно використовується для вирішення різних оптимізаційних задач. До таких завдань відносять оптимізацію пропускної здатності каналів і вибір маршрутів передачі повідомлень.
4. ПОСТАНОВКА ЗАВДАННЯ
Припустимо, що є деяка кількість відео-файлів, обсяг яких не перевищує 10 Гігабайт. Ці файли потрібно передати абоненту на відстань, на якій сигнал здатний передаватися на максимально допустимої швидкості. З пропонованих мереж 3G, LTE, VANet, WiMax необхідно вибрати оптимальну бездротову мережу для передачі відеоконтенту на відстань, яку задає користувач.
Специфіка використання радіоефіру в якості середовища передачі даних накладає свої обмеження на топологію мережі. Якщо порівнювати її з топологією провідної мережі, то найбільш близькими варіантами виявляються топологія зірка і комбінована топологія кільце і загальна шина raquo ;. Слід згадати, що розвиток бездрот...
