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

ип

СП СП

<=» О-

ш ^

I— ^ О- ""*

АКАДЕМИЯ НАУК АЗЕРБАЙДЖАНА ИНСТИТУТ КИБЕРНЕТИКИ

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

АЛГУЛИЕВ РАСИМ МАГАМЕД ОГЛЫ

УДК 681.324

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

05. 13. 14 - Системы обработки информации и управления

АВТОРЕФЕРАТ

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

БАКУ - 1995

Работа выполнена в институте Кибернетики Академии Наук Азербайджана

Научный руководитель: член-корр. АН Азербайджана, доктор

технических наук, профессор АЛИЕВ т.А.

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

академик Международной Академии Информатизации кульба в.В.

доктор технических наук меликов А.з.

Ведущее предприятие: Институт Системного Программирования

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

Защита состоится " ¿т " марта 1995 г. в II00 часов на заседании специализированного совета Н.004.21.01 при Институте Кибернетики Академии Наук Азербайджана по адресу: 370141, г.Баку, ул.Ф.Агаева,9.

С диссертацией можно ознакомится в библиотеке института Кибернетики АН Азербайджана

Автореферат разослан " 20" февраля 1995 г.

Ученый секретарь специализированного нусратов O.K.

-з-

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

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

В настоящее время сети передачи данных с коммутацией пакетов (спд с кп), построенные в соответствии с эталонной моделью взаимодействия открытых систем мое и Рекомендацией Х.25 мкктт, получили широкое распространение во многих развитых странах мира (TELENET в сша, TRANSрас во Франции, DATAPAC в Канаде, .DATEX-P в ФРГ и т.д.), эффективность которых зависит от технических характеристик, применяемых в них центров коммутации пакетов (цкп). с • увеличением нагрузки на спд с кп характеристики эксплуатируемых цкп не могут удовлетворять предъявленным к ним требованиям. Анализ принципов построения существующих в мире наиболее известных'цкп показывает, что их низкая эффективность, в основном, связана с тем, что в таких цкп реализованы статические методы маршрутизации и выбор путей передачи пакетов на спд с кп осуществляется централизованно. с другой стороны, организация процесса коммутации пакетов и используемые в них аппаратно-программные средства вт и техники связи не отвечают современным требованиям . кроме того, появление мощных и относительно дешевых микропроцессорных средств, производство ведущими фирмами мира сетевых узлов на бис, а также разработка эффективных методов динамического управления потоками информации и ратификация международными организациями новых стандартов в данной области создают необходимую предпосылку для проектирования высокопроизводительных; отказоустойчивых и многофункциональных цкп на базе микропроцессоров, обладающих свойствами модульности, развиваемос-ти, гибкости и т.д.' Исходя из этого, тема настоящей диссертационной работы-посвящена вопросам разработки и исследования методов проектирования многомикропроцессорного цкп с адаптивной маршрутизацией.

Цели и'задачи работы. Целью диссертационной работы является разработка многомикропроцессорного (ММП) ЦКП С шинно-кольцевой структурой, позволяющего реализовать методы динамического управления • потоками информации, службы Рекомендации Х.25 МККТТ,

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

- анализ принципов построения существующих в мире наиболее известных ЦКП в целях определения их преимуществ и недостатков, а также тенденции развития их архитектуры в зависимости от текущего уровня ВТ и техники связи;

- разработка методов декомпозиции протокола сетевого уровня (СУ) ЦКП с адаптивной маршрутизацией;

- разработка математической модели и алгоритмов для оценки эффективности методов декомпозиции протокола СУ ЦКП с адаптивной маршрутизацией;

- разработка однокритериальных и многокритериальной оптимизационных моделей и алгоритмов для структурного синтеза ММП ЦКП с адаптивной маршрутизацией;

- разработка алгоритма для определения порядка подключения микропроцессорных (МП) модулей к шинам с маркерным доступом в локальных группах ММП ЦКП с адаптивной маршрутизацией;

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

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

Научная новизна диссертационной работы заключается в следующем! .

- определена тенденция развития архитектуры ЦКП, с учетом которой разработаны методы декомпозиции протокола СУ;

- предложены математические модели и алгоритмы для оценки эффективности методов декомпозиции протокола СУ, которые позволяют автоматизировать проектирование ММП ЦКП;

- сделан системный подход к структурному синтезу ММП ЦКП, для осуществления которого разработаны однокритериальные и многокритериальная оптимизационные модели и алгоритмы;

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

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

Практическая ценность и реализация результатов работы.

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

- в связи с реализацией всего набора служб Рекомендации _ X.25 разработанный ММП ЦКП может применяться в создании других сетей пакетной коммутации с распределенным управлением;

- возможность функционирования ММП ЦКП с различным количеством линий связи в реальном масштабе времени позволяет существенно снизить ' затраты на эксплуатацию сети в "условиях изменяющейся нагрузки;

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

- при помощи предложенных моделей и алгоритмов модернизированы и расширены функциональные возможности ЦКП, эксплуатируемых в региональной компьютерной сети AZERNET Совместного Азербайджанско-Российского предприятия "Азеринком";

- результаты работы были использованы при разработке и внедрении I и II очередей Республиканской информационно-вычислительной сети с пакетной коммутацией, а также в создании азербайджанских узлов международной компьютерной сети INTERNET;

- предлагаемый 1 ММП ЦКП с шинно-кольцевой структурой в качестве конкурентноспособного технического продукта на мировом рынке телекоммуникационных средств включен' в план производства перспективных разработок Азербайджанского Научно-производственного объединения "Улдуз".

Апробация работы. Основные результаты работы докладывались: на V Всесоюзном симпозиуме по проблемам управления на сетях и узлах связи (Винница, 1985 г.); на VI Советско - Итальянском семинаре по сетям коммутации пакетов (Москва-Суздаль, 1986 г.); во

Всесоюзной школе "Проектирование автоматизрованных систем контроля и управления сложными объектами" (Туапсе, 1986 г.); на научной конференции аспирантов АН Азерб. ССР (Баку, 1987 г.); на XII Всесоюзном семинаре по вычислительным сетям (Москва-Одесса, 1987 г); в 3-ей Всесоюзной школе "Проектирование автоматизированных систем контроля и управления сложным объектами" (Харьков, 1988 г.); в V всесоюзной школе "Распределенные автоматизированные системы массового обслуживания"1, (mockbs- Рига, 1988 г.);

!

на Международной конференции по сетям INE? 93 ..(Сан-Франсиско, 1993 г.); ка Международном симпозиуме по компьютерам (Конья, 1993 г). Кроме того, основные положения диссертации с.бсуждались на семинарах Института Проблем Передачи Информации Российской АН, Таганрогского Радиотехнического Института им.В.Д.калмыкова, Института Кибернетики и отдела Автоматизированных Систем Управления АН "Азербайджана.

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и трех приложений, общий объем дисссертации 155 страниц, в том числе 125 страниц машинописного текста основной части, 7 страниц списка литературы, включающего 86 наименований, 29 рисунков, 5 таблиц и 23 страниц приложений в тексте.диссертации.

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

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

Первая глава посвящена архитектурным запросам построения ЦКП, особое ударение делается на ЦКП, функционирующее в соответствии с эталонной модель» взаимодействия отг.рктых систем (ЭМВОС) и Рекомендацией X.25. здесь всесторонне'исследуются гротоколы физического, кгнзльаого и сгтевргЬ урегнев;- Лспьзано, что по выполняемым функциям протоколы СУ àsdhgk-cscff■ э2.ч-н ЦКП б значи-

тельной. степени отличаются друг от друга. В связи с этим, считается, что нет необходимости в выполнении функций коммутации и маршрутизации пакетов на СУ АВМ. С другой стороны, способы реализации СУ во многом определяют архитектуру ЦКП, которые непосредственно влияют на показатели эффективности функционирования СПД с КП. Таким образом, определена логическая, структура ЦКП, где в качестве протоколов сетевого, канального и физического уровней используются протоколы Х.25/3, LAP в и Х.21 Рекомендации X.25, соответственно. Здесь особое' внимание уделено вопрссам, связанным с установлением виртуального канала (ВК), передачей данных и разъединением ВК, по результатам которых построена временная диаграмма сеанса связи по коммутируемым ВК Рекомендации Х.25 на входящем DTE^/DCE^ и исходящем DCE2/DTE2 стыках СПД с КП. Далее, в соответствии с поставленными в работе задачами, анализируются протоколы сетеметрической службы в целях их реализации в ЦКП. Как известно, эффективное функционирование СПД с ЦКП, в основном, зависит от качества управления сетью, которое непосредственно влияет на внутреннюю архитектуру протокола СУ ЦКП. В связи с широким распространением в последнее время методов динамического управления потоками информации в работе исследуется сеть с распределенным управлением, т.е. в таких сетях каждый ЦКП анализирует информацию не о всей сети, а лишь локальную информацию о ближающих к данному ЦКП участках сети.-

В этой главе в эволюционном порядке анализируются принципы построения ' существующих 'в мире наиболее известных ЦКП, определяются их достоинство и недостатки, а также тенденция развития их архитектуры в зависимости от. текущего уровня ВТ и техники связи. В частности, подвергаются исследованию однопроцессорные ЦКП на базе мини-ЭВМ, однопроцессорные ЦКП на базе МП, ММП ЦКП с шинной и кольцевой структурами. Анализ принципов построения ЦКП показал, что их архитектуру, в основном, определяют способы технической реализаци:: функций СУ и организации внутренней среды связи между модулями. Это, в.первую очередь, связано со сложностью и в какой-то степени- неопределенностью СУ ЭМВОС и пакетного уровня Рекомендации " Х.25. При этом серьезные проблемы возникают при выборе метода . маршрутизации. В существующих структурах, в основном, реализуются статические методы маршрутизации, а управление СПД с КП осуществляется централизованно или, в -лучшем случае, слабо де-

-в-

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

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

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

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

- декомпозиция, ориентированая на комбинированное разбиение задач по функциям и нагрузке.

В разделе 2.1 разработан метод декомпозиции по функциям, по которому протокол СУ ЦКП разбивается на четыре горизонтальные подуровни: 1) подуровень 1: прием и выдача пакетов (ПУ1), 2) подуровень 2: коммутация пакетов (ПУ2), з) подуровень 3: маршрутизация пакетов (ПУЗ), 4) подуровень 4: управление маршрутами (ПУ4). Здесь каждый из подуровней детально анализируется и из него выделяются, протокольные объекты (ПО), предназначенные для выполнения отдельных функций протокола СУ ЦКП. В частности, ПУ1: ПО "процесс приема пакетов" и по "процесс выдачи пакетов"; ПУ2 : ПО "входной ■ буфер", ПО "массив путевых номеров", ПО "процесс коммутации пакетов" и по "выходной буфер"; ПУЗ: ПО "массив состояний логических каналов в линиях связи", ПО "массив состояний логических каналов в абонентских линиях связи", ПО "массив маршрутов", ПО "массив инциденций АВМ к абонентским линиям" и ПО "процесс маршрутизации пакетов"; ПУ4: ПО "массив вероятностей распределения пакетов", ПО "блок вычисления вероятностей распределения пакетов" и ПО

"процесс управления маршрутами". Отметим, что на ПУ4

непосредственно выполняются функции динамического управления распределением пахетов по исходящим линиям связи ЦКП, для осуществления которых используется игровой метод, далее, в разделе 2.2 предлагается метод декомпозиции протокола СУ ЯКП, занимающий промежуточное место между горизонтальным и

вертикальным разбиениями, по которому ПО подуровней ПУЗ, ПУ4 протокола остаются как на горизонтальном, так и вертикальном разбиении. ПУ1 полностью разбивается на л вертикальных уровней для обслуживания линий связи. И, наконец, в целях уменьшения нагрузки и организации параллельной обработки на ПУ2 выделяются специальные ПО, прикрепленные к конкретным типам пакетов служб Рекомендации X.2S. Далее, в разделе 2.3 разрабатывается математическая модель и алгоритм, которые позволяют оценить тот или иной метод декомпозиции на стадии проектирования ММП ЦКП. С этой целью протокол СУ ЦКП разбит на две части: пакетный (ПП) и коммутационный (КП) подуровени для каждой линии связи. ПП выполняет функции х.25/3, а кп - функции коммутации, маршрутизации и управления маршрутами. Допустим; что в результате

применения методов декомпозиции КП получены графы G =(Е ,Г ),

(s) s s s

где Es - множество ПО , Гд - множество дуг, описывающих

взаимодействия между ПО и i,j=i,n , s=i7k. Здесь

Д. j s

k - количество вариантов декомпозиции, а ^-количество узлов графа Gs. В качестве показателя оценки распределенных Fs структур ММП ЦКП принимаем среднее время t пребывания примитивов в них, полученных в результате физической реализации графов G , для определения которого используется основное положение марковсхой сети массового обслуживания (СеМО). Для

(а)

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

(s) ' 1

MjT с -собственными компонентами (RAM,ROM и т.д.) и при

отображении графа G на физическую структуру . F появляется еще ..........s s

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

ns+1 ns+1 (S)

а± (1)

■ I W- I

— u(s)-Ais)

входящего количественно равный

(б)

где а.* - коэффициент передачи (трансформации)

Гэ)

Ло потока примитивов к входу СМО м^ ' среднему числу появлений произвольного примитива во входящем

(д\ (с)

потоке СМО м. , - среднее время пребывания примитивов в

(б) (бт

СМО, М? - интенсивность входящего потока-примитивов СМО,

, - интенсивность обслуживания примитивов СМО М^,

которые равна:

для всех 1=1,п+1

Ь.(Е) 1

1=1, п

1=П +1

б

Здесь X - интенсивность потока пиимитивов- от источника М к

0 ' (б) 0

структуре интерпретируемой как разомкнутая СеМО; Ь^

(з)

1

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

[д)

примитива в СМО М^ , С - пропускная способность среды связи М_ .,,1 - средняя длина примитивов в структуре Р . Подставляя

'значения А^^ и формуле (1) и с учетом для всех

3 = 171? получим:

г (8)

t = Б

(Б)

а. и

1 Б

Ь1

ОС . Л„И 1 ОБ

1=1

*<Е> 1 пз+1 в

С0 -

г

(2)

Таким образом, из формулы (2)'видно, что необходимо выбрать

(э)

такие МП, суммарная стоимость которых вместе со стоимостью

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

(2). В связи с этим,

рассмотрим М=<сЗ^)| » вектор (массив) данных МП,причем

12 у т

Здесь - быстродействие г>-го МП, с1 -

стоимость за одну единицу быстродействия 1>-го МП. Допустим, что

все узлы структуры ? , кроме (п +1)-го узла, разбиты на (3 групп,

э (э) __—

в каждой из которых находятся г % узлов, где 7=1,Э и ¡3=1,5,

при условии, что

......

1?

г. ...г -г

Р

(з)

:.. .г г

(8) «я

6 =

пз при

т , при пд>м

/3)

Здесь г. - положительные целые числа, £-= номера разбиений п на

в Ч^ Р з

0 групп, причем, каждая г группа реализуется на базе-одного1':-' 1»-го МП, выбранного из массива М. Эти транзитивные бинарные отношения опишем следующими псевдобулевыми переменными:

X.1

(8)

1, если 1-й протокольный объект графа входит в

группу г разбиения О', в противном случае

1, если г группа протокольных объектов разбиения

графа в реализуется на базе и-го МП,- выб-р з .

ранного из массива М О, в противном случае

Тогда вышепоставленная задача сводится к следующей математической постановке:

ь = тз.п з

ш

/3

1:1 "Х- -¿"»л

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

.(s)

i=l

Г = 1

(s)

irc

=i ,

(5)

0

Vx(s) - 1

7=1 p

p=l,m, fJ=l,ä, (6)

Ii rml'ß' ß~1,s' (7)

i=l 1>=1 7 = 1 p P Cs) (s)

где D^ =D0"Dc K Rsß~ число разбиений ns на ß групп. Данная ' задача относится к классу задач квадратичного дискретного программирования с псевдобулевыми переменными. Определено, что сложность" вычисления N(k,ns,m) рассмотренной модели равна:

k 5 RSf3

m !n !

N(k,ns,m)= S

=1 ¡3=1 e„=l (m-ß) ¡П^5 !

7=1

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

заключается в следующем. Предположим,' что значения быстродействий МП являются непрерывными к неизвестными. В таком случае, с учетом dy=dQ, для всех v=i7m задача (3)-{8) принимает следующий ВИД:

ns (в)

. \ i s

t = > —¡—г-г—s- шщ

s / (s)(s)

4—^ х. -а:.

i = l 1 IOS

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

п

S

„«■>. d V .(=)

о

i=l

Решив данную задачу с помошью метода неопределенных множителей Лагранжа определим, что

,<в>.

„<з)_ „(з)

х i - " i Ло S +

Do

-d я М уа(з)

00 sLi

1=1

£ и

(S)

i=l

(S)

, i=l,ns (9)

После этого, исходя из' формулы (9) выбираются самые близкие

значения быстродейств и й

s>

к bv из массива М,

для чего

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

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

применяя * системный подход к структурному синтезу ММП ЦКП разрабатываются одяокритериальиые и многокритериальная

оптимизационные модели, относящиеся к классу задач дискретного программирования. Таким образом, в разделе 3.2 для минимизации среднего времени пребывания внутренних примитивов в кольцевой структуре КП физически представляется как совокупность Б локальных групп МП модулей с шинной структурой, которые взаимодействуют внутри групп через локальные шины и между группами через кольцо с интенсивностью А.^, 1^=17п и 5=170. С

учетом того, что множество МП модулей М=|м^|1=Т7п| разбивается на 0 локальных групп с последовательностью разбиений. _

2=1,гв, целевой функционал Т^ '- определяющий среднее время пребывания внутренних примитивов в кольцевой структуре, выражается следующим образом:

Ы

Т =пип-{тд.п 0 0 \ г

в п

ЧЕ

(г) (гП

1=1 :з=1

•8=1 1=1 j=l

X -X

13 ■ 1в js

(10)

где 0=ет1п'0таХ' 2=1и ПРИ ограничениях

з=1

(г)

для всех 1=1,п , е=ега1п-етах (и)

I

1=1

(2) Х1за2

для всех 5=1,0 , 0=0 . в , г=1,г.

' ' тт, тах 6

(12)

1 ^ (г) - -

КЬ Ь <Х ДЛЯ ВС6Х 5=1'е 'е=0ГО1п'етак '

8

<*> * н0 * н

°е * 0

г=1,2с

(13)

(14)

(15)

здесь X. =1,. если модуль М. входит в локальную группу Б при разбиении г, =0 в противном случае,- Н^ называется

функцией структурной отказоустойчивости при разбиении множества

М-{мА|1-1#п} на в локальных групп, где последовательность

разбиений пронумеруется индексом г,- Од2'- стоимостная функция, которая должна быть меньше, чем заданное значение О*; 'интенсивность обслуживания внутренних примитивов локальных шин, 5=170; количество .разбиений. В разделе 3.3 разработана

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

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

М)

=шах в

тах г

■ с в

- ■ ■ ч П

Х-сПМ)

3 = 1

при

С=1

ограничениях (11),

(16)

1=1

(12), (13), (15) и т

(2).

Т*-

0

Т . Здесь

заданное знач е ние среднего времени задержки внутренних

примитивов в кольцевой структуре,- с - количество функций Е^,

реализуемых на графе в=(Е,Г), €=17ё ; - коэффициенты важности

с ^

функций Р.., . где Т а_=1,- Ь^.=1, если по е. множество Е ?=1 5

Ье.=1,

е. 1

задействован в реализации функции Г,., Ье.=0, в противном случае.

В результате решения задачи, если определим такие /

которые обеспечивают ' максимальное значение н}.2^, тогда соответствующая данному разбиению распределенная структура ммп ЦКП будет самой отказоустойчивой. Анализ оптимизационной модели показывает, что повышение отказоустойчивости ММП ЦКП достигается без дополнительных материальных затрат за счет оптимального разбиения множества Е, что является одним из важных резервов обеспечения живучести системы при отказах блоков интерфейсов, обеспечивающих взаимодействие между локальными группами и кольцом. В работе.приводятся примеры, доказывающие адекватность оптимизационной модели к реальным ситуациям.

В разделе 3.4 предлагается оптимизационная модель для структурного синтеза ММП ЦКП по критерию стоимости:

=т!п-( 0 0

ии

г

б=1

< + ¿6 + «£ +

в э в

I -4)

+

,(2)

1 = 1

(17)

(•?) *

при ограничениях по формулам (11) (12), (13), (14) и т' 5Т . к '

Здесь й.- стоимость шинного хонтролера для МП модуля М^, где 1=17п,- <3 - стоимость шины локальной группы э МП модулей, 3=17в;

б 8 . __т;

<1з~ стоимость блока интерфейса БИ^, з=1, в; - стоимость

сетевого контролера для подключения БН к кольцу,- (3_ - стоимость

(г) э

кольца; йд - стоимость аппаратно-программной реализации

различных вариантов структур ММП ЦКП, которая зависит от порядка распределения МП модулей по локальным группам (г) и от количества локальных групп(0) в рассматриваемых структурах ЦКП.

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

многокритериальная оптимизационная модель ' для структурного

(г)

синтеза ММП ЦКП, целевая функция которой при применении

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

е е

Ш1П

г

(13)

где 2=1,и при ограничениях (11), (12) и (13).

Ш1 ГПЗ.Х и . »

Здесь v1, ■у'2 и ^ ~ коэффициенты важности частных критериев Т^ , (2) „ '„(2) 1

н

0

и Ъд , соответственно, где. £ лгг=1- Значения V выбираются

?=1

исходя из анализа уровня развития данной области, из требований к проектируемому ММП ЦКП и из существующих возможностей реализации этих требований. В предлагаемом аддитивном критерии для оценки ч , v2 и лт^ используется метод, ранжирования, В (18)

;<*>. н'21

- являются нормируемым значением критериев Од , соответственно, значения которых находятся в интервале (0,1). Для получения компромиссных решений частных критериев по выражению (18)' при ограничениях (11), (12) и (13) необходимо осуществить полный перебор всех разбиений. Однако, при па20 решить данную задачу практически невозможно из-за

-1F-

ограничения ресурсов компьютеров. В связи с этим, при решении

данной многокритериальной задачи на начальном этапе используется

эвристическая процедура Кернигака-Лина н- далее осуществляется •

полный перебор, в соответствии с которым генерируются

ízl

псевдобулевые перем е иные х^ и проверяются ограничения по формулам (11), (12) и (13). Разбиения, которые не удовлетворяют этим ограничениям не хранятся в памяти компьютера н отбрасываются. Разбиения, удовлетворяющие этим ограничениям, образуют- множество X допустимых локальных - решений, далее, на множестве X по известной процедуре определяется множество эффективных решений (Парето множество) для частных критериев, где Х^с X: После этого, на множестве Хр выбирается минимальное значение целевого, функционала W^ (18) . соответствующее данному минимальному значению разбиение, заданное ,матри-(zl

ней |Х>3 И будет определять оптимальную структуру ммп ЦКП в условиях многокритериальное™.

Четвертая глава посвящена вопросам реализации ММП <ЦКП с шинно-кольцевой структурой, синтезируемой в предыдущей главе.. Одной из важных задач при реализации.данной структуры является разработка методов для определения порядка подключения как МП модулей к шинам, . так и локальных групп к' кольцу ММП ЦКП. Локальные группы МП модулей через БИ подключаются к сетевым контроллерам кольца, функционирующим по стандарту IEEE 802.5. Существенной особенностью такой специализированной локальной сети является поддержание режима функционирования ММП ЦКП в реальном масштабе времени, что связано с' необходимостью использовать дорогостоящие средства связи' и вычислительной техники, что, в свою очередь, нередко оказывается экономически нецелесообразным. В связи с этим, в разделе 4.1 предлагается математическая модель, и алгортмы, не требующие дополнительные, материальные затраты и позволяющие минимизировать среднее время" доставки ■ внутренних примитивов по циклическому кольцу с маркерным доступом. Поскольку внутренние примитивы передаются в одном направлении по часовой стрелке и локальные группы L.

(о) ' 1

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

подключения их к кольцузначений Р^ - переходных вероятностей^ между ними и Р^- -вероятностей .активностей локальных групп L^, /

- 1В-

где 1^=1,п. Первоначальный порядок (вектор) подключения локальных групп к кольцу покажем как VI = < Г,, ;. ,.. . >,

К 1 1 П

который соответствует э-й перестановке. Все перестановки образуют множество Б, мощность которого равна п!. Исходя из

(э)

этого, выведено аналитическое, выражение ьи 'для перестановки (б)

локальных групп:

(s)

i"Pij [xij>-(Vtr+tc-tc) + (tl+2)-Cr+(n+1) (19)

i=lj=l

(s)

где xij расстояние между локальными группами L^ и L^,

выражающее количество сетевых контроллеров между ними по (s) '

перестановке V^ . tr, t - время задержки сетевых контроллеров

прк 'занятом и свободном маркерах,соответственно, при этом t >t ;

t , Ьс-время задержки сегментов кольца между соседними сетевыми

контроллерами при занятом и свободном маркерах, соответственно,

и t >t . Анализ выражения (19) показывает, что если определить ( s )

X. ■ по множеству S всех перестановок локальных групп, то ^о (s)

существует такие перестановки s<=s, при которых функция t^ '

обращается в экстремум, т.е.:

г <s)l

(с)

при ограничениях на элементы матрицы вытекающих из

принципа работы кольцевой локальной сети- с маркерным доступом:

-1

j=l

(s)

(n-1)(n+2)

i=l,n ,

Zi ь/

(s) (n-1) (11+2)

1=1

j=l,n- ,

(s)

(S)

3.-X.. + X.. =n+2 , 1] ai

i, j=l,n,i^j

4. Для четных n существуют симметричные пары.

' (s) (s) x.. =x.. , 13 31

2

2

количество которых равно п/2, причем значения (s) (s)_n

Данная модель относится к классу задач комбинаторной

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

is) (si

t^ и соответствующих им перестановок разработан

алгоритм, который реализован ; на персональном компьютере -IBM РС/АТ-386 . Расчеты,_проведенные по данному алгоритму показывают, что при относительно больших значениях п решить•эту задачу оказывается практически невозможным. По этой причине, разработан эвристический алгоритм, позволяющий в обход полного перебора

локализовать подмножество S экстремальных перестановок из (s)

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

(а)

процедура для минимизации среднего времени t^ доставки внутренних примитивов на шинах локальных групп Ьх, t=l,q, функционирующих в соответствии с протоколом IEEE 802.4. Здесь q-количество локальных групп в структуре ММП ЦКП, в каждой

из которых находятся п МП модулей, и, следовательно, Yn =п.

Г-1

(s )

Обозначим Y. . - расстояние между МП модулями М. и М. по

is) 3 1 D

.вектору V^ , выражающее количество шинных контроллеров между

ними и согласно принципу действия шинной сети с маркерным

(s> (s) '

доступом: • Л&лее, , - время задержки занятых и

свободных маркеров в шинных контроллерах; и t , t - время

С с

задержки занятого и свободного маркеров на одном сегменте шины,

I I

соответственно. отметим, что и tc>tc- В предлагаемом

методе шинные контроллеры на шине имеют жесткие позиции с

постоянными номерами 1=1,п идентификации, а МП модули в

"(s)

зависимости от номера s перестановки v\ меняют свои места.

(si

В этой связи, введем номера позиции R МП модуля М. по

(s) х

перестановке V' , который подключен к шинному контроллеру с

(s) -'

идентификационным номером 1. Другими словами, R^ =1, и

1=1,п для всех ses. С учетом вышеуказанного, получена

(s)

аналитическая формула функции t^ , которая приводится ниже:

-ZO-

nr пг

. is)

p. -p. . -i 13

<s) I • I I

x=l 3=1

— „ (31

для всех г=1,д. Как видно из формулы (20), если определить

по множеству 3 всех перестановок МП модулей, то существуют такие

перестановки , при которых функция имеет экстремумы,

т. е.

t=extr х

ses

}

T=l,q

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

,-Х , (1-1) (1+2) (п.,-1) (п -1+3)

1) - +-2-2-,

I— -"-j 9

j=l i=l

(1-1)(1+2) <nr-D (nr-l+3)

i=l,n , R.(s)=l, s€S ' X X '

_ (s>

j=i,n , R. =1, ses

X j

(s) (s)

3) Y. . =Y. . •, 4 di

i=l-nT , j=l,nr S6S

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

функции t V(S)

(s)

г. и соответствующих им экстремальные перестановки . На основе этих алгоритмов составлены программы на языке Фортран н реализованы на персональном компьютере IBM РС/АТ-386.

В разделе 4.3 рассматриваются некоторые вопросы аппаратной реализации ММП ЦКП с шинно-кольцёвой'структурой.'

В Приложении 1 приведены форматы пакетиэ Рекомендации Х.25> Приложение 2 содержит тексты программ для определения экстрему-

мов функций

(s)

t

М)

(s)

т и соответствующих им перестановок V^'

is)

локальных групп и МП модулей. В Приложении 3 представлены

документы об использовании результатов диссертационной работы.

ЗАКЛЮЧЕНИЕ

При решении поставленных в работе задач получены следующие

основные научные и практические результаты:

1. В результате анализа состояния работ в области создания ЦКП и современных требований к ним установлена необходимость структурной и функциональной иерархизации сетевого уровня ЭМВОС и обоснована технологическая эффективность такого разбиения.

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

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

4. Разработаны алгоритмы для определения порядка подключения МП модулей к маркерным шинам и локальных групп МП модулей к маркерному кольцу ММП ЦКП с адаптивной маршрутизацией.Применение этих алгоритмов позволяет увеличить пропускную способность маркерных шин и кольца ММП ЦКП без дополнительных затрат.

5. Предложены принципы аппаратно-программной реализации разработанного ммп ЦКП с шинно-кольцевой структурой.

6. При помощи предложенных моделей и алгоритмов модернизированы и расширены функциональные возможности ЦКП, эксплуатируемых в региональной компьютерной сети АйЕМГЕТ Совместного Азербайджанско-Российского предприятия "Азеринком".

7. Результаты работы были использованы при разработке и внедрении I и II очередей Республиканской .информационно-вычислительной сети с пакетной коммутацией, а также в создании азер-

байджанских узлов международной компьютерной сети INTERNET.

8. Предлагаемый ЫМП ЦКП с шинно-кольцевой структурой в качестве конкурентноспособного технического продукта на мировом рынке телекоммуникационных средств включен в план производства перспективных разработок Азербайджанского Научно-производственного объединения "Улдуз".

ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ

РАБОТАХ:

1. Алгулиев P.M., Лазарев В.Г., Аббасов A.M. и др. Архитектура программного обеспечения ЦКП с адаптивной маршрутизацией. Труды V Всесоюзного симпозиума по проблемам управления на сетях и узлах связи. М.^'Наука", 1986, с. 118-122.

2. Алгулиев P.M. сетевой подход к архитектуре ЦКП с адаптивной маршрутизацией, труды VI Советско - Итальянского семинара по сетям коммутации пакетов. М.: Наука, 1986, с.82 - 84.

3. Махмудов Ю.А., Алгулиев P.M. Об одном методе выбора структуры многомикропроцессорного ЦКП с адаптивной маршрутизацией. Тезисы - докладов всесоюзной школы "Проектирование автоматизированных систем контроля и управления сложными объектами" Харьков, ХИРЭ, 1986, с.60.

4. Алгулиев P.M. К вопросу проектирования многомикропроцессорного ЦКП с сетевой структурой. Материалы научной конференции аспирантов АН Азерб.ССР. Книга I. Баку: элм, 1987, с.37-39.

5. Лазарев В.Г., Махмудов Ю.А., Алгулиев P.M. Разработка архитектуры многопроцессорного центра коммутации пакетов с сетевой структурой. Тезисы докладов XII Всесоюзного семинара по вычислительным сетям. Часть 2. москва-одесса, 1987, с.190-195.

6. Аббасов A.M., Алгулиев P.M., Лазарев В.Г. и др. Архитектурная модель сетевого уровня центра коммутации пакетов с адаптивной маршрутизацией, препринт. М.: ИППИ АН СССР, 1987, 48с.

7. Махмудов Ю.А., Алгулиев P.M. Оценка методов разбиения сетевого уровня центра коммутации пакетов с адаптивной маршрутизацией. Тезисы докладов 3-й Всесоюзной школы "Проектирование автоматизированных систем контроля и управления сложными объектами". Харьков ХИРЭ, 1988, с.40.

8. Лазарев В.Г., Махмудов Ю.А., Алгулиев P.M. Метод синтеза многомикропроцессорного центра коммутации пакетов с шинно-

кольцевой структурой.Тезисы докладов V Всесоюзной школы "Распределенные автоматизированные системы массового обслуживания" Москва-Рига, ИПУ АН СССР, 1988, 2с.

9. Алгулиев P.M. Анализ среднего времени доставки сообщений в локально-управляющих микропроцессорных сетях с маркерным доступом // Многопроцессорные вычислительные структуры. Таганрог, ТРТИ, 1988, вып. 10(19), с.59-62.

10.Алгулиев P.M. Об одной модели оценки распределенных структур многомикропроцессорного центра коммутации пакетов по производительности // Многопроцессорные вычислительные структуры. Таганрог, ТРТИ, 1989, вып. 11(XX), с. 29-33.

11.Abbasov A.M., Alguliev R.M. и др. Azerbaijan computer networks: present state and perspectives. Uluslararasi Bilgisayar Uygulamalari Sempozyumu. Tebligler. 9-10 Haziran 1993, Konya, Selcuk Universitesi, pp. 21-25.

12.Abbasov A.M., ^ Alguliev R.M., Gasumov V.A., Aliev E.R. System management for large computer network: experience on design and creation of the Azerbaijan Republic information computer network. Procedings of 1NET'93. San-Francisco, California, USA, 17-20 August 1993, ISp.

ХУЛАС8

диссертасиза иши адаптив маршрутлашдырма функсизасына'малик чохмикропросессорлу пакетлэри коммутас^а мэркэзинин (ЧМП ПКМ) лазиЬэлэндирилмэси методларынын ишлэнмэси вд тддгиги мэсэлэлэринэ Ьэср олунмушдур. Бу заман ачыг системлэрин гаршылыглы фэали;пэтини тэнзимлэj9H еталон моделинин вэ Х.25 тэвсиjзэсинин тэлэблэринэ эсасэн гурулмуш ПКМ-нин архитектуру вэ онун jepHHS зетирдиди физики, канал ва шабакэ csBKjjaлэpинин протоколлары таягиг олунмуш, адаптив маршрутлашдырма методларынын вэ ceTeMBTpnja хидмзти протоколларынын реаллашдырылма . MyMKyHflyjy тэЬлил олунмушдур. Сонра кениш миг^асда KOMnjyTep шэбэкэлэриндэ истисмар олунан ПКМ-лэринин иш вэ гурулма принсиплэри Иэртэрэфли езрэнилмиш, онларын устунлузу вэ негсанлары, Ьабелэ тeлeкoммyникacиja техникасынын муасир вэзн^этинэ мувафиг инхишаф тенденсизасы MysjjoH олунмушдур. Бу арашдырмалар эсасында ПКМ-нин шэбэкэ сэвизэси протоколунун fleK0Mn03Hcnja методлары тэклиф олунмуш вэ онларын муга;зисэли тэЬлили учун ризази модел вэ евристик проседур ' ишлэнмишдир. MygjjaH олунмушдур ки, шэбэкэ C9BHjjacn протоколунун функсизалар вэ онун узэринэ душэн зукэ керэ дeкoмпoзиcиja олунмасы ЧМП ПКМ-нин ла^Ьэлэндирилмэсинэ rojyflaH тэлэблэрэ даЬа чох чаваб. верир. Бундан. сонра, Иэмин декомпозисиja методу эсасында ЧМП ПКМ-нин синтези мэсэлэлэринэ бахылмышдыр. Эввалчэ онун апарат реаллашдырылмасынын архитектур эсасы вэ ' микропросессор (МП) модулларынын гаршылыглы 'элагэсини тэ'мин едэн физики му!гитин структуру то'зин олунмуш, даЬа сонра ЧМП ПКМ-нин структурунун сечИлмэси учун чэлдишлэмэ, е'тибарлылыг вэ дэjэp кастэричилэрини оптималлашдырмага имкан верэн бирме'зарлы вэ чохме'зарлы pnja3H моделлэр вэ алгоритмлэр ишлэнмишдир. Бу моделлэрин Ьэлли нэтичэсин^э шин-даирэви структура малик ЧМП ПКМ синтез олунмушдур. Бундан сонра 1гэмин структурда МП модулларынын локал групларынын маркер даирэсинэ, Ьэмчинин бу локал груплардакы маркер .шинлэринэ МП модулларынын гошулмасы газдасыны Ta'jnH eTMsja имкан верэн pnja3H моделлзр вэ алгоритмлэр ишлэнмишдир. Нэтичэдэ, тэклиф олунан шин-даирэви структурлу ЧМП ПКМ-нин апарат- програм реаллашдырылмасы учун бир сыра тэклифлэр ишлэниб Ьазырланмышдыр.

Диссертасиэа ишиник елми-практики нэтичэлэри Республика информасиja-Ьесаблана шэбэкасиннн лаэиЬэлэндирилмэсиндэ,

INTERNET бе;)нэлхалг компэутер шэбакасикин a39p6aj4aH говшагларынын japaдылмacындa, AZERNET рекионал комп^утер шабэкэсинин ПКМ- ларинин тэкмиллашдирилмэсиндэ ва функсионал имканларынын кенишлэндирилмасинда истифада олунмуш, Ьэмчинин тэклиф олунан шин-даирави структура малик .ЧМП. ПКМ тeлeкoммyникacиja васитэлэринин flyHja базарында рагабатэдезумлу гургу кими "Улдуз" A3sp6aj4aH Елм-ИстеЬсалат Биpлиjи тэрэфикдэн jaxuH кэлэчэкдэ истеЬсал олунмасы учун перспектив плана дахил едилмишдир. ■

ABSTRACT

The dissertation work has been devoted to development and research of the methods for design of Multi-Microprocessor Packet Switching Centre (MMP PSC) with adaptive routing. In the process of research the architecture of PSC with physical, channel, and network' layers protocols has been studied on the base of reference model OSI/ISO and X.25 recommendations and feasibility analysis on adaptive routing methods with network measurement service protocols implementation has been conducted. Then the comprehensive study on building and working .principles •of PSC widely used in computer networks has been performed and the trend of their further development with account of telecommunication technology current state has been identified.Ori the basis of these studies the methods of decomposition of the network layer protocol of PSC have been proposed, mathematical models and heuristic procedures for performing the comparative analysis have been developed. It's been found that implementation of decomposition of the network layer protocol on its functions and loading is more productive in meeting the requirements of PSC design. Then onthe basis of that decomposition method the problems of MMP PSC synthesis have been addressed. First,the structure of physical environment that provides interlink between MP modules and determines the architectural base of hardware realization of the system has been defined, and then uni- and multi- criterial mathematical models and algorithms enabling the

refinement . of performance, reliability and cost parameters of MMP PSC structure identification have been developed. In the result of these models solution, the MMP PSC with token-lpus-token-ring structure has been synthesized. Then the mathematical models and algorithms that give an opportunity to determine the order of connection of. MP modules of the local clusters to the token-ring and connection of MP to token-buses of local clusters have been developed. As a result of it a number of recomendations on/hard- and software realization of the proposed MMP PSC with token-bus-token-ring structure have been produced.

The scientific and practical results of dissertation work have been applied in design of Republican Computer Network, in development of Azerbaijan Nodes of International computer network INTERNET, in refinement and enhancement of PSC functions in the regional computer network AZERNET, and besides, the manufacturing of the competitive on a world market scale telecommunication device on the base of proposed PSC with token-ring- token-bus structure has been included in prospective production development plan of Azerbaijan Scientific-Production Union "Ulduz".

Зак.1?<. Тираж 100. Печ.лист 1,0. тип. Отдела АСУ AHA, 370141,Баку,ул.Ф.Агаева, Э.

Бесплатно

Азчрбазчан Елмлэр Академи^асы Кибернетика институту

Элjaзмacы ьугугунда

влтулиаев расим мэьэммэд оглу

адаптив маршрутлашдырма функсиаасына малик чохмикропросессорлу пакетлэри коммутасияа мэрк93инин лал1ьэлэндирмэ методларынын ишлэнмэси

Техника елмлэри намизэди алимлик дэрэчаси алмаг учун тэгдим едилмиш диссертас^анын

АВТОРЕФЕРАТЫ

Бакы - 1995