Эффективные алгоритмы и программные средства реализации линейных диофантовых моделей сетей ЭВМ тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Кулаков, Кирилл Александрович

• Кулаков, Кирилл Александрович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Кулаков, Кирилл Александрович

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

Введение

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 превосходит по эффективности ранее известные алгоритмы и может применяться на практике в задачах управления сетевыми системами.

Список литературы диссертационного исследования кандидат физико-математических наук Кулаков, Кирилл Александрович, 2009 год

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, свободный. — Загл. с экрана.