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

Министерство приборостроения,

средств автоштизации Акалемия нвуи СССР

и систем управления Академия наук илг

СССР

Ордена Ленина Институт проблем управления (автоматики и телемеханики)

На правах рукописи . ЧИЧИНАД8Е РЕВАЗ ВШАНГОВМ

УДК 681.32:512.2 РА8РАБ0ТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ МАШРУТИЭАЦИИ

ИНФОРМАЦИОННЫХ ПОТОКОВ ПРИ ПР0ЕК1ИРШАНИИ ' ВЫЧИСЛИТЕЛЬНЫХ СЕТЁЙ МАССОВОГО 0БСЛУ1ШАНШ

Специальность 05.15.13 - Вычислительные маиивы, комплексы, 1 системы и сети

, ; Автореферат

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

Москва-! 990

Работа выполнен? в ордена Ленина Институте проблей управления (автоматики и телемеханики) Ыинприбора и АН СССР.

Научный руководитель - доктор технических наук, профессор

Хохикашвили Б.А.

Официальные оппоненты - доктор технических наук, профессо{

Трахтенгера Э.А.

кандидат технических наук, старшие научный сотрудник Черкасов Ю.Н.

Ведущая организация - Главный вычислительный центр гражданской авиации (ГВЦ ГА), о

8авдта состоится час.

на заседании Специализированного совета № 2 Д002.68.01 Института проблем управления по вдреоу: 117342, г.Москва, Профсоюзная ул., 65.

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

Автореферат разослан " /о" 19Э0г.

Ученый секретарь ... Специализированного совета ; д.т.н., профессор;

В.В.Игнатущенко

■Актуальность работь:. С развитием научно-технического про-

I

гресса растет объем передаваемой информации в различных сферах производства и научно Г. деятельности. Это требует создания высокопроизводительных, отказоустойчивых систем обработки и передачи данных, позволяющих: сократить затраты на обработку информации, обеспечить требуемое качество обслуживания, предотвратить неэффективное распределение и использование вычислитель них ресурсов. К таким системам могут бить отнесены 'распределенные вычислительные системы массового обслуживания, предназначенные для распределения ресурсов и выдачи информации различным пользователям.

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

.1 настоящему времени разработано и исслодовано большое чи-с..о методов и алгоритмов, посвященных реыгшв разлита« задач проектирования СПД (выбор топологической структуры СГЩ,^ыбор пропускных способностей и^распредел'ение потоков, анализ буферной памяти, управление потоком и т.п.). Аналку этих рабоя показывает, '¿ю задача определении оптимальных маршрутов поре,7а-чг информации в СЩ (задача маршрутизации) элнима'.'т одно ял

— я, -

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

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

оптимальные виртуальные маршруты передачи информационные потоков;

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

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

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

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

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

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

- Разработка алгоритма выбора пропускной способности и альтернативных маршрутов для отыскания оптимальной стратегии последовательного во времени повышения производительности в • развивающейсй СПД;

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

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

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

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

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

- метод отыскания шиной оценки среднего времени досгалки сообщений;

- аналитический метод расчета среднего времени доставки :.:ногопакетннх сообщений при использовании альтернативно;! маршрутизации;

- б -

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

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

Реализация результатов работы. Научные и практические результаты диссертации использованы при проектировании, внедрении и развитии Общесоюзной системы управления продажей билетов и бродарованием мест на внутренних авиалиниях "Сирена-2", разработанной в соответствии с программой работ по решению научно-технической проблемы 0.80.09, утвержденной Постановлением ГШ и Госплана СССР от 8.12.1981г. № 49Г/244 (прилоае-иис К; €¿0 и по совместному приказу Минприбора СССР и 1.ТА СССР !,'? 96/182 от 8.07.1982г.

Методика оптимального повышения производительности сети в процессе эксплуатации, разработанная в диссертации, была попользована в ГВЦ ГА при подготовке системы "Сирена-2" к летней навигации 19о9г.

Апробация работы. Основные положения диссертационной работы д0!сг.г)д1ша;;псь и обсуждались на 4-П и 5-й всесоюзных ико-лпх-сомнка^ах по распределенным автоматизированным системам

массового обслуживания (Кутаиси, 1987; Москва, 1988); на 5-м Всесоюзном семинаре "Распределенные информационно-управляющие системы" (Саратов, 1988); на 11-м Всесоюзном совещании по проблемам управления (Москва, 1988).

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

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

таблиц. Список литературы имеет наименований. "

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

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

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

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

I!

- е -

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

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

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

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

алгоритм позволяет оптимизировать сеть по этим критериям. Под разнородностью каналов понимается, что часть аппаратуры передачи данных в СПД "Сирена-2" работает в полудуплексном режиме. Чтобы учесть режим передачи каждого кайал& связи, введем матриц^ типов каналов (} =11^11 , где

I, если канал з линии (ы) работает в дуплексном режиме;

О-в противном случае.

Перейдем к постановке задачи.

•■ Известны: I) топологическая структура СГЩ, заданная в виде матрицы смежности Н =112^11 « 2) матрица информационных потоков » 3) средняя длина пакета ; Ф) пропускная способность канала связи В1 ; 5)0=119^11 режим передачи данных (I - дуплексный, 0 - полудуплексный) в

ЛИНИИ СВЯЗИ (и) --И) • 6) У—ИУцИ - чис-

ло пналов в пучке (1«|) (,1к)=1|2,'..-11') ; 7) - точ-

но" ть решения.

Хребуоюя найти: I) - средняя задержка сообщений в сети; 2) '•Г^Ц^Ц - задержка сообщений между всеми парами узлов (2 ) = 5 3) Р=11$ц!! - величины

потоков в' линиях связи (и^) и.<Ы)2, ...М) ; 4) эаотузки каналов связи в линиях (Ц) С^ —'»--К) , ее-

ли 1)^=0 £¿=0 1 5)

б) /и-^Ы

Введем переменные О^ЯС^ , определяющие долю

потока между уэлами Т и £ , передаваемого по линии (С,.р . В частности, если в о или I, то в СЦЦ применяется фик-

сированная маршрутизация; в противном случае - альтернативная маршрутизация. При этом в случае системной оптимизации минимизировать функционал

N N

и. -¿й С1)

я ^ п '

где Де - суммарный входной поток. С учетом разнородных каналов выражение (I) будет,иметь следующий вид; •» N N

Я*

В случае пользовательской оптимизации минимизируется функционал

ТН=Г Г и лш_

Ч-* 1—1

и!

О учетом разнородных каналов выражение (2) имеет вид при следующих ограничениях:

n , , г—I

1=5 О, ь^тз -I, иг

-

(5)

' «м

Г ■ 4 Уд

(б)

5.-1

Условие (3) отражает связь между переменными и

3^=0 ' если 2у=0 , и 7о , если . Огра-

ничение (5) обеспечивает условие сохранения потока в сети. Выражение (6) определяет, что величина потока в канале не должна превосходить его пропускную способность.

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

I

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

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

Пусть V/ - длина пути в виртуальном соединении между парой узлов ; 1_с - среднее число пакетов в многопакетном сообщении; $ - загрузка линии связи на С-м меиузловом соединении; ^ - средняя длина пакета.

Тогда среднее время доставки многопакетного сообщения для альтернативной маршрутизации определяется следующим образом:

»««*>т- (7, '

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

по ыарируту К , где

иг 1 * №

Здесь | С**,,! - совокупность всех подмножеств из элементов Ы -элементного множества Г=|М>"*^

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

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

[1 и

Е Ем

(2)

где } - суммарный внутренний поток в сети, который определяется по формуле Клейнрока: | «Я^ > где ^ ~ средняя длина пути в сети. Теперь для определения нижней оцеши средней задержки пакетов в сети, использовав метод неопределенных множителей Лагранжа, получим

N N

т« ^У-1 Г-

-21Л

дм

I «

где Л. - средняя длина пути в данной сети, 1А - число линий связи в сети. Соответствующее выражение выведено с учетом применения в сети разнородное каналов (т.е. для выражения (2'))!

' »1 -

где Л^ - общее число дуплексных каналов в сети равно

1 С»' ¿=1

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

СПД представляется неориентированным графом ,

вершины которого соответствуют узлам СПД, а ребра - линиям связи, т.е. - число вершин 6 , (А=1Е1 - число ре-

бер. Воем ребрам графа О приписаны неотрицательные веса Сч - стоимости аренды каналов связи между узлами Л 'и <} . Под стоимостью & понимается сумма весов, вводящих в & ребер. Итак, известны:

I) С =110^11 - матрица стоимостей аренды каналов свя-8и; 2) Л*ИЛ«11 - матрица информационных потоков; 3) ограничение на надежность (связность сети КсЬ=Д ; диаметр сети ; диаметр сети при отказе ребра или узла 4с1г )»

Ь) ограничение на время доставки сообщения - Тто.* ; 5) пропускная способность канала связи - В ; 6) средняя длина пакета - . Требуется найти: I) топологичеокую структуру ости (матрицу смежности соответствующего ей графа 0> )

2 = |1Ец11 5 2) количество каналов в каждом межузловом соединении ? ^ потоки Р ^ 4) оптимальные маршруты между всеми парами узлов П ?

(1.5) I- Л

Введем булевы переменные: Уу =( , если ребро

входит в один пз К независимых пу^ей между чсршинаып Ъ

к^п п-{гл)

и ■> ; Од- -и- в противно?! з:'/чао; У-ц имеет юг

- -

же смысл, что и в гл. 2.

Математическую модель задачи можно сформулировать в следующем виде.

Минимизировать функционал-N и

тт тг1

ГС N

при ограничениях

' N

^ у,г. , * (10)

м (га А

.1-1 ,1-1 Г"~) (г.»)

г-'

¿,4=«.л,-.. N

о

Яд

о

Е1* I-0,; (£Л

(И)

(12)

^ 2 с] (13)

N

(15)

(Лб)

(17)

N N (Ъ)

ч Е (18) ,

Условия (10)-(13) гарантируют наличие не менее двух независимых путей между каждой парой узлов;'условие ограничивает длину кратчайшего пути между каждой парой Т,5 величиной с)-| .

Условия (15)-(20) совпадают с условием (З)-(б) в задаче, поставленной в гл. I диссертационной работы. Для решения данной задачи разработано большое число алгоритмов, которые условно можно разделить на три класса: аналитический, эвристический и комбинаторный. Анализ этих алгоритмов показал, что наиболее подходящим с точки зрения поставленной в данной главе диссертации задачи (исследование влияния способа маршрута-вации на топологическую структуру сети) является комбинаторный подход. Для исследования выбран эффективный алгоритм комбинаторного типа, разработанный Е.В.Федотовым в Институте проблем управления, который включает следующие задачи:

- генерация двухсвязных основных подграфов заданного грач фа & ;

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

- определение нижней оценки стоимости сети с учетом информационных потоков;

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

- проверка ограничений на надежность.

При решении задачи выбора пропускных способностей и распределения потоков ранее применялась фиксированная процедура выбора маршрутов. Проведенные в диссертационной работе сравнения на примере сети "Сирена-2" показали значительное преимущество альтернативной маршрутизации перед фиксированной (разница в стоимости при решении задачй топологического синтеза СПД с применением альтернативной процедуры выбора маршрутов по сравнению с фиксированной достигала 262 800 руб/ год). Исходя из этого, в диссертационной работе при решении задачи синтеза топологической структуры сети предложено применить алгоритм альтернативной маршрутизации, рассмотренный в гл. 2.'Однако, альтернативная процедура маршрутизации требует на порядок больше времени по сравнению с фиксированной! что затрудняет ее применение при проектировании сетей с большой и средней размерностью. В связи с этим была проведена модификация алгоритма синтеза топологической структуры СПД с целью расширения области применения алгоритма альтернативной процедуры выбора маршрутов. Рассмотрены три случая применения этого алгоритма.

I. При решении задачи синтеза топологической структуры сети на этапе выбора пропускных способностей и распределения потоков используется алгоритм "подъема" (BcUorrucp) » ко_

Xi - 18 -

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

2. Декомпозиционный подход, который состоит в следующем:

а) решается задача топологического синтеза с фиксированной маршрутизацией;

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

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

f

нонагруяенных линий, который позволяет эффективно решать задачу распределения потоков с фиксированной маршрутизацией. Затем применяется алгоритм "спуска" (lep down.) , позволяющий удалить некоторые каналы в анализируемом варианте, выдерживая основные ограничения на качество функционирования сети.

В четвертой главе результаты предыдущих глав применяются для расчета топологической структуры СЦД "Сирена-2". Приведено описание реально функционирующей сети передачи данных системы "Сирсна-2" по состоянию на 1989г. Проведен анализ развития топологической отруктуры СПД "Сирена-2", состоящий в выборе последовательности топологических структур

V2,... Ьц , где К - общее число этапов внедрения, та-что к. 1

/ С(Рс) —-mm-i-i ■

где С _ стоимость аренды каналов для структуры Период развития СПД "Сирена-2" с 1987 по 1990гг. разбит на 4 этапа. В связи с этш рассматривались два варианта развития СПД:

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

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

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

Анализ измерения характеристик СПД сиотемы '"Сирена-2" показал, что они не всегда соответствуют проектным требованиям, что вызвано целым рядом причин. Для повыиения пропускной способности СПД "Сирена-2" и улучшения ее характеристик разработан алгоритм последовательного увеличения пропускной способности каналов связи, базирующийся на алгоритме альтернативной маршрутизации, предложенном в гл. 2. (Под увеличением пропускной способности подразумевается последовательный перевод каналов о полудуплексного режима работы на дуплексный и замена аппаратуры передачи данных с пропускной способности 1200 б"Д на 2400 бод.) Разработанный алгоритм позволил с минимальными затратами обшпечитт максимально возчояноо увеличение пропускной способности сети "Сирсиа-2".

Разработанный в гл. 2 метод распределении потоков позли1:;'." ет'получить зирхуалышс :лрпрути с ветвление?: поток! соо*п; =

- '¿ю -

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

Разработанные в диссертации алгоритмы реализованы в виде программных модулей на языке Фортран-1У. Модули объединены в комплексе программ "Маршрутизация", являющемся составной частью системы автоматизации проектирования сетей передачи данных, разработанной в Институте проблем управления. £ '

Приложения содержат: описание исходных данных, используемых при проектировании СПД "Сирена-2"; описание алгоритмов, используемых в гл. 3 для решения задачи топологического оин-теза СПД; акты, о внедрении результатов работы.

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

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

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

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

©

ЦИИ. ' - ' .

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

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

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

«

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

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

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

>

9. Сформулированы рекомендации по применению метода виртуальных соёдинений с ветвлением потока сообщений от узла-источника для сети "Сирена".

10. На основе разработанных в диссертации алгоритмов создан комплекс программ, являющийся сосгавной частью системы автоматизации проектирования сетей ЭВМ, разработанной в Институте проблем.управления. Этот комплекс активно применялся при проектировании сети ЭВМ "Сиреиа-2". Экономический эффект от внедрения; результатов диссертации составил 40 тыс. рублей.

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

в следующих работах:

1. Федотов Е.В., Чичинадзе Р.В. Алгоритм синтеза топологической структуры развивающихся сетей ЭВМ //Распределенные автоматизированные системы массового обслуживания. Тезисы докладов, 4-й Всесоюзной школы-семинара. - Кутаиси: Кутаисский политехнический институт, 1987, с, 9-10.

2. Вишневский В.К., Федотов Е.В., Чичинадзе Р.В. Анализ влияния алгоритмов маршрутизации на оптимальную топологию сети пакетной коммутации. //Пятая всесоюзная школа-семинар по распределенным автоматизированным сиотемам массового обслуживания. Тезисы докладов, - М., 1988, с. 150.

3. Вишневский В.LI., Оедотов Е.В., Чичинадзе Р.В. Методология и алгоритмы исследования динамики развития структур сетей пакетной комвдтации //Тезисы докладов 5-го Всесоюзного семинара "Распределенные информационно-управляющие системы". -Саратов: СГУ, 1988, с. 18.

к. Чичинадзе Р.В. Об одном алгоритме альтернативной маршрутизации //Пятая всесоюзная школа-семинар по распределенным автоматизированным системам массового обслуживания. Тезисы докладов. -М., 1988, с. 256-257.

5. Жожикаивили В.Л., Вишневский В.И., Федотов Е.В., Чичинадзе Р.В. Задачи и алгоритма построения развивающихся сетей ЭВМ //Тезисы докладов 11-го Всесоюзного совещания по проблемам управления. - !.!.: КПУ, 1989, с. 272-273.

6. Чичинадзе Р.В. Модифицированный алгоритм отклонения потоков для исследования интегральных характеристик сетей ЭВМ //Сообщения Аü ГССР.- I9S9.- Ii? 3.- Т. 134.- С. 81-83.

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

о6чрбэл(}оэео 6i)¿¿eobob Súrttlrt^doVicjoob «С&ОАОФЭЭЬОЬ

çù aù3fiJ3C33b ЭйЬоЬЛозо 8оЭЬйЬэЛзЬоЬ &й8оазсоао 31»0СЗЬоЬ сгЗАпзДОэЬоЬ çrtob

лзйоЛзедЛово cftjbac обг>%гр