Несиметрична многомаркерная кільцева локальна мережа з буферами кінцевої ємності і ординарної

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

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

Зміст

Введення

1 Математичні моделі функціонування несиметричних, многомаркерних КЛВС з кінцевими буферами різної ємності і ординарної дисципліною обслуговування

    1. Математична модель функціонування многомаркерной, несиметричною КЛВС з N АС, з k маркерами (1 <k <N) і

буферами різної ємності

1.2 Математична модель функціонування многомаркерной, несиметричною КЛВС з буферами , З 3 АС і 2-мя маркерами, з ординарної дисципліною обслуговування

1.3 Математична модель функціонування многомаркерной, несиметричною КЛВС з N АС, з k маркерами (k = N) та буферами

різної ємності

2 Визначення стаціонарних ймовірностей станів

несиметричних, многомаркерних КЛВС

2.1 Визначення стаціонарних ймовірностей станів многомаркерной,

несиметричною КЛВС з буферами різної ємності, з N АС і k

маркерами, з ординарної дисципліною обслуговування

2.2 Визначення стаціонарних ймовірностей станів многомаркерной,

несиметричною КЛВС з буферами , З 3 АС і 2-мя маркерами, з ординарної дисципліною обслуговування

2.3 Визначення стаціонарних ймовірностей станів многомаркерной,

несиметричною КЛВС з буферами різної ємності, з N АС і

k = N маркерами, з ординарної дисципліною обслуговування

3 Характеристики функціонування несиметричних, многомаркерних КЛВС

3.1 Характеристики функціонування многомаркерной, несиметричною КЛВС з буферами різної ємності, з N АС і k маркерами (1 <N <k), з ординарної дисципліною обслуговування

3.2 Характеристики функціонування станів многомаркерной, несиметричною КЛВС з буферами , З 3 АС і 2-мя маркерами, з ординарної дисципліною обслуговування

3.3 Характеристики функціонування станів многомаркерной, несиметричною КЛВС з буферами різної ємності, з N АС і k = N маркерами, з ординарної дисципліною обслуговування

Висновок

C писок використовуваних джерел

Введення

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

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

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

До основних характеристик ЛВС належать такі:

· Територіальна протяжність мережі (довжина загального каналу);

· Максимальна швидкість передачі даних;

· Максимальна кількість вузлів у мережі (воно може бути від декількох десятків до декількох сотень);

· Максимально можливу відстань між вузлами мережі;

· Фізична структура або топологія мережі;

· Фізичне середовище передачі і даних;

· Метод доступу абонентів до мережі;

· Умови надійної роботи мережі та ін

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

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

Деревоподібна структура




Кільцева структура




Зіркоподібна структура



Шинна структура

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

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

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

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

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

У 1980 р. в рамках Інституту інженерів з електротехніки та радіоелектроніки (IEEE) був створений комітет 802 зі стандартизації ЛВС, завданням якого було визначення набору процедур, за допомогою яких різні пристрої можуть взаємодіяти. Для підготовки проектів окремих стандартів були засновані підкомітети. Стандартом маркерного кільця займався підкомітет 802.5. Розробка цього стандарту була завершена в 1984 р., а в 1985 р. Американський національний інститут стандартів (ANSI) затвердив стандарт ANSI / IEEE 802.5 як національний стандарт США. У 1986 р. цей стандарт був затверджений в якості міжнародного. У Європі в 1982 р. Європейська асоціація виробників ЕОМ (ECMA) незалежно від ANSI випустила стандарт маркерного кільця ECMA -89. Стандарт ANSI / IEEE 802.5 сумісний зі стандартом ECMA -89.

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

Переваги КЛВС з маркерним доступом:

· Гарантується доступ кожного абонента в мережу через певні проміжки часу незалежно від навантаження мережі;

· Відсутність проблеми маршрутизації повідомлень, тому що маршрути передачі повідомлень фіксовані;

· Можливість розширення;

· Низька вартість підключення нових вузлів в мережу;

· Невисока вартість мережевих інтерфейсів, що реалізують прямі методи передач і управління доступу в мережу;

Недоліки КЛВС:

· Складне управління;

· При додаванні або заміні вузла необхідні зупинка в роботі мережі і тимчасовий розрив кільця;

· Вихід з ладу вузла мережі перериває роботу всієї мережі.

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

Математичними моделями описаної ЛВС «маркерне кільце» є циклічні СМО. Теорія циклічних СМО отримала розвиток в роботах закордонних вчених, огляд яких налічує понад 200 найменувань.

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

  1. вичерпні або зі спустошенням, коли прилад відключається від черги в момент, коли в ній немає повідомлень;

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

  3. з обмеженням k, коли прилад відключається від черги, обслуживши в ній не більше k повідомлень (якщо в системі не залишилося повідомлень, то прилад відключається, обслуживши менш k повідомлень);

  4. ординарне, коли прилад обслуговує по одному повідомленню в кожній черзі;

  5. Бернуллі, коли прилад обслуговує одне повідомлення в черзі (якщо воно там є), а потім відключається з ймовірністю p, і бере наступне з імовірністю 1-р (якщо повідомлень у системі немає, то прилад відключається з ймовірністю 1);

  6. зі скороченням k, коли прилад відключається від черги, обслуживши r повідомлень, де r = min (x, k), де x - це число повідомлень в черзі в момент підключення до неї приладу.

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

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

1 Математичні моделі функціонування несиметричних, многомаркерних КЛВС з конечнимібуферамі різної ємності і ординарної дисципліною обслуговування

    1. Математична модель функціонування многомаркерной, несиметричною КЛВС з N АС, з k маркерами (1 <k <N) та буферами різної ємності

Розглянемо несиметричну КЛВС з протоколом маркерного доступу, яка складається з N абонентських станцій, на i-ту АС надходить найпростіший потік повідомлень інтенсивності

На кожній АС є буфер з ємністю , Який служить для відправки повідомлень по кільцю, а також є приймальний буфер, який дозволяє приймати будь-яку кількість повідомлень. АС пронумеровані таким чином, що номер АС збільшується в напрямку руху вільних маркерів, причому після проходження N-ої АС вільний маркер надходить на першу АС. Для передачі повідомлень використовуються k маркерів, 1 <k <N.

Буфер на i-тій станції назвемо повністю вільним, якщо на АС немає повідомлень для передачі і повністю зайнятим, якщо на АС є повідомлень, що підлягають передачі.

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

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

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

Час переходу вільного маркера між сусідніми АС будемо вважати однаковим для всіх станцій і одно d. Швидкість руху повідомлення по кільцю така ж, як і швидкість руху вільного маркера. Час, необхідний для передачі і прийому повідомлення в кільці, позначимо через a.

Інтервал часу між послідовними парафіями маркерів на станції дорівнює або D = d + a при наявності хоча б одного повідомлення для передачі на АС кільця, або d, якщо ні на одній АС немає жодного повідомлення для передачі.

Після того, як АС-адресат прийняла повідомлення, квитанція про приймання передається по кільцю на АС-відправник цього повідомлення. При отриманні квитанції про прийом АС-відправник звільняється від переданого повідомлення, відправляє маркер на чергову АС.

    1. Математична модель функціонування многомаркерной, несиметричною КЛВС з буферами , З 3 АС і 2-мя маркерами, з ординарної дисципліною обслуговування

Розглянемо несиметричну КЛВС з протоколом маркерного доступу, яка складається з 3 абонентських станцій, на i-ту АС надходить найпростіший потік повідомлень інтенсивності

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

Буфер на i-тій станції назвемо повністю вільним, якщо на АС немає повідомлень для передачі і повністю зайнятим, якщо на АС є повідомлень, що підлягають передачі.

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

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

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

Час переходу вільного маркера між сусідніми АС будемо вважати однаковим для всіх станцій і одно d. Швидкість руху повідомлення по кільцю така ж, як і швидкість руху вільного маркера. Час, необхідний для передачі і прийому повідомлення в кільці, позначимо через a.

Інтервал часу між послідовними парафіями маркерів на станції дорівнює або D = d + a при наявності хоча б одного повідомлення для передачі на АС кільця, або d, якщо ні на одній АС немає жодного повідомлення для передачі.

Після того, як АС-адресат прийняла повідомлення, квитанція про приймання передається по кільцю на АС-відправник цього повідомлення. При отриманні квитанції про прийом АС-відправник звільняється від переданого повідомлення, відправляє маркер на чергову АС.

    1. Математична модель функціонування многомаркерной, несиметричною КЛВС з N АС, з k маркерами (k = N) та буферами різної ємності

Розглянемо несиметричну КЛВС з протоколом маркерного доступу, яка складається з N абонентських станцій, на i-ту АС надходить найпростіший потік повідомлень інтенсивності

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

Буфер на i-тій станції назвемо повністю вільним, якщо на АС немає повідомлень для передачі і повністю зайнятим, якщо на АС є повідомлень, що підлягають передачі.

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

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

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

Час переходу вільного маркера між сусідніми АС будемо вважати однаковим для всіх станцій і одно d. Швидкість руху повідомлення по кільцю така ж, як і швидкість руху вільного маркера. Час, необхідний для передачі і прийому повідомлення в кільці, позначимо через a.

Інтервал часу між послідовними парафіями маркерів на станції дорівнює або D = d + a при наявності хоча б одного повідомлення для передачі на АС кільця, або d, якщо ні на одній АС немає жодного повідомлення для передачі.

Після того, як АС-адресат прийняла повідомлення, квитанція про приймання передається по кільцю на АС-відправник цього повідомлення. При отриманні квитанції про прийом АС-відправник звільняється від переданого повідомлення, відправляє маркер на чергову АС.

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

2. Визначення стаціонарних ймовірностей станів несиметричних, многомаркерних КЛВС

2.1 Визначення стаціонарних ймовірностей станів многомаркерной, несиметричною КЛВС з буферами різної ємності, з N АС і k маркерами, з ординарної дисципліною обслуговування

Будемо розглядати поведінку КЛВС в моменти надходження маркерів на АС. У цьому випадку зміна станів КЛВС утворюють кінцеву ланцюг Маркова.

Під станом КЛВС будемо розуміти стан всіх АС кільця в момент вступу на них маркерів. Кожна АС може знаходитися завжди в одному з стані.

Усі стану КЛВС діляться на N періодичних класів, кожен з яких містить в розглянутому випадку стан.

Особливості протоколу призводять до того, що зазначена ланцюг Маркова є непріводімий, періодичної з періодом, рівним N.

Деякий j-тий клас (j {1,2, ..., N}) відповідає надходженню деякого фіксованого маркера на j-ту АС. Ймовірності переходів з j-того періодичного класу в (j +1) - ий утворюють ( ) Матрицю.

Закодуємо стану КЛВС парами чисел (i, r), i = ( ), 0 . Тут i визначає клас станів, тобто одно номерами тих станцій, на яких знаходяться маркери, r визначає номер стану.

Введемо позначення M = ( ) - Безліч номерів тих станцій, на яких знаходяться маркера, R = ( ), , L {1, ..., N}, - Позначає кількість повідомлень на l-тій АС. Також позначимо через P ( ) - Вектор-рядок ймовірностей станів КЛВС.

Позначимо через - Імовірність того, що за час на i-ту АС не надійде жодного повідомлення; - Імовірність того, що за час на i-ту АС надійде m повідомлень; - Імовірність того, що за час на i-ту АС надійде m і більше повідомлень.

Так як потік повідомлень пуассоновский, то маємо:

=

=

, I {1,2, ..., N}

Вивчаючи поведінку КЛВС у вкладені Марківські моменти, отримаємо таку процедуру визначення стаціонарних ймовірностей мережі.

Теорема. Стаціонарні ймовірності розглянутої КЛВС обчислюються із співвідношень:

P ( ) = P ( ) A ( ; )

(1)

де А - матриця ймовірностей переходів з i-того періодичного класу в стан (i +1) - го класу, елементи якої обчислюються за формулою:

a ( ) = + + , Часи обчислюються за такими формулами:

а також імовірність переходу дорівнює нулю, якщо:

1) > 0 , Q = {1,2,3, ..., N}

2)

Доказ:

P ( ) - Вектор-рядок ймовірностей станів i-того періодичного класу; матриця А розмірності , Елементами якої є ймовірності переходів з i-того періодичного класу в (i +1) - ий.

Внаслідок періодичності ланцюга Маркова якщо або (i, j) (N, 1). З цих міркувань маємо Р (1) = Р (N)

Р (J) = P (J -1) J {2,3, ..., N}, J визначає періодичний клас.

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

Таким чином, враховуючи умову нормування, маємо процедуру (1) визначення векторів стаціонарних ймовірностей КЛВС.

Доведено.

Для обгрунтування правильності формул часу необхідно враховувати наступні положення:

  1. якщо надходить повідомлення, а відповідний буфер зайнятий повністю, то повідомлення втрачається, і при підрахунку повідомлень, що надійшли воно не враховується;

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

  3. при передачі повідомлення з АС, на якій є маркер, буфер даної станції блокується;

  4. зі станції з маркером може передаватися не більше одного повідомлення.

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

2.2 Визначення стаціонарних ймовірностей станів многомаркерной, несиметричною КЛВС з буферами , З 3 АС і 2-мя маркерами, з ординарної дисципліною обслуговування

Будемо розглядати поведінку КЛВС в моменти надходження маркерів на АС. У цьому випадку зміна станів КЛВС утворюють кінцеву ланцюг Маркова.

Під станом КЛВС будемо розуміти стан всіх АС кільця в момент вступу на них маркерів. Кожна АС може знаходитися завжди в одному з стані.

Усі стану КЛВС діляться на 3 періодичних класів, кожен з яких містить в розглянутому випадку 12 станів.

Особливості протоколу призводять до того, що зазначена ланцюг Маркова є непріводімий, періодичної з періодом, рівним 3.

Деякий j-тий клас (j {1,2,3}) відповідає надходженню деякого фіксованого маркера на j-ту АС. Ймовірності переходів з j-того періодичного класу в (j +1) - ий утворюють матрицю.

Закодуємо стану КЛВС парами чисел (i, r), i = ( ), 0 11. Тут i визначає клас станів, тобто одно номерами тих станцій, на яких знаходяться маркера, r визначає номер стану.

Введемо позначення M = ( ) - Безліч номерів тих станцій, на яких знаходяться маркера, R = ( ), , L {1,2,3}, - Позначає кількість повідомлень на l-тій АС. Також позначимо через P ( ) - Вектор-рядок ймовірностей станів КЛВС.

Позначимо через - Імовірність того, що за час на i-ту АС не надійде жодного повідомлення; - Імовірність того, що за час на i-ту АС надійде m повідомлень; - Імовірність того, що за час на i-ту АС надійде m і більше повідомлень.

Так як потік повідомлень пуассоновский, то маємо:

=

=

, I {1,2,3}

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

P (2,3) = P (1,2) A (1,2);

P (3,1) = P (2,3) A (2,3);

P (1,2) = P (3,1) A (3,1);

А - матриця ймовірностей переходів з i-того періодичного класу в стан (i +1) - го класу, елементи якої обчислюються за формулою:

a ( ) =

часи обчислюються за такими формулами:

а також імовірність переходу дорівнює нулю, якщо:

1) > 0 , Q = {1,2,3}

2)

Для обгрунтування правильності формул часу необхідно враховувати наступні положення:

  1. якщо надходить повідомлення, а відповідний буфер зайнятий повністю, то повідомлення втрачається, і при підрахунку повідомлень, що надійшли воно не враховується;

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

  3. при передачі повідомлення з АС, на якій є маркер, буфер даної станції блокується;

  4. зі станції з маркером може передаватися не більше одного повідомлення;

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

У додатку буде надано матриці переходів для розглянутої КЛВС. Позначення означає, що маркери перебували на першій і другій станціях.

2.3 Визначення стаціонарних ймовірностей станів многомаркерной, несиметричною КЛВС з буферами різної ємності, з N АС і k = N маркерами, з ординарної дисципліною обслуговування

Будемо розглядати поведінку КЛВС в моменти надходження маркерів на АС. У цьому випадку зміна станів КЛВС утворюють кінцеву ланцюг Маркова.

Під станом КЛВС будемо розуміти стан всіх АС кільця в момент вступу на них маркерів. Кожна АС може знаходитися завжди в одному з стані.

Усі стану КЛВС діляться на N періодичних класів, кожен з яких містить в розглянутому випадку стан.

Особливості протоколу призводять до того, що зазначена ланцюг Маркова є непріводімий, періодичної з періодом, рівним N.

Деякий j-тий клас (j {1,2, ..., N}) відповідає надходженню деякого фіксованого маркера на j-ту АС. Ймовірності переходів з j-того періодичного класу в (j +1) - ий утворюють ( ) Матрицю. Зафіксуємо деякий маркер і будемо розглядати поведінку мережі в моменти надходження цього маркера АС.

Закодуємо стану КЛВС парами чисел (i, r), i = ( ), 0 . Тут i визначає клас станів, тобто одно номера станції, на якій знаходяться маркери, r визначає номер стану.

Введемо позначення M = ( ) - Безліч номерів тих станцій, на яких знаходяться маркера, R = ( ), , L {1, ..., N}, - Позначає кількість повідомлень на l-тій АС. Також позначимо через P ( ) - Вектор-рядок ймовірностей станів КЛВС.

Позначимо через - Імовірність того, що за час на i-ту АС не надійде жодного повідомлення; - Імовірність того, що за час на i-ту АС надійде m повідомлень; - Імовірність того, що за час на i-ту АС надійде m і більше повідомлень.

Так як потік повідомлень пуассоновский, то маємо:

=

=

, I {1,2, ..., N}

Вивчаючи поведінку КЛВС у вкладені Марківські моменти, отримаємо таку процедуру визначення стаціонарних ймовірностей мережі, яку можна записати у вигляді:

P ( ) = P ( ) A

де А - матриця ймовірностей переходів з i-того періодичного класу в стан (i +1) - го класу, елементи якої обчислюються за формулою:

a ( ) = + + ,

часи обчислюються за такими формулами:

а також імовірність переходу дорівнює нулю, якщо:

1) > 0 , Q = {1,2,3, ..., N}

2)

Для обгрунтування правильності формул часу необхідно враховувати наступні положення:

  1. якщо надходить повідомлення, а відповідний буфер зайнятий повністю, то повідомлення втрачається, і при підрахунку повідомлень, що надійшли воно не враховується;

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

  3. при передачі повідомлення з АС, на якій є маркер, буфер даної станції блокується;

  4. зі станції з маркером може передаватися не більше одного повідомлення.

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

3 Характеристики функціонування несиметричних, многомаркерних КЛВС

3.1 Характеристики функціонування многомаркерной, несиметричною КЛВС з буферами різної ємності, з N АС і k маркерами (1 <N <k), з ординарної дисципліною обслуговування

Наступні характеристики визначають ефективність функціонування аналізованої КЛВС:

  1. ймовірність того, що в мережі немає повідомлень (всі АС вільні) :

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

  1. ймовірність того, що всі АС зайняті (тобто на кожній станції є хоча б одне повідомлення) :

Справедливість цієї формули випливає з того, що АС зайнята, коли на ній є хоча б одне повідомлення, тобто . Сума за i від 0 до N -1 означає, що ми будь-яким фіксованим маркером пройшли всі кільце і повернулися в початковий стан.

  1. ймовірність того, що всі АС повністю зайняті (тобто на кожній АС всі буфери повністю зайняті) :

Справедливість цієї формули випливає з того, що АС повністю зайнята, коли на ній є рівно повідомлень. Сума за i від 0 до N -1 означає, що ми будь-яким фіксованим маркером пройшли всі кільце і повернулися в початковий стан.

  1. середнє число зайнятих станцій :

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

  1. ймовірність того, що l-та АС зайнята :

Ця формула справедлива для будь-якої фіксованої АС.

  1. коефіцієнт завантаження l-тій АС :

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

  1. середній час обслуговування повідомлень на l-тій АС :

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

  1. середній час обслуговування в мережі .

Вірність випливає з формули (7).

3.2 Характеристики функціонування станів многомаркерной, несиметричною КЛВС з буферами , З 3 АС і 2-мя маркерами, з ординарної дисципліною обслуговування

Наступні характеристики визначають ефективність функціонування аналізованої КЛВС:

  1. ймовірність того, що в мережі немає повідомлень (всі АС вільні) :

  1. ймовірність того, що всі АС зайняті (тобто на кожній станції є хоча б одне повідомлення) :

  1. ймовірність того, що всі АС повністю зайняті (тобто на кожній АС всі буфери повністю зайняті) :

  1. середнє число зайнятих станцій :

  1. ймовірність того, що l-та АС зайнята :

  1. коефіцієнт завантаження l-тій АС :

  1. середній час обслуговування повідомлень на l-тій АС :

8) середній час обслуговування в мережі :

Вірність даних формул була показана в пункті 3.1.

3.3 Характеристики функціонування станів многомаркерной, несиметричною КЛВС з буферами різної ємності, з N АС і k = N маркерами, з ординарної дисципліною обслуговування

Наступні характеристики визначають ефективність функціонування аналізованої КЛВС:

1) ймовірність того, що в мережі немає повідомлень (всі АС вільні) :

  1. ймовірність того, що всі АС зайняті (тобто на кожній станції є хоча б одне повідомлення) :

  1. ймовірність того, що всі АС повністю зайняті (тобто на кожній АС всі буфери повністю зайняті) :

5) середнє число зайнятих станцій :

6) імовірність того, що l-та АС зайнята :

7) коефіцієнт завантаження l-тій АС :

Висновок

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

Многомаркерние КЛВС з однією лінією зв'язку, ординарної дисципліною обслуговування і кінцевими буферами у постановці, наведеної в дипломній роботі, у відомій літературі не зустрічалися.

У дипломній роботі розроблено математичні моделі, що описують функціонування несиметричних КЛВС з кількома маркерами, кінцевими буферами і ординарним обслуговуванням повідомлень на АС; запропоновано аналітичний апарат, що дозволяє визначити ймовірності станів КЛВС з векторно-матричних систем рівнянь, виведено формули для характеристик, що описують особливості функціонування мереж.

Список використаних джерел

  1. Бакс В. Кільцеві локальні мережі з маркерним доступом та їх продуктивність / / ТІІЕР. - Т. 77, № 2. - С. 121-142.

  2. Бураковський В.В., Медведєв Г.А. Кільцева локальна мережа з протоколом маркерного доступу / / Техніка засобів зв'язку. Сер. Системи зв'язку. - 1990. - Вип. 7. - С. 9-16.

  3. Бураковський В.В., Медведєв Г.А. Характеристики локальних обчислювальних мереж з протоколами маркерного доступу / / Матеріали всесоюзної науково-технічної конференції Мікросистема-92: Тез. доповідей. - Томськ, 1992. - С. 44-46.

  4. Гнеденко Б.В., Коваленко І.М. Введення в теорію масового обслуговування. - М.: Наука, 1987. - 336 с.

  5. Протоколи інформаційно-обчислювальних мереж: Довідник / За ред. Мізіна І.А., Кулешова А.П. - М.: Радіо і зв'язок, 1990. - 504 с.

  6. Пятібратов А.П., Бєляєв С.М., Козирєва Г.М. та ін Обчислювальні машини, системи та мережі: Підручник / За ред. проф. А.П. Пятібратова. - М.: Фінанси і статистика, 1991. - 400 с.

  7. Феллер В. Введення в теорію ймовірностей і її застосування. - М.: Світ, 1984. - Т. 1. - 527 с.

Додати в блог або на сайт

Цей текст може містити помилки.

Комунікації, зв'язок, цифрові прилади і радіоелектроніка | Курсова
159.1кб. | скачати


Схожі роботи:
Несиметрична многомаркерная кільцева локальна мережа з буферами 2
Несиметрична многомаркерная кільцева локальна мережа з буферами
Однорангова локальна мережа і мережа з виділеним сервером Експертна система
Локальна мережа
Локальна мережа від і до
Локальна обчислювальна мережа містечка
Найпростіша локальна мережа з 2 комп`ютерів
Локальна обчислювальна мережа бухгалтерського відділу
Локальна обчислювальна мережа інформаційних класів університету
© Усі права захищені
написати до нас