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

6 сд

5 ДПР Ш

киевский политехнический институт

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

Супрун Александр Дмитриевич

УДК 681.324

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

Специальность 05.13.13 - вычислительные машшш, комплексы,

системы и сети

Автореферат на соискание ученой степени кандидата технических наук

Киев - 1993

Работа выполнена в НИИ специального приборостроения "Спектр" и кафедре математических методов и системного анализа Киевского политехнического института

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

доктор технических наук, профессор ЗАЯЧЕНКО Ю.П.

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

доктор технических паук, профессор ДОДОНОВ А.Г.,

доктор технических наук, доцент ПЕЧУРИН Н.К.

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

Институт кибернетики АН Украины

Защита состоится -Л'&Р'Мс? 1993 г. в 14эо часов

на заседании специализировшшого совета Д 068.14.09 в Киевском политехническом институте.

Отзывы на автореферат в двух экземплярах, заверенные печатью учреждения, просим направлять по адресу .• 252056, Киев - 056, пр. Победа, 37, КПИ, ученому секретарю.

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

Автореферат разослан " & " 1993 г.

Ученый секретарь специализированного совета Д 068.14.09

доктор технических наук, профессор

. /,О. В. Вузовский

/ .

II II О Т Л II и я

Цоль'й_ работы является разработка методики

топологического проектирования иорархичосюгх сетей поре дачи данных с заданными надежностными и вероятностно-временными характеристиками, анализа функционирования иерархических СГЩ.

Для достижения поставленной доли решаются следующие задачи :

1. Формализация задачи оптимального по экономическому критерию топологического проектирования иерархичоских СПД с учетом вароятностно-вромогашх и надамюстних ограничений.

2. Разработка методики расчета вероятности своевременной доставки сообщений (пакетов) в иерархических СЦД в классе нерегулярных структур.

3. Разработка эффективных аналитических методов расчета работоспособности с трукт урпо-сложных систем, в том числе иерархических СПД в классе нерегулярных структур.

4. Разработка методики и алгоритмов синтеза иерархических СПД в класса нерегулярных структур с учетом вероятностно-временных и надежностных условий.

6. Экспериментальное исследование основных положений методики анализа и синтеза иерархических С1Щ.

Автор защищает следующие основные положения диссертации :

- методику анализа вероятности связности заданного числа абонентских пунктов с центром в иерархических СПД в классе нерегулярных структур.

- методику анализа вероятности своевременной доставки сообщений (пакетов) в иерархических неизотрошшх СЦД:

- нижние оценки обобщенного биномиального распределения!

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

- г -

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

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

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

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

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

о

вероятности своевромэнной доставки сообщений (пакетов) в иерархических СПД; па основе указании* результатов разработана методика и алгоритмы для решения задач топологического синтеза и анализа функционирования иерархических СПД в классе нерегулярных (неизотрогпшх) структур.

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

Реализация научных результатов. Предложенная в диссертационной работе методика топологического проектирования и анализа функционирования иерархических СДД реализована в виде ППП, который внедрен в ВДШШШ (г. Москва) при разработке проекта модернизации СЦД специального назначения, а тагако в учебный процесс в Киевском политехническом институте для студентов специальности "Прикладная математика" по курсу "Математическое моделирование параллельных процессов".

Апробащш работы. Основные полоиашя и результаты диссертационной работы докладывались и обсуждались на 3 Всесоюзном совещании по распределенным автоматизированным системам массового обслуживания (Винница, 1990 г.), 4 Всесоюзном - совещании по распределенным вычислительным системам массового обслуживания (Душанбе, 1991 г.), Всесоюзной научно-практической конференции "Вопросы экономики и организации информационных технологий" (Гомель, 1991 г.), на семинаре по теоретическим проблемам теории вероятности в Киевском госуниверситете, на научно-практическом семинаре по проблемам теории надежности в ИК АН Украины.

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

Структура и объем работы. Диссертационная работа состоит из введения, чотырох глав и заключения, списка использованной литературы из 76 наименований и приложения. Работа содержит 112 страниц машинописного текста, 11 рисунков и 4 таблицы.

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

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

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

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

Четвертая глава поссящона вопроса! экспериментальных исследований методики синтеза иерархических наизотропних СГЩ. Продло-гсош результаты экспериментальных исследований водичин относительных погрешностей при пароходе к схоме независимых испытаний Бернулли для описания работоспособности иерархичоскоЯ СДЦ с нерегулярной структурой, шшшх оценок обобщенного биномиального распределения, времешшх характеристик алгоритмов синтеза иерархических сетей передачи данных; приведен пример синтеза работоспособной иерархической СПД.

В заключении приведены основные результаты работы.

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

Пусть определено множество узлов V = хои х и у, где х0- управ-лявдая вершина (источник), х - множество узлов СПД, *-<.!>, j=TTп -множество узлов исполнительного уровня (ИУ). Все узлы СПД характеризуются своим географическим местоположением." Интенсивность обмена информацией между источником и узлами ИУ определена массивом Л = >,.!«*.

В сети могут быть использованы КС различных типов <. а , а2, >, а также, известна функция стоимости КС. связывающего узлы 1 и J, в зависимости от его длины и пропускной

способности с!^:

спер{

е V. Также задана зависимость коэффициента готовности ЛС от ее длины ^уС1^)- При рассмотрении СЦЦ как новосстанавливаемой системы используют показатель -вероятность безотказной работы (ВЕР) рбР на заданном интервале времени.

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

Определение 1. Подграфом графа в назовем совокупность гда ^^ и Е]сЕ* ~ множество вершин (узлов) и дуг (КС) СПД, образующих всо возможные в в пути, соединяющие источш хо и узел ИУ е у.

Определение 2. Исполнительной подсистемой (ИП) Sj с s , jeY назовем систему ОД, определенную на множествах л, к,

JeY в выполнявдую функции по обеспечению обмена информацией между ИСТОЧНИКОМ Хо и узлом ИУ J е Y.

Пусть заданы случайные величины ... , п-jyi,

имеющие распределение Бернулли с параметрами р°в, р£в, ... , р£в соответственно. Пусть значение случайной величины ^ «= 1 соответствует наличию маршрута, связывающего источник xQ и узел ИУ JeY. Тогда р°в есть вероятность связности . двухполюсника (xq,j)

исполнительной подсистемы s., j е y. Заметим, что случайная вели-

n J

чина ? = Е ?, фиксирует число ИП со связными двухполюсниками. J-» J

Таким образом, мы приходим к определению наиболее важной характеристики функционирования системы s и сети ЦЦ .

Определение 3. Система s (или СПД), заданная на множествах g=(v,e), л, к называется работоспособной, если в ней' о вероятностью не менее р^д число ИП со связными двухполюсниками ( не менее Сзад. а вероятность доставки сообщений (пакетов) в срок

rcjr *-зад 110 М0Н0е рзад* то есть

рсд = р ( т st ) > рсд . m

р v ср зад' рзад ■ . w

Е

РСВ = Р ( ? * Сзад) * Р™д , (2)

Требуется синтезировать работоспособную СПД минимальной стоимости в классе иерархических структур, описываемую ориентированным графом g=(v,e) без петель, где е - множество ветвей СПД. Таким образом, требуется обеспечить

с да ( 1 с ) . min (3)

<l,j>eE iJ iJ J

при условии выполнения огра1шчений (1),(2).

Данная задача относится к классу задач нелинейного дискретного программирования и является np - полной. К тему же сложность решения данной задачи определяется вычислительной сложностью выражений (1) и, особенно, (2).

Для иерархической СЦЦ среднее время задержки тСр необходимо

основывать на оценках времен задержек в каждой исполнительной подсистеме Tj, j«y. Если СЦЦ представляет собой сложную разветвленную сеть, в которой кажДый подграф Gj, je* может располагать множеством маршрутов м^, связывающих узел ИУ j«v с источником хо, то задержка в подсистеме Sj, j«* может быть оценена следующим образом :

Т. - max { T.m > , j « У , (4)

J M. ш М, J

)"» J

Т. r t, , М. е М. ,

Jm ** тт 9 jm J *

jn

где tre- случайные величины времени задержки в КС (r,s)eMJm, MJm-a-ft маршрут в подграфе Qj, овязывалций источник хо о исполнительной вершиной (абонентским пунктом) j «к.

Если на вход подсистемы поступает пуассоновский потрк, а времена обслуживания заявок в КС являются независимыми показательно распределенными случайными величинами (гипотеза "о независимости" Л.Клейнрока) о параметрами dra, то t-r>- независимые показательно распределенные случайные величины, для которых tr>= t/(dre-Xre), где аг9~. пропускная способность КС, на вход которого поступает

ПОТОК 0 ИНТвНСНВНОСТЬЮ X , (r,s)eE.

г»

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

т =• (1/Х) Е A-jT , X = Е А., ,

ср j6Y j j jeY j

где Xj - интенсивность потока на входе исполнительной подсистемы Sj, Tj - максимальное время задержки в подсистема Sj, jcY.

ГГри анализе вероятности р(тСр5 <-зад) будем предполагать »-зад-показательно распределенной случайной величиной с параметром v, который характеризует интенсивность старения информации. Тогда, исходя из определения преобразования Лапласа-Стилтьеса, ого мультипликативного свойства для независимых случайных величин, получено следущео выражения для оценки р (т^ s ьзад)!

- с -

зад

) = II П

1 еУ I г , а ) €=М .

рс Ч. -- * Чад' )

где м^- маршрут в подграфе Gj, связывающий источник с исполнительной вершиной .1 е у с максимальной задержкой. Для оценки вероятности р для отдельных ветвей СДД можно вос-

пользоваться выражениями, полученными Захаровым Г.П. как для режима с коммутацией пакетов, так и для режима с коммутацией сообщений. Так, при рассмотрении КС, работающего в режиме с коммутацией сообщений, как СМО МШИ вероятность своевременной доставки (ВСД) сообщения определяется седующим образом :

где \ - интенсивность потока 'заявок на входе ' КС, ц -интенсивность обслуживания заявок, определяемая пропускной способностью данного КС, кг- коэффициент готовности КС, V -интенсивность старения информации (в нашем случае v.= ). т} -интенсивность восстановления КС.

Наиболее сложными с точки зрения вычислительных затрат являются показатели вероятности связности двухполюсников исполнительных подсистем и СВЯЗНОСТИ СДД В целом Р(£2?зад). Задача вычисления вероятности связности сети является по своей природе комбинаторной и связана с необходимостью перебора вариантов, число которых быстро возрастает при увеличении размера сети. Для определения величин р(^1), был использован модифицированный логико-вероятностный метод (ЛВМ), сущность которого заключается в использовании смешанной формы функции вероятностей (СФФВ), получаемой в результате частичного замещений в функции алгебры логики (ФАЛ) логи ских переменных вероятностями и представляющая собой компактную форму записи некоторого множества условных вероятностей. Данный метод является эффективным при решении задач относительно небольшой размерности сети (количество элементов 20+30). К тому же, если допускается приближенный расчет вероятности связности, то при этом удается значительно сократить трудоемкость преобразований и упростить расчетную формулу без ощутимой потери точности.

р

,СД =

ц кг - \ ♦ 1+1*г(1-кг)/С1*г+тО )

Слогаюсть рлсюта вероятности связности СПД р(£>£„„„) опродо-

«ЗиД

ляется прездо всего зависимостью функций связности исполнительных подсистем ?j, j^y мояду собой. Это связано с том, что некоторые участки маршрутов, соединяющих «центр с вершинами ИУ, являются общими для различных исполнительных подсистем. Известные аналитические методы расчета указанпой характеристики опираются на допущения об однордпости (все элементы СПД имеют одинаковые характеристики) и изотропной структуре СПД (коэффициенты ветвления на каждом уровне иерархии совпадали ),v"?ie позволяют их практически 1

использовать для анализа и, тем более, для синтеза, реальных распределенных СПД. Применение универсальных ЛВМ даже при умеренных размерах сети (количество узлов порядка 102) представляется весьма проблематичным.

В работе предлагается другой способ оценки вероятности связности СГЩ рАнализ СПД свидетельствует о том, что

od д

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

*в = ( 1 ' > у 1 з jE

кы ' С 1 ' 1 V ) & vIJ ' J G Y

j

где V* - полустепепь исхода узла для передачи штока Л^, JcY. Экспериментальные данные показывают, что при *в>1 зависимость подсистем значительно ослабевает. Так, при среднем коэффициенте ветвления и вероятностях безотказной рзботы (ВБР) элементов СПД в пределах [0.9,0.991 погрешность не превышает 6+8$. Учитывая, что точность входной информации на стадии проектирования сети порой значительно превышает указанную

погрешность (достигает 100$), переход к схеме с независимыми подсистемами при определенных значениях kß> 1 можно считать вполне допустимым.

С учетом высказанных допущений функционирование исполнительных подсистем распределенной СПД описывается обобщенной (неоднородной) схемой испытаний Бернулли ( р°в * р°в, i,j в * ). Однако, даже при небольшой количества исполнительных подсистем (20 + 30) расчет р(^Сзад) в этом случае еще требует серьезных вычислительных затрат.

Теорема. Вероятность р^т.п) в неоднородно! схеме Берну лли с вектором параметров < р1( 1=1,п > ограничена онизу вероятностью р°(m+k,n+w) для случайных величин, имеющих однородное Синомиаль-

ное распределение о параметром р «( П р. )*''<ntk>, то есть

I«»

РН(»,п) i P°(«+Jc,n+k), (5)

1 ä и i n, k « 0,1, ... .

Следствие. Для любого к - о, 1, ... имеет меото следующее соотношение:

P°(m,n) 2 P°(m+k,n+k) ,

k = О, (,',.., I S • S n,

где px = p"""*1", Pt, pa - параметры распределений для однородной схемы испытаний Берну лли длины п и n+k соответственно.

Таким образом, наилучшей из семейства p°(nn-k,n+k) с точки зрения оценки вероятности в неоднородной схеме испытаний Берну лли является оценка (б) при к « о.

Отметим некоторые особенности применения полученных оценок. Так, при Pj 0, j«uo применять оценку (б) следует к предельному распределению :

• lim PH(m,n) •= PH(m,n-k ) .

|J |=k °

1 о1 о

При Pj 1, j <i Jt переход к предельному распре деланию

lim PH(m,n) = PH(m-k -,n-k )

|J | = k 11

» i

позволяет значительно сократить объём вычислительных затрат, необходимых для расчета рн(ш,п). При решении практических задач правила формирования множеств и .1 могут быть определены на основе особенностей поведения и физической природы элементов исследуемой системы.

В классе нижних оценок предлагаемые оценки имеют существенное преимущество по сравнению с известными (основанными на построении минимальных путей и минимальных сечений) не только с точки зрения трудоёмкости вычислительных затрат, но и, как показывают экспериментальные данные, - величины погрешностей. Так, для реальных коэффициентов готовности элементов СДД, находящихся в диапазоне I0.9,0.99), значения вероятностей связности исполнительных подсистем СПД не выходят за границы отрезка 10.65,0.951. При этом максимальное значение погрешности для оценки (5) при к=0 не превышает ЗЖ, а для ценки Эзари-Прошана - 60Ж.

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

Р°( Е°> ? ) £ рсв . (6)

к 5 ?зад' зад * 1 '

п

где случайная величина ? = Е '» п-1у1. имеет однородное бино-

•»=1 о

миальное распределение, а слагаемые ^ V - распределение Бер-нулли с параметрами

Г п __ \1/П

р - ( ий Р? ] • т

Очевидно, что при удовлетворении условия (6) выполняется и неравенство (2), в то время как применение оценок, отличных от нижних, на обеспечивает строгости указанного перехода.

Применяя при больших значош!ях п известное нормальное приближенно Муавра-Лзпласа к одпордному биномиальному распределе-

зад)

ншо (при условии р°(?° >со„п)20.б), ограничение (6) преобретаот

вид =

®„С <2пр - 1 )/ /4лр(1 -р) ) * Р-Д- 1/2 , ^ (8)

где Фо(х) - интегральная функция Гаусса, определенная на отрезке с0,х1. функция Ф0(х) мокет бить вычислена с помощью известных численных методов практически с любой степенью точности.

Отметим, что при решении задачи топологического синтеза сети, содоржащой н узлов, число вариантов их соединения имеет нижнюю

границу (1-2н2"м'/2)2ы'ы","'г, а верхнюю границу Поэто-

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

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

1) синтез начальной структуры в виде минимального остовного • дерева (МОД) при ограничении на ВСД сообщений (пакетов) в отдельной линии связи;

2) выбор пропускных способностей (ВПС) МОД при ограничении на ВСД сообщений (пакетов) в сети (1). В процессе решения данной задачи обеспечивается минимум стоимостных затрат;

3) синтез работоспособной иерархической СПД.

Особенностью такой декомпозиции является то, что при решении

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

Для синтеза начальной СПД (МОД) предложен алгоритм, основанный на известном методе Иссау-Вильямса, модифицированный вводом огрзничонния на ВСД сообщений. Алгоритмы решения задач 2 и 3 ис-

пользуют принципы метода последовательных приближоний, а такие катода опешсп показателей вероятности связности и ВСД сообщений. Алгоритм решения задачи 2 (ВПС) имоет следующий вид г Шпг 1. Формируется множество номеров неработоспособных Ш :

_ < J , < рСДд, ^

Шаг 2. Выбираем ветвь (г*,5*) с максимальным эффектом :

(г ) = 1п<3тах { а > .

(к) 1 а

(г ,в>еЕ ..¡еЛ ) 1

где ая = (рн-рсд""1')/Дсг1; рн, дсг1 - новое значение ВСД сообщений СГЩ рн и приращение стоимости ветви (г ) соответственно, рассчитанные после увеличения ПС в ветви (г.з) на величину минимального шага ь = Н0Д(с11, аа.....ак).

Шаг 3. Устанавливаем для ветви (г*,г*) с максимальным эффектом атох новую пропускную способность = <знж ж .

гш та

Шаг 4. Опродоляом ВСД сообщений в отдельных ИП , jGY и

СПД в целом рсд,1(:

Шаг 5. Если условие рСДсЬ,> выполняется, то конец алгоритма. В противпом случае к = к + 1 и переход на шаг 1.

Алгоритм синтеза работоспособной СПД (задача 3) имеет следующую структуру :

Шаг 1. Формируется множество номеров неработоспособных ИП -. . у)<> = { , рсв.к-»г р«> ^ } ?

где р* - достаточное значение вероятности связности в ИП, определяемое из (8).

Шаг 2. Выбираем в&твь (г'.э*) с максимальным эффектом =

(г*,з*) = 1пс!тах < а > ,

4 * ' га

_1Ь

(г , е>е£

где е<к' = е^'и е^'и е;к\

г.шожоство ботвой, для которых производится резервирование КС; Е;к'= < - ВДО-

жоство сущоствующих вотвой, вводимых в структуру НП jcj' е^к>=1 (г,2)в£1к~1>, ге^1"1', (к 1 1г£. £ 1ро> - множэство новых ветвей, анализируемых при вводе в СДД;

ар== (рн-рсв<к"4> )/Асгз, где рн, Дсгз- новое значение вероятности связности СДД и приращение затрат соответственно, получаемые при вводе в эксплуатацию дополнительной линии связи между узлами г и я.

Шаг 3. Устанавливаем линию связи (г*,**) с максимальным Эффектом : Е]к>= Е^к-"и (г*,г"), г* е ^,

Шаг 4. Определяем новые значения вероятностей связности Ш1 р°в<к>, J 6 * и всей СПДРсв"".

Шаг Б. Если условие (7)-(8) выполняется, то конец алгоритма. В противном случае к » к + 1 и переход на шаг 1.

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

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

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

2. Предложена методика оценки вероятности связности заданного числа абонентских пунктов с центром, а также вероятности своевременной доставки сообщений (пакетов) в иерархических сетях

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

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

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

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

6. Предложенные модели и методика анализа функционирования и топологического проектирования иерархических сетей передачи дашшх реализованы в виде соответствующего ППП и апробированы.при разработке проекта модернизации СОД специального назначения в Центральном научно-исследовательском институте машиностроения. Результаты роботы внедрены в учебный процесс в Киевском политехническом шшитуто для студентов специальности -Прикладная

матомаиага" по курсу "Математическое моделирокши-г; ппр&шиышх

ПрОЦЭССОВ" .

1. Зайченко Ю.П., Супрун А.Д. Нижние оценки в неоднородной схеме испытаний Бернулли // Азтоматика, 1992.- n 4.- с.44-52.

2. Зайченко Ю.П., Супрун А.Д., Алгоритм синтеза структуры распределенных сетей передачи данных с ограничениями надежности и живучести // Вопр. экономики и организации информационных технологий : Матер. Всесоюз. научно-практической конференции.-Гомель, 1991.-ч.1.- с.170-173.

3. Зайченко Ю.П., Супрун А.Д., Швидкий O.A. Модели анализа надежности и живучести вычислительных сетей и синтеза их структуры // 3 Всесоюз. совещ. по распределенным автоматизированным системам массового обслуживания: Тез. докл. - Москва, 1990. -с. 117-118.

4. Зайченко Ю.П., Супрун А.Д. Алгоритм синтеза структуры древовидных сетей о ограничением надежности // 4 Всесоюз. совещ. то распределенным вычислительным системам массового обслуживания: Тез. докл. - Москва, 1991, с.84-85.

5. Зайченко Ю.П., Супрун А.Д. Синтез структуры иерархической СДД с вероятностно-временными ограничениями // 5 Совещ. по распределенным вычислительным системам и сетям (cds-92) : Тез. докл. - Калининград, 1992, с.43-45.

6. Зайченко Ю.П., Супрун А.Д. Об оценке надежностных характеристик сети передачи данных в задаче топологического синтеза // 4 Всесоюз. совещ. по распределенным вычислительным системам массового обслуживания: Тез. докл. - Москва, 1991, с.67-68.

РАБОТЫ, ОПУБЛИКОВАННЫЕ ПО ТШЕ ДИССЕРТАЦИИ

'Автор

Супрун А.Д.

Поди, к печ. ä.zof.9?,. Форматc.o'tv/t Бумага'«»,

Печ. офс. Усл. печ. л■ С, 9Л Уч.-изд. л. О, 6 6 Тираж ь'о

Зак.Л-.iCJf/ ■

Киевская книжная типография научной книги. Кнео, Репина, 4.