автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Аналитическое моделирование дискретно-временных и структурно-сложных систем передачи информации

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

РГ6 "ж

2 ^ Ш ШВ

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

КУРЕНКОВ Борис Ефимович

УДК 519.2

АНАЛИТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ДИСКРЕТНО-ВРЕМЕННЫХ И СТРУКТУРНО-СЛОЖНЫХ СИСТЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ

( 05.13.17 - теоретические основы информатики )

Автореферат

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

Москва 1993

Работа выполнена на кафедре теории вероятностей и математической статистики Российского университета дружбы народов

Научный руководитель -Действительный член Академии естественных наук Российской Федерации, доктор технических наук, профессор, Г.П. Башарин

Официальные оппоненты: доктор физико-математических наук, доцент Г.И. Фалин кандидат физико-математических наук, доцент В.А. Кокотушкин

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

в 15 час. 00 мин. на заседании специализированного совета К 053.22.28 в Российском университете друхбы народов.

Адрес: 117923, Москва, ул.Орджоникидзе, 3, факультет физико-математических и естественных наук, ауд.

О диссертацией можно ознакомиться в научной библиотеке Российского университета дружбы народов по адресу: 117198, Москва, ул. Миклухо-Маклая, д. 6.

Автореферат разослан " ¡^^С'рЛ 1993 г.

Российской Академии наук

Защита диссертации состоится " 1993 г.

Ученый секретарь специализированного совета кандидат физико-математических

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

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

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

Множественность доступа и обусловленные ею процедуры управления доступом, реализуемые в большинстве современных СПИ, при моделировании отражаются с помощью структурно-сложных СМО, функционирование которых описывается над весьма многомерным прост ранством состояний. По своей вероятностно-временной природе эти СМО в ряде случаев близки к сетям массового обслуживания, а методы их исследования, в основном, являются развитием методов, разработанных такими учеными как Б.В.Гнодепко, А.А. Боровков, Г.П. Пашарин, П.П. Бочаров, Р.Л. Добругаин, В.В. Калашников, И. II. Коваленко, В.А. Михайлов, В.А. Наумов, В.И. Нейман, А.Д. Соловьев, Ю.М. Сухов, A.JI. Толмачев, А.Д. Харкенич, М.А. Шнепс, L. Kleinrock, K.I'. Kelly, W.J. Gordon, J.R. Jackson, G.F. Newell, B. Pit-tel, J. Walrand И ДРУГИМИ.

- z

Основным математическим аппаратом, предоставляющем возможность определения прикладных характеристик функционирования и используемым как для сетей массового обслуживания, так и для структурно-сложных СМО, стали численные методы расчета характеристик многомерных вероятностных распределений, имеющих мульти пликативный вид. Несмотря на внешнюю простоту формульного пред ставления распределений мультипликативного вида требуется существенное развитие этих итак достаточно сложных и трудоемких численных методов, вызванное значительным усложнением вида пространства состояний, через которое описывается стратегия управления множественным доступом. В большой степени универсальным методом расчета характеристик распределений мультипликативного вида является метод свертки, впервые разработанный в работах J.P. Buzen и получивший свое развитие благодаря работам A.M. Андронопа, Л.В. Богуславского, В.М. Вишневского, Ю.И. Митрофанова, К.Е. Самуйлова, V. Baskett, K.M. Chandy, G. Barbaris, V.B. Iversen,'J.S. Kaufman, S. Lam, B.K. Müntz, F.G Palacios, J.W. Roberts и других.

Наиболее естественным способом отразить в модели синхронный характер функционирования СПИ является ее представление в виде дискретно-временной системы массового обслуживания {ДВ СМО), то есть такой, в которой все изменения состояния могут происходить лишь в дискретные моменты, расположенные на временной оси через равные интервалы. Анализ ДВ СМО по сравнению с непрерывными во времени, хотя и имеет ряд спецефических отличии, в целом является более простым. Несмотря на это, научные статьи на эту тему стали частыми лишь сравнительно недавно и в настоящее время существует ряд ДВ СМО, являющихся аналогами давно исследованных классических систем массового обслуживания, анализ которых не проводился или имеются существенные ошибки в таком анализе. Методы исследования ДВ СМО и соответствующий математический аппарат разрабатывались в значительной мере благодаря работам ГЛ. Климова, В.А. Малышева, Г.И. Фалина, B.C. Цыбакова, К. Bharath-Kumar, O.J. Boxraa, H. Bru-neel, H. КоЬауаь-hi, M. Sidi, J.J. Hunter И МНОГИХ ДРУГИХ.

Наряду с предоставлением возможности рассчитывать характе ристики дискретно-временных и структурно-сложных СМО необходимо было также продемонстрировать каким образом такими моделями описываются конкретные современные СПИ, наиболее характерные по общим принципам своего функционирования, и как эти модели могут

быть проанализированы. !! качество таких примеров были выбраны: система сигнализации по общему каналу (ОКС) 7, а именно метод защиты от ошибок при передаче путем привентивного циклического повторения; семейство циклических методов детерминированного множественного доступа, широко используемое в локальных вычислительных сетях; станция такой сети на основе однопроцессорной (однотипной) архитектуры; звено сети связи с коммутацией каналов. В этой части диссертационная работа опирается на исследования, проведенные в работах И.А. Мизина, В.Д. Ершова, В.А. Кфимушкина, В.А. Кокотушкина, С.И. Самойленко, Hayward, A.A. Frederics, S.W. Fuhrman, II. Takagi и ДРУГИХ.

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

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

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

- выведены ПФ стационарных распределений длины очереди, акту альной и виртуальной длительностей ожидания, а также функциональные уравнения, определяющие 11Ф длительности периода занятости, числа обслуженных за период занятости заявок и их совместного распределения в однолинейной ДВ СМО с геометрическим групповым поступающим потоком, неограниченным накопителем, рекуррентным обслуживанием общего вида и дисциплиной обслуживания FIFO;

- получено аналитическое соотношение между стационарным распределением длины очереди в описанной ДВ СМО и ее аналогом с накопителем ограниченной емкости;

разработан метод расчета НФ стационарного распределения длительности ожидания в однолинейной ДВ СМО с рекуррентным ординарным поступающим потоком с ограниченными интервалами между поступлениями, неограниченным накопителем, рекуррентным обслуживанием общего вида и дисциплиной обслуживания FIFO;

- развит алгоритм свертки для расчета характеристик распределений мульпликативного вида, характерного для структурно-сложных СМО, и получены достаточные условия его применимости общего вида;

- разработана и проанализирована дискретно-временная модель метода защиты от ошибок при передаче путем привентивного циклического повторения;

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

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

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

Практическая ценность работы. Методы исследования дискретно-временных и структурно-сложных СМО» расчетные формулы и численные алгоритмы и методы, полученные в диссертации могут быть использованы для определения прикладных ВВХ функционирования современных СПИ, модели которых относятся к указанным типам. Результаты анализа разработанных моделей конкретных систем и методов передачи информации непосредственно предназначены и были применены для расчета и оптимизации этих систем. Разработанные в диссертации численные алгоритмы были программно реализованы и была показана их работоспособность.

Реализация результатов работы. Результаты диссертации использовались в исследованиях, проводившихся по плану госбюджетных НИР Университета дружбы народов в соответствии с Координационным планом фундаментальных и прикладных исследований АН СССР на 1986-1990гг. от 05.12.85 по проблеме "Информационно вычислительные сети" {п. 1.13.8.2), а также по хоздоговорным темам "Разработка моделей, методов их анализа и прикладных программ для исследования интервально-маркерного доступа в волоконно оптических локальных системах передачи информации" (номер гос. регистрации 0188003274), выполнявшейся по заказу ЛНПО

"Красная заря", и "Методика анализа, оптимизации и проектирования сети ОКС" (номер гос. регистрации 01850052029), выполнявшейся по заказу ЦНИИ Связи.

Апробация работы. Основные результаты, изложенные в диссер тационной работе, докладывались на: семинаре кафедры теории вероятностей механико математического факультета МГУ (рук. Б.В. Гнеденко, Ю.К. Беляев, А.Д. Соловьев, 1989); седьмой (Одесса, 1982), девятой (Тарту, 1986), десятой (Батуми, 1988) Всесоюзных школах-семинарах по теории телетрафика; первом (София, 1988) и втором (Москва, 1989) Международных семинарах по теории телетрафика и компьютерному моделированию; 9-12, 16 Всесоюзных школах-семинарах по вычислительным сетям; семинаре Института проблем передачи информации Российской академии наук (рук. Г.П. Башарип, А.Д. Харкевич, М.Л. Шнопс); Научных конференциях Российского Университета дружбы народов.

Публикации. По теме диссертации опубликовано 17 работ.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы из ¿^-^наименований и одного приложения. Диссертация содержит ffС страниц текста, € рисунков, £ таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В параграфах 1. 2-1. 4 исследуется ДВ СМО Gem Gi|GJ |l \<*>\FIFO, то есть система с геометрическим групповым поступающим потоком, рекуррентным обслуживанием, одним обслуживающим устройством,накопителем неограниченной емкости и обслуживанием в порядке поступления. В утверждениях 1.5-1.6 показано, что ЦСВ о^, обознающие число заявок в системе в начале такта, непосредственно следующего за моментом ухода п-ой заявки, rfe 1, образуют однородную цепь Маркова (ЦМ), эргодичную при р-Л'(1)В'(1)<1, Г1Ф финального распределения ЦМ оп, Tfe 1, в этом случае имеет вид:

A{z)~1 1-Л(0)

SlZ) = *nC(Z)- , - (1 р)---,

0 Z-C(Z) ° Л'(1)

где A(z) - НФ числа заявок поступающих за такт, B(z) - ПФ

длительности обслуживания в тактах, C(z) - BlA(z)}, A(z)~

=(A(z)-A(0))/(1-A(0)).

Для определения ПФ виртуального V(z) и актуального Yl(z) времени ожидания в указанной ДВ СМО вводится понятие задания как совокупности поступающих за такт заявок. С помощью анализа ЦМ, вложенной по моментам окончания обслуживания заданий, получено следующее выражение как для виртуального, так и для актуального времени ожидания в стационарном режиме функционирования:

1-A{B{Z)) z-l

V(z) = W(z) = (l-p)---,

A'UHl-BU)) г-МВШ) причем виртуальное время ожидания определено как время ожидания тестовой заявки, расположенной случайно внутри группы поступающих заявок. Полученное совпадение согласуется с результатами для соответствующей СМО в непрерывном времени.

Вид ПФ стационарных распределений S(z), V(z) допускает непосредственное дифференцирование, что дает простую возможность выразить среднее, дисперсию и моменты более высокого порядка этого распределения через аналогичные величины исходных Г1Ф. Кроме указанных характеристик часто требуется вычислить определенные квантили функции распределения длины очереди или длительности ожидания. Это также можно сделать, приняв какое-либо предположение о конкретном виде исходных ПФ. Удобно принять, что ПФ A(z), B(z) являются дробно-рациональными, так как это почти всегда согласуется с реальностью, а если эти ПФ не являются

дробно-рациональными, то их можно сколь угодно близко аппрок симировать такими функциями. Еще более простим является предположение о том, что исходные распределения имеют конечный носитель, то есть соответствующие ПФ являются полиномами. При любом из этих предположений ПФ стационарной длины очереди S(z) является дробно-рациональной функцией, для которой расчет коэффициентов при разложении в степенной ряд (стационарных вероятностей) алгоритмически достаточно прост.

В параграфе 1.1 исследовалось распределение длительности % периода занятости и числа обслуженных за этот период заявок % в описанной ДВ СМО. Выведены следующие функциональные зависимости, определяющие ПФ этих ЦСВ и их совместного распределения:

Мz% Diz) - MDj(z)), D^z) tí{zA(D¡[z))).

ttzx = Xíz) r. MXjlz)), X^z) = zBlÁiX^z))),

tízV = Y(z,u) --■ AlY^z.u)), Y^z.u) = vBizAlY^z.u))) .

В утверждениях 1.9, 1.10 доказано, что при р < 1 эти соотношения единственным образом определяют функций D(z) и X(z), представимые в виде сходящегося при \z\ < 1 степенного ряда по г с неотрицательными коэффициентами, сумма ряда из которых равна 1.

Последние соотношения позволяют дифференцированием получить аналитические выражения для моментов ЦСВ них, например

А'( 1) В'И)

т

1- 4(0) 1-4'(1)В'(1)

*2Y(z,u) dY(z.u) dY(z.u)

cov(%,%) = ОД-МОД - ---------iz~1 " T----- Iz=1 ----- Iz=1

ózdu I £] dz \L] 0u I Ji

041) s A'( i)2

-- [Л'(1 )M"(1 ) - --------- ]

(l-4(0))(i-^'(l)B'(3))2 ~ l Ai 0)

4'(1) , 2 1

^"(iM'm+s'm ¿A"(i)J

(1-A(0)){1-A'(Í)B'(I))3

Для расчета самих распределений этих ЦСВ предложено использовать

последовательность функций, определяемую рекуррентно: f0(zM, fu1(z)=B(zA(ft(z))), №, такую, что D^z) limf^z).

В параграфе 1.5 рассматривается ДВ СМО G1\G1\1 \oa\FIFO-Переход от непрерывного к дискретному времени позволяет исследовать эту СМО и численно получать при этом такие ее характеристики, которые в случае непрерывного времени или не поддаются расчету, или их определение сильно затруднено.

В предположении, что Г!Ф интервалов времени Т^ между последовательными поступлениями имеет вид

ь Я „

и z T(z) = J 0nzn, 121,

Tl- 1

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

и-г

Е Wt gt(z)

W(z) = -------------, wt = r*. I ы ^ t S,

T(1/z)B(z)

gi(Z) =■£ Ъ, E efr - ¡P+UJ-k) , 1=0..И-2. 1 3=1 3 tei+3+1

Из аналитичности производящей функции W(z) в области|2( ^ 1 следует, что неизвестные ty^.i-O.-N-2, могут быть найдены из неоднородной системы линейных алгебраических уравнений (СЛАУ):

п-г

Т. wt gitZfr) = 0 , 1^1..11-2, N-2

Е w. g.'(1) = T'(1) - B'(1). i=0 1 1

Таким образом, численный метод анализа рассматриваемой ДВ СМО состоит из следующих этапов:

1. определение корней знаменателя функции W(z), лежащих в области{2

2. составление и решение СЛАУ,

3. расчет стационарных характеристик и распределения времени ожидания заявок.

Предложенная методика анализа ДВ СМО GI|GI|i|<»| FIFO является основанием для создания соответствующего программного обеспечения. При этом последняя задача почти полностью решается с помощью стандартных подпрограмм, если принять что Г1Ф B(Z) имеет дробно-рациональный вид. Отметим также, что предположение о конечности носителя распределения СВ т:^, достаточно часто выполняется в реальных синхронных СПИ, а с математической точки зре ния ясно, что если мы ограничиваемся дискретными распределениями, имеющими конечные среднее и дисперсию, то распределения с ограниченным носителем всюду плотны в этом метрическом пространстве (с естественной метрикой) и, следоваательно, ими может быть сколь угодно точно приближено любое распределение этого класса.

nj

В параграфе 1.6 проводится анализ ДВ СМО Geom [GI1 \Г<со конечной емкости R=r+1 с потерями, происходящими при заполнении накопителя. Расчет стационарного распределения ЦМ, вложенной по мементам ухода заявок, основывается на доказанном в утверждении 1.13 соотношении между ПФ стационарных распределений для СМО с ограниченным и неограниченным накопителем:

Л; = 1^(2) щ cR,

где - усечение ПФ стационарного распределения длины

очереди в СМО неограниченной емкости: R

R~'lir(z)1l zt' t--0

a Cjj - константа, получаемая из условия нормировки:

CR

1 "?(z)lt

t=0

-1

»

Здесь - коэффициент при г разложения ПФ Х(г) в степенной

ряд.

В главе 2 рассматриваются СМО сложной структуры, являющиеся моделями СПИ, в которых реализован множественный доступ к тому или иному общему ресурсу, регулируемый соответствующими процеду-

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

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

В параграфе 2.2 предложен общий вид пространства состояний

X - { п - (Пу.п^0, (п,Ъи) < г, и - 1..1 ),

где параметры Ьц > 0 и ги > О определяют структуру доступности, и формулируются (утверждение 2.1) условия, обычно выполняющиеся на практике, при которых стационарное распределение имеет мультипликативный вид: й

р (п) р (0) II /, (п.) , п <1 X, 1=1 1 1

где /¿(п^) - некоторые положительные функции нелого неотрицательного аргумента, а

к ^

Р (0) =

к

е и т%)

п с X

I! параграфе 2.3 доказана возможность применения алгоритма свертки, являющегося общепринятым в сетях массового обслуживания для расчета характеристик мультипликативных распределений, к расчету модели системы спутниковой связи (ССС), имеющей сущест венно более сложный характер границ пространства состояний. На этом примере продемонстрированы спецефические трудности, возни-

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

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

Введем множества I^ -It: Ьи( t ,11^1 ■ ■ I, где b u(t) - 1-ая компонента вектора Ьц и отношение следования (частичный порядок) на множестве 1,2,...,1 ): будем говорить, что элемент у предшествует элементу w ( v^U) ), если и только если R^R^, V,W=1..l■ В утверждении 2.4 сформулирован модифицированный алгоритм свертки и обосновано его применение при выполнении условия разделенности ограничений:

а) для любых v,W - 1..1 либо v Л V), либо wit), либо R^Mi^-0,

б) для любых v,w - 1..1 таких, что H®, b„ х Ь„, ■

U Ш ! Rv

где знак ж означает, что соответствующие векторы равны с точностью до умножения одного из них на константу, а х ■ -

и

вектор составленный из элементов вектора X, имеющих индексы из множества Л (сужение х на Л).

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

Глава 3 посвящена разработке и исследованию моделей некоторых систем и методов передачи информации. Стремление наиболее адекватно отразить особенности их функционирования и получить достаточно легко реализуемые методы расчета их ВВХ приводит к дискретно-временным и/или структурно-сложным СМО.

В параграфе 3.1 предлагается и анализируется модель метода защиты от ошибок при передаче путем привентивного циклического повторения (PCR - Preventive Cyclic Retransmition), ИСПОЛЬЗ.уе-мого в так называемой сети общих каналов сигнализации (ОКС). Протокол передачи определяется следующими правилами.

1. Поступающие для передачи СЕ хранятся в буфере передачи (БП).

2. Ожидающие в ВН сообщения передаются в канал в порядке поступления, при этом они снабжаются порядковым номером.

3. Копии переданных СЕ хранятся в буфере ретрансляции (BP) до получения подтверждения о правильном приеме (pack - Positive Acknowlegment) с приемной стороны, после чего они стираются.

4. Если в БГ1 нет ожидающих СЕ, то в канал ретранслируются копии сообщений, хранящиеся в БР.

5. Если сообщений нет ни в БП, ни в БР, в канал для поддержания синхронизации передаются заполняющие сообщения (ЗС).

6. На приемной стороне при обнаружении ошибки пораженная СЕ игнорируется. Следующие за ней сообщения также не воспринимаются, до тех пор, пока пораженная CF. не будет ретранслирована.

7. Порядковые номера изменяются циклически от 0 до Ц-1, емкость бр рассчитана на К сообщений. При заполнении бр копии сообщений циклически ретранслируются до получения pack, даже если в би имеются ожидающие СЕ.

8. Поступление нового сообщения не прерывает передачу ни ЗС, ни ретранслируемого из БР сообщения.

Далее обосновывается модель pcr метода, представляющая собой однолинейную ДВ СМО с двумя накопителями и относительным приоритетом, функционирование которой описывается вложенной ЦМ над пространством X - l(J,q): J-1,2, q-0,1,2,3,... } с переходными вероятностями, вычисляемыми по достаточно сложным формулам. В результате анализа этой ЦМ получены аналитическое выражение для Г1Ф числа СЕ в БГ1 на тех периодах, когда в системе нет ошибочно переданных СЕ, и рекуррентное соотношение, позволяющее рассчитать вероятностное распределение числа СЕ в БР на тех периодах, когда такие СЕ имеются. Показано также, что ЦМ эргодична при р<1/2-

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

Рассматриваемая АС имеет следующие особенности.

1. Функционирование станции в составе абонентской ЭВМ как одно из ее внешних устройств, причем архитектура этой ЭВМ - однотипная.

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

г

л

1 о »I /

LÜ ' □ —

□.......□

D Е

F

Рис.1. Модель станции ЛВС.

СМО функционирует по следующему алгоритму. Пакеты данных, предназначенные для передачи по ЛВС (А--пакеты), поступают в накопитель неограниченной емкости В и ожидают в нем. Далее в соответствии с порядком поступления один из них передается через общую шину (Olli) в буфер I), в котором он ожидает момента, когда рассматриваемая станция получит право доступа к передающей среде, а затем выдается в нее. Только после завершения передачи буфер D освобождается, и следующий А-пакет, находящийся в накопителе В, начинает конкуренцию за доступ к ОЩ, что на рис.1 показано с помощью пунктирной линии. Пакеты данных, переданные другими станциями ЛВС и направленные на рассматриваемую станцию (Р-пакеты), принимаются п буфер G■ Так как буфер G, также как D, рассчитан на / пакет максимальной длины, то при его занятии следующие пакеты теряются. Принятый пакет ожидает освобождения ОЩ и передастся по ней, освобождая в момент завершения этой передачи буфер G. В отсутствии ^-пакетов и А-пакетов ОШ занята фоновыми заданиями из бункера Н. Занятие ОШ происходит в соответствии с относительными приоритетами: высший - у i'-пакетов (так как необходимо сделать возможно меньшими потери на приеме), второй - у А-пакетов, нисший у фонопнх заданий.

Для анализа этой СМО сначала разрабатывается и анализируется модель занятости среды Е, что позволяет определить вероятность потерь ¿'пакетов и с какой частотой одна из станций ЛВС получает право доступа к среде. Основной характеристикой для Л-пакетов являются задержки, которые определяются интервалами времени между моментами, когда следующие один за другим Л-пакеты начинают конкурировать за захват ОШ (эквивалентное время обслуживания).

Проведенное исследование привело к аналитическим выражениям

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

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

Пусть W^ т - число заявок на AG'm в момент ее í-ro опроса,

wt т' Известно, что случайные величины (СВ)

п), i-1,2,.. образуют ЦМ. Введем следующее простое предположение: условное распределение СВ ..п, при

фиксированном ш^, , подчиняется полиномиальному закону:

где b , т=1..п - параметры распределения, которые должны быть

определены. Тогда по распределению СВ можно определить распределение ее слагаемых, а значит и распределения числа обслуженных заявок за цикл, его длительности и числа поступивших заявок. Так как СВ v>i+i зависит только от этих величин, то введенное предположение позволяет рассматривать последовательность СВ 1^1, как цепь Маркова. Ее анализ - несравнимо более легкая задача, так как пространство состояний одномерное, а не ц-мерное.

Для определения параметров модели Ъш< Ш-1■-П, предположим, что мы рассчитали финальное распределение СВ и. Тогда из модели легко определить доли заявок, обслуживаемых на каждой АС. Эти доли должны совпадать с соответствующими долями в общем объеме поступающих заявок. Варьируя значения Ьт< т-1■-П, можно добиться такого совпадения, в частности, в диссертации предложен итеративный алгоритм определения Ьт> т~1--п.

В параграфе 3.4 рассматривается пучок соединительных линий (СЛ) иерархической сети связи с коммутацией каналов. На пучок СЛ поступает несколько потоков вызовов, инициированных разными парами АС, причем каждый из потоков не обязательно является пуассо-

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

CT

2. Проанализирована ДВ СМО Gern|Gl|/|ю|FIFO и получены ана литические выражения ПФ стационарных распределений длины очереди и длительности ожидания и функциональные соотношения для характеристик периода занятости. Проведено сравнение этой СМО с ее аналогом с ограниченным накопителем.

3. Разработан метод расчета ПФ стационарного распределения длительности ожидания в ДВ СМО GI\GIJ 1|oo|PIFO.

4. Развит алгоритм свертки для расчета характеристик структурно-сложных СМО, и получены достаточные условия его применимости общего вида.

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

учитывающие их специфические особенности, и получены алгоритмы

расчета их характеристик.

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

1. Ьашарин Г.П., Куренков Б.Е. Исследование одной СМО с дискретным временем II Изв. АН СССР. Техн. киб. - 1883, 6, с.26-30.

2. Башарин Г.11., Куренков Б.Е. О дискретной модели узла одной сети передачи данных // Системы управления информационных сетей. - М.: Наука, 1983, с.82-90.

3. Башарин Г.П., Куренков Б.Е. 0 разделении ограниченного накопителя между потоками в многоканальной СМО // Вычислительная математика и информатика. - М.: Изд-во УДН, 1983, с.60 65.

4. Башарин Г'.П., Куренков Б.Е, Самуйлов К.Е. Алгоритмический анализ марковских систем массового обслуживания сложной структуры // Методы теории телетрафика в децентрализованных системах управления. - М.: Наука, 1986, с.3-11.

5. Куренков Б.Е. Эффективный метод расчета характеристик многомерных мультипликативных распределений // Анализ информационно-вычислительных систем. - М.: Изд-во УДН, 1986, с.30-35.

6. Башарин Г.П., Куренков Б.Е. Анализ избыточных потоков в сетях коммутации каналов // Проблемы передачи информации. - 1987, т. 23, з, с.54-63.

7. Башарин Г.П., Вигулис Л.А., Куренков Б.Е. Об оптимальном выборе структурных параметров систем спутниковой связи с многостанционным доступом // Проблемы передачи информации. -1987, Т. 23, 4, с.102-109.

8. Куренков R.E. Виртуальная и реальная длительности ожидания в системах массового обслуживания в дискретном времени II Системы массового обслуживания и информатика. - М.: Изд-во УДН, 1987, с.90-95.

9. Куренков Б.Е., Гуггга С. Исследование системы массового обслуживания в дискретном времени // Системы массоповго обслуживания и информатика. - М.: Изд-во УДН, 1987, с.96 101.

10. Куренков Б.Е. Общий подход к анализу циклических СМО // Модели распределения информации и методы их анализа.

Труды 10 Всесоюзной школы-семинара по теории теретрафика. с.35 38.

11. Kurenkov В.Е. A general approach to Cyclic Queueing Systems Analysis // International Seminar on Teletraffic Theory and Computer Modelling, Proceedings, Sofia, Bulgaria, March 21-26, 1988, p.72 75.

12. Куренков В.Е. 0 матаматической модели и методе анализа ЛВС с множественным доступом циклического типа // Численные методы и информатика. М.: Изд-во УДН, 1988, с.70-73.

13. Куренков Г..Е. Аналитическая модель системы передачи данных с предупредительным циклическим повторением // Численные методы и информатика. - М.: Изд-во УДН, 1988, с.74-79.

14. Куренков Б.Е. Асимптотический анализ циклического обслуживания при малой нагрузке // Моделирование систем и информатика. М.: Изд-во УДН, 1989, с.29 33.

15. Вашарин Г.Г1-, Куренков Б.Е. Метод расчета индивидуальных характеристик избыточной нагрузки в сотях коммутации каналов // Электросвязь. 1991, 6, с.9 12.

16. Аджемов A.C., Баиарин Г.П., Бизин A.B., Куренков Б.Е. О методах распределения пропускной способности цифрового коммутационного поля между узко- и широкополосными вызовами // Электросвязь. - 1992, 2, С.34 36.

17. Кулькова Л.И., Куренков Б.Е. Дискретно-временная модель станции ЛВС с циклическим доступом // Системный анализ и информатика. - М.: Изд-во РУДН, 1992. с.70-83.

Подписано в печать. Объем 1.0 п.л. Тир. 100, зак. Ь¿Ь ТИПОГРАФИЯ РОССИЙСКОГО УНИВЕРСИТЕТА ДРУЖб!! НАРОДОВ