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

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

Кулаков Кирилл Александрович

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА РЕАЛИЗАЦИИ ЛИНЕЙНЫХ ДИОФАНТОВЫХ МОДЕЛЕЙ СЕТЕЙ ЭВМ

Специальность 05.13.18 — математическое моделирование, численные методы и комплексы программ

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

Петрозаводск — 2009

003464984

Работа выполнена в ГОУ ВПО Петрозаводский государственный университет

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

кандидат технических наук, доцент Ю. А. Богоявленский

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

доктор физико-математических наук, профессор Н. К. Косовский

кандидат физико-математических наук, доцент В. Т. Вдовицын

Ведущая организация:

Московский государственный университет им. М. В. Ломоносова

Защита состоится "17"апреля 2009 г. в'^'час. на заседании диссертационного совета Д 212.190.03 в Петрозаводском государственном университете по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.

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

Автореферат разослан .^^^ВггЧШ г.

Учёный секретарь диссертационного совета. Д 212.190.03 V■7 в- в- Поляков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Коэффициенты системы одНЛДУ принадлежат множеству целых чисел Ъ, а неизвестные — множеству неотрицательных целых Z+. Конечный и единственный базис Гильберта системы есть множество всех ее неразложимых решений за исключением нулевого. Концепция базиса Гильберта появляется в трудах ученых D. Hilbert, Р. Gordan, J. G. van der Corput, E. В. Elliot и P. A. MacMahon. Сложность задачи решения таких систем исследуется в работах В. Н. Шевченко, Н. К. Косовского, A. Schriever, L. Pottier, М. Henk, L. Juban, J.-F. Romeuf и др. В диссертации рассматривается задача численного нахождения базиса Гильберта (НБГ).

Базис Гильберта является удобным средством для описания дискретных свойств сетей ЭВМ и может использоваться при решении задач обеспечения надежности сетей, идентификации структуры нагрузки канала, описании маршрутов с заданными свойствами2. В диссертации проблема построения линейных диофантовых моделей рассматривается на примере актуальной прикладной технической задачи — восстановления соединений в сети ЭВМ.

1 Traffic engineering with MPLS in the Internet / X. Xiao, A. Hannah, B. Bailey et al. // IEEE Net. Mag. 2000. Vol. 14. P. 28-33.

2Korzun, D. A diophantine model of routes in structured P2P overlays / D. Korzun, A. Gurtov // ACM SIGMETRICS Performance Evaluation Review. 2008. Vol. 35, no. 4. P. 52-61.

Существующие методы восстановления (напр., IP reroute) не обеспечивают гарантированного времени восстановления. Кроме того, необходимо выполнять отбор маршрутов-кандидатов на основе дополнительных критериев. Например, некоторые маршруты восстановления могут не подходить из-за загруженности линий связи.

Задача восстановления соединений актуальна для технологии многопротокольной коммутации с использованием меток (Multiprotocol label switching, MPLS), позволяющей уменьшать время выбора направления пересылки пакета и выполнять рационализацию трафика. В алгоритме SLSP3 находятся простые циклы в графе сети, по которым отбираются маршруты-кандидататы, затем для выбора оптимального маршрута решается задача ЦЛП. Трудоемкость последней зависит от выбора циклов и их числа.

Таким образом, актуальной является задача разработки линейных дио-фантовых моделей сетей MPLS для рационального поиска и отбора маршрутов. Автором предлагается иерархия таких моделей. Маршруты-кандидаты определяются базисом Гильберта, а для отбора предлагается использовать содержательный нелинейный критерий — кумулятивную характеристику маршрута.

Применение предлагаемых моделей возможно при условии наличия эффективных алгоритмов нахождения базиса Гильберта (НБГ) и их протестированных реализаций. В работах С. Л. Кривого, Д. В. Пасечника, G. Huet, М. Clausen, A. Fortenbacher, Е. Contejean, Е. Domenjoud, М. Filgueiras, А.-Р. Tomás и других авторов предложен ряд алгоритмов НБГ для произвольных одНЛДУ и их систем. Эти алгоритмы представлены без верхних оценок сложности, а их реализации не проверены массовым тестированием. Нижние оценки сложности определяются размером базиса Гильберта и могут экспоненциально зависеть от размеров исходной системы. Такое положение определяет актуальность исследований частных классов систем одНЛДУ для построения эффективных алгоритмов НБГ.

М. Filgueiras и A. Tomás показали, что систему НЛДУ можно ассоциировать с контекстно-свободной грамматикой (АНЛДУ). Ю. А. Богоявленский и Д. Ж. Корзун развили этот результат, предложив метод построения системы АНЛДУ по произвольной КС-грамматике и двум цепочкам над ее алфавитом. При равенстве цепочек строится однородная система АНЛДУ (одАНЛДУ). В диссертации используется только алгебраическое определение такой системы.

Известно, что методы последовательного исключения для систем линей-

3Но, Р.-Н. Reconfiguration of spare capacity for MPLS-based recovery in the Internet backbone networks / P.-H. Ho, H. T. Mouftah // IEEE/ACM Trans. Netw. 2004. Vol. 12, no. 1. P. 73-84.

пых уравнений справедливы, когда и коэффициенты, и неизвестные принадлежат полю или кольцу целых чисел. В то же время неизвестны аналоги метода исключения неизвестных, когда коэффициенты принадлежат множеству Z, а неизвестные — множеству неотрицательных целых чисел ¡Z+.

Таким образом, актуальной является задача построения эффективного алгоритма НБГ для систем одАНЛДУ на основе метода последовательного исключения уравнений и неизвестных. Автором исследуется подход, позволяющий решать как задачу HB Г, так и задачу генерации систем с известным базисом Гильберта (ИБГ системы). К ним относятся тестовые, эталонные и модельные системы (последние структурно соответствуют реальным сетям MPLS, далее — М-системы).

Для практического применения алгоритмов НБГ необходимы тестирование и экспериментальная оценка эффективности программных реализаций, в том числе по сравнению с другими. В работе для сравнения используются реализации алгоритмов Syntactic4 и SlopesSys5.

Таким образом, актуальной является задача реализации алгоритмов НБГ и разработки программной системы (ПС) для их тестирования и экспериментального исследования предлагаемых моделей на М-системах. Для решения этих задач автором предлагается комплекс программ, доступный через Интернет с помощью Web-обозревателя.

Объект и предмет исследования. Объектами исследования являются сети MPLS, системы одАНЛДУ и базисы Гильберта, а предметом исследования — линейные диофантовы модели сетей ЭВМ, алгоритмы НБГ и генерации ИБГ систем, сложность алгоритмов, программные реализации алгоритмов и средства их экспериментального исследования.

Цели диссертационной работы состоят в следующем.

1. Развитие метода последовательного исключения для частного класса — систем одАНЛДУ, коэффициенты которых принадлежат Z, а неизвестные — Z+. Разработка, обоснование, реализация, тестирование и экспериментальное исследование алгоритмов НБГ и генерации этих систем.

2. Разработка, обоснование и реализация линейных диофантовых моделей сетей MPLS для использования в алгоритме SLSP, а также проверка эффек-

4Корзун, Д. Ж. Grammar-Based Algorithme for Solving Certain Classes of Nonnegative Linear Diophantine Systems / Д. Ж. Корзун // Тр. межд. семинара Finnish Data Processing Week at the University of Petrozavodsk (FDPW'2000): Advances in Methods of Modem Information Technology. .Vol. 3. Петрозаводск: Изд-во ПетрГУ, 2001. P. 52-67.

5Tomás, A. P. Algorithme for Solving Diophantine Equations in Naturals [Электронный ресурс] / A. P. Tomás, M. Filgueiras. Электрон, дан. DCC-FC & LIACC, Universidade do Porto. 2001. Режим доступа: http://www.dcc.fc.up.pt/~apt/dioph/, свободный. Загл. с экрана.

тивности алгоритмов НБГ на сгенерированных М-системах.

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

Научная новизна. Для решения задачи восстановления соединений в сетях MPLS впервые предложено использовать линейные диофантовы модели на основе систем одАНЛДУ и базисов Гильберта.

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

Разработан, обоснован и протестирован новый алгоритм НБГ произвольной системы одАНЛДУ, имеющий лучшие теоретические и экспериментальные оценки по сравнению с известными алгоритмами.

Разработаны и обоснованы пять алгоритмов генерации частных классов ИБГ систем одАНЛДУ. Ранее задача построения тестовых примеров решалась с помощью полученных вручную малых наборов систем или непосредственной (без построения базиса Гильберта) генерацией.

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

Разработанные алгоритмы НБГ и генерации ИБГ систем могут быть использованы в прикладных задачах с дискретными переменными. Результаты выполненного экспериментального исследования позволяют оценить практическую эффективность реализаций таких алгоритмов.

Разработанный комплекс программ может быть использовал для решения прикладных задач путем доступа через Интернет, а также для тестирования и экспериментального исследования алгоритмов НБГ.

На защиту выносятся следующие положения:

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

2. Предложены преобразования системы одАНЛДУ к трапециевидной форме и обратной подстановки базиса Гильберта. Они развивают метод последовательного исключения для класса систем одАНЛДУ, позволяя разра-

батывать эффективные алгоритмы НБГ и генерации ИБГ систем.

3. Разработай, обоснован, реализован и протестирован псевдополиномиальный алгоритм НБГ произвольной системы одАНЛДУ TransSol. Сложность алгоритма позволяет реализовать с его помощью линейные диофантовы модели сетей MPLS реальных размерностей.

4. Разработаны и обоснованы пять алгоритмов генерации ИБГ систем, четыре из которых программно реализованы.

5. Разработан комплекс программ, содержащий реализации предложенных алгоритмов НБГ и генерации ИБГ систем, реализации алгоритмов НБГ других авторов, ПС a!g_analyser для измерения потребляемых ресурсов и ПС Web-SynDic для доступа к исследуемым алгоритмам через Интернет.

6. Результаты тестирования и экспериментального исследования программных реализаций алгоритмов НБГ TransSol, Syntactic и SlopesSys показывают эффективность предложенного алгоритма TransSol при реализации линейных диофантовых моделей сетей MPLS.

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

Апробация работы. Результаты диссертационной работы докладывались

и обсуждались на международном научном семинаре "Finnish Data Processing Week at the University of Petrozavodsk (FDPW'2003)" (2003 г.), на конкурсе-конференции студентов и молодых ученых Северо-Запада "Технологии Microsoft в теории и практике программирования" (2004 г.), на Всероссийской научной конференции "Научный сервис в сети Интернет" (2004 г.), на второй международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности" (2006 г.), на международной конференции "Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы (SORUCOM'06)", на международном семинаре "Распределенные компьютерные и телекоммуникационные сети: теория и приложения (DCCN-2007)", на XIV Всероссийской научно-методической конференции "Телематика'2007", на научном семинаре "Проблемы современных информационно-вычислительных систем" механико-математического факультета МГУ им. М. В. Ломоносова под руководством проф. В. А. Васенина (2007 г.), на научном семинаре кафедры информатики математико-механического факультета СПбГУ под руководством проф. Н. К. Косовского (2008 г.), на семинаре Института прикладных математических исследований Карельского НЦ РАН под руководством проф. В. В. Маза-лова (2008 г.), на семинаре кафедры вычислительной математики механико-

математического факультета МГУ им. М. В. Ломоносова под руководством проф. Г. М. Кобелькова (2008 г.), а также на научных семинарах кафедры информатики и математического обеспечения ПетрГУ.

Публикации. По теме диссертационной работы опубликовано 10 печатных работ, в том числе работа [1] в журнале, внесенном в список ВАК.

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, библиографического списка использованной литературы (98 наименований), пяти приложений, имеет объем 136 машинописных страниц и 34 страницы приложений, содержит 25 рисунков и 12 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В п. 1.1 вводятся основные понятия и определения. Система одНЛДУ:

Ах = 0, А € ZnXm , (1)

где п — число уравнений системы, т — число неизвестных, А — матрица коэффициентов, О — нулевой вектор из Z".

Ненулевое решение h 6 системы (1) называется неразложимым, если оно не может быть представлено в виде суммы двух ненулевых решений этой системы. Базисом Гильберта системы (1) называется множество всех ее неразложимых решений "К = {hw,...h(4)}. Он единствен, конечен, а общее решение имеет вид х = a.sh<~5', а,

Пусть система S состоит из подсистем S' = (А'х = О) и S" = {А"х = О), а {/'1',/'2)! • • • ,/(?1>} есть базис Гильберта S'. Его подстановка в S" приводит к системе S из уравнений k = 1,... ,п" и неизвестных oi,...,aqi■ Получено следующее описание базиса Гильберта системы S в терминах S' и S.

Теорема 1.1. Пусть Oi = {j/1^, </2\ ... есть базис Гильберта сис-

темы S. Тогда базис Гильберта исходной системы S есть

Я = min{fcw = f><s)/(p) | s= 1,2,... ,<72}. (2)

p=i

Здесь minX = {х € X | $ х' 6 X : х' < х и х' ф ж}.

Индексное разбиение: In'm — {/o,/i,... ,/п}, где Ik Я Nm = {l,...,m}, (JLo = 'о может быть пусто, h ф 0 для к ф 0 и hnlj = 0 для к ф j.

Определим матрицу разбиения Е(1п'т) € {0,1}пХт следующим образом. Если г € /к, то Екг = 1, иначе Екг = 0. Столбцы в Е для г € /о — нулевые, а для г & к Ф 0, — стандартные единичные вектора е^.

Ассоциированная с КС-грамматикой система одНЛДУ (одАНЛДУ):

тп

Xi = к= 1,2, (3)

г£1к i= 1

В матричном виде Е(1п'т)х = Лх. В левой части любое ач встречается не более одного раза.

Свойство 1.1. .Если 5" получена из системы одАНЛДУ 5 удалением части уравнений или неизвестных, то — также система одАНЛДУ.

Уравнение Фробениуса с единичными коэффициентами — это НЛДУ вида ^"=1 Х1 — с для некоторой константы с^Ъ^..

В п. 1.2 представлены проблемы вычислительной сложности реализации линейных диофантовых моделей сетей ЭВМ. Требование целочисленности и неотрицательности существенно затрудняет использование схем классических методов решения линейных систем. Задача НБГ является вычислительно трудоемкой, поскольку число базисных решений может экспоненциально зависеть от размерности системы и абсолютных величин коэффициентов. Существующие методы ориентированы на решение произвольной системы одНЛДУ и неприемлемы на практике в случае больших систем.

В п. 1.3 рассматриваются частные случаи системы одАНЛДУ. Пусть 1п'т и — индексные разбиения Мт. Систему одАНЛДУ вида

£ х{ = £ х*> к = \,...,п

¿е ^1е\/)с

, Ек = 0, (4)

гег у

£ Хг = £ Хг, РСМт

. ¿е^ ¿е^

назовем симметричной (содАНЛДУ). Она известна в теории потоков и определяет циркуляцию в орграфе где уравнения соответствуют вершинам а неизвестные — дугам Мт. Дуга г выходит из вершины к, если 1 £ 4, и входит в вершину ], если i(zJj. Уравнение для Z соответствует висячей вершине г с входящими дугами i€.Z. Множество F определяет петли.

Назовем 1одАНЛДУ систему (3) при п = 1:

]|Гх;= ^а^. (5)

•е/1 з€10

В работе используются следующие известные свойства.

Свойство 1.2. Любое базисное решение к системы (<1) соответствует простому контуру в С? и наоборот, причем к € {0,1}т.

Свойство 1.3. Базис Гильберта (5) состоит из всех ( где Ь Е й'/1', ^ = а ~ единичный вектор из для ] 6 1о-

В п. 1.4 предлагаются преобразования системы одАНЛДУ к трапециевидной форме и обратной подстановки базиса Гильберта. Возьмем уравнение системы (3). Пусть Ь\ С 1г — множество индексов неизвестных, которые не встречаются в оставшихся уравнениях. Если Ь\ ф 0, то уравнение принимает

ВИД + Е.е/д!,! = Еад

Преобразование к трапециевидной форме = 5, к = 1,..., г).

1. Берем в уравнение, для которого Ьк ф 0. Если такого уравнения нет, то преобразование завершено. Считаем, что выбрано первое уравнение.

2. Систему представим в виде (х1 для г € Ьк не входят в

[ Е 1'=Е «нЖ;

= < шк\ьк (б)

I 3(к+

3. Система является системой одАНЛДУ (свойство 1.1) и содержит на одно уравнение меньше, чем

Неизвестные определяются индексами ик+ 1 — А^т \ и-=1 Полагая текущей, переходим к шагу 1.

Полученная трапециевидная форма имеет вид:

{Е ж, + Е Xi=¿2akiXi> к = 1,2,... ,г — 1 г<=ьк г€1к\ьк г$1к (7)

Теорема 1.2. Система б (7,) равносильна либо 1одАНЛДУ (при г = п), либо системе содАНЛДУ (при г <п).

Обратная подстановка базиса Гильберта (к = г — 1.....1).

1. В (6) подставляем в первое уравнение, получая

¿61к\ьк Шк нбЯ^+ч

2. Находим базис Й решая (8) относительно (х^цц^ и (а^^^ск+г);

3. Вычисляем = тт|Егб1,к 1>е» + ЕлеиС^1) I (а) е

4. Полагаем текущей систему

и выполняем шаги 1-4.

Уравнение (8) может быть записано как

X/ х' ~ X ¿киан , где = ^^анЫ - ^ /ц. (9)

•б-Ьк ьеи<1с+1) '¿'к *€1к\ьк

Следующая теорема показывает, что (9) есть 1 одАНЛДУ.

Теорема 1.3. Пусть система одАНЛДУ преобразована к (7) и Нк = и>=о Ь ■ Тогда для любых к = 1,2, ...,г и Н € выполняется:

(а) Е*ея* ^ ^ ес/ш кф 1, то ёк-\,ы > -1.

В п. 1.5 перечислены достоинства предложенных преобразований по срав-

нению с общей схемой исключения, позволяющие решать задачу НБГ для систем большой размерности.

1. Число итераций может быть меньше п (г ^ п). При г < п исходная система сводится не к одному уравнению, а к системе содАНЛДУ, для НБГ которой известны линейные по числу базисных решений алгоритмы (свойство 1.2). На каждой итерации обратной подстановки используется известный линейный алгоритм (свойство 1.3) для НБГ 1одАНЛДУ.

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

3. На каждой итерации преобразования к трапециевидной форме может исключаться несколько неизвестных (х¿, i € Lk), которые агрегируются в виде 1одАНЛДУ (9).

4. В обратной подстановке для произвольной системы одАНЛДУ нельзя полностью избавиться от выполнения операции отбора минимальных решений (2). Однако автором найден подкласс систем, для которых она не требуется (теорема 3.3 в гл. 3). Разработанные автором алгоритмы генерации М-систем не требуют этой операции.

В п. 1.6 выполняется обзор линейных диофантовых моделей и обосновывается целесообразность их выбора как математического объекта для моделирования сетей MPLS. В системе одАНЛДУ E(In'm)x — Ах уравнения соответствуют маршрутизаторам сети MPLS, а неизвестные — линиям связи. Матрица А определяет характеристики пересылки пакетов по линиям связи. Базис Гильберта определяет маршруты соединения.

Во второй главе предложена иерархия линейных диофантовых моделей сетей MPLS для задачи восстановления соединений. Модели предназначены для замены исходной модели алгоритма SLSP.

В п. 2.1, 2.2 приведен обзор сетей MPLS и рассмотрена задача восстановления соединений. На практике сети MPLS насчитывают от 10 до 500 маршрутизаторов и часто близки к полносвязным. Имеется общий механизм восстановления, определяющий последовательность действий маршрутизаторов для поиска нового маршрута и переключения на него соединения.

В п. 2.3 дан обзор известных алгоритмов восстановления соединений в сетях MPLS. В алгоритме SLSP текущий маршрут разбивается на частично перекрывающиеся домены, для которых строятся маршруты восстановления. При разрыве соединения в поврежденном домене соответствующий участок заменяется. Алгоритм использует модель сети MPLS в виде графа П(N, L) с множествами узлов N и линий связи L. Для входного маршрутизатора домена построение маршрутов восстановления состоит из трех шагов: 1) построить множество CY простых циклов из Q(N, L); 2) для каждого домена s текущего

маршрута г отобрать простые циклы CYr,s С CY, которые в точности проходят через $ (цикл покрывает домен); 3) решая задачу ЦЛП, из элементов CYT,s выбрать оптимальный (на основе характеристик линий связи).

В п. 2.4 предлагается диофантова модель топологии сети MPLS, заданной орграфом Г(N, L) с матрицей инцидентности E(J"'m) — Е(Jn,m). Модель определяется системой содАНЛДУ J2i£ik Xi = ж;, к = 1,..., п, равно-

сильна исходной SLSP-модели и позволяет искать маршруты восстановления между всеми парами входных и выходных маршрутизаторов домена. Множество всех простых циклов CY определяется базисом Гильберта.

В п. 2.5 предлагается модель с фиксированным соединением, г. Строим маршрут восстановления для домена s = (u,v) с входным и выходным маршрутизаторами и и v. Для этого в орграфе домена Ггз: 1) удалим все дуги, входящие в и или выходящие из v, 2) удалим внутренние вершины и дуги текущего маршрута, 3) добавим фиктивную дугу (v, и). В полученном орграфе любой контур, проходящий через (v, и), определяет маршрут между и и v (получается исключением (v, и) из контура). Простые контуры определяются базисом Гильберта и формируют СУГ,3.

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

Пусть орграф Г"з(Л) с весами дуг А = (aw,)w€N,ieb получен из Г"* добавлением фиктивных вершины z и дуги (v,z). Веса дуг (v,u) и (v,z) равны 1 и О соответственно. Орграфу Г"з(/1) соответствует система одАНЛДУ вида:

Величины XI характеризуют, например, затраты на передачу данных в маршруте. Базисное решение х с хт = 1 определяет маршрут восстановления, получаемый удалением дуг (у, и) и (у,г).

В п. 2.7 вводится кумулятивная характеристика С„ маршрута (и, у), представляющая собой нелинейный критерий его качества. Пусть маршрут (и, у) состоит из вершин и = \«о, \а/2, ..., — V. Тогда СЦ вычисляется через вложенные маршруты (и,\л/)е) начиная с вершины и. Ее значение для \л/к

(10)

зависит от значений для всех предыдущих вершин (см. правую часть (10)): Си = 1, Сик — ^ ^ ^¡.¡Р^Сц '), /с = 1,...,/, 4 < к,

где Р^С"') = ач — часть кумулятивной характеристики маршрута (и,\л/<), проходящего через дугу г € . Зависимость Рг от С"1 определяется решениями уравнения Фробениуса ^¿€/и1( Рг = С"4 (см. левую часть (10)). Начиная с исходной вершины в С™ накапливаются произведения линейных комбинаций кумулятивной характеристики маршрута. Число множителей равно числу вершин маршрута, а линейные комбинации составляются по дугам маршрута, входящим в Когда маршрут состоит из одного пути в графе, то

Си — йу^ ¿2 ' " • ^Уг'г, -

Если дуга г неэффективна (значение а„г > 1), то добавление к С„ величины увеличивает оценку затрат Хг на передачу данных в маршруте по дуге г в араз. Это соответствует принципу "слабого звена" — наличие неэффективной линии связи приводит к ухудшению качества маршрута.

Предложенная модель допускает простое вычисление кумулятивной характеристики. Пусть маршрут (и, V) определяется базисным решением х (хуи = 1). Тогда С„ = х„и + = + 1.

В силу свойств базиса Гильберта базисное решение х определяет маршрут с минимальным значением ж, для некоторой дуги i маршрута. Тем самым при решении задачи НБГ выполняется рациональный отбор маршрутов-кандидатов (шаг 2 алгоритма ЭЬЗР), что уменьшает трудоемкость поиска оптимального маршрута восстановления с использованием ЦЛП (шаг 3).

В п. 2.8 предлагается модель с множественной пересылкой. Физический интерфейс маршрутизатора может реализовать несколько линий связи. На основе модели с характеристиками линий связи и с фиксированным соединением построим модель в виде системы одАНЛДУ общего вида (3), учитывающую варианты множественной пересылки. В матрице А дополнительно к столбцам соответствующим линиям связи указываются столбцы, соответствующие множественной пересылке. Для этой модели также справедливо понятие кумулятивной характеристики, введенное в п. 2.7.

В п. 2.9 обсуждается практическое применение предложенных моделей. Предлагаемые автором линейные диофантовы модели сетей МРЬБ предназначены для замены исходной модели алгоритма БЬЯР. Они позволяют реализовать шаги 1 и 2 и упростить шаг 3 алгоритма ЭЬБР.

Базис Гильберта используется для поиска и отбора кандидатов на маршрут восстановления. Базисное решение определяет простой маршрут (не является комбинацией других маршрутов). Это позволяет рассматривать как

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

Основной проблемой применения диофантовых моделей на практике является трудоемкость задачи НБГ, зависящая от размера базиса Гильберта. Введенные в моделях ограничения на маршруты-кандидаты (условие xvu = 1 и пороговое значение кумулятивной характеристики) позволяют уменьшить размерность задачи ЦЛП на шаге 3 алгоритма SLSP.

В третьей главе на основе предложенных в гл. 1 преобразований разрабатываются алгоритмы НБГ и генерации ИБГ систем.

В п. 3.1 выполняется постановка задач НБГ и генерации ИБГ систем. Последняя заключается в построении системы (3) и ее базиса Гильберта Л при заданных ограничениях на процесс и результат генерации. Входные параметры: число уравнений п и неизвестных т, ограничения сверху на коэффициенты |]Л|| и базис Гильберта ||СК||, q = |!Я|. Результат: матрицы коэффициентов А и Б(Г'т) и базис Гильберта %.

В п. 3.2 изложен способ построения оценок сложности алгоритмов НБГ и генерации ИБГ систем. Используется модель с произвольным доступом к памяти (RAM) с операцией умножения. На основе верхних оценок затраченных времени и памяти исследуются временная сложность Т и емкостная сложность V. Оценивается память для хранения всех данных, кроме входных и результата. Сложность оценивается в зависимости от размера входных и выходных данных п, т, ||А|| и ||5С||. Если сложность ограничена полиномом от всех этих параметров, то алгоритм является псевдополиномиальным,.

В п. 3.3 предлагается псевдополиномиальный алгоритм НБГ произвольной системы одАНЛДУ (TransSol):

I. Выполнить алгоритм преобразования к трапециевидной форме, получая последовательность систем II. Найти базис Гильберта системы Для 1 одАНЛДУ используется свойство 1.3, для системы содАНЛДУ — свойство 1.2.

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

В диссертации получены следующие базовые оценки сложности.

Теорема 3.1. Сложность алгоритма преобразования к трапециевидной форме в наихудшем случае составляет Т = 0(тпп) и V = О(т).

Для этапа II известны алгоритмы НБГ с оценками сложности Т — 0((т+ n)q) и V = 0(т + п), где q = |5i(r)|. Пусть Q = max {|Й(к)|}.

Теорема 3.2. Сложность алгоритма подстановки базиса Гильберта в наихудшем случае составляет

Т = 0(mnQ2)

uV = 0(mQ).

Пусть = 0(q), где q = |iK| = Тогда сложность подстановки

линейна по числу базисных решений исходной системы. Автором исследован один из таких случаев (здесь = {he IK<fc+l) I dkh = -1}).

Теорема 3.3. Пусть = 0 для к = г — 1, г — 2,..., 1. Тогда слож-

ность алгоритма подстановки базиса Гильберта в наихудшем случае составляет Т = 0(mnq) uV = 0(mq).

В алгоритме TransSol размер базисов Гильберта исходной и промежуточных систем может оказаться большим. Предложенные модели сетей MPLS допускают использование части базиса Гильберта. Автором предлагаются три способа соответствующей модификации алгоритма: 1) вводится ограничение на размер базиса Гильберта, 2) рассматриваются только решения с Xi ^ 1 (проходящие через дугу г) и 3) рассматриваются только решения с заданным пороговым значением кумулятивной характеристики. Первые два способа — эвристические, поскольку не гарантируют отбор всех искомых маршрутов.

В п. 3.4-3.8 предложены алгоритмы генерации частных классов ИБГ систем, получены оценки сложности (теоремы 3.5, 3.7, 3.9, 3.10, 3.12).

Алгоритм JordanGen строит систему (Е(/п,р)|В)а; = (Е(/П,Р)|В + Д)ж и базис "К = {е*}?=1, где В 6 {О, I}"**'»-*), Bik = 1 для k = 1,..., m - р и Д е Zlx(m~p>, Ei=i Дч > 0 для i = 1,... ,m - p.

Алгоритм GaussGen строит систему (I|B)x = (D\B + Д)а: и базис CK = {h(a,}r=Tin- Если i>tiHi-n = i, та h\a) = 1. Если i>nui-n=fis, то h\3) = 0. Иначе h\s) = Gsi. Матрица В 6 {0, l}nx(m~n) строится как в алгоритме JordanGen. Матрица D £ Z"xn: если i + 1 < j, то Dij 6 Z+, если г + 1 = j, то Dtj е N, иначе Dij = 0. Матрица Д € 2"x(m-n). Матрица I -единичная (п х п)-матрица.

Алгоритм ExtGaussGen строит систему (Е(/п'р)|В)ж = (.0|В+Д):е и базис

Л = {hla)}43=1. Если г > 1п и ET=in+ih<j3) = h т0 h\s) <= (°>ипаче ^ > Разбиение 7n'p = {{1,...,h), {h +1,..., h},..., {ln-1 +1, • • •, In}} для 0 = l0 < l\ < h < ■ ■ ■ < ln = ln+i =pun^p<m. Матрица В 6 {0, l}nx!m-p) строится как в алгоритме JordanGen. Матрица Д € Z^x(m_p\ Матрица D £ Z"Xp: если j < I,, то Dij = 0, если I, < j < li+i, то Dij g N, иначе Dij 6 Z+.

Алгоритм SymGen строит систему содАНЛДУ E(I"'m)x = E(Jn'm)x и базис ■К = {/i(s) £ {0,1}т}*=1 на основе орграфа G(Nn,Nm) системы (4) и его простых контуров.

Алгоритм BxtSymGen строит систему

Е(/Ь,р) 0 ViD Д

О Е(i"-b'm~P) J " ^ <о E(Jn_b,m_p)

и базис % = {км}ч3=1. Если г ^ р, то 5? 0, иначе е {0,1}. Матрица Д 6 Матрица О € строится как в алгоритме Ех1Саи5зСеп, а

матрицы Е(/п-ь,тп~р) и E(Jn-b<m~p) - алгоритмом SymGen.

Для всех алгоритмов генерации доказано (теоремы 3.4, 3.6, 3.8, 3.11), что получаемый базис Гильберта удовлетворяет генерируемым системам. Результаты доказанных в гл. 3 теорем об оценках сложности сведены в табл. 1. Для сравнения даны оценки сложности алгоритма Syntactic.

Таблица 1

_Сложность алгоритмов_

Алгоритм ВременнЗя сложность Емкостная сложность

TransSol 0(mnQ2) 0{mQ)

TransSol (условие т. 2.3) 0(mnq) 0(mq)

Syntactic 0{m2n2Ql) 0(mn2Qs)

JordanGen 0(m2) 0(mn)

GaussGen 0(mn(m — n)) 0(m'2)

ExtGaussGen 0{mnq) 0(m(n + q))

SymGen 0(т(тп + n)q) 0(mq)

ExtSymGen 0(m(m + ri)q) 0(m(n + q))

В п. 3.9 рассматривается применение алгоритмов НБГ и генерации ИВГ систем для реализации линейных диофаптовых моделей сетей MPLS.

М-системы модели топологии генерируются алгоритмом SymGen без ограничений, а модели с фиксированным соединением — алгоритмом SymGen с фиксацией текущего маршрута г = (u,v) следующим образом. Для сгенерированной системы E(In'm)x = Е(Jn'm)x с базисом Гильберта !К' выбираем 0 < ки ^ п, 0 < км ^ п и îvu € р jk , удаляем все неизвестные ац: г € /*„ fV*u \ {¿vu} и строим % = {h € | hil = 1}.

М-системы модели с характеристиками линий связи генерируются алгоритмами GaussGen, ExtGaussGen и ExtSymGen следующим образом. Для сгенерированной системы Е(1п'т)х = Ах с базисом Гильберта выбираем 0 < u < n, V = 1, для которых aui > 0, удаляем все неизвестные хг\ i > 1, г е h и aUi > О и строим H = {h S "К' \ hi = 1}.

Для алгоритма GaussGen матрица D € Z"xn: если г + 1 = j, то Dij S N, иначе Dij = 0. Матрица Д € ^х(т-п) уд0влетв0ряет условию Д^ > 0 Bij > 0 для j = 1,... ,m — п. Для алгоритмов ExtGaussGen и ExtSymGen матрица D £ Z"Xp: если U < j < U+i, то Dij € N, иначе Dij = 0. Матрица Д € удовлетворяет условию Д,3- > 0 Bij > 0 для j = 1.....m —р.

М-системы модели с множественной пересылкой генерируются алгоритмами GaussGen, ExtGaussGen и ExtSymGen как и для модели с характеристиками линий связи, но без ограничений на коэффициенты системы.

В четвертой главе описан комплекс программ для массового автоматизированного тестирования и экспериментального исследования программных реализаций алгоритмов НВГ.

В п. 4.1, 4.2 сформулирована задача экспериментального исследования практической эффективности алгоритмов НБГ и описан способ вычисления потребляемых ресурсов. Для их измерения используются наборы эталонных систем и М-систем. Потребление общего времени оценивается стандартным образом. Оценка потребления системного времени и требуемой памяти основана на анализе данных операционной системы.

В п. 4.3 описан комплекс программ, содержащий реализации предложенных автором алгоритмов НБГ и генерации ИБГ систем, реализации алгоритмов НБГ других авторов, ПС alg_analyser для измерения потребляемых ресурсов и ПС Web-SynDic6 для доступа к алгоритмам через Интернет.

Алгоритмы НБГ, генерации и ПС alg_analyser реализованы в среде ОС Linux на языке ANSI С с использованием GNU С compiler (gcc 4.1.2). Объем кода реализации алгоритмов равен 3986 LOC, ПС alg_analyser — 2660 LOC.

ПС Web-SynDic предоставляет доступ через Интернет к алгоритмам решения и генерации с помощью web-обозревателя и предназначена для демонстрации работы алгоритмов, тестирования их реализаций, экспериментального исследования их практической эффективности, а также реализует услугу решения систем одАНЛДУ. Используются платформа Java (Java SDK 1.6.0) и сервер Apache Tomcat 5.0. Объем кода реализации равен 11907 LOC.

В п. 4.4 представлены результаты трех частей экспериментов по тестированию, оцениванию практической эффективности и сравнительному анализу доступных реализаций алгоритмов НБГ: SlopesSys, Syntactic и TYansSol.

Часть I (2002 г.). Массовое тестирование алгоритма Syntactic. Алгоритмы генерации: JordanGen и GaussGen. Построено 7 наборов, более 1.5- 10a систем.

Часть II (2002 г.). Сравнение алгоритмов SlopesSys и Syntactic. Алгоритмы генерации: JordanGen и GaussGen. Построено 2 набора, 104 систем.

Часть III (2008 г.). Сравнение алгоритмов Syntactic и TransSol для модели с множественной пересылкой. Проведены шесть серий экспериментов для различных классов систем. Алгоритмы JordanGen, GaussGen и ExtGaussGen генерировали для каждой серии наборы из 5000 систем (в серии шесть — 800 систем). Общее число систем — 75800.

В части I ошибок в реализации алгоритма Syntactic выявлено не было. На используемом классе тестовых систем алгоритм допускает получение решения за время до десятков секунд даже в условиях больших размеров входных данных (п,т ~ 102 ... 103, max{|ajj| | 1 < i ^ п, 1 ^ j ^ m} ~ 105).

6http://websyndic.cs.karelia.ru

В частях II и III некоторые системы исключены из выборки (не были решены за выделенное время алгоритмами SlopesSys и Syntactic, но были решены алгоритмом TransSol). Вычислялись выборочные характеристики: среднее значение, выборочная медиана Q(50%) и процентили Q(5%) и Q(95%). Пример полученной экспериментальной зависимости общего времени решения от числа неизвестных представлен на рис. 1.

Выбор.среднее

— 0(5%) ..... 0(50%)

— 0(95%)

О 300 600 900 1200 1500 1800 Число неизвестных (m)

(a) Syntactic: зависимость Т(т)

0 300 600 900 1200 1500 1800 Число неизвестных (m) (b) TransSol: зависимость Т(т)

Рис. 1: (Часть III, серия 5, ExtGaussGen) Зависимость общего времени решения от числа неизвестных m

Результаты экспериментов согласуются с полученными теоретическими оценками сложности и показывают практическую эффективность предложенного алгоритма TransSol. Он допускает решение больших систем (m, q ~ 103) в пределах десятков секунд (ЭВМ Intel Xeon, 2.80ГГц). По сравнению с алгоритмом Syntactic потребление памяти и общее время меньше на 10-35% и до двух раз соответственно. Отметим, что построение маршрутов восстановления для таких сетей на основе исходной SLSP-модели требует нескольких минут (ЭВМ SUN Ultra 80, 4 х 450МГц).

В заключении формулируются результаты диссертационной работы.

Список опубликованных работ по теме диссертации

1. Кулаков, К. А. Итеративный алгоритм нахождения базиса Гильберта однородных линейных диофантовых систем, ассоциированных с контекстно-свободными грамматиками / К. А. Кулаков, Д. Ж.Корзун, Ю. А. Богоявленский // Вестник СПбГУ. Сер. 10. Вып. 2. - СПб.: Изд-во СПбГУ, 2008. - С. 7384.

2. Кулаков, К. А. Генерация систем неотрицательных линейных диофантовых уравнений / К. А. Кулаков // Материалы межд. конф. "Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы".—Т. 2. — Петрозаводск: Изд-во ПетрГУ, 2006.—С. 58-65.

3. Кулаков, К. А. Диофантова модель сети MPLS для восстановления соединений за полиномиальное время / К. А. Кулаков // Сб. тр. второй межд.

научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности". — Т. 5. — СПб.: Изд-во Политех, унта, 2006.-С. 137-143.

4. Кулаков, К. А. Восстановление соединений сети MPLS с использованием линейных диофантовых моделей / К. А. Кулаков // Тр. межд. семинара "Распределенные компьютерные и телекоммуникационные сети: теория и приложения (DCCN-2007)". — T. 2.-М.: ИППИ РАН, 2007.-С. 23-27.

5. Кулаков, К. А. Технология автоматизации тестирования алгоритмов решения неотрицательных линейных диофантовых уравнений / К. А. Кулаков, Д. Ж. Корзун // Материалы межвузовского конкурса-конференции студентов и молодых ученых Северо-Запада "Технологии Microsoft в теории и практике программирования".— СПб.: Изд-во СПбГПУ, 2004.— С. 142-143.

6. Кулаков, К. А. Generating homogenious systems of équations for testing and experimental analysis of linear diophantine solvers / К. A. Кулаков, Д. Ж. Корзун //Тр. межд. семинара Finnish Data Processing Week at the University of Petrozavodsk (FDPW'2003): Advances in Methods of Modem Information Technology. — Vol. 5. — Петрозаводск: Изд-во ПетрГУ, 2005.— P. 259-278.

7. Кулаков, К. А. Восстановление маршрутов в опорных инфраструктурах высокопроизводительных телекоммуникационных системах на базе MPLS / К. А. Кулаков, Д. Ж. Корзун, Ю. А. Богоявленский // Тр. XIV Всероссийской науч.-метод. конф. Телематика'2007. — Т. 2.— СПб.: Изд-во СПбГУ ИТМО, 2007. - С. 398-399.

8. Проект Web-SynDic: Система удаленного решения линейных диофантовых уравнений в неотрицательных целых числах/Ю. А. Богоявленский, Д. Ж. Корзун, К. А. Кулаков, М. А. Крышень // Материалы межд. конф. "Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы", — Т. 1.— Петрозаводск: Изд-во ПетрГУ, 2006. — С. 136-145.

9. Система Web-SynDic для демонстрации и исследования синтаксических алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах / Д. Ж. Корзун, Ю. А. Богоявленский, К. А. Кулаков и др. // Тр. Всероссийской науч. конф. "Научный сервис в сети Интернет". — М.: Изд-во МГУ, 2004.-С. 8-10.

10. Web-SynDic — система демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений / К. А. Кулаков, А. Ю. Сало, А. В. Ананьин и др. // Материалы межвузовского конкурса-конференции студентов и молодых ученых Северо-Запада "Технологии Microsoft в теории и практике программирования".— СПб.: Изд-во СПбГПУ, 2004. - С. 43-44.

Подписано к печати 26.02.2009. Формат 60x89 1/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Изд. №62.

Государственное образовательное учреждение

высшего профессионального образования Петрозаводский государственный университет Отпечатано в типографии Издательства ПетрГУ

185910, г. Петрозаводск, пр. Ленина, 33.

Перечень сокращений и условных обозначений

Введение

1. Системы однородных неотрицательных линейных ди-офантовых уравнений, ассоциированные с контекстно-свободными грамматиками

1.1 Основные свойства систем одАНЛДУ.

1.2 Сложность задачи нахождения базиса Гильберта.

1.3 Частные случаи систем одАНЛДУ.

1.4 Преобразования произвольной системы одАНЛДУ.

1.5 Сравнение предложенных преобразований с общим методом последовательного исключения.

1.6 Моделирование сетей ЭВМ на основе систем одАНЛДУ и базисов Гильберта

Выводы.

2. Линейные диофантовы модели сети MPLS

2.1 Обзор технологии и размерность реальных сетей MPLS

2.2 Задача восстановления соединений в сети MPLS.

2.3 Обзор алгоритмов восстановления соединений.

2.4 Модель топологии.

2.5 Модель с фиксированным соединением.

2.6 Модель с характеристиками линии связи.

2.7 Кумулятивная характеристика маршрута.

2.8 Модель с множественной пересылкой

2.9 Вопросы применения моделей.

Выводы.

3. Алгоритмы нахождения базиса Гильберта и генерации систем одАНЛДУ

3.1 Постановка задач решения и генерации.

3.2 Построение оценок вычислительной сложности.

3.3 Алгоритм TransSol нахождения базиса Гильберта системы одАНЛДУ.

3.3.1 Алгоритм преобразования к трапециевидной форме

3.3.2 Алгоритм НБГ системы 5(г).

3.3.3 Алгоритм подстановки базиса для системы (1.9)

3.3.4 Модификация алгоритма TransSol для нахождения части базиса.

3.4 Алгоритм JordanGen генерации систем одАНЛДУ с единичным базисом Гильберта.

3.5 Алгоритм GaussGen генерации систем одАНЛДУ с частично единичным базисом Гильберта.

3.6 Алгоритм ExtGaussGen генерации систем одАНЛДУ с частично единичным базисом Гильберта. Общий случай

3.7 Алгоритм SymGen генерации систем содАНЛДУ.

3.8 Алгоритм ExtSymGen генерации систем одАНЛДУ, сводящихся к симметричным.

3.9 Применение алгоритмов НБГ и генерации для моделирования сети MPLS.

3.9.1 Генерация и реализация модели топологии.

3.9.2 Генерация и реализация модели с фиксированным соединением

3.9.3 Генерация и реализация модели с характеристиками линии связи.

3.9.4 Генерация и реализация модели с множественной пересылкой

3.10 Сводная информация по разработанным алгоритмам . 94 Выводы.

Комплекс программ и экспериментальное исследование алгоритмов

4.1 Постановка задач экспериментального исследования.

4.2 Измерение вычислительных ресурсов.

4.3 Комплекс программ для поддержки экспериментов.

4.3.1 Реализация алгоритмов НБГ и генерации.

4.3.2 Программная система alganalyser.

4.3.3 Программная система Web-SynDic.

4.4 Экспериментальное исследование алгоритмов.

4.4.1 Схема организации экспериментов.

4.4.2 Тестирование алгоритма Syntactic.Ill

4.4.3 Сравнение алгоритмов SlopesSys и Syntactic.

4.4.4 Сравнение алгоритмов Syntactic и TransSol на М-системах.

Выводы.

Сложность сетей ЭВМ постоянно возрастает за счет введения новых протоколов, роста числа приложений и их требований к качеству обслуживания. Этот рост приводит к усложнению прикладных технических задач управления сетевыми системами, что, в свою очередь, требует развития соответствующих методов математического моделирования. В моделях сетей ЭВМ необходимо учитывать дискретность как самих сетей (напр., топология и характеристики линии связи), так и возможных управляющих воздействий на них (напр., переключение маршрута или кратное увеличение пропускной способности линии связи), а также большую размерность (число ЭВМ порядка 102-106), см., напр., [32,53,72].

Традиционно решение многих задач управления сетями основано на графовых моделях и их обобщениях (напр., гиперграфы), реализация которых использует базовые алгоритмы на графах (напр., поиск простых контуров, кратчайших путей, оптимальных потоков) и методы целочисленного линейного программирования (ЦЛП) [12,10,13,74]. На практике этот подход может приводить к затруднениям [60,93,82,87].

Так, кратчайшие пути могут порождать перегрузку линий связи, линейность целевой функции не всегда адекватна на практике, оптимизационные задачи дают только одно решение, поиск альтернативных решений и различные обобщения графовых моделей требуют многократного использования базовых алгоритмов. В ряде случаев этих затруднений можно избежать применяя модели на основе систем однородных неотрицательных линейных диофантовых уравнений (одНЛДУ) и базисов Гильберта (линейные диофантовы модели). [17,19,64,56,80].

Системой одНЛДУ называется система, коэффициенты которой — целые числа, а неизвестные — неотрицательные целые. Конечный и единственный базис Гильберта однородной системы НЛДУ (системы одНЛДУ) представляет собой множество всех ее неразложимых решений за исключением нулевого. Традиционно системы НЛДУ исследовались в теории чисел [5] и комбинаторном анализе [70]. Концепция базиса Гильберта появляется в исследованиях ученых D. Hilbert, P. Gordan, J. G. van der Corput, E. B. Elliot и P. A. MacMahon (см. исторические справки в [36,85,39,50]). Термин "базис Гильберта" дан F. Giles и W. Pulleyblank [57] в ходе развития теории вполне двойственной целочисленности и целочисленных полиэдров [10,36,37]. Сложность задачи решения таких систем исследуется в работах В. Н. Шевченко [37], Н. К. Косовского [20], A. Schriever [36], L. Pottier [79], М. Henk [59], L. Juban [50], J.-F. Romeuf [83] и др.

Базис Гильберта используется в самых разнообразных приложениях. Так, при автоматизации дедуктивных построений задача ассоциативно-коммутативной унификации сводится к решению системы одНЛДУ, где базис Гильберта определяет минимальный полный набор унификаторов [88, 52,41,90]. В целочисленном программировании этот базис используется при построении универсального тестового множества для семейства целочисленных задач [36,39]. В задачах управления памятью и распараллеливания программ доступ к данным (кэш-память, массивы) описывается системой НЛДУ, решения которой определяют повторные обращения [80,56].

Базис Гильберта представляется удобным инструментом для описания дискретных свойств сетей ЭВМ. Известно, что базис системы одНЛ-ДУ, построенной по матрице инцидентности графа сети, определяет простые контуры в графе. Они используются при решении задач обеспечения надежности и устойчивости сети к сбоям [67,87]. При идентификации структуры нагрузки канала передачи данных базис Гильберта определяет главные источники нагрузки [17]. В самоорганизующихся и одноранговых сетях этот базис описывает маршруты с заданными свойствами [19,64].

Таким образом, актуальной является проблема развития методов моделирования сетей ЭВМ на основе систем одНЛДУ pi их базисов Гильберта. В диссертационной работе эта проблема рассматривается на примере актуальной прикладной технической задачи — восстановления соединений в сети ЭВМ. Ее актуальность вызвана ростом числа чувствительных к задержкам приложений (напр., потоковый звук и видео). Существующие методы восстановления (напр., IP reroute [95,87]) не обеспечивают гарантированного времени восстановления. Кроме поиска возможных маршрутов, необходимо выполнять отбор маршрутов-кандидатов на основе дополнительных критериев. Например, некоторые маршруты могут не подходить из-за загруженности линий связи.

Задача восстановления соединений особенно актуальна для технологии многопротокольной коммутации с использованием меток (Multiprotocol label switching, MPLS) [84,73], позволяющей значительно уменьшать время выбора направления пересылки пакета и выполнять рационализацию (инжиниринг [30,8,72]) трафика. Технология MPLS имеет общий механизм восстановления, включающий поиск маршрута [86]. В [60] предложен алгоритм Short Leap Shared Protection (SLSP) для поиска маршрута восстановления. Используемая в алгоритме SLSP-модель основана на поиске простых циклов в графе сети по которому отбираются маршруты-кандидаты, а затем выбор оптимального маршрута решается задачей ЦЛП. Трудоемкость последней зависит от числа выбранных простых циклов [71,36].

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

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

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

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

Применение предлагаемых моделей возможно при условии наличия эффективных алгоритмов нахождения базиса Гильберта (НБГ) и их протестированных реализаций. Однако в этой области существует серьезный пробел. В настоящее время предложен ряд алгоритмов НБГ для случая произвольных одНЛДУ и их систем на основе различных математических методов: верхние границы компонент базисных решений [62,79,59]; элементарные преобразования матриц [66]; покомпонентное построение решений, начиная с пулевого [45,46]; преобразования производящих функций (метод Elliott — MacMahon) [70,49,77,40]; нахождение базисных решений с минимальным носителем и последующим построением оставшихся базисных решений как рациональных положительных комбинаций [48,91,65]; нахождение базиса Гребнера идеала в кольце полиномов [79,78].

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

Задача НБГ является вычислительно трудоемкой, поскольку число базисных решений в худшем случае экспоненциально зависит от размерности системы и абсолютных величин ее коэффициентов [36,50]. В этом случае эффективным можно считать псевдополиномиальный алгоритм, сложность которого ограничена полиномиально не только в зависимости от числа уравнений и неизвестных, но и от числа базисных решений [42,17].

Такое положение определяет актуальность исследований частных классов систем одНЛДУ для построения специализированных эффективных алгоритмов НБГ. Например, в случае системы одНЛДУ из двух уравнений, время нахождения базиса Гильберта полиномиально по числу неизвестных и максимальному значению коэффициентов [83].

М. Filgueiras и A. Tomas показали, как систему НЛДУ можно ассоциировать с контекстно-свободной (КС) грамматикой (сокращенно — система АНЛДУ) [54]. Авторы [4], а затем Д. Ж. Корзун в [15,17] развили этот результат, предложив метод построения системы АНЛДУ по произвольной КС-грамматике и по двум цепочкам. При равенстве цепочек строится однородная система АНЛДУ (система одАНЛДУ). В диссертации используется только алгебраическое определение этих систем [15,17].

Известно, что метод последовательного исключения для систем линейных уравнений справедлив, когда и коэффициенты системы и неизвестные рассматриваются, как элементы одного множества, например произвольного поля (варианты метода Гаусса [28,3]) или кольца целых чисел Z (метод Эрмита [13]). В то же время неизвестны аналоги этого метода, когда коэффициенты являются элементами множества Z, а неизвестные — элементами множества неотрицательных целых чисел Z+.

Таким образом, актуальной является задача построения эффективного алгоритма НБГ системы одАНЛДУ на основе метода последовательного исключения уравнений и неизвестных.

Автором предлагается и обосновывается алгоритм — аналог метода исключения, позволяющий решать как задачу НБГ, так и задачу генерации систем одАНЛДУ с известным базисом Гильберта (НБГ системы). Последние включают тестовые, эталонные и модельные системы одАНЛДУ, структурно соотвествующие реальным сетям MPLS (М-системы). Для практического применения алгоритма необходимы тестирование и экспериментальная оценка эффективности его реализации, в том числе по сравнению с реализациями других алгоритмов.

Таким образом, актуальной является задача программной реализации алгоритмов НБГ и разработки программных средств для их тестирования, экспериментального и сравнительного анализа, оценки эффективности предлагаемых моделей на М-системах и представления результатов исследований в Web-пространстве.

Эти задачи решаются с помощью разработанного автором комплекса программ. Тестирование позволяет проверить корректность реализации алгоритма на наборе тестовых систем [35]. При этом необходимы разработка и реализация ПО измерения эффективности и автоматической генерации и проверки тестов.

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

Цель исследования формулируется следующим образом.

1. Развитие метода последовательного исключения для частного класса — систем одАНЛДУ, коэффициенты которых принадлежат Z, а неизвестные — Z+. Разработка, обоснование, реализация, тестирование и экспериментальное исследование алгоритмов НБГ и генерации этих систем.

2. Разработка, обоснование и реализация линейных диофантовых моделей сетей MPLS для использования в алгоритме SLSP, а также проверка эффективности алгоритмов НБГ на сгенерированных М-системах.

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

Научная новизна работы отражена в следующих положениях.

Для решения задачи восстановления соединений в сетях MPLS впервые предложено использовать линейные диофантовы модели па основе систем одАНЛДУ и базисов Гильберта.

Впервые предложены и обоснованы преобразования систем одАНЛДУ к трапециевидной форме и обратной подстановки базиса Гильберта для случая, когда коэффициенты системы принадлежат Z, а неизвестные

Разработан, обоснован и протестирован новый алгоритм НБГ произвольной системы одАНЛДУ, имеющий лучшие теоретические и экспериментальные оценки по сравнению с известными алгоритмами.

Разработаны и обоснованы пять алгоритмов генерации частных классов ИБГ систем одАНЛДУ. Ранее задача построения тестовых примеров решалась с помощью полученных вручную малых наборов систем или непосредственной (без построения базиса Гильберта) генерацией.

Объектами исследования в работе являются сети MPLS, системы одАНЛДУ и базисы Гильберта, а предметом исследования — линейные ди-офантовы модели сетей ЭВМ, алгоритмы НБГ и генерации систем одАНЛДУ, сложность алгоритмов, программные реализации алгоритмов и средства их экспериментального исследования.

Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка использованной литературы (98 наименований), пяти приложений, имеет объем 136 машинописных страниц и 34 страницы приложений, содержит 25 рисунков и 12 таблиц.

Выводы

В главе 4 представлен разработанный комплекс программ и описаны результаты проведенных с его помощью экспериментальных исследований программных реализаций алгоритмов НБГ и генерации ИБГ систем одАНЛДУ. Результаты позволяют сделать положительный вывод о практической применимости разработанных автором алгоритмов для реализации линейных диофантовых моделей сетей ЭВМ.

Разработанная автором ПС alganalyser автономно тестирует программные реализации и измеряет потребление ресурсов. Автором реализованы алгоритм НБГ TransSol и алгоритмы генерации GaussGen, JordanGen,

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

Автором выполнено экспериментальное исследование из трех частей: I) тестирование алгоритма решения Syntactic; II) сравнение алгоритмов решения SlopesSys и Syntactic; III) сравнение алгоритмов решения TransSol и Syntactic при использовании в линейных диофантовых моделях сети MPLS. Получен вывод о практической применимости алгоритмов решения Syntactic и TransSol для систем одАНЛДУ, размерности которых соответствуют размерностям реальных сетей MPLS: общее время в пределах десятков секунд для m, q ~ 103. Показано, что алгоритм TransSol превосходит алгоритм Syntactic для такого класса систем одАНЛДУ: потребление памяти и общее время меньше на 10-35% и до двух раз, соответственно.

Заключение

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

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

Проведен анализ алгоритмов НБГ систем одНЛДУ, показавший необходимость разработки эффективных алгоритмов численного решения этой задачи для использования в линейных диофантовых моделях. Для систем одАНЛДУ разработаны и обоснованы преобразования к трапециевидной форме и подстановки базиса Гильберта, являющиеся развитием общего метода исключения неизвестных и уравнений для случая, когда коэффициенты системы принадлежат Z, а неизвестные - Z+.

На базе этих преобразований предложен и обоснован псевдополиномиальный алгоритм НБГ произвольной системы одАНЛДУ. Определен подкласс систем одАНЛДУ, для которого сложность алгоритма TransSol не зависит от размеров промежуточных систем. Также разработаны и обоснованы алгоритмы генерации ИБГ систем.

Разработанные алгоритмы реализованы в виде комплекса программ, обеспечивающих тестирование и экспериментальное исследование алгоритма НБГ, в том числе, для М-систем. Комплекс также обеспечивает доступ к алгоритмам из web пространства.

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

1. Ахо, А. Теория синтаксического анализа, перевода и компиляции / А. Ахо, Д. Ульман. - М.: Мир, 1978. - 612 с.

2. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Д. Хопкрофт, Д. Ульман. — М.: Мир, 1979.— 536 с.

3. Бахвалов, Н. С. Численные методы / Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков. 5 изд. - М.: БИНОМ, 2007. - 636 с.

4. Боревич, 3. И. Теория чисел / 3. И. Боревич, И. Р. Шафаревич. — М.: Наука, 1972. 495 с.

5. Бредфорд, Э. Кроссплатформенные приложения для Linux и Windows. Для профессионалов / Э. Бредфорд, J1. Може. — СПб.: Питер, 2003. — 672 с.

6. Галатенко, В. А. Программирование в стандарте POSIX: Курс лекций / В. А. Галатенко, — М.: Интернет-университет информ. технологий, 2004. 560 с.

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

8. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэ-ри, Д. Джонсон. М.: Мир, 1982. - 416 с.

9. Емеличев, В. А. Многогранники, графы, оптимизация / В. А. Емели-чев, М. М. Ковалев, М. К. Кравцов, — М.: Наука, 1982.— 341 с.

10. Кантор, И. Длинные числа и операции с ними Электронный ресурс. / И. Кантор. — Электрон, дан. — Режим доступа: http://algolist.ru/ maths/longnum.php, свободный. — Загл. с экрана.

11. Касьянов, В. Н. Графы в программировании: обработка, визуализация и применение / В. Н. Касьянов, В. А. Евстигнеев, — СПб.: БХВ-Петербург, 2003. 1104 с.

12. Ковалев, М. М. Дискретная оптимизация (целочисленное программирование) / М. М. Ковалев. — М.: Изд-во БГУ, 1977.— 191 с.

13. Корзун, Д. Ж. Об одной взаимосвязи формальных грамматик и систем линейных диофантовых уравнений / Д. Ж. Корзун // Вестник молодых ученых, 2000. № 3. СПб.: Изд-во СПбГТУ, 2000. - С. 50-56.

14. Корзун, Д. Ж. Синтаксические алгоритмы решения неотрицательных линейных диофантовых уравнений и их приложение к моделированию структуры нагрузки канала Интернет: Дисс. на соиск. канд. физ.-мат. наук / Петрозаводск, ПетрГУ. — 2002. — 185 с.

15. Корзун, Д. Ж. Использование линейных диофантовых уравнений для моделирования маршрутизации в самоорганизующихся сетях / Д. Ж. Корзун, А. В. Гуртов // Электросвязь. -2006. №6. - С. 34-38.

16. Косовский, Н. К. Логики конечнозначных предикатов на основе неравенств / Н. К. Косовский, А. В. Тишков,— СПб.: Изд-во СПбГУ, 2000.- 268 с.

17. Курош, А. Г. Курс высшей алгебры / А. Г. Курош. — М.: Наука, 1971. — 432 с.

18. Нефедов, В. Н. Курс дискретной математики / В. Н. Нефедов, В. А. Осипова. М.: Изд-во МАИ, 1992.- 264 с.

19. Олифер, В. Г. Компьютерные сети. Принципы, технологии и протоколы / В. Г. Олифер, Н. А. Олифер. СПб.: Питер, 2008.- 958 с.

20. Проект Web-SynDic: Система удаленного решения линейных диофантовых уравнений в неотрицательных целых числах / Ю. А. Богоявленский, Д. Ж. Корзун, К. А. Кулаков, М. А. Крышень // Материалы международной конференции "Развитие вычислительной техники в

21. России и странах бывшего СССР: история и перспективы". — Т. 1.— Петрозаводск: Изд-во ПетрГУ, 2006.- С. 136-145.

22. Российский Интернет в цифрах и фактах / В. А. Садовничий, В. А. Ва-сенин, А. А. Мокроусов, А. В. Тутубалин. М.: Изд-во МГУ, 1999.— 148 с.

23. Самарский, А. А. Математическое моделирование: Идеи. Методы. Примеры / А. А. Самарский, А. П. Михайлов, — 2-е изд. — М.: Физматлит, 2005. 320 с.

24. Соммервилл, И. Инженерия программного обеспечения / И. Соммер-вилл. — 6 изд. — М.: Вильяме, 2002. — 624 с.

25. Схрейвер, А. Теория линейного и целочисленного программирования / А. Схрейвер. М.: Мир, 1991.- Т. 2.- С. 342.

26. Шевченко, В. Н. Качественные вопросы целочисленного программирования / В. Н. Шевченко. — М.: Наука, 1995. — 190 с.

27. Aardal, К. Solving a system of linear diophantine equations with lower and upper bounds on the variables / K. Aardal, C. A. J. Hurkens, A. K. Lenstra // Math. Oper. Research.- 2000.- Vol. 25, no. 3.— Pp. 427-442.

28. Andrews, G. E. Macmahon's Partition Analysis VI: A New Reduction Algorithm / G. E. Andrews, P. Paule, A. Riese // Ann. Comb.— 2001.— Pp. 251-270.

29. Baader, F. Unification in Commutative Theories, Hilbert's Basis Theorem, and Grobner Bases / F. Baader j j J. Assoc. Comput. Mach. — 1993. — Vol. 40, no. 3. Pp. 477-503.

30. Bezem, G. Enumeration in graphs: Tech. Rep. RUU-CS-87-07 / G. Bezem, J. van Leeuwen: Dept. of Inform, and Сотр. Sciences, Utrecht Univ., 1987. P. 59.

31. CCCC — С and С++ Code Counter Электронный ресурс. — Электрон, дан. — Режим доступа: http: //сссс. sourcef orge. net/, свободный. — Загл. с экрана.

32. CESNET Электронный ресурс.: Czech nren operator.— Электрон, дан.— Режим доступа: http://www.ces.net, свободный. — Загл. с экрана.

33. Clausen, М. Efficient solution of linear Diophantine equations / M. Clausen, A. Fortenbacher // J. Symbolic Comput. 1989. - Vol. 8. - Pp. 201-216.

34. Contejean, E. An Efficient Incremental Algorithm for Solving Systems of1.near Diophantine Equations / E. Contejean, H. Devie // Inform. Corn-put.- 1994,-Vol. 113, no. 1,- Pp. 143-172.

35. Cygwin Электронный ресурс.— Электрон, дан.— Режим доступа: http: / /www. cygwin. сот/, свободный. — Загл. с экрана.

36. Domenjoud, Е. Solving systems of linear diophantine equations: an algebraic approach / E. Domenjoud // Math. Found, of Сотр. Sci. 1991 / Ed. by A. Tarlecki. Springer-Verlag, 1991. - Vol. 520. - Pp. 141-150.

37. Domenjoud, E. From Elliott-MacMahon to an Algorithm for General Linear Constraints on Naturals / E. Domenjoud, A. P. Tomas // Lect. Notes in Сотр. Sci. 1995. - Vol. 976. - Pp. 18-35.

38. Durand, A. On the complexity of recognizing the Hilbert basis of a linear Diophantine system / A. Durand, M. Hermann, L. Juban // Theoret. Comput. Sci. 2002. - Vol. 270, no. 1-2. - Pp. 625-642.

39. Exponenta.ru Электронный ресурс.: Образовательный математический сайт. — Электрон, дан. — AXOFT. — Режим доступа: http: // exponenta.ru, свободный. — Загл. с экрана.

40. Fages, F. Associative-Commutative Unification / F. Fages // J. Symbolic Comput. 1987. - Vol. 3, no. 3. - Pp. 257-275.

41. Fedyk, D. Metrics and resource classes for traffic engineering / D. Fedyk, A. Ghanwani.— Internet Draft.— 1999. http://ftp.ist.utl.pt/pub/ drafts/draft-fedyk-mpls-te-metrics-00.txt.

42. Filgueiras, M. A Fast Method for Finding the Basis of Non-negative Solutions to a Linear Diophantine Equation / M. Filgueiras, A. P. Tomas j j J. Symbolic Comput. 1995. - Vol. 19, no. 6. - Pp. 507-526.

43. Ghosh, S. Cache miss equations: a compiler framework for analyzing and tuning memory behavior / S. Ghosh, M. Martonosi, S. Malik // ACM Trans. Prog. Lang. Syst.— 1999. Vol. 21, no. 4,- Pp. 703-746.

44. Giles, F. R. Total dual integrality and integer polyhedra / F. R. Giles, W. R. Pulleyblank // Lin. Alg. Appls. 1979. - Vol. 25. - Pp. 191-196.

45. Gnu Multiple Precision Arithmetic Library Электронный ресурс.— Электрон, дан, — Режим доступа: http://gmplib.org/, свободный. — Загл. с экрана.

46. Непк, М. On minimal solutions of linear Diophantine equations / M. Henk, R. Weismantel // Contrib. Alg. Geom.— 2000,— Vol. 41, no. 1.— Pp. 49-55.

47. Ho, P.-H. A framework for service-guaranteed shared protection in WDM mesh networks / P.-H. Ho, H. T. Mouftah // IEEE Commun. Mag. -2002. Vol. 40. - Pp. 97-103.

48. Ho, P.-H. Reconfiguration of spare capacity for MPLS-based recovery in the internet backbone networks / P.-H. Ho, H. T. Mouftah // IEEE/ACM Trans. Netw. 2004. - Vol. 12, no. 1. - Pp. 73-84.

49. Huet, G. An algorithm to generate the basis of solutions to homogeneous linear Diophantine equations / G. Huet // Inform. Process. Lett. — 1978. — Vol. 7, no. 3. Pp. 144-147.

50. Johnson, D. B. Finding All the Elementary Circuits of a Directed Graph / D. B. Johnson // SIAM J. Comput. 1975. - Vol. 4, no. 1. - Pp. 77-84.

51. Korzun, D. A diophantine model of routes in structured P2P overlays / D. Korzun, A. Gurtov // SIGMETRICS Performance Evaluation Review. 2008. - Vol. 35, no. 4. - Pp. 52-61.

52. Krivoi, S. Criteria of Satisfiability for Homogeneous Systems of Linear Diophantine Constraints / S. Krivoi // PPAM '01: Proc. of Internat. Conf. on Parallel Processing and Applied Math. — London, UK: Springer-Verlag, 2002. Pp. 264-271.

53. Lankford, D. Non-negative integer basis algorithms for linear equations with integer coefficients / D. Lankford // J. Automated Reasoning. — 1989.— Vol. 5. Pp. 25-35.

54. Liu, H. A new way to enumerate cycles in graph / H. Liu, J. Wang // AICT/ICIW. IEEE Computer Society, 2006. - P. 57.

55. Liu, Y. A Fast Rerouting Scheme for OSPF/IS-IS Networks / Y. Liu, A. L. N. Reddy // Internat. Conf. on Сотр. Comm. and Netw. (ICC-CN) / Ed. by R. P. Luijten, L. A. DaSilva, A. P. J. Engbersen. IEEE, 2004. - Pp. 47-52.

56. Love, R. Linux System Programming: Talking Directly to the Kernel and С Library / R. Love. O'Reilly Media, Inc., 2007.

57. MacMahon, P. A. Combinatory analysis / P. A. MacMahon. — New York: Chelsea (USA), I960. Vol. 2. - 340 pp.

58. Mateti, P. On Algorithms for Enumerating All Circuits of a Graph / P. Mateti, N. Deo // SIAM J. Comput. 1976. - Vol. 5, no. I. - Pp. 90-99.

59. Morris, S. B. Network Management, MIBs and MPLS: Principles, Design and Implementation / S. B. Morris. — Prentice Hall PTR, 2003. 416 pp.

60. Rosen, E. MPLS Label Stack Encoding / E. Rosen, D. Tappan, G. Fe-dorkow et al.- RFC 3032 (Proposed Standard). 2001,- Updated by RFCs 3443, 4182. http://www.ietf.org/rfc/rfc3032.txt.

61. Network Analysis: Methodological Foundations / Ed. by U. Brandes, T. Er-lebach. — Springer, 2005. — Vol. 3418 of Lecture Notes in Computer Science. — P. 472.

62. Ooms, D. Overview of IP Multicast in a Multi-Protocol Label Switching (MPLS) Environment / D. Ooms, B. Sales, W. Livens et al. RFC 3353 (Informational). — 2002. http://www.ietf.org/rfc/rfc3353.txt.

63. Pan, P. Fast Reroute Extensions to RSVP-TE for LSP Tunnels / P. Pan, G. Swallow, A. Atlas. RFC 4090 (Proposed Standard). - 2005. http:// www.ietf.org/rfc/rfc4090.txt.

64. Pasechnik, D. V. On computing Hilbert bases via the Elliot-MacMahon algorithm / D. V. Pasechnik // Theoret. Comput. Sci. 2001. - Vol. 263, no. 1-2. - Pp. 37-46.

65. Pis on-С as ares, P. N-solutions to linear systems over Z / P. Pison-Casares,

66. A. Vigneron-Tenorio // Linear Algebra and its Applications. — 2004. — Vol. 384, no. 1. Pp. 135-154.

67. Pugh, W. Constraint-Based Array Dependence Analysis / W. Pugh, D. Wonnacott 11 ACM Trans. Program. Lang. Syst.- 1998.- Vol. 20, no. 3. Pp. 635-678.

68. Rockafellar, R. T. Network Flows and Monotropic Optimization / R. T. Rockafellar. — John Wiley and Sons, 1984. — 616 pp.

69. Romeijn, H. E. Generating experimental data for the generalized assignment problem / H. E. Romeijn, D. R. Morales // Oper. Res. — 2001.— Vol. 49, no. 6. Pp. 866-878.

70. Romeuf, J.-F. A polynomial algorithm for solving systems of two linear Diophantine equations / J.-F. Romeuf // Theoretical Computer Science. — 1990. Vol. 74, no. 3. - Pp. 329-340.

71. Rosen, E. Multiprotocol Label Switching Architecture / E. Rosen, A. Viswanathan, R. Callon.— RFC 3031 (Proposed Standard). 2001. http://www.ietf.org/rfc/rfc3031.txt.

72. Sebo, A. Hilbert Bases, Caratheodory's Theorem and Combinatorial Optimization / A. Sebo // Proc. of the 1st Integer Programming and Combinatorial Opt. Conf. / Ed. by R. Kannan, W. R. Pulleyblank. — University of Waterloo Press, 1990. Pp. 431-455.

73. Sharma, V. Framework for Multi-Protocol Label Switching (MPLS)-based Recovery / V. Sharma, F. Hellstrand. RFC 3469 (Informational). - 2003. http://www.ietf.org/rf c/rfc3469.txt.

74. Stamatelakis, D. IP layer restoration and network planning based on virtual protection cycles / D. Stamatelakis, W. D. Grover, S. Member // IEEE J. Selected Areas Commun. — 2000. — Vol. 18. — Pp. 1938-1949.

75. Stickel, M. E. A Unification Algorithm for Associative-Commutative Functions / M. E. Stickel // J. ACM. 1981. - Vol. 28, no. 3. - Pp. 423-434.

76. Tarjan, R. E. Enumeration of the Elementary Circuits of a Directed Graph / R. E. Tarjan // SI AM J. Comput.- 1973.- Vol. 2, no. 3.-Pp. 211-216.

77. Tomas, A. P. On Diophantine systems coming from AC-unification of higher-order patterns: exploiting symmetries / A. P. Tomas, E. Conte-jean. —1997.http://www.dcc.fс.up.pt/Pubs/TR97/dcc-97-15.ps.gz.

78. Traffic engineering with MPLS in the Internet / X. Xiao, A. Hannah, B. Bailey et al. // IEEE Net. Mag. — 2000. Vol. 14. - Pp. 28-33.

79. Wang, D. Efficient distributed bandwidth management for MPLS fast reroute / D. Wang, G. Li // IEEE/ACM Trans. Netw. 2008. - Vol. 16, no. 2. - Pp. 486-495.

80. Wang, J. IP fast reroute with failure inferencing / J. Wang, S. Nelakuditi // INM '07: Proceedings of the 2007 SIGCOMM workshop on Internet network management. New York, NY, USA: ACM, 2007,- Pp. 268-273.

81. Web-SynDic Электронный ресурс.: Project website.— Электрон, дан.

82. Петрозаводск: ПетрГУ.— Режим доступа: http://websyndic.cs. karelia.ru/site, свободный. — Загл. с экрана.