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

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

Введение

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

1.1. Обозначения и понятийный аппарат.

1.1.1. Системы неотрицательных линейных диофантовых уравнений.

1.1.2. Контекстно-свободные грамматики.

1.1.3. Дополнительные понятия и обобщения

1.1.4. Равновесие леса разбора.

1.1.5. Базовые преобразования лесов разбора.

1.2. Ассоциированная с КС-грамматикой система НЛДУ.

1.2.1. Балансовые соотношения в выводе.

1.2.2. Равновесие грамматики.

1.2.3. Построение ассоциированной системы.

1.3. Решения ассоциированной системы.

1.3.1. Решения системы и выводы в грамматике.

1.3.2. Лес решения

1.3.3. Общий вид решения.

1.3.4. Частные случаи обобщенных выводов.

Выводы к главе.

2. Эффективные алгоритмы решения некоторых классов ассоциированных систем неотрицательных линейных диофантовых уравнений 58 2.1. Анализ простейших классов ассоциированных систем.

2.1.1. Операции над множествами ВПП и обозначения

2.1.2. Системы е-АНЛДУ.

2.1.3. Системы (А, Б)-АНЛДУ и однородные АНЛДУ

2.2. Алгоритмы нахождения базиса Гильберта.

2.2.1. Системы е-АНЛДУ.

2.2.2. Алгоритм латинской композиции.

2.2.3. Алгоритм фиктивных правил.

2.3. Анализ вычислительной сложности и тестирование.

2.3.1. Наихудший случай.

2.3.2. Тестирование.

2.3.3. Экспериментальная оценка эффективности алгоритмов

2.4. Алгоритмы нахождения одного решения

Выводы к главе.

3. Математическая модель стационарной агрегирующей структуры нагрузки канала Интернет

3.1. Задача построения модели структуры нагрузки

3.2. Дискретная линейная модель структуры нагрузки.

3.2.1. Однородные линейные дискретные зависимости

3.2.2. Математическая модель.

3.2.3. Интерпретации математической модели.

Системой неотрицательных линейных диофантовых уравнений (система НЛДУ) называется линейная система, коэффициентами которой являются произвольные целые, а решения рассматриваются только в неотрицательных целых числах. НЛДУ и их системы представляют известный объект математических исследований. Первые серьезные результаты в этой области были получены еще в Древней Греции [3].

Традиционно исследование решений уравнений в неотрицательных целых числах проводилось в рамках теории чисел [8], диофантова [71] и комбинаторного [88] анализов. В последние десятилетия существенно возросшая потребность в практически полезных методах решения различных целочисленных задач, в том числе, систем НЛДУ, стимулировала развитие теорий целочисленных полиэдров и вполне двойственной целочисленности [40], опирающихся на введенное F. Giles и W. Pulleyblank [77] понятие базиса Гильберта (см. также [40,100]). Развивались и соответствующие методы построения эффективных вычислительных алгоритмов [63].

В результате была выявлена центральная роль базиса Гильберта в методах решения систем НЛДУ, т. к. для них существует единственный такой базис, описывающий множество решений компактным образом. Методы и алгоритмы нахождения базиса Гильберта имеют многочисленные теоретические и практические приложения в таких областях математики, кибернетики и информатики, как теория чисел [8,78], исследование операций и целочисленное линейное программирование [19,37,40,47], анализ сложности алгоритмов [40,85,93], автоматизация дедуктивных построений [52,63,103], управление памятью и параллельными вычислениями [70,102] и ряд других.

Основными задачами численного решения систем НЛДУ являются: 1) определение совместности, 2) нахождение некоторого решения, 3) нахождение базиса Гильберта. В настоящее время в работах Е. В. Elliot [71],

G. Huet [80], E. Contejean [64], M. Clausen и A. Fortenbacher [62], E. Domenjoud [67], M. Filgueiras и A. Tomás [106] и ряде других предложено много алгоритмов для решения этих задач. Эти алгоритмы основаны на различных математических методах: динамическое программирование [32,54,66,93], целочисленное линейное программирование [19,32,40,47,48], элементарные преобразования матриц [44,87], приведение базисов в решетках [45,46], лексикографический и другие виды перебора [32,40,70,80,97], последовательное покомпонентное построение решений [51,62,64,65], логическое программирование [50,52], линейная алгебра и производящие функции [67,68,71,88,94,97], теория сравнений [14,75,104-106], теория конечных автоматов [55].

Эти алгоритмы ориентированы на решение произвольных НЛДУ. Их вычислительная сложность в наихудшем случае больше, чем полиномиальная, и зависит как от размерностей системы, так и от абсолютных величин коэффициентов уравнений [32,40,67,85,97]. Теория сложности алгоритмов относит задачи численного решения произвольных систем НЛДУ к трудным вычислительным проблемам.

Известно, что задача нахождения некоторого решения НЛДУ эквивалентна задаче ЦЛП и является NP-полной [40,93]. Задача нахождения базиса Гильберта представляется еще более сложной (overNP), поскольку число элементов в базисе может неполиномиально зависеть и от размерностей системы, и от абсолютных величин ее коэффициентов [14,15, 39, 42, 70]. Задача определения, будет ли заданное решение базисным, является coNP-полной [69,78,85,100]. Задача подсчета числа элементов в базисе Гильберта системы НЛДУ является #Р-сложной и принадлежит классу #NP [79,85]. В тоже время, многие вопросы сложности вычисления базиса Гильберта до сих пор остаются открытыми [85,87].

Итак, в общем случае, решение системы НЛДУ является чрезвычайно трудоемкой задачей и использование упомянутых выше алгоритмов может оказаться неприемлемым для многих практически важных задач. Естественным подходом в такой ситуации является выделение классов систем НЛДУ, допускающих построение эффективных алгоритмов решения. Так, многие линейные задачи на потоки в сетях эффективно решаются методами ЦЛП на основе свойства полной унимодулярности [32,40]. Ограничение на число появлений неизвестных в уравнениях системы до двух переводит задачу подсчета числа элементов в базисе Гильберта из класса #NP в класс [79].

В работе [74] португальских математиков М. Filgueiras и A. Tomás показано, как по формальной КС-грамматике можно построить некоторую систему НЛДУ, которую мы называем ассоциированной системой НЛДУ (системой АНЛДУ). Некоторые решения системы АНЛДУ соответствуют определенным выводам в грамматике. Это позволяет использовать методы синтаксического анализа для решения таких систем, если будет решена проблема описания решений системы, в том числе и базисных, в терминах грамматических выводов, которая на данный момент оставалась открытой. Сам метод [74] с полным основанием может быть назван синтаксическим.

Этот метод позволяет получать широкий класс систем НЛДУ специального вида. Например, в этот класс попадают некоторые системы, основанные на матрице инциденций графа и обладающие свойством унимодулярности. Однако, в общем случае, системы, построенные по методу [74], не обладают свойством унимодулярности, что не позволяет эффективно использовать для их решения методы ЦЛП. Кроме того, свободные члены рассмотренных в [74] систем АНЛДУ имеют специальный вид. В частности, этот метод не позволяет получать однородные системы, которые играют ключевую роль во многих приложениях. Отметим также, что в [74] не представлены конкретные алгоритмы решения предложенных систем АНЛДУ.

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

Одной из важных областей приложения эффективных алгоритмов нахождения базиса Гильберта является, на наш взгляд, проблема моделирования элементов сети Интернет с целью их анализа и планирования. Хороший обзор работ по этой проблеме дают Т. Monk и К. Claffy [90,91], где сказано: «Поскольку зависимость всех стран и мирового сообщества в целом от Интернет возрастает, то крайне важно разработать механизмы, которые бы позволили планировать и анализировать ее инфраструктуру, чтобы обеспечить эффективное масштабирование Интернет».

Важнейшей задачей исследования вычислительных систем является планирование их мощности на основе математических моделей производительности с целью обеспечения приемлемого уровня качества функционирования. Масштаб и сложность Интернет крайне затрудняют непосредственное применение традиционных методов анализа производительности [82,89] и предопределяют необходимость предварительного проведения структурной декомпозиции Интернет.

В работе [12] обоснована двухуровневая декомпозиция Интернет на системы локальных поставщиков услуг (ЛПУ), одной из важнейших подсистем которых является канал связи ЛПУ с внешним миром (далее — канал).

Классическая задача планирования мощности состоит в предсказании момента времени насыщения системы и определения наиболее экономически оправданного способа избежать этого насыщения так долго, как это возможно. Согласно основополагающим работам S. F. Lam, D. Ferrary и других исследователей [72,73,82,86,89], любой проект планирования мощности состоит из пяти основных этапов: описание текущего состояния системы и среды, в которой она работает; описание рабочей нагрузки системы; идентификация модели производительности системы; предсказание рабочей нагрузки; предсказание будущей производительности системы.

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

Построение модели нагрузки всегда начинается с выполнения разбиения нагрузки на некоторые классы и вычисления основных статистик для каждого класса. Часто разбиение выполняют методами кластерного анализа [99]. Для предсказания поведения нагрузки в зависимости от интересующих исследователя параметров используют классические методы математического моделирования, например, марковские и регрессионные модели. Обзор можно найти в [10,16,49,53,76,98].

В диссертационной работе мы рассматриваем задачу построения математической модели нагрузки канала. Очевидно, что она может быть адекватно решена только на основе анализа данных мониторинга трафика канала. Поскольку современные ЛПУ обслуживают тысячи и даже десятки тысяч пользователей, то трафик его каналов характеризуется как очень большим объемом, так и весьма сложной структурой. Наши исследования трафика базового маршрутизатора Федерального Петрозаводского узла (ФПУ) RUNNet (см. таблицу 2 на с. 140) показывают, что его полезная средняя пропускная способность равна 1.1 Mbps, а за пять месяцев наблюдений маршрутизатор обслужил почти 2.5 миллиона уникальных IP-адресов. Отметим также, что с переходом в недалеком будущем на высокопроизводительные сети [11] объемы трафика возрастут на порядки.

Все это означает, что разумный анализ трафика может быть выполнен только на основе его агрегирования и структурирования. При этом, прежде всего необходим обоснованный выбор элементарных единиц трафика. Выполнение анализа трафика с объемами, указанными выше, на уровне байтов и пакетов представляется практически нереализуемым. В данной работе мы опираемся на результаты интенсивных исследований последних лет по потокам данных в Интернет [56,59-61,83], активно продвигаемых в виде программных продуктов, в частности фирмой CISCO [92]. В диссертационной работе в качестве элементарных единиц трафика канала принят частный случай потока данных — TCP-соединение и его эвристические аналоги (согласно технологии CISCO NetFlow) для протоколов UDP и ICMP.

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

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

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

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

Учитывая вышеизложенное, цель диссертационного исследования может быть сформулирована следующим образом.

1. Развитие синтаксического метода построения систем НЛДУ для расширения класса получаемых систем АНЛДУ и разработка, обоснование, реализация и тестирование эффективных алгоритмов решения этих систем на основе методов синтаксического анализа.

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

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

Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка использованной литературы (107 наименований) и приложения, имеет общий объем 185 машинописных страниц, включая 11 страниц приложения, содержит 27 рисунков и 10 таблиц.

Выводы к главе

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

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

2. На основе экспериментальных измерений нагрузки базового маршрутизатора ФПУ RUNNet на длительном периоде времени получено, что: модельное допущение о существовании стационарных масштабируемых линейных зависимостей, определяющих компактную структуру нагрузки не противоречит экспериментальным данным; при фиксированном уровне агрегации число обнаруживаемых источников можно считать константой; при фиксированной длине периода наблюдений число обнаруживаемых источников имеет порядок роста о(М) при N—>00, где N — число промежутков разбиения этого периода; отобранные главные источники оказывают существенное влияние на формирование нагрузки (до 90-95%) независимо от времени и выбранного уровня агрегации; число агрегированных источников, требуемых для приемлемого уровня точности (80-90%) получаемой модели нагрузки, невелико.

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

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

Заключение

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

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

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

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

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

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

1. Айвазян С.А., Мхитарян B.C. Прикладная статистика и основы эконометрии: Учебник для вузов. — М.: ЮНИТИ, 1998. — 1022 с.

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

3. Башмакова И. Г. История диофантова анализа от Диофанта до Ферма. — М.: Наука, 1984. — 261 с.

4. Богоявленский Ю. А., Корзун Д. Ж. Общий вид решения системы линейных диофантовых уравнений, ассоциированной с контекстно-свободной грамматикой // Труды Петрозаводского государственного университета. Сер. "Прикладная математика и информатика". Вып. 6.

5. Петрозаводск: Изд-во ПетрГУ, 1997. — С. 79-94.

6. Богоявленский Ю. А., Корзун Д. Ж. Гибкая обработка данных о ТСР-соединениях // Труды Петрозаводского государственного университета. Сер. "Прикладная математика и информатика". Вып. 8. — Петрозаводск: Изд-во ПетрГУ, 2000. С. 151-176.

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

8. Братчиков И. JI. Синтаксис языков программирования. — М.: Наука, 1975. — 232 с. (Сер. «Библиотечка программиста»)

9. Васенин В. А. Российские академические сети и Internet (Состояние, проблемы, решения) / Под ред. проф. В. А. Садовничего. — М.: Изд-во РЭФИА, 1997. 173 с.

10. Васенин В. А. Высокопроизводительные научно-образовательные сети России. Настоящее и будущее. — М.: Изд-во МГУ, 1999. — 32 с.

11. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основания информатики : Пер. с англ. — М.: Мир, 1998. — 702 с.

12. Исраилов М. Н. Нахождение числа решений линейных диофантовых уравнений и их приложения в теории инвариантных кубатурных формул II Сибирский математический журнал. — 1981. Т. XXII. № 2. С. 121-136.

13. Калашников В. В., Рачев С. Т. Математические методы построения стохастических моделей обслуживания. — М.: Наука, 1988. — 312 с.

14. Канторович JI. В. О некоторых новых подходах к вычислительным методам и обработке наблюдений // Сиб. мат. журнал. — 1962. — Т. 3. № 5. С. 701.

15. Кнут Д. Е. Искусство программирования для ЭВМ : В 3 т. / Пер. с англ. — М.: Мир, 1978. Т. 3: Сортировка и поиск. — 844 с.

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

17. Корзун Д. Ж. О существовании порождающей КС-грамматики для произвольной линейной диофантовой системы // Труды Петрозаводского государственного университета. Сер. "Математика". Вып. 6. — Петрозаводск: Изд-во ПетрГУ, 1999. — С. 34-40.

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

19. Мартынов А. П. и др. Линейные модели с взаимозависимыми параметрами и их применение / А. П. Мартынов, Е. А. Салимоненко, JI. И. Ван-чухина, JI. А. Калашникова. — Уфа: Изд-во «Реактив», 1998. — 204 с.

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

21. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность : Пер. с англ. — М.: Мир, 1985. — 512 с.

22. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хоп-крофт, Дж. Ульман; Пер. с англ. А. О. Слисенко; Под ред. Ю. В. Ма-тиясевича. — М.: Мир, 1979. — 536 с.

23. Романовский И. В. Дискретный анализ : Учеб. пособие. — СПб.: Невский диалект, 2000. — Издание 2-е, исправленное. — 240 с.

24. Сакович В. А. Исследование операций (детерминированные методы и модели) : Справочное пособие. — М.: Минск: Выпг. шк., 1984. — 256 с.

25. Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука, 1989. — 432 с.

26. Сертоз С. О числе решений диофантова уравнения Фробениуса // Дискретная математика. — 1998. Т. 10. Вып. 2. — С. 62-71.

27. Схрейвер А. Теория линейного и целочисленного программирования : Пер. с англ. Т.1. -М.: Мир, 1991. -360 е.; Т.2. -М.: Мир, 1991. —342 с.

28. Тюрин Ю. Н., Макаров А. А. Статистический анализ данных на компьютере. — М.: ИНФРА-М, 1998. 528 с.

29. Фрумкин М. А. О числе натуральных решений системы линейных уравнений // Математические заметки. — 1980. Т. 28. № 3. — С. 321-334.

30. Чернецкий В. И. Математическое моделирование стохастических систем. — Петрозаводск: Изд-во Петрозаводского гос. ун-та, 1994. — 488 с.

31. Черникова Н. В. Алгоритм для нахождения общей формулы для неотрицательных решений систем линейных уравнений // ЖВМ и МФ. 1964. Т. 4. - С. 733-738.

32. Aardal K., Weismantel R., Wolsey L. Non-standard approaches to integer programming : Research Report / Utrecht University (Netherlands); — UU-CS-1999-41. — 1999. — 64 p.http : //www. cs. ruu.nl/research/t echreps/UU-CS-1999-41. html

33. Adas A. Traffic Models in Broadband Networks // IEEE Communications Magazine. — 1997. Vol. 35. — PP. 82-89.

34. Ajili F. Constraints Diophantiennes Linéaires: résolution et coopération inter-résolveurs : Doctorale Thèse. — Université Nancy (France), 1998.137 p.

35. Ajili F., Contejean E. Avoiding slack variables in the solving linear dio-phantine equations and inequations // Theoretical Computer Science. — 1997. Vol. 173. No. 1. — PP. 183-208.

36. Ajili F., Lock H. C. R. Integrating Constraint Propagation in Complete Solving of Linear Diophantine Systems // Proceedings of Principles of Declarative Programming (ALP/PLILP'98). Springer-Verlag, 1998. LNCS 1490. — PP. 463-480.

37. Babic G., Vandalore B., Jain R. Analysis and Modeling of Traffic in Modem Data Communication Networks : Technical Report / Ohio State University (USA); — OSU-CISRC-1 /98-TR02. — 1998. — 35 p.http://www.cis.ohio-state.edu/~jain/papers/trfmodel.htm

38. Bellman R. Notes on the theory of dynamic programming, IV — maximization over discrete stes f ( Naval Research Logistics Quarterly. — 1965. Vol. 3. — PP. 67-70.

39. Boudet A., Comon H. Diophantine Equations, Presburger Arithmetic and Finite Automata // Proceedings of the 21st International Colloquim on Trees in Algebra and Programming (CAAP'96), 1996. — PP. 30-43.

40. Brownlee N. Traffic Flow Measurement: Experiences with NeTraMet. — IETF RFC 2123 (informational). — March 1997.

41. Brownlee N. SRL: A Language for Describing Traffic Flows and Specifying Actions for Flow Groups. — IETF RFC 2723 (informational). — October 1999.

42. Brownlee N., Mills C., Ruth G. Traffic Flow Measurement: Architecture.

43. TF RFC 2722 (informational). — October 1999.

44. Claffy K. Internet Traffic Characterization-. PhD Thesis. — University of California (USA), 1994. — 121 p.

45. Claffy K., Braun H.-W., Polyzos G. C. A Parameterizable Methodology jor Internet Traffic Flow Profiling // IEEE Journal on Selected Areas in Communications, Special Issue on the Global Internet. — 1995. Vol. 13. No. 8. — PP. 81-94.

46. Clausen M., Fortenbacher A. Efficient Solution of Linear Diophantine Equations J J Journal of Symbolic Computation. — 1989. Vol. 8. No. 1&2.1. PP. 201-216.

47. Comon H., Dincbas M., Jouannaud J.-P., Kirchner C. A Methodological View of Constraint Solving // Constraints. — 1999. Vol. 4. No. 4.1. PP. 337-361.

48. Contejean E. Solving linear diophantine constraints incrementally //In David S. Warren (ed.), Proceedings of the 10th International Conference on Logic Programming. — Budapest (Hungary): The MIT Press, 1993.1. PP. 532-549.

49. Contejean E., Devie H. An efficient algorithm for solving systems of diophantine equations // Information and Computation. — 1994. Vol. 113. No. 1. — PP. 143-172.

50. Dantzig G. B. Discrete-variable extremum problems // Operation Research. — 1957. Vol. 5. — PP. 266-277.

51. Domenjoud E. Solving Systems of Linear Diophantine Equations: An Algebraic Approach // In U. Tarlecki (ed.), Proceedings of 16th International Simposium on Mathematical Foundations of Computer Science. SpringerVerlag, 1991. LNCS 520. — PP. 141-150.

52. Domenjoud E., Tomas A. From Elliott-MacMahon to an algorithm for general constraints on naturals // In U. Montanari, F. Rossi (eds.), Principles and Practice of Constraint Programming (CP'95). Springer-Verlag, 1995. LNCS 976. — PP. 18-35.

53. Durand A., Hermann M., Juban L. On the complexity of recognizing the

54. Elliot E. B. On linear homogeneous diophantine equations / Quartely Journal of Pure and Applied Maths. — 1903. Vol. 136.

55. Ferrary D. Computer Systems Performance Evaluation. — New Jersey (USA): Prentice-Hall Inc., 1978. — 543 p.

56. Ferrary D., Serazzi G., Zeigner A. Measurement and Tuning of Computer Systems. — New Jersey (USA): Prentice-Hall Inc., 1983. — 514 p.

57. Filgueiras M., Tomás A. P. A fast method for finding the basis of nonnegative solutions to a linear Diophantine equation // Journal of Symbolic Computation. — 1995. Vol. 19. — PP. 507-526.

58. Frost V.S., Melamed B. Traffic Modeling for Telecommunications Networks //IEEE Communications Magazine.—1994. Vol.32. No. 3. —PP. 70-81.

59. Giles F., Pulleyblank W. Total dual integrality and integer polyedra // Linear algebra and its applications. — 1979. No. 25. — PP. 191-196.

60. Huet G. An algorithm to generate the basis of solutions to homogenous linear diophantine equations // Information Processing Letters. — 1978. Vol. 3. No. 7. — PP. 144-147.

61. Jacobson V., Leres C., McCanne S. TCPDUMP — Dump Traffic on a Network. Lawrence Berkeley National Laboratory, Network Research Group, ftp://ftp.ee.lbl.gov/tcpdump.tau:.Z

62. Jain R. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. — New York (USA): John Wiley k Sons, Inc., 1991. — 720 p.

63. Jain R., Routhier S. A. Packet trains—measurement and a new model for computer network traffic // IEEE Journal on Selected Areas in Communications. — September 1986. — PP. 986-995.

64. Jelenkovic P. R. The Effect of Multiple Time Scales and Subexponentiality on the Behavior of a Broadband Network Multiplexer. PhD Thesis. — Columbia University (USA), 1996. — 197 p.

65. Juban L. Sur les Problèmes de Complexité en Déduction Automatique: Base de Hilbert, Modèles Uniques et Minimaux: Doctorale Thèse. — Université Nancy (France), 1999. — 118 p.

66. Lam S. F., Chan K. H. Computer Capacity Planning. Theory and Practice. — Academic Press Inc., 1987. — 214 p.

67. Lankford D. Non-negative Integer Basis Algorithms for Linear Equations with Integer Coefficients J. Journal of Automated Reasoning. — 1989. Vol. 5. — PP. 25-35.

68. MacMahon P. A. Combinatory Analysis. New York: Chelsea (USA), 1960. Vol. 2. — 340 p.

69. Menasce D. A., Almedia V. A. F., Dowdy L. W. Capacity Planning and Performance Modeling: Prom Mainframes to Client-Server Systems. — New Jersey (USA): Prentice-Hall Inc., 1994. — 412 p.

70. Monk T., Claffy K. A Survey of Internet Statistics/Metrics Activities. — San Diego (USA): University of California (National Laboratory for Applied Network Research, NLANR), 1996.http: //www. caida. org/outreach/papers/metr icsurvey. html

71. NetFlow Services and Applications: White Paper. Cisco Systems Inc. —2000. http: //www. cisco. com/warp/public/cc/pd/iosw/ioft/neflet/ tech/napp swp.htm

72. Papadimitriou C. H. On the complexity of integer programming // Journal of the ACM. — 1981. Vol. 28. — PP. 765-768.

73. Pasechnik D. V. On computing Hilbert bases via the Elliot—MacMahon algorithm // Theoretical Computer Science. — 2001. Vol. 263. — PP. 37-46.

74. Paxson V., Floyd S. Wide-Area Traffic: The Failure of Poisson Modeling // IEEE ACM Transactions on Networking. — 1995. Vol. 3. No. 3.1. PP. 226-244.

75. Paxson V., Floyd S. Why We Don't Know How To Simulate The Internet j j Proceedings of the 1997 Winter Simulation Conference, December 1997. http://www.icir.org/floyd/papers/wsc97.ps

76. Pottier L. Minimal solutions of linear diophantine systems: bounds and algorithms // Proceedings of the 4th International Conference on Rewriting Techniques and Applications (RTA'91), Como (Italy). — 1991.1. PP. 162-173.

77. Raatikainen K. E. E. Modelling and analyzing techniques for capacity planning: PhD Thesis. —University of Helsinki (Finland), 1988. —175 p.

78. Raatikainen K. E. E. Cluster Analysis and Workload Classification // Performance Evaluation Review. — 1993. Vol. 20. No. 4. — PP. 24-30.

79. Sippu S., Soisaloin-Soininen E. Parsing Theory: Languages and Parsing. EATCS Monographs on Theoretical Computer Science. Vol. 15. SpringerVerlag, 1988. — 228 p.

80. Sogno J.-C. Analysis of Standard and New Algorithms for the Integer and Linear Constraint Satisfaction Problem : Research Report / INRIA (Prance); — RR-1828. — 1998. — 50 p.http://www.inria.fr/rrrt/rr-1828.html

81. Stickel M. A Unification Algorithm for Associative-Communicative Functions // Journal of the ACM. — 1981. Vol. 28. No. 3. — PP. 423-434.

82. Tomás A. P., Filgueiras M. Solving Linear Diophantine Equations : Technical Report / LIACC, Universidate do Porto (Portugal); — TR 374822.1993. — 16 p. ftp://ftp.cs.unh.edu/pub/csp/archive/papers/ nato/ESTproceed/tomas.ps

83. Tomás A. P., Filgueiras M. An algorithm for solving systems of linear Diophantine equations in naturals // In E. Costa, A. Cardoso (eds.), Progress in Artificial Intelligence (EPIA'97). Springer-Verlag, 1997. LNAI 1323.1. PP. 73-84.

84. Willinger W., Paxson V. Discussion of ''Heavy Tail Modeling and Tele-traffic Data" by S.R. Resnick // Annals of Statistics. — 1998. Vol. 25. No. 5. — PP. 1805-1869.