Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Разложение времени сетевой задержки по каналам сети





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

gjk – Трафик (traffic), поступающий в сеть из внешних источников для тех сообщений, которые возникают в узле j и предназначены для узла k.

Полный внешний трафик, поступающий в сеть, определим как:

, где N – число узлов.

Обозначим T – средняя задержка сообщения, Zjk – задержка сообщения, которое возникло в j и предназначено для узла k.

Ясно, что эти две средние величины связаны равенством:

,

так как доля (gjk/g) полного входящего трафика сообщений имеет в среднем задержку равную Zjk.

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

Обозначим через pjk путь, по которому идут сообщения, возникающие в узле j и имеющие в качестве узла назначения узел k. Говорят, что i-ый канал (с пропускной способностью Ci) включен в путь pjk, если сообщения, идущие по этому пути, проходят указанный канал (CiÎpjk).

Тогда среднее число сообщений в единицу времени, проходящих по i-му каналу связи равно:

Кроме того, заметим что Zjk – сумма (Ti) средних задержек, испытываемых сообщением при передаче по различным каналам пути pjk.

Следовательно:

Изменим теперь порядок суммирования (условие на i сменим на пару jk).

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

Используя известный результат исследований Джексона:

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

и

1/m - средняя длина сообщения,

1/m Сi – среднее время передачи сообщения по каналу Сi.

 
 

Можно провести расчет для случая непоказательных длин сообщений. Но при этом будет проявлена слишком большая смелость, так как для систем M/G/1 результат Джексона неприменим.

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


 

Задача выбора пропускных способностей каналов

Предположим, что заданы потоки и топология сети.

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

Для решения задачи будем варьировать пропускными способностями каналов , - стоимость пропускной способности для i-ого канала.

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

Для минимизации Т - времени пребывания требования в сети составим функцию Лагранжа:

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

Решая относительно , получим:

Определим b, составив ограничение путем перемножения на и суммировав по i:

Следовательно:

где - добавочная стоимость.

При таком наборе пропускных способностей каждый канал будет иметь, по крайней мере, пропускную способность и, кроме того, некоторую дополнительную пропускную способность.

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

 

Вернемся к рассмотренному ранее примеру.

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

 

Тогда:

Для рассмотренного ранее примера имели значения:


 

15. СМО типа M/M/1

Введем следующие обозначения:

– средняя норма прибытия, интенсивность входного потока

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

– вероятность того, что в системе в момент времени находится ровно требований

 

Вычислим – вероятность того, что в системе момент времени находится ровно требований.

Для этого определим вероятность того, что за время произошло одно прибытие (одно обслуживание).

Так как простейший поток обладает свойством ординарности (за интервал времени не может произойти более одного прибытия), то справедливо:

– вероятность того, что за время не произошло прибытий

– вероятность того, что за время не было окончаний обслуживания

Рассмотрим случаи реализации события с вероятностью :

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

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

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

Вероятность равна сумме вероятностей рассмотренных случаев:

(1)

Эта формула справедлива для , а для имеем:

а) В момент времени нет требований, а за время нет новых прибытий:

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

(2)

Уравнения (1) и (2) называют дифференциальными уравнениями Колмогорова для СМО типа .

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

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

Доказательство:

Для и это справедливо, так как и . Предположим, что справедливо и , тогда

Вычислим – вероятность того, что в системе нет требований. Пусть , тогда

Тогда .

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

 
 

Вычислим среднее число требований N, находящихся в системе:

Так как всегда имеет место

- среднее число требований в обсл. пр.


 

16. Одноканальная СМО с отказами (M/M/1/0)

На вход поступает пуассоновский поток с интенсивностью l. Заявка, заставшая канал занятым получает отказ и покидает систему. Обслуживание подчинено показательному закону с параметром m. Единственный канал может находиться в одном из двух состояний: S0 – канал свободен, S1 – канал занят.

 

 

Пользуясь общим решением для схемы «гибели и размножения» получим:

Очевидно, требование получит отказ, когда канал занят (доля необслуженных заявок).

Доля обслуженных заявок – относительная пропускная способность:

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

Время обслуживания равно , если требование будет обслужено и равно 0, если нет.

Пример. Система обработки информации представима в виде M/M/1/0.

Интенсивность потока требований l=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/m). Время ожидания не превышает k обсл.

Будем нумеровать состояния СМО по числу требований, находящихся в системе.

S0 – канал свободен

S1 – канал занят, очереди нет

Sk+1 – канал занят, в очереди k заявок

 

Пользуясь общим решением схемы «гибели и размножения» и введя обозначение r=l/m, получим:

Выражение для p0 справедливо для r<1, при:

Заявка получает отказ, когда все k мест в очереди заняты:

Оставшаяся доля заявок будет обслужена, поэтому относительная пропускная способность:

Абсолютная пропускная способность: A=l q.

Выводы выражения для среднего времени ожидания пребывания в очереди (W). Любая заявка с вероятностью p0 не будет ждать обслуживания (время ожидания=0), с вероятностью p1 будет ждать одного обслуживания (время ожидания= ), с вероятностью p2 будет ждать одного обслуживания (время ожидания= ) и т. д.

Время обслуживания X равно 1/m, если заявка обслуживается и X=0, если она получила отказ.


 

18. Одноканальные замкнутые СМО (M/M/1/k/l).

Одноканальные замкнутые СМО (M/M/1/k/l).

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

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

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

Пусть m – число каналов обслуживания, l – число источников заявок, k – число мест в очереди (k³l-1), m - интенсивность обслуживания.

S0 – канал свободен

S1 – канал занят, очереди нет

Sl – канал занят, в очереди l-1 требований

Из состояния S0 в состояние S1 систему переводит поток ll, из S1 в S2 уже (l -1) l, т. к. один источник заявок не функционирует и ожидает обслуживания. Из S2 в S3 в имеем поток (l -2) l и т. д.

k³l-1

 

 

Пользуясь общим решением для схемы гибели и размножения, напишем:

Относительная пропускная способность q=1, Pотн=0 т. к. каждое требование будет, в конце концов, обслужено.

Pзан=(1–p0) – вероятность, что канал занят. Занятый канал обслуживает в среднем m требований в единицу времени, следовательно, абсолютная пропускная способность:

В СМО в среднем работает (l-N) источников заявок, каждый из которых поток интенсивность которого =l.

Общий поток требований (l-N) l будет обслужен и, следовательно, равен абсолютной пропускной способности:

Откуда среднее число требований, находящихся в СМО:

Значение N можно вычислить непосредственно:

Среднее число требований, находящихся в обслуживающем устройстве равно:

Среднее число требований, ожидающих обсл. в очереди:

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

Если k<l-1

 

 

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

Определить эксплуатационные характеристики системы.

Решение.

 

 

Вероятность занятости системы коллективного доступа:

Абсолютная пропускная способность системы:

Среднее число запросов в системе:

Среднее число требований в обслуживающем устройстве:

Среднее число требований в ожидающем устройстве:

19.Многоканальная СМО с отказами (M/M/m/0)

Обозначения:

S0 – все каналы свободны

S1 – занят один канал, остальные свободны

---

Si – занято i каналов

---

Sm – заняты все каналы

 

Пользуясь общим решением для схемы «гибели и размножения» получим формулы Эрланга:

Зная все выражения можно найти характеристики эффективности СМО:

т. к. заявка получает отказ, если все каналы заняты.

Вероятность того, что заявка будет принята к обслуживанию (Она же относительная пропускная способность).

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

Среднее число заявок, находящихся в системе M/M/m/0 определим следующим образом:

A – среднее число заявок, обслуживаемых в единицу времени
m – среднее число заявок, обслуживаемых одним занятым каналом.

Тогда число занятых каналов (число заявок в системе).

Однако N можно выразить и непосредственно:

N=0 p0+1 p1+…+m pm


20.Одноканальная СМО с отказами (M/M/1/0) =16.


 

Пример.1

Сравнить эксплуатационные характеристики для моделей систем обработки информации M/M/2/k({0,3,¥})

l=9тр/час =12тр/час

Решение:

r=0,75 y=0,375

А=lq=8,939 V=0,75q=0,745

T=(0,745+0,104)/9=0,0943 час=5,65 мин

W=0,104/9=0,0115 час=0,69 мин

Х=0,745/9=0,083 час=4,96 мин

Модели T W X N Q V q
M/M/2/¥ 5,8 0,8 0,87 0,12 0,75
M/M/2/3 5,65 0,69 4,96 0,849 0,104 0,745 0,993
M/M/2/0 3,6 3,6 0,54 0,54 0,719

 


 

Пример 2.

Сравнить системы коллективного пользования с одним и двумя каналами обслуживания l=3, l=2, m=6.

Решение.

r=1/3


V=0,419+2(0,14+0,023)=0,744 – Среднее число занятых каналов

A=Vm=0,744·6=4,465 – Абсолютная пропускная способность

N=l-V/r=3-0,744/(1/3)=0,767 – Среднее число тр. Вес.? (всего?)

Q=N-V=0,023Среднее число тр. в очереди

X=1/m=0,167 T=N/A=0,172 W=0,005

Модели T W X N Q V A p0
M/M/2/k/3 0,172 0,005 0,167 0,767 0,023 0,744 4,465 0,419
M/M/1/k/3 0,265 0,098 0,167 1,038 0,384 0,654 3,923 0,346

 

 

Пример 3.

Вычислительная сеть M/D/1 обслуживает поток задач, запросы на выполнение которых поступают в случайные моменты времени (в среднем 9 требований в час). На решение одной задачи необходимо 5 минут.

Определить математическое ожидание:

Времени реакции системы на запрос –

Времени ожидания в очереди –

Числа требований в системе –

Числа требований в очереди –

Числа требований в обслуживающем приборе –

Если в качестве модели системы выбрать модель M/D/1

 
M/M/1 2,25 0,75
M/D/1 1,875 1,125 0,75 12,5 7,5
M/Er/1 2,438 1,688 0,75 16,25 11,25

 

Пример.4

Система обработки информации представима в виде M/M/1/0.

Интенсивность потока требований l=9тр/час.
Средняя продолжительность обработки tобр=5 мин.
Определить T, W, X, N, Q, V, q, A, Pотк.

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

 

Решение: Номинальная пропускная способность системы:

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

Таким образом, »57% заявок будет обслужено в установившемся режиме.

Вероятность отказа Pотк=1-q=0,429.

Значит около 49% требований получит отказ.

Абсолютная (фактическая) пропускная способность обслуживающего прибора (канала):

,

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


 

Пример 5.

Вычислительная система обслуживает поток задач. Входной поток и поток обслуживания простейшие.l=9m=12

Определить математическое ожидание

- времени реакции системы на запрос – T

- времени ожидания в очереди – W

- числа требований в системе – N

- числа требований в очереди – Q

- числа требований в обслуживающем приборе – V

- относительную пропускную способность – q

если в качестве модели системы выбрать модель M/M/1/3

 

 


Пример 6 = Пример 5

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

l=9

m=12

Определить математическое ожидание

- времени реакции системы на запрос – T

- времени ожидания в очереди – W

- числа требований в системе – N

- числа требований в очереди – Q

- числа требований в обслуживающем приборе – V

- относительную пропускную способность – q

если в качестве модели системы выбрать модель M/M/1/3


Пример.7

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

l=9

m=12

Рассмотреть модель M/M/1/5 и сравнить характеристики для k1=¥, k2=3,k3=1,k4=0.

 

k T W X N Q V q
¥ 0,33 0,25 0,08 2,25 0,75
0,165 0,09 0,078 1,48 0,81 0,675 0,896
0,093 0,03 0,063 0,837 0,27 0,567 0,756
0,048 0,048 0,428 0,428 0,57

 


Пример 8.

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

Определить эксплуатационные характеристики системы.

Решение.

 

 

Вероятность занятости системы коллективного доступа:

Абсолютная пропускная способность системы:

Среднее число запросов в системе:

Среднее число требований в обслуживающем устройстве:

Среднее число требований в ожидающем устройстве:


 

Пример.9

Систему обработки информации можно представить в виде модели M/M/2/0. Интенсивность требований l=9тр/час. Номинальная пропускная способность m=12тр/час.

Найти эксплуатационные характеристики системы.

Решение. Приведенная интенсивность потока требований .

Вероятность отказа:

Pотк=p2=(0,75)2/2!p0=0,28p0=0,138

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

q=1– p2=0,862 A=l q=7,754

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

V=N=r q=0,647

Среднее время пребывания требования в системе:

T=X=q/m=0,018 час=4,3 мин

Модели T W X N Q V q
M/M/2/¥ 5,8 0,8 0,87 0,12 0,75
M/M/2/0 4,3 4,3 0,65 0,65 0,86
M/M/1/0 2,88 2,88 0,43 0,43 0,57

 

 

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.