Предельные теоремы для процессов обслуживания в сетях с потерями тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи УДК 519.18

КРАДИНОВ Михаил Юрьевич

ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ ПРОЦЕССОВ ОБСЛУЖИВАНИЯ В СЕТЯХ С ПОТЕРЯМИ

01.01.05 — теория вероятностей и математическая статистика

Автореферат

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

Москва — 1991

Работа вьшояона «а кафедре теории вероятяоагеЯ ыеханако-иатеыатического факультета Московского государственного университета имени li.B.Acuoaocoia

Научные руководители: акадешкАН УССР Гнеденко Б.В.,

доктор физино-иатеиатических иаук, в.н.с. Фалин Г.И. .

Официальные оппонентыгдоктор фиэико-цатеыатических наук, в.u.c. Еечияккн A.B. кандидат фивико-ыатеиатических наук доцэнт Ушаков В.Г.

Ведущая организация- Институт Проблем передачи информации

АН СССР

Защита диссертации оостоится " " -Ях^сх^И 1992 г. в 16 чес.05 мня. на заседании специализированного совета Д, 053. (5.04 при Московской государственном университете киони Н.В.Ломоносова по адресу: II9899,ГСП,Москва,Ленинские Горы, ИГУ, механик о-цатсыатическиВ факультет, аудитория 16-24*

С диссертацией иохко ознакомиться в библиотеке иеханико-цатеиатического факультета МГУ им. М.В.Ломопосоза (14 этаг).

Автореферат разослан " ^ " JL<*-((c*£)J? 1992 г.

Ученый секретарь специализироаанного совета Д. 053. Сб. (У* при M Г/ доктор физшсо-иатсмагичвскюс нбук

Т.П.Лукаиенко

г .. о Б Щ;А Я ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теми. В последнее время всвязи с интенсивным развитием информационных сетей (IICY таких например, как цифровые сети интегрального обслуживания, для соответствующих им стохастических моделей особенно остро стоит проблема расчёта характеристик качества обслуживания. Без знания последних невозможно решить задачу проектирования наиболее оптимальных сетей. Однако, описывающие процессы обслуживания для реальных ИС имеют, как правило, болыцую размерность. Что создаёт значительные трудности для на-ховдения точных значений интересующих характеристик, даже в том случае, когда распределение основного процесса обслуживания имеет лультипликативную форму. Среди приближенных методов предпочтение этдаётся тем, которые хотя бы асимптотически точны в некотором 1ределе. Наряду с режимами малой и большой нагрузки для сетей также рассматриваются предельные режимы, сопровождающиеся увели-¡ением размеров моделей. Наиболее характерным для сетей связи пишется так называемый предел при усложнении маршрутизации ( dlvet.se xouting ¿itnii ) . Сначала строгие резуль-

•аты для такого предела были получены Ю.М. Цуховым, Р.Л. Добруши-шм и М.Я. Кельбертом для звездообразных сетей с очередями. За оследние несколько лет появилось множество работ в этом налрав-ении и для сетей с потерями таких авторов, как F. (*. KePElj , '.И. Фалин, w. Wßitfc , Х.в. ZiedLns , P. t/.Huni и др.

о строгие результаты были получены лишь для симметричных сетей С2J> [3], [4]. При этом в общем случае для сетей присущ

. WRiti VV. üßocßihg oufien setWcQ Ls tecjuciedl Цгоы savaxaß ¡jaciüties slmuttaheou^iy ДТ&Т Tech 3 1985. 64. iS0?-18se.

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

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

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

Научная новизна. Подучены следуйте новые результаты:

1. Предложено строго доказанное, специальное интегральное представление для стат. суммы основного процесса обслуживания.

2. Получены достаточные условия и явное выражение для правильного асимптотического поведения стат. суммы в пределе при усложнении маршрутизации.

2. Фалин Г.И. Эргодичность, устойчивость и нечувствительность для одного класса сетей j коммутацией каналов. Пробл. передачи ин!>орм. 1988. Т.24,вип. I.C.74-78.

3. Hunt Р.З. Imp tied, costs ih toss netuAdv. ApfJ. Ptob. 4989.21.661-CW.

4. Ke£Cy R P., Ztedihs I.B. Li^Lt Meoxems [<n ¿o&s. hetcuo-tAs luite divei&e touting. Adv. Appl. fcob. i989.2i.R04-ai»o.

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

4. Приведён алгоритм получения коэффициентов асимптотического раз ло лее ни я по отрицательным степеням параметра сложности маршрутизации для одного класса характеристик.

5. Доказано диффузионное приближение для векторнозначного процесса

(¿)) долей линий с одинаковым чис-

лом занятых каналов ( О,..., К} в симметричной

звездообразной сети с /V линиями. Для приближающего ( К+1) - мерного процесса Орнштейна-УлонЗека получены вектор средних сносов и матрица диффузии. Теоретическая и практическая ценность. Содержание диссертации носит теоретический характер. В то ;.се время, описанный алгоритм получения асимптотического разложения позволяет с высокой точностью определять значения интересующих характеристик. Результаты ЦПТ и диффузионного приближения могут быть использованы для получения оценок вероятностей больших уклонений. Апробация. Результаты диссертации докладывались на XII конференции молодых учёных МРУ в 1990 году, на семинаре "Вероятностные методы в технике" под руководством профессора Ю.К. Беляева, академика АН УССР, профессора Б.В. Пюденко, профессора А.Д. Соловьёва, а также в институте- Проблем передачи информации на семинаре под руководством профессора Р.Л. Добрушина.

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

Структура диссертации. Диссертация состоит из введения, двух глав и списка литературы из 87 названий.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении даётся обзор литературы, относящейся к теме диссертации, и изложены её основные результаты.

Исследуемая сеть структурно состоит из N перенумерован-tiux линий. В линии с номером Ml содержится ^т каналов

K=(Ki• В сеть независимыми пуассоновскими потоками поступают заявки *£ различных типов

Тип заявки определяется, таким образом, маршрутом или набором пар. 1!це первые компоненты в парах определяют номера линий, через которые проходит маршрут, а вторые-числа каналов в каздой линии маршрута, необходимых для обслуживания заявки. Если б момент поступления заявки типа d хотя бы в одной из линий её маршрута недостаточно свободных каналов, то заявка безвозвратно теряется, в противном случае она мгновенно занимает требуемое число каналов во поех линиях своего маршрута на некоторое случайное время со средним единица, по истечении которого считается обслуженной и уходит из системы, освобо'кдая все ранее используемые каналы. Времена обслуживания предполагаются независимыми как меццу собой так и от входящих потоков и одинаково распределены для заявок одного типа. Интенсивность поступления заь ок типа обозначается через

. Кроме того, матрица маршрутизации R состоит из t столбцов и N строк, так что на месте пересечения ¿-oii строки и ¿•~го стол(5ца стоит число каналов, требуемое .заявкой типа ol(i) из ¿"ой линии.

Основным процессом обслуживания является процесс «•осюпния которого суть вектора t1=(lV oi^tJ) , где

lot. интерпретируется как число заявок типа , находящихся на вбслуж.чнашти в данном состоянии.

- л -

Фазовое пространство определяется как ^ • Яп^ к}

Известно Г51 одномерное стационарное распределение процесса:

XV

Ы / »<*

где

2=2: П Х^/п*!

Свякем с каадым типом ( маршрутом) .. (йу две характеристики, длину

и ширину кпсгх £/

Пусть кроме того, с{(оС\ 2(и) '

Глава I посвящена изучению описаншвс выше сетей, у которых с1а2., 2. < °° . в этом случае набор интенсив но стей

удобно представить в виде: р

ЛН Л^' '"р./е^У , где а+Г^'1) ,

,/У; £=<1,. функцию __ г' Пе

И*....,»V :хепе<к

будем интерпретировать как стат. сумму для однолинейной сети. Оказывается, что асимптотические значения характеристик определяются через неотрицательные решения ^ ( называемые также неподвижными точками Зрланга ^ еле дуй.чего нелинейного уравнения:

ХЧАЖЬХ

(2)

ЙЛЫ1° */£*

- )•" О- -»С определяется как:

и

Заметим, что распределение (.1) однозначно определяется параметрами (Л/ ,К ,X. ,Л) . Следующая теорема об интегральном представлении играет ключевую роль в анализе Главы I. ТЕОгеМА I. Пусть з^ЗЛ и ^«(»^^ЗЛ независимые нормальные вектора со средними X и 0 , и матрицами ковариадий

Л

О И

Л. , соответственно, такими что _Л0-_/Ц=Л. • Тогда верно тоджество:

й \) (з)

' ' 1т=1 ч»»>,4) >* ч

где комплексно нормальный вектор £ равен

Заметим, что представлений симметрической матрицы

А

в виде разницы неотрицательно определенных

бесконечно много. Оказывается, что лишь некоторые из них являются наиболее удобными для асимптотического анализа. Определение. Назовём представление матрицы _А.=-

= ^ ( 6,Л&Д, §1,- В^ЬД^. С стандартном

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

Здесь - диагональная матрица с неотрицательными элементами

-их

местах.

5. Ьигтоп Т).Ч.,исЛосгЙи Э.Р. Тп&елИ^^'

с| иосЯ«»ч ti.es т « слгсмИ-ЬШ^Ь&еЫ

£е4соЛ*в З. АррВ. РгоЬ. 43ГЦ. 21. 850-859.

И формула А-Д^.- А_ Даёт представление симметрической матрицы А в виде разности неотрицательно определённых, такое что

1тА+±ЪпА_

В §4 приведён пример последовательности симметричных сотей в случае = , для которых неотрицательное реше-

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

На самом деле, некоторым обобщением результатов £6j показано, что в случае cC=2L £=» неподвижная точка Зрланга единственна. Дальнейшие результаты Главы1 получены именно для последнего случая. И кроме того, далее под представлением _Л_0—_Л_^ понимается стандартное представление, связанное с единственной, таким образом, неподвижной точкой Зрланга X & Обозначим:

&г £ - диагональные матрицы (/V* /V) с элементами

' tfr^Ki^K)-ecfnri ХЛ;L.

на (hijto) -их .местах, соответственно.

а «^nui ~т I ai-trim I ;

d=»hün (da > d^ )

x-T (

d+Xt, )

6. ke&ßu p.p B£ocßihg fnoi oLi iih'es in ßarcge cLtcuii-suälcfced heW/dk. Acfv. Арр£. ЪоЬ. «U.4a. 4?a-sos\ .

- минимальное собственное значение матрицы Б-{Ц-Л-^ 1-0^. Сформулируем условия для последовательности сетей, задаваемых параметрами (Л^К^ЛЛ ,^"■'1,2,... А1. Существует £о>0 такое, что для любых достаточно больших номеров N : £0

А3-3 к ^: (а^еЦь* УЕ'+ о.

Здесь через "Т^с. (обозначен след матрицы А

Следующая теорема устанавливает асимптотическое поведение стат.

суммы из ( I ^ .

ТЕОШ.1А 3. Пусть для последовательности сетей, задаваемых параметрами К", У?, . » выполнены условия А(1-3^. Тогда справедливо асимптотическое равенство при /V—»<х» :

Ъ1ы, к»,Л»,Л» \

Затем, для проверки условия А2 следует вычислять детерминанты матриц увеличивающейся размерности, и это может оказаться достаточно непростой задачей, если к тому же учесть, что в общем случае не существует явных аналитических выражений для элементов матриц _Л_0 и -А-4 , участвующих в стандартном представлении, Чтобы спормулировать более простые для проверки условия А2,АЗ' , обеспечивающие выполнимость А2, АЗ . Обозначим:

^^ - элемент матрицы (» стоящий на (m,mi -ом месте, Ж-d,...,^ *,

Л - значение максимального элемента матрицы

ZUti^kmi» (-%iLY) ' =Т-Г((B4 J. b^MAl.^

4Л сГт /J'f

i* /ч W\-l

аз^— i

В §7 доказана ЦГГГ для случайных величин вида ^ (W^ = sT ' где распределение вектора = олре-

деляется (I) . А матрица и В0КТОР

... состоят из неслучайных элементов Wtf ,

таких что . Определённые mera величины в1

«АеЗ

и d интерпретируются как асимптотические дисперсия и среднее величины

i.+гКыО - (8o-A.w+ Хц,Л(е+АВ3> ^AoJO+AJiV,

И/С-АиЛ-^и -Л- ы1 =( X тт< (7 X Ы1 -(X 4и>1,... ),

ТЕОРЕМА 4.Пусть для последовательности сетей, задаваемых параметрами (/V у^ \ы ) выполнены условия А1,А2, Аз' . И кроме того, для последовательности массивов коэ^ициентои выполнено дополнительное условие:_

Тогда последовательность случайных величин

^"Оа/'^ц/Ч- аы ег"

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

Пусть теперь случайный вектор ^ = ^ ^^ представляет числа занятых каналов в линиях сети в стационарном режиме. В §8 приведён алгоритм, позволяющий получать асимптотические разложения для характеристик типа , где \ - некоторый ограничегашй функционал на

Свяжем с сетью, задаваемой параметрами (Л/^К^Х ,-А.^ следующие величины: 2/ . а

-уо |гйп Г—Ы-—

.....Л(

А=тах Ль»

Пусть также ^Ц^' ~ собственные числа матриц

Ь3А , расположенные в порядке возрастания. Обозначим:

• Следующая теорема устанавливает асимптотическое разложение для стат. cyi.au!.

ТЕОРЕМА 6. Пусть имеется последовательность сетей, задаваемых параметрам (М, К^Л^-Л. ) , А/-4. ,2,... . Тогда'для любого , справедливо разложение:

, и, ¡ы ,»

V1 Гг?5(Лг)^л/)р Л Л )),

где значение функции ('_>'>'; ' ) вычисляется по параметрам сети (/VI и компонентам неподвижной точки Эрланга

с помоп1ью известного алгоритма, и кроме того, для любого

функция равномерно ограничена на

множестве всевозможных параметров сети (м К^Х .

Если же для указанной выше последовательности сетей выполнены условия А(1-3), то последовательность значений (М^ К ]

стремится к нулю.

В Глгаве2 рассматривается последовательность симметричных

сетей (случай с[ - Е — i ) , задаваемых параметрами^

(N, , /V=4,2,... так» чт0 в СХ9,ле серийКтвке7+,

о для любого n=»^2,... • а матрица _д_ состоит из равных элементов Х/Л/ » КР°ма диагональных - равных нулю. Для последовательности стационарных векторнозначных процессов )) • представляю:^« доли линий с одинаковым числом занятых каналов (0,... t к ) , доказана следующая теорема о диффузионном приближении, теорема 7. Последовательность процессов ( Cj)- (Ts1 С-сходится к - мерному стационарному процессу Орнштейна-Уленбека с вектором сносов Ах и матрицей диффузии Пце

К,пГ Щг-с %1{к*к}) +

,если Vb-t+L О .если lm-£l?2

( В последних записях >^-1 Q

Вектор = является усечённым пуассоновским рас-

пределением с параметром Л , который определяется как единственный в IR+ корень нелинейного уравнения: Л°= Кроме того, определение С-сходимости см.СО»

7. Боровков A.A. Асимптотические методы в теории массового обслуживания. М.:Наука,1980.

Заметим, что последняя теорема обобщает ¡юяультаг из 3 3 » гдя она била докатана для сетей с одноияняльными линиями (К=1) .

В качестве следствия получена асимптотика процесса сумарно-го числа потерянных заявок всех типов на отрезке времени СО, ¿7 •

В заключении, автор выражает глубокую благодарность споим научным руководителям, академику АН УССР Б.В. Гнеденко и доктору физико-математических наук Т.Н. Фалину за постановку задачи и внимание к работе.

Основные результаты диссертации опубликованы в работах, указанных на следующей страница.

1. Крадинов М.Ю. О диффузионном приближении симметричных сотей с потерями. Мат. заметки. 1991.Т.50,вып.1.С.141-143.

2. Крадинов М.Ю. Звездообразная сеть связи с потерями при большом числе линий. Функциональный и стохастический анализ и их приложения. М.:МГУ,1991.С.48-51.

3. Крадинов М.Ю. О диффузионном приближении симметричной звездообразной сети с потерями при большом числе линий. Рад. ж. Изв.

АН СССР. Техн. кибернет. П.,1991. 28 е.- Деп. в ВИНИТИ 26.06.91. К? 2717-В91. |

4. Крадинов М.Ю. Сети с коммутацией каналов в пределе при усложнении маршрутизации. Вестник МГУ. Математика и механика. 1992, Г 2.

5. Крадинов М.Ю. Асимптотическое поведение стат. суммы основного процесса обслуживания в сетях с коммутацией каналов и потерями. Деп. в ВИНИТИ. М.,1991. 28 с. 29.11-91 Л/9М 55"- В94. .