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

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

□030Б2404

Максимович Вадим Васильев»

•■«и/

УПРАВЛЕНИЕ ПЕРЕРАСПРЕДЕЛЕНИЕМ ПОТОКОВ В МАГИСТРАЛЬНЫХ СЕТЯХ ПЕРЕДАЧИ ДАННЫХ

05 13 01 - Системный анализ, управление и обработка информации (промышченность)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Иркутск - 2007

003062404

Работа выполнена в ГОУ ВПО "Иркутский государственный университет путей сообщения" Федерального агентства железнодорожного транспорта

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

доктор технических наук, профессор Опарин Геннадий Анатольевич

Официальные оппоненты

доктор технических наук, профессор Башкуев Юрий Буддич

доктор физико-математических наук, профессор Попков Владимир Константинович

Ведущая организация ГОУ ВПО "Иркутский государственный технический университет"

Защита состоится "17" мая 2007 г в 10 часов на заседании диссертационного совета Д 218 004 01 при ГОУ ВПО "Иркутский государственный университет путей сообщения" по адресу 664074, Иркутск, ул Чернышевского, 15, ауд А803

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

Автореферат разослан "17" апреля 2007 г

Ученый секретарь диссертационного совета

Н П Деканова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы Сети передачи данных (СПД), использующие протокол Internet Protocol (IP), широко распространены по всему миру В последнее время в сетях передачи данных, использующих протокол IP, внедряются усчуги, как характерные для традиционных сетей с коммутацией каналов, такие как телефония, так и новые услуги, такие как видеотелефония, телевидение по запросу, виртуальные частные сети При этом пользователи требуют от сетей передачи данных на основе протокола IP, такого же качества предоставляемых услуг и надежности сети, к которому они привыкли в традиционных сетях TDM(Time-Division Multiplexing, Мультиплексирование с разделением времени) и PSTN(Public Switched Telephone Network, Публичная коммутируемая телефонная сеть) При этом остро стоит вопрос об эффективности использовании ресурсов СПД, надежности и быстрого восстановления работы сети после сбоя Не смотря на резкое увеличение скоростей на магистральных каналах связи, пропускная способность локальных сетей растет еще быстрее В октябре 2006 года подразделешюм IEEE SA(IEEE Standard Association) организации IEEE(Institute of Electrical and Electronics Engineers) принят стандарт Ethernet с пропускной способностью 10 Гигабит/сек(100Вазс-Т) по медной паре на расстоянии 100 и более метров Раньше для таких величин пропускной способности использовали дорогое оптоволокно, и внедрение медной пары вместо оптоволокна резко удешевит внедрение и сопровождение локальных сетей с такими скоростями передачи данных, что сделает внедрение локальных сетей с такой пропускной способностью массовой, и повлечет за собой широкое внедрение широкополосных сервисов и резкое возрастание объемов данных передаваемых через глобальные сети между локальными сетями Причина неэффективного использования ресурсов глобальных (магистральных) сетей передачи данных заключается в существующих алгоритмах протокочов маршрутизации Из-за недостатков традиционных протоколов маршрутизации потоки данных направляются только по маршруту с минимальной метрикой, игнорируя Другие маршруты Разумеется, если маршруты для передачи данных будут выбираться с учетом доступных ресурсов сети, это положительно скажется на качестве обслуживания и позволит при неизменных ресурсах сети повысить качество обслуживания или увеличить количество услуг, для которых необходимо гарантированное качество сервиса

Один из способов решения вышеприведенных проблем заключается во внедрении в СПД, использующих протокол II', методов перераспределения потоков данных, которые давно используются в таких сетях как А'1М Задача методов перераспределения заключается в достижении наиболее эффективного использования ресурсов СПД при обеспечении требуемого качества предоставляемых сервисов,

з

быстрого восстановления после сбоев Как правило, работа методов перераспределения требует использования протоколов маршрутизации с учетом ограничений (Constraint-Based Routing Protocol), иначе называемых протоколы маршрутизации с учетом уровня качества (QoS-Based Routing Protocol)

В глобальных СПД базовые средства перераспределения потоков данных в настоящее время реализованы в рамках технологии MPLS-TE (Multiprotocol Switching Label Traffic Engineering) При использовании технологии MPLS-TE маршрутизаторы сами могут самостоятельно рассчитывать пути, но без учета всей информации о состоянии СПД, особенно о загруженности каналов связи В этих условиях предпочтительным является использование внешней управляющей программы, обеспечивающей сбор статистики об интенсивности входных потоков и принятие (на основе этой информации) необходимых управляющих решений по перераспределению потоков данных с учетом пропускных способностей каналов связи

Тематика диссертационного исследования находится в русле приоритетных направлений развития науки в Российской Федерации "Информационно-телекоммуникационные системы", утвержденных Президентом Российской Федерации 21 мая 20Об i (Кг Пр-843)

Объект исследования. Глобальные СПД с технологией перераспределения потоков данных MPLS-TE

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

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

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

2 Формализовать задачу перераспределения потоков данных с целью равномерной загрузки каналов связи в виде специализированной задачи удовлетворения ограничений(в том числе и булевых)

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

4 Разработать архитектуру, алгоритмическое, информационное и программное обеспечение системы управления равномерной загрузкой каналов связи в магистральной СПД

5 Оценить эффективность разработанных методов и средств на примере производственной задачи перераспределения потоков данных и балансировки загруженности каналов связи для магистральной СПД Восточно-Сибирской железной дороги (ВСЖД) Методы исследования При решении перечисленных задач использовались методы системного анализа, теории управления, обработки информации, теории компьютерных сетей передачи данных, комбинаторные методы дискретной математики и искусственного интеллекта

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

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

2 Предложена, разработана и реализована архитектура, алгоритмическое, информационное и программное обеспечение централизованной системы управления потоками данных в глобальных СПД с применением технологии МРЪБ-ТЕ

Практическая значимость полученных результатов Применение разработанных в диссертации методов и программных средств позволяет повысить эффективность использования ресурсов магистральных СПД с технологией МРЬБ-ТЕ

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

Реализация Исследования по теме диссертации выполнялись в рамках плановых тем кафедры "Управ пение техническими системами" Иркутского государственного университета путей сообщения Результаты исследования используются информационно-вычислительном центре ВСЖД филиала ОАО "РЖД" для совершенствования алгоритмов управления магистральной СПД, а также в Иркутском государственном университете путей сообщения при выполнении дипломных работ по кафедре "Управление техническими системами"

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

• II Всероссийская конференция "Инфокоммуникационные и вычислительные технологии и системы" (Иркутск, 2006),

• VI Международная научно-практическая конференция "Моделирование Теория, методы и средства " (Новочеркасск, 2006),

• 44-ая Всероссийская научно-практическая конференция "Современные технологаи-железнодорожпому транспорту и промышленности" (Хабаровск, 2006),

• конференция "Ляпуновскис чтения & Презентации информационных технологий" (Иркутск, 2006),

• V Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография" - ЗГВЕСКУРТО'Об (Шушенское, 2006)

Публикации По теме диссертации опубликовано 6 работ в виде статей в журналах, трудах международных и российских конференций и сборнике научных трудов ИрГУПС, в том числе одна статья в издании, рекомендованном ВАК для опубликования научных положений диссертационных работ В работах опубликованных в соавторстве, автору принадлежат научные и практические результаты, заявленные в диссертации При этом булевы модели и средства генерации туннельных маршрутов разработаны совместно с ГА Опариным, АГ1 Новопашиным, В Г Богдановой и являются неделимыми

Структура и объем работы Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 91 наименования Общий объем диссертации - 98 страницах машинописного текста, полный объем диссертационной работы 131 страница Работа включает 30 рисунков, 2 таблицы и 8 приложении Приложения содержат дополнительные материалы, включающие схемы СПД ВСЖД, описание структуры файлов, результаты вычислительных экспериментов

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ Во введении обосновывается актуальность темы диссертационной работы, формулируются цель и основные направления научного исследования, отмечаются новизна и практическая значимость полученных результатов

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

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

6

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

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

Алгоритмы "заранее вычисляемые" могут быть разделены на реализующие непосредственно выбор маршрута в источнике (Source Routing), выбирающие маршрут до начала установки соединения, и поэтапную маршрутизацию (Нор-Ьу-Нор), выбирающие маршрут непосредственно в процессе установки

'Вишневскии В М Теоретические основы проектирования компьютерных сетей М ЗЛО "Техносфера" - 2003 - 512 с

2 Gafnt М , Bertsekas D Asymptotic Optimality of Shortest F^th Routing Algorithms 11 IEEE Trans Of Information Theory - 1987 - N 1

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

Во втором разделе главы приводится описание протокола Multiprotocol Switching Label (MPLS), структуры меток, принципы работы MPLS Далее рассматриваются принципы работы Multiprotocol Switching Label Traffic Engineering (MPLS-TE), компонентов технологии, в том числе виртуальных туннелей Приводятся алгоритмы работы Shortest Path First (SPF) и Constrained Shortest Path First (CSPF)

В третьем разделе главы рассматриваются подходы к внедрению и эксплуатации технологии MPLS—ТЕ - тактический, неавтономный стратегический и автономный стратегический

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

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

8

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

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

Приводится обзор алгоритмов перераспределения потоков данных, таких как MIRA (Minimum-Interference Routing Algorithm3), LMIRA4 (Light Minimum Interference Routing Algorithm), New Bandwidth Guaranteed Routing Algorithm, MATE (MPLS adaptive traffic engineering5) и обзор программных продуктов SP Guru Network Planner компании OPNET и IP/MPLSView компании WANDL, VENUS (Virtual-circuit Enhanced Network Usage Simulator), RAIES Bell Labs и другие Отмечается, что наиболее близкие к теме диссертационного исследования разработки и программные продукты компаний OPNET, WANDL и Bell Labs практически недоступны на российском рынке Необходимы отечественные теоретические и технологические разработки, позволяющие эффективно решать задачи перераспределения потоков данных с целью балансировки загрузки каналов связи магистральных СПД, использующих технологию MPLS-TE

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

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

3 M Kodialam and f V Lakshman, "Minimum interference routing with applications to MPLS traffic engineering," m Proceedings of the Conference on Computer Communications (TFEE Infoc-nm) - Mar 2000 -10 p

4 G B Figueiredo, N L S da Fonseca, J A S Monteiro A Minimum Interference Routing Algorithm Technical Report IC-03-014 -2003 - 12 p

5 A Elwalid, C Jin, S Low, I Widjaja MATE MPLS adaptive traffic engineering Proc of IEEE INFOCOM'2001 - 2001 -20 p

РБ-{У,Е) без петель, где V - множество узлов коммутации, а Е — множество линий связи (|К| = и, Щ-т) Граф Р5 согласно назовем первичной сетью Также зададим ориентированный граф ЖБ = (У,К), = р, где множество дуг Л определяется потоками данных, поступающими в сеть и выходящими из нее Потоки данных состоят из пакетов, имеющих одинаковый приоритет и образующих пуассоновский поток со средним значением у, (пакетов/сек) для дуги Граф назовем вторичнои сетью6

Кроме того будем предполагать1

1) все линии связи абсолютно надежны и помехоустойчивы,

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

3) длины всех пакетов независимы и распределены по показательному закону со средним значением 1/ц (байт),

4) каждая линия связи е1 состоит из единственного дуплексного канала с пропускной способностью, равной (байт/сек)

Для случая фиксированной (однопутевой) маршрутизации определим множество хц (1 = 1, т, ] = 1, р ) двоичных переменных (хц е 10,1|), значения которых определяются следующим образом хч = 1, если поток проходит по линии связи е1 и ху = 0 - в противном случае Предположим так же, что для переменных хц

выполняются известные условия сохранения потока в сети'

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

(1)

_ р

для всех г = 1, т, й* < , =

7=1

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

определяет полную пропускную способность канала связи

6 Попков В К Математические модели связности 4 2 Гиперграфы и гиперсети - Новосибирск Изд ИВМиМГ СО РАН - 2001 - 180 с

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

легко определить величины потоков fl в линиях связи е1 первичной сети Пусть х* (соответственно ff ) — множество решений промежуточной задачи, где к означает номер решения Среди всех решений выберем такое, которое обеспечивает минимальное значение величины / неравномерности загрузки каналов связи

/ = тах^-min/*->imn (2)

Ести задача (2) имеет несколько решений, то среди них выбираем решение, для которого велотина max fl минимальна

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

^Чш-/)2 (3)

I

(п - количество каналов связи, f — -~Yf, - средняя загрузка каналов СПД) и

п ,

выборе решения промежуточной задачи, для которого D минимально Аналогично (2) в случае нескольких решений, выбираем то решение, для которого величина D минимальна

Сформулированную задачу далее будем называть задачей о равномерной загрузке каналов связи магистральной СПД

Итак, для фиксированной маршрутизации имеем х^е^ОД}, что позволяет

решать сформулированную задачу как переборную на языке теории графов Пусть Н - отображение, которое ставит в соответствие каждой дуге rt е R вторичной сети WS = (V,R) множество Д простых путей первичной сети PS = (V,E) таким образом, что начальные и конечные верппшы дуги г% и простых путей из Dt совпадают Такие простые пути в графе PS согласно терминологии MPLS-TE будем далее называть туннельными маршрутами Очевидно, отображение Н обеспечивает выполнение условии сохранегаш потока в сети дта переменных ху Если

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

Задача в такой постановке рассматривается и решается как дискретная задача удовлетворения ограничений (Constraint Satisfaction Problem - CSP), которая на

п

формальном уровне CSP представляется виде тройки (Y,D,Cy, где Y — \y\,yi> >УР}~ конечное множество переменных, D = |£>1,D2, ,DpJ - множество доменов Каждый домен Д - это конечное множество, содержащее возможные значения i -той переменной, С = jCVC2, конечное множество ограничений

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

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

Решение CSP - это такое означивание каждой переменной, что для любого ограничения выполняется соответствующее отношение над значением связанных им переменных Означивание переменной - есть присваивание ей некоторого значения из домена Целью решения CSP может быть как нахождение одного удовлетворяющего набора значений всех переменных (любого или с заданными свойствами), так и нахождение всех таких наборов Предполагается, что задача удовлетворения ограничений может не иметь решения Для многих задач переменные из множества Y - это скалярные переменные целого или перечисляемого типа В нашем случае переменная из Y — это структурированная величина, кодирующая туннельный маршрут в СПД Каждому потоку данных ставится в соответствие своя переменная, возможные значения которой представляют туннельные маршруты в сети для этого потока Множество ограничений С задается системой неравенств (1) для каждого канала связи Наиболее эффективный путь решения такой дискретной задачи удовлетворения ограничений состоит в использовании метода распространения ограничений в сочетании с техникой интеллектуального возврата и применении ряда приемов, учитывающих специфику задачи и повышающих общую эффективность поиска решения

Итак, задано множество переменных Y, соответствующее множеству дуг R графа вторичной сети WS Пусть для каждого у, е Y построено множество туннельных маршрутов (домен Д) и имеется множество ограничений (1) по допустимой верхней загрузке каналов связи первичной сети PS Необходимо для каждого потока, проходящего через первичную сеть, выбрать такой туннельный маршрут, 1гри котором суммарная загрузка ft не превышает величину d* Далее

7 Яхно Т М Программирование в ограничениях обзоры и классификация подходов и методов Системная информатика Сб научн тр - Новосибирск Наука, 1995 -Вып 4 Методы теоретического и системного программирования - С 160 — 192

среди всех решении задачи следует выбрать решение, которое обеспечивает минимальную неравномерность загрузки каналов связи в смысле условий (2) или (3)

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

е,, что требует выделения этому потоку ресурса у^ от пропускной способности й*

канала связи Поэтому, если туннельный маршрут из включает канал связи е, и

yJ > (I, то такой маршрут удаляется из области В] Если после выполнения

указанной процедуры для некоторого ] = 0, то поставленная задача не имеет

решения

Демоны ограничений Специфическая особенность нашей задачи удовлетворения ограничений состоит в следующем при вычислении загрузки /г I -го канала связи необходимы знания лишь о тех линиях связи, которые входят в туннельный маршрут (порядок каналов в маршруте для вычисления величины не имеет значения) Это обстоятельство позволяет существенно упростить процедуру отыскания общих каналов в двух или нескольких маршрутах, если каждому маршруту поставить в соответствие двоичный набор длины т таким образом, что г -ый элемент этого набора равен едшшцс, если г -ый элемент канала связи входит в маршрут, и равен нулю — в противном случае Нахождения общих дуг при этом сводится к выполнению булевых операций над машинными словами, которые эффективно реализуются на любом компьютере Предложенный механизм позволяет на каждом шаге решения задачи удовлетворения ограничений быстро выявлять текущие активные ограничения из (1) и выполнять их проверку (запуск демонов ограничений)

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

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

данных (значение из В} ) из узла-источника в узел-адресат) Через обозначим

мощность множества DJ (после выполнения процедуры отбраковки туннельных

маршрутов) Упорядочим маршрут в каждом домене 1)] в порядке возрастагом длины

маршрута В памяти компьютера списки областей и текущих значений

переменных у} (у = 1 ,р) удобно представить в виде двух двоичных массивов £) и 7

Размерность массива У равна ру.ц, где с{ - число байт (или слов), необходимых для

размещения представления маршрутов в битовом представлении у -ая строка массива У представляет текущее значение переменной у] Размерность массива О равна 1х{ру.с[), где ! = maxlength¡ В г-ой строке массива последовательно располагаются двоичные описания маршрутов из областей Массив О

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

Распространение ограничений Обозначим через У 1 -ую строку матрицы У

Тогда У' = V У задает множество активных каналов (каналов, по которым идет хотя 1=1

бы один поток данных), полученных в результате означивания переменных У\'У2< 'Л Метод распространения ограничении требует введения еще одной структуры данных для множества областей П1,02, ,Ор Это целочисленный массив 2 размерностью Ыр, который позволяет выявить возможные значения /-ой переменной у, из области ее определения Д после очередного означивания Обозначим через Z' столбец матрицы Z В этом столбце одновременно перечисляются допустимые и недопустимые значения переменной у,, причем при последних указывается номер переменной, означивание которой является причиной запрета использования этого значения (результат распространения ограничений)

Вначале массив X обнуляется На последующих этапах = 0 означает, что 1 -ое значение из £>( — одно из допустимых значений для у1 = б означает недопустимость г-го значения из Д., где - первая по счету переменная, являющаяся причиной запрета (определяется путем анализа нарушенных ограничении по загрузке каналов связи) в результате означивания переменной у! из области О,

Пусть у, = £>,' Для каждого канала связи, входящего в маршрут £>,' определяется множество номеров проходящих по нему потоков, связашшх с присвоением значений переменным у1,у2, ,у,_{ Для каждого ] -го канала связи из этого списка находится минимальный индекс переменной из множества у1,у2, ,,У(Ч такой, что +у,><1* Тогда значение 5 вычисляется как по всем

каналам, входящим в маршрут

Интеллектуальный возврат Нам понадобится целочисленный массив Р, каждый элемент р, которого есть значение последнего ненулевою элемента в столбце 7J Если pt = length, и для всех значений из области Dt нарушены ограничения (1), необходимо вернутся назад к первой переменной, которая является причиной неудачи и присвоить ей новое значение (задать новый маршрут для этой переменной) Номер рЪ точки возврата определяется путем анализа конфликтного множества Z' и определяется, как mm Z\ При интеллектуальном возврате

необходимо восстановить состояние (среду) точки возврата путем обнуления в столбцах Z' (pb<i<t) значений элементов, равных или превышающих значение РЪ

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

Поэтому далее имеет смысл рассмотреть алгоритмы перечисления всех простых путей, длины которых не превосходят некоторой заданной величины k(k<n) Условия задачи генерации туннельных маршрутов запишем в виде системы булевых уравнений Для их решения будем использовать эффективные решатели таких уравнений системы РЕБУС8, которые в ряде случаев обгоняют специализированные алгоритмы поиска на графах

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

Опарин Г А , Богданова В Г Технология булева моделирования дискретных задач в инструментальных комплексе РЕБУС Моделирование Теория, мет оды и средства Материалы V Межд Научн -практ конф -Новочеркаск ЮРГТУ - 2005 -41 - С 18-22

туннельные маршруты для общего случая, когда первичный граф РБ = (У,Е) является мультиграфом Вторая модель обеспечивает решение задачи для случая, когда граф Р8 = (У,Е) является обычным графом

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

Если Р8 - это обычный ориентированный граф (не мультиграф), то размерность булевой модели равна произведению длины маршрута на число вершин в графе В этом случае в качестве первичного представления графа используется матрица смежности вершин Бг которая определяется следующим образом значение элемента я этой матрицы равно числу дуг, направленных от вершины г к вершине ] (для нашего случая 5у — 0 или = 1) Вторая модель используется для решения

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

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

Маршрут передвижения определим в виде матрицы X кхп булевых переменных х{], где индекс t (дискретное время) обозначает номер шага

передвижения фишки, индекс ] соответствует номеру вершины графа, х0 = 1 означает, что на шаге с номером ( фишка находится в вершине с номером у

Тогда для элементов матрицы X для построения туннельных маршрутов длины к (к <п) необходимо установить следующие булевы ограничения

Условие 1 Определены начальная и конечная позиции фишки в вершинах графа (номера вершин д и р соответственно)

Условие 2 В каждый момент времени 1 фишка выполняет один и только один ход из всех допустимых, то есть в каждый момент времени на множестве вершин графа стоит одна и только одна фишка (или в каждой строке матрицы X может быть одна и только одна единица) Это ограничение выражается уравнением

*1А=0> Д =°> хк,Р =°> Д ХК, =0

■к,Р

к Гл-1 п

{=1 1=1 у=1+1

& =0

Условие 3. Фишка может посетить узел не более одного раза (каждый столбец матрицы X содержит не более одной единицы). Этому ограничению соответствует уравнение:

п Ы к

v V v (х- л А" ) = 0.

Условие 4, Условие выбора допустимого хода фишки на каждом шаге записывается в следующем виде.

Ы л

V V V (X; Л1 , ,) = 0,

где / ■ - множество допустимых ходов (номеров вершин графа) фишки на шаге с номером t (элементарно определяется но матрице смежности

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

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

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

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

В качестве объекта управления в нашем случае выступает СПД, представляющая собой множество однотипных маршрутизаторов, соединенных дуплексными каналами связи с заданной пропускной способностью (базовая магистраль) В качества инструментального средства управлешы и перераспределения нагрузки в каналах связи используется технология MPLS-1E, обеспечивающая привязку потока данных по запросу к физическим каналам Указанные программно-техшгческие средства позволяют реализовать глобальные (цептрализовашше) алгоритмы перераспределения потоков MPLS, позволяющие обеспечить равномерную загрузку физических каналов связи (цель управления) в условиях нестабильности входных потоков данных (ВПД) Входные потоки данных, поступающие на узел-источник для передачи в узел-адресат являются возмущающими воздействиями для ОУ Предполагается, что интенсивности ВПД в общем случае являются медленно меняющимся или кусочно-постояшшми функциями времени t

Система управлешш имеет контрольно-измерительные приборы, к числу которых относятся а) датчики перегрузки каналов (ДПК), формирующие список номеров ар перегруженных каналов, б) датчики отказа каналов или узла (ДОКУ),

формирующие списки <У„ отказавших каналов и узлов, в) измерители интенсивности входных потоков (ИИВП), формирующие вектор у интенсивности потоков у{ ут в момент времени t Для работы ИИВП используется информация, получаемая с маршрутизаторов с помощью протокола Netflow Информация на выходах датчиков и измерителя обновляется с некоторым периодом дискретности Т Величина Т выбирается таким образом, чтобы не слишком перегружать сеть сбором дополнительной информации и, в тоже время, с необходимой точностью фиксировать моменты нарушения штатного режима функционирования сети Информация с КИП

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

Вычисление новых маршрутов в УУ сводится к решению задачи удовлетворения ограничений Если решение этой задачи существует и конструктивно построено, ю список новых туннельных маршрутов передается в исполнительный орган, в противном случае выдается сигнал оператору о невозможности формирования новых ТМ, обеспечивающих равномерную загрузку каналов связи Оператор, на основании имеющейся у него информации о параметрах функционирования сети и пошаговой работе УУ, в любом случае (решение найдено или решение отсутствует) имеет возможность изменить допустимые значения верхней загрузки d* каналов связи, длину туннельных маршрутов и запустить процесс поиска новых ТМ заново

Точками приложения управляющих воздействий в ОУ являются конфигурационные файлы, которые определяют функционирование маршрутизаторов ИО так же является программным блоком, который реализует ТМ путем создания и последующей загрузки новых конфигурационных файлов (КФ) для каждого из маршрутизаторов сети

Блоки КИП, УУ, ИО составляют математическое обеспечение специального программно-аппаратного центрального узла сети, который будем называть в дальнейшем сервером маршрутизации (СМ)

Во втором разделе главы разработана структура, алгоритмическое, информационное и программное обеспечение сервера маршрутизации В частности, приводится обоснование выбора коллектора Netflow для сбора информации о потоках данных и их интенсивностях, языков программирования Perl и Pascal для реализации модулей ИИВП и УУ (формирования ТМ) Приводится структура данных в программе формирования ТМ и в базе данных коллектора Netflow Рассматривается реализация блоков ДПК, ДОКУ, ИО

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

19

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

На магистральном уровне СПД ВСЖД состоит из регионального узла (РУ), расположенного в Иркутске и являющимся ядром сети передачи данных ВСЖД, и транспортно-периферийных узлов (ТПУ) РУ узел связан дуплексными каналами связи Е1 пропускной способностью 2,048 Мбит/сек с транспортно-периферийными узлами ТПУ, расположенными на крупных станциях (рис 2) Магистраль СПД ВСЖД содержит один региональный узел, состоящий из двух маршрутизаторов, и девятнадцать ТПУ

Построена первичная сеть магистральной СПД ВСЖД в виде мультиграфа РБ = (У ,Е), Е - множество тиний связи {\У\=п,\Е\=т), п-20, т = 88 Так как каналы связи являются полнодуплексными, для представления канала связи в графе РБ используется два ориентированных ребра Некоторые узлы СПД ВСЖД соединяются несколькими каналами связи, например ТПУ Лена - РУ, ТПУ Вихоревка — РУ, ТПУ Наушки - ТПУ Улан-Удэ и так далее В наших расчетах мы используем упрощенную модель первичной сети, когда все кратные ребра сведены к двум ориентированным ребрам Это означает, что несколько параллельных каналов связи представляются в виде одного общего канала связи с пропускной способностью, равной сумме пропускных способностей каналов, составляющих этот общий канал связи Такая редукция первичной сети позволяет использовать более бысгрый алгоритм построения туннельных маршрутов для каждого потока данных Замена мультиграфа первичной сети обычным графом позволяет ускорить необходимые расчеты без потери общности, при условии, что интенсивность входных потоков не превышает пропускной способности множества каналов связи, соединяющих два маршрутизатора (для нашей задачи это условие выполняется) Модель первичной сети в виде обычного графа содержит 72 дуги

Вычислительный эксперимент с магистральной СПД ВСЖД проводился с периодом дискретности обновления информации об интенсивности ВПД Г=15 минут

Иркутск -Сорт

Сухонская Черемхово Зима -- 1 - „ 1 1

-Лулун

Наушм1

Нижнеудинск

Улан-Удэ

Слюдянка

Новая Чара

Таксимо

Се аероб а ика л ьск

Усть-Илимск . 2

Лсиа

_Ууна

IВихоревка

Коршунихо

Рис. 2. Базовая сеть мвщстршш СЦД ВСЖД.

В результате функционирования блока ИИВП сервера маршрутизации выявлено шестьдесят потоков данных, с интенсивностями от 1000 байг/сек до 838000 байт/сек Построена модель вторичной сети (граф Цг8 = (у,К),\Я\=р), которая содержит 60 дуг Штатные средства маршрутизации большую часть ВПД передают по одним и тем же каналам связи, входящим в кратчайшие маршруты При этом значение неравномерности загрузки каналов связи £) в магистральной СПД ВСЖД равно 4,58*1010

Функционирование сервера маршрутизации позволило снизить нагрузку на перегруженные каналы связи за счет перемещения некоторых ВПД на малоиспользуемые каналы связи В целом проведенный вычислительный эксперимент говорит о возможности более эффективного использования доступных ресурсов магистральной СПД ВСЖД и увеличения суммарной нагрузки на сеть В результате работы предложенной в диссертации системы балансировки загрузки величина £> уменьшилась до значения 3,64*1010, что говорит о сокращении неравномерности загрузки каналов связи на 21% и о неэффективном использовании ресурсов СПД при использовании традиционных протоколов поэтапной маршрутизации

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

Главным результатом диссертационной работы является создание моделей, методов и средств управления равномерной загрузкой каналов связи в магистральных сетях передачи данных на основе использования технологии МРЬ8-ТЕ Характерной особенностью предложенного в диссертации подхода является систематическое использование методов программирования в ограничениях (в том числе и булевых) для решения задачи перераспределения потоков данных в магистральной СПД

Основные научные п практические результаты, которые выносятся на защиту

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

2 Методическое, алгоритмическое и программное обеспечение решения задачи

3 балансировки загрузки каналов связи, основанное на применении технологии программирования в ограничениях

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

5 Решение прикладной задачи о перераспределении потоков данных в магистральной СПД ВСЖД

Полномасштабное или далее частичное внедрение результатов диссертационного исследования в магистральную СПД ВСЖД позволят более эффективно использовать

22

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Опарин Г А , Богданова В Г , Новопашин А П, Максимович В В Фиксированная маршрутизация в магистральных сетях передачи данных булевы модели генерации множества туннельных маршрутов и узла-источника в узел-адресат // Вестник 11 У Приложение -2006 -№17 -С 170-175

2 Максимович В В Фиксированная маршрутизация как инструмент обеспечения требуемой загрузки каналов связи в сетях передачи данных математические модели и методы решения //Современные технологии - железнодорожному транспорту и промышленности труды 44-ой Всероссийской научно-практической конференции ученых транспортных вузов, инженерных работников и представителей академической науки, 2526 января 2006 г-Хабаровск Изд-во ДВГУПС, 2006 - Т 2 - С 225-229

3 Опарин Г А, Максимович В В Равномерная загрузка каналов связи при фиксированной маршрутизации в магистральных сетях передачи данных как задача удовлетворения ограничен™ // Моделирование Теория, методы и средства Материалы VI Международной наун -практ конф , г Новочеркасск, 7 апр 2006 г В 5 ч / Юж - Рос гос Техн ун-т(НПИ)-Новочеркасск ЮР1 ТУ, 2006-Ч 5-С 33-39

4 Опарин Г А , Богданова В Г , Новопашин А П , Максимович В В Математические модели, методы и средства управления равномерной загрузкой каналов связи в магистральных сетях передачи данных // Инфокочмуникационные и вычислительные технологии и системы (ИКВТС-06) Материалы И Всероссийской конференции с международным участием - Улан-Удэ Изд-во Бурятского университета Т 2, 2006 -С 7487

5 Опарин Г А , Максимович В В Управление маршрутизацией в магистральных сетях передачи данных с использованием технологии MPLS Информационные системы контроля и управления в промышленности и на транспорте Моделирование систем управления Сб науч трудов / Под ред С H Васильева, Ю Ф Мухопада - Иркутск Изд-во ИрГУПС, 2006 - Вып 14-С 22-29

6 Опарин Г А , Богданова В Г , Новопашин А П , Максимович В В Распределение нагрузки в магистральных сетях передачи данных как задача удовлетворения ограничений //Ляпуновские чтения & Презентация информационных технологий Материалы конференции - Иркутск ИДСТУ СО РАН, 2006 - С 36

Подписано в печать 16 04 07 Формат 60 х 84 1/16 Гарнитура 1 нпез^'й'Иотап Бумага офсетная Печать трафаретная Уел печ л 1,4 Тираж 150 экз Зак 437

Отпечатано в Глазковской типографии 664039, г Иркутск, ул Гоголя, 53 Тел 38-78-40

ВВЕДЕНИЕ.

ГЛАВА 1. СРЕДСТВА ПЕРЕРАСПРЕДЕЛЕНИЯ ПОТОКОВ ДАННЫХ В КОМПЬЮТЕРНЫХ СЕТЯХ.

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

1.2. Многопротокольная коммутация меток.

1.3. Методы перераспределения потоков данных с помощью технологии MPLS-TE.

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

2.1. Постановка задачи о равномерной загрузке каналов связи.

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

2.3. Программирование в ограничениях как метод решения задачи о равномерной загрузке каналов связи СПД.

2.4. Булевы модели генерации туннельных маршрутов.

ГЛАВА 3. СИСТЕМА УПРАВЛЕНИЯ РАВНОМЕРНОЙ ЗАГРУЗКОЙ КАНАЛОВ СВЯЗИ В МАГИСТРАЛЬНОЙ СЕТИ ПЕРЕДАЧИ ДАННЫХ.

3.1. Описание системы управления.

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

3.3. Балансировка загрузки каналов связи для магистральной СПД ВСЖД.

Актуальность темы. Сети передачи данных (СПД), использующие протокол Internet Protocol (IP), широко распространены по всему миру. В последнее время в сетях передачи данных, использующих протокол IP, внедряются услуги, как характерные для традиционных сетей с коммутацией каналов, такие как телефония, так и новые услуги, такие как видеотелефония, телевидение по запросу, виртуальные частные сети. При этом пользователи требуют от сетей передачи данных на основе протокола IP, такого же качества предоставляемых услуг и надежности сети, к которому они привыкли в традиционных сетях TDM(Time-Division Multiplexing, Мультиплексирование с разделением времени) и PSTN(Public Switched Telephone Network, Публичная коммутируемая телефонная сеть). При этом остро стоит вопрос об эффективности использовании ресурсов СПД, надежности и быстрого восстановления работы сети после сбоя. Не смотря на резкое увеличение скоростей на магистральных каналах связи, пропускная способность локальных сетей растет еще быстрее. В октябре 2006 года подразделением IEEE SA(IEEE Standard Association) организации IEEE(Institute of Electrical and Electronics Engineers) принят стандарт Ethernet с пропускной способностью 10 Гигабит/сек(100Вазе-Т) по медной паре на расстоянии 100 и более метров. Раньше для таких величин пропускной способности использовали дорогое оптоволокно, и внедрение медной пары вместо оптоволокна резко удешевит внедрение и сопровождение локальных сетей с такими скоростями передачи данных, что сделает внедрение локальных сетей с такой пропускной способностью массовой, и повлечет за собой широкое внедрение широкополосных сервисов и резкое возрастание объемов данных передаваемых через глобальные сети между локальными сетями. Причина неэффективного использования ресурсов глобальных (магистральных) сетей передачи данных заключается в существующих алгоритмах протоколов маршрутизации. Из-за недостатков традиционных протоколов маршрутизации потоки данных направляются только по маршруту с минимальной метрикой, игнорируя другие маршруты. Разумеется, если маршруты для передачи данных будут выбираться с учетом доступных ресурсов сети, это положительно скажется на качестве обслуживания и позволит при неизменных ресурсах сети повысить качество обслуживания или увеличить количество услуг, для которых необходимо гарантированное качество сервиса.

Один из способов решения вышеприведенных проблем заключается во внедрении в СПД, использующих протокол IP, методов перераспределения потоков данных. Задача методов перераспределения заключается в достижении наиболее эффективного использования ресурсов СПД при обеспечении требуемого качества предоставляемых сервисов, быстрого восстановления после сбоев. Как правило, работа методов перераспределения требует использования протоколов маршрутизации с учетом ограничений (Constraint-Based Routing Protocol), иначе называемых протоколы маршрутизации с учетом уровня качества (QoS-Based Routing Protocol).

В глобальных СПД базовые средства перераспределения потоков данных в настоящее время реализованы в рамках технологии MPLS-TE (Multiprotocol Switching Label Traffic Engineering). При использовании технологии MPLS-TE маршрутизаторы сами могут самостоятельно рассчитывать пути, но без учета всей информации о состоянии СПД, особенно о загруженности каналов связи. В этих условиях предпочтительным является использование внешней управляющей программы, обеспечивающей сбор статистики об интенсивности входных потоков и принятие (на основе этой информации) необходимых управляющих решений по перераспределению потоков данных с учетом пропускных способностей каналов связи.

Тематика диссертационного исследования находится в русле приоритетных направлений развития науки в Российской Федерации

Информационно-телекоммуникационные системы", утвержденных Президентом Российской Федерации 21 мая 2006 г. (№ Пр-843).

Объект исследования. Глобальные СПД с технологией перераспределения потоков данных MPLS-TE.

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

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

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

2. Формализовать задачу перераспределения потоков данных с целью равномерной загрузки каналов связи в виде специализированной задачи удовлетворения ограничений(в том числе и булевых).

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

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

5. Оценить эффективность разработанных методов и средств на примере производственной задачи перераспределения потоков данных и балансировки загруженности каналов связи для магистральной СПД Восточно-Сибирской железной дороги (ВСЖД).

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

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

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

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

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

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

Реализация. Исследования по теме диссертации выполнялись в рамках плановых тем кафедры "Управление техническими системами" Иркутского государственного университета путей сообщения. Результаты исследования используются информационно-вычислительном центре ВСЖД филиала ОАО "РЖД" для совершенствования алгоритмов управления магистральной СПД, а также в Иркутском государственном университете путей сообщения при выполнении дипломных работ по кафедре "Управление техническими системами".

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

• II Всероссийская конференция "Инфокоммуникационные и вычислительные технологии и системы" (Иркутск, 2006).

• VI Международная научно-практическая конференция "Моделирование. Теория, методы и средства." (Новочеркасск, 2006).

• 44-ая Всероссийская научно-практическая конференция "Современные технологии-железнодорожному транспорту и промышленности" (Хабаровск, 2006).

• конференция "Ляпуновские чтения & Презентации информационных технологий" (Иркутск, 2006).

• V Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография" - SIBECRYPTO'06 (Шушенское, 2006).

Публикации. По теме диссертации опубликовано 6 работ в виде статей в журналах, трудах международных и российских конференций и сборнике научных трудов ИрГУПС, в том числе одна статья в издании, рекомендованном ВАК для опубликования научных положений диссертационных работ. В работах, опубликованных в соавторстве, автору принадлежат научные и практические результаты, заявленные в диссертации. При этом булевы модели и средства генерации туннельных маршрутов разработаны совместно с Г.А. Опариным, А.П. Новопашиным, В.Г. Богдановой и являются неделимыми.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 91 наименования. Общий объем диссертации - 98 страницах машинописного текста, полный объем диссертационной работы 131 страница. Работа включает 30 рисунков, 2 таблицы и 8 приложений.

ЗАКЛЮЧЕНИЕ

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

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

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

2. Методическое, алгоритмическое и программное обеспечение решения задачи балансировки загрузки каналов связи, основанное на применении технологии программирования в ограничениях.

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

4. Решение прикладной задачи о перераспределении потоков данных в магистральной СПД ВСЖД.

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

1. http://standards.ieee.org/2. http://www.ieee.org/

2. Олифер В.Г., Олифер Н.А. Компьютерные сети. 3-е изд.-СПб.: Питер2006.-958 с.

3. Davie В., Rekhter Y. MPLS Technology and Applications Los Altos.: CA.—2000.-287 c.

4. V. Sharma, et. al., "Framework for MPLS based Recovery", Internet draftdraft-ietf-mpls-recovery-frmwrk-04.txt>-July, 2001.-31 p.

5. M. Kodialam, T.V. Lakshman, Dynamic Routing of Bandwith Guaranteed

6. Tunnels with Restoration. Proc Of Infocom - March, 2000.-10 p.

7. Вишневский В. M. Теоретические основы проектирования компьютерныхсетей. М.: ЗАО "Техносфера".- 2003 512 с.

8. Gafni М., Bertsekas D. Asymptotic Optimality of Shortest Path Routing

9. Algorithms // IEEE Trans. Of Information Theory 1987 - N 1 - 83- 90 p.

10. Дикер Пилдуш Г. Сети ATM корпорации Cisco С.П.: Вильяме - 2004—880 с.

11. ATM Forum. Private Network-Network Interface Specification. Version10.- AF-PNNI-0055.000- March, 1996.-385 p.

12. ATM Forum. PNNI Augmented Routing. Version 1.0.-AF-RA-0104.0001. January, 1999 -65 p.

13. ATM Forum. Private Network-Network Interface Specification. Ver. 2.O.1.ving List.- LTD-CS-RA-PNNI-02.03.- July, 1996.

14. Reilly J., Abate M. Scheduled Connections: Managing Temporal Constrainson Broadband Network Resources // Proceedings of IS& N'98. May, 1998— Lecture Notes in Computer Science. Springer.-425 p.90

15. Вивек Олвейн. Структура и реализация современной технологии MPLS .- С.П.: Вильяме.- 2004.- 470 с.

16. Awduche D. MPLS and Traffic Engineering in IP Network, IEEE Communications, Vol. 37, Dec. 1999.-7 p.

17. Шринивас Вегешна. Качество обслуживания в сетях IP С.П.: Издательский дом "Вильяме",- 2003 - 368 с.

18. D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, X. Xiao. Overview and Principles of Internet Traffic Engineering. Request for Comments: 3272-2002.-71 p.

19. D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus. Requirements for Traffic Engineering Over MPLS. Request for Comments: 2702.-1999-29 p.

20. E. Crawley, R. Nair, B. Rajagopalan, H. Sandick. A Framework for QoS-based Routing in the Internet. Request for Comments: 2386 1998 - 37 p.

21. J. Moy. OSPF Version 2. Request for Comments: 2328.-1998.- 244 p.

22. J. Moy. OSPF Standardization Report. Request for Comments: 2329.-1998-9 p.

23. Томас M. Томас II., Структура и реализация сетей на основе протокола

24. OSPF. 2-ое изд.- С.П.: Вильямс.-2004.- 816 с.91

25. Пакет К., Тир Д. Создание масштабируемых сетей Cisco С.П.: Издательский дом "Вильяме".- 2002 - 792 с.

26. I. Widjaja, I. Saniee, A. Elwalid, and D. Mitra. Online Traffic Engineering with Design-based Routing, ITC Specialist Workshop, Wurzburg-2002-10 p.26. www.opnet.com27. www.wandl.com

27. P. Aukia, M. Kodialam, P. V. Koppol, Т. V. Lakshman, H. Sarin, B. Suter. RATES: A Server for MPLS Traffic Engineering. IEEE Network, vol. 14, no. 2- Mar./Apr. 2000.-10 p.

28. J. Boyle, R. Cohen, D. Durham, S. Herzog, R. Rajan, and A. Sastry. "The COPS (common open policy service) protocol," Internet Draft, Internet Engineering Task Force Feb. 1999.-38 p.

29. M. Kodialam and Т. V. Lakshman, "Minimum interference routing withapplications to MPLS traffic engineering," in Proceedings of the Conference on Computer Communications (IEEE Infocom).- Mar. 2000.-10 p.

30. G.B. Figueiredo, N.L.S. da Fonseca, J.A.S. Monteiro. A Minimum1.terference Routing Algorithm. Technical Report 1С—03-014—2003 —12 p.

31. B.W.X. Su, C.P. Chen, "A new bandwidth guaranteed routing algorithm for

32. MPLS traffic engineering", Proceeding of IEEE International Conference on Communications April, 2002.-10 p.

33. S. Suri, M. Waldvogel, P. Warkhede. Profile-based routing: A newframework for MPLS traffic engineering. Washington University Computer Science Technical Report WUCS-00-21.- July, 2001.-11 p.

34. A.Elwalid, C. Jin, S. Low, I. Widjaja. MATE: MPLS adaptive trafficengineering. Proc. of IEEE INFOCOM'2001.- 2001.-10 p.

35. Eric Osborne, Ajay Simha. Traffic Engineering with MPLS Cisco Press2002.- 608 p.

36. Попков В.К. Математические модели связности 4.2 Гиперграфы игиперсети.- Новосибирск: Изд. ИВМиМГ СО РАН 2001.- 180 с.

37. Опарин Г.А., Богданова В.Г., Новопашин А.П., Максимович В.В.

38. Опарин Г.А., Богданова В.Г., Новопашин А.П., Максимович В.В.

39. Фиксированная маршрутизация в магистральных сетях передачи данных: булевы модели генерации множества туннельных маршрутов и узла-источника в узел-адресат. //Вестник ТГУ. Приложение -2006-№17. С. 170-175.

40. Лорьер Ж.-Л. Системы искусственного интеллекта: Пер. с франц.-М.:1. Мир.- 1991.-586 с.

41. Яхно Т.М. Программирование в ограничениях: обзоры и классификацияподходов и методов. Системная информатика: Сб. научн. тр-Новосибирск: Наука, 1995-Вып. 4: Методы теоретического и системного программирования С. 160 - 192.

42. Dechter R., Pearl J. Tree Clustering for Constraint Network // Arificial1.telligence.- 1989.- Vol.38.-P. 353-366.

43. Freuder E. Synthesizing Constraint Expressions // Comm. of the ACM, 19781. V.21.-№ 11.-P. 958-966.

44. Dechter R., Pearl J. Network-based heuristics for constraint-satisfactionproblems //Artifical Intelligence.-1998.-V.34.-№1.-P. 1-38.

45. Bitner J.R., Reingold E.M. Blacktrack programming techniques // Commun.

46. ACM.-l 975.-V. 18.-P.651-656.

47. Montanari U. Networks of constraints: Fundamental properties andapplications to picture processing // Information Science, 1974- V.7.-№66-P.95-132.

48. Mackworth A.K. Consistency in networks of relations // Artifical1.telligence.- 1977.-V.8.-№1.-P.99-118.

49. Freuder E. A sufficient condition of backtrack-free search // J.ACM 19821. V.29.-№1 -P.24-32.

50. Mohr R., Henderson T. Arc-consistency and path-consistency revisited //

51. Artificial Intelligence.- 1986.-№28.-P.325-330.

52. Deville Y., Van Hentenryc P. An Efficient Arc Consistency Algorithm for a

53. Class of CSP Problems // Proc. IJCAI.-1991.-P.325-330.

54. Bessiere C. Arc-consistency and arc-consistency again // Artifical1.telligence.- 1994,- №65.-P. 179-190.

55. Bessiere C., Freuder E.C., Regin J.-C. Using inference to reduce arcconsistency computation // Proc. 14th IJCAI.-1996.-V.1.-P.592-598.

56. Haralick R.M., Elliot G.L. Increasing tree search efficiency for constraintsatisfaction problem // Artificial Intelligence.-l980.-№14.-P.263-313.

57. McGregor J.J. Relational consistency algorithms and their applications topicture processing // Infotrom. Sci.-1979.-V.19.-P.229-250.

58. Tsang E. Foundations of Constraint Satisfaction // Academic Press.-1993.-201. P

59. Zsofia Ruttkay. Constraint Satisfaction a Survey / CWI Quarterly .-19981. V. 1 .-№2-3 -P. 123-161.

60. Decther R., Rossi F. Constraint Satisfaction. Survey ECS.-March.-2000.-151. P

61. Dechter R., Pearl J. Network-based heuristics for constraint-satisfaction problems // Artifical Intelligence.-1998.-V.34.-№l.-P.l-38.

62. Dechter R. Enhancement schemes for constraint processing: backjumping,learning, and cutest decomposition // Artificial Intelligence -1990 -V.41-№3-P.273-312.

63. Roberto J. Bayardo, Daniel P. Miranker. An optimal backtrack algorithm fortree-structured constraint satisfaction problems // Artificial Intelligence .-1994.-№71 -P. 159-181.

64. Van Hentenryck P. Constraint Satisfaction in Logic Programming // Logic

65. Progr. Series, MIT Press-Cambridge, MA.-1989.

66. Kondrak G., Van Beek P. A theoretical evalution of selected backtrackingalgorithms // Artifical Intelligence.- 1997.-V.98.-№(l-2)-P.365-387.

67. Gasching J. A general backtracking algorithm that eliminates most redundanttests I I Proceedings IJCAI-77.-Cambridge,MA.-1977.-P.457.

68. Haralick R.M., Elliot G.L. Increasing tree search efficiency for constraintsatisfaction problem // Artificial Intelligence.-V.14- 1980-P.263-313.

69. MCGregor J.J. Relational consistency algorithms and their applications topicture processing // Infortorm. Sci.-№19.-1979.-P.229-250.

70. Горшков С.П. Применение теория NP-полных задач для оценкисложности решения систем булевых уравнений // Обозрение прикладной и промышленной математики.Серия дискретной математики.- Т.2.-Вып.З.-1995.- С. 325-398.

71. Prosser P. Hybrid algorithms for the constraints satisfaction problem //

72. Comput. Intell.-l 990.-P. 17-24.

73. Опарин Г.А., Богданова В.Г. Технология булева моделирования дискретных задач в инструментальном комплексе РЕБУС. Моделирование. Теория, методы и средства. Материалы V Межд. Научн.-практ. конф-Новочеркасск: ЮРГТУ-2005-Ч. 1-С. 18-22.

74. Опарин Г.А., Новопашин А.П. Булево моделирование планирования действий в распределенных вычислительных системах. Известия РАН. Теория и системы управления - 2004 - N.S.- С.105-108.

75. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1973- 386 с.

76. Опарин Г.А., Максимович В.В. Управление маршрутизацией вмагистральных сетях передачи данных с использованием технологии MPLS. Информационные системы контроля и управления в промышленности и на транспорте. Моделирование систем управления:

77. Сб. науч. трудов / Под ред. С.Н. Васильева, Ю.Ф. Мухопада- Иркутск: Изд-во ИрГУПС, 2006.- Вып. 14.- С. 22-29.75. http://netacad.kiev.ua/flowc.76. www.netams.com.

78. MySQL Administrator's Guide.- Sams Publishing 2004 - 400 p.

79. MySQL Certification Study Guide Sams Publishing.- 2004 - 648 p.

80. X.M. Дейтел, П.Дж. Дейтел, T.P. Нието, Д.К. МакФай., Какпрограммировать на Perl М.:ЗАО "Издательство БИНОМ".- 2002 г-1088 с.80. http://search.cpan.org/~ehood/Proc-Daemon-0.03/Daemon.pm.81. http://www.freepascal.org.82. http://www.freepascal.ru.

81. М. Бен-ари. Языки программирования. Практический сравнительныйанализ. М.: Издательство "Мир",- 2000 г.- 336 с.84. http://search.cpan.org/~irogers/Net-Telnet-3.03/lib/Net/Telnet.pm.85. http://search.cpan.org/~ioshua/Net-Telnet-Cisco-l.10/Cisco.pm

82. Cisco Systems. Руководство по технологиям объединенных сетей, 3-еиздание С.П.: Издательский дом "Вильямс".-.2002.- 1040 с.

83. В. Боллапрагада, К. Мэрфи, Р. Уайт. Структура операционной системы

84. Cisco IOS С.П.: Издательский дом "Вильяме" .- 2002 - 200 с.88. http://www.cisco.com.89. www.openview.hp.com.90. http://www.splintered.net/sw/flow-tools/.91. http://www.mindrot.org/softflowd.html.