автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка и исследование алгоритмов адаптивной маршрутизации в сетях ЭВМ (на примере сети ЭВМ "Сирена-2")

Й-я ■ ^

Российская Академия Наук Инспдут проблем управления

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

П Р ЫТ О В АЛЕКСАНДР АЛЕКСЕЕВИЧ

Разработка и исследование алгоритмов адаптивной маршрутизации в сетях ЭВМ (на примере сети ЭВМ "Сирена-2")

Специальность: og.13.13 - Вычислительные мамины, комплексы.

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

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

Москва 1992

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

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

\

Профессор, Вишневский В.М.

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

зав. сектором Манн А. А. - кандидат технических наук, старший научшй сотрудник Пащенков Н.Я.

Ведущее предприятие - Главный вычислительный центр гражданской авиации

Зашита состоится "_"_199_ г. в_ час. на

заседании Специализированного совета N 2 Института пооСлом управления РАН Д002.68.01 ПО адресу: 117806, Москва, Профсоюзная ул., 65. Телефон Совета 334-93-29.

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

Автореферат разослан "___"_ 19S2 г.

Ученый секретарь Специализированного couera к.о-шилат тохничаских наук

Е.Б. Оркевич

' 11 ¡,: 1; 5КБЛИС7 к К; , ОБМАЯ ХАРШЕРИСШбе РАБОТЫ

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

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

Целью диссертационной работы является разработка новых эФФек-

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

В соответствии с поставленной иельь основными задачами диссертации являются:

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

-разработка метода оценки целесообразности введения приоритетной маршрутизации в сетях с многими классами потоков,

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

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

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

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

СВЯЗИ!

- алгоритм расчета и рассьшки маршрутной информации, исключающий циклы алиной 2.

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

Практическая ценность работы. Разработамгый в диссертации

алгоритм маршрутизации предназначен для использования в дейта-

граммных сетях коммутации пакетов, реализованных на низкоскорос-/ . ■ гной, ненадежной "телекоммуникационной технике. Этот алгоритм

позволяет улучшить эффективность обслуживания СПЯ в условиях

перегрузок и отказов каналов связи.

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

Реализация результатов работы. Разработанные алгоритмы знедрены во всех тридцати пяти Управлениях гражданской авиации и жлючены в базовый комплект программного обеспечения Общесоюзной 5истемы управления продажей билетов и бронированием мест на внутренних авиалиниях "Сирвна-2", разработанной в соответствии с программой работ по решению научно-технических проблем 0.80.09, задание i5.02.0X.A4, утвержденной постановлением ГКНТ и Госплана СССР от (.12.81. и 491/244/приложение N64/ и по совместному приказу Минпри-iopa СССР и МГА СССР N96/182 от 8.07.82.

Апробация работы. Основные результаты работы докладывались ia 4-ой, 5-ой Всесоюзных школах-семинарах по распределенным аато-1агизированным системам массового обслужиаания( Кутаиси, 1987; 'ига, 1988), з, 4-ом Всесоюзных совещаниях по распределенным авто-

матизированным системам массового обслуживания (Москва, 1950; Душанбе, 1991).

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

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

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

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

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

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

На основании проведенного анализа существующих стратегий маршрутизации и с учетом особенностей СПД "Сирена-2" Формулируется основная задача диссертационной работы, которая заключается в раз-

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

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

- адаптивности: алгоритм должен реагировать на неисправности и перегрузки каналов и узлов сети;

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

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

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

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

В диссертации показана необходимость решения нескольких частных задач:

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

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

- разработки техники пакетной коммутации применительно к сети Сирена-2" (параграф 4.4);

- разработка системы приоритетов применительно к сети "Сирона-й"

(параграф 4.З.):

- внедрение разработанных алгоритмов в СПД "Сирена-2"< глава 4);

- разработки системы измерений и проведение прямых измерений на сети с целью оценки эффективности разработанных протоколов ( параграфы 2.4 и 3.4).

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

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

Этот метод инвариантен к способу определения задержек.

Предлагается использовать оценку задержки на передачу по участку "узел+канал" как сумму задержки на ожидание в очереди к выходному каналу, задержки на передачу по каналу, задержки на ожидание во входной очереди пакетов на обработку в узле и задержки на обработку в узле так, как показано в выражении (I):

Т-»и'Тке + 7м+Рк'Ткр + ТР; к,1И)

где, Пщ -средняя очередь пакетов к каналу (к,£); Т^-среднее время передачи пакета.по каналу (к, в), оно определяется обратно пропорционально пропускной способности канала связи в Фиксированных весовых коэффициентах; р^ -средняя очередь пакетов на обработку в узле к; -среднее время на обработку пакета в узле и определяется в Фиксированных весовых коэффициентах; ы-число узлов в сети.

Использование метрики (1) позволяет учитьвать перегрузки и от-

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

каналу связи в меньшей степени зависит от длины пакета, если ис-

<

пользовать Фиксированную длину пакета, т.е. использовать технику коммутации пакетов.

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

Целью маршрутизации является выбор маршрута в метрике (1) по критерию минимума сродней задержи среди индивидуальных задержек между узлом-источником и узлом-адресатом (пользовательская оптимизация). Такой подход отличается от оптимизации средней задержки по всей сети. При общесистемной оптимизации, пользователь при учете влияния своего траФика на траФии остальных пользователей, должен вьзбирать пути минимальной инкроментной задержки. Но как показано в ряде работ, например у М-См-Ч для двухсвязной сети среднего размера с однородными пропускными способностями! различие между структурами траФика при пользовательской и системной оптимизации незначительно.

Алгоритм маршрутизации можно описать с помощью пяти элемента!

1. Таблиц маршрутизации, хранящихся в каждом узле и время от времени корректируемых по информации, получаемой из соседних узлов, размерностью К*М, гдэ н-число узлов в сети; М- число каналов связи в узле, а элемент таблицы Тц(£}-всть оценка задержки из данного узла I цо узла j через, направление 6 .(и=1,..„к; С

2. Алгоритма выбора направления с наименьшей задержкой. Из столбца

маршрутной таблицы, который соответствует узлу-адресату выбирается лучшее направление с учетом средних очередей на эти направления по Формуле (1). При этом не учитываются следующие направления-- не работоспособные в данный момент времени;

- имеющие очередь пакетов больше допустимой;

- имеющие оценку задержки больше допустимой.

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

(- '»¿»[»и т1£ + т^; е*е5}

(г)

1 и«',..-!*'

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

Вектор лучших задараон сравнивается с вектором лучших задержек разосланных в последний раз. Рсшониа о рассылке принимается в сл^аус йчх случаях:

- хотя бы один канал поменял свой статус (восстановился/ отказал канал связи);

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

Частота рассылки управляется порогом, который после рассылки ступенчато изменяется от НАХ до нуля-

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

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

Накладные расходы алгоритма на процессор менэо IX, на канал в среднем -2х. Для сетей подобных сети "Сирена -г" в большинстве случаев алгоритм быстро сходится к оптимальным марырутам, т.к. все каналы равноскоростнш и использование метрики (1) приводит к выравниванию нагрузок. Исключение составляют отказы узлов; в этом случае алгоритм должен сходиться к пороговому значению задержки доступа в сеть, значение которой может быть высокой. Во время сходимости возможно образование циклов, что является платой за адаптивность. Для ликвидации циклов длиной 2 используется предложенный в данной работе способ расчета векторов задержки. Для ликвидации циклов длиной болею 2 применяется ограничение на число переприемов, а для предотвращения зацикливания - управление доступом в сеть по числу зацикленных пакетов.

Различный модификации метода "гельеФов" использутся в ряде зару-<3вшах сетей, например, decnet, datapac, burrouohs, tidas и т.д. Все оии не учитывают перегрузки в сети. С одной сторону, это обьясняется том, что зарубежные сети работают при низких загрузках сети и используют э алгоритмах маршрутизации критерий минимума стоимости передачи не зависящий от нагрузки, с другой стороны, желанием иметь устойчивый алгоритм маршрутизации. Перегрузки учитывались в первой версии сети анра, но начиная со второй версии в этой сети используется другой алгоритм маршрутизации (модификация алгоритма Дийкстра). Основным недостатком, обнаруженным в этой сети, была неспособность эффективного расцепления траФика по нескольким путям при длительной нагрузке. Алгоритм сети "Сирена-2" за счет использования метрики (1) является многопутовым и гибко распределяет нагрузку между всеми направлениями, а устойчивость достигается за счет усреднения за интервал времени, выбираемого исходя из динамики входных потоков.

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

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

В современных крупномасштабных С1Д одновременно передается аналоговый трафик, пакеты оайлов, электронная почта, слухе1-"'ije со-

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

Для того, чтобы Формализовать задачу, введем следующие опредо-деления и обозначения.

Известны: 1. Топологическая структура СПД, состоящая из к-уз-лов М-каналов связи, заданная в виде матрицы смежности. 2. Матрицы информационных потоков р-классов, образующих пуассоновские потоки между всеми парами узлов || 3- Длины пакетов р-классов распределены по показательному закону со средними значениями • 4. Пропускные способности каналов .

Пусть (пакет/сек.(-величина потока в канале (к, £),

, (Р) т (Р>

вызванная потоком , а (пакет/сек. Ьвеличина потока в

канале (к,£), вызванная передачей пакетов класса р для всех пар узлов.

Рассматривая сеть, как совокупность независимых систем массового обслуживания М/с/1, используя Формулы Поллячека-Хинчина для сродной задержки для потоков р-классов с относительным приоритетом, мож-но сформулировать задачу в виде задачи оптимизации производи голь-нссти сети при некоторых ограничениях:

Найти Н^)! » такие что

производительность О ~> МАХ, при ограничениях: г км ей Л-е- ^ '"ах

(Р) ,

£ Н а,а [ Н(Р) ; к»£

.СМ , .

; к-л

0 Л* « ^ ; -М-*, ...,л/

ГО

, я Г У I '<« р

■С р Дср) р

Условие (3) - ограниченна на средние задержку б сети при бесприоритетным обслуживании, условие (4) -ограничение на среднюю задержку в сети с относительна приоритетом, при котором р-класо пакетов имаот относительный приритвт парад р+1 классом- условна (О-опредоляет, что величина потока в канале не превосходит его пропускную способность, условие (б)-обеспечивает сохранение потоков в сети.

I

Для решения подобных задач разработано большое число методов.

Наиболее разработаны методы для решения задачи без приоритетов. Наи-

«

более известными среди них является метод экстремальных потоков, гра-

<Р>

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

Для решения поставленной задачи предлагается следующий алгоритм, являющийся модификацией алгоритма отклонения потока. ИАГ 1. Вычисление начального допустимого потока (исходя из топологии и матрицы вхошгых потоков).

Шаг 2. Оптимизация производительности 0 по формуле (3) при Фиксированных маршрутах, выбранных на ШАГЕ 1.

ШАГ з. Оптимизация маршрутов методом отклонения потоков для всех р-классов потоков.

ИАГ 4. Оптимизация производительности 9 по Формуле (3) при выбранных маршрутах на ШАГЕ з.

ИАГ G. Проверка на улучшение максимальной производительности по сравнению с предыдущей итерацией. Если можно улучшить О, то возврат к ШАГУ 3, иначе полученное значение О считать максимальным значением производительности для босприоритетного обслуживания ч переход к ШАГУ 6.

ИАГ 6. Оптимизация производительности в по Формуле (4) при неизменных маршрутах. Полученное значение 0 - ость максимальная про-ипаодитольность и ля приоритетно о сбелукизт^я-

Ш,»Г 7. STOP.

Трудоемкое!" алгссима опрслоляеТся трудоемкостью шагов 1 и з. тих шагах пгюизводчтея расчет кратчайших маршрутов, напри-кагопом Флойпа или модифицированным алгоритмом Дийкстра. Их трудоемкость 0(.v.'.

На шаге 3 о отличим от стандартного алгоритма отклонения по-гста, данный ош оритм отклоняет по кратчайшии ¿туч ям но весь ,":это;*;

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

На шагах 2,4,5 решается одномерная задачи оптимизации выпуклой функции. I

Сравнение прозврдительностей, полученных на ШАГЕ С и 6 определяет целесообразность ввода приоритетного обслуживания.

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

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

Топология сети "Сирена-2" в настоящее время включает 35 узлов .и 65 каналов связи- Сеть двухсвязная, с ограничением на максимально« число переприемов, равное 2. Средняя связность на узел 3.0, среднее число переприемов -0.7. Все узлы реализованы на ЭВМ СМ-2М с произво-

лительностьо ю-1'2 пакетов/сек. Большинство каналов связи использует аппаратуру АПДМА-ТФ, реализующей функции модема и УЗО, с пропускной способностью 1200 бит/сек.

Структура программного обеспечения в узлах реализована с учетом рекомендаций iso. 11а канальном уровне Bsc подобный протокол. На сетевом уровне- дейтаграммная коммутация пакетов, адаптивная маршрутизация, приоритетная передача с 4 классами приоритетов.

Реализация алгоритма маршрутизации имеет следующие параметры: Интервал расчета маршрутной информации равен Ю сек. Пороговое значение задержки, управляющее частотой рассылки изменяется ступенчато раз в ю сек. от МАХ до о так, чтобы раз в 1 мин- рассылка была произведена обязательно. "Веса" каналов связи выбираются следующим образом:

1 - если направление образовано одним дуплексным каналом со скоростью 2400 бит/сек. или двумя дуплексными каналоми со скоростью 1200 Сит/сек. каждьй;

2 - если направление образовано одним дуплексным каналом со скоростью 1200 бит/сек. или двумя полудуплексными каналами со скоростью 1200 бит/сек. каждый:

3 - если направление образовано одним полудуплексным каналом со скоростью 1200 бит/сек.

"Вес" процессора выбирается равным 1/10.

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

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

На сеансовом уровне реализованы следующие сеансы: терминал-терминал, терминал-прикладная программа, прикладная программа-прикладная программа. На представительском у ровно определен синтаксис работы с пользователями -7-битовый ascii, дополненный русскими буквами. Прикладной уровень вотолняет Функции по продаже авиабилетов и по передаче Файлов. Кроме того, СПД "Сирена-2" имеет прикладной уровень, реализующий Функции Центра управления сетью, который выполняет измерительные Функции, осуществляет сбор статистики, позволяющей провести анализ Функционирования сети.

Разработанные в диссертации алгоритмы реализованы в виде программных модулой на языке АССЕМБЛЕР. Использование языка низкого уровня объясняется требованием эффективности программ и ограниченным объемом оперативной памяти ЭВМ СМ-2М.

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

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

4

2. Разработана техника коммутации пакетов, обеспечивающая улуч-юние временных характеристик сети и эффективность процедур маршру-■изаиии.

3. Разработан и исследован метод обоснования целесообразности «эиоритетной маршрутизации в условиях многих классов пакетов.

4. Разработана система приоритетной передачи в СПЛ. повышающей ФФективность использования ресурсов сети.

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

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

7. Разработанные алгоритмы и программы внедрены и входят в азооьй комплект программного обеспечения СПЛ "Сирена-2".

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

1. Прыгов А.А., Савинеокий А.Б. Управление процессами и ресур-аки в транспортной службе сети ЭВМ "Сиреиа"//Сеть ЭВМ "Сирена", опросы аппаратно-программного обвспаченияД1н-т проблей управлэ-^я.-М.,198б.-с.24-28.

2. Вишневский В.Н.,Кацмам Г.Л.Лрытов А.А.Измерения и обработ-4 статистистических данных в сети ЭВМ "сирена".//4-я Всесоюзная сола-семинар "Распределенные автоматизированные системы массового

обслуживания'/Кутаиси, i9S7.-c.ie9-l6C.

3. Прытов А-А. Алгоритмы маршрутизации сети "Сирена-2".//0-я Всесоюзная школа-семинар по распределенным автоматизированным системам массового обслуживания./Рига, i988.-c.222.

4. Прытов A.A. Адаптивная маршрутизация сети "Сирена-2".//3-е Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания./Москва, 1990.-с.124-125.

5. Вишневский В.М.Лрытов A.A.,Федотов ЕВ. Определение произ-

i

водитедьности сети передачи данных с различными рлассами пакетов. //3-е Всесоюзное совещание по распределенным автоматизирование системам массового обслуживания./Москва, 19Эо.-с.109-ш.

е. Прытов A.A. Распределенные компоненты 11УС сети "Сирена-2". //4-е Всесоюзное совещание по распределенным вычислительным системам массового обслуживания./Душанбе. l99l.-c.2S.

Прытов А.А.,Винарский М.Г. Элементы централйэованного управления в сети передачи данных "Сирена-2н.//4-е сесоюзное совещание по распределенным вычислительным системам массового обслуживания./Душанбе, 1S91-c.26.

Личный вклад диссертанта. Все научные результаты, составляют основже содержание работы, получены диссертантом самостоятельно. В работах, выполненных в соавторстве. A.A. Прытов внес следующий вклад: в работе [1] предложено использование дейтаграм-иного способа коммутации пакетов в сети "Сирена-2". В работе [21 все измерения были выполнены измерительной системой, разработанной диссертантом. В работе [&] был предложен алгоритм расчета производительности сети с многими классами пакетов. В работе IT] был предложен алгоритм обнаружения изолированных узлов в сети "Сирена".