автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Исследование точности измерения характеристик в приоритетных системах передачи информации и вычислительных системах

РОССИЙСКАЯ АКАДЕМИЯ НАУК

^ 7 Ф^^СТИТУТ ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ

на правах рукописи

ТРОФИМОВ Дмитрий Петрович

УДК 519.872

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

Специальность: 05.13.01 - Управление в технических системах

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва - 1997

Работа выполнена в Институте проблем передачи информации РАН

Научный руководитель:

кандидат технических наук Е.И. Школьный Е.И.

Официальные оппоненты:

доктор технических наук, профессор В.И. Нейман доктор технических наук, профессор М.А. Шнепс-Шнеппе

Ведущая организация:

Ленинградский Отраслевой Научно-исследовательский Институт Связи.

Защита состоится 1997г. в час. на заседании

диссертационного совета Д.003.29.01 при Институте проблем передачи информации РАН по адресу: 101447, Москва. Б. Каретный пер., 19.

С диссертацией можно ознакомиться в библиотеке ИППИ РАН.

Автореферат разослан' ' 1997г.

Ученый секретарь

Диссертационного совета Д.003.29.01 доктор технических наук, профессор

Степанов С.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Для решения этой задачи необходимо определять дисперсии статистических оценок характеристик систем. Основные результаты в этой области получены А.М. Андроновым. В. Бенешем, А. Деклю, И.Н. Коваленко, А. Костеном, А. Ку-чурой. Г. Линдом. К. Олсоном, Д.Г. Поляком. П.Я. Розенблитом. М.А. Шнепс-Шнеппе и другими авторами.. Общий недостаток этих работ заключается в том. что полученные результаты применимы только для анализа частных случаев систем массового обслуживания. Е.И. Школьному удалось преодолеть этот недостаток и получить результаты применимые для произвольных систем, описываемых полумарковскими процессами с конечным множеством состояний. В данной работе метод, предложенный Е.И. Школьным использован для анализа моделей приоритетных систем передачи информации и вычислительных систем.

Цель работы:

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

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

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

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

5. Разработка методики и практических рекомендаций для решения задач контроля и управления скоростью .передачи данных в канале с учетом точности измерения характеристик. Применение полученных результатов для решения практических задач.

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

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

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

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

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

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

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

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

б) многопроцессорной вычислительной системы с блоками оперативной памяти:

в) многопроцессорной системы с двумя типами оперативной памяти.

3. Исследована точность измерения параметров в системе с потоком телефонных вызовов и потоком сообщений.

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

5. Разработана методика управления скоростью передачи данных в канале, основанная на результатах исследования однолинейной системы с приоритетами. Определена точность управления в зависимости от точности измерений характеристик.

Практическая ценность

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

а) с заданной достоверностью определять ширину доверительного интервала для результатов измерения характеристик в зависимости от времени измерения:

б) вычислять время измерения для получения-статистических оценок характеристик системы с заданной погрешностью:

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

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

2. Построенные оценки дисперсии выборочного среднего позволяют:

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

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

Реализация результатов работы

Разработанная в диссертации методика построения несмещенных оценок выборочного среднего по выборке зависимых одинаково распределенных случайных величин внедрена в МНИИ радиосвязи при проектировании АСУ сети связи.

Методика управления скоростью передачи данных в канале с учетом точности измерения характеристик была внедрена в ГП ВНИИФТРИ на специализированной сети передачи данных.

Апробация работы

Основные результаты работ доложены и обсуждены на: XIII Всесоюзной школе-семинаре по вычислительным сетям (г. Алма-Ата, 1988г.), 3-ем международном семинаре по теории телетрафика и компьютерному моделированию (Болгария, София, 1990г.)„ 4-ом международном семинаре по теории телетрафика и компьютерному моделированию (г. Москва, 1992). Результаты диссерта-. ции неоднократно докладывались на научных семинарах в ИППИ РАН.

Публикации. Основные результаты диссертации опубликованы в 9 работах.

Структура н объем работы. Диссертация состоит из введения, пяти глав, .заключения и списка литературы с 142 наименованиями. В приложении приведены акты о внедрении и использовании результатов диссертации. Она имеет 134 стр. основного машинописного текста и содержит 18 рисунков.

СОДЕРЖАНИЕ РАБОТЫ Во введении дается обзор результатов исследования точности различных оценок характеристик в системах массового обслуживания. Обосновывается актуальность, теоретическая и практическая необходимость исследования точности измерений характеристик и управления в системах с приоритетами и вычислительных системах. Кратко излагается содержание диссертации по главам.

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

Модель (рисунок 1) представляет систему, состоящую из 'у линий и двух накопителей емкости /I/ и )ь . В систему поступают пуассоновские потоки телефонных вызовов и сообщений интенсивности и л : соответственно. Вызовы обслуживаются с абсолютным приоритетом. Время обслуживания каждого вызова име-

г^-^ А

экспоненциально« распределение с параметром (процесс обслуживания вы-вов такой же, как в системе М/М/у/п/).

При уплотненном способе обслуживания (первая модель) каждое поступившее сообщение занимает все к линий, щ . не занятых вызовами, на время, распре* деленное по экспоненциальному закону с параметром к/}:. Если свободных ли-

Я,

1 2 Я/

2 л?

Рис- 1 ний нет, то поступившее сообщение за-

мает одно место в накопителе емкости т. При отсутствии свободных мест соо-дение теряется.

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

Марковские процессы /(г) , описывающие функционирование систем, опре-

глены на множестве состояний / = (/,,/,) бб, где /, = 0,у + л, -суммарное число

мест для ожидания, занятых вызовами, а /, = 0, л, +• х

X = / при I, < V и / = 0 при /', > V), (', = 0,л, + V - тт((,.') -число сообщений в си-геме для первой и второй модели соответственно.

Определены статистические оценки ¡гк{1) . к = 1.4, соответствующие непре-ывному измерению за время I следующих характеристик систем: средней загрузки истемы вызовами, вероятности потерь вызовов по времени, вероятности потерь о вызовам (или коэффициента потерянных вызовов), среднего времени передачи ообщений. Оценки имеют вид отношений процессов накопления /г,(/) = 5,(/)/*, л-,(0 = 5,(/)//, л-ДО = 5,(0/5,(0. »г, (0 =

де 5,(0 = ] тт(/,(г).1-у/г - загрузка линий вызовами, 5;(0 - время пребывания

ч

фоиесса /(г) в состояниях блокировки вызовов / ~В = {/: /', = г - л,} с С, 3.^1) -шсло потерянных вызовов в состояниях / = В. $'40 - число всех поступивших в систему вызовов. 5>(/) - суммарное время ожидания и передачи сообщений. &,(') - чи-:ло поступивших в систему сообщений за время /.

и

При получении результатов первой и третьей глав использованы работы Е.И. Школьного, где исследованы статистические оценки характеристик полумарковских систем с конечным множеством состояний вложенной цепи Маркова. Оценки имеют вид отношения процессов накопления к(1) = Sr(t)I Sf(t), являются

состоятельными, асимптотически несмещенными и асимптотически нормальными, а их математические ожидания и дисперсии при t -> со определяются равенствами: Ш(0 = в = Mh(r)/ Mi(f) = MS(r)/MS(f), Dx(t) = d/t+o(l/1), где (2)

d= MS(0) MS1 i(MS(/)Y •

где величины *A(r) являются накопленными за один шаг процесса /(г) частями величин 5г(0. а случайные величины S(r), S, означающие накопление одношаговых величин Л(г) и Л = h(r) - 6h(f) соответственно за период регенерации процесса /(г), определяются стохастическими равенствами

S(r) = к,(г) + £хцSt(г). S = А, + 2Z„S„,tsG. (3)

i«; ¡«1

где z„- = 1 при условии, что процесс /(г) перешел из состояния / в состояние j за один шаг. Хц-0 в противном случае: Sf (г), St - случайные величины, означающие накопление одношаговых величин А(г) и А соответственно за время первого перехода процесса /(г) из состояния / в состояние у, а условные случайные величин к; (г). h:i(r). h,. Л,, имеют функции распределения:

P\h,(r) < л] = P{h(r) < д | /(г,) = / = (/,./,)}.

P{lhl(r) < л] = P\h(r) < л*| /(г,) = / = (»,./.)./(г.) = j = (у,.;.)}.

P[ll, < Aj = P{h < A'| /(Г,) = ! = (/,,/,)}. (4)

P{h„ < Л} = P[h < лI /(Г,) - / = (/,./.)• /(Г;) = j =

где г, иг, - последовательные моменты скачков процесса /(г). Моменты случайных величин S;, (г), 5„- определяются системами уравнений: =ЛЛ, , /е G, t * А',

НО

л:- - " - - ------- - - (5)

/{5. ]"' - X Л,- фд- ]"' =-X А,[ Л*/„ ЛС, ] + Л-/[Л, ]: . / е С. / X /с.

/ в Лг Г*к

где р., - вероятность перехода из состояния / в состояние у. Для марковских систем равенства (2). (5) принимают вид

Mx(i) = 0 = Цг) / Ц/), Dn(i) = dlt + o(]lt), где "

tec [ на ]

(6)

л/ Що lV{Sj0 =Л1 Щ • ' е С, / * О,

JtG /*>

где /} = P(ini:) - стационарные вероятности состояний i = (t,./.) 6 С марковского процесса/(г), - интенсивность перехода процесса /(г) из состояния ( = (/,,/,) в

состояние j - (у,,/.). Л, = интенсивность выхода процесса /(г) из состоя-

ла

ния / = (/,,/;) • Величины 5i0 означают накопление леличин h за время пер'вого перехода процесса/(г) из состояния у = (7,,)',) в состояние (0.0).

Для двух моделей были получены системы уравнений равновесия относительно стационарных вероятностей Р, процесса /(г), вычислены моменты случайных величин h(r), h^r), г - 0.6, для каждой из статистических оценок (1) вычислены моменты соответствующих случайных величин h,, а также получены системы уравнений (б). Например, для первой модели (уплотненное обслуживание) и статистической оценки л-Д/) моменты случайных величин определяются равенствами:

Щ (0) = Щ(0) = // А, . Ци,(0)]' = 2 / (А, ): .

Mh„(Г) = Щ{Г) = min(/',.v)/A, , .Vi[/i,(/)]"' = 2[rmn(/,.v)]-' /(А,): . (7)

.Цл,.]' = /[(min(;,, v) - #)/ Af ]', а система уравнений (б) примет вид

[-Ы, +min(/,.v)/?, (v - min(i,.v))(/-0)0:]X(i,.;,)-{<*,X(i, + /,/, -¿J +

л,X(/,,/: +D + P, min(/,,v)X{j, - U,) + (v- min(/,,v))01 (I- 0)X(i,,i, - /)} = {л, -¡-Я, + min(/,,v)/?, + (v-mm{i,,v))P:}Mh, , i, =0,v+n,, = 0,n, +/,,/-(0,0),

где X{i,.i.) = MS:0 . Ш; определяется из (7), через д . к = /.-/. обозначены индикаторные функции подмножеств

О, = {/': /, < V}, Ог = {/: /, < у + л,},

О, = {/: /, </»,+*,}, С, = {/:/, = V-/, /,

множества состояний С процесса /(г).

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

Алгоритм вычисления математических ожиданий и дисперсий статистических оценок як (0. Л = и статистических оценок параметров систем реализован в пакете программ на языке РЬ-1, с помощью которого получены численные результаты.

рис. 2 рис. 3

Например, на рисунках 2 и 3 приведены кривые 1-3 значений среднего времени Г передачи (ожидания и обслуживания) сообщений и главных членов с/ разложений дисперсии £>/Т,(/) = г+о(У/1) соответствующей статистической оценки ,т,(|) для пучков, состоящих из V = 10 (1-ая кривая), г = 25 (2-ая кривая) и V = 50 (3-я кривая) линий. На пучки поступают потоки вызовов интенсивности л, = 4. л, = 15 ил, = 36 соответственно. Остальные параметры определяются равенствами п, - 0. п. = 50, Р, = /./?,= ¡20. <2 = 0 (все интенсивности выражены в единицах средней длительности обслуживания вызовов) . На рисунках 2 и 3 кривые для уплотненного способа передачи сообщений - сплошные, для неуплотненного - штриховые. Значения Л. представлены в числе сообщений в секунду, Г в [е.]. с/ в [с.'].

Из рисунка 2 видно, что средняя длительность передачи сообщений в режиме уплотненной передачи всегда меньше, чем при неуплотненной. Например, по пучку V = 50 линий при одинаковом качестве обслуживания Т=2.4 с. в уплотненном

режиме передается в 4.5 раз, а при Т=3.3 с. почти в два раза больше сообщений, чем в неуплотненном режиме.

Все результаты первой главы новы и опубликованы в [1,4]. Во второй главе предложен метод вычисления дисперсий косвенных статистических оценок характеристик узлов марковской замкнутой сети массового обслуживания (ЗСеМО). Для частных случаев ЗСеМО получены рекуррентные формулы дисперсии оценок характеристик сети.

Рассмотрена модель экспоненциальной ЗСеМО, состоящей из т узлов. В ней обслуживается конечное число заявок, равное п. Время обслуживания заявок в к-

4

ом узле подчиняется экспоненциальному закону с параметром лС/)=а»С/)|'*> где к = ¡.т - номер узла, ] = 0, л - числе заявок в узле, <аг1С/) - целочисленная неотрицательная функция от к и у такая, что а4(0)=0. Заявка, обслуженная в ¿-ом-узле, с вероятностью Ой < /, = /),£ = 1,т, переходит в узел I = 1,т. В час-

тности, с вероятностью Он 2 0 в-¿-ом узле происходит повторное обслуживание заявки.

Обозначим через ¡к{т) число заявок в ¿-ом узле в момент времени г, г >0. Тогда векторный случайный процесс У(г)={^(г), к = /,//)}, определенный на

пространстве состояний С(л)={/: = 0.1.....л. Л =/,/м,/,+...+/„= л} и описывающий функционирование ЗСеМО, является марковским.

В многочисленных работах, посвященных исследованию ЗСеМО получены формулы и системы уравнений для вычисления стационарных вероятностей Р(/), / еС(л), марковского процессаУ(г)

шп = У<Г> / у ^ т

и мт/,к>митл'

гле

."(о=П /?(/)=ПГКсо. Р>

<=/ к=1 1=1 к,1

при любом заданном значении у/ величины ук,к = 2,т. являются единственным решением системы уравнений

"I <2, к = Тт (10)

и средних характеристик для отдельных узлов сети:

= (i-Q*)nt вк2 = до. в„ = ек:1>вк,, /с=/.m. (iо

¡«С(л> I «G<»>

где и = / J, - это соответственно интенсивность потока заявок, поступающих в узел из других узлов (при и»/), математическое ожидание числа заявок (при и-2) и времени пребывания заявок в к-м узле (при и-З).

Для каждого значения к обозначим множество индексов / в Qu через

. С„ ={/: 0 < Qn < 1,1 = Л/я}. Рассмотрим одноточечное подмножество Ак с Ct и

д

множество Вк=Ск\Ак . Тогда величина Q^, I еАк зависит от остальных независимых величин Qj, I еВк (2« = 1~1lQu> к= I,m, I

(«а,

Заметим, что характеристики (11) являются функциями от параметров Mi' Qw I е Вк, к = 1,т. Поэтому можно получить (косвенные) статистические оценки к= l.m, а= 1,3, характеристик 6^ путем замены з равенствах (1!) параметров juk, Qu, I б Вк, к = l.m их статистическими оценками

Mt (0 = Sk (0/S* (0 .&(') = Su (0/Sk(0 • (12)

где Sk(t) - число освобождений приборов к-го узла, 5, (f) - суммарное время пребывания заявок в к-м узле, £«(/) - число переходов заявок к-го узла в /-й за время измерения t.

Используя результаты Е.И. Школьного для вычисления моментов статистических оценок параметров марковских систем, доказано, что оценки (12) состоятельные. асимптотически нормальные и асимптотически несмещенные, дисперсии и ковариации оценок (12) при i х определяются равенствами Dft„ (0 = dUk 11 + o(l / t). DQ* C*> = dQJt+o(U /). сЦ&,(0.а.,] = сщ/г+е>(//0. I.JeBt. k^TJiuUj,

(13)

где

d.. =

= /<,/ Уак(1к)Р(Г), =(/-&)&/U Ze»(W)

/ 1ч<7(И / N

Си = aa/i,"* o(//0 —>0 при / -> х.

(14)

Все остальные ковариации между оценками ut.(i). Qyii), I еВ.К, А: = l.m, равны нулю.

Показано, что оценки к = 1,т, и= и, являются непрерывными функ-

шями от оценок (12). Кроме того, у этих функций имеются непрерывные первые и ггорые производные по всем оценкам параметров (12) и существует окрестность

■очки ({лк, Qy, I к = 1,т) в которой выполняется равенство (л^С/)) < О', где

7 и р - неотрицательные постоянные. Доказано, что из этих условий следует сос-•оятельность, асимптотическая нормальность и асимптотическая несмещенность щенок к = 1,т, и =1,3, а дисперсии этих оценок при I—юо определяются

>авенствами

^(0 = ^/1 + 0(1/1). « = 75, к = Тт,

де ê9tu/âQ/=0, j е=4 ,i-l,m. __ _

Вычислены главные члены разложений дисперсий и ковариаций статистичео :их оценок параметров ЗСеМО (14), получены формулы и системы уравнений для 1ычисления частных производных в (15) характеристик (11) по параметрам / sS,, к ■= ¡.т. Алгоритм реализован в пакете программ на языке Pascal, "[олучены численные результаты.

В главе рассмотрены три частных случая ЗСеМО. для которых получены ре-:уррентные формулы для вычисления моментов статистических оценок гь(1), к = 1,т, и = 1,3.

Все результаты второй главы новы и опубликованы в [3, 5-9].

В третьей главе исследованы две модели однолинейной системы с относи-ельным и абсолютным приоритетом.

Для модели с относительным приоритетом на обслуживание поступают два |езависимых пуассоновских потока сообщений интенсивности и В случае, :огда при поступлении на обслуживание сообщения /-го потока. 1= 1,2, система за-1ята, поступившее сообщение занимает одно из мест в накопителе емкости Поле освобождения линии на обслуживание поступает сообщение первого потока, •ели первый накопитель пуст, то на обслуживание поступает сообщение второго ютока. Время обслуживания сообщений /-го потока. 1=1.2. имеет функцию расп->еделения F/nj.

Рассмотрим моменты времени г„, г, = h'k~:'(0)+ rt_, , к> 1. сразу после окон-1ания обслуживания сообщений и после прихода первого сообщения в пустую си-

схему, где Л1*'(0) - интервал между последовательными моментами rt и rt,,. Обозначим через /,(г), / = 12, число сообщений первого и второго потоков соответственно. находящихся в системе в момент времени г, через S(t) = raax(A:rt <t) - номер последнего из моментов времени zt таких, что они попали в интервал [O.t], а через

ЖО={й(0),Л(О.....wo» Об)

- вектор случайных величин, где h(0) = t- тзи1 - время от момента последнего из событий rt до текущего момента времени; h(l), h{3) - суммарное время пребывания всех сообщений первого и второго потоков соответственно в системе за интервал времени А(0): Л(2), h(4) - число поступивших на обслуживание сообщений первого и второго потоков соответственно за время Л(0): h(5), h(7) - число потерянных сообщений первого и второго потоков соответственно за время h(0); h{6), h(8) - число всех пришедших сообщений первого и второго потоков соответственно за время h(0) (h(6) = h{2) +h(5), h{8) = h(4)+h(7))\h{9), h{10) - время занятия канала сообщениями первого и второго потоков соответственно за время Л(0). Опи-

__ а

сывающий функционирование системы процесс~J{t)={i,{9{t)),i,{9(l)),H(t)}. определенный на пространстве состояний G х [О,со)", где С = {(/,,/;): I, = 0,л,, /, =0,п:)

является полумарковским. ~ ......

Вычислены переходные вероятности вложенной в процесс У(г) цепи Маркова J(rk) = (i,(Tk),i:{rt)). к > О и вероятности перехода при условии, что интервал между скачками равен V.

РЧМ, = = <J,J:P^o) = (',.';)}•

Лу:,,,;(0 = Р{Ат,) = = (i„/,). r,-r0 = t}.

(17)

Например, вероятность перехода из состояния (0,1.) в состояние (л,,л.) определяется равенствами

Г- ~ ' . „ (Л,и)*' (л,i/)'-

=J I X :.; ; dF:(u) = i-ф;(л..А-:)-

„.-,.„,-!. к, ¿к. 0°) У -/'тФ.(л;.А-,)- У Zfri^T0-^.' + *•>. >0-

где Ф,(а.к) = je ■"'и*dF,(и). / = /J.

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

1ения одношаговых случайных величин (16) за время /.

Из (2)-(5) следует, что (19) являются состоятельными, асимптотически нормальными и асимптотически несмещенными оценками соответствующих характеристик. Кроме того, из (2)-(5) следует, что для вычисления математического ожи-1ания и дисперсии оценок (19) достаточно вычислить моменты одношаговых слу-<айных величин (4). Тогда подставив-их в (5) и решив системы уравнений (5) из (2), 3) получаем моменты статистических оценок (19).

Для вычисления моментов случайных величин-(4) доказана Теорема. Пусть на временном интервале [О.и) поступило к сообщений пуас-гоновского потока интенсивности л . Сообщения поступают в случайные моменты зремени 0 < и, < и, <...£ ик < и. к = ¡2.... Тогда первые два момента случайной ве-

тчины а(и.к.1) = У, (м "",»)' означающей суммарное время ожидания первых к-1

:ообщений до момента окончания временного интервала и, определяются равенствами

*,(«) = 5,(0/5,(0. *;(0 = <0/5,(0. *,(0 = 5,(0/5,(0. Л-ДО = 5.(0/5,(0. *з(0 = 5,(0/5,(0. МО = 5,„(0/5,(0.

(19)

процессов накоп-

Ш(и,к,/) = и(к- !)(к + / + 1)/{2(к + /)).

Ма:(и.к.Г) = г (к - ¡)[Зк3 + (Ю + ЗГ)к: -г (-31: +4/ + 9)к -

31* - 141: -91 + 2)1 [12{к + 1)(к -г 2)]. к>1> 0.

:20)

Обозначим через И"] (г), г - 0.10. случайные величины, имеющие функцию

распределения

Р{1С:,ЛГ) < *} = < = С',./;). Дт,) = (У/.У:). Т, - Г, =

(21)

Гогяа из (17), (21) и формулы полной вероятности получаем равенства:

= I Ч^.^Г^Ь - г° < ^^ = ДО = С/,.Л)}.

/>{г, - г, < /|У(г0) = (/,,/,). Дт,) = (у,-Л)} = р{г,-та < г.У(г„) = (/„/,),

Дг,) = (У/.Л)} / Р{Л*о) = (<'м<А Дг,) = О'/.Л)} = Р[г, - < Дг,) = (у„у;} Дг») = С,.¿;)) / ф(г,) = О',,Л)!Дг0) = (.'„/,)} =

]>{г,-г„ < Г.ДГ,) = = ('/.':). Г, - г„ = =

¡Рч

а

Введем обозначения:

£(/)(л,/л<5)= Ма(и.к.1)/и+й g^3\n,i,k,S) = Ма!(и,к,1)1и: +

\к-п+1-5 при&2л-/ + £, (23)

ИМа(и,к,[)!и+1 , где / = <„ ...

4 ' [0 приА<л-1+<5.

Из (20)-(23) вычисляем моменты случайной величины (Г):

и.-'ЛиЛр^ +/+0- (24)

/ = /.2, I, > 0.у, < л,, у_, < л,. Моменты остальных одношаговых случайных величин вычисляются аналогично.

В третьей главе рассмотрена также модель системы, в которой сообщения первого потока обслуживаются с абсолютным приоритетом и занимают линию на время, распределенное в соответствии с функцией (процесс обслуживания сообщений такой же как в системе МЮ/1/п ). Поступившее на обслуживание сообщение второго потока занимает линию на фиксированное время с/ (ниже будем называть сообщения второго потока пакетами). В случае, когда при поступлении пакета система занята, а также при прерывании обслуживания пакета поступившим в систему сообщением первого потока, пакет занимает одно место в накопителе емкости >ъ .

Рассмотрены моменты времени г,, г* = Ла'"(0) + г4_, , к > Л сразу после окончания обслуживания сообщений и пакетов, после прихода пакета в пустую систему, а также после прихода первого сообщения в систему (в системе нет сообщений. но могут быть пакеты). Вектор (16) и величины /ДО,/,(;).5(') определяются также как и для системы с относительным приоритетом. Тогда процесс

Д1)={1,(Э(1)\1:(Э(0),Н(1)) • определенный на пространстве состояний 0х[0,х)",

Л ___

■де (7={(/,./.): I, = У,л,, = 0.п.) является полумарковским. Нетрудно убедиться, что

Г/"(О при / < й, ГО при г < с1.

■ функции распределения интервала между поступлениями сообщений в систему, времени пребывания процесса /(г) в состоянии (0,1.), ¡, > 0 и времени обслуживания пакетов соответственно. Тогда из (17), (25) и с учетом равенства

]Г е~и - 1 находим вероятности перехода вложенной цепи Маркова:

к*о к.

** ^ (л /V-"'-* 3 У;-1; *

?.„„ - ¡^»«»'■{йг**»'^;^

»•-о Д '•/ X *•• _ _

X X + = Ал,, 1; = О.П.,

где Ф,(а.к) = |е''" ¡1^^(11). I = /2. Остальные переходные вероятности вычисля-

а

кзтся аналогично (26).

Рассмотрены статистические оценки (19). вычислены моменты одношаговых случайных зеличин. составлены системы уравнений (5) и получены математические ожидания и дисперсии статистических оценок (19).

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

Пусть л;, ..V.......-выборка из п зависимых одинаково распределённых

случайных величин (з.о.р.с.з.) с неизвестным средним значением ¡л. Предположим. что существует такое т (0 <т<п-1). что выполняются равенства:

СОУ^.Л)) = -м)(Х/-м)} = о. = 1,п, \i-Ji > т, (27)

где соу и М означают ковариацию и математическое ожидание.

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

соу(х1,х,.11) = соч{х1.х^к) = ск, (,; = 1.п - к. (28)

Введём обозначения:

я-к

■ Ы1 ;•/ ы1

Л-* _

Л = X! - -Ч ХЛ.* - -V ) > (Л - к), ^ = СОУ(,Г, , .г,.).

(29)

Из (27)-(29) получена система уравнений:

с= МА + З. Вс = ЫА. (30)

где с-(с0,с1.....ся). Л = (</„.(*,.....О, А = (4,.А,.....А„) -вектор-строки, а с, А -

транспонированные вектора. В означает матрицу с элементами Ьа . определяемыми равенствами:

тах(л - 2к.О)

(п-ку

шах(л - 2к + /.О) + тах(л - 2к - /,0) 3*--^р-

п-к + тах(л - 2к - ¡.0) ои--;-—-. /> к.

(31)

где А'.;' = О.т. и ¿>и =

{п-ку 1 при / = к.

[О при 1 ?= к.

Введём обозначения:

с' =В'Л. <=с>Я;. (32)

Переходя к математическим ожиданиям в (32) и учитывая (30) получаем равенства:

Л/с1 = с. Ш'„ = л",. (33)

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

Известно, что оценки ковариаций элементов выборки Ак. к = (Кии являются состоятельными и асимптотически нормальными при п х. Построенные оценки

Ьн =

(32) являются линейными комбинациями от величин Лк, к = 0,т. поэтому они также являются состоятельными и асимптотически нормальными при п -> =о.

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

Все результаты четвертой главы новы и опубликованы в [2].

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

Приведён пример внедрения предложенной методики на специализированной сети передачи данных в ГП ВНИИФТРИ. Методика содержит: графики значений среднего времени обслуживания сообщений, вероятности потерь сообщений. загрузки системы сообщениями первого и второго потоков, графики доверительных интервалов для статистических оценок характеристик системы при фиксированной длительности измерения, а также алгоритм их использования для управления системой.

Основные результаты пятой главы новы.

Основные результаты диссертации состоят в следующем.

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

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

3. Для нескольких частных случаев замкнутой сети массового обслуживания результаты получены в виде формул. Для остальных моделей полученные алгоритмы реализованы в пакете программ на языках PL-1 и Pascal. Численные результаты представлены в виде таблиц и графиков и проанализированы.

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

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

Список работ, опубликованных по теме диссертации

1. Школьный Е.И. . Трофимов Д.П. Точность измерения характеристик в системе с приоритетным и уплотненным обслуживанием/УХШ Всесоюзная школа-семинар по вычислительным сетям. Часть 2. Москва-Алма-Ата. 1988. С. 289294.

2. Трофимов Д.П. Построение несмещенных оценок дисперсии выборочного среднего и ковариаиий элементов выборки зависимых одинаково распределенных

случайных величин// 3-th International seminar on teletrafic theory and computer modeling. Bulgaria. Sofia. 1990. 3 c.

3. Трофимов Д.П. Точность измерения характеристик замкнутой сети массового обслуживания с двумя узлами // Анализ систем информатики. М. Наука. 1991. С. 82-88.

4. Школьный Е.И., Трофимов Д.П. Точность измерения характеристик в системе с приоритетным и уплотненным обслуживанием // Анализ систем информатики. М. Наука. 1991. С. 71-81.

5. Трофимов Д.П., Школьный Е.И. Точность измерения характеристик в замкнутой сети массового обслуживания // Перспективные средства телекоммуникации и интегрированные системы связи. Часть П. М. 1992. С. 292-298.

6. Трофимов Д.П.. Школьный Е.И. Анализ точности измерения загрузки многопроцессорной системы // Там же. С. 299-305.

7. Трофимов Д.П. Дисперсия статистической оценки загрузки процессоров вычислительной системы с двумя типами оперативной памяти // Там же. С. 306-310.

8. Школьный Е.И.. Трофимов Д.П. Дисперсия статистической оценки загрузки процессоров вычислительной системы // Proc. 4-th International Seminar on Teletrafic Theory and Computer Modeling. Moscow. 1992.

9. Трофимов Д.П., Школьный Е.И. Статистика замкнутой марковской сети массового обслуживания // Автоматика и телемеханика. 1995. №2. С. 57-66.

Личный вклад автора в совместных работах [1, 4-6. 8.9] выделить невозможно. результаты принадлежат в равной степени каждому из соавторов.

Приложение содержит документы о внедрении диссертационной работы.