bigpo.ru
добавить свой файл
1 2 3
Предположим, что СВ и независимы. Тогда и формула (7.23) приобретает вид

.

Пусть теперь . При этом оказывается, что и, следова-тельно,

. (7.28)

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

,

где – ПФ числа требований в системе. Таким образом, заменив в правой части формулы (7.28) на z, получаем

,

т. е. формулу Поллачека – Хинчина.


2. Случай дискретного требования. Предположим, что требование дискретно, т. е. с вероятностью содержит k знаков, k = 1, 2, ..., . Введем в рассмотрение ПФ числа знаков (объема) требования . В этом случае имеем

.

Предположим, что каждый знак требования обслуживается в течение случайного времени , пусть – ФР СВ , a – ПЛС ФР (вспомним модель с дискретными требованиями из п. 7.1). Тогда, обозначив через условную ФР времени обслуживания требования при условии, что оно содержит k знаков, получим



.

И аналогично

.

Подставив найденные функции в формулу (7.23), получим

,

откуда следует, что ПФ числа знаков, находящихся в системе в стационарном режиме, равна

,

или, по-другому,

. (7.29)

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


3. Время обслуживания требования пропорционально его объему. В этом случае имеем , 0 и, следовательно,

.

Для ПЛС ФР тогда имеем

. (7.30)

Найдем также для этого случая ФР , представив ее в виде

,

где из того, что , следует



Поэтому



Или, иначе, , где .

Заметив теперь, что в нашем случае плотность условного распределения с ФР можно представить в виде дельта-функции и что , найдем :



. (7.31)

Отсюда следуют формулы для вычисления моментов , , .

Подставив полученные соотношения (7.30), (7.31) в (7.23), имеем

. (7.32)

Сделаем еще одно предположение о том, что объемы требований распределены экспоненциально с параметром f, т. е. . Легко заметить, что в этом случае , и из формулы (7.32) следует, что

. (7.33)

Для нахождения явного вида ФР необходимо найти обращение преобразования Лапласа . При этом следует рассмотреть два случая.


1) 1/2. В этом случае квадратный трехчлен в знаменателе формулы (7.33) имеет два разных вещественных корня:

, .

Поэтому обращение данного преобразования методами теории вычетов в этом случае дает

.

После простых вычислений приходим к формуле

(7.34)


где , .


2) 1/2. В этом случае и формула (7.33) принимает вид

,

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

,

откуда после вычислений получаем

. (7.35)


Первые два момента СВ имеют вид

, .

Возвращаясь к примеру, рассмотренному нами в п. 7.6, заметим, что для CMO функция имеет вид: , а для СМО получаем , где .


4. Оценки характеристик потерь в системе с ограниченным суммарным объемом. Рассмотрим теперь СМО , которая отличается от рассмотренной нами выше системы с пропорциональным объему временем обслуживания только тем, что в ней суммарный объем ограничен величиной V. Для этой системы явный вид ФР определяется соотношениями (7.34), (7.35). Поэтому, пользуясь формулами

, ,

где можем найти оценки характеристик потерь и Простые вычисления дают

, если ,

и

, если ;





, если ,

и

, если .

Отметим, что в том случае, если СВ и независимы и распределены экспоненциально (см. модель с непрерывными требованиями в п. 7.1), явный вид ФР стационарного объема определяется соотно-шением

.

Для такой системы оценки характеристик потерь имеют вид

, .

Заметим, что в п. 7.5 мы получили точную формулу для вероятности потери данной системы:

.

Очевидно, выполняется неравенство .


7.9. Системы M/G/n/0 и M/G/


Классическая СМО была рассмотрена в п. 6.4. Предположим, что требование в этой СМО характеризуется случайным объемом независимым от объемов других требований. Время обслуживания требования зависит только от его объема. Задана ФР . Будем считать, что суммарный объем требований в системе неограничен. Относительно параметров входного потока, ФР, моментов и преобразований всех рассматриваемых здесь СВ примем обозначения п. 7.7. Примем также обозначение . Будем считать, что эта величина конечна, т. е. в рассматриваемой СМО существует стационарный режим.


Теорема 3. Для СМО в стационарном режиме при указанных предположениях справедливо соотношение

, где .


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

, .

Если число требований в системе , то объем j-го требования в системе зависит только от величины , , и, в соответствии с леммой 1,

.

ПЛС правой части последнего выражения имеет вид

.

При условии имеем , причем СВ независимы. Поэтому для ПЛС по х условной ФР получаем



. (7.36)

Очевидно, функцию можно представить в виде

, (7.37)

где функции определяются соотношением (6.42). Из (7.37) с учетом (6.42) и (7.36) получаем

. (7.38)

Остается вычислить интеграл в последнем выражении:



(7.39)

В самом деле,

.

Подставив (7.39) в (7.38), получаем утверждение теоремы. 


Следствие 1. Два первых момента стационарного суммарного объема СМО определяются соотношениями

; .


Следствие 2. Если и , , то явный вид ФР СВ определяется соотношением



(заметим, что в этом случае ).


Следует отметить, что в том случае, когда СВ и независимы и распределены экспоненциально с параметрами f и соответственно, имеем

.

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

Легко показать, что ПЛС стационарного суммарного объема в этом случае имеет вид

,

а первый момент и дисперсия стационарного суммарного объема определяются соотношениями

, .

Первое из этих соотношений мы могли бы получить непосредственно из аналога формулы Литтла.

Если СВ и независимы, имеем

.

Наконец, если , , то , и в этом случае

,

а первый момент и дисперсия имеют вид

, .

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


7.10. Примеры расчета объема памяти

информационных систем


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


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

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

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

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


Анализ концентратора при бесконечном объеме БП. Статистический анализ информационных систем передачи научной и коммерческой информации (в таких системах объем требований, а, значит, и время обслуживания, достаточно велики) дает основания предположить, что на вход концентратора поступает простейший поток сообщений интенсивности а; объемы сообщений (в битах или символах) распределены по геометрическому закону со средним значением , т. е. , . Моменты i-го порядка () СВ определяются соотношениями

, ,

В п. 7.7 мы получили соотношения для ПЛС ФР стационарного суммарного объема и его первых двух моментов и для самого общего случая СМО с неограниченной памятью. Из этих соотношений элементарно следует, что в нашем конкретном случае имеем

;



где .

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

,

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

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








Средний

суммарный

объем


Среднее время

пребывания

Погрешность

(%)

















0,2

0,4

0,6

0,8

0,225

0,533

1,050

2,400

0,450

1,067

2,100

4,800

1,125

1,330

1,750

3,000

1,250

1,670

2,500

5,000

50

50

50

50

10

20

30

40




0,2

0,4

0,6

0,8

1,575

3,733

7,350

16,80

1,800

4,267

8,400

19,20

4,880

6,330

9,250

18,00

5,000

6,700

10,00

20,00

12,5

12,5

12,5

12,5

2,4

5,5

7,5

10,0



0,2

0,4

0,6

0,8


4,275

10,133

19,950

45,600

4,500

10,667

21,000

48,000

12,350

16,333

24,300

48,000

12,50

16,70

25,00

50,00

5

5

5

5

1,2

2,2

2,8

4,0

Следовательно, при достаточно больших объемах требований (в реальных информационных системах имеем  15 знаков = 120 бит) замена геометрических распределений экспоненциальными является оправданной. И в этом случае, как следует из результатов, полученных в п. 7.8,

,

, .

Для рассматриваемой системы в п. 7.8 получен явный вид ФР стационарного суммарного объема.

Учет ограничения объема БП. Анализируя данную систему с неограниченной памятью, можем, как известно, оценить требуемый объем памяти V по заданным характеристикам потерь. Если, например, вероятность потери мала (), то можно считать, что ограничение по объему памяти практически не влияет на временные характеристики системы (время пребывания и время ожидания).

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

,

где – ФР стационарного суммарного объема в анализируемой СМО. Решая это уравнение численно относительно V, определим величину V, якобы гарантирующую эту вероятность потери.

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

,

причем в п. 7.8 были получены явные формулы для определения величины в системе со временем обслуживания, пропорциональным объему требования. Именно такую систему мы сейчас и рассматриваем.

Проведем сравнительный анализ оценок и . Его результаты, рассчитанные для случая (в этом случае можно считать, что объем памяти V измеряется в числе средних объемов требования), помещены в табл. 2. При этом считаем также, что первый момент времени обслуживания (т. е. за единицу времени принимается среднее время обслуживания; в случае необходимости перевод в другие единицы делается элементарно). Данные в таблице приведены для загрузок и . Точное значение вероятности потери будет несколько меньше, чем , но больше, чем , и в этом заключается главный недостаток «классического» подхода, не способного обеспечить непревышение заданной вероятности потери.

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

  • Таблица 2



V0

4

8

12

16

20

24

28

32

360,200000

0,027368

0,002218

0,000174

0,000014

0,0000010,600000

0,194241

0,047492

0,010854

0,002385

0,000511

0,000108

0,000022

0,000005

0,0000011,000000

0,071547

0,005948

0,000476

0,000037

0,0000031,000000

0,286946

0,073518

0,017228

0,003843

0,000838

0,000176

0,000037

0,000008

0,000002


2. Коммутационный центр. Основными функциями коммутационного центра в сети являются прием сообщения или его части (пакета) из канала связи, запись принятой информации в накопитель, анализ служебной части сообщения или пакета и последовательная его передача в соответствии с адресом получателя. В дальнейшем будем пользоваться термином «сообщение» для обозначения как собственно сообщения, так и пакета, т. е. его части, передаваемой в сети по такому же принципу, что и целое сообщение. В процессе решения перечисленных задач коммутационный центр выполняет множество операций, которые условно можно разделить на три группы: 1) операции по обработке сообщений; 2) операции по управлению сообщениями; 3) операции по обеспечению взаимодействия центра с другими элементами данной сети или других сетей.

Одной из важнейших характеристик коммутационного центра является объем буферной памяти, в которой хранится информация о находящихся в центре сообщениях. Рассмотрим модель определения объема памяти центра, который представим в виде трехфазной СМО (рис. 13), содержащей фазы приема (1), передачи (2) и задержки (3) сообщения.

В рассматриваемой системе память является общим, динамически распределяемым ресурсом. Объемы сообщений будем считать распределенными по экспоненциальному закону: . Сообщения поступают на прием по m каналам, образуя простейшие потоки интенсивности (). Время приема пропорционально объему сообщения, т. е. , где – время приема единицы объема сообщения по i-му каналу.

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


Фаза приема (1)


...








Память ()


...


...


Фаза передачи (2)


Фаза задержки (3)


...


Рис. 13. Схема коммутационного центра


в один из имеющихся n передающих каналов, причем канал с номером j может быть выбран с вероятностью ().

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

Сначала рассмотрим первую фазу (фазу приема). На этой фазе имеется m независимых СМО. Рассмотрим одну из них, при этом в обозначениях параметров будем опускать индексы, означающие номера соответствующих систем внутри данной фазы. Найдем ПЛС ФР объема обслуживаемого в этой СМО сообщения (т. к. только обслуживаемые сообщения на этой фазе содержатся в памяти). Тогда, вспоминая СМО (см. п. 7.7), получаем в принятых нами в этом пункте обозначениях

.

Здесь, очевидно, , где . Из формулы (5.31) следует, что , а из следствия леммы 1 получаем

.


следующая страница >>