ВОССТАНОВЛЕНИЕ СОЕДИНЕНИЙ СЕТИ MPLS С ИСПОЛЬЗОВАНИЕМ ЛИНЕЙНЫХ ДИОФАНТОВЫХ МОДЕЛЕЙ

Кулаков К.А.
Петрозаводский государственный университет
E-mail: kulakov@cs.karelia.ru

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

1. Задача восстановления
Рассмотрим сеть MPLS, использующую управление маршрутизацией пакетов [2]. Для соединения между конечными точками фиксируется маршрут из последовательности узлов сети. Каждый из узлов маршрута может управлять восстановлением соединения. Потеря соединения вызывается нарушением линии связи между соседними узлами или выходом из строя узла маршрута. Решение задачи восстановления включает построение нового маршрута для соединения (поиск маршрута) и переключение соединения на этот маршрут (активация маршрута). Далее будем рассматривать лишь задачу поиска маршрута.
Поиск может происходить как непосредственно после потери соединения (исправленный маршрут), так и заранее (резервный маршрут). Существует два базовых метода восстановления [2]:
1)	восстановление маршрута между узлами;
2)	восстановление маршрута между конечными точками.
В первом методе строится только маршрут обхода точки разрыва (линия или узел). Основным достоинством здесь является максимальное сохранение старого маршрута, что обеспечивает достаточно быстрое восстановление. Среди недостатков выделяют возможность существенного ухудшения характеристик маршрута после многократных восстановлений.
Во втором методе происходит построение обходного маршрута, который не пересекается (по узлам или линиям связи) с текущим маршрутом. Основным достоинством здесь является возможность построения наилучших маршрутов независимо от числа выполненных ранее восстановлений. Среди недостатков выделяют вычислительную сложность, которая существенно зависит от размера сети. В силу этого метод рекомендуется только для построения резервных маршрутов.
Для практического применения в сети MPLS наиболее предпочтительной представляется комбинация базовых методов для построения резервного маршрута [1]. При установлении соединения текущий маршрут разбивается на частично перекрывающиеся сегменты — домены. Для каждого домена строится один или более резервных маршрутов восстановления (второй базовый метод). При потере соединения определяется поврежденный домен, который заменяется на резервный (первый базовый метод). Это позволяет более быстро строить новый маршрут по сравнению со вторым базовым методом, поскольку поиск ограничен доменом. В то же время, ухудшение характеристик получаемых маршрутов происходит менее выражено, чем в первом базовом методе, поскольку домен затрагивает не два соседних узла, а больший сегмент маршрута.

2. Диофантовы модели сети MPLS
Нами предлагается моделирование сети MPLS в виде однородной системы неотрицательных линейных диофантовых уравнений, ассоциированной с формальными грамматиками (система одАНЛДУ) [3,4]. Это позволит использовать псевдополиномиальные синтаксические алгоритмы решения [5].
Система одАНЛДУ имеет вид , где  — количество уравнений,  — количество неизвестных. Левая часть  — (0,1)-матрица разбиения множества  на попарно непересекающиеся подмножества , . Правая часть — матрица неотрицательных целых коэффициентов правой части системы.
Рассмотрим орграф  некоторой сети MPLS с множеством узлов  и линий связи , который получен заменой каждой линии связи двумя ориентированными дугами. В простейшем случае построение модели основано на матрице инцидентности орграфа . Уравнения системы одАНЛДУ соответствуют вершинам орграфа, а неизвестные — дугам. Исходящие дуги вершины определяют неизвестные в левой части уравнения, а входящие — в правой. Полученная система одАНЛДУ представляет линейную диофантову модель топологии сети. 
В предложенном варианте построения модели матрица  является матрицей инцидентности орграфа сети, и матрица  в качестве столбцов содержит единичные векторы. Данная модель аналогична поиску простых контуров в графе сети MPLS. В общем случае модель можно описать следующим образом:
.
Возьмем линейную диофантову модель топологии сети и введем ограничения на поиск маршрутов. Нам требуется отобрать все такие маршруты, которые проходят через два заданных узла сети. Введем дополнительную дугу , которая соединяет конечный узел с начальным и будем искать только те контуры, которые проходят через данную дугу. Полученная модель представляет собой линейную диофантову модель с обратной связью. Пусть уравнение 1 в модели описывает начальный узел, а уравнение n — конечный узел. В общем случае модель можно описать следующим образом:

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

Под решением системы одАНЛДУ будем понимать нахождение ее базиса Гильберта — конечного множества всех неразложимых решений [6]. В рассмотренном нами случае, когда для построения одАНЛДУ используется матрица инцидентности, базис Гильберта  соответствует множеству простых контуров  орграфа сети [7]. В случае если модель строится с учетом дополнительных ограничений на элементы сети, то базис Гильберта соответствует не всем простым контурам , а происходит отсев контуров, которые не могут быть кандидатами на маршрут восстановления. 

3. Алгоритмы решения систем одАНЛДУ
Для того класса систем одНЛДУ, который используется в предлагаемой модели, известны псевдополиномиальные синтаксические алгоритмы нахождения базиса Гильберта [5]. Теоретическая оценка сложности наихудшего случая составляет  для времени решения и  для требуемой памяти, где  — число элементов в базисе,  — число неизвестных,  — число уравнений. Экспериментальный анализ показывает, что для большинства тестовых систем временна́я сложность составляет . Эти алгоритмы позволяют использовать различные ограничения, накладываемые на значения неизвестных, что делает удобным их модификацию под используемые модели.
Характеристика	Метод	Число неизвестных	
		100	200	500	1000	
Время, сек	1	0,014	0,036	0,252	1,546	
Память, Кб		1756	2084	3792	8168	
Время, сек	2	0,02	0,112	3,064	23,598	
Память, Кб		1756	2184	4048	10188	
В таблице приведены характеристики алгоритма решения (среднее время работы и максимальный объем используемой памяти) в зависимости от числа неизвестных m. Измерения выполнены с помощью системы Web-SynDic [6].
Для каждого значения m генерировались 20 систем. Использовалось два метода генерации [8]. Первый позволяет генерировать частный случай орграфа сети MPLS. Второй учитывает возможность использования коэффициентов правой части (матрица ), отличных от коэффициентов инцидентности. Оба метода поддерживают ограничения на размер базиса Гильберта (q≤500). При оценке объема памяти измерялись все затраты (сегменты данных, потоки, сегменты кода и т.п.). Измерения выполнялись на ЭВМ с CPU Celeron 1200 МГц, RAM 512 Мб, Linux 2.6.5. Система Web-SynDic работала на платформе Java 1.4.2.08 / Apache Tomcat 5.0.19.
Данные результаты показывают, что синтаксический алгоритм дает существенный выигрыш по времени, по сравнению с использованием классических алгоритмов нахождения простых контуров в графе. Так, в [9] для нахождения простых контуров требовалось несколько минут даже при m=100 (использовалась ЭВМ SUN Ultra 80, CPU 2х450 МГц, RAM 2 Гб).

3. Заключение
Использование систем одАНЛДУ для моделирования маршрутизации в сетях MPLS и разработка основанных на них алгоритмов эффективного восстановления соединений представляется практически важной и перспективной. Получаемые диофантовы модели маршрутизации дают более общий метод, чем непосредственное использование графа сети. Они позволяют учитывать дополнительные характеристики элементов сети и искомых резервных маршрутов. Данный подход может применяться и для других сетей, отличных от MPLS, в которых поддерживается управление маршрутами и известна топология сети.

REFERENCES
1.	Pin-Han Ho, Hussein T. Mouftah. A framework for service-guaranteed shared protection in WDM mesh networks. SPIE Commun. Mag., vol. 40, pp.97-103, 2002.
2.	V. Sharma, F. Hellstrand Framework for Multi-Protocol Label Switching (MPLS)-based Recovery. RFC 3469. Feb 2003.
3.	Богоявленский Ю. А., Корзун Д. Ж. Общий вид решения системы линейных диофантовых уравнений, ассоциированной с контекстно-свободной грамматикой. Труды Петрозаводского государственного университета. Сер. ``Прикладная математика и информатика''. Вып. 6. — Петрозаводск: Изд-во ПетрГУ, 1997. — С. 79–94.
4.	Корзун Д. Ж. Об одной взаимосвязи формальных грамматик и систем линейных диофантовых уравнений. Вестник молодых ученых, 2000. № 3. — СПб: Изд-во СПбГТУ, 2000. — С. 50–56.
5.	Корзун Д. Ж. Grammar-Based Algorithms for Solving Certain Classes of Non-negative Linear Diophantine Systems. Труды международного семинара Finnish Data Processing Week at the University of Petrozavodsk (FDPW'2000): Advances in Methods of Modern Information Technology. Vol. 3. — Петрозаводск: Изд-во ПетрГУ, 2001. — С. 52–67.
6.	Схрейвер А. Теория линейного и целочисленного программирования: Пер. с англ. Т.1. — М.: Мир, 1991. — 360 с.; Т.2. — М.: Мир, 1991. — 342 с.
7.	Кулаков К. А. Генерация систем неотрицательных линейных диофантовых уравнений и ее приложения. Магист. Дисс. Петрозаводск, ПетрГУ, 2005. 82с.
8.	Кулаков К.А. Генерация систем неотрицательных линейных диофантовых уравнений. Материалы международной конференции "Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы". — Петрозаводск, Изд-во ПетрГУ, 2006. — Ч. 2. С. 58-65.
9.	Pin-Han Ho, Hussein T. Mouftah. Reconfiguration of Spare Capacity for MPLS-Based Recovery in the Internet Backbone Networks. IEEE/ACM Trans. on Net. Vol. 12. Feb. 2004. pp.73–84.