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

! • V 1"> о

российская академия наук /, 2001

институт проблем передачи информации

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

БЕРЕЗКА МИХАИЛ П А В Л О 3 И Ч

МЕТОДЫ И МОДЕЛИ АДАПТИВНОЙ МАРШРУТИЗАЦИИ В СЕТЯХ ЭВМ (НА ПРИМЕРЕ СЕТИ ЭВМ "ЭКСПРЕСС-2")

Специальность: 05.'.3,13 - Телекоммуникационные системы и компьютерные

сети

Автореферат

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

Москва 2001

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

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

В.М. Вишневский

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

В.Г. Лазарев

кандидат технических наук Г.Л. Кацман

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

Защита состоится /х« \<Я 2001 г в час на

/¿5--—

заседании специализированного совета Д.002.077.01 в Институте

проблем передачи информации РАН по адресу 101447 Москва, ГСП-

4, Большой Каретный пер, д.19 2-3$ - ^ V'

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

проблем передачи информации РАН.

Автореферат разослан « /У« /г^-З 2001 г.

Ученый секретарь

специализированного совета Д.002.077.01 доктор технических наук,

профессор Степанов С.Н.

Общая характеристика работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

- сравнительный анализ и выбор алгоритмов маршрутизации применительно к сети ЭВМ «Экспресс-2».

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

Предложенный в работе алгоритм маршрутизации позволяет улучшить эффективность функционирования СПД в условиях перегрузок и отказов каналов связи. Алгоритм позволяет также повысить эффективность использования имеющихся каналов связи путем расщепления трафика по нескольким направлениям. Реализация результатов работы. Методы и алгоритмы, предложенные в диссертации, внедрены во всех 29-ти региональных центрах системы «Экспресс-2». Работы по модернизации алгоритмов маршрутизации сообщении проводились в 1999-2000 годах в рамках договоров ВНИИАС МПС на сопровождение эксплуатации системы «Экспресс-2» с МПС РФ, железнодорожными администрациями Украины, Белоруссии, Казахстана, Молдовы, Латвии и Узбекистана.

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

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

Апробация работы. Результаты диссертации докладывались на:

• V совещании по распределенным системам и сетям, СГ)8-92. Светлогорск,1992. «Организация сети передачи данных в АСУ "Экспресс-2"»

• Международной конференции по проблемам управления. Москва, ИПУ, 1999. «Адаптивная маршрутизация сообщений в сети передачи данных».

• На научных семинарах ИППИ РАН и ВНИИАС МПС. Публикации. Основные результаты диссертации опубликованы в 10 печатных работах.

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

приложения содержат ¿.О страниц. Список литературы имеет У.уГнаименоваиий.

Содержание работы.

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

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

В первой главе имеется постановка задачи, описаны стратегии маршрутизации в сетях ЭВМ, развитие СПД «Экспресс-2» и методы маршрутизации в ней.

Задача, поставленная в исследовании, была вызвана потребностями СПД «Экспресс-2». За перод развития системы «Экспресс-2» значительно увеличилось количество узлов и ребер сети, связность сети соответственно уменьшилась. В то же время были внедрены новые технологии организации продажи билетов и V управления пассажирскими перевозками, резко повысившие требования к надежности и пропускной способности сети.

В настоящее время сеть объединяет 31 узел системы "Экспресс", расположенные в России (17), Украине (7), Казахстане (3), Белоруссии, Латвии, Молдове и Узбекистане.

Основной режим работы сети - диалоговый, со средней длиной сообщения 167 байт. Требования по надежности и времени доставки: шлейфовая задержка не более 30 секунд для 95% сообщений. Кроме того, для реализации функций управления пассажирскими перевозками, информация обо всех перевозках пассажиров Российских ж.д. передается в Москву, что образует поток так называемого «архивного» трафика, передаваемого с. меньшим приоритетом, чем диалоговый, и имеющего среднюю длину сообщения 1524 байта.

Система коммутации сообщений "NETWORK" изначально строилась с использованием распределенной адаптивной динамической маршрутизации.

Ключевыми принципами этой маршрутизации являлось:

- наличие информации в каждом узле сети о состоянии всей

сети;

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

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

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

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

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

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

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

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

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

имеющихся потоков для обеспечения более эффективного распределения трафика по имеющимся ребрам администратором сети;

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

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

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

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

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

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

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

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

- справедливости: алгоритм должен обеспечивать равные

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

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

Исследование выполнялось для трех вариантов маршрутизации:

- однопутевая маршрутизация с фиксированными ценами ребер;

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

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

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

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

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

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

Задача определения оптимальных маршрутов и распределения потоков в сети передачи данных сформулирована в следующем виде.

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

1) все линии связи абсолютно надежны;

2) линии связи могут состоять из нескольких полудуплексных каналов с эффективной пропускной способностью, равной [байт/сек]; (к, !) - линия связи между узлами к и /; количество каналов в линии (к, /) равно уц; если линия связи между узлами

к я / отсутствует, то ук1 = 0;

3) узлы коммутации имеют бесконечную память;

4) И1 " вРемя обработки сообщения в узле г [сек];

5) сообщения, циркулирующие по сети передачи данных, разделены на Р классов, причем:

- сообщения класса р имеют относительный приоритет (приоритет без прерывания обслуживания) по отношению к сообщениям классар+1;

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

6) длины сообщений независимы и распределены по показательному закону со средним значением [байт]; р = 1,2, ...Р.

7) Трафик сообщений класса р, поступающий в сеть, образует пуассоновский поток со средним значением -у^Р) [сообщений/сек] для сообщений, возникающих в узле / и предназначенных узлу у; пусть: Р N N

Т = X £ Т. У у ^ - полный внешний трафик.

р-! /= 1 у'= 1

Обозначим через х^'^ - долю потока из узла г в узел проходящую по линии (к, /). В соответствия с предположением 5), переменные не зависят от приоритетного класса. Тогда:

N N

Ч1(Р)= 2 I ц/Р>-> ¿=0=1

где: Хк1 (Р) - величина потока в линии (к, I) [сообщений/сек], обусловленная входным потоком у,-.- (Р).

Хк1

Для переменных

(У)

Лк1

должно выполняться условие

сохранения потока в сети, которое записывается следующим образом:

1'.

А= 1

И

N *=1

(Ц)

1к

-1, I — г

0, /

1, ' =7

Пусть далее:

,, Ч1(р) Гк1(р) =-

х(Р)

(р) =

/к!® +Лк(Р)

- загрузка линии связи (/с, /) сообщениями

класса р\ величины и /ц/Р) складываются, так как каналы

используют полудуплексный режим;

ры = I Рм(р); р=1

М- ЪРк{г)

N

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

, N N N N Р рк1(Р) Р у,(Р) рк(Р)

Сделанные предположения и обозначения позволяют сформулировать задачу поиска таких значений переменных х^*'^ ,

которые обеспечат оптимальное (наименьшее) значение величине Т. Известны:

1) топологическая структура сети передачи данных;

2) матрицы входных потоков для каждого приоритетного класса -

11 уц (Р> \\;

3) пропускные способности линий связи -11 11 и количество каналов связи в каждой линии -11 уц 11;

4) средние длины сообщений для каждого приоритетного класса - \lyfp) [байт];.

5) сроднее время обработки сообщений в узлах коммутации

-щ.

Требуется найти:

I) Переменные х^'^ и, следовательно, потоки в линиях связи д/^ такие, что:

Т -> тш (2)

при выполнении ограничений:

, N N ....

Л/Р) ' -фу I I цй» У; к, I = 1, 2, ...М; р = 1, 2, ...Р (3)

Р

=1.2,...Н (4)

р= 1

--1, / = /

N .... N .. У г ^ - V г М =

к=1 А-1 ^

0,1*1.} (5)

1. I"}

О < < 1;!. )Л, 1 = 1, 2, .. (6)

Задача (2 - 6) называется задачей выбора оптимальных потоков и определения оптимальных маршрутов в сети передачи данных по критерию средней задержки.

Ограничение (6) предполагает, что для передачи сообщении из узла г в узел _/' может быть использовано более одного маршрута, то есть задача (2 - 6) описывает альтернативную процедуру выбора маршрутов.

Если условие (6) заменить на условие:

х^ е { 0, 1 \\i.j, к, 1,2, ...И (ба)

то задача (2 - 5) совместно с условием (ба) будет определять фиксированную (однонаправленную) маршрутизацию.

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

Введем переменную: N

Лк1

, если I х,М > 0;

г г 41 <

/=1

(7)

N

"к!

0, если £ х,}1^ = 0;

V м

^ к, I - 1,2, ...и.

Иными словами, переменная = 1, если линия связи (к, I)

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

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

£ v^P <n; k,j = 1,2, ...N (8)

/=1

Таким образом, задача (2 - 8) описывает n-путевую маршрутизацию.

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

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

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

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

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

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

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

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

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

Шаг 1. Определить веса линий связи и инициализировать потоки в линиях связи Уу (р) :

Г

гтГ 1

оо;

к. /= 1,2, ...Ы: уц = 0

к, I = 1,2, = 1,2, ...Р

Шаг 2. Положить:

П(у := 0 (Пгу - множество оптимальных маршрутов между парой узлов (/,у)); = 1,2, ...Ь?

^/^■•=0; к, /,/ = 1,2, ...Ы

Шаг 3. Используя «веса» линий связи и'^, определить кратчайшие пути Яу-0 между всеми парами узлов «источник - адресат». Включить кратчайшие пути в множества П,-.-:

У

n;ß=>rLjj;i,j= 1,2, ...N

Шаг 4. Распределить потоки по кратчайшим путям:

Vi.y'= 1,2, ...N: V(k,l) s пу° :

Vfkl(p>-"fu® + 1,2,...P

2) если vk® = 0,то = 1 Шаг 5. Используя формулу (1), вычислить величину Т0у

Шаг 6. Положить: у^ := у Шаг 7. Положить:

(1)

(?) у4 '

f := min {у, }

vmax

fkl

ГДе: Р»»ах = ",axi ЧЦ }; V f/W > 0 Шаг 8. Пересчитать потоки в линиях связи:

(2)

/к!(р} := /« ^ - V; А-, / = 1,2, ...N ; р = 1, 2,.. .Р

У

Шаг 9. Вычислить задержки Zц между каждой парой узлов «источник (г) - адресат (/')».

Шаг 10. Отсортировать множество пар узлов (/,/) в порядке убывания величин /¡j^ij-Полученное множество пар обозначим через Q. Шаг 11. Выбрать очередную пару узлов (¡qJq) е Q. Если все пары рассмотрены, то

то STOP:

если у < у, то допустимых решении нет; (2)

если у = у, то получено оптимальное решение с заданной

точностью £.

Шаг 12. Для выбранной пары узлов (¡д^'д) инициализировать ютоки по кратчайшим путям ц>ц (р) :

1) И)к1 (Р) :=/к1 (р) ; к, I = 1,2, .. .Ы; р = 1,2,.. ,Р

(2)

'-= Фл-/- ъ0]0 = ».2, ...Р

Шаг 13. Определить «веса» линий связи \vj.j:

^ и=1,2,...№Л.;>0„/4(<4(

°о; / = 1,2, ...N: у у = 0 или

Шаг 14. Используя «веса» линий связи и^, определить кратчайший путь я,-0у0 (0) для пары узлов (¡0, ]0). Шаг 15. Проверить ограничение (8):

а )ЧиО<»:-*иео> Ь) если = 0. то 1}кро) = 1 2)У (А-, 1)е определить:

N

а)к = £ ;/к0о) 1= 1

Ь) если к > К, то перейти к шагу 11;

Шаг 16. Распределить потоку,- по кратчайшему пути щ • ^'

(2)

Шаг 17. Найти величину р 6 [0,1], минимизирующую функцию Т(р), при условии выполнения ограничения (4).

Шаг 18. Выполнить отклонение потока на величину р: /к1(р) = + -ты(р)-> к,1= 1,2, ...И;р = 1,2, ...Р

Шаг 19. Используя формулу (1), вычислить величину Тпеху

Шаг 20. Если ¡Т^ - Тпец, |< е, то перейти к шагу 11 (значение целевой функции улучшить не удалось).

Иначе:

1) включить кратчайший путь ^ в множество П¡^ : к- • <°)=>П. ■

2 )V(t/^eяíoУoí0>:vи^.-^

3) положить: То|(3 ™ Тпеи,; у(1) := у(2);

4) если у(1)< у, то перейти к шагу 7; иначе перейти к шагу 9.

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

1) при невысокой нагрузке на сеть значения средней задержки сообщении по сети отличаются незначительно;

2) перегрузка сети наступает при увеличении нагрузки на сеть:

- для фиксированной маршрутизации - в 1.7 раза;

- для 2-х путевой маршрутизации - в 2.6 раза;

- для альтернативной маршрутизации - в 3.1 раза.

Начальная нагрузка, принятая за 1, соответствует суммарному потоку 6.75 сообщений в секунду.

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

В четвертой главе описаны алгоритмы к-путевой альтернативной маршрутизации применительно к СПД «Экспресс-2» и вопросы их практической реализации. Описана методика сбора статистических данных на реальной СПД и результаты натурных экспериментов по использованию различных методов маршрутизации в реальной СПД.

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

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

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

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

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

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

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

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

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

Шлейфовая задержка определяется по задержке времени между отправкой всех сообщений диалогового характера

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

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

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

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

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

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

обнаружения зациклившихся сообщений (сообщений,

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

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

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

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

- 26.01.2000, 31.01.2000, 01.02.2000 - алгоритм двунаправленной маршрутизации с учетом текущей загрузки ребер.

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

Средневзвешенная шлейфовая задержка сообщений в сети составила:

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

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

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

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

Основные результаты работы.

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

2. Проведен анализ методов математического моделирования, применимых к маршрутизации в СПД «Экспресс-2»;

3. Проведено математическое моделирование предложенного метода маршрутизации, а также методов однопутевой и к-путевой маршрутизации без учета текущей загрузки на примере сети ЭВМ «Экспресс-2»;

4. Разработан алгоритм определения шлейфовой задержки в сети;

5. Разработан алгоритм обмена информацией о состоянии сети и поддержании идентичности модели сети в узлах сети;

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

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

8. Проведен натурный эксперимент на реальной сети ЭВМ «Экспресс-2», который подтвердил высокую степень соответствия полученных теоретических результатов и натурного эксперимента;

9. Проведена практическая реализация и внедрение предложенных алгоритмов в сети ЭВМ «Экспресс-2». Разработанные алгоритмы и программы внедрены на всех региональных центрах системы и входят в базовый комплект программного обеспечения АСУ «Экснресс-2».

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

1. Березка М.П., Рыжик Б.З. Организация сети передачи данных в АСУ "Экспресс-2". Тезисы докладов V совещания по распределенным системам и сетям, CDS-92. Светлогорск, 1992 РЦ ГПНТБ России с.7-9

2. Березка М.П., Борткевич А.И. Автоматизированная система коммутации сообщений NETWORK. "Проблемы информатизации на ж.д. транспорте" М,Транспорт,1992 с.76-83 ISBN 5-277-01656-2

3. Березка М.П., Родин И.В., Рыжик Б.З. Развитие математического и программного обеспечения АСУ "Экспресс-2". "Автоматика, телемеханика и связь на железнодорожном транспорте", 1994 N 2, с.19-20 ISSN 0005-2329

4. Березка М.П., Родин И.В., Рыжик Б.З. Некоторые проблемы разнородных и интегрированных сетей на базе АСУ "Экспресс-2".

"Компьютерные технологии управления на ж.д. транспорте" М, НИИЖА, 1995 с.132-140 УДК 656.25-52

5. Березка М.П. Адаптивная маршрутизация сообщений в сети передачи данных. Международная конференция по проблемам управления. Тезисы докладов, т.З, с. 176-178 М, ИПУ, 1999 ISBN 593394-004-6

6. Б. Марчук, И. Родин, М. Березка, А. Комиссаров На пути к «Экспрессу-3». «Железнодорожный транспорт/Connect! Мир связи» (совместный выпуск), №9, 1999г, с. 64-67

7. Березка М.П., Богданов В.М., Овчинников Б.С. Взаимодействие терминалов и информационных систем в АСУ «Экспресс» при переходе от системы «Экспресс-2» к системе «Экспресс-3». «Автоматика, связь, информатика», №4, 2000г, с.22-24. ISSN 00052329

8. Березка М.П. Маршрутизация сообщений в сети передачи данных АСУ «Экспресс-2». «Автоматика, связь, информатика», №10, 2000г, с.40-43 ISSN 0005-2329

9. Березка М.П., Вишневский В.М., Федотов Е.В. Модернизация алгоритмов маршрутизации в сети ЭВМ «Экспресс-2». «Ведомственные корпоративные системы и сети (ВКСС. Connect!)»,

№ 1, 2001г

10. Березка М.П., Вишневский В.М., Левнер Е.В., Федотов Е.В. Математические модели алгоритмов адаптивной маршрутизации. Электронный журнал ИППИ РАН, №1, 2001 г

Личный вклад диссертанта. Все научные результаты, составляющие основное содержание работы, получены диссертантом самостоятельно. В работах, выполненных в соавторстве, М.П.Березка внес следующий вклад: в [1] предложен алгоритм маршрутизации для СПД «Экспресс-2»; в [2] предложена методика обмена между узлами информацией о состоянии сети; в [3] рассмотрены результаты функционирования алгоритма маршрутизации при отказах отдельных элементов сети; в [4] рассмотрены проблемы функционирования СПД «Экспресс-2» и предложен алгоритм адаптации к перегрузкам ребер сети; в [6] предложена реализация методов адаптивной маршрутизации с

учетом текущей загрузки ребер; в [7] рассмотрены вопросы функционирования СПД «Экспресс-2» в условиях перехода к «Экспресс-3» и использования частью узлов сети в качестве транспорта сети TCP/IP; в [9] проведены расчеты параметров сети «Экспресс-2» на математических моделях при различных алгоритмах маршрутизации и проведены натурные эксперименты на реальной сети; в [10] рассмотрены математические модели маршрутизации, применимые к СПД «Экспресс-2».

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ МАРШРУТИЗАЦИИ В СЕТЯХ ЭВМ.

1.1. Распределенная обработка данных в сетях ЭВМ.

1.2. Стратегии маршрутизации в сетях передами данных.

1.3. Краткая характеристика системы "Экспресс-2".

1.4. Развитие СПД "Экспресс-2" и методы маршрутизации.

1.5. Постановка задачи исследования.

ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ИССЛЕДОВАНИЯ АЛГОРИТМОВ МАРШРУТИЗАЦИИ В СЕТЯХ ПЕРЕДАЧИ ДАННЫХ.

2.1. Основные понятия и определения.

2.2. Постановка задачи.

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

ГЛАВА 3. МОДЕРНИЗАЦИЯ АЛГОРИТМОВ МАРШРУТИЗАЦИИ СООБЩЕНИЙ В СПД "ЭКСПРЕСС-2".

3.1. Разработка алгоритма адаптивной маршрутизации с учетом текущей загрузки для АСУ "Экспресс-2".

3.2. Исследование методов маршрутизации в сети передачи данных системы "Экспресс - 2".

3.3. Результаты анализа методов маршрутизации СЦЦ "Экспресс-2".

ГЛАВА 4. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ АЛГОРИТМОВ МАРШРУТИЗАЦИИ В СПД "ЭКСПРЕСС-2".

4.1. Методика распространения информации о состоянии сети.

4.2. Протокол адаптивной маршрутизации с учетом текущей загрузки ребер.

4.3. Программная реализация алгоритма адаптивной маршрутизации.

4.4. Методика сбора статистических данных о функционировании СПД "ЭКСПРЕСС-2".

4.5. Анализ результатов измерений работы реальной СПД "Экспресс-2" при использовании различных алгоритмов маршрутизации.

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

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

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

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

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

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

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

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

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

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

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

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

- сравнительный анализ и выбор алгоритмов маршрутизации применительно к сети ЭВМ «Экспресс-2».

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

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

Реализация результатов работы. Методы и алгоритмы, предложенные в диссертации, внедрены во всех 29-ти региональных центрах системы «Экспресс-2». Работы по модернизации алгоритмов маршрутизации сообщений проводились в 1999-2000 годах в рамках договоров ВНИИАС МПС на сопровождение эксплуатации системы «Экспресс-2» с МПС РФ, железнодорожными администрациями Украины, Белоруссии, Казахстана, Молдовы, Латвии и Узбекистана. 6

Внедрение указанных алгоритмов позволило улучшить функционирование сети в условиях всплесков нагрузки, при отказе каналов связи и в условиях перегрузки в периоды максимального трафика, а также позволило обеспечить в рамках сети «Экспресс-2» сбор информации в Москву и Минск обо всех проездных и перевозочных документах, оформленных, возвращенных и погашенных в любом региональном центре России и СНГ, если эти документы имеют отношение к перевозкам по России/Белоруссии или в вагонах Российских/Белорусских железных дорог, для формирования аналитической базы данных по пассажирским перевозкам. Акты о внедрении приведены в приложении 1. Апробация работы. Результаты диссертации докладывались на:

• V совещании по распределенным системам и сетям, С08-92. Светлогорск, 1992. «Организация сети передачи данных в АСУ "Экспресс-2"»

• Международной конференции по проблемам управления. Москва, ИЛУ, 1999. «Адаптивная маршрутизация сообщений в сети передачи данных».

• На научных семинарах ИППИ РАН и ВНИИАС МПС.

Публикации. Основные результаты диссертации опубликованы в 10 печатных работах. Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и приложений. Диссертация содержит 130 страниц включающих 6 рисунков, 22 таблицы, приложения содержат 20 страниц. Список литературы имеет 48 наименований.

ЗАКЛЮЧЕНИЕ

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

2. Проведен анализ методов математического моделирования, применимых к маршрутизации в СПД «Экспресс-2»;

3. Проведено математическое моделирование предложенного метода маршрутизации, а также методов однопутевой и к-путевой маршрутизации без учета текущей загрузки на примере сети ЭВМ «Экспресс-2»;

4. Разработан алгоритм определения шлейфовой задержки в сети;

5. Разработан алгоритм обмена информацией о состоянии сети и поддержании идентичности модели сети в узлах сети;

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

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

8. Проведен натурный эксперимент на реальной сети ЭВМ «Экспресс-2», который подтвердил высокую степень соответствия полученных теоретических результатов и натурного эксперимента;

1. Клейнрок JI. Коммуникационные сети: Пер. с англ. М.: Наука, 1975. - 256 с.

2. Клейнрок Л. Вычислительные системы с очередями: Пер. с англ. М.: Мир, 1979. - 600 с.

3. Шварц М. Сети ЭВМ. Анализ и проектирование: Пер. с англ. М.: Радио и связь, 1981. -336 с.

4. Д. Бертсекас, Р. Галлагер. Сети передачи данных: Пер. с англ. М.: Мир, 1989. - 544 с.

5. Дэвис Д., Барбер Д., Прайс У., Соломонидес С. Вычислительные сети и сетевые протоколы: Пер. с англ. М.: Мир, 1981. - 563 с.

6. Мизин И. А., Богатырев В. А., Кулешов А. П. Сети коммутации пакетов,- М.: Радио и связь, 1986. 408 с.

7. Jackson J. R. Networks of waiting lines //Operations Research.-1957.-N5.-p. 518-521.

8. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М.: Наука, 1987.-336 с.

9. Fratta L., Gerla М., Kleinrock L. The flow deviation method: An approach to store-and-forward communication network design //Networks.-1973.-vol.3, N2.-p. 97-133.

10. Cantor D. G, Gerla M. Optimal routing in a packet-switched computer network// IEEE Trans, on Computers.-1974.-vol. C-23, N10.-p. 1062-1068.

11. M. Schwartz, Cheung С. K. The gradient projection algorithm for multiple routing in message-switched networks/ЯЕЕЕ Trans, on Commun.-1976.-vol. COM-24, N4.-p. 449-456.

12. Gerla M., Kleinrock L. On the topological design of distributed computer networks// ШЕЕ Trans, on Commun.-1977.-vol. COM-25, Nl.-p. 48-53.

13. Frank M., Wolfe P. An algorithm for quadratic programming //Naval Research Logistic Quarterly.-^, N3.-p. 95-110.

14. Floyd R. W. Algorithm 97: Shortest path //Comm. ACM.-1962.-N3.-p. 345.

15. Федотов E. В. Определение оптимальных маршрутов в сети пакетной коммутации// Сетевая обработка информации/ МДНТП. М., 1990. - с.95-98.

16. Gavish В., Hantler S. L. An algorithm for optimal route selection in SNA networks// IEEE Trans, on Commun.-1983.-vol. COM-31, N10.-p. 1154-1161.

17. Courtois P. J., Semal P. An algorithm for the optimization of nonbifurcated flows in computer communication networks //Performance Evaluation.-1981.-vol.1.-p.139-152.

18. Вишневский В.М., Федотов Е. В. Анализ методов маршрутизации при проектировании сетей пакетной коммутации//3-гс11.S. "Teletraffic Theory and Computing Modeling". София, 1990.

19. Мину M. Математическое программирование. Теория и алгоритмы: Пер. с фр. М.: Наука, 1990. - 488 с.

20. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

21. Held М., Wolfe P., Growder Н. P. Validation of subgradient optimization //Mathematical programming.-1974.-N6.- p. 62-88.

22. Dijkstra E. W. A note on two problems in connexion with graphs//Numer. Math.-1959,l.-p. 269-271.

23. Зайченко Ю. П. Задачи проектирования структуры распределенных вычислительных сетей// Журнал «Автоматика». № 3, 1981. с.35-44.

24. Жожикашвили В. А., Вишневский В. М. Сети массового обслуживания.Теория и применение к сетям ЭВМ,- М.: Радио и связь, 1988,- 192 с.

25. Э.МАИНИКА Алгортимы оптимизации на сетях и графах

26. Прытов A.A. Алгоритмы маршрутизации сети "Сирена-2". 5-я Всесоюзная школа-семинар по РАСМО Рига, 1988 с.222

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

28. Б.Марчук, И.Родин, М.Березка, А.Комиссаров "На пути к "Экспрессу-3". Журнал «Железнодорожный транспорт/Connect! Мир связи» (совместный выпуск), № 9, 1999г, с.64-67.

29. Березка М.П., Богданов В.М., Овчинников Б.С. "Взаимодействие терминалов и информационных систем в АСУ "Экспресс" при переходе от системы "Экспресс-2" к системе "Экспресс-3". Журнал «Автоматика, связь, информатика», № 4, 2000г. с.22-24.1.SN 0005-2329

30. Березка М.П. "Маршрутизация сообщений в сети передачи данных АСУ "Экспресс-2". Журнал «Автоматика, связь, информатика», №10, 2000г с.40-43. ISSN 0005-2329

31. Марчук Б.Е. От продажи билетов к управлению пассажирскими перевозками. Журнал «Автоматика, связь, информатика», № 9, 1999г с.4-7. ISSN 0005-2329

32. Марчук Б.Е. Межгосударственная система управления пассажирскими перевозками АСУ «Экспресс-3». В сб: «Опыт разработки, эксплуатации и перспективы развития «Экспресс». Научно-практическая конференция» М.,ВНИИЖТ,1997 с.34-43.

33. Лисицын А.Л., Марчук Б.Е. Автоматизация управления пассажирскими перевозками. В сб: «Опыт разработки, эксплуатации и перспективы развития «Экспресс». Научно-практическая конференция» М.,ВНИИЖТ,1997 с.8-12.

34. Березка М.П., Рыжик Б.З. Организация сети передачи данных в АСУ "Экспресс-2". Тезисы докладов V совещания по распределенным системам и сетям, CDS-92. Светлогорск, 1992 РЦ ГПНТБ России с.7-9.

35. Березка М.П., Борткевич А.И. Автоматизированная система коммутации сообщений NETWORK. В сб. "Проблемы информатизации на ж.д. транспорте" М,Транспорт,1992 с.76-83. ISBN 5-277-01656-2

36. Березка М.П., Родин И.В., Рыжик Б.З. Некоторые проблемы разнородных и интегрированных сетей на базе АСУ "Экспресс-2". В сб. "Компьютерные технологии управления на ж.д. транспорте" М, НИИЖА, 1995 с. 132-140. УДК 656.211.5.072

37. Кульгин М.В. Коммутация и маршрутизация IP/IPX трафика. М, КомпьютерПресс, 1998, 216 с. ISBN 5-89959-057-2

38. БлэкЮ. Сети ЭВМ: протоколы, стандарты,интерфейсы. М, Мир, 1990

39. Богуславский Л.Б. Управление потоками данных в сетях ЭВМ. М, Энергоиздат, 1984, 168 с.

40. Васильев Г.П., Горский В.Е., Шяудкулис В.И., Саух Н.М. Программное обеспечение неоднородных распределенных систем: анализ и реализация. М, Финансы и статистика, 1986, 158 с.

41. Мартин Дж. Вычислительные сети и распределенная обработка. Перев с англ. Вып 2. М, Финансы и статистика, 1985, 256 с.

42. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками в сетях связи. М, Радио и связь, 1983, 216 с.

43. Шварц М. Сети связи: Протоколы, моделирование и анализ. В 2-х частях. Часть1. Перев с англ. М, Наука, Гл.ред.физ-мат.лит, 1992, 336 с.

44. Бутрименко A.B. Разработка и эксплуатация сетей ЭВМ. М, Финансы и статистика, 1981, 256 с.

45. Березка М.П., Родин И.В., Рыжик Б.З. Развитие математического и программного обеспечения АСУ «Экспресс-2». Журнал «Автоматика, телемеханика и связь на железнодорожном транспорте» № 2, 1994, с.76-73 ISSN 0005-2329

46. Березка М.П., Вишневский В.М., Федотов Е.В. «Модернизация алгоритмов маршрутизации в сети ЭВМ «Экспресс-2». Журнал «Ведомственные корпоративные сети и системы130

47. BKCC. Connect)». № l, 2001

48. Березка М.П., Левнер Е.В., Вишневский В.М., Федотов Е.В. «Математические модели ал горитмов адаптивной маршрутизации». Электронный журнал ИППИ РАН. № 1, 2001

49. Березка М.П. Адаптивная маршрутизация сообщений в сетях передачи данных. Международная конференция по проблемам управления. Тезисы докладов, т.З, с. 176-178 ИЛУ, 1999 ISBN 5-93394-004-6

50. Лазарев В.Г. Интеллектуальные цифровые сети. М, Финансы и статистика, 1996 223 с.131