В. П. Вінницький1, В. Г. Поліщук



Скачати 247.05 Kb.
Дата конвертації24.04.2016
Розмір247.05 Kb.

УДК 621.397.6+621.396 (075.8)


В. П. Вінницький1, В. Г. Поліщук2

1Національний технічний університет України «КПІ»

2СП «Інфоком»

Метод оптимізації процедур інформаційної підтримки адаптивної маршрутизації
Розглянуто проблему адаптивної маршрутизації у телекомунікаційних мережах — аспект оптимізації процедур інформаційної підтримки алгоритмів маршрутизації, для вирішення якої запропоновано формальну математичну постановку і метод розв’язання цієї задачі. Метод дозволяє визначити оптимальний період сканування безпосередньо взаємодіючих вузлів мережі, затримки інформаційних трафікових пові-
домлень (заявок) при ненадійній роботі каналів зв’язку.


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

Вступ


Серед проблем, які виникають при створені й експлуатації телекомунікаційних мереж, одною із центральних є проблема маршрутизації і керування потоками (трафіком) повідомлень, що передаються каналами зв’язку. Метою будь-якого класу алгоритмів маршрутизації є забезпечення найкращої сукупності шляхів між джерелом інформації (адресантом) і споживачем (адресатом) при заданих вхідних потоках і конфігурації мережі. Частіше всього найкращими розглядаються шляхи мінімальної затримки. Оскільки вхідні потоки і конфігурація мережі змінюються за часом (остання, наприклад, із-за відказів ліній та вузлів), протокол маршрутизації повинен бути «адаптивним», тобто повинен пристосовувати маршрути до мережевих умов, що змінюються за часом. Такий тип визначення маршруту доставки повідомлення адресату отримав назву адаптивна маршрутизація, задача її полягає у визначенні процедури, яка динамічно корегує маршрутні таблиці у відповідності зі змінами в мережі та її вузлах.

Для формування маршрутних таблиць у вузлах необхідна інформація про миттєві зміни станів мережі та її трафік. Нажаль, вузли не можуть з точністю до наносекунд мати інформацію навіть про стан сусідніх вузлів, не кажучи вже про всю мережу. Це вимагало б непомірних накладних витрат, які ще називають системними витратами. Отже, вузли змушені приймати рішення за застарілою, ска-

© В. П. Вінницький, В. Г. Поліщук

жемо, на півсекунди і більше, інформацією [1, 2]. Це все відноситься до розділу будь-якої мережевої технології керування інформаційними потоками. До змінних, які відображають стан мережі і представляють інтерес для обчислення маршрутів, відносяться: топологічна зв’язність, структура трафіка, затримка і т.д. Для того, щоб визначити локальну зв’язність, кожен вузол контролює стан суміжних ліній і вузлів, відслідковуючи трафік у лінії або (за відсутності трафіка чи в примусовому порядку) періодично опитує сусідів. Навантаження локального трафіка контролюється за допомогою вимірювання або середніх (чи то миттєвих) довжин черг, або середніх потоків у вихідних лініях, або вхідного трафіка, який надходить із зовнішніх джерел.


Постановка задачі

Процес функціонування комутаційного вузла мережі при адаптивній маршрутизації за часом будемо розглядати як процес виконання визначених робіт маршрутизатором мережі згідно з моделлю, яка показана на рис. 1.

Рис. 1
Маршрутизатор j-го рівня (Mj) у відповідності з базовою дисципліною періодичного опитування виконує операцію «опитування», згідно якої накопичена інформація у буфері вузла (j + 1)-го рівня, що опитується, передається каналом зв’язку у маршрутизатор-ініціатор Mj, і так маршрутизатор-ініціатор проводить періодично сеансові опитування усіх сусідніх вузлів (j + 1)-го рівня (Mj+1), з якими у нього є канал зв’язку. На взаємодію маршрутизатора-ініціатора з одним із сусідніх маршрутизаторів витрачається процесорний час та час зайнятості каналу зв’язку. Таким чином, маршрутизатор-ініціатор періодично опитує усі сусідні маршрутизатори, утворюючи сеанс (цикл) взаємодії. Витрати часу зайнятості його на взаємозв’язок називають системними витратами, або системним навантаженням (системним трафіком).



1

1

1
Рис. 2
Ілюстрація описаного процесу демонструється часовою діаграмою (рис. 2), на якій = (1,…, i,…, n) — цикл опитування (i — час опитування і-го маршрутизатора); і — інтенсивність надходження інформаційних повідомлень (заявок на обслуговування); — інтенсивність виникнення повідомлень про зміни станів відносно інформації про них, що опитувалась у попередньому циклі; — інтервал обміну інформаційними повідомленнями. Таким чином, ( + ) — період опитування (інтервал між сусідніми моментами початку опитування). На рис. 1 БНmp і БНc — накопичувачі для повідомлень відповідно інформаційного трафіка та трафіка сигналізації про зміни стану маршрутизаторів.

Принципові труднощі, з якими приходиться стикатися при визначенні пе-ріоду виконання циклів опитування маршрутизаторів, виникають із двох суперечливих вимог, яким повинна відповідати організація ефективного керування ін-формаційним трафіком. Ефективне використання маршрутизатора передбачає мінімізацію витрат його на опитування сусідніх маршрутизаторів, для чого чим рідше виникають цикли опитування, тим менше відволікається він на роботу з системним трафіком. Одначе, занадто рідкі опитування сусідів приводять до порушення своєчасності забезпечення інформаційної підтримки основного алгоритму маршрутизації (запізнення сприяє старінню інформації) і до необхідності пошуку такого періоду опитування, за якого витрати часу маршрутизатором на опитування сусідніх маршрутизаторів були б мінімальні, і при цьому забезпечувався би їх мінімальний вплив на затримку трафікових інформаційних повідомлень, що передаються каналами зв’язку.


Метод розвязання

Для розв’язання задачі розглянемо поведінку за часом довільного маршрутизатора j-го рівня при виконанні роботи по вибору напрямку передачі інформаційних потоків повідомлень (заявок на тимчасове використання ресурсів як маршрутизатора, так і каналів передачі даних до вибраного маршрутизатора (j + 1)-го рівня). Передбачимо, що загальний потік заявок , який надходить від n мар-шрутизаторів (j – 1)-го рівня і описується пуасонівським потоком подій (заявок на обслуговування).

Адаптивні алгоритми маршрутизації, які застосовують в реальних мережах, класифікуються по інформації, яка використовується ними для прийняття маршрутних рішень. Одним із головних параметрів будь-якого методу маршрутизації є затримки заявок у вузлах та каналах зв’язку.

Для визначення впливу на величину затримки заявок системою маршрутизатор-канал зв’язку М К розглянемо типову ситуацію функціонування її в мережі за часом на сумісній часовій діаграмі (рис. 3). Введемо деякі додаткові позначення:



В — тривалість передачі повідомлення каналом зв’язку (час обслуговування заявки) без впровадження процедури опитування — випадкова величина з довільною функцією розподілу B(t) і щільністю розподілу ймовірностей dB(t);

Н — тривалість передачі інформаційного повідомлення каналом зв’язку при строго регламентованих перервах, які викликаються вимушеними тимчасовими припиненнями передачі його на час — час опитування маршрутизаторів (j + 1)-го рівня — випадкова величина з довільною функцією розподілу H(t) і щільністю розподілу ймовірностей dH(t);

Т — випадковий момент часу надходження поміченого повідомлення з інформаційного потоку, — інтервал часу між Т і початком передачі його каналом зв’язку — випадкова величина з довільною функцією розподілу (t), ця функція описує час очікування заявки-повідомлення у БНтр маршрутизаторі (час перебування заявки у черзі).

Рис. 3
Розглянемо тривалість R1 часу перебування інформаційного повідомлення-заявки у системі МК від моменту його надходження у маршрутизатор Мj до моменту доставки до вибраного Мі (j + 1)-го рівня. Для визначення R1 використаємо таку модель. Моменти ti звернення маршрутизатора Mj на опитування маршрутизаторів (j + 1)-го рівня представляють собою послідовність подій, які виникають в момент часу, інтервали між якими однакової довжини ( + ) — регулярний потік подій. Незалежно від моментів виникнення подій цього потоку візьмемо на осі часу точку Т, яка визначає момент надходження заявки-повідомлення у маршрутизатор Мj (зрозуміло, що момент Т надходження заявки не залежить від моментів початку циклу опитування). У такому разі і H — невід’ємні незалежно розподілені випадкові величини.

Перетворення Лапласа щільності розподілу суми і H за визначенням має вигляд
, (1)
де r1(s) — перетворення Лапласа розподілу часу перебування заявки у системі
М – К; (s) — перетворення Лапласа розподілу часу перебування заявки у маршрутизаторі (час очікування у черзі); — перетворення Лапласа розподілу часу зайнятості каналу зв’язку передачею повідомлення.

Перейдемо до визначення . Розглянемо сумарний час зайнятості системи М – К передачею повідомленням, яке надійшло в момент Т, враховуючи при цьому те, що протягом Н будуть виникати інтервали-перерви маршрутизотора Мj від передачі цього поміченого повідомлення на селективно вибраний маршрутизатор (j + 1)-го рівня.

Знайдемо вигляд функції розподілу інтервалу Н – Н(t). Імовірність того, що час перебування заявки у системі М – К знаходиться в границях [x, x + x] дорівнює dB(x). Припустимо, нам відомо, що час перебування заявки дорівнює t, і за цей час виникло k разів відхилення на опитування з імовірністю Pk(x). Для того, щоб сумарний час зайнятості М – К цим повідомленням при фіксованих x і k не перевищував t, необхідно і достатньо, щоб за час (t x) маршрутизатор відхилявся k разів на опитування, ймовірністю чого є величина , де F1(t) — функція розподілу часу опитування з щільністю розподілу f1(t) = (t – ). Тоді H(t) — функція розподілу загального часу перебування заявки у маршрутизаторі-каналі з урахуванням відхилень останнього на опитування буде мати вигляд
, (2)
де * — символ стілт’єсовської згортки.

Перейдемо до перетворення Лапласа, тоді отримаємо


. (3)
Вираз замінимо твірною функцією, де , тоді вираз (4) прийме такий вигляд

. (4)
Функцію знайдемо з таких міркувань. Імовірність розподілу числа k відхилень маршрутизатора від виконання роботи по передачі інформаційного повідомлення (обслуговуванню заявки) на інтервалі t визначається як
(5)
де — ціла частина відношення .

З урахуванням (5) твірна функція приймає вигляд


. (6)
Перетворення Лапласа щільності розподілу f1(t) буде таким:

Тоді матиме кінцевий вигляд
. (7)
Підставимо (7) у (4) і отримаємо у вигляді
. (8)
Для отримання верхньої оцінки вираз (8) запишемо як
(9)
де .

Щоб отримати середні характеристики тривалості передачі інформаційного повідомлення каналом зв’язку між маршрутизаторами обчислюємо і :


, (10)
, (11)
де і — відповідно перші початкові моменти розподілу часу перебування повідомлення у каналі зв’язку без урахування затрат на тривалість і частоту опитування.

Тепер визначимо . Приведений вище опис процесу функціонування (вхідний трафіковий інформаційний потік плюс маршрутизатор зі своїм буферним накопичувачем БНтр плюс канал зв’язку для передачі повідомлень за визначеним маршрутом через -го рівня) системи відображається адекватно динамічним процесом масового обслуговування моделі , стаціонарний режим якої визначається нерівністю , де — середнє значення інтервалу обслуговування заявки.

В однолінійній системі, на яку надходить пуасонівський потік, періоди зайнятості і незайнятості утворюють дві чергуючі і незалежні послідовності однаково розподілених випадкових величин. Розподіл тривалості періоду зайнятості відіграє суттєву роль у визначені залежності розподілу тривалості перебування (затримки) заявки в черзі або системі. Для кращого розуміння впливу на період зайнятості періодичного виникнення перерв на опитування розглянемо на часовій діаграмі (рис. 4), де: а) послідовність періодів опитування; б) послідовність чергування періодів зайнятості і незайнятості для моделі ; в) послідовність чергування періодів зайнятості і незайнятості при дії перерв на опитування. На цій діаграмі (ПЗ) і (ПНЗ) — відповідно -і періоди зайнятості і незайнятості моделі ; (ПЗ) і (ПНЗ) — відповідні періоди при періодичних перервах на опитування.

Розглянемо процес утворення періоду зайнятості системи як суму інтервалів елементарних періодів зайнятості (ЕПЗ). Період зайнятості розпочинається обслуговуванням заявки, що надійшла першою і тих заявок, що надійшли за час її обслуговування, утворюючи ЕПЗ1 [3, 4]. Протягом тривалості ЕПЗ1 надійдуть нові заявки, які утворять ЕПЗ2 і т.д. Таким чином, повний період зайнятості буде складатись із взаємозв’язаних інтервалів ЕПЗ, де допускається можливість нескінченого числа проміжків часу. Ясно, що для тих проміжків, які лежать поза періодом зайнятості, передбачається, що тривалість ЕПЗі дорівнює нулю. При відомо з імовірністю одиниця, що існує кінцеве число , для якого проміжок ЕПЗі і тривалості подальших проміжків дорівнює нулю. Позначимо тривалість інтервалу ЕПЗі як .































в)

б)



а)

пнз

пнз

пз

пз

t

t


t
Рис. 4
Можна отримати рекурентне співвідношення між перетвореннями Лапласа інтервалів і через відомі та , вираз якого є (9). Далі будемо спостерігати за «поміченою» заявкою, яка надійде на і-й ЕПЗ(), причому використаємо із теорії альтернуючих процесів відновлення граничну стаціонарну ймовірність стану як відношення тривалості ЕПЗ() до повної тривалості періоду зайнятості, а також умови надходження заявки у період зайнятості та період незайнятості . Для зняття умови, що помічена заявка надійшла у і-й ЕПЗ, виконується підсумовування по при [5]. Таким чином, отримуємоу вигляді
. (12)
Середні значення затримки інформаційних повідомлень у маршрутизаторі (буферному накопичувачі) знайдемо при обчисленнях і . Оскільки похідна від у точці має вид , тому необхідно двічі застосовувати правило Лопіталя. У результаті чого маємо

, (13)
. (14)
Формули (13) і (14) дають можливість обчислювати середнє значення та дисперсію затримки повідомлення заявки у маршрутизаторі і можуть бути використані як інформація для підтримки параметрів маршрутної матриці.

Тепер, на кінець, знайдемо перетворення Лапласа часу затримки заявки інформаційного трафікового повідомлення маршрутизатором і каналом зв’яз-ку з селективно вибраним маршрутизатором (j + 1)-го рівня як


, (15)
Рівняння (15) виражається через відомі величини, які отримуються із початкової постановки задачі — функції розподілу часу зайнятості каналу передачею трафікового інформаційного повідомлення (час обслуговування заявки), де — параметр вхідного потоку і — часові затрати на обмін службовою інформацією, а також поки ще не визначений параметр , який разом з представляє частоту опитування. Вираз (15) за формою є рівнянням Полячека–Хінчина для M|G|1 при .

Середні значення повної затримки інформаційної заявки-повідомлення системою МК, а саме час доставки повідомлення від моменту його надходження у Мj до моменту реєстрації вибраним маршрутизатором Mi (j + 1)-го рівня, визначимо із (15) таким же способом як і (13) та (14), тобто


, (16)
. (17)
Знайдемо границю як функцію від при , тобто
. (18)
Результат (18) означає, що при функціонування системи МК здійснюється без перерв (затрат на опитування), цей результат для M |G|1 отриманий у [5]. Функція (16) монотонно спадна і при наближається до границі, яка визначається з виразу (18).

Таким чином, отримані результати (10), (13) і (16) визначають функціональну залежність передачі повідомлення каналом, часу очікування у маршрутизаторі та часу затримки повідомлення системою МК (час доставки) від величини періоду опитування ( + ).

Перейдемо до розгляду впливу періоду опитування на затримку своєчасного інформування маршрутизатора Мj про зміни станів опитуємих маршрутизаторів Mi (j + 1)-го рівня. Очевидно, що інформування Мj про миттєві зміни параметрів станів за ініціативою Мi (i = 1,…, m ) може призвести як до перевантаження каналів, так і до повного завантаження Мj роботами по неперервному відновленню маршрутних таблиць та розрахунками по визначенню маршрутів трафіковим інформаційним повідомленням.

Помітимо, що величина параметру визначається протокольними процедурами (кадрами та командами опитування), числом вимірюємих параметрів стану опитуємого вузла і кількістю опитуємих вузлів. Тому для визначення впливу частоти опитування на затримки повідомлень R2 про зміни параметрів стану обмежимось визначенням величини R2.

Розглянемо типову ситуацію періодичного опитування, що зображена на рис. 5, де С — момент виникнення повідомлення про зміну значення контролюємого параметру; 2 — інтервал часу між С та початком наступного періоду опитування; R2 — час затримки повідомлення про зміну стану та його обробкою для матриці маршрутизації.

Для загального випадку щільності розподілу того інтервалу (j-й період опитування), на який випадковим чином випала точка С визначається як



, (19)
де f *(t) — щільність розподілу ймовірностей випадкових величин-інтервалів між двома сусідніми подіями-початками періодів опитування: .


Рис. 5

Для нашого випадку, коли інтервал строго постійний між початками періодів опитування, щільність розподілу інтервалу, на який випала точка С буде мати вигляд


(20)
На підставі виразів (19), (20) знайдемо закон розподілу часу (2 + ) = R2 від випадкової точки С до моменту закінчення циклу опитування і отримаємо
. (21)
Перетворення Лапласа буде таким:
. (22)
Як і для знайдемо
. (23)
Із (23) видно, що є функцією від , тобто лінійно зростає при і при . Цю функцію можна розглядати як функцію від змінного аргументу , значення якого залежать від числа — кількості опитуємих маршрутизаторів та інтенсивності зміни параметрів станів опитуємих вузлів. У даному випадку ми зупинились на кількості для того, щоб спростити операції запропонованого методу.

Будемо рахувати оптимальним таке значення періоду опитування , при якому величина забезпечує мінімум сумарних часових затрат на затримку трафікових інформаційних повідомлень та мінімум сумарних затрат на своєчасність інформування сусідніх вузлів про зміни параметрів, які вимірюють стан вузла. Затрати на затримки повідомлень про зміни спостерігаємих параметрів (станів) у відповідності з (23) збільшуються зі зростанням періоду і пропорційні середньому часу очікування , тобто часу від моменту виникнення повідомлення про зміни станів до завершення обробки його опитуємим маршрутизатором. Якщо ввести коефіцієнт пропорційної зміни середнього значення затримки, тоді він буде мати зміст штрафу за одиницю часу затримки повідомлень про зміни стану.

Функція монотонно спадає зі зростанням , а функція — лінійно зростає, і, отже, функція + має єдиний мінімум, який є рішенням рівняння
. (24)
Оптимальне значення для неперервної і диференційованої функції можна знайти, якщо прирівняти нулю першу похідну по , а потім із отриманого рівняння знайти .
Ненадійність каналів звязку

До цих пір проводився системний аналіз поведінки за часом маршрутизатора мережі при адаптивній маршрутизації та надійних каналах зв’язку. У трактах передачі каналами зв’язку виникають збійні ситуації, які приводять до порушення нормального режиму передачі даних. Боротьба з цими порушеннями і їх випливами на достовірність передачі інформації проводиться впровадженням засобів завадостійкого кодування та зворотного вирішального зв’язку, останній діє через протокольні процедури повторення передачі інформації, що зрештою зводиться до додаткових часових затрат на використання канальних ресурсів. Помітимо, що темпи (інтенсивності) завантаження каналу зв’язку (особливо на магістральних лініях) трафіковими потоками і темпи виникнення «збійних ситуацій» значно відрізняються, тому останні ще називають «рідкими подіями». У цьому розділі визначимо вплив цих подій на динамічний процес обміну потоками в ланках мережі.

Звернемо увагу на функціональні залежності і і помітимо, що у них одним з аргументів є перетворення Лапласа часу обслуговування (часу передачі інформаційного повідомлення).

Для визначення впливу ненадійності та відновленості каналу зв’язку на ефективність використання каналу при передачі трафікових повідомлень, введемо такі характеристики:



— функція розподілу тривалості часу до моменту виникнення відказу в подальшій передачі повідомлення;

— функція розподілу тривалості часу, який витрачається на відновлення робочого стану каналу — ліквідацію наслідків відказу;

— функція розподілу часу обслуговування заявки — тривалість часу передачі повідомлення каналом;

— функція розподілу «сумарного» часу обслуговування заявки — повний час зайняття каналу передачею повідомлення з урахуванням ліквідації відказу.

Нехай H1(t) є функція розподілу часу виникнення відказу, H2(t) — функція розподілу часу реакції на відказ (відновлення), тоді функція Ф(t) розподілу сумарного часу обслуговування повідомлення з урахуванням відказів і відновлень буде мати вигляд


. (25)
Дійсно, для того, щоб сумарний час обслуговування повідомлення не перевищував час t (імовірність чого дорівнює Ф(t)), необхідно і достатньо щоб: або час обслуговування повідомлення не перевищував t, тобто не виникло ні одного відказу, імовірність чого дорівнює першому доданку в правій частині рівняння (25), або перший відказ виник у проміжку [x, x + x] x t, і час реакції на відказ (відновлення робочого стану) плюс нова реалізація сумарного часу обслуговування із самого початку не перевищував (tx) — імовірність чого дорівнює другій складовій правої частини рівняння (25) [6, 7].

Нехай (s), h1(s) і h2(s) — перетворення Лапласа–Стілт’єса функцій розподілів (t), H1(t), H2(t) відповідно. Тоді, вирішивши рівняння (25) за допомогою перетворень Лапласа–Стілт’єса, дістанемо:


, (26)

де ; .

Для часткового випадку, коли потік відказів є пуасонівським , визначимо (s). Вирази для (s), (s) i h1(s) мають вигляд:
, , . (27)

Підставляючи (27) в (26) обчислимо (s) у такий спосіб


. (28)
Продиференціювавши (28) по s і поклавши s = 0 дістанемо середню тривалість обслуговування повідомлення з урахуванням тимчасових витрат на відновлення

(29)


де .

Таким чином, вираз (29) представляє середнє значення часу передачі інформаційного повідомлення при випадкових відказах і відновленнях, причому після відновлення відказної ситуації повідомлення заново передається каналом, тобто раніше витрачений час на обслуговування не враховується. Такі події виникають при передачі інформації каналами зв’язку, в яких використовують для підвищення достовірності передачі засоби завадостійкого кодування разом з процедурою вирішального зворотного зв’язку.



Висновки


Запропонований метод складається з двох незалежних складових: по-перше, окремо визначається вплив затрат часу на тривалість передачі повідомлення каналом зв’язку періодичністю опитування (вираз (9)); по-друге, час затримки пові-домлення маршрутизатором (15) і функція (вираз (24)) дають можливість отримати оптимальне значення періоду опитування; по-третє, перетворення Лапласа (26) дає можливість оцінити вплив ненадійності каналу на ефективну передачу повідомлення. І нарешті, шляхом підстановки (26) в (9) і (24) отримується загальний результат — алгоритм оптимального пошуку величини періоду сканування при ненадійній роботі каналу.


  1. Бертсекас А., Галлар Р. Сети передачи данных / Под ред. Б.С. Цыбакова. — М.: Мир, 1989. — 544 с.

  2. Мартин Д. Вычислительные сети и распределенная обработка данных: программное обеспечение, методы и архитектура. — Вып. 2. — М.: Финансы и статистика, 1986. — 269 с.

  3. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний / Под ред. Г.П. Башарина. — М.: Наука, 1975. — 360 с.

  4. Кокс Д.Р., Смит В.Л. Теория восстановления / Под ред. Ю.К. Беляева. — М.: Советское радио, 1967. — 299 с.

  5. Клейнрок Л. Теория массового обслуживания / Под ред. В.И. Нейман. — М.: Машиностроение, 1979. — 432 с.

  6. Винницкий В.П., Бродецкий Г.Л. Емкостно-временные характеристики многоприоритетной схемы обработки данных. — В кн.: Моделирование структур технических комплексов АСУ. — К.: Наук. думка, 1972. — С. 44–49.

  7. Винницкий В.П., Хиленко В.В. Методы системного анализа и автоматизации проектирования телекоммуникационных сетей. — К.: Интерлинк, 2002. — 192 с.

Надійшла до редакції 17.04.2003



ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2003, Т. 5, № 2 51


База даних захищена авторським правом ©shag.com.ua 2016
звернутися до адміністрації

    Головна сторінка