Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
- 27 -
НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ
НАЦІОНАЛЬНЕ КОСМІЧНЕ АГЕНТСТВО УКРАЇНИ
ІНСТИТУТ КОСМІЧНИХ ДОСЛІДЖЕНЬ
УДК 681.142
Гонтаренко Ірина Сергіївна
ПРОЦЕДУРИ КЕРУВАННЯ МНОЖИННИМ ДОСТУПОМ
ДО КАНАЛУ З ПАРАЛЕЛЬНОЮ ПАКЕТНОЮ ОБРОБКОЮ
01.05.04 - системний аналіз та теорія оптимальних рішень
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Київ –
Дисертацією є рукопис.
Роботу виконано в Інституті космічних досліджень НАНУ та НКАУ.
Науковий керівник: доктор технічних наук, с.н.с. Бунін Сергій Георгійович
Офіційні опоненти: доктор технічних наук, професор Коваленко Ігор Іванович,
Інститут прикладного системного аналізу НАНУ
та Міністерства освіти та науки України, заступник директора
кандидат технічних наук, c.н.с. Войтер Анатолій Петрович,
Інститут ядерних досліджень НАНУ, завідуючий відділом
Провідна установа:
Київський національний університет України ім. Тараса Шевченка,
кафедра теоретичної кібернетики.
Захист відбудеться "" березня 2002 р. о 15 годині на засіданні спеціалізованої вченої ради Д 26.205.01 в Інституті космічних досліджень НАНУ та НКАУ
за адресою: 03187, м. Київ -187, просп. академіка Глушкова, 40.
З дисертацією можна ознайомитись в архіві
Інституту космічних досліджень НАНУ та НКАУ
Автореферат розіслано "11" лютого 2002 р.
В. о. вченого секретаря
спеціалізованої вченої ради
д.т.н. , с.н.с. Зєлик Я.І.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. В системах, що реалізують одночасну взаємодію множини процесів із деяким одним процесом чи спільним для них ресурсом, оптимальна процедура керування множинним доступом є одним з основних факторів, які визначають якість функціонування системи. Проблема організації множинного доступу актуальна для радіо та комп’ютерних мереж, телекомунікаційних систем та технічних пристроїв із паралельною обробкою. Однак у ряді випадків її рішення з урахуванням усієї різноманітності вимог до системи та її властивостей пов'язано з необхідністю вдосконалення відповідної апаратури, що не завжди може бути виконано. Тому основною галуззю застосувань для досліджень у цьому напрямку стають сьогодні системи радіотелефонії. З одного боку, як наслідок їхньої постійно зростаючої популярності, збільшується потужність абонентського комплексу та зростає навантаження на існуючу апаратуру, що обумовлює необхідність якісно нових рішень. З іншого боку, із тієї ж причини в галузь радіотелефонії надходить достатня кількість інвестицій, що стимулює технологічний прогрес та дозволяє розробляти нові підходи до процедур оптимального розподілення ресурсів системи.
Існуючі системи множинного доступу Multiple access (МА) мають обмеження на кількість вимог, що одночасно обслуговуються, порушення якого породжує конфлікти. Так саме наявність конфліктів у системах зв'язку з кодовим поділом каналу (CDMA) призводить до того, що ефективність використання робочої смуги частот є низькою. Тому пропонується оптимізувати їхню роботу за рахунок механізмів, що реалізовані в процедурах впорядкування множинного доступу одного з альтернативних напрямків часового поділу (TDMA). Аналізу систем на основі цих протоколів присвячені класичні дослідження Ерланга, Клейнрока та Тобаги. Напрямки сучасних досліджень відображають роботи Цибакова, Михайлова, Буніна, Войтера.
Розробка більш складних протоколів, що поєднують можливості різних підходів до організації динаміки функціонування системи, може дати ефективні рішення актуальних у теперішній час проблем. Так, наприклад, в рамках сучасного стандарту IS661 пропонується поєднання кодового розподілу з методами множинного доступу з розподілом часу. Аналіз результатів, отриманих для систем радіозв'язку, вказує на можливість їхнього використання в інших системах із схожими характеристиками.
Зв’язок роботи з науковими програмами, планами, темами. Робота виконана у відділі Передачі даних Інституту космічних досліджень НАНУ та НКАУ в рамках основних наукових програм та тем:
Мета та задачі досліджень. Метою дисертаційної роботи є розробка ефективного рішення проблеми організації динаміки функціонування систем множинного доступу у системах із паралельною обробкою пакетів за рахунок процедур, що знижують вплив можливих конфліктів на якість обслуговування. Для реалізації поставленої мети повинні бути виконані наступні задачі :
Наукова новизна отриманих результатів. В дисертаційній роботі викладаються вперше отриманні результати :
Асинхронний протокол множинного доступу із сигналом зайнятості (МДСЗ) у системах із паралельною передачею пакетів, що здійснюється за допомогою кодового розподілу (CDMA);
Асинхронний протокол МДСЗ із процедурою розв’язання конфліктів в системах із паралельною передачею пакетів;
Синхронний протокол МДСЗ в системах із паралельною передачею пакетів;
Протокол множинного доступу з резервуванням для систем із паралельною передачею пакетів.
Практичне значення отриманих результатів. На основі отриманих у даній роботі результатів можливе створення нових систем зв'язку с CDMA, у тому числі й супутникових систем зв'язку, що більш ефективно використовують можливості, які надаються паралельною передачею пакетів. Протоколи, запропоновані в роботі, дозволяють підвищити значення пропускної здатності каналу, а також показники якості обслуговування. Це надає можливість організувати більш ефективне функціонування системи в умовах підвищеного навантаження. Аналіз розроблених протоколів враховує фактор затримки передачі сигналу (залежний від віддаленості супутника у випадку супутникових систем), тому є можливий вибір найбільш відповідного для конкретних значень параметрів мережі протоколу. На основі розробленого в роботі математичного апарата дослідження показників якості обслуговування був виконаний аналіз характеристик системи радіозв'язку при виконані робіт за проектом інтеграції обладнання сотового зв’язку “Alcatel” з системою “Customer care” для компанії UMС.
Особистий внесок пошукувача. В роботах [3, 4] дисертанту належить розробка протоколів множинного доступу, дослідження характеристик протоколів та чисельний аналіз параметрів систем на їхній основі. В роботі [2] дисертанту належить розробка та дослідження характеристик протоколу. В роботі [1] дисертанту належить опис процедур роботи абоненту та ретранслятору, аналітичне дослідження характеристик протоколу. Пошукувачем були самостійно розроблені математичні моделі систем масового обслуговування на основі запропонованого підходу до розподілу каналу. Були доведені необхідні твердження та аналітично отриманні ймовірності оцінки значень основних параметрів систем.
Апробація результатів дисертації. Результати, отриманні в дисертації, були представлені в доповідях на міжнародних конференціях "Автоматика 2000" (Львів, 2000) й "Автоматика 2001" (Одеса, 2001) та на семінарах у Київському Національному університеті ім. Т.Г. Шевченко та "Дискретні системи керування" в Інституті космічних досліджень.
Публікації. Основні результати дисертації викладено в 7 публікаціях у фахових наукових виданнях, у тому числі 4 статтях в журналах із спеціального списку ВАК України (одна без співавторів) та 3 тезах доповідей в матеріалах конференцій.
Структура та обсяг роботи. Дисертація складається з вступу, 4 розділів основної частини, висновків, списку використаних джерел (з 115 найменувань на 10 сторінках), та одного додатку на 9 сторінках. Основний зміст роботи викладено на 130 сторінках машинописного тексту, ілюстрованих 24 рисунками та 4 таблицями.
ЗМІСТ РОБОТИ
У вступі обґрунтовано актуальність теми дисертації. Сформульована мета роботи та основні здачі дослідження. В загальних рисах наведено характеристику роботи.
В першому розділі наводиться огляд існуючих підходів та розглядається коло застосувань, пов'язаних із проблемою множинного доступу. Так, обговорюються тенденції розвитку в області мережевих технологій та радіотелефонії. Показується ефективність цифрової передачі для телефонії, та в той же час важливість використання засобів радіоканалу для здійснення комутації між доменами глобальної мережі Internet. В обох випадках виникає конкуренція за доступ до середовища передачі та вирішуються спільні задачі.
На базі огляду існуючих підходів до розподілу каналу, розроблених у телефонії, зроблено висновок, що найбільш універсальний та широко використовуємий на сьогодні метод кодового розподілу каналу недостатньо ефективно використовує смугу частот. Для підвищення ефективності можна було б використовувати процедури, аналогічні протоколам множинного доступу з розподілом часу, відомим у телефонії.
При цьому можна розглядати канал передачі даних, що є головним функціональним ланцюгом системи зв'язку, як підсистему мережі. Дійсно, мережа являє собою ієрархічну структуру, що реалізує взаємодію відкритих підсистем, кожній з яких відповідає свій рівень ієрархії. Згідно прийнятому стандарту, структурі мережі відповідає семирівньова модель, один із нижніх рівнів якої, транспортний, містить канальний підрівень. Функцією цього підрівня є перетворення довільного потоку пакетованої інформації, що надається вищим рівнем, в форму, яка є доступною для обробки фізичними пристроями нижнього рівня. Взаємодія рівнів відбувається згідно міжрівньовим протоколам. Протокол являє собою сукупність формалізованих правил обміну інформацією між процесами в мережевому середовищі. Мета розробки протоколів множинного доступу до каналу полягає в зазначенні правил, реалізація яких при заданому вхідному потоці представляє алгоритм керування множинним доступом, що дозволяє організувати процес упорядкованої передачі пакетів незалежно від фізичного стану каналу.
Основними критеріями ефективності роботи каналу є швидкість та надійність передачі інформації. Тому аналіз існуючих протоколів включає оцінку ефективності використання каналу (максимальної середньої швидкості передачі), та якості обслуговування, що надається системою, яка реалізує протокол (його середній тривалості для одного пакету та середній кількості пакетів, які обслуговуються). Для цього розглядається модель масового обслуговування, яка відповідає протоколу, та аналізується динаміка системи. Для аналізу відомих протоколів, у припущенні, що тривалість обслуговування розподілена експоненціально, використовується апарат ланцюгів Маркова. В випадках, коли це не так, виникає потреба в розробці більш складного математичного апарату. На сьогодні не існує загального підходу, що дозволяв би для кожної системи множинного доступу, запропонувати достатньо просту адекватну формалізацію динаміки її функціонування.
У другому розділі формулюються задача організації множинного доступу, в контексті системного аналізу, та необхідні визначення, пропонуються відповідні протоколи множинного доступу.
Процедура керування множинним доступом організує процес інформаційної взаємодії у системі , де множина вузлів (абонентів) системи, а обслуговуючий пристрій (ретранслятор), з метою перетворення інформаційного потоку Ру потік Р, як показано на рис.1.
Рис.1. Схема інформаційних потоків у системі множинного доступу.
Алгоритм А, що реалізує процедуру розподілу, задає відображення
. (1)
При відсутності додаткових обмежень, алгоритм А визначається наступними факторами:
Для обґрунтування доцільності використання в системах зв’язку з СDMA протоколів множинного доступу, що здійснюють розподіл часу, розглядається множина протоколів, що реалізовані в системах зв’язку із простими сигналами, тобто з k = 1. З точки зору системного аналізу, задача полягає у відшуканні в множині всіх можливих протоколів цього класу такого протоколу, під час реалізації якого величина пропускної здатності системи, буде максимальною в порівнянні з відповідними величинами, що можуть бути отримані при реалізації всіх інших протоколів:
. (2)
Показується, що операція порівняння ефективностей протоколів задає порядок на множині протоколів одного класу:
. (3)
Визначається клас протоколів, кожен з яких модифікує деякий з існуючих протоколів ТDMA, для використання в системах зв’язку із складними сигналами (k 1):
. (4)
Для протоколів класу k можна припустити справедливість наступних умов:
1. Для кожного протоколу класу відповідний йому протокол класу kмає кращу пропускну здатність :
. (5)
2. Будьякий протокол класу kзабезпечує значення пропускної здатності, що перевищує ефективність передачі в системі СDMA без розподілу часу.
Виконання цих умов мотивує створення нових протоколів, які модифікують вже існуючи в системах із часовим розподілом для використання в системах із кодовим розподілом.
Додатковою підставою для створення протоколів із розподілом часу в системах СДМА є та обставина, що вони надають можливість підлаштування системи до вхідних параметрів, таких як відстань, на яку потрібно забезпечити зв’язок, потужність абонентського комплексу, навантаження на мережу.
Розробляються та описуються наступні протоколи множинного доступу з розподілом часу для систем зв’язку зі складними сигналами :
Далі визначається поняття робочого циклу, яке є необхідним для аналізу ефективності протоколу. Пропонується розглядати цикл, як послідовність двох фаз, початкової та фінальної. Початкова фаза циклу однорідна в наступному розумінні: на кожному її одиничному відрізку приходить не більш ніж k і не менш одного пакету. Вона може мати необмежену тривалість. Фінальна фаза циклу завжди має скінчену довжину та відлічується з моменту початку прийому ретранслятором деякого пакета, за час обробки якого приходить більш ніж k нових, або не приходить жодного. Завершення фази відбувається в момент повного припинення ретранслятором прийому пакетів при виконанні однієї з умов: якщо, при наявності конфлікту, завершується прийом останнього пакета учасника конфлікту; якщо за час обробки деякої вимоги відсутнє надходження нових вимог.
Формулюються та доводяться наступні твердження :
Твердження 1. Тривалість фінальної фази обмежена зверху числом 2+2а.
Твердження 2. Для тривалості циклу, початкової та фінальної фаз виконується нерівність:
. (6)
Повне число успішних передач циклу є сумою чисел успішних передач його початкової та фінальної фаз:
. (7)
З урахуванням прийнятого означення циклу для кожного з чотирьох протоколів описані процедури абонентів та ретранслятора. Проаналізовано структуру циклу (рис.2) для всіх запропонованих протоколів.
Рис.2. Структура циклу для асинхронного протоколу МДСЗ.
У розділі 3 досліджується ефективність систем з паралельною обробкою на основі запропонованих протоколів керування, для цього визначається середня швидкість передач фінальної фази в каналі , де NF середнє число успішних передач, а ТF середня тривалість фінальної фази циклу, а далі SР середня швидкість передач, що досягається в початковій фазі. Cередня швидкість передач повного циклу з урахуванням довжини початкової фази ТР, визначається рівнянням:
, (8)
де Т, повна тривалість циклу, задовольняє умові (5).
При знаходженні пропускної здатності каналу у фінальній фазі циклу для кожного з протоколів аналогічним чином шукаються значення середнього числа успішних передач та тривалості фінальної фази циклу.
Для простих асинхронних та синхронних протоколів МДСЗ середнє число успішних передач у фінальній фазі не повинно перевищувати k. Єдина відмінність полягає в умові успішності передач поточного циклу. В синхронному протоколі після приходу (k1) го пакету, коли настає інтервал вразливості, причиною конфлікту можуть стати тільки ті пакети, що надходять в першій його половині, тому інтервал вразливості, по суті, зменшується в два рази. Середнє число успішних передач фінальної фази в асинхронному та синхронному протоколах дорівнює, відповідно :
(9)
й . (10)
Для знаходження середньої тривалості циклу, визначається середній час приходу останнього пакета TL.При обчисленні середнього часу приходу останнього пакета враховується можливість як успішного, так і невдалого прийому пакетів, що передаються. Для асинхронного та синхронного протоколів, відповідно, одержуємо:
, (11)
. (12)
Середня тривалість фінальної фази задається сумою
в асинхронному протоколі , (13)
в синхронному протоколі . (14)
Остаточні формули для середньої швидкості передач в асинхронному та синхронному протоколах:
(15)
. (16)
На основі графіків залежності середньої швидкості передачі каналу від інтенсивності вхідного потоку пакетів при різних значеннях параметрів а (затримки сигналу) та k (максимальної припустимої кількості пакетів, що одночасно обробляються), один з них наведено на рис.3, зроблено порівняльний аналіз можливостей запропонованих протоколів.
а) б)
Рис.3 Залежність середньої швидкості передавання від інтенсивності трафіка при значеннях а = 0.01, та к =2 (1), к =5 (2), к =10 (3)
а) в асинхронному МДСЗ, б) у синхронному МДСЗ.
При знаходженні пропускної здатності каналу у фінальній фазі циклу для асинхронного протоколу МДСЗ із процедурою вирішення конфліктів враховується додаткова кількість передач, що реалізуються у фазі розв’язку конфліктів N, та тривалість фази.
Для середньої кількості передач, що реалізовані в циклі с конфліктом, N та середньої швидкості передавання одержується, відповідно:
, (17)
, (18)
де доданки N та T описують завершення циклу, коли абонентами мережі здійснюється безконфліктна передача. Графіки рис. 4 показують, що при збільшені затримки, коли внесок конфліктних циклів зростає настільки, що МДСЗ стає неефективним, ПРК дає можливість зберегти прийнятні значення пропускної здатності.
а) б)
Рис.4. Залежність середньої швидкості передачі від інтенсивності трафіка при значеннях к =7, а = 0.01 (1), а = 0.1 (2), а = 0.5 (3)
а) в асинхронному МДСЗ, б) в асинхронному МДСЗ з ПРК.
Пропускна здатність каналу в початковій фазі циклу, згідно її визначенню, даному у другому розділі, дорівнює
. (19)
Тривалість початкової фази циклу є зважена сума інтервалів часу, які отримуються зсувом :
. (20)
Момент TL приходу останньої в кожному з одиничних відрізків, що розглядаються, і не більш ніж kї за номером вимоги, вже було знайдено в (11) та (12), отже:
. (21)
Для асинхронного та синхронного протоколів вираз (21 ) прийме вигляд :
(22)
й , (23)
де NF та TF значення пропускної здатності у фінальній фазі циклу, отриманні для відповідних протоколів.
Пропускна здатність у системах із резервуванням знаходиться для повного циклу роботи, оскільки він, за визначенням, має скінчену тривалість. Успішна передача основних пакетів відбувається в двох випадках : якщо число i резервуючих пакетів, які надійшли, не перевищує k, тоді число передач в циклі дорівнює i; або передача основних пакетів відбувається аналогічно фазі розв’язку конфліктів в МДСЗ із ПРК. Середнє по всім i значення числа передач, які реалізовані в основному кадрі, дорівнює
(24)
Середній час повного циклу: , де ТR визначається як середнє число черговостей в інтервалі передачі даних:
. (25)
отриманий вираз дає рекурентну залежність для знаходження середньої тривалості nго циклу. При обчисленні значення Тn розглядалася Nа скінчена сума TR , де
, (26)
та припустима похибка при обчисленні TR, приймалась рівною 0,05. Ітераційний процес для знаходження TR є збіжним для довільного початкового значення Т із відрізка [а, [G/к]+1]. Таким чином, отриманий вираз середньої швидкості передач у циклі
може бути обчислений для будьякого заданого значення інтенсивності трафіку G. Результати обчислень для випадків, коли допустимою є одночасна передача k = 3 та k = 5 пакетів, довжина інтервалу резервування = 0.1, а тривалість захисного інтервалу, а = 0.01 наводяться в таблиці.
|
|
K=3 |
K=5 |
|
G |
||||||||||
|
N |
||||||||||
|
T |
.167 |
.44 |
.13 |
.058 |
.75 |
.828 |
.58 |
.021 |
.551 |
.83 |
|
S |
.8 |
.922 |
.830 |
.797 |
.789 |
.79 |
.274 |
.125 |
.052 |
.123 |
Як висновок порівняльного аналізу ефективності систем із розглянутими протоколами, що виконується в роботі, формулюються рекомендації щодо оптимального вибору одного з них в залежності від параметрів реальної системи.
В четвертому розділі система, що реалізує визначені протоколом процедури, розглядається з точки зору масового обслуговування. Визначаються параметри моделі масового обслуговування для систем зв’язку, робота яких основана на використанні раніш описаних протоколів.
Вхідний потік. Вважаємо, що кожній вимозі (пакету), що надходить на обслуговування, відповідає деякий вузол, що її передав. Потік вимог, що породжується кожним вузлом вважаємо пуасонівським, із параметром і для деякого вузла і, отже сумарний потік також є пуасонівським, із параметром .
Тривалість обслуговування.
Кількість обслуговуючих приладів. З врахуванням можливості паралельної обробки вимог в системах CDMA, навіть коли система має в розпорядженні один реальний обслуговуючий пристрій (ретранслятор), пропонується розглядати модель з k конфліктно залежними обслуговуючими приладами. Поки кількість заявок не перевищує k, кожна вимога обслуговується незалежно, як у ситуації обробки її окремим приладом. Але, під час конфлікту, поведінка системи направлена на його централізоване вирішення (протоколи резервування та МДСЗ із ПРК), або на запобігання його повторного виникнення (синхронний та асинхронний протоколи МДСЗ), тому обслуговування в кожному з віртуальних приладів підкоряється загальній дисципліні.
Затримка. Системи, що розглядаються, є системами з очікуванням. Його тривалість –випадкова величина, яка залежить від механізму здійснення затримки. Цей механізм є спільним для всіх протоколів МДСЗ, які ми розглядаємо. Він використовується для того, щоб зменшити ймовірність втрати пакетів, які надходять у систему в момент зайнятості каналу або поточного конфлікту, або пошкоджуються при виникненні конфлікту після їхньої передачі. Затримка є випадковою величиною з експоненціальним розподілом Р{ < 1 + t} = 1e-t із середнім значенням 1+1/.
Отже, розглядаються моделі масового обслуговування M/D/k (M/D/k/) для систем з синхронним та асинхронним протоколами МДСЗ, та M/G/k для систем МДСЗ із ПРК й систем із резервуванням (k вказує максимально допустиме число вимог, які обслуговуються одночасно).
У нашому випадку неможливо говорити про відсутність післядії, процес, що описує зміну числа вимог у системі, не є марківським. Однак, під час аналізу систем на основі синхронного та асинхронного протоколів МДСЗ можна побудувати динамічну модель функціонування систем, які ми розглядаємо, як аналог системи КолмогороваЧєпмена для марківських ланцюгів.
Стан систем обслуговування на основі запропонованих протоколів МДСЗ у деякий момент часу повністю визначається парою [M, N], де N число вимог, що обслуговуються системою в цей момент часу, а M кількість відкладених пакетів.
Для опису динаміки ймовірностей станів системи було розглянуто умови можливих переходів між станами ланцюга, що розглядається, та знайдені перехідні ймовірності:
,
,
, , (28)
де й
ймовірність приходу вимог, які раніш не передавалися, та повторного надходження вимог, які були відкладені раніш, відповідно. Для визначення стаціонарних ймовірностей записано систему різностних рівнянь, що зв’язує ймовірності в моменти часу t та t+ h. Якщо , отримаємо в лівій частині рівнянь похідні ймовірностей станів , в стаціонарному режимі вони обертаються в нуль, що дозволяє отримати систему однорідних рівнянь для знаходження стаціонарних імовірностей:
. . .
. . .
, (29)
. . .
де параметри системи: , .
Аналітичний розв’язок отриманої нелінійної нескінченновимірної однорідної системи рівнянь не виглядає можливим, тому, вважаючи m та S параметрами, розглядаємо ітераційний процес, який задано системою. При наявності стаціонарного розв’язку він має бути збіжним.
При проведенні чисельного аналізу моделі для k =1 було розглянуто скінченну кількість рівнянь системи. Отримано залежність середньої кількості відкладених пакетів від трафіка. Її вигляд свідчить про те, що зростання заборгованості зі збільшенням трафіка обмежено зверху лише числом відкладених пакетів, котрі розглядаються. Вказаний результат є наслідком обрізання системи рівнянь. При збільшенні максимального числа відкладених пакетів, що розглядаємо характер графіків не змінюється, що дозволяє припустити наявність необмеженого зростання заборгованості.
Твердження 3. У випадку k = 1 виконується: .
Відомі аналогічні результати, що отримані з аналізу стійкості синхронної Aloha. Стійкість має місце лише за умов "відсутності буферізації". Тобто в припущенні, що кожний новий пакет, котрий з'являється у абонента, перша вимога якого досі знаходиться у системі, втрачається. При цьому існує точка стійкої рівноваги системи, тобто значення трафіку, при якому швидкість виходу вимог з системи співпадає із швидкістю їхнього надходження в систему. Розглянута в роботі модель включає припущення "про нескінченну кількість абонентів". Вважається, що кожний новий пакет, котрий надходить до вузла зі старим пакетом, що не залишив систему, належить новому, віртуальному вузлу. Як відомо, для системи Aloha це спричиняє втрату стійкості, стан заборгованості необмежено зростає. У випадку, що розглядається в роботі, стійкість також відсутня, про що свідчить твердження 3.
Тому аналіз якості системи обслуговування передбачає необхідність розробки іншого підходу. Структурний аналіз тривалості обслуговування, що виконується в роботі, дозволяє з використанням ергодичності системи отримати основні характеристики якості обслуговування.
На рис. 5 показано послідовність подій, що відповідає асинхронному протоколу МДСЗ.
Рис. 5. Структура процесу обслуговування для асинхронного протоколу МДСЗ.
Середня тривалість однієї затримки дорівнює , успішного обслуговування , та середній час, що втрачає вимога у випадку конфлікту, дорівнює .
Знайдемо величину W як середнє значення часу за ймовірностним розподілом всіх можливих сценаріїв подій під час перебування вимоги в системі. Кількість затримок може прийняти довільне значення з натурального ряду, як і число попадань у конфлікт. Отже, тривалість перебування кожної вимоги в системі:
, (30)
де події tij відповідає ймовірність .
Середній час перебування вимоги в системі W є зваженою сумою: . Ймовірності подій зайнятості каналу, успішної передачі та конфлікту є відповідно, , та .
Отже, отримано середній час перебування вимоги в системі у вигляді:
(31)
Аналогічним чином виконується аналіз синхронного протоколу МДСЗ та протоколу з розв'язанням конфліктів. Вирази середньої тривалості перебування вимоги у системі для них є відповідно:
(32)
. (33)
Аналіз повного часу перебування пакета для систем з протоколом резервування не потребує врахування подій, які повторюються циклічно, щодо іншого, схема близька до наведеної вище. Середня затримка обслуговування дорівнює:
. (34)
В наслідок детермінованого характеру обслуговування, його тривалість TS є постійною для протоколу, що розглядається, величиною. Тому з отриманої величини W знаходимо затримку очікування TQ = WTS, відтак (застосовуючи теорему Літла) середню кількість вимог, що перебувають у системі N =W та очікують обслуговування NQ =TQ.
Результати обчислень за формулами (32)(34) наведені у таблиці:
|
k |
5 |
|
, =2/ |
0.5 |
|||||||
|
АМДСЗ |
5.5362 |
.3496 |
.91 |
.6610 |
.5370 |
.373 |
.816 |
|
|
СМДСЗ |
5.5628 |
.2749 |
.89 |
.6610 |
.014 |
.05 |
.707 |
|
|
МДСЗ з ПРК |
1.1743 |
.2561 |
84.46 |
1.5310 |
.187 |
.3836 |
.285 |
|
|
Резервування |
3.44 |
.44 |
3.44 |
.44 |
.44 |
.44 |
.44 |
.44 |
Таким чином, при значеннях трафіка близьких до k , оптимальним вибором є протоколи МДСЗ, для менших значень МДСЗ с ПРК.
ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ
В дисертаційній роботі вирішується проблема організації динаміки функціонування систем множинного доступу у системах із паралельною обробкою пакетів за рахунок процедур, що знижують вплив можливих конфліктів на якість обслуговування. При реалізації поставленої мети були виконані наступні задачі :
1. На основі проведеного в роботі порівняльного аналізу можливостей різних підходів до організації роботи мереж передачі даних запропоновано класифікацію протоколів множинного доступу з часовим розподілом.
ОСНОВНІ РОБОТИ ОПУБЛІКОВАНІ ЗА ТЕМОЮ ДИСЕРТАЦІЇ:
АНОТАЦІЇ
Гонтаренко І.С. Процедури керування множинним доступом у системах із паралельною пакетною обробкою. - Рукопис.
Дисертація на здобуття вченого ступеня кандидата технічних наук із спеціальності 01.05.04. - Системний аналіз та теорія оптимальних рішень. - Інститут космічних досліджень, Київ 2002 р.
В дисертаційній роботі розроблені та досліджені протоколи керування множинним доступом, які дозволяють підвищити ефективність паралельної обробки даних за рахунок процедур, які зменшують вплив можливого конфлікту на якість обслуговування та зменшують імовірність його виникнення; побудовані та досліджені математичні моделі систем на основі запропонованих протоколів. Протоколи, розглянуті в роботі, дозволяють реалізовувати ефективні з точки зору використання каналу процедури керування множинним доступом із врахуванням характеристик реальних систем.
Ключові слова: протокол керування, множинний доступ, складний сигнал, кодовий розподіл, паралельна обробка, розв’язок конфліктів, резервування, пропускна здатність, пакетна обробка.
Gontarenko I.S. The procedures of multiple access control in the systems with parallel packet processing. –Manuscript. – Thesis for a candidate of technical science degree by specialty 01.05.04 - System analysis and theory of decision making. - Institute of space researches, Kyiv, 2002.
The protocols of multiple access control have developed into the candidate thesis allow to increase efficacy of parallel packet processing by the procedures, which decrease a possible conflict influence to quality operating (service) and reduce expectancy of rise its. Mathematics models have built for systems on basis of offered protocols. Concerned in thesis protocols allow to realize optimal multiple access control procedure with viewpoint of channel using efficacy depending on different characteristics of possible systems.
Key words : control protocol, multiple access, mathematic model, carrying capacity, division of channel, packet processing.
Гонтаренко И.С. Процедуры управления множественным доступом в системах с параллельной пакетной обработкой. - Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.04. - Системный анализ и теория оптимальных решений. - Институт космических исследований, Киев 2002.
В диссертационной работе рассматриваются системы, где параллельное обслуживание допустимо для ограниченного числа пользователей. Его превышение порождает конфликтные ситуации, приводящие к потере требований и необходимости их повторного обслуживания. При этом снижается эффективность работы обслуживающего прибора и ухудшается качество обслуживания. Поэтому при проектировании таких систем разрабатываются процедуры, разрешающие ситуацию конфликта и снижающие вероятность его возникновения. В качестве примера рассматриваются широкополосные системы связи (ШСС), где параллельность обработки достигается за счет кодового разделения передач отдельных абонентов. ШСС, являющиеся одним из важнейших приложений, основанных на параллельной обработке пакетов, обладают перечисленными недостатками и потому недостаточно эффективно используют канал - основной ресурс системы. В работе показано, что использование процедур разделения времени позволяет увеличить пропускную способность канала, и более гибко организовывать работу системы, в зависимости от таких ее параметров, как задержка, емкость канала, величина нагрузки. В диссертации обосновывается целесообразность разработки процедур управления множественным доступом, осуществляющих разделение времени в системах с параллельной обработкой, основанной на подходе СDMA. Разрабатываются новые протоколы, регламентирующие процесс множественного доступа в ШСС:
Для каждого из перечисленных протоколов разрабатываются процедуры абонентов и ретранслятора, анализируется структура рабочего цикла. С целью анализа характеристик системы вводятся понятия начальной и финальной фаз цикла.
Для исследования эффективности функционирования систем на основе предложенных протоколов выводится выражение зависимости средней скорости передач от интенсивности входного потока. Приводится сравнительный анализ полученных протоколов, зависимости показателя эффективности каждого из них от величин задержки и емкости канала. Наименее чувствительным к увеличению задержки передачи в системе оказывается протокол множественного доступа с резервированиям. Далее в порядке возрастания зависимости пропускной способности от параметра а (задержки) следуют протокол МДСЗ с ПРК, синхронный протокол МДСЗ и асинхронный протокол МДСЗ.
В работе развивается математический аппарат для анализа систем массового обслуживания, работа которых регламентируется рассматриваемыми протоколами. Для протоколов МДСЗ строится система, описывающая динамику изменения состояния задолженности. Для протокола резервирования приводится анализ средней задержки требования в системе. Затем с использованием формулы Литтла вычисляются значения среднего числа требований в системе и средней задолженности.
Ключевые слова: протокол управления, множественный доступ, сложный сигнал, кодовое разделение, параллельная обработка, разрешение конфликтов, резервирование, пропускная способность.