Инвариантные методы анализа трафика в распределенных системах обработки информации тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Гаипов, Константин Эдуардович

• Гаипов, Константин Эдуардович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Гаипов, Константин Эдуардович

Оглавление

Введение

Глава 1. Протоколы и методы управления трафиком в IP/MPLS сетях

1.1 Маршрутизация в сетях на базе протокола IP

1.2 Динамическая маршрутизация в сетях IP на базе протокола OSPF

1.3 Динамическая маршрутизация в сетях IP на базе протокола BGP

1.3.1 Применение протокола BGP для инжиниринга трафика

1.4 Технологии MPLS и GMPLS

1.5 Методы обеспечения механизмов QoS в сетях IP

1.6 Архитектура интегрированного обслуживания

1.7 Архитектура дифференцированного обслуживания

1.8 Алгоритм Token Bucket

1.9 Механизмы борьбы с перегрузками в узлах сети

1.10 Дисциплины обслуживания очередей

1.11 Методы анализа сетей

1.11.1 Анализ сложных систем с помощью тензорного подхода

Вывод

Глава 2. Применение тензорного анализа для распределенных систем обработки информации

2.1 Типы сетей и базисы

2.1.1 Ортогональные сети

2.1.1.1 Ортогональная сеть с одним истоком и п стоками

2.1.1.2 Ортогональная сеть с N истоками и Мстоками

2.1.2 Узловые и контурные сети

2.2 Узловой метод анализа

2.2.1 Приведение ортогональных сетей к узловому виду

2.3 Контурный метод анализа

2.3.1 Приведение ортогональных сетей к контурному виду

2.4. Методы получения матриц циклов и разрезов

Вывод

Глава 3. Применение тензорного метода для оптимального распределения трафика

3.1 Применение контурного метода анализа для оптимизации трафика в СеМО

3.2 Применение узлового метода анализа для оптимизации трафика в СеМО

3.3 Применение метода линейно-независимых цепей для оптимизации трафика в СеМО

3.4 Применение тензорного анализа для оптимизации СеМО с произвольным числом входов и выходов

3.5 Применение узлового метода для оптимизации и анализа СеМО с произвольным числом входов и выходов

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

3.7 Применение метода линейно-независимых цепей для оптимизации и анализа СеМО с произвольным числом входов и выходов

3.8 Применение тензорного метода для определения линейной целевой функции

3.9 Физическое моделирование

Вывод

Глава 4. Применение тензорного метода для инжиниринга трафика в сетях на базе стека протоколов TCP/IP

4.1 Особенности распределения трафика в пакетных сетях

4.2 Применение тензорного метода в сетях IP на базе протокола OSPF

4.3 Применение тензорного метода для учета потерь при обслуживании

4.4 Применение тензорного метода для анализа протоколов HDLC и TCP

4.5 Применение тензорного метода для анализа трафика в мультисервисных сетях

Вывод

Заключение

Список сокращений

Список литературы

Введение диссертации (часть автореферата) на тему «Инвариантные методы анализа трафика в распределенных системах обработки информации»

Введение

Актуальность темы

На современном этапе технологического и социального развития общества и наряду с процессами всеобщей глобализации обработка и передача информации между различными подсистемами становится неотъемлемой частью любого сложного процесса или системы. Наряду с множеством механизмов качества обслуживания и различной природой трафика, создаваемого различного рода приложениями, совместно с протоколами формирования маршрутов в пакетных сетях, делают анализ и управление современными пакетными сетями обработки информации достаточно сложной задачей. Решению проблем, связанных с планированием трафика, посвящено большое количество работ как зарубежных, так и российских авторов: Д. Бертсекас, Р. Галлагер, Л. Клейнрок, Л. Форд, Д. Фалькернсон, Э. Майника, В.М. Вишневский, Е.А. Кучерявый, Г. Г. Яновский, А. В. Росляков, Г. П. Башарин и др.

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

систем обработки информации на основе матричной алгебры. Значительный вклад в развитие тензорного анализа сложных систем внесли работы Г. Крона, М.Н. Петрова, А.Е. Петрова, A.B. Лемешко и др.

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

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

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

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

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

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

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

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

Научная новизна

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

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

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

Практическая значимость работы

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

Методы исследования

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

Основные положения, выносимые на защиту

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

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

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

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

Апробация результатов

Основное содержание работы докладывалось и обсуждалось на научно-технической конференции «Инновации в условиях развития информационно-коммуникационных технологий» (Москва, 2007), VI всероссийской научно-практической конференции «Современные информационные технологии в науке, образовании и практике» (Оренбург 2007), научно-технической конференции «Современные проблемы радиоэлектроники» (Красноярск 2008, 2009, 2010, 2011, 2013), XI Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения» (Пенза 2009), международной научно-технической конференции «Современные информационные технологии» (Пенза 2009).

Глава 1. Протоколы и методы управления трафиком в IP/MPLS сетях

1.1 Маршрутизация в сетях на базе протокола IP

Протокол IP (Internet Protocol - протокол межсетевого взаимодействия) описанный в [1-11], один из основных протоколов межсетевого взаимодействия, который широко используется для маршрутизации трафика, как в локальных, так и глобальных сетях. Основным устройством в сетях IP являются устройства третьего уровня, такие как: маршрутизаторы и многоуровневые коммутаторы.

Правила распределения трафика (маршрутизация) записаны в таблицах маршрутизации, данное правило можно сформулировать, следующим образом: на IP адрес назначения, находящийся в заголовке пакета IP, накладываются маски сетей, записанных в таблице маршрутизации, в результате наложения маски сети на IP адрес получателя, получается префикс сети назначения, которому соответствует определенный выходной интерфейс маршрутизатора или IP адрес следующего транзитного перехода. В случае если в таблице маршрутизации после наложения маски на IP адрес получателя два и более префикса, то адрес следующего перехода выбирается тот, которому соответствует более длинная маска. Основным достоинством IP адресации является ее иерархичность, что позволяет сокращать маршрутные записи в маршрутизаторах, на основе записей CIDR (classless interdomain routing - бесклассовая междоменная маршрутизация).

Маршрутизация в сети Internet основана, как на статических маршрутных записях, так и на основе динамически составляемых маршрутных записей, с помощью протоколов маршрутизации. Статическая маршрутизация применяется в небольших сетях, где все маршрутные записи можно указать вручную. Динамическая маршрутизация применяется там, где ручная настройка затруднительна. При этом динамическую маршрутизацию классифицируют, как маршрутизацию внутри автономной системы (Interior Gateway Protocol (ЮР) -протоколы внутреннего шлюза) и маршрутизацию между автономными системами (Exterior Gateway Protocol (EGP)). Основной интерес из протоколов

серии ЮР представляет собой протокол OSPF (Open Shortest Path First -наикратчайший маршрут выбирается первым) [12,13], а из протоколов EGP -BGPv4 (Border Gateway Protocol version 4 - протокол граничного шлюза версии 4) [14,15]. Таким образом, маршрутизация в сети Internet является двухуровневой, вначале происходит поиск наикратчайшего маршрута между маршрутизаторами внутри автономной системы до граничного маршрутизатора, а затем происходит поиск оптимального маршрута между автономными системами. Выбор именно этих двух протоколов обусловлен тем, что они рекомендованы комитетом IETF (Internet Engineering Task Force - инженерная группа по развитию интернета) [16], как основные протоколы маршрутизации в сети Internet.

1.2 Динамическая маршрутизация в сетях IP на базе протокола OSPF

Протокол OSPF один из самых распространенных протоколов внутреннего шлюза в сети Internet. Основная версия протокола, получившая наибольшее распространение в сетях IP, описана в рекомендации [12]. В качестве алгоритма поиска наикратчайшего маршрута, принят алгоритм Дейкстры, а в качестве метрик приняты значения обратные пропускной способности, согласно RFC 2328

о

метрика определяется как отношение 10 к пропускной способности канала связи.

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

Стандартная область - все остальные области называются стандартными. С целью сокращения рассылки анонсов, и как следствие уменьшение нагрузки на процессор маршрутизатора, рекомендуемая топология для протокола OSPF имеет вид «ромашки», состоящая из опорной области в центре и тупиковых областей, соединенных с опорной областью [12,13].

Также спецификация протокола OSPF определяет несколько типов маршрутизаторов: граничный маршрутизатор области (ABR - Area Border Router), данный маршрутизатор находится на границе двух и более областей и имеет интерфейсы в каждой области; граничный маршрутизатор автономной системы (ASBR - Autonomous System Border Router) - данный тип маршрутизаторов объединяет одну из областей OSPF с другой автономной системой или с областью, где функционирует другой протокол маршрутизации.

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

Дальнейшее развитие протокол OSPF получил в рекомендации 2676 [17], эта рекомендация носит экспериментальный характер, но в ней определен новый

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

Помимо стандартизирующих документов существует множество статей по улучшению времени сходимости протокола ОБРЕ, выбора метрики и алгоритма поиска кратчайшего пути.

При планировании сети на базе протокола ОЗРБ, возникает две основные проблемы - это уменьшение количества анонсируемых сетей за счет агрегации маршрутов, и распределение метрик таким образом, чтобы ресурсы сети использовались эффективно.

При агрегации маршрутов происходит объединение 1Р адресов сетей с общим префиксом в единое адресное пространство. Такое объединение совместно с принципом пошаговой маршрутизации значительно сокращает объем таблицы маршрутизации, в случае если всего один канал ведет сразу к нескольким сетям, которые в таблице маршрутизатора можно представить агрегированной записью. Суть проблемы заключается в том, что на маршрутизаторах АВЯ, как правило, настраиваются агрегационные маршруты, которые объединяют сети находящиеся за АВЯ, с целью уменьшить количество записей в таблице маршрутизации и уменьшить время конвергенции протокола. В случае если две области 08РБ соединены двумя и более маршрутизаторами АВЯ, на которых настроены агрегационные записи, то в зависимости от выбранного правила агрегации и метрики, которая присваивается этой агрегационной записи, трафик может пойти не по оптимальному маршруту.

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

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

- обобщенная задача выбора метрик: для агрегационных адресов хеА вычислить функцию назначения метрик W{x} такую, что

была минимальной,

где

s, t- подсеть отправитель и получатель соответственно;

S - набор всех подсетей в автономной системе;

А - набор агрегационных маршрутов имеющих право на анонсирование;

А,- - набор агрегационных маршрутов имеющих право на анонсирование маршрутизатором i;

х - общий анонсируемый агрегационный адрес;

Х- Общие наборы анонсируемых агрегационных адресов;

D(s,t) - степень важности пары подсетей источник-приемник (s,t);

Wx ~ функция назначения метрик для набора агрегированных адресов

Isp (s,t) - длина наикратчайшего пути между парой (s,t);

Isp (s, t, X, Wx) - длина наикратчайшего пути между подсетями 5 и /, где агрегированные адресах анонсируются с весами Wx.

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

Рассмотрим, как распределяются потоки трафика в сетях, на базе протоколов, работающих по алгоритму Дейкстры, к которым относится, как OSPF, так и IS-IS. Представим сеть в виде направленного графа G=(N,A), где узлы N и ребра графа А представляют маршрутизаторы и каналы между ними соответственно. Каждое ребро графа имеет пропускную способность с,у. Наикратчайшим маршрутом считается такой, маршрут от узла и до узла v, чья сумма метрик будет минимальна.

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

'II ^

Ср

'1т

с =

"2т

'«1 С«2

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

Введем матрицу запросов Б, элементы <1иу, которой показывают скорость передачи от сети и к сети V.

4.

£> = <4 ¿/22 ■ ¿ги

<1 4.2 '

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

^11 ^12 '" Ьт

£ _ ^21 ^22 ^2 т

"' ^пт

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

канала было минимально, но при этом как отмечено .в [22,23] алгоритмы поиска наикратчайшего пути накладывают ряд ограничений. Ограничения заключаются в том, что поток, который проходит по наикратчайшему маршруту, во-первых, не может быть разделен на несколько альтернативных маршрутов между парой источник-приемник, во-вторых, если маршрут от маршрутизатора i до маршрутизатора v включает канал (s,t) и если маршрут от и к v проходит через маршрутизатор /, он так же должен включать и канал (s,t). Ряд статей [24-26] для решения такой задачи предлагают нахождения наборов метрик с помощью генетических алгоритмов [27,28]. Авторы других статей предлагают различные эвристические алгоритмы для решения оптимального распределения метрик [2933]

1.3 Динамическая маршрутизация в сетях IP на базе протокола BGP

Протокол BGP, описание которого дано в рекомендации RFC 4271. В отличие от протокола OSPF BGP является протоколом внешнего шлюза. Т.е. протокол BGP обменивается информацией не о достижимости сетей, а о достижимости автономных систем и их агрегационных IP сетей, которые содержатся в данной автономной системе, то есть, протоколом BGP на основе информации, полученной от различных маршрутизаторов, строится граф автономных систем со всеми связями между узлами. Протокол BGP по умолчанию работает, как дистанционно векторный протокол, основываясь на значениях атрибута AS PATH. Метрикой является количество транзитных автономных систем. На самом же деле маршрутизация между автономными системами определяется политикой интернет провайдеров, которые решают, как должен передаваться трафик.

Идеология маршрутизации BGP основана на трех информационных базах данных о маршрутизации (RIB - Routing Information Base).

Adj-RIB-In - в этой базе содержится информация из входящих сообщений UPDATE других BGP маршрутизаторов, в терминологии протокола BGP такие

машрутизаторы называется спикерами. В этой базе содержатся все известные маршруты к другим граничным маршрутизаторам. Local-RIB - в этой базе данных содержится информация, которую будет использовать маршрутизатор для пересылки пакетов, данная база получается в результате применения локальной политики на базу Adj-RIB-In. Данная база является таблицей маршрутизации, используемая для пересылки пакетов. Adj-RIB-Out - в этой базе данных BGP спикер содержит ту маршрутную информацию, которую он будет анонсировать своим соседним спикерам. Информация в этой базе также получается в результате наложения определенной политики на базы Adj-RIB-In и Local-RIB.

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

В документе [14] определено семь атрибутов маршрута: ORIGIN, AS РАТН, NEXTHOP, MULTI EXIT DISC, LOCAL PREF,

ATOMIC AGGREGATE, AGGREGATOR. Помимо этого в документах [95-98] приведены еще шесть опциональных нетранзитивных атрибутов. Все атрибуты передаются в сообщении UPDATE.

Данные атрибуты делятся на четыре категории: общеизвестные обязательные (Well-known mandatory), общеизвестные предоставленные на собственное усмотрение (Well-known discretionary), опциональные транзитивные (Optional transitive), опциональные не транзитивные (Optional non-transitive)

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

1. Если ближайший следующий узел недоступен, то маршрут игнорируется. (Поэтому важно всегда иметь IGP-маршрут на ближайший соседний узел).

2. Предпочитается маршрут с наибольшим значением коэффициента предпочтения.

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

5. Если длина AS_PATH у маршрутов совпадает, то следует выбрать маршрут с наименьшим значением атрибута типа протокола ORIGIN, наиболее предпочитаемым маршрутом будет тот, который имеет значение атрибута ORIGIN равное IGP, затем EGP и наименее предпочитаемый маршрут имеет значение INCOMPLETE.

6. Если атрибуты типов протокола также совпадают, то следует выбрать маршрут с наименьшим значением атрибута MED, если маршруты были приняты от одной и той же AS.

7. Если у маршрутов равные значения MED, то eBGP-маршрутам следует предпочесть iBGP-маршруты.

8. Если во всех предыдущих случаях получены совпадения, то следует предпочесть маршрут, который пролегает через ближайшего соседа по IGP, т.е. предлагается избрать кратчайший путь к удаленному узлу внутри AS. (Следовать кратчайшему пути до узла, указанного в NEXT HOP).

9. Если и внутренние маршруты окажутся одинаковыми, то для решения этой за дачи следует использовать атрибут ROUTER ID. В этом случае следует предпочесть маршрут, полученный от маршрутизатора BGP, с наименьшим значением RID.

1.3.1 Применение протокола BGP для инжиниринга трафика

Основными методами инжиниринга трафика с помощью протокол BGP является назначение атрибутов анонсируемым маршрутам. Основными атрибутами для управления трафиком являются LOCALPREF, MED, AS PATH.

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

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

Аналогичный способ для выбора предпочтительного маршрута можно организовать, используя атрибут ASPATH. Предпочтение отдается тому маршруту, который был анонсирован с меньшим числом транзитных автономных систем. При анонсировании маршрута спикером автономной системы можно указать в наборе AS SET несколько произвольных автономных систем, как правило, провайдеры указывают собственные номера автономных систем, таким образом, искусственно удлиняя AS SET дублированием номеров своей же автономной системы. Исследованию вопросов посвященных инжинирингу трафика с помощью атрибутов BGP посвящены работы [35-39].

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

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

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

1.4 Технологии MPLS и GMPLS

Архитектура сети MPLS (Multiprotocol Label Switching - многопротокольная коммутация по меткам) описана в [41-44], согласно документу [41] основными элементами технологии MPLS являются граничные (LER - Label Edge Router) и транзитные (LSR - Label Switch Router) маршрутизаторы коммутирующие по меткам.

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

Список литературы диссертационного исследования кандидат наук Гаипов, Константин Эдуардович, 2013 год

Список литературы

1. Internet Protocol RFC 791. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc791 .txt.

2. Девис Джозеф, Ли Томас. Microsoft Windows Server 2003. Протоколы и службы TCP/IP. Техническое руководство. Серия «Справочник профессионала» / Пер. с англ. - М.: «СП ЭКОМ», 2005 -72 е.; ил.

3. К. Щербо. Стандарты вычислительных сетей. Взаимосвязи сетей. Справочник - М.:КУДИЦ - ОБРАЗ, 2000 -272с.

4. Мельников Д.А. Информационные процессы в компьютерных сетях. Протоколы, стандарты, интерфейсы модели... - М.:КУДИЦ - ОБРАЗ, 2000. -256 е., ил. - (Библиотека профессионала).

5. Аппаратные средства локальных сетей. Энциклопедия / М. Гук, - СПб.: Питер, 2004. - 573.: ил.

6. Компьютерные сети. Практика построения. Для профессионалов. 2-е изд. / М.В. Кульгин. - СПб.: Питер, 2003. - 462.: ил.

7. Димарцио Д.Ф. маршрутизаторы Cisco. Пособие для самостоятельного изучения. - пер. с англ. - СПб: Символ-Плюс, 2005. - 512с., ил.

8. Хилл Брайан. Полный справочник по Cisco.: Пер с англ. - М.: Издательский дом «Вильяме», 2006. - 1088 е.: ил. - Парал. тит. англ.

9. Программа сетевой академии Cisco CCNA 1 и 2. Вспомогательное руководство, 3-е изд, с испр.: Пер с англ. - М.: Издательский дом «Вильяме», 2006. - 1168 е.: ил. - Парал. тит. англ.

10. Руководство по технологиям объединенных сетей, 4-е издание.: Пер. с англ. М.: Издательский дом "Вильяме", 2005. - 1040 с. : ил. - Парал. тит. англ.

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

12. OSPF Version 2 RFC 2328. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc2328.txt.

13. Томас, Том М. II. Структура и реализация сетей на основе протокола OSPF, 2-е изд.: Пер. с англ. М.: Издательский дом "Вильяме", 2004. - 816 с. : ил. -Парал. тит. англ.

14. A Border Gateway Protocol 4 (BGP-4) RFC 4271. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc4271.txt.

15. Принципы маршрутизации в Internet, 2-е издание.: Пер. с англ. М. : Издательский дом "Вильяме", 2001. - 448 с. : ил. - Парал. тит. англ.

16. The Internet Engineering Task Force. [Электронный ресурс]. Режим доступа: http://www.ietf.org.

17. QoS Routing Mechanisms and OSPF Extensions RFC 2676. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc2676.txt.

18. OSPF Extensions in Support of Generalized Multi-Protocol Label Switching (GMPLS) RFC 4203. [Электронный ресурс]. Режим доступа: http:// www. ietf. org/rfc/rfc4203 .txt.

19. OSPF-xTE: Experimental Extension to OSPF for Traffic Engineering RFC 4973. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc4973.txt.

20. Yuri Breitbart, Minos Garofalakis, Amit Kumar, Rajeev Rastogi. Optimal Configuration of OSPF Aggregates. [Электронный ресурс]. Режим доступа: http://www.ieee-infocom.org/2002/papers/324.pdf.

21. Гудман, С. Введение в разработку и анализ алгоритмов / Гудман, С., Хидетниеми, С. -М.: Мир, 1981. 368 с.

22. Dirk Staehle, Ute Kohlhaas, Stefan Kohler. Towards an optimization of the routing parameters for IP networks. [Электронный ресурс]. Режим доступа: http://www-info3. informatik.uni - wuerzburg. de/TR/tr25 8 .p df.

23. L.T.M. Berry, Ltm Berry, S. Kohler, D Staehle, P Tran-gia.Fast heuristics for optimal routing in large IP networks. [Электронный ресурс]. Режим доступа: http://www-info3.informatik.uni-wuerzburg.de/TR/tr262.pdf.

24. Luciana S. Buriol, Mauricio G. C. Resende, Celso C. Ribeiro, Mikkel, Luciana S.A Memetic Algorithm for OSPF Routing. [Электронный ресурс]. Режим доступа: http://www.research.att.com/~mgcr/doc/memetic-ospf-routing.pdf.

25. Eueung Mulyana, Ulrich Killat. Hybrid Genetic Algorithm Approach For OSPF Weight Setting Problem. [Электронный ресурс]. Режим доступа: http://www.tu-harburg.de/et6/papers/documents/Mulyana_Eueueng/PGTS2002-mulyana.pdf.

26. М. Ericsson , М. G. С. Resende , P. М. Pardalos. A genetic algorithm for the weight setting problem in ospf routing. [Электронный ресурс]. Режим доступа: http://www.research.att.com/~mgcr/doc/hgaospf.pdf.

27. Рутковская Д., Пилиньский М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы: пер. с польск. И.Д. Рудинского. - М.: Горячая линия - Телеком, 2006. - 452 е.: ил.

28. Bilal Gonen. Genetic Algorithm Finding the Shortest Path in Networks. [Электронный ресурс]. Режим доступа: http://www.bilalgonen.com/courses/cs776/project/CS776_semester_project_Bilal_ Gonen.pdf.

29. Bernard Fortz. Internet Traffic Engineering by Optimizing OSPF Weights. [Электронный ресурс]. Режим доступа: http://www.cs.utexas.edu/~yzhang/teaching/cs386m-s8/Readings/ospf.pdf.

30. Matthew Roughan, Mikkel Thorup, Yin Zhang. Traffic Engineering with Estimated Traffic Matrices. [Электронный ресурс]. Режим доступа: http://www.icir.org/vern/imc-2003/papers/p307-roughanl.pdf.

31. Riikka Susitaival, Samuli Aalto. Adaptive load balancing with OSPF. [Электронный ресурс]. Режим доступа: http://lib.tkk.fi/diss/2007/isbn9789512288311/article5.pdf.

32. Luciana S. Buriol, Mauricio G. C. Resende, Celso C., Ribeiro, Mikkel Thorup. A Memetic Algorithm for OSPF Routing. [Электронный ресурс]. Режим доступа: http://www.informs.org/Conf/Telecom02/Abstracts/Buriol01351173414.pdf.

33. Bernard Fortz , Jennifer Rexford , Mikkel Thorup. Traffic Engineering With Traditional IP Routing Protocols. . [Электронный ресурс]. Режим доступа: http://www.cs.princeton.edu/~jrex/teaching/spring2005/reading/fortz02.pdf.

34. Exterior Gateway Protocol Formal Specification RFC 904. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc904.txt.

35. Nick Feamster, Jennifer Rexford. Network-Wide BGP Route Prediction for Traffic Engineering. . [Электронный ресурс]. Режим доступа: http://nms.Ics.mit.edu/~feamster/papers/itcom2002.ps.gz.

36. Nick Feamster, Hari Balakrishnan, Jennifer Rexford, Aman Shaikh, Jacobus Van Der Merwe. The Case for Separating Routing from Routers. [Электронный ресурс]. Режим доступа: http://nms.lcs.mit.edu/~feamster/papers/rcp-fdna04.ps.gz.

37. Nick Feamster, Jared Winick, Jennifer Rexford. A Model of BGP Routing for Network Engineering. [Электронный ресурс]. Режим доступа: http://www.research.att.com/~jrex/papers/whatifatron.pdf.

38. Priyadarsi Nanda , Andrew James Simmonds. Effect of network policies on internet traffic engineering. [Электронный ресурс]. Режим доступа: http://www-staff.it.uts.edu.au/~simmonds/Papers/AACC05_paperl5_policy.pdf.

39. Bruno Quoitin , Steve Uhlig , Cristel Pelsser , C. Pelsser , Louis Swinnen , Olivier Bonaventure. Interdomain traffic engineering with BGP. [Электронный ресурс]. Режим доступа: http://www.info.ucl.ac.be/people/OBO/papers/commag-may2003.pdf.

40. Zhuoqing Мао, Zhuoqing Мао, Zhuoqing Мао. Solving the Interdomain Routing Puzzle - Understanding Interdomain Routing Dynamics. [Электронный ресурс]. Режим доступа: http://sahara.cs.berkeley.edu/papers/ZM03.pdf.

41. Multiprotocol Label Switching Architecture RFC3031. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc3031 .txt.

42. MPLS Label Stack Encoding RFC 3032. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc3032.txt.

43. Гольдштейн А.Б., Тольдштейн Б.С. Технология и протоколы MPLS. СПб.: БХВ - Санкт-Петербург, 2005. - 304с.: ил.

44. Структура и реализация современной технологии MPLS.: Пер. с англ. М.: Издательский дом "Вильяме", 2004. - 480 с. : ил. - Парал. тит. англ.

45. RFC 3471. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc3471 .txt.

46. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.:Техносфера, 2003. - 512 с.

47. Росляков A.B. Виртуальные частные сети. Основы построения и применения.

- М.: Эко-Трендз, 2006. - 304с.: ил.

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

- 544с., ил.

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

50. Дэвис Джонатан, Питере Джеймс, Бхатия Манож, Калиндииди Сатиш, Мукхержи Судипто. Основы передачи голосовых данных по сетям IP, 2-е изд.: Пер. с англ. - М.: ООО «ИД. Вильяме», 2007. - 400 е.: ил. - Парал. тит. англ.

51. Мак-Квери Стив, Мак-Грю Келли, Фой Стефан. Передача голосовых данных по сетям Cisco Frame Relay, ATM и IP.: Пер. с англ. - М.: ООО Издательский дом «Вильяме», 2007. - 512 е.: ил. - Парал. тит. англ.

52. A.B. Росляков, М.Ю. Самсонов, И.В. Шибаева. IP-телефония. - М.: Эко-Трендз, 2003. 252 е.: ил.

53. Resource ReSerVation Protocol (RSVP) RFC 2205. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc2205.txt.

54. Кучерявый Е.А. Управление трафиком и качество обслуживания в сети Интернет. - СПб.: Наука и техника, 2004. - 336с.: ил.

55. Sally Floyd, Van Jacobson. Random Early Detection Gateways for Congestion Avoidance. [Электронный ресурс]. Режим доступа: http://www.icir.org/floyd/papers/early.twocolumn.pdf.

56. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. - М.: Мир, 1981.-323 е., ил.

57. Клейнрок Л. Коммуникационные сети (стохастические потоки и задержки сообщений). - М.: Наука, 1970. - 256с.

58. Лузин H.H. Дифференциальное исчисление. М.: Высшая школа. 1960. -478 с.

59. Победря Б.Е. Лекции по тензорному анализу: Учеб. Пособие. - 3-е изд. М.: Изд-во Моск. ун-та, 1986. -264с.

60. Тензорное исчисление. Акивис М.А., Гольдберг В.В., Изд-во «Наука», Главная редакция физико-математической литературы, 1969 г.

61. P.A. Шарипов. Быстрое введение в тензорный анализ. [Электронный ресурс]. Режим доступа: http://techlibrary.rU/b/3glalrljlqlplc_2y.2h._2i2clsltlrlplf_lclclflelfloljlf_ lc_ltlflolilplrlo2clk_lalolalmljli._2004.pdf.

62. Крон Г. Тензорный анализ сетей. М.: Сов. радио, 1978.

63. Петров А.Е. Тензорный метод двойственных сетей. - М.: ООО «Центр информационных технологий в природопользовании» 2007. - 496 е.: ил.

64. Петров М. Н. Веревкина Е. В. Захарченко М.О. Тензорная методология в информационных сетях. Красноярск: НИИ СУВПТ, 2001.

65. Петров М.Н. Вероятностно-временные характеристики в сетях и системах передачи интегральной информации: Научное издание / КГТУ. Красноярск, 1997. 220 с.

66. Пономарев Д.Ю. О подходе к анализу сетей массового обслуживания с использованием тензорной методологии. Труды V Международной конференции «Идентификация систем и задачи управления» SICPRO '06. -М: Институт проблем управления им. В.А. Трапезникова РАН. - 2006. - С. 697-704.

67. Пономарев Д.Ю. Тензорный метод исследования сетей связи. Современные проблемы информатизации в информационных системах и телекоммуникациях / Сборник трудов. Под ред. д.т.н., проф. О.Я.Кравца. -Вып. 11 - Воронеж: Научная книга. - 2006. - С. 443-447.

68. Пономарев Д.Ю. Тензорный метод исследования телекоммуникационных сетей. «Молодежь и современные проблемы радиотехники и телекоммуникаций РТ-2006»: материалы международной научно-технической конференции студентов, аспирантов и ученых. - Севастополь: СевНТУ.-2006.-С. 48.

69. Пономарев Д.Ю. Тензорная методология в телекоммуникациях. Системы управления и информационные технологии. - 2006. - 1.1(23). - С. 161-165.

70. Пономарев Д.Ю. К вопросу тензорного метода анализа информационных сетей. Информационные системы и технологии (IST'2006): третья Международная конференция: материалы - Минск: Академия управления при Президенте Республики Беларусь. - 2006. - Ч. 1. - С.215-218.

71. Пономарев Д.Ю. Тензорный метод для телекоммуникационных сетей. Труды КГТУ. - 2006. - №2-3. - С. 49-56.

72. Пономарев Д.Ю. Об одном методе исследования сетей связи с применением тензорной методологии. Современные проблемы информатизации в проектировании и телекоммуникациях / Сборник трудов. - Вып. 12 -Воронеж: Научная книга. - 2007. - С. 313-317.

73. Пономарев Д.Ю. К вопросу тензорного метода анализа информационных сетей. Кибернетика и высокие технологии XXI века: Материалы VIII Международной научно-технической конференции. - Воронеж: НПФ «Саквоее» ООО. - 2007. - Т.2. - С. 590-595.

74. Пономарев Д.Ю. Исследование возможностей тензорного анализа сетей массового обслуживания. Имитационное моделирование. Теория и практика. / ИММОД-2007: Сборник докладов. - СПб: ЦНИИТС. - 2007. - Т.1. - С. 205209.

75. Пономарев Д.Ю. К вопросу тензорного метода анализа сетей массового обслуживания. Вторая международная конференция «Системный анализ и информационные технологии» САИТ-2007: Труды конференции. - М.: Издательство ЖИ. - 2007. - Т.2. - С. 227-228.

76. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ. - М.: Мир, 1984.-496 е., ил.

77. Форд. Д., Фалкерсон Д. Потоки в сетях: Пер. с англ. - М.: Мир, 1966. - 273 е., ил.

78. Свами М. Тхуласираман К. Графы сети и алгоритмы: Пер. с англ. - М.: Мир, 1984,-455 е., ил.

79. Лемешко А.В. Тензорная модель многопутевой маршрутизации агрегированных потоков с резервированием сетевых ресурсов, представленная в пространстве с кривизной. Пращ УНД1РТ, 2004, № 4

80. V. I. Parfyonov and S. V. Zolotarev. Optimal Selection of Routs in Data Transmission Networks Energy Approach. Radioelectronics and Communications Systems, 2008, Vol. 51, No. 10, pp. 555-564.

81. Васильев Ф.П. Методы оптимизации. - M.: Факториал пресс. 2002. - 824 с.

82. Дж. Хедли. Нелинейное и динамическое программирование. -М.: Мир. 1967. -508с.

83. Штагер В. В. Цифровые системы связи. Теория, расчет и оптимизация. М.: Радио и Связь, 1993. - 312 е.: ил. - 5-256-00626-6.

84. Distributed Internet Traffic Generator. http://www.grid.unina.it/software/ITG/

85. Transmission control protocol RFC 793. [Электронный ресурс]. Режим доступа: http://www.ietf.org/rfc/rfc0793.txt.