Білоруський державний університет інформатики і радіоелектроніки
кафедра мереж і пристроїв телекомунікацій
РЕФЕРАТ
На тему:
«Моделі систем масового обслуговування. Класифікація систем масового обслуговування »
МІНСЬК, 2008
Математичне введення в теорію ланцюгів Маркова. (Markov 's chain)
Дискретні ланцюги Маркова. Будемо говорити, що задана дискретна ланцюг Маркова, якщо для послідовності випадкових величин виконується рівність
Це означає, що потік випадкових величин визначається тільки вірогідністю переходу від попереднього значення випадкової величини до подальшого. Знаючи початковий розподіл вірогідності, можна знайти розподіл на будь-якому кроці. Величини i n можна інтерпретувати як номери станів деякої динамічної системи з дискретною безліччю станів (типу кінцевого автомата). Якщо вірогідність переходів не залежить від номера кроку, то такий ланцюг Маркова називається однорідною і її визначення задається набором ймовірностей
Для однорідного Марківського ланцюга можна визначити ймовірності переходу зі стану i в стан j за m кроків
Ланцюг Маркова званому, якщо кожне її стан може бути досягнуто з будь-якого іншого стану. Стан i називається поглинаючим, якщо для нього p ii = 1.
Стан називається поворотним, якщо вірогідність попадання в нього за кінцеве число кроків дорівнює одиниці. В іншому випадку стан відноситься до безповоротним. Ще Одне стан може бути періодичним і апериодическим в залежності від наявності кратних кроків повернення. Введемо вірогідність повернення в стан i через n кроків після відходу з цього стану:
Вони дозволяють визначити середнє число кроків або, інакше кажучи, середній час повернення:
Стан називається поворотним нульовим, якщо середній час повернення в нього рівно нескінченності, і поворотним ненульовим, якщо цей час звичайно. Відомі дві важливі теореми:
Теорема 1.
Стани непріводімий ланцюга Маркова або всі неповоротні, або всі поворотні нульові, або всі поворотні ненульові. У випадку періодичної ланцюга всі стани мають один і той же період.
Друга теорема розглядає імовірності досягнення станів в стаціонарному (тобто не залежному від початкового розподілу вірогідності) режимі. Відповідний розподіл ймовірностей також називають стаціонарним. Знаходження стаціонарного розподілу вірогідності досягнення станів одна з основних задач теорії телетрафіка.
Теорема 2.
Для непріводімий і апериодической ланцюга Маркова завжди існують граничні ймовірності, що не залежать від початкового розподілу вірогідності. Більш того, має місце одна з наступних двох можливостей:
А) всі стани ланцюга неповоротні або всі поворотні нульові, і тоді все граничні ймовірності рівні нулю і стаціонарного стану не існує;
Б) всі стани поворотні ненульові і тоді існує стаціонарний розподіл ймовірностей:
Стан називається ергодичним, якщо воно аперіодічно і зворотно ненульове. Якщо всі стани ланцюга Маркова ергодичність, то вся ланцюг називається ергодичної. Граничні ймовірності ергодичної ланцюга Маркова називають вірогідністю стану рівноваги, маючи на увазі, що залежність від початкового розподілу вірогідності повністю відсутня.
Ланцюг Маркова з кінцевим числом станів (кінцева ланцюг), зручно зображати у вигляді орієнтованого графа, званого діаграмою переходів. Вершини графа асоціюються із станами, а ребра з вірогідністю переходів.
Обчислення вірогідності досягнення станів проводиться прямими методами або за допомогою z-перетворення.
Ланцюг Маркова.
Введемо матрицю вірогідності переходів і вектор-рядок вірогідності на кроці n
Розподіл вірогідності на довільному кроці тоді буде підкорятися матричному співвідношенню:
Воно дозволяє рекуррентно обчислювати все ймовірності станів. Для знаходження граничного розподілу (стаціонарного) потрібно розв'язати рівняння:
Його можна вирішувати як систему лінійних алгебраїчних рівнянь, якщо ланцюг кінцева.
Для прикладу (рис. 1) маємо:
і рішення матричного рівняння зводиться до розв'язання системи трьох рівнянь:
Коефіцієнти першого рівняння в цій системі доповнюють до одиниці суму коефіцієнтів другого і третього рівнянь; це свідчить про лінійної залежності між ними. Тому для вирішення системи рівнянь потрібно ввести додаткове нормуюче умова. У даному прикладі:
Вирішуючи систему отриманих рівнянь, маємо:
Рівняння для вірогідності досягнення стану в перехідному режимі вирішити значно важче. Деякого спрощення можна досягти, використовуючи z - перетворення. Застосуємо його до рівняння для перехідних ймовірностей
Позначаючи відповідні перетворення, отримаємо:
Всі отримані тут математичні результати ставилися до однорідних Марківським процесам, де вірогідність переходів не залежить від часу. У більш загальному випадку така залежність має місце.
Розглянемо вірогідність переходу системи зі стану i на m-тому кроці в стан j на n-тому кроці для n> m.
Можна показати, що ці ймовірності пов'язані між собою, так званим рівняннями Чепмена-Колмогорова. (Chapman - Kolmogorov)
Для однорідних ланцюгів Маркова ці рівняння спрощуються так як
І зводяться до аналізованих вище.
Безперервні ланцюга Маркова.
Випадковий процес X (t) з дискретною безліччю значень утворює безперервний ланцюг Маркова, якщо
Майбутні стани залежать від минулого тільки через поточний стан. Для безперервний ланцюгів Маркова основним також є рівняння Чепмена-Колмогорова, для однорідного ланцюга має вигляд:
Тут матриця H (t) = [P ij (t)] - матриця ймовірностей переходу зі стану i в стан j у момент часу t, а матриця Q називається матрицею інтенсивностей переходів. Її елементи мають наступний сенс: якщо в момент часу t система знаходилася в стані E i, то ймовірність переходу протягом проміжку часу (t, t + Δt) в довільне стан E j задається величиною q ij (t) Δt + o (Δt) , а ймовірність відходу зі стану E i величиною-q ii Δt + o (Δt).
Таким чином, інтенсивності переходів можна обчислювати як відповідні межі при прагненні до нуля тривалості тимчасового інтервалу.
Найбільш важливим для подальшого використання є клас безперервних ланцюгів Маркова званих «процесами загибелі - розмноження» (Birth - death process). Для таких систем зі стану k можливі переходи тільки в стану k, k-1 і k +1 в наступні моменти часу:
· В момент t об'єм популяції дорівнював k і протягом часу (t, t + Δt) не відбулося зміни стану
· В момент t об'єм популяції дорівнював k-1 і протягом часу (t, t + Δt) народився один член популяції
· У момент часу t об'єм популяції дорівнював k +1 і протягом часу (t, t + Δt) загинув один член популяції
Рис. 1. Можливі переходи в стан Ек.
Будемо шукати ймовірність того, що в момент часу t об'єм популяції дорівнює k, позначивши його P k (t). Можна записати співвідношення для вірогідності досягнення стану k у момент часу t + Δt:
Визначимо граничні і нормуючі умови:
Висловимо ймовірності переходів за інтервал Δt через інтенсивності
Вер (+1) = λ k Δt + o (Δt); Вер (-1) = μ k Δt + o (Δt).
Вірогідність нуля народжень 1 - λ k Δt + o (Δt), а нуля смертей 1 - μ k Δt + o (Δt).
Таким чином, вірогідність того, що стан k збережеться незмінним, буде дорівнює добутку [1 - λ k Δt + o (Δt)] [1 - μ k Δt + o (Δt)].
Тоді рівняння Чепмена-Колмогорова набувають вигляду
Розкриваючи дужки і проводячи поділ на Δt, отримаємо:
У межі виходить система диференціально-різницевих рівнянь, рішення якої будуть відігравати важливу роль для практичних завдань.
У відповідність цій системі рівнянь можна поставити наочну діаграму інтенсивностей переходів, яка аналогічна діаграмі переходів для дискретних ланцюгів Маркова (Мал. 2)
Рис. 2 Діаграма інтенсивностей переходів для процесу розмноження і загибелі.
Овалом тут відповідають дискретні стану, а стрілки визначають інтенсивності потоків вірогідності (а не вірогідність!) Переходів від одного стану до іншого.
Має місце своєрідний «закон збереження»:
Різниця між сумою інтенсивностей, з якою система потрапляє в стан k і сумою інтенсивностей, з якою система залишає цей стан повинна дорівнювати інтенсивності зміни потоку в цей стан (похідної за часом).
Застосування закону збереження дозволяє одержувати рівняння для будь-якої підсистеми Марківського ланцюга типу процесу «загибелі-розмноження». Особливо ефективним виявляється побудова рішень у стаціонарному, сталому режимі, коли можна вважати що вірогідність в довільний, достатньо віддалений момент часу, залишаються постійними.
Прирівнюючи похідну за часом нулю, отримуємо систему різницевих рівнянь
Вважаючи, що інтенсивності λ -1 = λ -2 = λ -3 = ... 0; μ 0 = μ -1 = μ -2 = μ -3 = ... = 0, друге рівняння виписувати окремо далі не буде потрібно. Отже, стаціонарний режим в ланцюзі Маркова буде описуватися системою різницевих рівнянь і умовою нормування для вірогідності
Неважко бачити, що ці рівняння легко виводяться із закону збереження інтенсивностей ймовірностей. У стаціонарному режимі різниця потоків рівна нулю і отримані вище рівняння набувають сенсу рівнянь рівноваги або балансу, як їх і називають.
Інтенсивність потоку вірогідності в стан k дорівнює інтенсивності потоку з цього стану.
Вирішувати рівняння балансу можна, спочатку визначивши при k = 0 значення
Потім, побудувавши систему рівнянь для k = 1, можна отримати
Далі отримуємо
З умови нормування:
Система, описувана отриманими вище виразами, буде мати стаціонарні ймовірності станів, коли вона ергодична. Ця умова може бути виражене через співвідношення інтенсивностей. Необхідно і достатньо, щоб існувало деяке значення k, починаючи з якого виконувалося нерівність
Для більшості реальних систем масового обслуговування це нерівність виконується.
Класифікація систем масового обслуговування.
Використовується трьох -, чотирьох -, шести - компонентне символічне позначення системи масового обслуговування, запропоноване Кендаллом (Candall) і розвинене в роботах Г. П. Барашіна.
a / b / c: d / e / f
a - розподіл надходить потік запитів.
b - закон розподілу часу обслуговування.
Типові умовні позначення:
М - експоненційний (Марківське) розподіл,
D - детерміноване розподіл,
E k - ерланговское розподіл k-го порядку,
HM k - гіперекспоненціальное,
HE k - гіперерланговское розподіл порядку k,
GI - довільний розподіл незалежних проміжків між заявками,
G - довільний розподіл тривалостей обслуговування.
c - структура системи обслуговування (звичайно число серверів).
d - дисципліна обслуговування (параметри після двокрапки іноді опускають).
Зазвичай використовується скорочена символічне позначення, наприклад FF замість FIFO, LF, PR і т.п.
e - максимальне число запитів, сприймається системою, може вживатися символ ¥.
f - максимальне число запитів до системи обслуговування.
У деяких публікаціях останніми символами відображають якісні характеристики системи обслуговування. Деякі загальні результати та основи математичного апарату, необхідного для аналізу можна отримати, розглядаючи системи G / G / m.
Формула Літтла (Little).
Розглянемо тимчасову діаграму роботи системи масового обслуговування (рис. 3), відобразити на ній послідовність надходження вимог, приміщення вимог в чергу і обробки серверами системи.
Тимчасова діаграма роботи системи масового обслуговування.
У загальному випадку ясно, що зі збільшенням числа вимог росте час очікування. Встановимо співвідношення між середнім числом вимог в системі, інтенсивністю потоку і середнього часу перебування в системі. Позначимо число вступників у проміжку часу (0, t) вимог як функцію часу α (t).
Число виходять з системи заявок (обслужених) на цьому інтервалі позначимо δ (t). На малюнку 4 показані приклади функціональних залежностей цих двох випадкових процесів від часу.
Рис. 4 Залежність між середнім числом вимог в системі, інтенсивністю потоку і середнім часу перебування в системі.
Число вимог, що знаходяться в системі у момент t дорівнюватиме:
Площа між двома розглянутими кривими від 0 до t - дає загальний час, проведений усіма заявками в системі за час t.
Позначимо цю накопичену величину γ (t). Якщо інтенсивність вхідного потоку дорівнює λ, а середня інтенсивність за час t:
Нарешті, визначимо середнє число вимог в системі в проміжку (0, t):
З останніх трьох рівнянь випливає, що:
Якщо в СМО існує стаціонарний режим, то при t → ∞, будуть мати місце співвідношення:
Останнє співвідношення означає, що середнє число заявок у системі дорівнює добутку інтенсивності надходження вимог в систему на середній час перебування в системі. При цьому не накладається ніяких обмежень на розподіли вхідного потоку і часу обслуговування. Вперше доказ цього факту дав Дж.Літтл і це співвідношення носить назву формула Літтла.
Цікаво, що в якості СМО можна розглянути тільки чергу із заявок в буфері. Тоді формула Літтла набуває інший зміст - середня довжина черги дорівнює добутку інтенсивності вхідного потоку заявок на середній час очікування в черзі:
Якщо навпаки розглядати СМО тільки як сервери, то формула Літтла дає:
де
У будь-якому разі:
Одним з основних параметрів, які використовуються при описі СМО, є коефіцієнт використання (utilization factor). Це фундаментальний параметр, оскільки він визначається як відношення інтенсивності вхідного потоку до пропускної здатності системи. Оскільки пропускна здатність СМО містить m серверів може бути визначена як:
Неважко бачити, що коефіцієнт використання дорівнює в точності інтенсивності навантаження, якщо СМО з одним сервером і в m раз менше для систем з m серверами. Величина коефіцієнта використання дорівнює середньому значенню від частки зайнятих серверів і
Якщо в СМО типу G/G/1 існує стаціонарний режим і можна визначити ймовірність того, що в деякий випадковий момент сервер буде вільний, то
ЛІТЕРАТУРА
1. Л.М. Волков, М.С. Немирівський, Ю.С. Шинака. Системи цифрового радіозв'язку: базові методи і характеристики. Навчальний посібник.-М.: Еко-Трендз, 2005.
2. М.В. Гаранін, В.І. Журавльов, С.В. Кунегін. Системи і мережі передачі інформації. - М.: Радіо і зв'язок, 2001.
3. Передача дискретних сообщеній. / Под ред. В.П. Шувалова. - М.: Радіо і зв'язок, 1990.
4. Основи передачі дискретних сообщеній. / Под ред. В.М. Пушкіна. - М.: Радіо і зв'язок, 1992.
5. Н.В. Захарченко, П.Я. Нудельман, В.Г. Кононович. Основи передачі дискретних повідомлень. -М.: Радіо і зв'язок, 1990.
кафедра мереж і пристроїв телекомунікацій
РЕФЕРАТ
На тему:
«Моделі систем масового обслуговування. Класифікація систем масового обслуговування »
МІНСЬК, 2008
Математичне введення в теорію ланцюгів Маркова. (Markov 's chain)
Дискретні ланцюги Маркова. Будемо говорити, що задана дискретна ланцюг Маркова, якщо для послідовності випадкових величин виконується рівність
Це означає, що потік випадкових величин визначається тільки вірогідністю переходу від попереднього значення випадкової величини до подальшого. Знаючи початковий розподіл вірогідності, можна знайти розподіл на будь-якому кроці. Величини i n можна інтерпретувати як номери станів деякої динамічної системи з дискретною безліччю станів (типу кінцевого автомата). Якщо вірогідність переходів не залежить від номера кроку, то такий ланцюг Маркова називається однорідною і її визначення задається набором ймовірностей
Для однорідного Марківського ланцюга можна визначити ймовірності переходу зі стану i в стан j за m кроків
Ланцюг Маркова званому, якщо кожне її стан може бути досягнуто з будь-якого іншого стану. Стан i називається поглинаючим, якщо для нього p ii = 1.
Стан називається поворотним, якщо вірогідність попадання в нього за кінцеве число кроків дорівнює одиниці. В іншому випадку стан відноситься до безповоротним. Ще Одне стан може бути періодичним і апериодическим в залежності від наявності кратних кроків повернення. Введемо вірогідність повернення в стан i через n кроків після відходу з цього стану:
Вони дозволяють визначити середнє число кроків або, інакше кажучи, середній час повернення:
Стан називається поворотним нульовим, якщо середній час повернення в нього рівно нескінченності, і поворотним ненульовим, якщо цей час звичайно. Відомі дві важливі теореми:
Теорема 1.
Стани непріводімий ланцюга Маркова або всі неповоротні, або всі поворотні нульові, або всі поворотні ненульові. У випадку періодичної ланцюга всі стани мають один і той же період.
Друга теорема розглядає імовірності досягнення станів в стаціонарному (тобто не залежному від початкового розподілу вірогідності) режимі. Відповідний розподіл ймовірностей також називають стаціонарним. Знаходження стаціонарного розподілу вірогідності досягнення станів одна з основних задач теорії телетрафіка.
Теорема 2.
Для непріводімий і апериодической ланцюга Маркова завжди існують граничні ймовірності, що не залежать від початкового розподілу вірогідності. Більш того, має місце одна з наступних двох можливостей:
А) всі стани ланцюга неповоротні або всі поворотні нульові, і тоді все граничні ймовірності рівні нулю і стаціонарного стану не існує;
Б) всі стани поворотні ненульові і тоді існує стаціонарний розподіл ймовірностей:
Стан називається ергодичним, якщо воно аперіодічно і зворотно ненульове. Якщо всі стани ланцюга Маркова ергодичність, то вся ланцюг називається ергодичної. Граничні ймовірності ергодичної ланцюга Маркова називають вірогідністю стану рівноваги, маючи на увазі, що залежність від початкового розподілу вірогідності повністю відсутня.
Ланцюг Маркова з кінцевим числом станів (кінцева ланцюг), зручно зображати у вигляді орієнтованого графа, званого діаграмою переходів. Вершини графа асоціюються із станами, а ребра з вірогідністю переходів.
Обчислення вірогідності досягнення станів проводиться прямими методами або за допомогою z-перетворення.
Ланцюг Маркова.
Введемо матрицю вірогідності переходів і вектор-рядок вірогідності на кроці n
Розподіл вірогідності на довільному кроці тоді буде підкорятися матричному співвідношенню:
Воно дозволяє рекуррентно обчислювати все ймовірності станів. Для знаходження граничного розподілу (стаціонарного) потрібно розв'язати рівняння:
Його можна вирішувати як систему лінійних алгебраїчних рівнянь, якщо ланцюг кінцева.
Для прикладу (рис. 1) маємо:
і рішення матричного рівняння зводиться до розв'язання системи трьох рівнянь:
Коефіцієнти першого рівняння в цій системі доповнюють до одиниці суму коефіцієнтів другого і третього рівнянь; це свідчить про лінійної залежності між ними. Тому для вирішення системи рівнянь потрібно ввести додаткове нормуюче умова. У даному прикладі:
Вирішуючи систему отриманих рівнянь, маємо:
Рівняння для вірогідності досягнення стану в перехідному режимі вирішити значно важче. Деякого спрощення можна досягти, використовуючи z - перетворення. Застосуємо його до рівняння для перехідних ймовірностей
Позначаючи відповідні перетворення, отримаємо:
Всі отримані тут математичні результати ставилися до однорідних Марківським процесам, де вірогідність переходів не залежить від часу. У більш загальному випадку така залежність має місце.
Розглянемо вірогідність переходу системи зі стану i на m-тому кроці в стан j на n-тому кроці для n> m.
Можна показати, що ці ймовірності пов'язані між собою, так званим рівняннями Чепмена-Колмогорова. (Chapman - Kolmogorov)
Для однорідних ланцюгів Маркова ці рівняння спрощуються так як
І зводяться до аналізованих вище.
Безперервні ланцюга Маркова.
Випадковий процес X (t) з дискретною безліччю значень утворює безперервний ланцюг Маркова, якщо
Майбутні стани залежать від минулого тільки через поточний стан. Для безперервний ланцюгів Маркова основним також є рівняння Чепмена-Колмогорова, для однорідного ланцюга має вигляд:
Тут матриця H (t) = [P ij (t)] - матриця ймовірностей переходу зі стану i в стан j у момент часу t, а матриця Q називається матрицею інтенсивностей переходів. Її елементи мають наступний сенс: якщо в момент часу t система знаходилася в стані E i, то ймовірність переходу протягом проміжку часу (t, t + Δt) в довільне стан E j задається величиною q ij (t) Δt + o (Δt) , а ймовірність відходу зі стану E i величиною-q ii Δt + o (Δt).
Таким чином, інтенсивності переходів можна обчислювати як відповідні межі при прагненні до нуля тривалості тимчасового інтервалу.
Найбільш важливим для подальшого використання є клас безперервних ланцюгів Маркова званих «процесами загибелі - розмноження» (Birth - death process). Для таких систем зі стану k можливі переходи тільки в стану k, k-1 і k +1 в наступні моменти часу:
· В момент t об'єм популяції дорівнював k і протягом часу (t, t + Δt) не відбулося зміни стану
· В момент t об'єм популяції дорівнював k-1 і протягом часу (t, t + Δt) народився один член популяції
· У момент часу t об'єм популяції дорівнював k +1 і протягом часу (t, t + Δt) загинув один член популяції
Рис. 1. Можливі переходи в стан Ек.
Будемо шукати ймовірність того, що в момент часу t об'єм популяції дорівнює k, позначивши його P k (t). Можна записати співвідношення для вірогідності досягнення стану k у момент часу t + Δt:
Визначимо граничні і нормуючі умови:
Висловимо ймовірності переходів за інтервал Δt через інтенсивності
Вер (+1) = λ k Δt + o (Δt); Вер (-1) = μ k Δt + o (Δt).
Вірогідність нуля народжень 1 - λ k Δt + o (Δt), а нуля смертей 1 - μ k Δt + o (Δt).
Таким чином, вірогідність того, що стан k збережеться незмінним, буде дорівнює добутку [1 - λ k Δt + o (Δt)] [1 - μ k Δt + o (Δt)].
Тоді рівняння Чепмена-Колмогорова набувають вигляду
Розкриваючи дужки і проводячи поділ на Δt, отримаємо:
У межі виходить система диференціально-різницевих рівнянь, рішення якої будуть відігравати важливу роль для практичних завдань.
У відповідність цій системі рівнянь можна поставити наочну діаграму інтенсивностей переходів, яка аналогічна діаграмі переходів для дискретних ланцюгів Маркова (Мал. 2)
Рис. 2 Діаграма інтенсивностей переходів для процесу розмноження і загибелі.
Овалом тут відповідають дискретні стану, а стрілки визначають інтенсивності потоків вірогідності (а не вірогідність!) Переходів від одного стану до іншого.
Має місце своєрідний «закон збереження»:
Різниця між сумою інтенсивностей, з якою система потрапляє в стан k і сумою інтенсивностей, з якою система залишає цей стан повинна дорівнювати інтенсивності зміни потоку в цей стан (похідної за часом).
Застосування закону збереження дозволяє одержувати рівняння для будь-якої підсистеми Марківського ланцюга типу процесу «загибелі-розмноження». Особливо ефективним виявляється побудова рішень у стаціонарному, сталому режимі, коли можна вважати що вірогідність в довільний, достатньо віддалений момент часу, залишаються постійними.
Прирівнюючи похідну за часом нулю, отримуємо систему різницевих рівнянь
Вважаючи, що інтенсивності λ -1 = λ -2 = λ -3 = ... 0; μ 0 = μ -1 = μ -2 = μ -3 = ... = 0, друге рівняння виписувати окремо далі не буде потрібно. Отже, стаціонарний режим в ланцюзі Маркова буде описуватися системою різницевих рівнянь і умовою нормування для вірогідності
Неважко бачити, що ці рівняння легко виводяться із закону збереження інтенсивностей ймовірностей. У стаціонарному режимі різниця потоків рівна нулю і отримані вище рівняння набувають сенсу рівнянь рівноваги або балансу, як їх і називають.
Інтенсивність потоку вірогідності в стан k дорівнює інтенсивності потоку з цього стану.
Вирішувати рівняння балансу можна, спочатку визначивши при k = 0 значення
Потім, побудувавши систему рівнянь для k = 1, можна отримати
Далі отримуємо
З умови нормування:
Система, описувана отриманими вище виразами, буде мати стаціонарні ймовірності станів, коли вона ергодична. Ця умова може бути виражене через співвідношення інтенсивностей. Необхідно і достатньо, щоб існувало деяке значення k, починаючи з якого виконувалося нерівність
Для більшості реальних систем масового обслуговування це нерівність виконується.
Класифікація систем масового обслуговування.
Використовується трьох -, чотирьох -, шести - компонентне символічне позначення системи масового обслуговування, запропоноване Кендаллом (Candall) і розвинене в роботах Г. П. Барашіна.
a / b / c: d / e / f
a - розподіл надходить потік запитів.
b - закон розподілу часу обслуговування.
Типові умовні позначення:
М - експоненційний (Марківське) розподіл,
D - детерміноване розподіл,
E k - ерланговское розподіл k-го порядку,
HM k - гіперекспоненціальное,
HE k - гіперерланговское розподіл порядку k,
GI - довільний розподіл незалежних проміжків між заявками,
G - довільний розподіл тривалостей обслуговування.
c - структура системи обслуговування (звичайно число серверів).
d - дисципліна обслуговування (параметри після двокрапки іноді опускають).
Зазвичай використовується скорочена символічне позначення, наприклад FF замість FIFO, LF, PR і т.п.
e - максимальне число запитів, сприймається системою, може вживатися символ ¥.
f - максимальне число запитів до системи обслуговування.
У деяких публікаціях останніми символами відображають якісні характеристики системи обслуговування. Деякі загальні результати та основи математичного апарату, необхідного для аналізу можна отримати, розглядаючи системи G / G / m.
Формула Літтла (Little).
Розглянемо тимчасову діаграму роботи системи масового обслуговування (рис. 3), відобразити на ній послідовність надходження вимог, приміщення вимог в чергу і обробки серверами системи.
Тимчасова діаграма роботи системи масового обслуговування.
У загальному випадку ясно, що зі збільшенням числа вимог росте час очікування. Встановимо співвідношення між середнім числом вимог в системі, інтенсивністю потоку і середнього часу перебування в системі. Позначимо число вступників у проміжку часу (0, t) вимог як функцію часу α (t).
Число виходять з системи заявок (обслужених) на цьому інтервалі позначимо δ (t). На малюнку 4 показані приклади функціональних залежностей цих двох випадкових процесів від часу.
Рис. 4 Залежність між середнім числом вимог в системі, інтенсивністю потоку і середнім часу перебування в системі.
Число вимог, що знаходяться в системі у момент t дорівнюватиме:
Площа між двома розглянутими кривими від 0 до t - дає загальний час, проведений усіма заявками в системі за час t.
Позначимо цю накопичену величину γ (t). Якщо інтенсивність вхідного потоку дорівнює λ, а середня інтенсивність за час t:
Нарешті, визначимо середнє число вимог в системі в проміжку (0, t):
З останніх трьох рівнянь випливає, що:
Якщо в СМО існує стаціонарний режим, то при t → ∞, будуть мати місце співвідношення:
Останнє співвідношення означає, що середнє число заявок у системі дорівнює добутку інтенсивності надходження вимог в систему на середній час перебування в системі. При цьому не накладається ніяких обмежень на розподіли вхідного потоку і часу обслуговування. Вперше доказ цього факту дав Дж.Літтл і це співвідношення носить назву формула Літтла.
Цікаво, що в якості СМО можна розглянути тільки чергу із заявок в буфері. Тоді формула Літтла набуває інший зміст - середня довжина черги дорівнює добутку інтенсивності вхідного потоку заявок на середній час очікування в черзі:
Якщо навпаки розглядати СМО тільки як сервери, то формула Літтла дає:
де
У будь-якому разі:
Одним з основних параметрів, які використовуються при описі СМО, є коефіцієнт використання (utilization factor). Це фундаментальний параметр, оскільки він визначається як відношення інтенсивності вхідного потоку до пропускної здатності системи. Оскільки пропускна здатність СМО містить m серверів може бути визначена як:
Неважко бачити, що коефіцієнт використання дорівнює в точності інтенсивності навантаження, якщо СМО з одним сервером і в m раз менше для систем з m серверами. Величина коефіцієнта використання дорівнює середньому значенню від частки зайнятих серверів і
Якщо в СМО типу G/G/1 існує стаціонарний режим і можна визначити ймовірність того, що в деякий випадковий момент сервер буде вільний, то
ЛІТЕРАТУРА
1. Л.М. Волков, М.С. Немирівський, Ю.С. Шинака. Системи цифрового радіозв'язку: базові методи і характеристики. Навчальний посібник.-М.: Еко-Трендз, 2005.
2. М.В. Гаранін, В.І. Журавльов, С.В. Кунегін. Системи і мережі передачі інформації. - М.: Радіо і зв'язок, 2001.
3. Передача дискретних сообщеній. / Под ред. В.П. Шувалова. - М.: Радіо і зв'язок, 1990.
4. Основи передачі дискретних сообщеній. / Под ред. В.М. Пушкіна. - М.: Радіо і зв'язок, 1992.
5. Н.В. Захарченко, П.Я. Нудельман, В.Г. Кононович. Основи передачі дискретних повідомлень. -М.: Радіо і зв'язок, 1990.