Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона

Предложены новые методы анализа характеристик многоскоростных систем типа Гимпельсона, в которых обслуживаются заявки двух типов – узкополосные (n-заявки) и широкополосные (w-заявки). Обслуживание n-заявки осуществляется одним каналом, а для w-заявки требуется одновременно m каналов, m > 1. Заявк...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2005
Hauptverfasser:	Меликов, А.З., Фаттахова, М.И., Казиев, Т.С.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2005
Schlagworte:	Методи оптимізації, оптимальне управління і теорія ігор
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/13809
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона / А.З. Меликов, М.И. Фаттахова, Т.С. Казиев // Систем. дослідж. та інформ. технології. — 2005. — № 2. — С. 83-96. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859708947084083200
author	Меликов, А.З. Фаттахова, М.И. Казиев, Т.С.
author_facet	Меликов, А.З. Фаттахова, М.И. Казиев, Т.С.
citation_txt	Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона / А.З. Меликов, М.И. Фаттахова, Т.С. Казиев // Систем. дослідж. та інформ. технології. — 2005. — № 2. — С. 83-96. — Бібліогр.: 15 назв. — рос.
collection	DSpace DC
description	Предложены новые методы анализа характеристик многоскоростных систем типа Гимпельсона, в которых обслуживаются заявки двух типов – узкополосные (n-заявки) и широкополосные (w-заявки). Обслуживание n-заявки осуществляется одним каналом, а для w-заявки требуется одновременно m каналов, m > 1. Заявки обслуживаются в режиме без ожидания. Разработаны достаточно простые алгоритмы для расчета и оптимизации вероятностей потери разнотипных заявок при различных стратегиях доступа в каналы. Приводятся результаты численных экспериментов. New methods for analysis of characteristics of multirate queues of Gimpelson’s type are proposed. In these queues wide-band (w-call) and narrow-band (n-call) calls are serviced. For servicing n-call a single channel is required while for servicing w-call m channels, m > 1, required simultaneously. Calls are serviced in nonwaiting manner. Simple algorithms for calculation and optimization of loss probabilities of calls of different types under different channel access strategies are developed. Results of appropriate numerical experiments are given. Запропоновано нові методи аналізу характеристик багатошвидкісних систем типу Гімпельсона, у яких обслуговуються заявки двох типів — вузькосмугові (n- заявки) та широкосмугові (w-заявки). Обслуговування n-заявки здійснюється одним каналом, а w-заявка потребує одночасно m каналів m > 1. Заявки обслуговуються в режимі без очікування. Розроблено доволі прості алгоритми розрахунків і оптимізації ймовірностей втрати різнотипових заявок при різних стратегіях доступу до каналів. Наведено результати чисельних експериментів.
first_indexed	2025-12-01T04:40:31Z
format	Article
fulltext	 А.З. Меликов, М.И. Фаттахова, Т.С. Казиев, 2005 Системні дослідження та інформаційні технології, 2005, № 2 83 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 519.872 ЧИСЛЕННЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ МНОГОСКОРОСТНЫХ СИСТЕМ ОБСЛУЖИВАНИЯ ТИПА ГИМПЕЛЬСОНА А.З. МЕЛИКОВ, М.И. ФАТТАХОВА, Т.С. КАЗИЕВ Предложены новые методы анализа характеристик многоскоростных систем типа Гимпельсона, в которых обслуживаются заявки двух типов – узкополос- ные ( n -заявки) и широкополосные ( w -заявки). Обслуживание n -заявки осу- ществляется одним каналом, а для w -заявки требуется одновременно m ка- налов, 1>m . Заявки обслуживаются в режиме без ожидания. Разработаны достаточно простые алгоритмы для расчета и оптимизации вероятностей поте- ри разнотипных заявок при различных стратегиях доступа в каналы. Приво- дятся результаты численных экспериментов. ВВЕДЕНИЕ В широкополосных цифровых сетях интегрального обслуживания (Broad- band Integrated Service Digital Networks, B-ISDN) обрабатываются сообще- ния с различными требованиями к качеству обслуживания (Quality of Ser- vice, QoS). Так, например, речевой трафик имеет скорость передачи порядка нескольких Kбит и не может буферироваться (т.е. пакеты речевой информа- ции не могут ждать в буфере), в то время как высокоскоростные данные передаются со скоростью в десятки Mбит, и пакеты этих данных буфе- рируются. Для удовлетворения существенно различных требований к показателям QoS в реальных B-ISDN используются разные механизмы обслуживания. Один из них — изменение числа каналов (полос) из общей группы (супер канала) для разнотипных сообщений. Исследования моделей систем, в которых разнотипные заявки требуют случайного числа каналов одновременно, актуальны благодаря широкому использованию сетей с указанным механизмом обслуживания. Они называ- ются мультиресурсными (Multi-Resource Queue) или многоскоростными (Multi-Rate Queue, MRQ). Такие модели интенсивно исследуются в послед- ние три десятилетия. Обзор работ в этом направлении по состоянию на 1995 г. можно найти в [1,2]. Анализ литературы после указанного срока полностью подтвердил высказанное в работе [2] предположение о том, что исследования моделей MRQ окажутся центральными в прикладной теории А.З. Меликов, М.И. Фаттахова, Т.С. Казиев ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 84 систем обслуживания. Для краткости изложения укажем лишь монографии [3–5], почти полностью посвященные исследованию моделей данного типа и опубликованные после отмеченных обзорных работ. В настоящей работе исследуются модели MRQ с чистыми потерями, в которых заявки обслуживаются в режиме без ожидания: если в момент по- ступления заявки любого типа отсутствует необходимое количество сво- бодных каналов, то она теряется. Очень вероятно, что первой опубликован- ной серьезной работой в этом направлении, была статья Гимпельсона [6]. Потому MRQ данного типа будем называть моделями Гимпельсона. В работе [6] изучается модель MRQ, в которой на N каналах обслужи- ваются заявки двух типов – узкополосные (narrow-band, n -заявки) и широ- кополосные (wide-band, w -заявки). При этом n -заявка обслуживается лишь одним каналом, а для обслуживания одной w -заявки требуется одновре- менно m каналов, Nm ≤<1 . В этой работе для расчета стационарного рас- пределения модели используется итерационная процедура Гаусса-Зейделя, после чего показатели QoS (т.е. вероятности потери разнотипных заявок) вычисляются известным способом. Такой метод расчета показателей QoS системы достаточно трудоемкий при больших значениях N , что характерно для современных B-ISDN. В настоящей работе исследуются модели Гимпельсона с чистыми поте- рями при двух широко распространенных стратегиях доступа к каналам, отличных от полнодоступной стратегии (Complete Sharing, CS) [7]. При ис- пользовании CS-стратегии доступа поступившая заявка любого типа при- нимается системой, если в данный момент для ее обслуживания имеется до- статочное количество свободных каналов, и поэтому следует ожидать, что w -заявки будут теряться чаще, чем n -заявки. С целью защиты w -заявок рекомендуется использовать стратегию, ограничивающую доступ n -заявок в каналы (Restricted Access, RA) [8]. Другая превентивная мера защиты w - заявок от частых потерь — использование стратегии резервирования кана- лов (Trunk Reservation, TR) [9]. Эффективный алгоритм расчета вероятностей потерь при CS-стратегии доступа дан в работе [7]. Этот алгоритм улучшен (в смысле степени слож- ности) в [10]. В [8] разработан алгоритм расчета для RA-стратегии доступа, основанный на быстрых преобразованиях Фурье. В [9] аналогичный алго- ритм (но приближенный) разработан для TR-стратегии доступа. Он также с использованием подхода, предложенного в [10], улучшен и применен для оптимизации исследуемых моделей в работе [11]. В настоящей работе предложен единый подход к исследованию много- скоростных моделей Гимпельсона с чистыми потерями при RA- и TR- стра- тегиях доступа в каналы. Важно отметить, что предлагаемый подход отличается от известных [8, 9] и основан на принципах теории фазового укрупнения стохастических си- стем [12]. Как будет видно ниже, он оказывается эффективным в силу своей простоты, так как его применение не требует сложных математических пре- образований. Отметим, что модели, в которых каналы, обслуживающие w -заявки, могут работать лишь в определенных сочетаниях (т.е. эти каналы должны быть соседними), были исследованы в [13,14]. Модели последнего типа с помощью имитационного моделирования были изучены еще в работе [6]. Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона Системні дослідження та інформаційні технології, 2005, № 2 85 1. МЕТОДЫ РАСЧЕТА МОДЕЛИ ПРИ РАЗЛИЧНЫХ СТРАТЕГИЯХ ДОСТУПА В данной работе исследуются марковские модели MRQ, т.е. входящие тра- фики считаются пуассоновскими и времена обслуживания заявок являются показательно распределенными случайными величинами. Введем следующие обозначения: nλ ( wλ ) — интенсивность потока n - заявок ( w — заявок); nµ ( wµ ) — интенсивность обслуживания n -заявок ( w -заявок). 1.1. Расчет модели при RA-стратегии доступа в каналы При данной стратегии w -заявки принимаются всегда, если в момент их по- ступления число свободных каналов не меньше, чем m , а n -заявки прини- маются лишь тогда, когда имеется хотя бы один свободный канал, и при этом число заявок данного типа не превосходит некоторое пороговое значе- ние L , NL ≤<0 , где N — общее число каналов. Величина L называется параметром RA-стратегии доступа. Замечание 1. Из данной стратегии при NL = получается CS-стратегия доступа. В силу сделанных допущений функционирование данной MRQ описы- вается цепью Маркова (ЦМ) с состояниями вида ( )mn kk ,=k , где nk ( mk ) означает число n -заявок ( w — заявок) в системе. Тогда фазовое простран- ство состояний (ФПС) системы         ≤+   === Nmkk m NkLkS wnwnRA ,,0,,0:: k , (1) где [ ]x — целая часть x . Элементы производящей матрицы (ПМ) данной цепи Маркова с ФПС (1) ( )         −=′ −=′ +=′ +=′< =′ .случаяхостальныхв ,если ,если ,если ,,если 0 , , , , , 2 1 2 1 ekk ekk ekk ekk kk Lk k kq n ww nn n n RA µ µ λ λ (2) При использовании данной стратегии доступа, как и при CS-стратегии, стационарное распределение модели ( ) RASp ∈kk , имеет мультипликатив- ный вид. Однако аналогичные вычислительные трудности при нахождении стационарного распределения существуют и при данной стратегии. Поэтому ниже предлагается другой путь решения проблемы, в котором используются принципы теории фазового укрупнения состояний стохастических систем. Вероятности потери n -заявок ( ( )LNPB RA n , ) и w -заявок ( ( )LNPB RA w , ) при данной стратегии доступа ( ) ( ) ( )( ) ( )( )LfIfIpLNPB n Sk RA n RA =+== ∑ ∈ 0:, kk , (3) А.З. Меликов, М.И. Фаттахова, Т.С. Казиев ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 86 ( ) ( ) ( )( )mfIpLNPB RASk RA w <= ∑ ∈ kk:, , (4) где ( )AI — индикаторная функция события A ; ( )kf — число свободных каналов в состоянии RAS∈k , т.е. ( ) wn kmkNf −−=:k . Рассмотрим следующее расщепление ФПС (1):  L i i RARA SS 0= = , ∅=j RA i RA SS  , ji ≠ , (5) где { }ikSS nRA i RA =∈= :: k . Класс состояний i RAS описывается одним укрупненным состоянием >< i , и строится функция укрупнения ( ) >=< iU RA k , если i RAS∈k . (6) Тогда согласно алгоритмам фазового укрупнения (АФУ) стационарное распределение исходной модели ( ) RASp ∈kk , приближенно определяется так: ( ) ( ) ( ) LkSkp nRAn kn ,0,, =∈><≅ kkk πρ , (7) где ( ) i RA i S∈kk ,ρ и ( ) Lii ,0, =><π — стационарные распределения соот- ветственно внутри класса i RAS и укрупненной модели. Стационарное распределение внутри класса i RAS определяется как хо- рошо известное распределение состояний классической системы обслужи- вания 0///     − m iNMM с нагрузкой wν эрл, www µλν /:= , т.е. с помощью известных формул Эрланга ( ) ( )     − === m iNjLii j ji i j wi ,1,,0,0, ! , ρ ν ρ , (8) где ( ) 1 0 ! 0, −     − =             = ∑ m iN j j wi j i ν ρ . (9) Укрупненная модель представляет собой процесс размножения и гибели. С использованием (2), (8) и (9) элементы ПМ этой модели ( ) LxxxxqRA ,0,,, =′>′<>< , Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона Системні дослідження та інформаційні технології, 2005, № 2 87 ( ) ( ) ( ) ( ) ( )             −=′ =−+=′ ≠−+=′ =>′<>< ∑ ∑ −    − =     − = случаях,остальныхв0 ,1если, ,0mod,1если,, ,0mod,1если,, , 1 0 0 xxx mxNxxix mxNxxix xxq n m xN i x n m xN i x n RA µ ρλ ρλ (10) где YX mod — остаток от деления X на Y . Следовательно, стационарное распределение укрупненной модели при данной стратегии доступа ( ) ( ) ( ) LjkF j j j k j n ,1,0 ! 1 0 =><=>< ∏ − = π ν π , (11) где nnn µλν /:= ; ( ) ( ) 11 01 ! 10 −− ==         +=>< ∏∑ k i L k k n iF k ν π ; (12) ( ) ( ) ( ) ( ) ( )         =− ≠− = ∑ ∑ −    − =     − = .0modесли,, ,0modесли,, 1 0 0 mjNij mjNij jF m jN i j m jN i j ρ ρ (13) Таким образом, на основе (8) – (13) можно предложить следующий ал- горитм для расчета величин (3) и (4). Шаг 1. Для Li ,0= и     − = m iNj ,1 вычисляются величины ( )jii ,ρ из (8), (9). Шаг 2. Для Lj ,0= вычисляются величины ( )>< jπ из (11)–(13). Шаг 3. Величины (3) и (4) вычисляются так: ( ) ( ) ( ) ( )( )0mod,, 0 2 =−><      − +><= ∑ = miNIi m iNELLNPB L i B RA n πνπ , ( ) ( )∑ = ><          − = L i B RA w i m iNELNPB 0 2 ,, πν , где ( )sEB ,ν — B -формула Эрланга, т.е. А.З. Меликов, М.И. Фаттахова, Т.С. Казиев ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 88 ( ) ∑ = = s i i s B i ssE 0 ! !/, ν νν . Замечание 2. Данный алгоритм при NL= может быть использован для приближенного расчета показателей QoS стратегии CS. Замечание 3. Здесь и в дальнейшем часто используется B -формула Эрланга. Для облегчения вычислений по этой формуле могут быть исполь- зованы эффективные рекуррентные алгоритмы [15]. 1.2. Расчет модели при TR-стратегии доступа в каналы Согласно данной стратегии w -заявки принимаются, если в момент их по- ступления число свободных каналов не меньше m , а n -заявки принимаются лишь тогда, когда число свободных каналов больше mR , где RR<≤0 ,            =−    = .случаепротивномв ,0modесли,1 m N mN m N R Величина R называется параметром TR-стратегии доступа. Замечание 4. Из данной стратегии при 0=R получается CS-стратегия доступа. Состояние системы в произвольный момент времени при данной стра- тегии, как и при использовании RA-стратегий доступа, описывается дву- мерным вектором ( )wn kk ,=k . Однако ФПС модели при TR-стратегии отли- чается от (1) и задается следующим образом:         ≤+   =−== Nmkk m NkRmNkS wnwnTR ,,0,,0:: k . (14) Элементы производящей матрицы соответствующей ЦМ с ФПС (14) можно записать так: ( ) ( )         −=′ −=′ +=′ +=′> =′ .случаяхостальныхв0 ,если, ,если, ,если, ,,если, , 2 1 2 1 ekk ekk ekk ekkk kk ww nn w n TR k k Rmf q µ µ λ λ (15) При использовании TR-стратегии доступа в отличие от CS- и RA- стратегий не существует мультипликативного решения для стационарного распределения ( )kp , TRS∈k , что значительно осложняет задачу расчета вероятностей потери разнотипных заявок при TR-стратегии доступа в кана- лы. При использовании TR-стратегии доступа в каналы вероятности потери n -заявок ( ( )RNPBTR n , ) и w -заявок ( ( )RNPBTR w , ) определяются как Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона Системні дослідження та інформаційні технології, 2005, № 2 89 ( ) ( ) ( )( )mRfIpRNPB TRS TR n ≤= ∑ ∈ kk k :, , (16) ( ) ( ) ( )( )mfIpRNPB TRS TR w <= ∑ ∈ kk k :, . (17) В ФПС (14) рассмотрим следующее разбиение:  RmN i i TRTR SS − = = 0 , ∅=j TR i TR SS  , ji ≠ , (18) где { }ikSS nTR i TR =∈= :: k , т.е. i TRS содержит те состояния TRS∈k , в кото- рых число n -заявок равно RmNii −= ,0, . Класс состояний i TRS описывается одним укрупненным состоянием >< i RmNi −= ,0 . На основе разбиения (18) функция укрупнения ( ) >=< iUTR k , если i TRS∈k . (19) Стационарное распределение внутри классов i TRS определяется точно так же, как и в (8), (9), но при этом следует учитывать, что RmNi −= ,0 . Замечание 5. Здесь и в дальнейшем для простоты изложения стацио- нарные распределения внутри классов и укрупненных состояний при раз- личных стратегиях доступа обозначаются одинаково. Однако очевидно, что они оценивают вероятности различных состояний в различных моделях. С использованием (8), (9) и (15) заключаем, что элементы ПМ укруп- ненной модели ( ) ,,0,,, mRNxxxxqTR −=′>′<>< ( ) ( ) ( ) ( ) ( )              −=′ ≠−+=′ =−+=′ =>′<>< ∑ ∑ −    − − =     − − = случаях.остальныхв0 ,1если, ,0mod,1если,, ,0mod,1если,, , 1 0 0 xxx mxNxxix mxNxxix xxq n R m xN i x n R m xN i x n TR µ ρλ ρλ (20) Тогда с помощью (8), (9) и (20) находится стационарное распределение укрупненной модели ( ) ( ) ( ) RmNjiG j j j i j n −=><=>< ∏ − = ,1,0 ! 1 0 π ν π , (21) где ( ) ( ) 1 1 01 ! 10 − − = − =         +=>< ∏∑ i j RmN i i n jG i ν π , (22) А.З. Меликов, М.И. Фаттахова, Т.С. Казиев ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 90 ( ) ( ) ( ) ( ) ( )           =− ≠− = ∑ ∑ −    − − =     − − = .0modесли,, ,0modесли,, 1 0 0 miNji miNji iG R m iN j i R m iN j i ρ ρ (23) Следовательно, с помощью (20) – (23) можно предложить следующий алгоритм для расчета величин (16) и (17). Шаг 1. Для RmNi −= ,0 и     − = m iNj ,1 вычисляются величины ( )jii ,ρ из (8), (9). Шаг 2. Для RmNj −= ,0 вычисляются величины ( )>< jπ из (21)–(23). Шаг 3. Для RmNkn −= ,0 и     − +    − − = m kNR m kNk nn w ,1 вычисляют- ся величины ( )wn kkp , из (7). Шаг 4. Величины (16) и (17) вычисляются так: ( ) ( ) ( ) ( ) ( )             ≠− =− = ∑ ∑ ∑ ∑ − =     − +    − − = − =     −     − − = ,0modесли,, ,0modесли,, , 0 1 0 miNjip miNjip RNPB RmN i m iN R m iNj RmN i m iN R m iNj TR n ( ) ( )∑ − = ><          − = RmN i mB TR w i m iNERNPB 0 ,, πν . 2. ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ РАСЧЕТОВ МОДЕЛИ Здесь приводятся результаты численных экспериментов, выполненных с помощью разработанных в п. 1 алгоритмов расчета модели при различных стратегиях доступа в каналы. Все вычислительные программы разработаны на языке Object Pascal в интегрированной среде Delphi 6. Цель выполнения этих экспериментов — определение поведения вероятностей потерь n - и w - заявок при изменении нагрузочных параметров трафика, а также изучение их поведения при различных значениях параметров рассматриваемых стра- тегий доступа в каналы. Часть результатов численных экспериментов показана на рис. 1–4. Анализ результатов численных экспериментов при различных стратегиях доступа позволяет сделать следующие выводы: Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона Системні дослідження та інформаційні технології, 2005, № 2 91 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 PBn PBw PB PBw PBn L Рис. 1. Зависимость вероятности потерь разнотипных заявок от L при RA-стратегии доступа ( 5106060 ==== wn ν;ν;m;N ) 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 PBn PBw PB PBw PBn L Рис. 2. Зависимость вероятности потерь разнотипных заявок от L при RA-стратегии доступа ( 5102160 ==== wn ν;ν;m;N ) 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 1 2 3 4 5 6 7 8 9 s PBn PBw PB PBw PBn R Рис. 3. Зависимость вероятности потерь разнотипных заявок от R при TR-стратегии доступа ( 105660 ==== wn ν;ν;m;N ) А.З. Меликов, М.И. Фаттахова, Т.С. Казиев ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 92 1) при фиксированных wnmN νν ,,, функция ( )LNPB RA n , — монотон- но убывающая, функция ( )LNPB RA w , — наоборот, монотонно возрастающая относительно аргумента L (рис. 1,2); 2) при фиксированных wnmN νν ,,, функция ( )RNPBTR n , — монотон- но возрастающая, а функция ( )RNPBTR w , — наоборот, монотонно убываю- щая относительно аргумента R (рис. 3, 4). 3. ЗАДАЧИ ОПТИМИЗАЦИИ МОДЕЛИ ПРИ РАЗЛИЧНЫХ СТРАТЕГИЯХ ДОСТУПА Проведенный выше анализ показывает, что при использовании каждой из рассматриваемых стратегий доступа в каналы имеются определенные управляемые параметры и путем выбора их соответствующих значений можно улучшить те или иные желаемые показатели QoS-системы. Зачастую в реальных системах оказывается достаточно трудным управление входя- щим трафиком (т.е. в зависимости от текущей ситуации динамически управлять интенсивностями входящих трафиков, хотя в некоторых работах исследуются и такие системы). Поэтому реальными являются проблемы улучшения показателей QoS-системы путем выбора соответствующих зна- чений скоростей обслуживания заявок (особенно изменением значения па- раметра m ), числа каналов обслуживания, а также параметров используе- мых стратегий доступа в общие каналы. Здесь рассматриваются некоторые задачи подобного типа при RA- и TR-стратегиях доступа. Для краткости изложения в рамках каждой страте- гии доступа рассматривается только одна задача оптимизации. PB PBw PBn R Рис. 4. Зависимость вероятности потерь разнотипных заявок от R при TR-стратегии доступа ( 1052160 ==== wn ν;ν;m;N ) Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона Системні дослідження та інформаційні технології, 2005, № 2 93 3.1. Оптимизация модели при RA-стратегии доступа Оптимизация модели при данной стратегии доступа осуществляется путем выбора ее параметра L при условии, что общее число каналов (т.е. N ) яв- ляется фиксированным. Для примера рассмотрим следующую задачу. Пусть заданы ограничения на вероятности потери разнотипных заявок ( ) n RA n LNPB ε≤, , (24) ( ) w RA w LNPB ε≤, , (25) где nε и wε — заданные величины. Задача оптимизации ставится следующим образом. При фиксированном N требуется найти такой интервал максимальной длины [ ] [ ]NLL ,1, * 2 * 1 ⊂ , чтобы для всех [ ]* 2 * 1, LLL∈ удовлетворялись условия (24) и (25). При разработке алгоритма решения данной задачи используются свой- ства монотонности функций ( )LNPB RA w , и ( )LNPB RA n , относительно аргу- мента L при фиксированном N , а также соотношения ( ) ( ) ( )1,,, NPBLNPBNNPB RA n RA n RA n ≤≤ , (26) ( ) ( ) ( )NNPBLNPBNPB RA w RA w RA w ,,1, ≤≤ . (27) Тогда, с учетом (26) и (27) можно предложить такой алгоритм решения рассматриваемой задачи. Если ( ) n RA n NNPB ε>, и/или ( ) w RA w NPB ε>1, , то задача не имеет реше- ния. В противном случае параллельно решаются задачи ( ){ }n RA nLn LNPBL ε≤= ,minarg:* , (28) ( ){ }w RA w L w LNPBL ε≤= ,maxarg:* . (29) Задачи (28) и (29) могут быть решены с применением метода дихото- мии. Если wn LL > , то исходная задача опять не имеет решения. В против- ном случае решением рассматриваемой задачи является 2 ** 1 :,: wn LLLL == . 3.2. Оптимизация модели при TR-стратегии доступа Рассмотрим выравнивание значений вероятностей потерь разнотипных зая- вок путем выбора соответствующих значений параметра TR-стратегии дос- тупа R . В этом случае также используются свойства монотонности функций ( )RNPBTR w , и ( )RNPBTR n , относительно аргумента R при фикси- рованном N . А.З. Меликов, М.И. Фаттахова, Т.С. Казиев ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 94 Из формул (16) и (17) видно, что при таком определении TR-стратегии доступа, когда число резервируемых каналов для w -заявок является крат- ным m , абсолютное справедливое обслуживание (в смысле равенства зна- чений вероятностей потерь различных потоков) достигается лишь при 1=m и 0=R , т.е. при многопотоковой модели Эрланга без резервирования. Аб- солютного справедливого обслуживания при данной стратегии можно дос- тичь лишь тогда, когда число резервируемых каналов для w -заявок не явля- ется кратным m , а равно 1−m . В связи с изложенным выше ставится задача определения ε-с N правед- ливого обслуживания, т.е. при фиксированных и m требуется найти та- кие значения параметра R данной стратегии, для которых абсолютное зна- чение разницы вероятностей потерь разнотипных заявок не превосходит за- данное число 10, << εε , или более формально: требуется найти такой интервал максимальной длины [ ] [ ]RRR ,1, * 2 * 1 ⊂ , чтобы для всех [ ]* 2 * 1 , RRR∈ удовлетворялось условие ( ) ( ) ε≤− RNPBRNPB TR n TR w ,, . (30) Решение данной задачи можно осуществлять в два этапа. На первом — решается задача ( ) ( ) R TR n TR w RNPBRNPB min,, →− . (31) Обозначим решение задачи (31) через R (решение существует в силу конечности области допустимых значений R ). Для нахождения R можно использовать такую схему. В исходном интервале [ ]R,1 методом дихотомии находится такой ин- тервал единичной длины [ ]1~,~ +RR , для которого ( ) ( )RNPBRNPB TR n TR w ~,~, > и ( ) ( )1~,1~, +<+ RNPBRNPB TR n TR w . Тогда решение задачи (31) имеет вид ( ) ( ) ( ) ( ){ }1~,1~,,~,~,minarg:* +−+−= RNPBRNPBRNPBRNPBR TR w TR n TR n TR w .(32) После определения R из (32) можно предложить следующий метод решения исходной задачи. Если условие (30) не удовлетворяется при : RR = , то исходная задача не имеет решения. В противном случае в интервалах [ ],1 R и [ ]RR , нахо- дятся такие минимальное ( * 1R ) и максимальное ( * 2R ) значения параметра R , чтобы удовлетворить условие (30). При этом для нахождения * 1R и * 2R , так- же исходя из свойства монотонности функций ( )RNPBTR w , и ( )RNPBTR n , , может быть использован метод дихотомии. Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона Системні дослідження та інформаційні технології, 2005, № 2 95 4. РЕЗУЛЬТАТЫ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ МОДЕЛИ С использованием предложенных в п. 3 алгоритмов разработаны соответст- вующие вычислительные программы на языке Object Pascal в интегрирован- ной среде разработки Delphi 6 и показана их практическая реализуемость в любом диапазоне изменения структурных и нагрузочных параметров мо- дели. Часть результатов вычислительных экспериментов показаны в табл. 1 и 2, где символ ∅ означает, что задача не имеет решения. Анализ результатов вычислительных экспериментов позволяет сделать следующие выводы: 1) в задаче оптимизации модели при RA-стратегии доступа и фиксиро- ванных nmN ν,, , wν с уменьшением nε и/или wε длина интервала * 1 * 2 LL − также уменьшается; 2) в задаче оптимизации модели при TR-стратегии доступа и фиксиро- ванных nmN ν,, , wν с уменьшением ε длина интервала * 1 * 2 RR − также уменьшается. Т а б л и ц а 1 . Результаты решения задачи оптимизации модели при RA- стратегии доступа в каналы, 100=N Пара- метры Значения параметров nν 15 15 15 10 5 10 15 25 25 25 5 10 wν 10 10 25 20 10 5 15 15 15 15 10 15 m 6 6 6 6 12 12 12 12 24 24 24 24 nε 10–1 10–1 4·10–1 4·10–1 10–1 10–1 10–2 5·10–1 10–1 10–1 10–1 2·10–1 wε 10–1 5·10–2 5·10–1 3·10–1 10–1 10–1 10–3 6·10–1 9·10–1 10–2 7·10–1 8·10–1 [ ]* 2 * 1, LL [17, 100] [17, 18] [10, 100] [7,7] Ø [12, 100] Ø [13, 23] [27, 100] Ø [100, 100] [11, 100] Т а б л и ц а 2 . Результаты решения задачи оптимизации модели при TR- стратегии доступа в каналы, 100=N Пара- метры Значения параметров nν 15 15 5 5 10 10 1 0,1 5 5 20 20 wν 5 5 15 15 5 5 1 1,0 5 5 0,4 0,4 m 6 6 6 6 12 12 12 12 16 16 16 16 ε 10–2 10–4 10–1 10–2 10–1 10–2 10–3 10–4 10–1 10–2 10–3 10–4 [ ]* 2 * 1 , RR [1,13] [11,11] [10,100] Ø [1,5] Ø [1,3] [1,2] [3,3] Ø [1.4] [1,3] А.З. Меликов, М.И. Фаттахова, Т.С. Казиев ISSN 1681–6048 System Research & Information Technologies, 2005, № 2 96 ЗАКЛЮЧЕНИЕ Предложен единый подход к решению проблемы расчета вероятностей по- терь разнотипных заявок в многоскоростных системах Гимпельсона при ис- пользовании двух наиболее известных стратегий доступа в каналы. Он отличается простотой, позволяет сформулировать и решить различные зада- чи оптимизации исследуемой модели практически в любом диапазоне изме- нения параметров. Важно отметить, что этот подход позволяет также успешно исследовать модели Гимпельсона при наличии приоритетов различных типов и/или оче- редей. Эти исследования представляют предмет дальнейших публикаций. ЛИТЕРАТУРА 1. Kelly F.P. Loss networks // Ann. Appl. Prob. — 1991. — 1, №3. —.Р. 319–378. 2. Меликов А.З. Методы расчета и оптимизации моделей мультиресурсных систем обслуживания // Кибернетика и системный анализ. — 1996. — № 6. — С. 92–112. 3. Ross K.W. Multiservice loss models for broadband telecommunications networks. — N.Y.: Springer-Verlag, 1995. — 240 р. 4. Schwartz M. Broadband integrated networks. — N.Y.: Prentiсe-Hall, 1996. — 412 р. 5. Лагутин В.С., Степанов С.Н. Телетрафик мультисервисных сетей связи. — М.: Радио и связь, 2000. — 320 с. 6. Gimpelson L.A. Analysis of mixtures of wide- and narrow-band traffic // IEEE Trans. Commun. Technol. — 1965. — 13, № 3. — Р. 258–266. 7. Kaufman J.S. Blocking in shared resource environment // IEEE Trans. Commun. — 1981. — 10, №10. — Р. 1474–1481. 8. Ross K.W., Tsang D.H. Teletraffic engineering for product-form circuit-switched networks // Adv. Appl. Prob. — 1990. — 38, № 8. – Р. 1266–1271. 9. Pioro M., Lubacs J., Korner U. Traffic engineering problems in multi-service cir- cuit-switched networks // Comput. Networks and ISDN Syst. — 1990. — 1–5. — Р. 127–136. 10. Меликов А.З. Об одном алгоритме расчета мультиресурсных систем обслужи- вания // Электрон. моделирование. — 1992. — 14, № 25. — С. 52–56. 11. Melikov A.Z., Deniz D.Z. Non-exhaustive channel access strategy in multi-resource communication systems with non-homogeneous traffic // Proc. of 5th 12. Korolyuk V.S., Korolyuk V.V. Stochastic models of systems. – Boston: Kluwer Aca- demic Publishers, 1999. — 185 р. IEEE Symposium on Computers and Communications, July 3-6, 2000, France. — Р. 432–437. 13. Ross K.W., Tsang D.H. Optimal circuit access policies in an ISDN environment: A Markov decision approach // IEEE Trans. Commun. — 1989. — 37, № 9. — Р. 934–939. 14. Меликов А.З., Молчанов А.А., Пономаренко Л.А. Мультиресурсные системы массового обслуживания с частично коммутируемыми каналами // Элек- трон. моделирование. – 1992. — 14, № 8. — С. 89–91. 15. Freeman R.L. Reference manual for telecommunications engineering. — N.Y.: Wi- ley, 1994. — 235 р. Поступила 11.06.2004 МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР ЧИСЛЕННЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ МНОГОСКОРОСТНЫХ СИСТЕМ ОБСЛУЖИВАНИЯ ТИПА ГИМПЕЛЬСОНА А.З. МЕЛИКОВ, М.И. ФАТТАХОВА, Т.С. КАЗИЕВ Введение 1. Методы расчета модели при различных стратегиях доступа 1.1. Расчет модели при RA-стратегии доступа в каналы 1.2. Расчет модели при TR-стратегии доступа в каналы 2. ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ РАСЧЕТОВ МОДЕЛИ 3. ЗАДАЧИ ОПТИМИЗАЦИИ МОДЕЛИ ПРИ РАЗЛИЧНЫХ СТРАТЕГИЯХ ДОСТУПА 3.1. Оптимизация модели при RA-стратегии доступа 3.2. Оптимизация модели при TR-стратегии доступа 4. Результаты решения задач оптимизации модели Заключение
id	nasplib_isofts_kiev_ua-123456789-13809
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1681–6048
language	Russian
last_indexed	2025-12-01T04:40:31Z
publishDate	2005
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
record_format	dspace
spelling	Меликов, А.З. Фаттахова, М.И. Казиев, Т.С. 2010-12-02T14:30:10Z 2010-12-02T14:30:10Z 2005 Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона / А.З. Меликов, М.И. Фаттахова, Т.С. Казиев // Систем. дослідж. та інформ. технології. — 2005. — № 2. — С. 83-96. — Бібліогр.: 15 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/13809 519.872 Предложены новые методы анализа характеристик многоскоростных систем типа Гимпельсона, в которых обслуживаются заявки двух типов – узкополосные (n-заявки) и широкополосные (w-заявки). Обслуживание n-заявки осуществляется одним каналом, а для w-заявки требуется одновременно m каналов, m > 1. Заявки обслуживаются в режиме без ожидания. Разработаны достаточно простые алгоритмы для расчета и оптимизации вероятностей потери разнотипных заявок при различных стратегиях доступа в каналы. Приводятся результаты численных экспериментов. New methods for analysis of characteristics of multirate queues of Gimpelson’s type are proposed. In these queues wide-band (w-call) and narrow-band (n-call) calls are serviced. For servicing n-call a single channel is required while for servicing w-call m channels, m > 1, required simultaneously. Calls are serviced in nonwaiting manner. Simple algorithms for calculation and optimization of loss probabilities of calls of different types under different channel access strategies are developed. Results of appropriate numerical experiments are given. Запропоновано нові методи аналізу характеристик багатошвидкісних систем типу Гімпельсона, у яких обслуговуються заявки двох типів — вузькосмугові (n- заявки) та широкосмугові (w-заявки). Обслуговування n-заявки здійснюється одним каналом, а w-заявка потребує одночасно m каналів m > 1. Заявки обслуговуються в режимі без очікування. Розроблено доволі прості алгоритми розрахунків і оптимізації ймовірностей втрати різнотипових заявок при різних стратегіях доступу до каналів. Наведено результати чисельних експериментів. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Методи оптимізації, оптимальне управління і теорія ігор Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона Numerical methods for investigation of multirate queues of Gimpelson’s type Чисельні методи дослідження багатошвидкісних систем обслуговування типу Гімпельсона Article published earlier
spellingShingle	Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона Меликов, А.З. Фаттахова, М.И. Казиев, Т.С. Методи оптимізації, оптимальне управління і теорія ігор
title	Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона
title_alt	Numerical methods for investigation of multirate queues of Gimpelson’s type Чисельні методи дослідження багатошвидкісних систем обслуговування типу Гімпельсона
title_full	Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона
title_fullStr	Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона
title_full_unstemmed	Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона
title_short	Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона
title_sort	численные методы исследования многоскоростных систем обслуживания типа гимпельсона
topic	Методи оптимізації, оптимальне управління і теорія ігор
topic_facet	Методи оптимізації, оптимальне управління і теорія ігор
url	https://nasplib.isofts.kiev.ua/handle/123456789/13809
work_keys_str_mv	AT melikovaz čislennyemetodyissledovaniâmnogoskorostnyhsistemobsluživaniâtipagimpelʹsona AT fattahovami čislennyemetodyissledovaniâmnogoskorostnyhsistemobsluživaniâtipagimpelʹsona AT kazievts čislennyemetodyissledovaniâmnogoskorostnyhsistemobsluživaniâtipagimpelʹsona AT melikovaz numericalmethodsforinvestigationofmultiratequeuesofgimpelsonstype AT fattahovami numericalmethodsforinvestigationofmultiratequeuesofgimpelsonstype AT kazievts numericalmethodsforinvestigationofmultiratequeuesofgimpelsonstype AT melikovaz čiselʹnímetodidoslídžennâbagatošvidkísnihsistemobslugovuvannâtipugímpelʹsona AT fattahovami čiselʹnímetodidoslídžennâbagatošvidkísnihsistemobslugovuvannâtipugímpelʹsona AT kazievts čiselʹnímetodidoslídžennâbagatošvidkísnihsistemobslugovuvannâtipugímpelʹsona

Численные методы исследования многоскоростных систем обслуживания типа Гимпельсона

Institution

Ähnliche Einträge