Навігація
Головна
 
Головна arrow Інформатика arrow Обчислювальні системи, мережі та телекомунікації. Моделювання мереж
< Попередня   ЗМІСТ   Наступна >

АНАЛІТИЧНЕ МОДЕЛЮВАННЯ НА ОСНОВІ СИСТЕМ МАСОВОГО ОБСЛУГОВУВАННЯ

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

Аналітична модель мережі являє собою сукупність математичних співвідношень, що зв'язують між собою вхідні і вихідні характеристики мережі. При виведенні таких співвідношень доводиться нехтувати якимись малоістотними деталями або обставинами [8].

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

(3.1)

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

де А - процес прибуття; В - процес обслуговування; З - число серверів (вузлів); До - максимальний розмір черги (за замовчуванням - ∞);

in - число клієнтів (за замовчуванням - так); z - схема роботи буфера (за замовчуванням FIFO).

Букви А і В представляють процеси приходу і обслуговування і зазвичай замінюються такими буквами, що характеризують закон, відповідний розподілу подій:

  • D - постійна ймовірність;
  • Μ - Марківське експоненціальне розподіл;
  • G - узагальнений закон розподілу;
  • - розподіл Ерланга порядку k;
  • border="0" src="/imag/inform/zam_vs/image233.jpg"> - гиперекспониціональне розподіл порядку k [4].

Найбільш поширеними схемами роботи буферів є

FIFO (First-In-First-Out), LIFO (Last-In-First-Out) і FIRO (First-In- Random-Out). Наприклад, запис M / M / 2 означає чергу, для якої часи приходу і обслуговування мають експоненційний розподіл, є два сервера, довжина черги і число клієнтів можуть бути як завгодно великими, а буфер працює за схемою FIFO [19].

Середнє значення довжини черги Q при заданої середньої вхідний частоті повідомлень λ і середньому часу очікування W визначається на основі теореми Літла (1961) [18]:

(3.2)

Для варіанту черзі M / G / 1 вхідний процес характеризується розподілом Пуассона зі швидкістю надходження повідомлень λ. Можливість надходження до повідомлень на вхід за час t дорівнює:

(3.3)

Нехай N - число клієнтів в системі, Q - кількість клієнтів в черзі і нехай ймовірність того, що входить клієнт виявить j інших клієнтів, дорівнює:

(3.4)

Тоді середній час очікування:

(3.5)

де σ - середньоквадратичне відхилення для розподілу часу обслуговування.

Для варіанту черзі (Η - функція

розподілу часу обслуговування). Звідки випливає [18].

(3.6)

Для варіанту черзі M / D / 1 час обслуговування постійно, а середній час очікування становить:

(3.7)

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

де

(3.8)

(3.9)

де , а так само ймовірності того, що повідомлення відправника / 'направлено одержувачу . Вимога стабільності вимагає, щоб . Для великих n це призводить до

Робота мережі Ethernet характеризується рядом параметрів, до числа яких відносяться ймовірність захоплення каналу і ефективність [18]. Перший параметр визначається за виразом

(3.10)

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

Ефективність LAN Ethernet визначається наступним чином. Загальний час роботи мережі Ethernet ділиться між інтервалами передачі і інтервалами конкуренції. Для передачі кадру даних потрібно L / C секунд, де L - довжина кадру в бітах, С - швидкість передачі даних в біт / сек. Середній час Τ , необхідне на захоплення каналу, так само:

(З.11)

де W - середнє число тактів, що пройшли в інтервалі конкуренції, поки станція не захопили канал для передачі кадру даних; В - тривалість такту або час до виявлення конфлікту після початку передачі кадру.

Середнє число тактів W розраховується наступним чином:

(3.12)

З урахуванням введених показників ефективність Ε роботи локальної мережі Ethernet визначається наступним чином:

(3.13)

Для моделювання ЛВС найбільш часто використовуються наступні типи СМО:

  • 1. Одноканальні СМО з очікуванням. Являють собою один обслуговуючий прилад з нескінченною чергою. Дана СМО є найбільш поширеною при моделюванні. З тією або іншою часткою наближення з її допомогою можна моделювати практично будь-який вузол ЛВС.
  • 2. Одноканальні СМО з втратами. Являють собою один обслуговуючий прилад з кінцевим числом місць у черзі. Якщо число заявок перевищує число місць в черзі, то зайві заявки втрачаються. Цей тип СМО може бути використаний при моделюванні каналів передачі в ЛВС.
  • 3. Багатоканальні СМО з очікуванням. Являють собою кілька паралельно працюють обслуговуючих приладів із загальною нескінченної чергою. Даний тип СМО часто використовується при моделюванні груп абонентських терміналів ЛВС, що працюють в діалоговому режимі.
  • 4. Багатоканальні СМО з втратами. Являють собою кілька паралельно працюють обслуговуючих приладів із загальною чергою, число місць в якій обмежено. Ці СМО, як і одноканальні з втратами, часто використовуються для моделювання каналів зв'язку в ЛВС.
  • 5. Одноканальні СМО з груповим надходженням заявок. Являють собою один обслуговуючий прилад з нескінченною чергою. Перед обслуговуванням заявки групуються в пакети за певним правилом.
  • 6. Одноканальні СМО з груповим обслуговуванням заявок. Являють собою один обслуговуючий прилад з нескінченною чергою. Заявки обслуговуються пакетами, які складаються за певним правилом. Останні два типи СМО можуть використовуватися для моделювання таких вузлів ЛВС, як центри (вузли) комутації.

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

Відкритої називається тобто масового обслуговування, що складається з Μ вузлів, причому хоча б в один з вузлів мережі надходить ззовні вхідний потік заявок і є стік заявок з мережі. Для відкритих мереж характерно те, що інтенсивність надходження заявок в мережу не залежить від стану мережі, т. Е. Від числа заявок, вже надійшли в мережу. Відкриті мережі використовуються для моделювання ЛВС, що працюють в неоперативне режимі. Кожна заявка надходить на вхід відповідного вузла комутації, де визначається місце її обробки. Потім заявка передається на "свій" сервер або по каналу зв'язку - на "сусідній", де обробляється, після чого повертається до джерела і покидає мережу [18].

Замкнутої називається мережу масового обслуговування з безліччю вузлів Μ без джерела і стоку, в якій циркулює постійне число заявок. Замкнені СМО використовуються для моделювання таких ЛВС, джерелами інформації для яких служать абонентські термінали, що працюють в діалоговому режимі. У цьому випадку кожна група абонентських терміналів представляється у вигляді багатоканальної системи масового обслуговування з очікуванням і включається до складу пристроїв мережі [18].

Розрізняють простий і складний режими роботи діалогових абонентів. У простому режимі абоненти не проводять ніяких дій, крім посилки завдань у ЛВС і обмірковування отриманої відповіді [18].

Абоненти з терміналів посилають запити, які по каналах зв'язку надходять на вузли комутації, а звідти - на обробку на "свій" або "сусідній" сервер. Подальша обробка здійснюється так само, як у відкритій мережі [14].

При складному режимі діалогу робота абонентів представляється у вигляді сукупності операцій деякого процесу, званого технологічним. Кожна операція технологічного процесу моделюється відповідної СМО. Частина операцій передбачає звернення до ЛВС, а частина операцій може такого звернення не передбачати [18]. Алгоритм роботи самої ЛВС такий же, як для замкнутої мережі.

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

Алгоритм роботи мережі для діалогових абонентів аналогічний алгоритму роботи замкнутої мережі, а алгоритм роботи мережі для неоперативних абонентів - алгоритму роботи відкритої мережі.

Розрізняють експоненціальні і неекспоненціальние моделі ЛВС. Експонентні моделі засновані на припущенні про те, що потоки заявок, що надходять в ЛВС, є пуассоновским, а час обслуговування в вузлах ЛВС має експоненційний розподіл.

Для таких мереж отримані точні методи для визначення їх характеристик; трудомісткість отримання рішення залежить в основному від розмірності мережі [18].

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

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

При цьому не потрібно точного знання функцій розподілу випадкових величин, пов'язаних з даною СМО (інтервалів між надходженнями заявок часом обслуговування в приладах), а досить лише знання першого (математичного очікування) і другого (дисперсії або квадрата коефіцієнта варіації - ΚΚΒ) моментів цих величин [ 18].

Застосування дифузійної апроксимації при аналізі ЛВС засноване на наступному:

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

Постановка завдання аналізу ЛВС при цьому прийме наступний вигляд. дано:

  • • число вузлів ЛВС;
  • • тип кожного вузла ЛОМ (тип СМО, що моделює даний вузол);
  • • дисципліна обслуговування в кожному вузлі ЛВС;
  • • загальна кількість типів джерел заявок, що працюють в діалоговому режимі;
  • • загальна кількість типів джерел заявок, що працюють в неоперативне режимі;
  • • для діалогових джерел у випадку складного режиму роботи число технологічних процесів кожного типу, число операцій в кожному технологічному процесі, середнє і ΚΚΒ часу виконання кожної операції, матриця ймовірностей передач між операціями, а також наявність або відсутність на кожній операції звернення до ЛВС;
  • • для діалогових джерел у разі простого режиму роботи число джерел (терміналів) кожного типу, середнє і ΚΚΒ часу реакції абонента на відповідь мережі;
  • • для неоперативних абонентів - середня інтенсивність надходження заявок і ΚΚΒ часу між надходженнями заявок; по кожному типу заявок (діалогового і Неоперативне) середня інтенсивність обслуговування в кожному вузлі ЛВС, ΚΚΒ часу обслуговування в вузлах ЛОМ та матриця ймовірностей передач між вузлами. Потрібно знайти:
  • • середнє значення і дисперсію (або стандартне відхилення) часу затримки заявки кожного типу в ЛОМ в цілому;
  • • середнє значення і дисперсію (або стандартне відхилення) часу затримки в вузлах ЛВС;
  • • завантаження вузлів ЛВС;
  • • ймовірність втрати заявки у вузлі ЛВС (для вузлів, що моделюються СМО з втратами).

Обмеження можуть бути наступними:

  • • завантаження вузлів не повинна перевищувати 1;
  • • ймовірність втрати заявки не повинна перевищувати 1;
  • • всі характеристики повинні бути позитивні.

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

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук