Материал: Моделирование атак сети массового обслуживания. Бугров Ю.Г., Остапенко Г.А

Складывая вероятности обоих вариантов (по прави­лу сложения вероятностей), получим:

.

Раскроем квадратные скобки, перенесем р₁(t) в ле­вую часть и разделим обе части на :

.

Устремим, как и полагается в подобных случаях, к нулю; слева получим в пределе производную функции p₁(t). Таким образом, запишем дифферен­циальное уравнение для p₁(t):

.

Или отбрасывая аргумент t у функций р₁ , р₂ (теперь он нам больше уже не нужен):

. (3.6)

Рассуждая аналогично для всех остальных состоя­ний, напишем еще три дифференциальных уравнения. Присоединяя к ним уравнение (3.6), получим систе­му дифференциальных уравнений для вероятностей со­стояний:

. (3.7)

Это — система четырех линейных дифференциаль­ных уравнений с четырьмя неизвестными функциями p₁ , p₂, p₃ , p₄ - Заметим, что одно из них (любое) можно отбросить, пользуясь тем, что p₁ + p₂ + p₃ + p₄ = 1: вы­разить любую из вероятностей p₁ через другие, это выражение подставить в (2.7), а соответствующее уравнение с производной отбросить [45].

Сформулируем теперь общее правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности какого-то (i-ro) состоя­ния. В правой части — сумма произведений вероятно­стей всех состояний, из которых идут стрелки в дан­ное состояние, на интенсивности соответствующих по­токов событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-ro) состояния.

Чтобы решить уравнения Колмогорова и найти ве­роятности состояний, прежде всего надо задать на­чальные условия. Если мы точно знаем начальное со­стояние системы Si, то в начальный момент (при t = 0) p₁(0)= 1, а все остальные начальные вероятно­сти равны нулю.

Таким образом, уравнения Колмогорова дают воз­можность найти все вероятности состояний как функ­ции времени [46].

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

Предположим, что это условие выполнено и фи­нальные вероятности существуют:

. (3.8)

Финальные вероятности мы будем обозначать теми же буквами р₁, р₂, ..., что и сами вероятности состоя­ний, но разумея под ними уже не переменные величи­ны (функции времени), а постоянные числа. Очевидно, они тоже образуют в сумме единицу:

3.4. Основные элементы теории массового обслуживания

При исследовании операций часто приходится сталкиваться с работой своеобразных систем, называе­мых системами массового обслуживания (СМО), При­мерами таких систем могут служить: телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро, магазины, парикмахерские и т. п. [48].

Каждая СМО состоит из какого-то числа обслужи­вающих единиц (или «приборов»), которые мы будем называть каналами обслуживания. Каналами могут быть: линии связи, рабочие точки, кассиры, продавцы, лифты, автомашины и др. СМО могут быть одноканальными и многоканальными.

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

Процесс работы СМО представляет собой случай­ный процесс с дискретными состояниями и непрерыв­ным временем; состояние СМО меняется скачком в моменты появления каких-то событий (или прихода новой заявки, или окончания обслуживания, или мо­мента, когда заявка, которой надоело ждать, покидает очередь) [49].

Предмет теории массового обслуживания — построе­ние математических моделей, связывающих заданные условия работы СМО (число каналов, их производи­тельность, правила работы, характер потока заявок) с интересующими нас характеристиками — показате­лями эффективности СМО, описывающими, с той или другой точки зрения, ее способность справляться с потоком заявок. В качестве таких показателей (в зави­симости от обстановки и целей исследования) могут применяться разные величины, например: среднее число заявок, обслуживаемых СМО в единицу време­ни; среднее число занятых каналов; среднее число заявок в очереди и среднее время ожидания обслужи­вания; вероятность того, что число заявок в очереди превысит какое-то значение, и т. д.

Математический анализ работы СМО очень облег­чается, если процесс этой работы — марковский. Как было сказано выше, для этого достаточно, чтобы все потоки событий, переводящие систему из состояния в состоя­ние (потоки заявок, потоки «обслуживании»), были простейшими. Если это свойство нарушается, то мате­матическое описание процесса становится гораздо сложнее и довести его до явных, аналитических фор­мул удается лишь в редких случаях. Однако все же аппарат простейшей, марковской теории массового об­служивания может пригодиться для приближенного описания работы СМО даже в тех случаях, когда по­токи событий — не простейшие. Во многих случаях для принятия разумного решения по организации работы СМО вовсе и не требуется точного знания всех ее характеристик — зачастую достаточно и приближенно­го, ориентировочного [50].

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

СМО с очередью подразделяются на разные виды, в зависимости от того, как организована очередь — ограничена она или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания (так называемые «СМО с нетерпеливыми заявками»). При анализе СМО должна учитываться также и «дис­циплина обслуживания» — заявки могут обслуживать­ся либо в порядке поступления (раньше пришла, раньше обслуживается), либо в случайном порядке. Нередко встречается так называемое обслужива­ние с приоритетом — некоторые заявки обслужи­ваются вне очереди. Приоритет может быть как абсолютным — когда заявка с более высоким приоритетом «вытесняет» из-под обслуживания заявку с низшим (например, пришедший в парикмахерскую клиент вы­сокого ранга прогоняет с кресла обыкновенного клиента), так в относительным — когда начатое обслуживание доводится до конца, а заявка с более высоким приоритетом имеет лишь право на лучшее место в очереди [51].

. (3.9)

Финальные вероятности же вероятности можно выразить следующим образом. Если вероятности р₁, р₂, ..., постоянны, то их производные равны нулю. Значит, чтобы найти фи­нальные вероятности, нужно все левые части в урав­нениях Колмогорова положить равными нулю и ре­шить полученную систему уже не дифференциальных, а линейных алгебраических уравнений. Можно и не писать уравнений Колмогорова, а прямо по графу состояний написать систему линейных ал­гебраических уравнений. Если перенести отрицатель­ный член каждого уравнения из правой части в левую, то получим сразу систему уравнений, где слева стоит финальная вероятность данного состояния р₁, умно­женная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в i-e состояние, на вероятности тех состояний, из которых эти потоки исходят [47].

Пользуясь этим правилом, напишем линейные алгебраические уравнения для финальных вероятно­стей состояний системы, граф состояний которой дан на рисунке 2.7:

(3.10)

Эту систему четырех уравнений с четырьмя неизвестными p_0, p_1, p_2, p₃ казалось бы, вполне можно ре­шить. Но вот беда: уравнения (2.10) однородны (не имеют свободного члена) и, значит, определяют неиз­вестные только с точностью до произвольного множи­теля. Воспользуемся нормировочным условием:

(3.11)

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

Кроме этих признаков, СМО делятся на два класса: «открытые» и «замкнутые». В открытой СМО ха­рактеристики потока заявок не зависят от того, в ка­ком состоянии сама СМО (сколько каналов занято). В замкнутой СМО — зависят.

Оптимизация работы СМО может производиться под разными углами зрения: с точки зрения организа­торов (или владельцев) СМО или с точки зрения об­служиваемых клиентов. С первой точки зрения жела­тельно «выжать все, что возможно» из СМО и добиться того, чтобы ее каналы были предельно загружены. С точки зрения клиентов желательно всемерное уменьшение очередей, которые зачастую становятся настоящим «бичом быта», приводя к бессмысленной трате сил и времени и, в конечной итоге, к понижению производительности труда. При решении задач оптимизации в теории массового обслуживания существен­но необходим «системный подход», полное и комплек­сное рассмотрение всех последствий каждого решения. Например, с точки зрения клиентов СМО желательно увеличение числа каналов обслуживания; но ведь ра­боту каждого канала надо оплачивать, что удорожает обслуживание. Построение математической модели поз­воляет решить оптимизационную задачу о разумном числе каналов с учетом всех «за» и «против».

3.5. Схема гибели и размножения

Схема гибели и размножения. Мы знаем, что, имея в распоряжении размеченный граф состояний, можно легко написать уравнения Колмогорова для ве­роятностей состояний, а также написать и решить ал­гебраические уравнения для финальных вероятностей. Для некоторых случаев удается последние уравнения решить заранее, в буквенном виде. В частности, это удается сделать, если граф состояний системы пред­ставляет собой так называемую «схему гибели и раз­множения».

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 3.8.

Рис. 3.8. Граф состояний для схемы гибели и размножения

Особенность этого графа в том, что все состояния системы можно вытя­нуть - в одну цепочку, в которой каждое из средних со­стояний (S₁, S₂, ..., S_n-1) связано прямой и обратной стрелкой с каждым из соседних состояний — правым и левым, а крайние состояния (S₀, S_n) - только с од­ним соседним состоянием. Термин «схема гибели и раз­множения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

Найдем финальные вероятности состояний для схемы гибели и размножения. Предположим, что все потоки событий, переводя­щие систему по стрелкам графа — простейшие (для краткости будем называть и систему S и протекаю­щий в ней процесс — простейшими) [52].

Пользуясь графом на рис. 3.8, составим и решим алгебраические уравнения для финальных вероятно­стей состоянии (их существование вытекает из того, что из каждого состояния можно перейти в каждое другое, и число состояний конечно). Для первого со­стояния S₀ имеем:

. (3.12)

Для второго состояния S₁:

.

В силу (3.12) последнее равенство приводится к виду:

.

Далее, совершенно аналогично:

.

И вообще:

,

где k принимает все значения от 0 до n. Итак, фи­нальные вероятности p_0 ,p_1, ...,p_n удовлетворяют урав­нениям

(3.13)

Кроме того, надо учесть нормировочное условие

. (3.14)

Решим эту систему уравнений. Из первого уравне­ния (3.13) выразим р₁ через р₀: