"КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ"

УДК 681.513

ДЕМЧІНСЬКИЙ ВОЛОДИМИР ВАСИЛЬОВИЧ

Методи розподілу ресурсів у системі керування трафіком на основі зворотного зв'язку в комп'ютерних мережах із заданою якістю обслуговування

Спеціальність 05.13.06 - Інформаційні технології

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

Київ- 2008

Робота виконана в Національному технічному університеті України "Київський політехнічний інститут", м. Київ, на кафедрі математичних методів системного аналізу.

Науковий керівник: Доктор технічних наук, професор

Зайченко Юрій Петрович,

Національний технічний університет України "КПІ", професор кафедри математичних методів системного аналізу

Офіційні опоненти: Доктор технічних наук, с.н.с.

Алішов Надір Ісмаіл-огли,

Інститут кібернетики ім.В.М. Глушкова НАН України, провідний науковий співробітник;

Доктор технічних наук, професор

Печурін Микола Капітонович,

Національний авіаційний університет, професор кафедри комп'ютерних систем і мереж.

Захист відбудеться "22 " квітня 2008 р. о 15:00 на засіданні спеціалізованої вченої ради Д 26.002.03 в НТУУ "КПІ" (м. Київ, пр. Перемоги 37, корп. 35).

Відгуки на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати за адресою: вченому секретарю НТУУ "КПІ", пр. Перемоги 37, м. Київ, 03056.

З дисертацією можна ознайомитися в бібліотеці Національного технічного університету України "Київський політехнічний інститут".

Автореферат розіслано "21" березня 2008 року

Вчений секретар спеціалізованої вченої

ради, доктор технічних наук, професор Новіков О.М.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми дослідження зумовлена зростанням і об'єднанням мультисервісних комп'ютерних мереж і появою у зв`язку з цим нових додатків, орієнтованих на передачу нетрадиційних типів інформації, - наприклад, передачу голосу й відеоконференцій, для підтримки яких необхідні гарантії якості обслуговування, що вимагає розробки нових методів і алгоритмів керування потоками даних у мережах. Для об'єднання безлічі складних неоднорідних існуючих мережних технологій однією, мультисервісною високошвидкісною мережною технологією, була розроблена технологія АТМ (Asynchronous Transfer Mode, асинхронний режим передачі). З метою підтримки передачі голосу, відео й трафіка даних додатків з різними вимогами до пропускної здатності, мережа повинна мати можливість обслуговування різних типів мережного трафіка залежно від висунутих до них вимог. У мережі АТМ для гарантування певних параметрів з'єднання введені механізми контролю за трафіком, керування й запобігання перевантаженням, які називаються керуванням трафіком. Керування трафіком дозволяє мережі АТМ надавати певну якість обслуговування з'єднанням і захищати існуючі з'єднання від перевантажень та зниження продуктивності.

У напрямку вдосконалення механізмів керування трафіком у віртуальних каналах найбільший внесок зробили роботи ATM-форуму (Ш. Кальянораман, К. Рамакришнан). Вирішення завдань забезпечення якості обслуговування, справедливого розподілу ресурсів, керування чергами й розробки ефективних механізмів відкидання комірок мають велике значення для поліпшення керованості мережі. У відомих методах і алгоритмах залишалися невирішеними питання відповідності всім вимогам до алгоритмів явної індикації швидкості, повільне усунення перевантажень, залежність ефективності від параметрів, облік стану активності джерел і характеристик трафіка, неточність керування, високий рівень втрат. Тому існуючі механізми вимагають поліпшення.

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана згідно з планами наукових досліджень у рамках теми "Моделювання, аналіз і проектування комп'ютерних і телекомунікаційних мереж вузівського й міжвузівского рівнів на основі перспективних мережних технологій", номер державної реєстрації 0100U002050 (2000-2002 р.), і теми "Розробка методів і алгоритмів керування трафіком у телекомунікаційних мережах АТМ", номер державної реєстрації 010U000144 (2003-2004 р.).

Мета й завдання дослідження. Мета роботи - підвищити ефективність системи керування трафіком мереж АТМ шляхом розробки методів і алгоритмів керування.

Об'єктом дослідження є технологія АТМ.

Предметом дослідження є протоколи передачі даних у мережах АТМ і методи керування трафіком.

Відповідно до поставленої мети сформульовані наступні основні завдання дослідження:

1.

2.

3.

4.

Методи дослідження. Теоретичною основою дослідження є класифікація, формалізація й аналіз існуючих алгоритмів керування трафіком і механізмів забезпечення якості обслуговування, використовуваних у комп'ютерних мережах. Для забезпечення рівномірності розподілу ресурсів застосовувалися методи теорії прийняття рішень (максимінна схема розподілу ресурсів і розподіл на основі N-ядра). Імітаційне моделювання функціонування мережі, що реалізує технологію АТМ, проводилося з метою тестування ефективності запропонованих алгоритмів і механізмів керування і їх порівняння з існуючими. Для доведення значимості отриманих висновків застосовувалися методи статистичного й дисперсійного аналізу.

Наукова новизна отриманих результатів. Для досягнення поставленої мети застосовано комплексний підхід до побудови системи керування трафіком у комп'ютерних мережах, розроблені й обґрунтовані нові методи явної індикації швидкості на основі розподілу ресурсів з N-ядра й ітераційного розподілу ресурсів і захисту від перевантажень із адаптивною індикацією, які підвищують керованість мережі, прискорюють реагування на зміну стану потоків і знижують втрати в мережі АТМ:

-

-

-

-

Практичне значення отриманих результатів.

Результати дослідження доповнюють існуючі технології розробки й настроювання системи керування трафіком у комп'ютерній мережі:

-

-

-

-

-

Алгоритми керування потоками даних, запропоновані автором у роботі, дозволяють підвищити керованість трафіком, тим самим підвищуючи ефективність функціонування мережі. Методика побудови системи керування трафіком може бути корисною при впровадженні механізмів якості обслуговування в комп'ютерній мережі. Імітаційна модель може бути використана як у рамках науково-дослідних робіт, так і для підвищення кваліфікації системних інженерів. Результати роботи впроваджені в навчальний процес НТУУ "КПІ" і ряду інших ВУЗів. Результати роботи були використані при розробці й настроюванні системи керування трафіком мережі передачі даних, що експлуатується в ДНВЦ "Природа". Акт про впровадження: №05-01/56 від 30.03.2007. Система керування трафіком, яка впроваджена в мережі ДНВЦ "Природа", дозволяє підвищити загальну ефективність функціонування мережі, забезпечує диференційоване рівномірне обслуговування користувачів і служб, а також зменшує затримку в мережі й час реакції прикладних програм.

Особистий внесок здобувача. Основні результати роботи отримані автором самостійно. У роботах отримані наступні результати:

У роботі [1] проведені дослідження основних методів керування трафіком у мережах АТМ.

У роботі [2] розглянуті особливості імітаційного моделювання технології АТМ.

У роботі [3] аналізуються аспекти застосування механізмів якості обслуговування, зокрема в мережах ATM.

У роботі [4] запропоновано алгоритм явної індикації швидкості трафіка ABR (Available Bit Rate) на основі ітераційного розподілу ресурсів.

Апробація результатів дисертації. Основні положення дослідження обговорювалися на міжнародній конференції "Автоматика 2001" у м. Одесі в 2001 р., на міжнародній конференції "Автоматика 2002" у м. Донецьку в 2002 р., "SAІT 2004" у м. Києві в 2004 р., "SAІT 2005" у м. Києві в 2005 р.

Публікації. За матеріалами дослідження опубліковані чотири статті в провідних фахових виданнях, затверджених ВАК України.

Обсяг і структура дисертації. Дисертація, загальним обсягом 168 сторінок, складається із вступу, трьох розділів і висновків, усього викладених на 142 сторінках тексту, списку літератури (176 найменувань), 23 малюнків, 8 таблиць, 4 додатків.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовується актуальність теми дисертаційної роботи, визначаються мета й завдання дослідження, основні положення, які виносяться на захист, і формулюються наукова новизна й практичне значення отриманих результатів.

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

Ріст мультисервісних комп'ютерних мереж і поява у зв`язку з цим прикладних програм, особливо мультимедіа, які вимагають підтримки якості обслуговування, обумовили еволюцію методів і алгоритмів керування трафіком у мережах. Перспективними з погляду інвестицій сферами варто вважати ті, які пов'язані з удосконаленням технологій передачі даних. Швидка комутація, фіксований розмір комірки (назва структури даних, використовуваної при передачі, специфічна для АТМ), що дозволяє передавати комірку за фіксований проміжок часу, конвергенція різних типів трафіка з різними механізмами обслуговування залежно від класу й керування трафіком відповідно до умов сервісної угоди спричиняють застосування АТМ для передачі мультимедійного трафіка й трафіка реального часу.

Технологія АТМ, що продовжує еволюцію ідей, закладених в X.25 і Frame Relay, одержала визнання як універсальна, орієнтована на з'єднання технологія, яка дозволяє поєднувати в одній мережі передачу різних типів даних у широкому діапазоні швидкостей із забезпеченням якості обслуговування окремо для кожного з'єднання. Подальшим розвитком ідей, покладених в основу технології АТМ, є технологія мультипротокольної комутації мітки MPLS (Multi-Protocol Label Switching). Застосований в MPLS метод за своїми можливостями подібний технологіям віртуальних каналів, але не залежить ані від мережного, ані від канального рівнів. MPLS також забезпечує швидку комутацію й високу якість обслуговування. Розробки, пов'язані з технологіями якості обслуговування, методами розподілу ресурсів і алгоритмами керування трафіком на основі зворотного зв'язку, застосовувані в АТМ, одержують свою реалізацію й подальший розвиток у технології MPLS.

Щоб мати можливість підтримувати різні вимоги користувачів та програм до ПЗ (пропускної здатності), мережа повинна мати механізми якості обслуговування. Для забезпечення якості обслуговування задачі справедливого розподілу ресурсів, керування чергами й ефективність відкидання комірок відіграють істотну роль. Керування трафіком дозволяє одержувати певну якість обслуговування. Однак залишаються невирішеними питання повільного усунення перевантаження, облік стану активності джерел, неточність керування, нерівномірність розподілу ресурсів і високий рівень втрат, тому існуючі механізми вимагають поліпшення й задача є актуальною.

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

Керування перевантаженням - поєднання механізмів запобігання й контролю перевантаження. Керування потоком - складається з узгодження швидкості передачі відправника зі швидкістю, з якою одержувач здатний приймати потік пакетів. Під потоком мається на увазі послідовність пакетів, що передаються від джерела до приймача. У мережах, орієнтованих на з'єднання, всі дані одного потоку прямують по одному маршруту. Звичайно керування потоком реалізується за допомогою зворотного зв'язку між одержувачем і відправником. Керування трафіком зачіпає всі існуючі класи трафіка з різними умовами обслуговування й механізмами керування.

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

Зазначені механізми якості обслуговування знайшли своє застосування в системі керування трафіком АТМ і стандартизовані в специфікації "Traffіc Management 4.1". Резервування ресурсів в АТМ є частиною процесу контролю за встановленням з'єднання й алгоритму обслуговування черг в комутаторі. Розподіл ресурсів і керування навантаженням застосовуються в алгоритмах явної індикації швидкості.

Специфіка АТМ дозволяє найбільш точно управляти мережними ресурсами, досягаючи при цьому найбільш ефективного їхнього використання при гарантуванні параметрів якості обслуговування. Фіксований розмір комірки й класи обслуговування дозволяють технології АТМ забезпечувати більш чітко розподілену пропускну здатність, ніж в інших транспортних протоколах другого рівня. Застосування механізму віртуальних з'єднань дозволяє прискорити комутацію за рахунок зменшення обсягу інформації, що використовується в процедурі прийняття рішення про просування комірки.

Стандартизовано класи трафіка (CBR - з постійною швидкістю, VBR - зі змінною швидкістю, ABR - з доступною швидкістю й UBR - з невстановленою швидкістю) і механізми обслуговування залежно від класу. Зокрема клас VBR має пріоритет в обслуговуванні порівняно з ABR.

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

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

Відповідно до завдань керування трафіком, алгоритм індикації явної швидкості повинен робити справедливий розподіл пропускної здатності при максимізації завантаження каналу й стабілізації довжини черги комутатора. Керування чергою в контексті алгоритмів явної індикації швидкості трафіка ABR - це варіювання величини ресурсу, що розподіляється, залежно від довжини черги. Найвідоміші роботи в напрямку дослідження й розвитку алгоритмів керування трафіком в АТМ належать Ш. Кальянораману й К. Рамакришнану.

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

Незважаючи на застосовувані механізми керування трафіком, буфери комутаторів можуть бути переповнені, що неминуче призводить до примусового відкидання комірок і, в першу чергу, потоків з низьким пріоритетом.

На ефективність служби ABR впливають механізми відкидання комірок (превентивного відкидання й відкидання залишків пакета). Статичний алгоритм відкидання комірок жорстко контролює частку буфера для комірок одного з'єднання. При заповненні цього простору починається відкидання комірок даного з'єднання, якщо навіть у цілому завантаження буфера невисоке, що означає неефективне використання буфера й нерівномірний розподіл ресурсів. Крім того такий алгоритм не враховує належність комірок до більш або менш пріоритетних потоків.

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

Існуючі методи керування трафіком ABR мають такі недоліки:

-

-

-

-

-

-

-

-

Підвищити ефективність передачі трафіка ABR можна шляхом розробки і застосуваня нових механізмів керування потоком, розподілу ресурсів і керування чергами. Вирішення даної проблеми може бути досягнуте за рахунок розробки механізмів керування трафіком ABR, заснованих на справедливому розподілі ресурсу в комплексі з керуванням чергами. Напрямком проектування є справедливий розподіл ПЗ для з'єднань ABR при ефективному контролі черг комутаторів. Другим напрямком є розробка ефективного механізму індикації й відкидання при перевантаженнях. Створені алгоритми повинні гарантувати стійке функціонування й відповідати вимогам ATM-форуму.

Відповідно до аналізу предметної області та враховуючи недоліки існуючих механізмів, для досягнення поставленої мети - підвищення ефективності системи керування трафіком мереж АТМ - необхідно вирішити наступні завдання:

-

а) згідно з максимінним критерєм;

б) відповідно до розподілу з N-ядра;

-

-

-

-

-

У другому розділі розглядаються задачі, які вирішуються при керуванні трафіком ABR. Наводяться розроблені автором дисертації методи підвищення ефективності керування трафіком ABR і алгоритми, отримані на їх основі.

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

-

-

-

Задача керування потоком має наступну математичну постановку:

Керування трафіком АТМ використовує зворотний зв'язок адресат-джерело з метою приведення у відповідність змінної вільної ПЗ зі змінними вимогами джерел. Опишемо розімкнуту систему. Через обмежуючий комутатор проходять некерований трафік VBR і керований трафік ABR. Співвідношення між потоком ABR і вільною П.З у точці обмеження:

(1) , де

di(t): бажана швидкість і-го джерела в момент часу t, mi di(t)Mi;

ri(t): швидкість і-го джерела в момент t установлена мережею, mi ri(t)Mi;

Tid: затримка поширення від і-го джерела до точки обмеження трафіка (Tdmin Tid Tdmax);

qa(t): число комірок ABR у черзі обмежуючого порту в момент (qa(t)<B);

Ca(t): доступна для ABR ПЗ (K x С< Ca(t)<C, где 0K1);

pa(t): коефіцієнт завантаження ПЗ ABR у момент t ( 0 pa(t)1 и pa(t)=1, коли qa(t)>0);

na(t): число активних джерел ABR у момент t (0 na(t)N).

Рівняння дає співвідношення між вимогами ABR, ПЗ, довжиною черги й завантаженням (баланс комірок). Ліва частина - загальна вимога ABR у момент t - сума вимог джерел із затримкою. Вимога кожного джерела - мінімум між бажаною швидкістю й швидкістю, установленою мережею. Права частина - сума швидкості збільшення черги ABR і ПЗ, помноженої на коефіцієнт завантаження. У цілому - вимоги джерел ABR впливають на завантаження й швидкість збільшення черги.

Одна із задач алгоритму комутатора - обчислення й передача джерелам сигналів зворотного зв'язку ri(t) відповідно до алгоритму індикації швидкості. Згідно з задачами керування трафіком, здача може бути розглянута як задача максимізації завантаження каналу

Max pa(t) (2)

Стосовно до (1) це означає існування деякого , що

(3)

Така постановка задачі не враховує стан черги (при зменшенні ПЗ зростає довжина черги, 2-й індикатор перевантаження).

Аналогічно, можна розглядати задачу керування чергою при дотриманні максимінного критерію з обмеженнями (3):

Min qa(t)-qo(4)

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

На практиці стан каналу враховується в завданні у вигляді функції керування чергою f(qa(t)). Розглядається задача (2) з обмеженнями у вигляді:

(5)

Функція f(qa(t)) повинна задовольняти умовам:

-

-

-

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

Якщо замість максимінного критерію застосувати розподіл ресурсу з N-ядра:

, де, при деякому , R-сумарна величина ресурсу, що розподіляється, dі - вимога і-го учасника, sі- виділений і-му учасникові ресурс. Тоді обмеження в задачі (2) матиме вигляд:

(6)

при або

(7)

при .

Таким чином, потрібно знайти значення ri та , які максимізують (2) при обмеженнях (6) або (7).

Алгоритми керування трафіком повинні задовольняти вимогам ефективності, справедливості розподілу ресурсів, стійкості, оперативності, масштабованості, робастності, обчислювальної складності та відповідності стандартам. У роботі пропонуються наступні рішення поставлених завдань:

Алгоритм розподілу ПЗ відповідно до N-ядра.

Автором дисертаційної роботи запропонована реалізація методу розподілу ресурсу з N-ядра й уперше розроблений алгоритм явної індикації швидкості на основі розподілу з N-ядра (NDA - N-Kernel Dіstrіbutіon Algorіthm):

,

де d - величина бажаної швидкості потоку, R – величина ресурсу, що розподіляється (ПЗ), sі - виділений і-му учасникові ресурс. Значення визначається на початку кожного інтервалу керування: ,

де розподілена на попередньому часовому інтервалі величина ПЗ, Nact- число активних у цей момент з'єднань. Величина R, залежно від реалізації алгоритму, може бути отримана в результаті виміру доступної ПЗ, а також варіюватися залежно від довжини черги.

Алгоритм досягає ефективного стану за рахунок використання індикатора перевантаження . У сталому режимі задана ПЗ розподіляється повністю. Справедливість одержуваного розподілу гарантується критерієм N-ядра, що дає, однак, інший, ніж максимінний критерій, розподіл. Модифікація алгоритму, який змінює значення ПЗ, що розподіляється, шляхом множення на функцію керування чергою, використовує тим самим другий індикатор перевантаження (довжину черги) і дозволяє контролювати затримку черги, підвищуючи в такий спосіб ефективність і стійкість алгоритму.

Ітераційний алгоритм рівномірного розподілу пропускної здатності.

Автором дисертації запропонована ітераційна схема розподілу ресурсів. Нехай обсяг ресурсу, що розподіляється, дорівнює R, число учасників розподілу дорівнює n, для кожного учасника Aі величина вимоги дорівнює dі а величина виділеного ресурсу sі. - розподілена величина ресурсу. Для кожного учасника встановлюється біт fі=1, якщо sі=dі. Якщо sі<dі , то fі=0. ; nsat<=n. Початковим розподілом ресурсів може бути будь-яке сполучення , де R - доступна величина ПЗ.

Для кожного Aі : якщо , то виділений ресурс . Інакше . Обсяг виділеної частки ресурсу не може перевищувати величини вільного ресурсу. При незмінних величинах вимог dі величини виділюваних часток sі прямують до стійкого розподілу. При сталому розподілі величина розподіленого ресурсу Rall не перевишує величини всього ресурсу R і може становити близько 92-95% величини R. Це є прийнятним для каналів, де розподіляється не вся пропускна здатність.

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

На основі запропонованого методу розподілу ресурсів розроблений алгоритм:

1. Нехай величина пропускної здатності, доступної трафіку, ABRcap, а число активних потоків nact. Для кожного потоку комутатор зберігає величину виділеного ресурсу eі й біт стану fі. При активації з'єднання fі=1, eі=0. Комутатор обчислює nsat=fi и CAPfree=ABRcap-ei.

2.При одержанні зворотної RM комірки в ній установлюється нове значення індикації швидкості:

, де BRMі[ER] - значення індикації, отримане в цій комірці.

Для поліпшення характеристик керування пропонується робити обчислення доступної ПЗ із наступним згладжуванням величини й обмежувати ширину каналу, що розподіляється, залежно від довжини черги ABRcap=f(QABR)*(LІNKcap-VBRcap), де f(QABR) - деяка функція керування чергою.

З метою обліку стану індивідуальних черг віртуальних з'єднань пропонується застосувати функцію керування для корекції виділеної частки ресурсу залежно від довжини черги потоку. Для дотримання балансу будемо використовувати лінійну функцію. Фактор множення швидкості з'єднання прямує до 2 при зменшенні довжини черги й обмежений знизу величиною 0,5. Значення параметрів модифікованого алгоритму отримані експериментальним шляхом. У цьому випадку формула приймає вигляд

,

де , QABR - запланована довжина класової черги, qі - згладжена величина черги потоку. Таким чином, алгоритм буде відповідати вимогам керування чергою й дозволятиме контролювати середню затримку в черзі.

У деяких випадках, при коливаннях доступної ПЗ високої частоти й значної амплітуди, відомі алгоритми не в змозі розвантажити чергу, що призводить до тривалих інтервалів перевантаження, супроводжуваних коливаннями черги трафіка ABR. Для вирішення цієї проблеми застосовано підхід, що ставить у залежність цільове значення довжини класової черги від величини довгострокового ковзного середнього доступної ПЗ:

, де поточне значення залежить від згладженої оцінки ПЗ ABRcapt, а значення - бажана довжина черги при доступній ПЗ ABRcap0.

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

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

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

Двокроковий метод явної індикації швидкості.

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

Схема обробки RM комірок припускає роздільний розподіл ресурсу для прямих і зворотних RM комірок і дозволяє зменшувати величину виділеної смуги для тих потоків, які не в змозі використати наявний ресурс. За цією схемою автором уперше розроблений двокроковий метод (локалізації "вузького горла"), що базується на дворазовому застосуванні ітераційного алгоритму рівномірного розподілу ресурсів (окремо для прямих (величина ) і зворотних (величина ) службових комірок) і порівнянні їхніх результатів. При відсутності перехідних процесів у мережі . Значна нерівність свідчить про наявність обмеження швидкості нижче по маршруту передачі. При відмінності й більш, ніж на деяку величину (тобто.>1+), перевищуючу частку зменшити з коефіцієнтом k1. .

У іншому випадку величина все одно буде використана не повністю. Різниця пропускної здатності може бути повернута в пул вільного ресурсу, після чого перерозподілена між іншими потоками.

Співвідношення може виникнути в перехідному стані при збільшенні завантаження в одному з комутаторів (наявності "вузького горла" вище по віртуальному шляху) або у випадку зменшення вимоги джерела. У цьому випадку виділена смуга також може бути перерозподілена. Тому значення зменшується до .

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

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

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

Іншим аспектом, що вимагав додаткових досліджень, було застосування моделі самоподібного (self-sіmіlar) трафіка. Традиційний аналіз черг, в основі якого лежить припущення про пуасонівський потік (мультиплексування великої кількості незалежних потоків даних дає в результаті пуасонівський), не може точно прогнозувати продуктивність системи в деяких умовах, менш адекватний даним експериментальних досліджень і дає занижені оцінки довжин черг.

Модель повинна точно відтворювати архітектуру АТМ мережі й характеристики мережного устаткування, зокрема алгоритми керування трафіком:

1.

2.

3.

4.

Вимоги до експериментів:

1.

2.

Сценарії, що містять в собі топології мережі й параметри джерел трафіка, дозволяють досліджувати роботу алгоритмів у достатньому діапазоні модельних ситуацій на предмет відповідності алгоритмів завданням ефективності, справедливості, стійкості й необхідним перехідним характеристикам. Проведемо дослідження поводження керованого трафіка ABR при впливі пріоритетного трафіка VBR. Всі вхідні потоки джерел VBR мають самоподібне (self-sіmіlar) розподілення. Інтенсивність джерел трафіка ABR змінюється відповідно до механізму зворотного зв'язку. Інтенсивність джерел трафіка VBR, що має пріоритет над трафіком ABR, постійна, за винятком четвертої серії експериментів.

Будемо порівнювати три модифікації ітераційного алгоритму явної індикації швидкості трафіка ABR з алгоритмом на основі розподілу з N-ядра й еталонним алгоритмом ERІCA. Позначимо Іter-MQ - ітераційний алгоритм явної індикації швидкості трафіка ABR, Іter-MQV - ітераційний алгоритм із керуванням чергами потоків, Іter-MQV2 - прискорений ітераційний алгоритм із керуванням чергами потоків, NDA - алгоритм явної індикації швидкості трафіка ABR на основі розподілу з N-ядра, ERІCA - еталонний алгоритм.

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

Для порівняння характеристик досліджуваних алгоритмів спостерігаються наступні метрики: інтенсивності джерел ABR, довжини черг трафіків і окремих потоків, сумарна величина ресурсу, що розподіляється, завантаження каналу, затримка й продуктивність.

У всіх експериментах час перехідного процесу (від запуску імітації до досягнення сталого режиму) не перевищує 20мс. Виходячи із цього, мінімальним буде час прогону, рівний 100мс. В експериментах із зовнішньою зміною стану системи буде потрібний час прогону до 200 мс. Для експериментів кожної серії забезпечена однакова послідовність датчика випадкових чисел, що дозволило одержати рівні характеристики трафіка VBR у всіх експериментах серії. Тим самим для трафіка ABR створені рівні умови у всіх експериментах серії. Попередні дослідження свідчать, що вибірки з вихідних параметрів Load (навантаження), CTD (затримка) і CDV (варіація затримки) задовольняють нормальному закону розподілення.

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

Інші сценарії дозволяють досліджувати перехідні характеристики алгоритмів і містять тест на адаптацію нового з'єднання ABR, тест в умовах змінюваного числа джерел ABR і тест "виживання" алгоритмів - в умовах різкої зміни інтенсивності пріоритетного трафіка. Їхнє завдання - досліджувати властивості збіжності й стійкості алгоритмів, а також адаптацію до змін величини доступної ПЗ.

Другий сценарій експериментів дозволяє досліджувати встановлення нового з'єднання ABR порівнюваними алгоритмами. Експерименти дають можливість досліджувати збіжність до рівномірного розподілу й коливання метрик алгоритмів при адаптації нового з'єднання.

Третій сценарій експериментів дозволяє порівнювати ефективність і стійкість алгоритмів в умовах змінюваної активності ABR джерел.

Четвертий сценарій експериментів дає можливість порівнювати стійкість алгоритмів і усунення перевантажень в умовах різкого зростання інтенсивності пріоритетного трафіка.

П'ятий сценарій експериментів дозволяє досліджувати роботу механізму адаптивного відкидання в порівнянні з механізмами EPD і TPD в умовах малих і великих втрат.

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

Сценарий | Iter-MQ | Iter-MQV | Iter-MQV2 | NDA | ERICA

1 |

CTD, mks | 361,69 | 342,59 | 334,84 | 336,40 | 355,82

CDV, mks | 154,42 | 131,55 | 121,42 | 121,97 | 144,17

Load, Kcells | 961,63 | 975,71 | 993,61 | 966,11 | 954,27

2 |

CTD, mks | 362,50 | 342,11 | 335,16 | 336,53 | 356,69

CDV, mks | 154,76 | 129,46 | 122,08 | 122,32 | 145,36

Load, Kcells | 1447,5 | 1472,1 | 1500,8 | 1461,5 | 1434,3

3 |

CTD, mks | 391,04 | 375,09 | 364,53 | 384,29 | 392,70

CDV, mks | 162,12 | 141,54 | 131,46 | 168,08 | 174,34

Load, Kcells | 1161,9 | 1150,9 | 1120,6 | 1123,6 | 1149,7

4 |

CTD, mks | 382,49 | 357,04 | 343,05 | 342,51 | 383,58

CDV, mks | 242,49 | 197,46 | 166,24 | 161,03 | 249,83

Load, Kcells | 1863,6 | 1924,6 | 1958,7 | 1906,0 | 1852,5

Розроблений ітераційний алгоритм демонструэує збіжність до справедливого розподілу ПЗ, зниження коливань затримки, швидке усунення перевантажень й збільшення продуктивності в порівнянні з ERІCA. У свою чергу, алгоритм ERІCA, хоча й задовольняє вимогам до такого класу алгоритмів, але демонструє більше зростання черг, коливання затримки й порушення умови справедливості при перевантаженні (сценарій 4).

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

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