ББК 32.88
Б90
Рецензенты: доктор техн. наук, профессор Л. Г. Доросинский;
доктор техн. наук, профессор Б. А. Панченко
Будылдина Н. В., Трибунский Д. С., Шувалов В. П.
Б90 Оптимизация сетей с многопротокольной коммутацией по меткам.
— М.: Горячая линия–Телеком, 2010. — 144 с.: ил.
ISBN 978-5-9912-0124-7.
В монографии рассмотрены основные вопросы многопротокольной коммутации
по меткам, преимущества, проблемы распределения трафика и безопаcности
в сетях MPLS, переход от MPLS к GMPLS, особенности GMPLS.
Особое место в монографии уделено методам оптимизации трафика в сетях
IP/MPLS с дифференцированным обслуживанием и методам распределения
многопродуктовых потоков, а также локализации сбоев, резервированию и
восстановлению для обеспечения живучести в сетях GMPLS. Представлен алгоритм
оптимизации сетей на основе множителей Лагранжа и модель для
определения показателей надежности в сетях GMPLS с защитной коммутацией
(1+1) в условиях недостоверного комбинированного контроля.
Для научных работников, инженеров и разработчиков аппаратуры связи,
студентов старших курсов радиотехнических факультетов вузов, аспирантов.
ББК 32.88
Адрес издательства в Интернет WWW.TECHBOOK.RU
Научное издание
Будылдина Надежда Вениаминовна
Трибунский Дмитрий Сергеевич
Шувалов Вячеслав Петрович
Оптимизация сетей с многопротокольной коммутацией
по меткам
Монография
Редактор Ю. Н. Чернышов
Компьютерная верстка Ю. Н. Чернышова
Обложка художника В. Г. Ситникова
Подписано в печать 05.11.2009. Печать офсетная. Формат 60×88/16.
Уч. изд. л. 9,5. Тираж 1000 экз.
ISBN 978-5-9912-0124-7
⃝ Н. В. Будылдина, Д. С. Трибунский,
В. П. Шувалов, 2010
c
⃝ Оформление издательства
«Горячая линия—Телеком», 2010
c
Стр.2
Введение
Технология многопротокольной коммутации по меткам (MultiProtocol
Label Switching, MPLS) является ведущей технологией, способной
стать фундаментом для инфраструктуры мультисервисных сетей следующего
поколения (NGN), в рамках которых станет возможна передача
любого трафика через единую телекоммуникационную инфраструктуру.
MPLS сочетает в себе гибкость дейтаграммного IP и виртуальных каналов
MPLS с поддержкой трафик-инжиниринга, что открывает принципиально
новые возможности для использования протокола IP в современных
сетях, которые ранее были технически не осуществимы.
Особенностями MPLS-TE являются:
• высокая масштабируемость;
• поддержка QoS;
• универсальность по отношению к протоколам сетевого уровня;
• значительное упрощение процедур маршрутизации;
• универсальность по отношению к транспортным технологиям (ATM,
Ethernet, POS и т.п.).
Применение технологии MPLS позволяет перейти на новый уровень
обслуживания и организовать предоставление услуг более высокого
качества. Особенно перспективным является использование этой технологии
для создания виртуальных частных сетей (VPN) и перехода к
мультисервисным сетям на основе IP.
Основным подходом в маршрутизации в сетях с коммутацией пакетов
вот уже долгое время является выбор маршрута на основе топологии
сети без учета информации о текущей загрузке. Для каждой пары «адрес
источника — адрес назначения» такие протоколы выбирают единственный
маршрут, не принимая во внимание информационные потоки,
протекающие через сеть. В результате все потоки между парами конечных
узлов идут по кратчайшему маршруту (в соответствии с некоторой
метрикой). Выбранный маршрут может быть более рациональным, если,
например, в расчет принимается номинальная пропускная способность
канала связи или вносимые ими задержки, либо менее рациональным,
если учитывается только количество промежуточных маршрутизаторов
между исходным и конечным узлами.
Такой подход приводит к тому, что даже если кратчайший путь перегружен,
пакеты все равно посылаются по этому пути. Налицо явная
ущербность методов распределения ресурсов сети — одни ресурсы работают
с перегрузкой, а другие не используют вовсе. Традиционные
методы борьбы с перегрузками эту проблему решить не могут, нужны
качественно иные механизмы.
Стр.3
4
Введение
С этой целью на сетях связи осуществляется внедрение новых сетевых
технологий, например MPLS, которая обеспечивает гарантированную
среднюю пропускную способность в соответствии с принципами инжиниринга
трафика. Наряду с этим, необходимо предусмотреть, чтобы сети
были спроектированы с учетом необходимых методов оптимизации,
которые позволят провайдерам максимально эффективно использовать
имеющуюся инфраструктуру.
Поэтому для более эффективного использования сетевых ресурсов
важными являются задачи оптимизации выбора алгоритмов маршрутизации,
чтобы обеспечить производительность сети и сбалансировать
нагрузку в случае изменения трафика, без необходимости изменения
структуры сети и повышения емкости каналов.
Поставленная задача оптимизации обычно решается с учетом ограничений
и относится к так называемым задачам NP-complit, т.e. задачам,
решение которых требует больших временных затрат∗. Некоторые
пути уменьшения времени вычислений представлены в первых пяти главах.
В частности, дана содержательная постановка задачи необходимости
построения сетей с использованием технологии MPLS, ее преимущества
и дано сравнение с другими технологиями. Рассмотрены вопросы
управления трафиком и проблемы оптимизации трафика, а также дан
обзор методов оптимизации трафика в сетях IP/MPLS.
Управление потоком передаваемой информации позволяет направлять
потоки данных не по кратчайшему пути, вычисленному с помощью
традиционного протокола маршрутизации, а через менее загруженные
узлы и каналы связи. При правильном моделировании потока и правильном
выборе методов оптимизации процессов нагрузка на все физические
каналы связи, маршрутизаторы и коммутаторы должна быть
сбалансирована таким образом, чтобы ни один из этих компонентов не
был недогружен или перегружен. В результате сеть будет работать более
эффективно, стабильно и предсказуемо.
В первой главе рассматриваются особенности построения сети с
MPLS, отмечены ее достоинства и недостатки, во второй главе обсуждаются
способы управления трафиком в сетях MPLS и представлены
пути совершенствования технологии MPLS, формирование трафика и
обеспечение качества услуг. В третьей главе представлен обзор методов
оптимизации трафика в IP/MPLS-сетях.
В четвертой главе рассмотрены методы распределения многопродуктовых
потоков и существующие подходы к решению задачи определения
оптимального дизайна путей с коммутацией по меткам (Label
∗ Точнее, к недетерминированным полиномиальным задачам (nondeterministic
polynomial time problem, NP). Это задачи, которые можно решить на машине Тьюринга
за время, полиномиально зависящее от числа переменных. К таким задачам
относятся, например, поиск пути на графе или классическая задача о комивояжере.
— Прим. ред.
Стр.4
Введение
5
Switched Path, LSP), а также предложен эвристический алгоритм пропорционального
распределения потоков, который позволяет получить квазиоптимальный
дизайн LSP. Из существующих методов решения задачи
оптимизации рассмотрены метод минимального разреза и метод линейного
программирования.
Точное решение задач оптимизации можно получить с помощью
линейного программирования, однако сложность вычислений при линейном
программировании быстро возрастает с увеличением числа узлов в
сети и для больших сетей является критической, что приводит к необходимости
использования эвристических методов.
В пятой главе рассматриваются вопросы выбора оптимальных путей
LSP с дифференциальным обслуживанием трафика при наличии
нескольких ограничений. Решение поставленной задачи предлагается
осуществить путем использования метода неопределенных множителей
Лагранжа. Задача разбита на две части. В первой решается вопрос,
связанный с необходимостью перенаправления потоков при выходе из
строя ранее выбранного пути. Это приводит к увеличению нагрузки на
«резервные» пути и, следовательно, к необходимости увеличения пропускной
способности «резервных» путей на величину определенную так
называемым коэффициентом отказоустойчивости. Во второй части с
учетом результатов, полученных в первой, решается задача выбора квазиоптимальных
путей.
Во последних двух главах рассмотрены вопросы обеспечения высоких
показателей готовности. Известно, что коэффициент готовности зависит
от времени наработки на отказ и времени восстановления. В свою
очередь время восстановления зависит от момента обнаружения отказа,
его локализации и времени, за который произойдет устранение отказа.
В главе 6 рассмотрены как общие подходы к локализации отказов,
так и частные, среди которых метод наложенных сетей и метод локализации
отказов путем использования тест-станций. В качестве примера
реальной системы мониторинга рассмотрена система Nagios.
Глава 7 содержит материал, посвященный общим вопросам резервирования
и восстановления. Рассмотрены методы защиты звена, пути,
сегмента. Приведены рекомендации по использованию методов защиты.
В качестве одной из мер по обеспечению QoS представлен метод на основе
использования приоритетов. Большой раздел посвящен защите и
восстановлению в сетях GMPLS (раздел 7.5). Следует заметить, что вопросам
защиты и восстановления, помимо упомянутых выше, посвящены
как монографии (например, [138]), так и множество статей в журналах
[139–152 и др.]. Авторы не ставили перед собой задачу дать полный
обзор литературы по данной тематике, а лишь пытались обратить внимание
читателя на эту проблему.
Монография может быть использована при развертывании опытной
зоны или пуско-наладочных испытаний нового сегмента, что позволяет
выяснить все потенциально возможные «узкие места», минимальный
Стр.5
6
Введение
разрез в сети, которые могут возникнуть в сети через 1–2 года после начала
эксплуатации. При эксплуатации, в случаях внедрения новых услуг,
изменения плана маршрутизации и т.п. любые изменения в структуре
трафика могут привести к негативным последствиям на сети. Используя
разные классы обслуживания и измеряя коэффициенты отказоустойчивости
связи, можно посмотреть реакцию сети на изменение структуры
трафика или увеличения объема передаваемой информации в сети, а
также на возникновение неисправности трактов.
Полученные результаты, с одной стороны, представляют научный
интерес, с другой стороны, могут быть использованы специалистами
при составлении проекта модернизации мультисервисной сети связи к
внедрению на сетях связи. Работа не претендует на детальный охват
всех вопросов оптимизации телекоммутационных сетей. Однако авторы
надеются, что методики, представленные в ней, будут полезны широкому
кругу читателей.
При подготовке рукописи использован ряд первоисточников. В основном
это англоязычные статьи и материалы IEEE. В поиске работ по
тематике представленного в монографии материала и переводе ряда статей
принимали участие магистранты и аспиранты СибГУТИ О. Артемьева,
А. Бахарев, А. Бритова, которым авторы выражают искреннюю
благодарность.
Стр.6
Оглавление
Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 1. Многопротокольная коммутация по меткам . . . . . . . .
1.1. Определение основных целей и задач исследования. Общие
понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
7
7
1.2. Преимущества MPLS 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3. Проблемы распределения трафика и безопасности в сетях
MPLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.4. Обобщенная многопротокольная коммутация по меткам . . . 17
1.4.1. Переход от MPLS к GMPLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.2. Особенности GMPLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Глава 2. Управление трафиком и обеспечение качества услуг
в сетях MPLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1. Формирование трафика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 3. Методы оптимизации трафика в IP/MPLS сетях . .
Глава 4. Методы распределения многопродуктовых потоков
4.1. Модель для оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Цели оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
35
2.2. Управление трафиком. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3. Обеспечение QoS (качества услуг) . . . . . . . . . . . . . . . . . . . . . . . . . 43
46
50
51
53
4.3. Методы оптимизации. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4. Принцип максимального потока (минимального разреза) . .
4.5. Линейное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6. Эвристический метод определения оптимального дизайна .
4.7. Сравнение алгоритмов поиска оптимального дизайна . . . . . . 65
55
58
59
Глава 5. Оптимизация сетей IP/MPLS с дифференциальным
обслуживанием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1. Формулировка задачи оптимизации . . . . . . . . . . . . . . . . . . . . . . .
68
69
5.1.1. Ограничение по резервированию пропускной способности . . . . . 69
5.1.2. Оценка необходимости увеличения пропускной способности LSP
с учетом возможных отказов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.1.3. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.2. Эвристический алгоритм оптимизации . . . . . . . . . . . . . . . . . . . .
5.2.1. Подзадача на основе использования метода неопределенных
множителей Лагранжа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2. Алгоритм оптимизации на основе множителей Лагранжа . . . . . . 76
75
75
5.3. Метод повторной оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.4. Модель сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Стр.143
144
Оглавление
Глава 6. Обнаружение и локализация сбоев . . . . . . . . . . . . . . . . .
6.1. Классификация сбоев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Реакция системы и требования к системам локализации сбоев
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
84
86
6.3. Методы локализации сбоев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3.1. Методы, относящиеся к области искусственного интеллекта . . . 88
6.3.2. Техника пересечения моделей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.3.3. Методы, ориентированные на использование теории графов . . . 92
6.3.4. Метод наложенных сетей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.4. Мониторинг сети. Оптимальная расстановка зондирующих
станций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.5. Система мониторинга сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Глава 7. Резервирование и восстановление . . . . . . . . . . . . . . . . . . 111
7.1. Пути обеспечения живучести сетей связи . . . . . . . . . . . . . . . . . . 112
7.2. Классические модели защиты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.3. Использование механизма приоритетов для схем с разделяемой
защитой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.4. Защита и восстановление в сетях GMPLS. . . . . . . . . . . . . . . . . . 118
7.5. Разработка модели для определения показателей надежности
в сетях GMPLS с защитной коммутацией (1+1) в условиях
недостоверного комбинированного контроля . . . . . . . . . . . . . . . 130
Краткий глоссарий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Стр.144