вар 4. 1. Марковский процесс с дискретными состояниями и дискретным временем
![]()
|
13. Разложение времени сетевой задержки по каналам сети jk – Трафик (traffic), поступающий в сеть из внешних источников для тех сообщений, которые возникают в узле j и предназначены для узла k. Полный внешний трафик, поступающий в сеть, определим как: ![]() Обозначим T – средняя задержка сообщения, Zjk – задержка сообщения, которое возникло в j и предназначено для узла k. Ясно, что эти две средние величины связаны равенством: ![]() так как доля (jk/) полного входящего трафика сообщений имеет в среднем задержку равную Zjk. Отметим, что последнее равенство представляет разложение сети по парам источник-адресат. Обозначим через jk путь, по которому идут сообщения, возникающие в узлеj и имеющие в качестве узла назначения узел k. Говорят, что i-ый канал (с пропускной способностью Ci) включен в путь jk, если сообщения, идущие по этому пути, проходят указанный канал (Cijk). Тогда среднее число сообщений в единицу времени, проходящих по i-му каналу связи равно: ![]() Кроме того, заметим что Zjk – сумма (Ti) средних задержек, испытываемых сообщением при передаче по различным каналам пути jk. ![]() Следовательно: ![]() Изменим теперь порядок суммирования (условие на i сменим на пару jk). ![]() ![]() Теперь средняя задержка представляет разложение по отдельным каналам. Используя известный результат исследований Джексона: Канал сети можно рассматривать как такой же канал, действующий независимо от сети, но с пуассоновским входным потоком, интенсивность которого равно интенсивности, задаваемой сетью. ![]() и 1/ - средняя длина сообщения, 1/ ![]() ![]() Можно провести расчет для случая непоказательных длин сообщений. Но при этом будет проявлена слишком большая смелость, так как для систем M/G/1 результат Джексона неприменим. Однако это приближение приводит к модели, которая очень хорошо согласуется с моделированием на ЭВМ. 14. Задача выбора пропускных способностей каналов Предположим, что заданы потоки ![]() Необходимо минимизировать время пребывания требования в сети, удовлетворяющее ограничению: ![]() Для решения задачи будем варьировать пропускными способностями каналов ![]() ![]() ![]() ![]() Для минимизации Т - времени пребывания требования в сети составим функцию Лагранжа: ![]() Как обычно, используя метод Лагранжа, получаем следующую систему из М уравнений ![]() ![]() Решая относительно ![]() ![]() Определим , составив ограничение путем перемножения на ![]() ![]() Следовательно: ![]() где ![]() ![]() ![]() При таком наборе пропускных способностей каждый канал будет иметь, по крайней мере, пропускную способность ![]() Минимальная средняя задержка сети, пропускные способности в которой выбраны оптимально, может быть записана в виде: ![]() В ![]() ернемся к рассмотренному ранее примеру. ![]() ![]() если ![]() ![]() ![]() ![]() ![]() ![]() Тогда: ![]() ![]() Для рассмотренного ранее примера ![]() ![]() 15. СМО типа M/M/1 Введем следующие обозначения: ![]() ![]() ![]() ![]() ![]() Вычислим ![]() ![]() ![]() Для этого определим вероятность того, что за время ![]() ![]() Так как простейший поток обладает свойством ординарности (за интервал времени ![]() ![]() ![]() ![]() ![]() Рассмотрим случаи реализации события с вероятностью ![]() а) В момент времени ![]() ![]() ![]() ![]() б) В момент времени ![]() ![]() ![]() ![]() в) В момент времени ![]() ![]() ![]() ![]() Вероятность ![]() ![]() ![]() Эта формула справедлива для ![]() ![]() а) В момент времени ![]() ![]() ![]() б) В момент времени ![]() ![]() ![]() ![]() ![]() Уравнения (1) и (2) называют дифференциальными уравнениями Колмогорова для СМО типа ![]() Для установившегося режима вероятность пребывания в системе ![]() ![]() Методом математической индукции докажем, что ![]() ![]() Доказательство: Для ![]() ![]() ![]() ![]() ![]() ![]() ![]() Вычислим ![]() ![]() ![]() Тогда ![]() Представим СМО типа M/M/1 в виде графа, у которого вершины обозначают состояния системы, характеризующиеся числом требований, а ребра будут обозначать интенсивность перехода из одного состояния в другое. ![]() ![]() Вычислим среднее число требований N, находящихся в системе: ![]() Так как всегда имеет место ![]() ![]() ![]() 16. Одноканальная СМО с отказами (M/M/1/0) На вход поступает пуассоновский поток с интенсивностью . Заявка, заставшая канал занятым получает отказ и покидает систему. Обслуживание подчинено показательному закону с параметром . Единственный канал может находиться в одном из двух состояний: S0 – канал свободен, S1 – канал занят. ![]() Пользуясь общим решением для схемы «гибели и размножения» получим: ![]() Очевидно, требование получит отказ, когда канал занят (доля необслуженных заявок). ![]() Доля обслуженных заявок – относительная пропускная способность: ![]() Абсолютная пропускная способность: ![]() Время обслуживания равно ![]() ![]() Пример. Система обработки информации представима в виде M/M/1/0. Интенсивность потока требований =9тр/час. Средняя продолжительность обработки tобр=5 мин. Определить T, W, X, N, Q, V, q, A, Pотк. Сравнить фактическую пропускную способность СМО с номинальной, которая была бы, если обработка информации длилась без перерыва. ![]() Решение: Номинальная пропускная способность системы: ![]() Относительная пропускная способность: ![]() Таким образом, 57% заявок будет обслужено в установившемся режиме. Вероятность отказа Pотк=1-q=0,429. Значит около 49% требований получит отказ. Абсолютная (фактическая) пропускная способность обслуживающего прибора (канала): ![]() что почти вдвое меньше, чем номинальная пропускная способность, это объясняется случайным характером потока заявок и потока обслуживания. ![]() 17. Одноканальная СМО с ограниченным ожиданием (M/M/1/k). В этой модели количество мест в очереди равно k, что и накладывает ограничение на время ожидания каждого требования, т. е. (W<k/). Время ожидания не превышает k обсл. Будем нумеровать состояния СМО по числу требований, находящихся в системе. S0 – канал свободен S1 – канал занят, очереди нет … Sk+1 – канал занят, в очереди k заявок ![]() Пользуясь общим решением схемы «гибели и размножения» и введя обозначение =/, получим: ![]() Выражение для p0 справедливо для <1, при: ![]() Заявка получает отказ, когда все k мест в очереди заняты: ![]() Оставшаяся доля заявок будет обслужена, поэтому относительная пропускная способность: ![]() Абсолютная пропускная способность: A= ![]() Выводы выражения для среднего времени ожидания пребывания в очереди (W). Любая заявка с вероятностью p0 не будет ждать обслуживания (время ожидания=0), с вероятностью p1 будет ждать одного обслуживания (время ожидания= ![]() ![]() ![]() Время обслуживания X равно 1/, если заявка обслуживается и X=0, если она получила отказ. ![]() |