Сеть массового обслуживания. Системы массового обслуживания Электрические сети как система массового обслуживания

ВНИМАНИЕ!!! Этот раздел будет состоять из нескольких страниц, остальные из которых в данный момент находится в стадии написания. Но уже написанная часть достаточно интересная, поэтому я считаю, что будет полезно уже сейчас сделать её доступной читателям

Давно-давно, когда мы были студентами, этот раздел математики у нас выпил немало студенческой крови. А между тем, этот раздел чрезвычайно интересный!

• Моделирование СМО — для тех, кто уже всё знает.

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

1 Эрл - это занятие одной телефонной линии в течение 1 часа.

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

Я не ставлю себе целью написать целый учебник по ТМО. Такого роду материалов в интернете много. «Изюминкой» моей статьи должен стать интерактивный онлайн-расчётник, который позволит менять исходные данные и смотреть, как будет меняться поведение системы.

Главные понятия Теории:

Исходные данные для рассчётов в ТМО

Основные показатели работы СМО

Какие задачи позволяет решать ТМО?

Вот несколько типичных задач, которые могут быть решены с применением аппарата теории массового обслуживания. На этой странице скоро появится расчётник, который позволит найти решение этих задач.

• Классическая задача. Справочная служба имеет многолинейный телефонный номер, в среднем разговор оператора с абонентом длится 3 минуты, а в течение суток поступает 600 звонков. Сколько нужно иметь телефонных линий (и посадить операторов), чтобы не более 2% звонков оставались без ответа по причине занятости всех линий? А если звонков будет 300 или 1400 в течение суток?

  В терминах ТМО задача звучит так:

  • λ = 25 звонков в час (600 звонков поделить на 24 часа)
  • μ = 20 звонков в час (60 минут поделить на 3)
  • m = 0 (при занятости всех линий звонящий абонент услышит гудки «занято»)
  • Найти n , при условии, что вероятность отказа 2%
• В резервуар водонапорной башни железнодорожной станции непрерывно поступает вода - по кубометру воды за 3 минуты. От водонапорной башни воду получают три гидроколонки для снабжения паровозов водой. На каждую колонку заезжает паровоз в среднем раз в 2 часа и берёт от 10 до 30 кубометров воды (количество воды равномерно распределено в указанном диапазоне). При переполнении резервуара вода вытекает из переливной трубы, чего желательно избегать. Какой объём резервуара требуется водонапорной башне?

  В терминах ТМО задача звучит так:

  • λ = 20 м 3 в час
  • μ = 10 м 3 в час (математическое ожидание разового расхода 20 м
  • n = 2 - количество каналов обслуживания (гидроколонок)
  • Найти m - размер накопителя, т.е. резервуара при условии нулевой вероятности отказа

Пора уже что-то посчитать!

Вычислительные мощности, доступные каждому в XXI веке колоссальны, и позволяют легко и непринуждённо проводить ресурсоёмкий расчёт - имитационное моделирование . В таблице ниже осуществляется моделирование простенькой одиночной системы массового обслуживания. Можно изменять любые из исходных данных и наблюдать, как система отзывается. Можно, например, увеличить интенсивность потока заявок и наблюдать, как система будет «утопать» в заявках (или увеличится поток отказов, если размер накопителя конечен). А вслед за этим можно увеличить количество приборов в системе и наблюдать, как показатели работы придут в норму. В этом расчёте предельная длина очереди равна 1000. Для большинства применений это можно считать бесконечно большим накопителем, однако следует помнить, что если в накопителе окажется больше тысячи заявок, расчёт будет некорректным.

Если интересно, см. математической модели в этой таблице. Даже такая модель позволяет делать интересные наблюдения. Например, можно сравнить несколько СМО с одинаковой производительностью μ×n, обслуживающих одинаковый поток заявок λ, но содержащих различное количество обслуживающих приборов n. В зависимости от того, стремимся ли мы сократить количество обслуживающих аппаратов или же вероятность ожидания, выгодным будет либо наличие одного высокопроизводительного прибора, или десятка низкопроизводительных. Также видно, что среднее арифметическое времени ожидания - величина коварная. Надо будет сделать расчёт медианной величины...

См. также:

• Моделирование системы массового обслуживания — более серьёзный расчёт с более гибко регулируемыми параметрами

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

Определение 1. Пусть имеется некоторая физическая система S , которая с течением времени меняет свое состояние (переходит из одного состояния в другое), причем заранее неизвестным, случайным образом. Тогда мы будем говорить, что в системе S протекает случайный процесс.

Под «физической системой» можно понимать что угодно: техническое устройство, предприятие, живой организм и т.д.

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

Определение 2. Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.

Пусть в настоящий момент t 0 система находится в определенном состоянии S 0 . Мы наблюдаем процесс со стороны и в момент t 0 знаем состояние системы S 0 и всю предысторию процесса, все, что было при t < t 0 . Нас, естественно. Интересует будущее: t > t 0 . Можем ли мы его предугадать? В точности – нет. Наш процесс случайный, следовательно – непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время t система S окажется в состоянии S 1 или сохранит состояние S 0 и т.д.

Если процесс марковский, то предсказывать можно, только учитывая настоящее состояние системы S 0 и забыв о его «предыстории» (поведение системы при t < t 0 ). Само состояние S 0 , разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Т.е. в марковском процессе «будущее зависит от прошлого только через настоящее» .

Пример. Система S – счетчик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент времени t характеризуется показаниями счетчика – числом частиц, пришедших до данного момента. Пусть в момент t 0 счетчик показывает S 0 . Вероятность того, что в в момент t > t 0 счетчик покажет то или другое число частиц S 1 (или менее S 1 ) зависит от S 0 , но не зависит от того, в какие именно моменты приходили частицы до момента t 0 .

На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Например, S ­ – группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» – x и «синих» – y , сохранившихся (не сбитых) к какому-то моменту. В момент t 0 нам известны численности сторон x 0 и y 0 . Нас интересует вероятность того, что в какой-то момент времени t 0 + t численный перевес будет на стороне «красных». От чего зависит эта вероятность? В первую очередь от того, в каком состоянии находится система в данный момент времени t 0 , а не от того, когда и в какой последовательности погибали сбитые до момента времени t 0 самолеты.

В сущности любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», перенести в «настоящее». Например, пусть речь идет о работе какого-то технического устройства; в какой-то момент времени t 0 оно ещё исправно, и нас интересует вероятность того, что оно проработает ещё время t . Если за настоящее время считать просто «система исправна», то процесс безусловно не марковский, потому что вероятность, что она не откажет за время t , зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт. Если оба эти параметра (общее время работы и время после ремонта) включить в настоящее состояние системы. То процесс можно будет считать марковским.

Определение 3. Процесс называется с дискретными состояниями, если его возможные состояния S 1 , S 2 ,... можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит «скачком», практически мгновенно.

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

Мы будем рассматривать только процессы с дискретными состояниями.

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

Возможные состояния системы:

S 0 – оба узла исправны;

S 1 – первый узел ремонтируется, второй исправен;

S 2 – второй узел ремонтируется, первый исправен;

S 3 – оба узла ремонтируются.

Стрелка, направленная из S 0 в S 1 означает момент отказа первого узла и т. д. На рисунке нет стрелки из состояния S 0 в состояние S 3 , поскольку вероятность того, что два прибора откажут одновременно, стремится к нулю.

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

Важнейшей характеристикой потока событий является его интенсивность l – среднее число событий, приходящееся на единицу времени. интенсивность потока может быть постоянной (l = const ), так и переменной, зависящей от времени. Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, а поток автомашин с 14-ти до 15-ти часов дня можно считать постоянным.

Определение 6. Поток событий называется регулярным, если события следуют одно за другим через определенные, равные промежутки времени.

Определение 7. Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность l стационарного потока должна быть постоянной. Это отнюдь не означает, что фактическое число событий, появляющееся в единицу времени, постоянно, – нет, поток неизбежно (если только он не регулярный) имеет какие-то случайные сгущения и разрежения. Важно, что для стационарного потока эти сгущения и разрежения не носят закономерного характера: на один участок длины 1 может попасть больше, а на другой – меньше событий, но среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.

Например, поток вызовов, поступающих на АТС между 13 и 14 часами. Практически стационарен, но тот же поток в течение суток уже не стационарен.

Определение 8. Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t 1 и t 2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. По сути это означает, что события, образующие поток, появляются в те или другие моменты независимо друг от друга, вызванные каждое своими собственными причинами.

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

Определение 9. Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами сразу.

Например поток клиентов к зубному врачу – обычно ординарный. Поток поездов, подходящих к станции – ординарен, а поток вагонов – неординарен.

Определение 10. Поток событий называется простейшим (или стационарным Пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия, а сам входной поток распределен по закону Пуассона ().

Для описания случайного процесса, протекающего в системе с дискретными состояниями S 1 , S 2 , ..., S n часто пользуются вероятностями состояний p 1 ( t ),..., p n ( t ) , где p k ( t ) – вероятность того, что в момент времени t система находится в состоянии S k . Вероятности p k ( t ) удовлетворяют условию: .

Если процесс, протекающий в системе с дискретными состояниями и непрерывным временем является марковским, то для вероятностей состояний p 1 ( t ), ..., p n ( t ) можно составить систему линейных дифференциальных уравнений. При составлении этих уравнений удобно пользоваться графом состояний системы, на котором против каждой стрелки, ведущей из состояния в состояние, проставлена интенсивность потока событий, переводящего систему по стрелке (рис.4.2):

Начальные условия для интегрирования такой системы отражают состояние системы в начальный момент времени. Если, например, система при t =0 была в состоянии S k , то . Эти уравнения можно решать аналитически, но это удобно только тогда, когда число уравнений не превышает двух (иногда трех). В случае, когда уравнений оказывается больше, применяют численные методы.

Что будет происходить с вероятностями состояний при ? Будут ли p 1 ( t ), ..., p n ( t ) стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний: . p i – среднее относительное время пребывания системы в i -ом состоянии.

Как найти финальные вероятности? Поскольку все p i = const , то производные, стоящие в левой части каждого уравнения равны нулю. Т.о. мы получили систему линейных алгебраических уравнений. Поскольку ни одно уравнение в этой системе не имеет свободного члена, то система является вырожденной (т.е. все переменные будут выражены через одну). Чтобы этот избежать, необходимо воспользоваться нормировочным условием (), при этом любое уравнение можно отбросить.

Классификация систем массового обслуживания

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

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

Также СМО делятся на системы с приоритетами и без них. В свою очередь системы с приоритетом делятся на СМО с прерыванием и без.

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

Рис.4.3

Найдем вероятности p k :

Для состояния S 0 : , отсюда ;

Для состояния S 1 n : , подставляем полученное значение для p 1 : . Аналогично, .

Вероятность p 0 найдем из нормировочного условия :

, – геометрическая прогрессия, при r <1 сходится. – вероятность того, что нет заявок.

– вероятность того, что прибор занят обслуживанием заявки. r = l / m – мера загрузки одноканальной СМО.

В текущий момент времени в системе может быть 0, 1, 2, ..., k , ... заявок с вероятностями p 0 , p 1 p 2 , ... Математическое ожидание количества заявок:

учитывая, что , получим:

Средняя длина очереди равна разности между средним числом заявок в системе и средним числом заявок, находящихся под обслуживанием: .

Формулы Литтла

Первая формула Литтла позволяет определить время реакции СМО (время пребывания заявки в системе).

Пусть X ( t ) – число заявок, поступивших в СМО до момента времени t , Y ( t ) – покинувших СМО до t . Обе функции случайны и увеличиваются скачком на единицу в моменты прихода и ухода заявок. Тогда число заявок в системе в момент времени t можно определить как: . Рассмотрим очень большой промежуток времени T и вычислим среднее число заявок в системе:

.

Интеграл равен площади ступенчатой фигуры, ограниченной функциями X ( t ) и Y ( t ) , эта сумма состоит из прямоугольников, ширина которых равна единице, а длина – времени пребывания i -ой заявки в системе. Сумма распространяется на все заявки, поступившие в систему за время T . Правую часть домножим и разделим на l : . T l – среднее количество заявок, пришедших за время T . Поделив сумму всех времен t i на среднее число заявок, получим среднее время пребывания заявки в системе: .

Совершенно аналогично можно получить среднее время пребывания заявки в очереди: .

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

Рис.4.5

Найдем вероятности p k :

Для состояния S 0 : ;

Для состояний S 1 – S n : ;

Для S n +1 : ; ...

Для S n+s-1 : ;

Для S n+s : .

Из первых n +1 уравнений получаем:

Из последнего уравнения выражаем: и подставляем в предпоследнее: , . Тогда .

Продолжая аналогию: .

Теперь найдем p 0 , подставив полученные выражения в нормировочное условие (): . Отсюда .

Показатели эффективности СМО

– Вероятность потери требования в СМО. Особенно часто ею пользуются при исследовании военных вопросов. Например, при оценке эффективности противовоздушной обороны объекта она характеризует вероятность прорыва воздушных целей к объекту. Применительно к СМО с потерями она равна вероятности занятости обслуживанием требований всех n приборов системы. Чаще всего эту вероятность обозначают p n или p отк .

– Вероятность того, что обслуживанием требований в системе занято k приборов, равна p k .

– Среднее число занятых приборов: характеризует степень загрузки обслуживающей системы.

– Среднее число свободных от обслуживания приборов:.

– Коэффициент простоя приборов: .

– Коэффициент занятости оборудования: .

– Средняя длина очереди: , p k - вероятность того, что в системе находится k требований.

– Среднее число заявок, находящихся в сфере обслуживания: .

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

Кроме перечисленных критериев при оценке эффективности СМО могут быть использованы стоимостные показатели:

q об – стоимость обслуживания каждого требования в системе;

q ож – стоимость потерь, связанных с простаиванием заявок в очереди в единицу времени;

q у – убытки, связанные с уходом из системы заявки;

q k – стоимость эксплуатации каждого прибора в единицу времени;

q k пр – стоимость простоя единицы времени k -го прибора системы.

При выборе оптимальных параметров СМО по экономическим показателям можно использовать функцию стоимости потерь в системе (для СМО с ожиданием): T – интервал времени.

Для СМО с отказами: .

Для смешанных: .

Критерий экономической эффективности СМО: , с – экономический эффект, получаемый при обслуживании каждой заявки.

СМО замкнутого типа

Пример. С1, С2, С3 – станки; НЦ – центральный накопитель; B – манипулятор. Транспортная тележка (манипулятор) транспортирует отработанную деталь от станка к накопителю и укладывает ее там, забирает новую деталь (заготовку), транспортирует ее к станку и устанавливает в рабочую позицию для зажима. Во время всего периода, необходимого для выгрузки–загрузки, станок простаивает. Время T з смены заготовки и есть время обслуживания.

Интенсивность обслуживания станков определяется как , – среднее время обслуживания станка, которое вычисляется как , где n – число заявок. Интенсивность подачи станком заявки на обслуживание определяется как (где – среднеее время обработки детали станком).

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

В станочной системе число заявок на обслуживание может быть равно 0, 1, 2, ... m , где m – общее число станков. Тогда возможны следующие состояния:

S 0 – все станки работают, манипулятор стоит.

S 1 – все станки, кроме одного, работают, манипулятор обслуживает станок, от которого поступила заявка на смену заготовок.

S 2 – работают m -2 станка, на одном станке идет смена заготовки, другой ожидает.

S 3 – работают m -2 станка, один станок обслуживается манипулятором, два станка ожидают в очереди.

S m – все станки стоят, один обслуживается манипулятором, остальные ожидают очереди исполнения заказа.

Рис.4.6.

Вероятность перехода в состояние S k из одного из возможных состояний S 1 , S 2 , ... S m зависит от случайного поступления заявок на обслуживание и вычисляется как:

p 0 – вероятность того, что все станки работают.

Манипулятор работает при состояниях системы от S 1 до S m ­ . Тогда вероятность его загрузки равна: .

Число станков, находящихся в очереди связано с состояниями S 2 , – S m , при этом один станок обслуживается, а (k -1) – ожидают. Тогда, среднее число станков в очереди: .

Коэффициент простоя одного станка (из-за ожидания при многостаночном обслуживании): .

Среднее использование одного станка:

Применение метода Монте-Карло для решения задач,

связанных с теорией массового обслуживания

Для того, чтобы описать поток однородных событий, достаточно знать закон распределения моментов времени t 1 , t 2 , ..., t k , ..., в которые поступают события.

Для удобства дальнейших рассмотрений целесообразно от величин t 1 , t 2 , ..., перейти к случайным величинам z 1 , z 2 , ..., z m , ... , таким образом, что:

Случайные величины z k являются длинами интервалов времени между последовательными моментами t k .

Совокупность случайных величин z i считается заданной, если определена совместная функция распределения: . Обычно рассматриваются только непрерывные случайные величины z k , поэтому часто пользуются соответствующей функцией плотности f ( z 1 , z 2 ,..., z k ) .

Обычно в теории СМО рассматриваются потоки однородных событий без последействия, для которых случайные величины z k независимы. Поэтому . Функции f i ( z i ) при i >1 представляют собой условные функции плотности при условии, что в начальный момент интервала z k ( i >1) поступила заявка. В отличие от этого функция f 1 ( z 1 ) является безусловной функцией плотности, т.к. относительно появления или непоявления заявки в начальный момент времени не делается никаких предположений.

Широкое применение имеют так называемые стационарные потоки, для которых вероятностный режим их во времени не изменяется (т.е. вероятность появления k заявок за промежуток времени (t 0 , t 0 + t ) не зависит от t 0 , а зависит только от t и k ). Для стационарных потоков без последействия имеют место соотношения:

где l – плотность стационарного потока.

Поступившая в систему заявка может занимать только свободные линии. Относительно порядка занятия линий могут быть сделаны различные предположения:

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

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

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

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

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

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

в) заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями. Если в момент освобождения линии имеется m заявок в очереди, то в простейшем случае вероятность выбрать для обслуживания некоторую определенную заявку может быть принята равной q =1/ m . В более сложных случаях вероятности q 1 , q 2 ,..., q m считаются зависящими от времени пребывания заявки в системе, времени, остающегося до получения отказа и других параметров.

· Для решения ряда прикладных задач оказывается необходимым учитывать такой важный фактор, как надежность элементов обслуживающей системы. Будем предполагать, что с точки зрения надежности каждая линия в данный момент времени может быть либо исправной, либо неисправной. Надежность линии определяется вероятностью безотказной работы R = R ( t ) , задаваемой как функция времени. Будем также предполагать, что линия, вышедшая из строя по причине неполной надежности, может быть введена в строй (отремонтирована), для чего требуется затратить время t p . Величину t p будем считать случайной величиной с заданным законом распределения.

Относительно судьбы заявки, при обслуживании которой линия выходит из строя, могут быть сделаны различные предположения: заявка получает отказ; заявка остается в системе (с общим временем пребывания в системе не более t n ) как претендент на обслуживание вне очереди; заявка поступает в очередь и обслуживается на общих основаниях и т.д.

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

Метод статистических испытаний позволяет более полно, по сравнению с асимптотическими формулами, исследовать зависимость качества обслуживания от характеристик потока заявок и параметров обслуживающей системы.

Это достигается благодаря двум обстоятельствам. Во-первых, при решении задач теории массового обслуживания методом статистических испытаний может быть использована более обширная информация о процессе, чем это обычно удается сделать, применяя аналитические методы.

С другой стороны, значения показателей качества обслуживания, получаемые из асимптотических формул, строго говоря, относятся к моментам времени, достаточно удаленным от начала процесса. Реально, для моментов времени, близких к началу процесса, когда еще не наступил стационарный режим, значения показателей качества обслуживания в общем случае существенно отличаются от асимптотических значений. Метод статистических испытаний позволяет достаточно обстоятельно изучать переходные режимы.

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

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

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

· Структура алгоритма, моделирующего

процесс обслуживания заявок

Рассмотрим однофазную СМО, имеющую n линий, на которые поступают заявки в случайные моменты времени t i . Если вмомент поступления заявки оказываются в наличии свободные линии (их число n св ), заявка занимает одну из них на время t p . В противном случае заявка находится в системе до момента t n , ожидая обслудивания. В т t чение времени ожидания некоторые линии могут освободиться (их число m ), и в этом случае будет возможность обслужить заявку. Если до момента времени t n ни одна из линий не освобождается (m =0 ), заявка получает отказ.

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

Для исследования качества обслуживания заявок предусматривается N * кратное моделирование процесса функционирования системы в интервале (0, T ) . В процессе моделирования число обследованных реализаций обозначим через N .

Алгоритм:

1. Определяется момент t i поступления очередной заявки в систему.

2. Если t i < T , то переход на шаг 3, иначе – на шаг 11.

3. Проверка возможности обслужить поступившую заявку: если n св >0 , то переход на шаг 4, иначе – на шаг 12. (Значение времени поступления заявки t i сравнивается с t осв для всех линий, т.о. выявляются свободные линии.)

4.Если n св >1 , то переход на шаг 5, иначе – на шаг 6.

5. Выбирается номер свободной линии по специальным правилам.

6. Назначается выбранная линия.

7. Проверка: имеет ли место срыв обслуживания по причине недостаточной надежности? Если да, то переход на шаг 8, иначе – на шаг 10.

8. Определение времени t рем ремонта линии, вышедшей из строя (t рем имеет определенный закон распределения).

9. N отк = N отк +1 . Переход на шаг 1.

10. Определение времени занятости t з линии, которая назначена обслуживать заявку (некая случайная величина с определенным законом распределения) и времени освобождения линии: t осв = t i + t з . Переход к очередной заявке (шаг 1).

11. Проверка: если N < N * , то N = N +1 и переход на шаг 1, иначе – обработка результатов опыта и конец.

12. Определить:

А) времени t n пребывания заявки в системе;

Б) число освободившихся каналов m за время t n .

13. Если m >0 , то переход на шаг 14, иначе – на шаг 9.

14. Если m >1 , то переход на шаг 15, иначе – на шаг 6.

15. Выбирается определенная линия в соответствии с принятыми правилами и переход на шаг 6.

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

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

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

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

где А – процесс прибытия; В – процесс обслуживания; С – число серверов (узлов); К – максимальный размер очереди (по умолчанию – ∞);

in – число клиентов (по умолчанию – да); z – схема работы буфера (по умолчанию FIFO).

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

Наиболее распространенными схемами работы буферов являются

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

Среднее значение длины очереди Q при заданной средней входной частоте сообщений λ и среднем времени ожидания W определяется на основе теоремы Литла (1961) :

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

(3.3)

Пусть N – число клиентов в системе, Q – число клиентов в очереди и пусть вероятность того, что входящий клиент обнаружит j других клиентов, равна:

Тогда среднее время ожидания:

где σ – среднеквадратичное отклонение для распределения времени обслуживания.

Для варианта очереди(Η – функция

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

Для варианта очереди M/D/ 1 время обслуживания постоянно, а среднее время ожидания составляет:

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

где

(3.9)

где, аравно вероятности того, что сообщение отправителя /" направлено получателю. Требование стабильности требует, чтобы. Для бо́льших n это приводит к

Работа сети Ethernet характеризуется рядом параметров, к числу которых относятся вероятность захвата канала и эффективность . Первый параметр определяется по выражению

где Ρ – вероятность того, что ровно одна станция попытается передать кадр в течение такта и захватить канал; Q – число станций, пытающихся захватить канал для передачи кадра данных.

Эффективность LAN Ethernet определяется следующим образом. Общее время работы сети Ethernet делится между интервалами передачи и интервалами конкуренции. Для передачи кадра данных требуется L/C секунд, где L – длина кадра в битах, С – скорость передачи данных в бит/сек. Среднее время Τ , необходимое на захват канала, равно:

где W – среднее число тактов, прошедших в интервале конкуренции, пока станция не захватит канал для передачи кадра данных; В – длительность такта или время до обнаружения конфликта после начала передачи кадра.

Среднее число тактов W рассчитывается следующим образом:

С учетом введенных показателей эффективность Ε работы локальной сети Ethernet определяется следующим образом:

Для моделирования ЛВС наиболее часто используются следующие типы СМО:

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

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

Открытой называется есть массового обслуживания, состоящая из Μ узлов, причем хотя бы в один из узлов сети поступает извне входящий поток заявок и имеется сток заявок из сети. Для открытых сетей характерно то, что интенсивность поступления заявок в сеть не зависит от состояния сети, т. е. от числа заявок, уже поступивших в сеть. Открытые сети используются для моделирования ЛВС, работающих в неоперативном режиме. Каждая заявка поступает на вход соответствующего узла коммутации, где определяется место ее обработки. Затем заявка передается на "свой" сервер или по каналу связи – на "соседний", где обрабатывается, после чего возвращается к источнику и покидает сеть .

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

Различают простой и сложный режимы работы диалоговых абонентов. В простом режиме абоненты не производят никаких действий, кроме посылки заданий в ЛВС и обдумывания полученного ответа .

Абоненты с терминалов посылают запросы, которые по каналам связи поступают на узлы коммутации, а оттуда – на обработку на "свой" или "соседний" сервер. Дальнейшая обработка осуществляется так же, как в открытой сети .

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

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

Алгоритм работы сети для диалоговых абонентов аналогичен алгоритму работы замкнутой сети, а алгоритм работы сети для неоперативных абонентов – алгоритму работы открытой сети.

Различают экспоненциальные и неэкспоненциальные модели ЛВС. Экспоненциальные модели основаны на предположении о том, что потоки заявок, поступающие в ЛВС, являются пуассоновскими, а время обслуживания в узлах ЛВС имеет экспоненциальное распределение.

Для таких сетей получены точные методы для определения их характеристик; трудоемкость получения решения зависит в основном от размерности сети .

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

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

При этом не требуется точного знания функций распределения случайных величин, связанных с данной СМО (интервалов между поступлениями заявок временем обслуживания в приборах), а достаточно только знание первого (математического ожидания) и второго (дисперсии или квадрата коэффициента вариации – ΚΚΒ) моментов этих величин .

Применение диффузионной аппроксимации при анализе ЛВС основано на следующем:

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

Постановка задачи анализа ЛВС при этом примет следующий вид. Дано:

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

Ограничения могут быть следующими:

Иногда представляет интерес определение такого показателя, как максимальное время задержки заявки каждого типа в ЛВС. Максимальное время – это такое время, превышение которого допустимо лишь для некоторого, наперед заданного процента заявок каждого типа. Для определения максимального времени используется методика, основанная на аппроксимации функции распределения времени задержки в сети эрланговским или гипсрэкспонснциальным распределением, при этом необходимо задавать долю (процент) заявок, для которых рассчитывается максимальное время.

Рассмотренный в предыдущей лекции марковский случайный процесс с дискретными состояниями и непрерывным временем имеет место в системах массового обслуживания (СМО).

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

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

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

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

Рис. 1

1. Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
2. Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:

• принимает заявки;
• формирует очередь, если все каналы заняты;
• направляет их к каналам обслуживания, если есть свободные;
• дает заявкам отказ (по различным причинам);
• принимает информацию от узла обслуживания о свободных каналах;
• следит за временем работы системы.

1. Очередь – накопитель заявок. Очередь может отсутствовать.
2. Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
3. Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).

Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:

терминатор – уничтожитель трансактов;

склад – накопитель ресурсов и готовой продукции;

счет бухгалтерского учета – для выполнения операций типа «проводка»;

менеджер – распорядитель ресурсов;

Классификация СМО

Первое деление (по наличию очередей):

• СМО с отказами;
• СМО с очередью.

В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.

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

СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь, – ограничена или не ограничена . Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».

Итак, например, рассматриваются следующие СМО:

• СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
• СМО с обслуживанием с приоритетом, т. е. некоторые заявки обслуживаются вне очереди и т. д.

Типы ограничения очереди могут быть комбинированными.

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

Естественно, поток заявок, порожденный самой системой, будет зависеть от системы и ее состояния.

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

Пример замкнутой системы: выдача кассиром зарплаты на предприятии.

По количеству каналов СМО делятся на:

• одноканальные;
• многоканальные.

Характеристики системы массового обслуживания

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

• входной поток поступающих требований или заявок на обслуживание;
• дисциплина очереди;
• механизм обслуживания.

Входной поток требований

Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание, и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (количество таких требований в каждом очередном поступлении ). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.

А i – время поступления между требованиями – независимые одинаково распределенные случайные величины;

E(A) – среднее (МО) время поступления;

λ=1/E(A) – интенсивность поступления требований;

Характеристики входного потока:

1. Вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание.
2. Количество требований в каждом очередном поступлении для групповых потоков.

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

Очередь – совокупность требований, ожидающих обслуживания.

Очередь имеет имя.

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

• первым пришел – первый обслуживаешься;

first in first out (FIFO)

самый распространенный тип очереди.

Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.

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

Вы как программисты должны уметь делать списки двусторонние, односторонние.

Действия со списком:

• вставить в хвост;
• взять из начала;
• удалить из списка по истечении времени ожидания.
• пришел последним - обслуживаешься первым LIFO (обойма для патронов, тупик на железнодорожной станции, зашел в набитый вагон).

Структура, известная как СТЕК. Может быть описан структурой массив или список;

• случайный отбор заявок;
• отбор заявок по критерию приоритетности.

Каждая заявка характеризуется помимо прочего уровнем приоритета и при поступлении помещается не в хвост очереди, а в конец своей приоритетной группы. Диспетчер осуществляет сортировку по приоритету.

Характеристики очереди

• ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
• длина очереди.

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

Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся:

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

Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».

S i – время обслуживания i -го требования;

E(S) – среднее время обслуживания;

μ=1/E(S) – скорость обслуживания требований.

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

Коэффициент использования СМО

N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.

ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.

Структура обслуживающей системы

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

Пример. Кассы в магазине.

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

Пример. Медицинская комиссия.

Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.

Итак, функциональные возможности любой системы массового обслуживания определяются следующими основными факторами :

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

Основные критерии эффективности функционирования СМО

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

• вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
• вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);

Очевидно, что Р обсл + P отк =1.

Потоки, задержки, обслуживание. Формула Поллачека–Хинчина

Задержка – один из критериев обслуживания СМО, время проведенное заявкой в ожидании обслуживания.

D i – задержка в очереди требования i ;

W i =D i +S i – время нахождения в системе требования i .

(с вероятностью 1) – установившаяся средняя задержка требования в очереди;

(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).

Q(t) – число требований в очереди в момент времени t;

L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.

Тогда показатели (если существуют)

(с вероятностью 1) – установившееся среднее по времени число требований в очереди;

(с вероятностью 1) – установившееся среднее по времени число требований в системе.

Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.

Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.

К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения

Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.

Кроме этого можно также говорить о таких характеристиках, как:

• абсолютная пропускная способность системы – А=Р обсл *λ;
• относительная пропускная способность системы –

Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:

.

В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).

Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.

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

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

1. ИССЛЕДОВАНИЕ ОСОБЕННОСТЕЙ МУЛЬТИМЕДИЙНОГО ВИДЕОТРАФИКА ПРИ ЕГО ПЕРЕДАЧЕ ПО ПАКЕТНЫМ СЕТЯМ

1.1. Основные типы мультимедийного трафика реального времени.

1.2. Общий подход к описанию мультимедийного трафика реального времени.

1.3. Параметры качества обслуживания при передаче мультимедийного трафика в пакетных сетях передачи данных.

1.4. Технологии и стандарты кодирования и передачи видеотрафика.

1.5. Аппроксимация видеотрафика марковскими процессами.

2. АНАЛИЗ И РАЗРАБОТКА МЕТОДОВ МОДЕЛИРОВАНИЯ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ ПЕРЕДАЧИ МУЛЬТИМЕДИЙНЫХ ВИДЕОТРАФИКОВ.

2.1. Анализ классов математических моделей для исследования процессов передачи мультимедийного видеотрафика в пакетных сетях.

2.2. Сети массового обслуживания как модели телекоммуникационных систем.

2.2.1. Параметры сетей массового обслуживания.

2.2.2. Характеристики стационарного режима функционирования сети массового обслуживания.

2.3. Расчет замкнутых неоднородных сетей массового обслуживания большой размерности.

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

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

3. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ПЕРЕДАЧИ ВИДЕОТРАФИКА В

ПАКЕТНЫХ СЕТЯХ ПЕРЕДАЧИ ДАННЫХ.

3.1. Общие принципы организации мультимедийных сервисов в пакетных телекоммуникационных сетях.

3.2. Концептуальная модель задержек передачи видеотрафика.

3.3. Математическая модель задержек передачи видеопотока.

3.4. Вероятностно- временные характеристики модели оценки задержек передачи видеопотока.

3.5. Результаты моделирования.

4. ОЦЕНКА ДЖИТТЕРА ПЕРЕДАЧИ ВИДЕОПОТОКОВ В ПАКЕТНЫХ

СЕТЯХ ПЕРЕДАЧИ ДАННЫХ.

4.1. Общая постановка задачи.

4.2. Оценка дисперсии задержки передачи видеотрафика в пакетной сети, достоверность результатов.

Рекомендованный список диссертаций

• Влияние самоподобности речевого трафика на качество обслуживания в телекоммуникационных сетях 2005 год, кандидат технических наук Осин, Андрей Владимирович

• Аппроксимативные методы и модели массового обслуживания для исследования компьютерных сетей 2011 год, доктор технических наук Бахарева, Надежда Федоровна

• Разработка модели и анализ характеристик обслуживания видеоинформации в узле сети АТМ 2002 год, кандидат технических наук Молчанов, Дмитрий Александрович

• Влияние мультифрактальных свойств GPRS/EDGE трафика на характеристики обслуживания мобильных телекоммуникационных сетей 2009 год, кандидат технических наук Матвеев, Сергей Борисович

• Методика исследования информационных процессов в телекоммуникационных системах на железнодорожном транспорте 2006 год, кандидат технических наук Толстошеин, Андрей Викторович

Введение диссертации (часть автореферата) на тему «Применение сетей массового обслуживания для исследования процессов передачи видеопотоков в пакетных сетях»

Похожие диссертационные работы по специальности «Системы, сети и устройства телекоммуникаций», 05.12.13 шифр ВАК

• Исследование фрактальных свойств потоков трафика реального времени и оценка их влияния на характеристики обслуживания телекоммуникационных сетей 2007 год, кандидат технических наук Урьев, Григорий Анатольевич

• Разработка метода повышения пропускной способности уровня абонентского доступа 2009 год, кандидат технических наук Булатов, Сергей Валерьевич

• Влияние помехоустойчивости широкополосных систем беспроводного доступа IEEE 802.16 на качество передачи потокового трафика 2010 год, кандидат технических наук Арсеньев, Андрей Владимирович

• Пути построения и методы анализа гибридных мультисервисных спутниковых систем связи 2002 год, кандидат технических наук Сирухи Джозеф Вере

• Сетевая информационная система с виртуальными подсетями повышенной производительности 2009 год, кандидат технических наук Хворов, Алексей Александрович

Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Аль-Днебат Саид Али

Список литературы диссертационного исследования кандидат технических наук Аль-Днебат Саид Али, 2004 год

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