Методи дослідження мереж масового обслуговування

Дипломна робота

Методи дослідження мереж масового обслуговування

РЕФЕРАТ

Дипломна бакалаврська робота: 73 сторінки, 7 джерел, 7 таблиць, 5 рисунків.

Перелік ключових слів: мережа масового обслуговування, рівняння балансу, теорема ВСМР, теорема Нортона, декомпозиція мережі.

Об'єкт дослідження: мережі масового обслуговування.

Мета роботи: огляд методів розрахунку та дослідження мереж МО.

ЗМІСТ

ВСТУП

РОЗДІЛ 1. ОСНОВНІ ПОНЯТТЯ І ОЗНАЧЕННЯ

1.1 Механізм обслуговування

1.2 Дисципліна обслуговування

1.3 Маршрутна матриця і потоки в мережах

1.4 Інші означення

РОЗДІЛ 2. СКЛАДАННЯ РІВНЯННЬ ЛОКАЛЬНОГО БАЛАНСУ ДЛЯ МЕРЕЖМАСОВОГО ОБСЛУГОВУВАННЯ

2.1 Однорідні експоненціальні мережі масового обслуговування

2.1.1 Рівняння глобального балансу для замкнених мереж

2.1.2 Вигляд розв'язку в мультиплікативній формі

2.1.3 Мережі, що залежать від навантаження

2.1.4 Показники якості функціонування однорідних мереж

2.2 Мережі МО з кількома класами повідомлень

2.2.1 Опис змішаної мережі

2.2.2 Теорема ВСМР

2.2.3 Відкриті мережі масового обслуговування з кількома класами повідомлень

2.2.4 Розширення теореми ВСМР

РОЗДІЛ 3. МЕТОД АНАЛІЗУ СЕРЕДНІХ ЗНАЧЕНЬ

3.1 Загальне описання методу

3.2 Однорідна замкнена мережа масового обслуговування, що залежить від навантаження

3.3 Обчислення основних співвідношень

РОЗДІЛ 4. ОБЧИСЛЕННЯ ХАРАКТЕРИСТИК МЕРЕЖ МО

4.1 Метод Бузена

4.2 Обчислення характеристик мережі масового обслуговування

РОЗДІЛ 5. МЕТОД ДЕКОМПОЗИЦІЙНОЇ АПРОКСИМАЦІЇ

5.1 Апроксимація функцій розподілу475.2 Теорема Нортона для аналізу замкнених і розімкнених локально-збалансованих мереж масового обслуговування

5.3 Наближений декомпозиційний алгоритм

5.4 Декомпозиція розімкнених мереж масового обслуговування на рівні перших моментів

РОЗДІЛ 6. МЕТОД ПОЛІНОМІАЛЬНОЇ АПРОКСИМАЦІЇ

6.1 Опис методу

6.2 Оцінка обчислювальної складності

РОЗДІЛ 7. ПРИКЛАД РОЗРАХУНКУ МЕРЕЖІ МАСОВОГО ОБСЛУГОВУВАННЯ

ВИСНОВКИ

ПЕРЕЛІК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

ДОДАТОК

ВСТУП

Одним з розділів теорії масового обслуговування є мережі масового обслуговування. Поява цього розділу пов'язана з вирішенням практичних задач проектування обчислювальних систем та мереж. Перші підходи до аналізу мереж масового обслуговування (МО) були розроблені у 1960-70 pp. математиками Й.Джексоном, В.Гордоном та Ж.Ньюелом. Однак ці роботи не знайшли широкого практичного застосування до появи в 1971 р. роботи Ф.Мура, у якій було показано, що мережі МО є адекватними моделями функціонування обчислювальних систем. Подальший розвиток області застосування теорії мереж МО пов'язаний з удосконалюванням апаратного та програмного забезпечення обчислювальних систем.

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

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

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

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

РОЗДІЛ Й. ОСНОВНІ ПОНЯТТЯ ТА ОЗНАЧЕННЯ

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

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

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

1.1 МЕХАНІЗМ ОБСЛУГОВУВАННЯ

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

де - кількість однакових обслуговуючих приладів у і-му центрі.

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

є раціональною функцією вигляду

де -- відповідно поліноми степеня d і d₁

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

Таблиця 1.1 Характеристики деяких розподілів

Тип розподілу	Функція розподілу	Математичне сподівання	Дисперсія	Перетворення Лапласа
Експоненціальний
Ерланга k- го порядку
Гіперекспоненціальний k- го порядку

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

1.2 ДИСЦИПЛІНА ОБСЛУГОВУВАННЯ

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

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

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

1.3 МАРШРУТНА МАТРИЦЯ І ПОТОКИ В МЕРЕЖАХ

Перехід повідомлення з одного центру після закінчення обслуговування в ньому в іншій здійснюється відповідно до заданого маршруту, під яким розуміється послідовність відвідуваних повідомленням центрів мережі. Маршрут повідомлення по мережі МО задається матрицею маршрутів P, вид якої залежить від того, чи є мережа МО відкритою або замкненою. У відкриту мережу МО повідомлення надходять із зовнішнього джерела і можуть покидати мережу після завершення обслуговування. Якщо прийняти зовнішнє джерело за новий центр мережі і позначити індексом 0, то маршрут у відкритій мережі задається стохастичною матрицею , де і -- відповідно імовірність надходження в j-й центр повідомлення з джерела і імовірність покидання повідомленням мережі після закінчення обслуговування в і-му центрі; -- імовірність того, що повідомлення, що йде з i-го центру, перейде в j-й центр

Очевидно, що виконується рівність

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

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



розв'язок якої через припущення про те, що стохастична матриця маршрутів Р є невиродженою, існує і єдиний.

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

Число незалежних рівнянь в системі (1.3.3) на одиницю менше кількості змінних, так що її рішення єдине з точністю до мультиплікативної константи. Іншими словами, якщо -- розв'язок системи рівнянь (1.3.3), то при розв'язком є і . Для відшукання однозначного розв'язку системи рівнянь (1.3.3) достатньо довільно задати значення e_i ,наприклад покласти e_i=1. У цьому випадку величину e_i можна інтерпретувати як середнє число відвідувань повідомленням центру між двома послідовними відвідуваннями ним першого центру.

Нехай -- потік, що проходить через -й центр в стаціонарному режимі. Тоді вираз зв'язує потоки, що проходять через i-й і перший центри мережі.

1.4 ІНШІ ВИЗНАЧЕННЯ

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

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

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

РОЗДІЛ 2. СКЛАДАННЯ РІВНЯНЬ ЛОКАЛЬНОГО БАЛАНСУ ДЛЯ МЕРЕЖ МО

2.1 ОДНОРІДНІ ЕКСПОНЕНЦІАЛЬНІ МЕРЕЖІ

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

2.1.1 РІВНЯННЯ ГЛОБАЛЬНОГО БАЛАНСУ ДЛЯ ЗАМКНЕНИХ МЕРЕЖ

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

де -- число повідомлень, що знаходяться в k-му центрі (у черзі і на обслуговуванні) у момент t (), і позначимо через



імовірність того, що у момент t мережа знаходиться в стані

Позначимо через S(N,M) множину М-вимірних векторів з невід'ємними цілочисельними координатами

потужність якої (кількість станів) дорівнює

Випадковий процес N(t), який визначений на просторі станів S(N,M), є марківським, оскільки тривалості обслуговування в центрах мережі розподілені за експоненціальним законом. Аналізуючи можливі переходи цього процесу за проміжок часу і переходячи до границі при , одержуємо наступну систему прямих диференціальних рівнянь Колмогорова:

де - -- вектор, i-я координата якого дорівнює 1, а інші дорівнюють нулю; функція визначає число повідомлень, що знаходяться на обслуговуванні в k-му центрі (), коли загальне число повідомлень в ньому дорівнює при n_i=0 і при .

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

з урахуванням тотожності одержуємо наступну систему лінійних різницевих рівнянь:

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

2.1.2 ВИГЛЯД РОЗВ'ЯЗКУ В МУЛЬТИПЛІКАТИВНІЙ ФОРМІ

Переходячи до розв'язання системи рівнянь (2.1.2), введемо функцію

яка може бути представлена також рекурсивно:

введемо заміну змінних в (2.1.2):



Після підстановки (2.1.4) в (2.1.2) одержимо нову систему рівнянь відносно Q(n):

Якщо представити Q(n) у вигляді функції М невідомих параметрів x_i:

і підставити у вираз (2.1.5), то (2.1.5) набуває наступного простого вигляду:

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

або, ввівши позначення

Отже, невідомі параметри x_k визначаються з системи лінійних рівнянь (2.1.9), рішення якої в силу припущення про вид маршрутної матриці Р єдине з точністю до мультиплікативної константи е.

Таким чином, стаціонарний розподіл ймовірності станів даної замкненої однорідної експоненціальної мережі МО має вигляд

Нормалізуюча константа визначається з умови нормування

Тут підсумовування ведеться по всіх можливих станах вектора

.

З (2.1.11) витікає, що

Підставляючи (2.1.12) в (2.1.10) і враховуючи, що , одержуємо остаточно



З останнього виразу видно, що стаціонарні імовірності Р(n) не залежать від константи е з точністю, до якої визначаються значення вектора е, і мають вид добутку, співмножники якого є стаціонарні імовірності станів i-го центру, що розглядається окремо від мережі.

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

З останнього виразу, з урахуванням того, що

, визначається граничний розподіл числа повідомлень, що знаходяться в i-му вузлі :

Вирази (2.1.10), (2.1.15) і (2.1.13) справедливі відповідно для мереж,що не залежать від навантаження, і мереж, в яких залежність інтенсивності обслуговування центру від числа повідомлень у ньому визначається функцією (1.1.1).

2.1.3 МЕРЕЖІ, ЩО ЗАЛЕЖАТЬ ВІД НАВАНТАЖЕННЯ

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

Стаціонарні імовірності станів замкненої однорідної експоненціальної мережі, що залежить від навантаження, задовольняють наступній системі лінійних рівнянь:

яка виводиться так само, як система рівнянь (2.1.2). Тут -- символ Кронекера.

Підставляючи в (2.1.16) рівняння (2.1.9), яке записане у вигляді

Очевидно, що рівняння глобального балансу (2.1.17) виконується, якщо вираз, що стоїть у фігурних дужках, рівний нулю:

Таким чином, рівняння (2.1.18), яке називають рівнянням локального балансу, є достатньою (але не необхідною) умовою глобального балансу (2.1.19). З рекуррентного рівняння (2.1.18) безпосередньо випливає, що стаціонарна імовірність Р(n) має наступний вигляд:

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

Таким чином, ми знову одержали розв'язок, що має мультиплікативну форму.

Для відкритої мережі МО з інтенсивністю вхідного потоку стаціонарні імовірності Р(n), що визначаються за допомогою міркувань, аналогічних виводу формул (2.1.2), (2.1.16), мають вигляд

де позначено

Стаціонарний розподіл Р(n) існує і єдиний, якщо збігається ряд



У частковому випадку, коли інтенсивність вхідного потоку не залежить від числа повідомлень в мережі і дорівнює Л, маємо

В цьому випадку (2.1.21) набуде вигляду

Тут P_i(n_i) -- стаціонарна імовірність того, що в і-му центрі, що розглядається ізольовано, знаходиться n_i, повідомлень:

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

, залежить від довжини черги.

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

2.1.4 ПОКАЗНИКИ ЯКОСТІ ФУНКЦІОНУВАННЯ ОДНОРІДНИХ МЕРЕЖ

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

По аналогії з формулою (2.1.15) граничний розподіл числа повідомлень в М-му (граничному) центрі визначається у вигляді

З урахуванням виразу (2.1.20) для нормалізуючої константи маємо

Граничний розподіл в будь-якому центрі може бути одержаний шляхом перенумерації центрів так, щоб даний центр став граничним. Для одержаної таким чином мережі застосовується вираз (2.1.23). Легко бачити, що для центру М, який не залежить від навантаження , вираз (2.1.23) перетвориться до вигляду (2.1.15). В цьому випадку при визначенні характеристик вузлів з номерами i=1,2,…,M-1 додаткова перенумерація не потрібна.

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



З визначення слідує, що

Підставляючи (2.1.25) і (2.1.23) в (2.1.24), одержуємо для

Для випадку, коли інтенсивність обслуговування в i-му центрі описується виразом (1.1.1), продуктивність л_i(N) може бути визначена через середню кількість зайнятих приладів в і-му центрі u_i(n):

де u_i(n) задовольняє наступному співвідношенню:

.

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

З (2.1.27) і (2.1.28) встановлюється рівність нормованих пропускних спроможностей для кожного центру



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

Математичне сподівання числа повідомлень в М-му центрі з урахуванням виразу (2.1.23) має вигляд

Для вузла, що не залежить від навантаження, вираз, що описує середню довжину черги в центрі, спрощується:

Відповідно до формули Літтла середній час перебування повідомлень в i-му центрі обслуговування T_i(N) дорівнює відношенню середньої довжини черги до середньої інтенсивності вхідного потоку. У стаціонарному режимі інтенсивність вихідного потоку дорівнює інтенсивності вхідного потоку, тому



Особливий інтерес представляє час циклу V_i(N) -- середнє значення інтервалу часу між моментом виходу з i-го центру до моменту першого надходження вказаного повідомлення в цей центр. Якщо e_i=1, то величину e_j можна інтерпретувати як середнє число відвідувань повідомленням j-го центру між двома послідовними відвідуваннями i-го центру. Отже, сумарний середній час, проведений повідомленням за час циклу в j-му центрі, складає . Звідси

Підставляючи в (2.1.33) вираз (2.1.32) і враховуючи співвідношення (2.1.29), яке в даному випадку має вигляд , маємо:

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

2.2 МЕРЕЖІ МАСОВОГО ОБСЛУГОВУВАННЯ З КІЛЬКОМА КЛАСАМИ ПОВІДОМЛЕНЬ

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

2.2.1 ОПИС ЗМІШАНОЇ МЕРЕЖІ

Змішана мережа МО складається з кінцевого числа М центрів обслуговування, між якими відповідно до маршрутної матриці Р циркулює R різних класів повідомлень. Під час переходу з одного центру в іншій повідомлення можуть змінювати клас так, що повідомлення r-того класу може стати повідомленням s-го класу .

Маршрут в змішаній мережі з кількома класами задається матрицею , де -- імовірність того, що повідомлення r-то класу, що закінчило обслуговування в i-му центрі, перейде в k-й центр і стане повідомленням s-го класу.

На парах (ir) визначається марківський ланцюг з матрицею переходів Р, який можна розкласти на L ергодичних неперетинних підланцюгів, множина станів кожного з яких E₁, E₂, …, E_L.

Нехай n_ir -- число повідомлень класу r в i-му центрі в стані мережі n; N_j=M(n, E_j) і N=M(n) -- відповідно число повідомлень в підланцюзі E_j і в мережі МО в стані n. Тоді виконуються співвідношення

причому, якщо N_j = M(n, E_j) = const при , дана мережа є замкненою.

Вхідний потік, який надходить в розімкнену мережу із зовнішнього джерела, може бути заданий різними способами. У першому випадку з джерела надходить один пуассонівський потік, інтенсивність якого Л(M(n)) є функцією загального числа повідомлень в мережі при її стані n. Вхідне повідомлення надходить в i-й центр і стає повідомленням класу r з імовірністю P_{0, ir}, яка не залежить від стану мережі. У другому випадку є L пуассонівських вхідних потоків повідомлень, які надходять у відповідні підланцюги. Інтенсивність j-го потоку є функцією числа повідомлень в j-му підланцюзі . Повідомлення j-го потоку, що виходить з джерела, з імовірністю P_{j, ir} надходить в i-й центр і стає повідомленням r-того класу, якщо , та

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

Для довільного підланцюга справедлива наступна система рівнянь згідно (1.3.2):

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

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

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

Центр типу 2. Обслуговування повідомлень в однолінійному центрі здійснюється відповідно до дисципліни РП. Тривалість обслуговування повідомлення r-го класу, r=1, 2, ..., R, розподілена за законом Коксу з параметрами

і середнім

де --імовірність того, що повідомлення класу r досягає l-ї стадії обслуговування в і-му вузлі. Стан центру визначається вектором , де - вектор , l-та координата якого означає число повідомлень r-го класу в і-му центрі, які знаходяться на l-му етапі обслуговування. Число повідомлень r-го класу в i-му центрі складає , а загальне число повідомлень в центрі . Таким чином, швидкість завершення обслуговування повідомлення r-го класу, що знаходиться на l-му етапі у стані n_i центру, дорівнює . Після завершення обслуговування повідомлення покидає центр з імовірністю b_irl и переходить до наступної стадії з імовірністю a_irl.

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

Центр типу 4. Однолінійний центр з дисципліною обслуговування ОППО («останнім прийшов -- першим обслужений»). Так само, як для вузлів другого і третього типів, розподіл тривалості обслуговування має раціональне перетворення Лапласа і може відрізнятися для повідомлень різних класів. Стан центру визначається вектором . де -- пара, що характеризує повідомлення, що стоїть j-м в черзі, при дисципліні обслуговування ОППО, r_j -- номер класу повідомлення і l_j -- номер перерваного етапу обслуговування. Обслуговування перерваного повідомлення починається з того етапу, на якому воно було перерване.

2.2.2 ТЕОРЕМА ВСМР

Назва теореми - складено з перших літер прізвищ авторів: Baskett F., Chandy K., Muntz R., Palacios F.) Через зроблені припущення і означення процес, що описує функціонування змішаної мережі МО, є марківським. Стан мережі є вектором , де характеризує стан i-го центру і має структуру, що залежить від типів центрів мережі, описаних вище.

Рівняння глобального балансу для знаходження стаціонарного розподілу P(n) ймовірностей станів мережі записуються по аналогії з (2.1.16) в загальному вигляді таким чином:

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

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

Стаціонарний розподіл існує, якщо збігається ряд

де G -- нормалізуюча константа.

У практичних додатках докладний опис станів вузлів, що включає, наприклад, етап обслуговування і порядок розташування повідомлень у вузлі, не є істотним. Основний інтерес представляють агреговані стани вузлів і відповідні стани мережі . Ймовірності стаціонарного агрегованого стану мережі P(n) можна одержати підсумовуванням P(n') по всіх станах n'. В силу мультиплікативності P(n') це еквівалентно підсумовуванню множників по всіх станах вузлів при фіксованих . Якщо позначити одержані множники через Z_i(n_i), то вираз для P(n) набуде вигляду

де нормалізуюча константа G і функція визначаються так само, як і в (2.2.35), а Z_i(n_i) залежить від типу i-го вузла і має наступний вигляд:

якщо і-й вузол першого типу,

якщо і-й вузол другого або четвертого типу,



якщо i-й вузол третього типу,

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

2.2.3 ВІДКРИТІ МЕРЕЖІ МО З КІЛЬКОМА КЛАСАМИ ПОВІДОМЛЕНЬ

Для відкритих мереж, коли інтенсивність вхідного потоку повідомлень з джерела не залежить від стану мережі, можливі подальші спрощення. Розглянемо спочатку закон розподілу числа повідомлень в мережі без розділення повідомлень на різні класи. В цьому випадку стан і -го центру характеризується числом повідомлень в ньому n_i, а стан мережі --вектором і вираз для P(n) набуде наступного простого вигляду:

Де



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

вираз для стаціонарного розподілу станів мережі набуває наступного вигляду:

Де

2.2.4 РОЗШИРЕННЯ ТЕОРЕМИ ВСМР

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

У ряді інших робіт одержана значна кількість теоретичних результатів, які розширюють теорему ВСМР. Зокрема, в роботі Ноетзела введена узагальнена дисципліна обслуговування LBPS (Last Batch Processor Sharing), яка визначає великий клас дисциплін обслуговування, при яких стаціонарні ймовірності станів мережі МО мають мультиплікативну форму для довільного розподілу тривалості обслуговування в центрах мережі.

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

Розглянемо відкриту ВСМР- мережу, в яку надходить L пуассонівських потоків повідомлень. Додатково до позначень п.2.2.2 введемо вектор агрегованого стану мережі

На множині L - вимірних, цілочисельних, невід'ємних векторів задані два набори функцій: які можуть приймати значення на множині {0, 1}. Повідомлення l-го підланцюга, що надходить у мережу, приймається на обслуговування, якщо функція втрат , і втрачається, якщо . Функція , якщо у момент відходу з мережі повідомлення l- го підланцюга нове повідомлення вказаного під ланцюга миттєво вводиться в мережу, і в іншому випадку.

Введемо наступні позначення:

де D і V -- відповідно допустимі множини векторів n та U(N) . Тоді справедлива наступна теорема.

Теорема. Нехай функція втрат і функції задовольняють умові

для всіх пар y і у--1_l з V. Тоді стаціонарний розподіл ймовірностей станів мережі МО має мультиплікативну форму:

нормалізуюча константа.

РОЗДІЛ 3. МЕТОД АНАЛІЗУ СЕРЕДНІХ ЗНАЧЕНЬ

3.1 ЗАГАЛЬНЕ ОПИСАННЯ МЕТОДУ

Розглянемо спочатку застосування методу аналізу середніх значень для розрахунку замкненої однорідної експоненціальної мережі МО, що не залежить від навантаження, яку позначимо через D(N). Якщо обслуговування у вузлах мережі D(N) здійснюється відповідно до дисципліни ПППО, то середній час очікування T_i(N) в i-му центрі складається з середньої тривалості обслуговування повідомлення ф_i, яке щойно надійшло, і середньої тривалості обслуговування всіх повідомлень, що знаходилися в i-му центрі ф_iн_i(N), де н_i(N) -- середня кількість повідомлень в i-му центрі у момент надходження нового повідомлення. Таким чином,

і для визначення н_i(N) необхідно досліджувати стаціонарний режим марківського ланцюга, що описує функціонування мережі в моменти надходження повідомлень в i-й центр. Стаціонарні імовірності станів мережі D(N) у момент надходження повідомлень в i-й центр співпадають із стаціонарними імовірностями станів мережі D(N-1) для довільного моменту часу. Звідси безпосередньо витікає, що , де -- середня кількість повідомлень в i-му центрі мережі D(N-1), та (3.1.1) набуває вигляду:

Щоб одержати рекурентний алгоритм для розрахунку середніх характеристик мережі, необхідно знайти співвідношення, яке зв'язує величини L_i(N) и T_i(N). Таке співвідношення витікає з формули Літтла, застосованої до i-го центру:

де л_i(N)- інтенсивність потоку повідомлень, що надходять в i-й центр.

Якщо позначити через i^* номер довільного виділеного центру мережі, то:

де- e_j однозначно визначається рівняннями

а продуктивність виділеного центру з урахуванням формули Літтла має вигляд:

Враховуючи початкові умови , за допомогою системи рівнянь

можна рекуррентно по N розраховувати середні характеристики однорідної мережі МО, інтенсивності обслуговування центрів якої не залежать від навантаження

3.2 ОДНОРІДНА ЗАМКНЕНА МЕРЕЖА МО, ЩО ЗАЛЕЖИТЬ ВІД НАВАНТАЖЕННЯ

Перш ніж переходити до виводу рекурсивних співвідношень для середніх характеристик мережі МО, вузли якої залежать від навантаження, визначимо співвідношення для граничних розподілів . Вираз для граничного розподілу довжини черги в i-му центрі (i=1,2,…,M) може бути представлено у вигляді:

де g_i (n,M)- нормалізуюча константа мережі, в якій відсутній і-й центр і циркулює n повідомлень.

Підставляючи в останній вираз і враховуючи що

одержимо:

Звідси витікає

Якщо i-й центр включає однотипних обслуговуючих приладів,

то , і вираз (3.2.6) набуде вигляду:

Але перша сума в останньому виразі означає середнє число повідомлень в черзі i-го центру для мережі D(N-1) (виключаючи повідомлення, що знаходяться на обслуговуванні):

а друга -- імовірність того, що всі обслуговуючі прилади зайняті:

Таким чином, в даному випадку



Співвідношення (3.2.5), (3.2.6)разом з виразами (3.2.3), (3.2.4) та початковими умовами дозволяють рекурентно по n_i визначати основні характеристики мережі МО, яка залежить від навантаження.

3.3 ОБЧИСЛЕННЯ ОСНОВНИХ СПІВВІДНОШЕНЬ

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

Позначимо через імовірність того, що повідомлення класу після закінчення обслуговування в i-му центрі надходить у центр j (j,i = 1, 2, …, M). Агрегований стан мережі позначимо через , де та - кількість повідомлень r-го класу в i-му центрі. Величина повинна задовольняти наступні умови:

1)

2)

3)

Множину можливих станів можна визначити наступним чином

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

де -- середнє число відвідувань повідомленням класу r центру j між двома відвідуваннями ним виділеного центру. Значення однозначно визначаються з системи рівнянь

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

Покажемо, що середній час очікування повідомлень r-го класу в i-му центрі, що залежить від навантаження, може бути виражений через характеристики мережі таким чином:

Дійсно, з визначення маємо

РОЗДІЛ 4. ОБЧИСЛЕННЯ ХАРАКТЕРИСТИК МЕРЕЖ МАСОВОГО ОБСЛУГОВУВАННЯ

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

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

Основою більшості таких алгоритмів є рекурентний метод Бузена (алгоритм згортки).

4.1 МЕТОД БУЗЕНА

Відповідно до цього методу алгоритм розрахунку нормалізуючої константи

де множник згідно (2.1.26), (2.1.34) має вигляд



а простір станів мережі

зводиться до простої ітеративної процедури, суть якої полягає в наступному.

Розглянемо функцію

Очевидно, що при при m>1маємо

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

Якщо центр т не залежить від навантаження, той вираз (4.1.3) можна спростити. В цьому випадку

Підставивши (4.1.5) у вираз (4.1.3), після спрощень одержуємо

Формули (4.1.6) і (4.1.3) дозволяють здійснювати рекурентне обчислення g(n, m) при початкових умовах У табл. 4.1 і 4.2 показаний схематичний опис алгоритму Бузена. Стовпці таблиці заповнюються послідовно зверху вниз. Якщо центр т не залежить від навантаження, то елементи стовпця т обчислюються по формулі (4.1.6), інакше - використовується вираз (4.1.4) і для відшукання Z_j(k) застосовується рекурентний вираз

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

ТАБЛИЦЯ 4.1 Метод Бузена. Центри не залежать від навантаження.

m n	1	2	…	m-1	m	…	M
0	1	1	…	1	1	…	1
1
…	…						…
n-1
n
…	…						…
N

ТАБЛИЦЯ 4.2 Метод Бузена. Центри залежать від навантаження.

m n	1	…	m-1	m	…	M
0	1	…			…	1
1
…	…		…			…
n-1
n
…	…					…
N

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



Останній вираз можна записати у рекуррентному вигляді

де

Підставляючи (4.1.7) в (4.1.3), одержуємо

Після перетворень маємо остаточно

Для мережі, що не залежить від навантаження , вираз (4.1.8) співпадає з (4.1.6). Якщо , то



вираз (4.1.8) дозволяє значно скоротити обчислення по порівнянню з прямим використовуванням формули (4.1.3) для випадку, коли центр т складається з кількох однакових обслуговуючих центрів.

Відмітимо, що нормалізуючі константи, які обчислені в результаті роботи описаного вище алгоритму не є однозначними, оскільки залежать від конкретного вибору величин , які визначаються з системи рівнянь

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

4.2 ОБСЧИСЛЕННЯ ХАРАКТЕРИСТИК МЕРЕЖІ МО

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

де нормалізуючі константи визначаються з останнього стовпця табл. 4.1. Для мережі, що залежить від навантаження, формула (4.1.1) описує граничний розподіл лише для граничного центру М. Для відшукання граничного розподілу кількості повідомлень в будь-якому центрі і при обчисленні величин g(n,m) у табл. 4.1 необхідно перенумерувати центри так, щоб i-й центр став граничним, і повторно застосувати алгоритм Бузена.

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

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

. З урахуванням нової допоміжної функції граничний розподіл приймає вигляд

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

звідки витікає, що



У разі, коли i-й центр містить A_i однакових обслуговуючих приладів, маємо

В частинному випадку при A_i=2

Значення допоміжної функції у виразі (4.2.10) розраховуються ітераційно з початковою умовою

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

РОЗДІЛ 5. МЕТОД ДЕКОМПОЗИЦІЙНОЇ АПРОКСИМАЦІЇ

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

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

Інші методи розглянемо детальніше.

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

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

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

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

5.1 АПРОКСИМАЦІЯ ФУНКЦІЙ РОЗПОДІЛУ

Якщо функції розподілу тривалості обслуговування в центрах мережі допускають раціональне перетворення Лапласа і обслуговування повідомлень в центрах мережі здійснюється відповідно до дисципліни РП, ОБО або ОППО, то відповідно до теореми ВСМР стаціонарні імовірності станів мережі задовольняють мультиплікативній формі і мають вигляд . Таким чином, один із способів наближеного дослідження немарківських мереж МО полягає в апроксимації довільних функцій розподілу тривалості обслуговування повідомлень в центрах мережі узагальненим розподілом Кокса. Строге обґрунтування можливості такої апроксимації дається наступною теоремою.

Теорема. Нехай Q(x) -- довільна функція розподілу, яка задовольняє умові Q(0)=0, і -- клас нескінченних сумішей ерланговськіх розподілів. Тоді для будь-яких і знайдеться такий розподіл , що



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

На практиці звичайно розглядають дві основні характеристики функції розподілу: математичне сподівання ф=M[t] і дисперсію D=M[t²]-M²[t], де та .Таке завдання функції розподілу обґрунтовується тим, що характеристики багатьох систем МО визначаються тільки першими двома моментами функції розподілу тривалості обслуговування.

Покажемо тепер, що апроксимація функцій розподілу із заданими значеннями ф і щ може бути ефективно проведена при щ<1 узагальненим розподілом Ерланга, а при щ>1 гіперекспоненціальним розподілом другого порядку.

Розглянемо узагальнений розподіл Коксу для випадку, коли µ₁= µ₂=… µ_k=µ, a₀=1, a_r=1 при b_k=1. Таким чином, після першого етапу повідомлення може закінчити обслуговування з імовірністю b₁ або продовжувати обслуговування на етапах, що залишилися, з імовірністю a₁=1-b₁. Вираз для перетворення Лапласа узагальненого розподілу Кокса в цьому випадку набуває вигляду