Введение к работе
з .
Актуальность проблемы. Тема диссертации актуальна в связи с важным значением задачи эффективного использования пропускных способностей каналов связи в сетях передачи данных (в частности в СПД «Экспресс-2») с обеспечением установленного качества обслуживания. Особую важность имеет эффективная маршрутизация сообщений в условиях отказов отдельных элементов сети, всплесков трафика и локальных перегрузок. Несмотря на бурное развитие телекоммуникационных технологий, многие крупные сети передачи данных производственного назначения до сих пор вынуждены использовать низкоскоростные и ненадежные каналы связи. В тоже время многие как отечественные, так и зарубежные сети не используют алгоритмов маршрутизации, адаптивных к перегрузкам каналов. В значительной мере это объясняется тем, что большинство зарубежных сетей использует при выборе маршрута передачи критерий минимума стоимости передачи, а стоимость каналов связи в коммерческих системах не зависит от нагрузки. В тоже время существует класс отечественных и зарубежных сетей, для которых выбор маршрута, использующий в качестве метрики величину шлейфовой задержки и учитывающий перегрузки в сети, улучшает характеристики сети. Поэтому разработка адаптивного алгоритма маршрутизации, учитывающего текущую загрузку, перегрузки в сети и обеспечивающего эффективное расщепление трафика по нескольким направлениям, является актуальной задачей.
Целью диссертационной работы является разработка новых эффективных методов адаптивной маршрутизации, учитывающих текущую загрузку, реальную пропускную способность, перегрузки
и отказы отдельных элементов сети и позволяющих существенно повысить эффективность функционирования СПД.
В соответствии с поставленной целью задачами диссертации являются:
разработка и исследование адаптивного алгоритма маршрутизации, эффективно функционирующего в низкоскоростной ненадежной технической среде;
разработка методов математического моделирования алгоритмов адаптивной маршрутизации в СПД;
оценка целесообразности использования алгоритмов адаптивной маршрутизации в СПД «Экспресс-2» на основе разработанных методов математического моделирования.
Методы исследования. В работе использовались методы теории систем и сетей массового обслуживания, теории графов, теории потоков в сетях, динамического и системного программирования. Научная новизна работы заключается в разработке и исследовании новых алгоритмов адаптивной маршрутизации, позволяющих более гибко, чем в известных отечественных н зарубежных сетях, распределять нагрузку в сети, в разработке нового метода математического моделирования сети в условиях двух классов потоков и использования альтернативной п-путевой маршрутизации. Новыми научными результатами являются:
алгоритм адаптивной маршрутизации, основанный на методе лавинной рассылки, использующий новый способ определения шлейфовой задержки;
постановка задачи выбора оптимальных маршрутов и распределения потоков для п-путевой альтернативной маршрутизации; .
алгоритм решения задачи выбора оптимальных маршрутов и расчета характеристик сети для п-путевой альтернативной маршрутизации;
эффективный метод определения нижней оценки задачи выбора оптимальных маршрутов для фиксированной (однопутевой) маршрутизации;
сравнительный анализ и выбор алгоритмов маршрутизации применительно к сети ЭВМ «Экспресс-2».
Практическая ценность. Разработанный в диссертации алгоритм маршрутизации предназначен для использования в деитаграммных сетях коммутации пакетов, реализованных на низкоскоростной, ненадежной технике.
Предложенный в работе алгоритм маршрутизации позволяет улучшить эффективность функционирования СПД в условиях перегрузок и отказов каналов связи. Алгоритм позволяет также повысить эффективность использования имеющихся каналов связи путем расщепления трафика по нескольким направлениям. Реализация результатов работы. Методы и алгоритмы, предложенные в диссертации, внедрены во всех 29-ти региональных центрах системы «Экспресс-2». Работы по модернизации алгоритмов маршрутизации сообщений проводились в 1999-2000 годах в рамках договоров ВНИИАС МПС на сопровождение эксплуатации системы «Экспресс-2» с МПС РФ, железнодорожными администрациями Украины, Белоруссии, Казахстана, Молдовы, Латвии н Узбекистана.
Внедрение указанных алгоритмов позволило улучшить функционирование сети в условиях всплесков нагрузки, при отказе каналов связи и в условиях перегрузки в периоды максимального трафика, а также позволило обеспечить в рамках сети «Экспресс-2»
сбор информации в Москву и Минск обо всех проездных и перевозочных документах, оформленных, возвращенных и погашенных в любом региональном центре России и СНГ, если эти документы имеют отношение к перевозкам по России/Белоруссии или в вагонах Российских/Белорусских железных дорог, для формирования аналитической базы данных по пассажирским перевозкам. Апробация работы. Результаты диссертации докладывались на:
V совещании по распределенным системам и сетям, CDS-92. Светлогорск,1992. «Организация сети передачи данных в АСУ "Экспресс-2"»
Международной конференции по проблемам управления. Москва, ИПУ, 1999. «Адаптивная маршрутизация сообщений в сети передачи данных».
На научных семинарах ИППИ РАН и ВНИИАС МПС.
Публикации. Основные результаты диссертации опубликованы в 10
печатных работах.
Структура м объем диссертации. Диссертация состоит из
введения, четырех глав, заключения и приложений. Диссертация
содержит /1зО страниц включающих й рисунков, . таблиц,
приложения содержат страниц. Список литературы имеет
У.уГнаименоваиий.