МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СЕТИ ETHERNET КАК СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

1.1. Понятие системы массового обслуживания (СМО)

Система массового обслуживания (СМО) — система, которая производит обслуживание поступающих в неё требований. Обслуживание требований в СМО осуществляется обслуживающими приборами. Классическая СМО содержит от одного до бесконечного числа приборов. В зависимости от наличия возможности ожидания поступающими требованиями начала обслуживания СМО подразделяются на:

- системы с потерями, в которых требования, не нашедшие в момент поступления ни одного свободного прибора, теряются;

- системы с ожиданием, в которых имеется накопитель бесконечной ёмкости для буферизации поступивших требований, при этом ожидающие требования образуют очередь;

- системы с накопителем конечной ёмкости (ожиданием и ограничениями), в которых длина очереди не может превышать ёмкости накопителя; при этом требование, поступающее в переполненную СМО (отсутствуют свободные места для ожидания), теряются.

Выбор требования из очереди на обслуживание производится с помощью так называемой дисциплины обслуживания. Их примерами являются FCFS/FIFO (пришедший первым обслуживается первым), LCFS/LIFO (пришедший последним обслуживается первым), random (случайный выбор). В системах с ожиданием накопитель в общем случае может иметь сложную структуру.

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

Цикл функционирования системы массового обслуживания подобного рода повторяется многократно в течение всего периода работы обслуживающей системы. При этом предполагается, что переход системы на обслуживание очередного требования после завершения обслуживания предыдущего требования происходит мгновенно, в случайные моменты времени.

Примерами систем массового обслуживания могут служить:

- посты технического обслуживания автомобилей;

- посты ремонта автомобилей;

- персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач;

- станции технического обслуживания автомобилей;

- аудиторские фирмы;

- отделы налоговых инспекций, занимающиеся приемкой и проверкой текущей отчетности предприятий;

- телефонные станции и т. д.

Основными компонентами системы массового обслуживания любого вида являются:

- входной поток поступающих требований или заявок на обслуживание;

- дисциплина очереди;

- механизм обслуживания.

Все системы массового обслуживания различают по числу каналов обслуживания на:

-  одноканальные системы;

-  многоканальные системы.

1.2. Задачи одноканальной СМО с ограниченной очередью

В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Если заявка застаёт канал свободным, то она принимается на обслуживание и обслуживается каналом. После окончания обслуживания канал освобождается. Дисциплина очереди естественная: кто раньше пришёл, тот раньше и обслуживается. Максимальное число мест в очереди m.

Граф такой СМО представлен на рисунке 1.2.

*Рисунок 1.2 – Граф одноканальной СМО с ограниченной очередью в файле "Формулы и диаграмы"*

Состояния СМО представляются следующим образом:

- S₀ - канал обслуживания свободен;

- S₁ – канал обслуживания занят, но очереди нет;

- S₂ – канал обслуживания занят, в очереди одна заявка;

- S_k+1 – канал обслуживания занят, в очереди k заявок;

- S_m+1 – канал обслуживания занят, все m мест в очереди заняты.

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

Интенсивность потока обслуживания равна μ. Длительность обслуживания – случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий.

Система уравнений, описывающих процесс в этой системе, имеет решение:

*Формула 1.1. в файле "Формулы и диаграмы"*

Знаменатель первого выражения представляет собой геометрическую прогрессию с первым членом 1 и знаменателем ρ, откуда получаем

*Формула 1.2. в файле "Формулы и диаграмы"*​

*Формула 1.3. в файле "Формулы и диаграмы"*​

и предельные вероятности приобретают вид:

*Формула 1.4. в файле "Формулы и диаграмы"*​

*Формула 1.5. в файле "Формулы и диаграмы"*​

*Формула 1.6. в файле "Формулы и диаграмы"*​

*Формула 1.7. в файле "Формулы и диаграмы"*​

Выполнение условия стационарности ρ <1 необязательно, поскольку число заявок в СМО контролируется путем введения ограничения на длину очереди. Однако выражение справедливо только при ρ <1 (поскольку для ρ =1 получается неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем ρ = 1 равна в этом случае m +2 и

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной m:

Вероятность отказа в обслуживании заявки (отказ произойдет в случае, если канал занят и в очереди находятся m заявок):

*Формула 1.8. в файле "Формулы и диаграмы"*​

Относительная пропускная способность.

*Формула 1.9. в файле "Формулы и диаграмы"*​

Абсолютная пропускная способность.

*Формула 1.10. в файле "Формулы и диаграмы"*​

Среднее число находящихся в очереди заявок.

В случае, когда ρ отлично от 1, можно воспользоваться формулой

*Формула 1.11. в файле "Формулы и диаграмы"*​

При ρ = 1 можно прибегнуть к прямому подсчету

*Формула 1.12. в файле "Формулы и диаграмы"*​

Среднее число находящихся в системе заявок.

Поскольку среднее число находящихся в системе заявок 

*Формула 1.13. в файле "Формулы и диаграмы"*​

где   - среднее число заявок, находящихся под обслуживанием, то зная   остается найти  . Т.к. канал один, то число обслуживаемых заявок может равняться либо 0, либо 1 с вероятностями P0 и P1=1- P0 соответственно, откуда

*Формула 1.14. в файле "Формулы и диаграмы"*​

и среднее число находящихся в системе заявок равно

*Формула 1.15. в файле "Формулы и диаграмы"*​

Среднее время ожидания заявки в очереди.

*Формула 1.16. в файле "Формулы и диаграмы"*​

То есть, среднее время ожидания заявки в очереди равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.

Среднее время пребывания заявки в системе.

Время пребывания заявки в системе  складывается из времени ожидания заявки в очереди  и времени обслуживания  . Если загрузка системы составляет 100%, то  =1/μ, в противном случае  =q/ μ. Отсюда

*Формула 1.17. в файле "Формулы и диаграмы"*​

1.3. Задачи многоканальной СМО с ограниченными очередями

Рассмотрим n-канальную систему массового обслуживания с ожиданием.

Будем считать входящий поток заявок на обслуживание простейшим потоком с интенсивностью λ.

Интенсивность потока обслуживания равна μ. Длительность обслуживания – случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий.

Размер очереди допускает нахождение в ней m заявок.

Для нахождения предельных вероятностей можно использовать следующие выражения.

*Формула 1.18. в файле "Формулы и диаграмы"*​

*Формула 1.19. в файле "Формулы и диаграмы"*​

*Формула 1.20. в файле "Формулы и диаграмы"*​

Вероятность отказа в обслуживании заявки (отказ произойдет в случае, если все каналы заняты и в очереди находятся m заявок):

*Формула 1.21. в файле "Формулы и диаграмы"*​

Относительная пропускная способность.

*Формула 1.22. в файле "Формулы и диаграмы"*​

Абсолютная пропускная способность.

*Формула 1.23. в файле "Формулы и диаграмы"*​

Среднее число занятых каналов.

Для СМО с очередью среднее число занятых каналов не совпадает (в отличие от СМО с отказами) со средним числом заявок в системе. Отличие равно числу заявок, ожидающих в очереди.

Обозначим среднее число занятых каналов  . Каждый занятый канал обслуживает в среднем μ заявок в единицу времени, а СМО в целом – А заявок в единицу времени. Разделив А на μ получим

*Формула 1.24. в файле "Формулы и диаграмы"*​

Среднее число находящихся в очереди заявок.

Для нахождения среднего числа ожидающих в очереди заявок в случае, если χ≠1, можно использовать выражение:

*Формула 1.25. в файле "Формулы и диаграмы"*​

Для χ=1 необходимо подсчитать сумму:

*Формула 1.26. в файле "Формулы и диаграмы"*​

Среднее число находящихся в системе заявок.

*Формула 1.27. в файле "Формулы и диаграмы"*​

Среднее время ожидания заявки в очереди.

Среднее время ожидания заявки в очереди можно найти из выражения (χ≠1).

*Формула 1.28. в файле "Формулы и диаграмы"*​

Среднее время пребывания заявки в системе.

Так же как и в случае с одноканальной СМО имеем:

*Формула 1.29. в файле "Формулы и диаграмы"*​