Постоянная и динамическая коммутация
Как сети с коммутацией пакетов , так и сети с коммутацией каналов можно разделить на два класса:
- сети с динамической коммутацией ;
- сети с постоянной коммутацией .
В сетях с динамической коммутацией :
- разрешается устанавливать соединение по инициативе пользователя сети;
- коммутация выполняется только на время сеанса связи, а затем (по инициативе одного из пользователей) разрывается;
- в общем случае пользователь сети может соединиться с любым другим пользователем сети;
- время соединения между парой пользователей при динамической коммутации составляет от нескольких секунд до нескольких часов и завершается после выполнения определенной работы - передачи файла, просмотра страницы текста или изображения и т.п.
Примерами сетей, поддерживающих режим динамической коммутации , являются телефонные сети общего пользования, локальные сети , сети TCP/IP .
Сеть , работающая в режиме постоянной коммутации :
- разрешает паре пользователей заказать соединение на длительный период времени;
- соединение устанавливается не пользователями, а персоналом, обслуживающим сеть;
- период, на который устанавливается постоянная коммутация , составляет обычно несколько месяцев;
- режим постоянной (permanent ) коммутации в сетях с коммутацией каналов часто называется сервисом выделенных (dedicated ) или арендуемых (leased ) каналов;
- в том случае, когда постоянное соединение через сеть коммутаторов устанавливается с помощью автоматических процедур, инициированных обслуживающим персоналом, его часто называют полупостоянным (semi-permanent) соединением , в отличие от режима ручного конфигурирования каждого коммутатора .
Наиболее популярными сетями, работающими в режиме постоянной коммутации , сегодня являются сети технологии SDH , на основе которых строятся выделенные каналы связи с пропускной способностью в несколько гигабит в секунду.
Некоторые типы сетей поддерживают оба режима работы. Например, сети X.25 и ATM могут предоставлять пользователю возможность динамически связаться с любым другим пользователем сети и в то же время отправлять данные по постоянному соединению определенному абоненту.
Пропускная способность сетей с коммутацией пакетов
Одним из отличий метода коммутации пакетов от метода коммутации каналов является неопределенность пропускной способности соединения между двумя абонентами. В случае коммутации каналов после образования составного канала пропускная способность сети при передаче данных между конечными узлами известна - это пропускная способность - канала . Данные после задержки, связанной с установлением канала , начинают передаваться на максимальной для канала скорости (рис. 7.1). Время передачи сообщения в сети с коммутацией каналов Т к.к. равно сумме задержки распространения сигнала по линии связи и задержки передачи сообщения. Задержка распространения сигнала зависит от скорости распространения электромагнитных волн в конкретной физической среде, которая колеблется от 0,6 до 0,9 скорости света в вакууме. Время передачи сообщения равно V/C, где V - объем сообщения в битах, а C - пропускная способность - канала в битах в секунду.
В сети с коммутацией пакетов картина совсем иная.
Рис.
7.1.
Процедура установления соединения в этих сетях, если она используется, занимает примерно такое же время, как и в сетях с коммутацией каналов , поэтому будем сравнивать только время передачи данных.
Рис. 7.2.
На рис. 7.2 показан пример передачи данных в сети с коммутацией пакетов . Предполагается, что по сети передается сообщение того же объема, что и сообщение, передаваемое на рис. 7.1 однако оно разделено на пакеты , каждый из которых снабжен заголовком. Время передачи сообщения в сети с коммутацией пакетов обозначено на рисунке Т к.п. При передаче этого разбитого на пакеты сообщения по сети с коммутацией пакетов возникают дополнительные задержки. Во-первых, это задержки в источнике передачи, который, помимо передачи собственно сообщения, тратит дополнительное время на передачу заголовков t п.з. , к тому же добавляются задержки t инт, вызванные интервалами между передачей каждого следующего пакета (это время уходит на формирование очередного пакета стеком протоколов ).
Во-вторых, дополнительное время тратится в каждом коммутаторе . Здесь задержки складываются из времени буферизации - пакета t б.п. (коммутатор не может начать передачу пакета , не приняв его полностью в свой буфер ) и времени коммутации t к. Время буферизации равно времени приема пакета с битовой скоростью протокола. Время коммутации складывается из времени ожидания пакета в очереди и времени перемещения пакета в выходной порт . Если время перемещения пакета фиксировано и, как правило, невелико (от нескольких микросекунд до нескольких десятков микросекунд), то время ожидания пакета в очереди колеблется в очень широких пределах и заранее неизвестно, так как зависит от текущей загрузки сети.
Проведем грубую оценку задержки при передаче данных в сетях с коммутацией пакетов по сравнению с сетями с коммутацией каналов на простейшем примере. Пусть тестовое сообщение, которое нужно передать в обоих видах сетей, имеет объем 200 Кбайт. Отправитель находится от получателя на расстоянии 5000 км. Пропускная способность линий связи составляет 2 Мбит/c.
Время передачи данных по сети с коммутацией каналов складывается из времени распространения сигнала, которое для расстояния 5000 км можно оценить примерно в 25 мс (принимая скорость распространения сигнала равной 2/3 скорости света), и времени передачи сообщения, которое при пропускной способности 2 Мбит/c и длине сообщения 200 Кбайт равно примерно 800 мс. При расчете корректное значение К (2 10), равное 1024, округлялось до 1000, аналогично значение М (2 20), равное 1048576, округлялось до 1000000. Таким образом, передача данных оценивается в 825 мс.
Ясно, что при передаче этого сообщения по сети с коммутацией пакетов , обладающей такой же суммарной длиной и пропускной способностью - каналов , пролегающих от отправителя к получателю, время распространения сигнала и время передачи данных будут такими же - 825 мс. Однако из-за задержек в промежуточных узлах общее время передачи данных увеличится. Давайте оценим, на сколько возрастет это время. Будем считать, что путь от отправителя до получателя пролегает через 10 коммутаторов . Пусть исходное сообщение разбивается на пакеты в 1 Кбайт, всего 200 пакетов . Вначале оценим задержку, которая возникает в исходном узле. Предположим, что доля служебной информации, размещенной в заголовках пакетов, по отношению к общему объему сообщения составляет 10%. Следовательно, дополнительная задержка, связанная с передачей заголовков - пакетов , составляет 10% от времени передачи целого сообщения, то есть 80 мс. Если принять интервал между отправкой пакетов равным 1 мс, то дополнительные потери за счет интервалов составят 200 мс. Таким образом, в исходном узле из-за пакетирования сообщения при передаче возникла дополнительная задержка в 280 мс.
Каждый из 10 коммутаторов вносит задержку коммутации , которая может составлять от долей до тысяч миллисекунд. В данном примере будем считать, что на коммутацию в среднем тратится 20 мс. Кроме того, при прохождении сообщений через коммутатор возникает задержка буферизации пакета. Эта задержка при величине пакета 1 Кбайт и пропускной способности линии 2 Мбит/c равна 4 мс. Общая задержка, вносимая 10 коммутаторами , составляет примерно 240 мс. В результате дополнительная задержка, созданная сетью с коммутацией пакетов , составила 520 мс. Учитывая, что вся приложение делит процессор .
На эффективность работы сети влияют размеры пакетов , которые передает сеть . Слишком большие размеры пакетов приближают сеть с коммутацией пакетов к сети с коммутацией каналов , поэтому эффективность сети падает. Кроме того, при большом размере пакетов увеличивается время буферизации на каждом коммутаторе . Слишком маленькие пакеты заметно увеличивают долю служебной информации, так как каждый пакет содержит заголовок фиксированной длины, а количество пакетов , на которые разбиваются сообщения, при уменьшении размера пакета будет резко расти. Существует некоторая "золотая середина", когда обеспечивается максимальная эффективность работы сети, однако это соотношение трудно определить точно, так как оно зависит от многих факторов, в том числе изменяющихся в процессе работы сети. Поэтому разработчики протоколов для сетей с коммутацией пакетов выбирают пределы, в которых может находиться размер пакета , а точнее его поле данных, так как заголовок, как правило, имеет фиксированную длину. Обычно нижний предел поля данных выбирается равным нулю, что дает возможность передавать служебные пакеты без пользовательских данных, а верхний предел не превышает 4 Кбайт. Приложения при передаче данных пытаются занять максимальный размер поля данных, чтобы быстрее выполнить обмен, а небольшие пакеты обычно используются для коротких служебных сообщений, содержащих, к примеру, подтверждение доставки пакета .
При выборе размера пакета необходимо также учитывать интенсивность битовых ошибок канала . На ненадежных каналах необходимо уменьшать размеры пакетов , так как это сокращает объем повторно передаваемых данных при искажениях пакетов .
Инженеры, проводящие лабораторные тестирование коммутаторов, как оказалось, наибольшее значение придают одному параметру - пропускной способности. Почему? Поскольку пропускная способность поражает воображение пользователей и они убеждены, что именно этот параметр в основном определяет то, заслуживает ли этот коммутатор внимания.
Последние тесты коммутаторов Ethernet 10 Гбит/с показали,
что с точки зрения пропускной способности они значительно отличаются друг
от друга. Парадокс состоит в том, что чем быстрее сеть, тем меньшее
значение имеет пропускная способность свитча.
Этот фактор, естественно,
весьма важен, но только в тех случаях, когда сеть интенсивно загружена
пакетами. В то же время задержка (то есть время, необходимое для
переключения между портом ввода и порта вывода)
играет важную роль для
каждого типа движений пакетов, в каждой ситуации и в каждой
сети.
Устройства, характеризующиеся большой величиной задержки,
уменьшают скорость работы сети - и это происходит вне зависимости от того,
загружена ли сеть на 1% или на 100%. Для того, чтобы приложения
"запротестовали", задержки вовсе не должны составлять несколько сот
миллисекунд.
Если говорить о коммутаторах, оснащенных интерфейсами
Ethernet 1 и 10 Гбит/с, то чаще всего задержка у них составляет величину
от нескольких десятков до нескольких сотен миллисекунд. До сих пор
считается, что задержки, составляющие несколько десятков миллисекунд, не
влияют на производительность сетевых приложений.
Отчасти это неверно.
Даже небольшие задержки порядка нескольких десятков миллисекунд могут
стать причиной резкого уменьшения производительности сетей Ethernet 1 и 10
Гбит/с. "Виновен" в этом, если так можно выразиться, протокол ТСР, а
точнее, окна, необходимые этому протоколу для передачи пакетов в
сеть.
Как работает ТСР? Отправитель высылает ограниченные порции данных
таким образом, чтобы получатель мог выслать в обратном направлении
информацию, подтверждающую их получение. Окна обеспечивают подтверждения о
получении нескольких пакетов сразу, но если отправитель не получает от
получателя за определенное время такого подтверждения, то все пакеты
должны быть переданы повторно.
Поскольку в сети Интернет свыше 80%
передач происходит с помощью протоколов ТСР, повторная передача пакетов
может привести к значительному снижению работоспособности приложений,
запущенных в той же среде.
Например, в сети работает коммутатор E1200
(Force10 Networks) и получает пакеты Ethernet длиной 1518 байт,
соответствующих максимально возможной длине пакетов Ethernet и обычно
используемых при передаче больших объемов данных. Использование сетей на
этот момент умеренное, в пределах 10%. Коммутатор принимает 81274 пакета в
секунду (один пакет принимается за 12 микросекунд).
В ОС Windows 2000 и
XP размер пакета ТСР по умолчанию составляет 16 Кб. Это означает, что в
сеть можно отправить без подтверждения их получения не более 11 пакетов.
Для 11 пакетов (считая по 12 микросекунд на каждый), каждая задержка более
132 микросекунд будет означать, что данные будут высылаться
повторно.
Последние тесты коммутаторов Ethernet 10 Гбит/с показали, что
в устройствах Avaya и Force10 Networks задержка при переключении пакетов
длиной 1518 байт составляет свыше 40 микросекунд. То есть одиннадцать
таких задержек - и мы имеем дело с повторно передаваемыми через протокол
ТСР пакетами. Компания Force10 представила свой коммутатор E1200 и
сообщила, что задержки удалось уменьшить вполовину (теперь они составляют
23 микросекунды). При таких задержках в сетях Ethernet 10 Гбит/с и дальше
происходит повторная передача пакетов, но в сетях 1 Гбит/с протокол ТСР
уже не передает их повторно. Но размеры окон изменяются динамически: чем
больше окошко, тем большее влияние имеют маленькие задержки.
Можно
описать влияние окна ТСР на работу любой сети. Для того, чтобы это
сделать, необходимо знать три параметра: длина пакетов, размер окна ТСР и
степень использования сети.
Установка протокола TCP/IP
Протокол TCP/IP использует IP-адрес, маску подсети и шлюз по умолчанию для соединения с узлами. Узлы TCP/IP, работающие в глобальной сети, требуют задания всех трех параметров в конфигурации. Каждая плата сетевого адаптера в компьютере, использующем TCP/IP, нуждается в этих параметрах.
IP-адрес - это логический 32-разрядный адрес, однозначно определяющий узел TCP/IP. Каждый IP-адрес состоит из двух частей: идентификатора сети и идентификатора узла. Первый служит для обозначения всех узлов в одной физической сети. Второй обозначает конкретный узел в сети. Каждому компьютеру, использующему TCP/IP, требуется уникальный IP-адрес, например, 194.103.2.200.
Маска подсети выделяет часть IP-адреса и позволяет TCP/IP отличить идентификатор сети от идентификатора узла. Пытаясь связаться, узлы TCP/IP используют маску подсети (например, 255.255.255.0), чтобы определить, находится узел-получатель в локальной или удаленной сети.
Для того чтобы установить соединение с узлом из другой сети, вы должны сконфигурировать IP-адрес шлюза по умолчанию. TCP/IP посылает пакеты, предназначенные для удаленных сетей, на шлюз по умолчанию, но только в том случае, если на локальном узле не сконфигурирован другой маршрут к сети получателя. Если вы не сконфигурируете шлюз по умолчанию, то связь может быть ограничена локальной сетью.
Зайдите на Панель управления, а затем в раздел "Сеть". Если TCP/IP не числится в списке установленных сетевых протоколов, необходимо его установить. Затем выделите TCP/IP и нажмите на кнопку "Свойства". Если ваш компьютер включен в большую сеть, необходимо убедиться, что имя компьютера, домена и информация об IP-адресе не конфликтуют с сетью. В отличие от IP-адреса и маски подсети шлюз по умолчанию является необязательным параметром. Если вы его опустите, то область работы вашего компьютера ограничится локальной сетью.
Пример
Подсчет средних характеристик
Одноканальные СМО с ожиданием
Такие системы при условии, что нет ограничений на длину очереди, имеют бесчисленное множество состояний:
Е 0 , Е 1 , Е 2 , Е 3 , ...
Е 0 – в системе 0 требований (система свободна);
Е 1 – в системе 1 требование (система занята);
Е 2 – в системе 1 требование, и одно требование ожидает в очереди;
Е 3 – в системе 1 требование, и два требования ожидают в очереди и т. д.
P 0 = 1-φ, φ = λ/μ.
Следовательно,
P k = (1-φ)φ k , k = 1, 2, ….
Условие φ > 0 является необходимым и достаточным для наличия стационарного режима работы системы.
Интересно знать, почему стационарный режим существует только при этом условии?
Это условие означает, что среднее число требований, поступивших в СМО, меньше, чем интенсивность самого обслуживания; поэтому система успевает ритмично работать. Теперь ясно, почему система не может работать при условии, когда коэффициент загрузки больше 1. Но почему нет установившегося режима, когда коэффициент загрузки равен 1? Ведь в этом случае, сколько в среднем требований поступает в СМО, столько в среднем и обслуживается. Однако требования поступают в систему неравномерно, и время их обслуживания тоже колеблется, так что могут быть и простои, и перегрузки. Вот поэтому при таком условии не поддерживается стационарный режим.
При изучении СМО важнейшими являются средние значения (математические ожидания) таких случайных величин:
n – количество требований, находящихся в системе;
v – длина очереди;
w – время ожидания в очереди.
Ниже их формулы:
v = φ 2 /(1-φ);
w = [φ/(1-φ)]*.
Интенсивность потока автомобилей, поступающих на моечную станцию (одноканальная СМО) – 4 автомобиля в час, а интенсивность обслуживания – 5 автомобилей в час. Предполагая, что станция работает в стационарном режиме, найти среднее число автомобилей, находящихся на станции, среднюю длину очереди и среднее время ожидания обслуживания.
Решение
Определяем коэффициент загрузки системы:
n = 0,8/(1-0,8) = 4;
v = 4*0,8 = 3,2;
Сделаем следующие предположения относительно таких систем:
· входной поток пуассоновский;
· время обслуживания распределено по экспоненциальному закону;
· время обслуживания не зависит от входного потока;
· все линии обслуживания работают независимо.
Будем считать, что система содержит некоторое количество линий обслуживания s. Она может находиться в состояниях Е 0 , Е 1 , Е 2 , Е 3 , ... Е S . Расчёт переходных вероятностей показывает, что из каждого из свободных состояний система может переходить в соседнее состояние, либо в такое же, в каком была.
Для нахождения вероятностей используется следующая формула:
P k = φ k /k!*P 0 , φ = λ/μ, где k = 1, 2, ...
Так как сумма всех вероятностей составляет 1, то
Отсюда следуют формулы:
Увеличение коэффициента загрузки системы ведет к увеличению вероятности отказа системы. Это не устраивает потребителей. Уменьшение вероятности отказа системы может быть достигнуто за счёт увеличения количества линий обслуживания.
Однако резкое увеличение количества линий не устраивает организатора, потому что ведёт к дополнительным затратам на приобретение новых линий обслуживания, и увеличивает вероятность простоя линий. Расчет показывает, что среднее число свободных линий обслуживания
ρ = s-φ(1-P s).
Теперь ясно, что при сильном увеличении количества линий обслуживания, увеличится среднее число простаивающих линий.
Таким образом, мы имеем дело с двумя противоположными тенденциями. Задача сводится к выбору оптимального варианта. С этой целью будем минимизировать функцию стоимости СМО – С(s). Если через с 1 мы обозначим стоимость одного отказа (организатор системы платит штраф за каждый отказ), а через с 2 – стоимость простоя одной линии за единицу времени, то функция стоимости будет иметь следующий вид:
C(s) = c 1 λP s +c 2 ρ.
Или в развернутом виде:
Сначала с увеличением s она убывает, а затем растёт. Наша задача состоит в том, чтобы найти её минимум.
В качестве показателей эффективности СМО с отказами будем рассматривать:
А - абсолютную пропускную способность СМО, т.е. среднее число заявок, обслуживаемых в единицу времени;
Q - относительную пропускную способность, т.е.
Среднюю долю пришедших заявок, обслуживаемых системой;
/’отк. - вероятность отказа, т.е. того, что заявка покинет СМО необслуженной;
к - среднее число занятых каналов (для многоканальной системы). Одноканальная система с отказами. Рассмотрим задачу.
Имеется один канал, на который поступает поток заявок с интенсивностью X. Поток обслуживании имеет интенсивность р. Найти предельные вероятности состояний системы и показатели ее эффективности.
Система S (СМО) имеет два состояния: 6о - канал свободен, iS) - канал занят. Размеченный граф состояний представлен на рис. 15.6.
кро - Ц/>1, V-P\ - kp0,
т.е. система вырождается в одно уравнение. Учитывая нормировочное условие ра + />1=1, найдем из (15.18) предельные вероятности состояний
15.5. Известно, что заявки на телефонные переговоры в телевизионном ателье поступают с интенсивностью X, равной 90 заявок в час, а средняя продолжительность разговора по телефону / 0б.=2 мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера.
Решение. Имеем Х=90 (1/ч), ґ 0б=2 мин. Интенсивность потока обслуживании |д.=1/Г об.” 1/2=0,5 (1/мин)=30 (1/ч). По (15.20) относительная пропускная способность СМО 0=ЗО/(9О+ЗО)=О,25, т.е. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа в обслуживании составит /отк=0,75 (см. (15.21)). Абсолютная пропускная способность СМО по (15.29) Л=900,25=22,5, т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок.
Многоканальная система с отказами. Рассмотрим классическую задачу Эрланга.
Имеется п каналов, на которые поступает поток заявок с интенсивностью X. Поток обслуживании имеет интенсивность ц. Найти предельные вероятности состояний системы и показатели № эффективности.
Система 5 (СМО) имеет следующие состояния (нумеруем их то числу заявок, находящихся в системе): 5о, і’г, -, ... Эп,
Где Э/с - состояние системы, когда в ней находится к заявок, т.е. іанято к каналов.
Граф состояний СМО соответствует процессу гибели и размножения и показан на рис. 15.7.
| А _ | А. __ | |||
| * | *5| | *$! | ||
| ц | * 2ц |
| я. |
| X ... А. |
| "зіг |
| Рис. 15.7 Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью X. Интенсивность же потока обслуживании, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости ОТ СОСТОЯНИЯ. Действительно*! если СМО находится в состоянии 5г (два канала заняты), то ощ может перейти в состояние 5) (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживании будет 2ц. Аналогично суммарный поток обслуживании, переводящий СМО из состояния 5з (три канала заняты) в 52, будет иметь интенсивность Зц, т.е. может освободиться любой из трех каналов и т.д. В формуле (15.16) для схемы гибели и размножения получим для предельной вероятности состояния |
Р\=РРо, Р2=^Ро, > Рк=^Ро, Рп~Ро- (15.26)
Формулы (15.25) и (15.26) для предельных вероятностей получили названия формул Эрланга в честь основателя теории массового обслуживания.
Вероятность отказа СМО есть предельная вероятность того, что все п каналов системы будут заняты, т.е.
0 = 1-Р07К = 1-£Ро.
Абсолютная пропускная способность:
Среднее число занятых каналов к есть математическое ожидание числа занятых каналов:
где рк - предельные вероятности состояний, определяемых по формулам (15.25), (15.26).
| (15.31) |
^ 15.6. В условиях задачи 15.5 определить оптимальное число телефонных номеров в телевизионном ателье, если условием оптимальности считать удовлетворение в среднем из каждых 100 заявок не менее 90 заявок на переговоры.
Решение. Интенсивность нагрузки канала по формуле
(15.25) р=90/30=3, т.е. за время среднего (по продолжительности) телефонного разговора I „б=2 мин. поступает в среднем 3 заявки на переговоры.
Будем постепенно увеличивать число каналов (телефонных номеров) л=2, 3, 4, ... и определим по формулам (15.25), (15.28),
(15.29) для получаемой л-канальной СМО характеристики обслуживания. Например, при п = 2 р0=^1 + 3 + 32/2!) = 0,118 » 0,12;
б = 1 - (з2/2!)- 0,118 = 0.471 * 0,47 ; Л=900,471=42,4 и т.д. Значение характеристик СМО сведем в табл. 15.1.
Таблица 15.1
По условию оптимальности 0 £ 0,9, следовательно, в телевизионном ателье необходимо установить 5 телефонных номеров (в этом случае 0 = 0,90 - см. табл. 15.1). При этом в час будут обслуживаться в среднем 80 заявок (А = 80,1), а среднее число занятых телефонных номеров (каналов) по формуле (15.30) к = = 80,1/30 = 2,б7>
1> 15.7. В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ
не принимается, и предприятие вынуждено обратиться в другой вычислительный центр. Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч). Найти предельные вероятности состояний и показатели эффективности работы вычислительного центра.
Решение. По условию п=3* А,=0,25 (1/ч), Г0б=3 (ч). Интенсивность потока обслуживаний ц= 1/ 0б.=1 /3=0,33. Интенсивность нагрузки ЭВМ по формуле (15.24) р=0,25/0,33=0,75. Найдем предельные вероятности состояний:
по формуле (15.25) р0=(1+0,75+0,752/2!+0,753/3!)"*=0,476;
по формуле (15.26) ^1=0,750,476=0,357; /?2=(0»752/2!) 0,47б= =0,134; рз=(0,753/3!) 0,476=0,033, т.е. в стационарном режиме работы вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% - имеется одна заявка (занята одна ЭВМ), 13,4% - две заявки (две ЭВМ), 3,3% времени - три заявки (заняты три ЭВМ).
Вероятность отказа (когда заняты все три ЭВМ), таким образом, Яотк=рз=0,033.
По формуле (15.28) относительная пропускная способность центра 0 = 1-0,033 = 0,967, т.е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок.
По формуле (15.29) абсолютная пропускная способность центра А = 0,25-0,967 = 0,242, т.е. в один час в среднем обслуживается 0,242 заявки.
По формуле (15.30) среднее число занятых ЭВМ к = = 0,242/0,33 = 0,725, т.е. каждая из трех ЭВМ будет занята обслуживанием заявок в среднем лишь на 72,5/3 = 24,2%.
При оценке эффективности работы вычислительного центра необходимо сопоставить доходы от выполнения заявок с потерями от простоя дорогостоящих ЭВМ (с одной стороны, у нас высокая пропускная способность СМО, а с другой стороны - значительный простой каналов обслуживания) и выбрать компромиссное решение.
Ниже будут рассмотрены примеры простейших систем массового обслуживания (СМО). Понятие «простейшие» не означает «элементарные». Математические модели этих систем применимы и успешно используются в практических расчетах.
Одноканальная смо с отказами
Дано : система имеет один канал обслуживания, на который поступает простейший поток заявок с интенсивностью. Поток обслуживаний имеет интенсивность. Заявка, заставшая систему занятой, сразу же покидает ее.
Найти : абсолютную и относительную пропускную способность СМО и вероятность того, что заявка, пришедшая в момент времени t, получит отказ.
Система при любом t > 0 может находиться в двух состояниях:S 0 – канал свободен;S 1 – канал занят. Переход изS 0 вS 1 связан с появлением заявки и немедленным началом ее обслуживания. Переход изS 1 вS 0 осуществляется, как только очередное обслуживание завершится (рис.4).
Рис.4. Граф состояний одноканальной СМО с отказами
Выходные характеристики (характеристики эффективности) этой и других СМО будут даваться без выводов и доказательств.
Абсолютная пропускная способность (среднее число заявок, обслуживаемых в единицу времени):
где – интенсивность потока заявок (величина, обратная среднему промежутку времени между поступающими заявками -);
–интенсивность потока обслуживаний (величина, обратная среднему времени обслуживания )
Относительная пропускная способность (средняя доля заявок, обслуживаемых системой):
Вероятность отказа (вероятность того, что заявка покинет СМО необслуженной):
Очевидны следующие соотношения: и.
Пример . Технологическая система состоит из одного станка. На станок поступают заявки на изготовление деталей в среднем через 0,5 часа. Среднее время изготовления одной детали равно. Если при поступлении заявки на изготовление детали станок занят, то она (деталь) направляется на другой станок. Найти абсолютную и относительную пропускную способности системы и вероятность отказа по изготовлению детали.
Т.е. в среднем примерно 46 % деталей обрабатываются на этом станке.
.
Т.е. в среднем примерно 54 % деталей направляются на обработку на другие станки.
N – канальная смо с отказами (задача Эрланга)
Это одна из первых задач теории массового обслуживания. Она возникла из практических нужд телефонии и была решена в начале 20 века датским математиком Эрлангом.
Дано : в системе имеетсяn – каналов, на которые поступает поток заявок с интенсивностью. Поток обслуживаний имеет интенсивность. Заявка, заставшая систему занятой, сразу же покидает ее.
Найти : абсолютную и относительную пропускную способность СМО; вероятность того, что заявка, пришедшая в момент времениt , получит отказ; среднее число заявок, обслуживаемых одновременно (или, другими словам, среднее число занятых каналов).
Решение . Состояние системыS (СМО) нумеруется по максимальному числу заявок, находящихся в системе (оно совпадает с числом занятых каналов):
S 0 – в СМО нет ни одной заявки;
S 1 – в СМО находится одна заявка (один канал занят, остальные свободны);
S 2 – в СМО находится две заявки (два канала заняты, остальные свободны);
S n – в СМО находитсяn – заявок (всеn – каналов заняты).
Граф состояний СМО представлен на рис. 5
Рис.5 Граф состояний для n – канальной СМО с отказами
Почему граф состояний размечен именно так? Из состояния S 0 в состояниеS 1 систему переводит поток заявок с интенсивностью(как только приходит заявка, система переходит изS 0 вS 1). Если система находилась в состоянииS 1 и пришла еще одна заявка, то она переходит в состояниеS 2 и т.д.
Почему такие интенсивности у нижних стрелок (дуг графа)? Пусть система находится в состоянии S 1 (работает один канал). Он производитобслуживаний в единицу времени. Поэтому дуга перехода из состоянияS 1 в состояниеS 0 нагружена интенсивностью. Пусть теперь система находится в состоянииS 2 (работают два канала). Чтобы ей перейти вS 1 , нужно, чтобы закончил обслуживание первый канал, либо второй. Суммарная интенсивность их потоков равнаи т.д.
Выходные характеристики (характеристики эффективности) данной СМО определяются следующим образом.
Абсолютная пропускная способность :
где n – количество каналов СМО;
–вероятность нахождения СМО в начальном состоянии, когда все каналы свободны (финальная вероятность нахождения СМО в состоянии S 0);
Рис.6. Граф состояний для схемы «гибели и размножения»
Для того, чтобы написать формулу для определения , рассмотрим рис.6
Граф, представленный на этом рисунке, называют еще графом состояний для схемы «гибели и размножения». Напишем сначала для общую формулу (без доказательства):
Кстати, остальные финальные вероятности состояний СМО запишутся следующим образом.
S 1 , когда один канал занят:
Вероятность того, что СМО находится в состоянии S 2 , т.е. когда два канала заняты:
Вероятность того, что СМО находится в состоянии S n , т.е. когда все каналы заняты.
Теперь для n – канальной СМО с отказами
Относительная пропускная способность:
Напомним, что это средняя доля заявок, обслуживаемых системой. При этом
Вероятность отказа :
Напомним, что это вероятность того, что заявка покинет СМО необслуженной. Очевидно, что .
Среднее число занятых каналов (среднее число заявок, обслуживаемых одновременно):
