Содержание к диссертации
Введение
Глава 1. Обзор и анализ существующих методов уменьшения размера таблиц маршрутизации 11
1. 1. Маршрутизация, архитектура маршрутизаторов 11
1.2. Обзор методов оптимизации поиска в таблицах маршрутизации 13
1.3. Методы уменьшения размера таблиц маршрутизации 17
1.4. Методы минимизации булевых функций большой размерности 23
1.4.1 Классификация алгоритмов минимизации булевых функций 23
1.4.2 Алгоритмические сложности решения задачи минимизации ДНФ 24
1.4.3 Точные алгоритмы минимизации ДНФ 26
1.4.4 Приближенные алгоритмы 34
Выводы 37
Глава 2. Разработка метода уменьшения таблиц маршрутизации в ІР-сетях 39
2.1. Метод уменьшения размера таблиц маршрутизации 39
2.2 Точный алгоритм минимизации булевых функций в классе ДНФ 45
2.2.1 Двоичные диаграммы решения 46
2.2.2 Генерация всех простых импликант булевой функции 51
2.2.3 Упрощение матрицы покрытия 53
2.2.4 Построение минимального покрытия 58
2.3 Приближенный алгоритм минимизации ДНФ 62
Выводы 65
Глава 3. Компьютерное моделирование и экспериментальная оценка разработанного метода уменьшения таблиц маршрутизации 67
3.1. Выбор средств разработки программного пакета 67
3.2 Программная реализация разработанного метода уменьшения таблиц маршрутизации 69
3.2.2 Описание программного продукта 73
3.3 Применение разработанных методов минимизации ДНФ для уменьшения размера таблиц маршрутизации 77
3.4. Оценка зависимости производительности маршрутизатора от размера таблицы маршрутизации 82
3.5 Экспериментальная оценка эффективности предложенных алгоритмов для задач из набора MCNC Benchmarks 888
Выводы 90
Заключение 91
Список литературы 93
Приложение 101
- Обзор методов оптимизации поиска в таблицах маршрутизации
- Методы минимизации булевых функций большой размерности
- Точный алгоритм минимизации булевых функций в классе ДНФ
- Программная реализация разработанного метода уменьшения таблиц маршрутизации
Введение к работе
Актуальность исследования. Неотъемлемой частью процесса
построения быстродействующих сетей является разработка эффективных
схем хранения и поиска записей в таблицах маршрутизации (ТМ). Одним из
следствий быстрого роста Internet стало значительное увеличение размера
таблиц маршрутизации. Данный факт, а также ограниченность ресурсов
программного и аппаратного обеспечения, существенно затрудняют
возможность их эффективной обработки. Исследователями было предложено
большое количество схем для увеличения скорости поиска в таблицах
маршрутизации. Алгоритмические методы включают в себя: локальный
поиск, двоичный поиск, использование специальных структур данных
(бинарные деревья, трие), хеширование и ряд других. Основным недостатком
данных подходов является то, что они требуют нескольких обращений к
памяти. Требования к производительности современных сетей являются
очень высокими, в то время как время отклика современных архитектур
памяти ограничивают возможное количество обращений к памяти. Одним из
наиболее распространенных и перспективных аппаратных решений является
тернарная ассоциативная память (ТСАМ). Главной особенностью ТСАМ
является то, что адресация осуществляется на основе содержания данных,
поиск нужной записи, при этом, может быть осуществлен за одно обращение
к памяти. Значительное число исследований, посвященных проблеме
повышения эффективности обработки таблиц маршрутизации,
ориентировано на использование данной аппаратной реализации и основано
на методах сжатия таблиц маршрутизации [87]. Уменьшение таблиц
маршрутизации позволяет повысить скорость поиска нужной записи,
использовать память меньшего размера, а также снизить энергопотребление
маршрутизатора. Современное состояние дел в данной области знаний во
многом основано на работах Х.Лиу (Н. Liu)[56], С. GreprHoy(S.Stergiou)[83],
В. Равикумара (V. Ravikumar)[74], Р. Гуо (R.Guo) и Ж. Дельгадо-Фриаса (J.
Delgado-Frias)[45]. Отечественные авторы, например, В. Г. Олифер и Н. А. Олифер[9], внесли вклад в развитие теоретических основ проблем эффективной маршрутизации. Большинство существующих методов сжатия таблиц маршрутизации основано на сведении данной проблемы к задаче минимизации булевых функций в классе дизъюнктивных нормальных форм. При этом используются алгоритмы минимизации, которые были разработаны в первую очередь для оптимизации интегральных схем и не учитывают специфику данной задачи. В связи с этим, возможность их практического применения ограничена задачами небольшой размерности.
Объектом исследования в работе является обработка таблиц маршрутизации в IP-сетях. Предметом исследования являются методы сокращения размеров таблиц маршрутизации, как средства повышения скорости обработки пакетов и снижения затрат памяти для хранения информации о маршрутах в сети.
Цели и задачи исследования. Целью настоящей работы является разработка быстродействующего метода уменьшения размера таблиц маршрутизации, позволяющего уменьшить время поиска записей, снизить энергопотребление маршрутизатора и сократить аппаратные затраты. Для выполнения данной цели необходимо решить следующие задачи:
анализ существующих методов сокращения таблиц маршрутизации;
построение математической модели таблиц маршрутизации;
разработка быстродействующих методов сокращения таблиц маршрутизации;
экспериментальное исследование эффективности предлагаемых алгоритмов.
Методы исследования. При решении поставленных задач использовались методы математического моделирования, дискретной оптимизации, теории графов, линейного программирования.
Научная новизна
1. Предложен подход к решению задачи оптимизации размеров таблиц маршрутизации, использующий для представления ГР-адресов импликанты булевых функций. В основу подхода положено применение:
двоичных диаграмм решения для совместной обработки импликант,
метода ветвей и границ для ограничения перебора в пространстве возможных решений,
двухуровневого представления импликант для повышения скорости поиска в множестве всех исходных импликант,
эвристического алгоритма выборочной генерации простых импликант булевых функций.
Сочетание составных частей подхода по определенным правилам позволяет
строить эффективные алгоритмы уменьшения размера таблиц
маршрутизации.
Разработан точный алгоритм построения минимальной дизъюнктивной нормальной формы булевых функций, соответствующих множествам записей таблицы маршрутизации, основанный на использовании двоичных диаграмм решения и метода ветвей и границ, отличающийся более высокой скоростью работы, по сравнению с известными подходами.
Разработан приближенный алгоритм построения минимальной дизъюнктивной нормальной формы булевых функций, соответствующих множествам записей таблицы маршрутизации, основанный на двухуровневом представлении множества импликант функции и эвристическом алгоритме генерации простых импликант. Показана возможность применения предложенного алгоритма для сокращения размера таблиц маршрутизации большой размерности в режиме реального времени.
Основные положения, выносимые на защиту
Алгоритмическая модель процесса уменьшения размера таблиц маршрутизации, основанная на использовании разработанных алгоритмов минимизации булевых функций и метода ветвей и границ.
Метод уменьшения таблиц маршрутизации, основанный на использовании эвристического алгоритма выборочной генерации простых импликант булевых функций, который обладает большей скоростью вычислений, по сравнению с известными подходами, и позволяет обрабатывать таблицы большой размерности в режиме реального времени.
Программный комплекс, реализующий разработанные алгоритмы, компьютерное моделирование и экспериментальная оценка эффективности методов уменьшения таблиц маршрутизации.
Практическая и теоретическая значимость исследований. Результаты диссертационной работы могут найти применение при разработке программных систем, предназначенных для повышения экономичности маршрутизаторов. Разработанные алгоритмы также могут быть использованы в системах автоматизации проектирования интегральных схем.
Достоверность результатов обеспечивается строгостью постановок задач, корректностью выбранного математического аппарата и подтверждается результатами компьютерного моделирования.
Личный вклад автора. Постановка задач исследования осуществлена совместно с научным руководителем А.А.Смагиным. Основные теоретические и практические исследования проведены автором самостоятельно.
Апробация работы проведена на шестой всероссийской научно-
практической конференции (с участием стран СНГ) «Современные проблемы
создания и эксплуатации радиотехнических систем» (Ульяновск, 2009) и
ежегодных научно-технических семинарах кафедры
«Телекоммуникационные технологии и сети» УлГУ.
Публикации. По теме диссертации опубликовано 7 работ, в том числе 2 - в изданиях из перечня ВАК.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка используемой литературы из 89 наименований и одного приложения. Основной текст диссертации изложен на 100 страницах.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка используемой литературы из 89 наименований и одного приложения. Основной текст диссертации изложен на 97 страницах.
Первая глава посвящена обзору и анализу существующих методов уменьшения размера таблиц маршрутизации. Отмечается, что большинство методов, приводимых в литературе, основано на минимизации булевых функций. Построена классификация методов сжатия таблиц маршрутизации. На основе проведенного анализа показано, что возможность использования известных схем уменьшения размера таблиц маршрутизации ограничена задачами небольшой размерности.
Вторая глава посвящена разработке метода уменьшения размера таблиц маршрутизации в IP-сетях. Метод основан на представлении адресной части таблиц маршрутизации с помощью булевых функций. Разработаны два алгоритма минимизации булевых функций — точный, основанный на применении двоичных диаграмм решения и метода ветвей и границ, и приближенный, главными чертами которого является использование двухуровневой структуры данных для представления импликант и эвристического алгоритма выборочной генерации простых импликант.
В третьей главе рассматриваются вопросы компьютерной реализации предложенных алгоритмов, а также полученные экспериментальные оценки их качества. Приводится описание разработанного программного пакета. Показано, что предложенные методы минимизации дают выигрыш в быстродействии по сравнению с существующими подходами. Отмечена возможность применения разработанного приближенного алгоритма для
сокращения размера таблиц маршрутизации в режиме реального времени. Результаты компьютерного моделирования показывают, что за счет использования предлагаемого метода достигается повышение скорости поиска записей в таблице маршрутизации, а также сокращается его энергопотребление.
В заключении изложены основные результаты диссертационного исследования.
Приложение 1 содержит листинг программной реализации разработанных алгоритмов.
Обзор методов оптимизации поиска в таблицах маршрутизации
Размер таблиц маршрутизации увеличивается с каждым годом и, на сегодняшний день, может превышать 300000 записей. В связи с этим, значительный интерес представляют методы повышения эффективности обработки таблиц маршрутизации. Предложенная в 1992 технология бесклассовой междоменной маршрутизации CIDR (Classless Inter-Domain Routing)[9,87] отчасти позволила решить данную проблему.
В традиционной (классовой) маршрутизации длина маски подсети должна равняться 8, 16 или 24 разрядам. Данный подход существенно затруднял процесс выделения новых адресов, а также привел к быстрому росту таблиц маршрутизации. СПЖ снимает ограничение на длину маски подсети. Использование этого метода обусловило иерархическую структуру адресного пространства - например, провайдерам соответствуют короткие IP-префиксы, при этом они могут предоставить клиентам IP-префиксы большей длины. CIDR использует нотацию следующего вида для записи IP-префиксов : 1Р-адрес/длина маски. Например, 202.112.56.0/24.
Несмотря на то, что введение CIDR значительно повысило эффективность использования ресурса IP-адресов, начиная с 1998-99 гг., стало очевидным, что данная технология не позволяет в полной мере остановить экспоненциальный рост таблиц маршрутизации (см. рис. 1. 1[26]). В связи с этим, на первый план выходит разработка эффективных методов хранения и управления таблицами маршрутизации.
При этом, одной из наиболее важных задач является повышение скорости поиска в таблицах маршрутизации. Рассматриваемые в литературе методы [46,68,86,87] можно условно разделить на аппаратные и программные [19] (рис. 1.2). Программные методы, как правило, основаны на алгоритмическмх подходах - двоичном поиске, хешировании и др., либо на использовании специальных структур данных - трие, бинарные деревья. Данные схемы требуют нескольких обращений к памяти [56], что существенно затрудняет возможность их использования в быстродействующих сетях.
Большинство существующих аппаратных решений основано на использовании специализированных интегральных схем (ASIC), либо контентно-адресуемой памяти (САМ).
Метод, предлагаемый в диссертации, в первую очередь, ориентирован на аппаратную реализацию в виде САМ [56,58]. Упрощенная схема данной разновидности памяти [82] приведена на рис. 1.3. Схема работы САМ принципиально отличается от функционирования обычной машинной памяти (памяти с произвольным доступом - RAM) — RAM возвращает данные, хранящиеся по определенному адресу, в то время как САМ проверяет -содержатся ли в ней запрашиваемые данные. В случае САМ адресация осуществляется на основе содержания данных, операция поиска, при этом, может быть осуществлена за одно обращение к памяти. В процессе поиска входное слово одновременно сравнивается со всеми строками. Каждая строка содержит модуль проверки соответствия с искомым словом, результат проверки определяет значение (0 или 1) в ячейке вектора соответствий. Приоритетный шифратор выбирает адрес первого элемента вектора соответствий, содержащего 1. В каждой позиции САМ может быть только О или 1. САМ поддерживают только сравнения образцов с фиксированной длиной и, следовательно, в явном виде не подходят для поиска ІР-префиксов. Возможным решением является использование нескольких САМ, каждая из которых хранит IP-префиксы определенной длины [47].
Более эффективный подход основан на применении так называемых тернарных САМ[56,58,88,89]. Помимо индекса, ТСАМ хранят отдельную маску для каждой записи. Маска определяет, какие из битов индекса являются активными (см. таблицу 1.2). Основными недостатками ТСАМ являются высокая стоимость и большое энергопотребление. Так, 18Мбитный модуль ТСАМ может потреблять в процессе поиска до 15 Вт[88]. При этом потребляемая мощность пропорциональна количеству записей, хранимых в ТМ. Заметим, что в маршрутизаторе может быть использовано несколько модулей ТСАМ, например, каждый входной порт маршрутизатора Cisco 8500 оснащен 64 Кбайтной платой.
Сжатие таблиц маршрутизации позволяет повысить скорость поиска нужной записи, использовать память меньшего размера.
Методы минимизации булевых функций большой размерности
Проблеме минимизации булевых функций в классе ДНФ было посвящено множество исследований. Обзор наиболее известных алгоритмов, разработанных до 1986 г. можно найти в работе [11], обзор современных алгоритмов - в [38]. Далее приведена классификация алгоритмов по различным критериям 1]. Алгоритмы минимизации по их назначению можно разделить на: 1. алгоритмы построения сокращенной ДНФ; 2. алгоритмы построения кратчайших и минимальных ДНФ; 3. алгоритмы построения достаточно простых ДНФ В последних двух типах алгоритмов можно выделить подтипы в зависимости от того, строится или не строится в процессе работы сокращенная ДНФ По применимости к различным классам булевых функций алгоритмы можно разделить на: 1. применимые к всюду определенным булевым функциям; 2. ориентированные на минимизацию не всюду определенных булевых функций. В зависимости от способа реализации алгоритмы делятся на типы, предназначенные 1. для вычислений вручную; 2. для вычислений с использованием ЭВМ. Алгоритмы минимизации можно разделить на типы, использующие следующие математические средства и методы: 1. диаграммы и минимизирующие карты; 2. алгебрологические преобразования; 3. численные методы; 4. методы теории графов; 5. методы линейного программирования; 6. прочие методы. В зависимости от способа задания входной информации можно выделить типы алгоритмов, использующие следующие представления: 1. различные виды ДНФ (совершенная, сокращенная и др.); 2. таблицы; 3. числовые коды наборов, обращающих функцию в 1 (или в 0). 4. другие представления.
В рамках данной работы наибольшее внимание будет уделено рассмотрению алгоритмов построения кратчайших ДНФ всюду определенных булевых функций с использованием ЭВМ.
Сложность процедуры построения минимальной ДНФ, вообще говоря, зависит от способа задания булевой функции — она может быть задана таблицей истинности, ДНФ, множеством точек, в которых функция равна 1 (не полностью заданная функция, соответственно, - множествами точек, в которых функция равна 1 и 0). В любом из этих случаев, задача минимизации ДНФ является труднорешаемой [4,39,85]. Ряд важнейших результатов, подтверждающих тезис о неустранимости перебора из процедуры построения минимальных ДНФ, получен в работах Ю. И. Журавлева[5,11]. В частности, следует отметить доказательство того, что определение вхождения некоторой простой импликанты произвольной булевой функции хотя бы в одну ее минимальную ДНФ, требует знания окрестности бесконечного порядка. Под окрестностью порядка г простой импликанты р здесь понимается множество всех простых импликант, находящихся на расстоянии г от р. В свою очередь, расстояние между двумя простыми импликантами р и р заданной булевой функции / равняется наименьшему числу к (1 к \Р\,Р- множество всех простых импликантД такому, что Зр0,...рк_х єР, удовлетворяющие следующим условиям: рГ\ро 0, РіГ\рі+1 0 для к 2 и 0 i k-2, pk_l=p\ р}Фр для 0 / -1.
Основными факторами, затрудняющими построение минимальной ДНФ функции, являются большие размерности задачи - количество точек, в которых функция принимает значение 1 и количество всех простых импликант; первое, очевидно, не превосходит 2". Можно показать, что верхняя граница количества простых импликант функции равна -р[31]. При этом имеет место
Иными словами, почти все булевы функции имеют очень большую сложность реализации. В связи с принципиальными трудностями нахождения минимальной ДНФ, часто рассматривают некоторые ослабления этой задачи. Одна из возможностей заключается в построении решения, которое не обязательно является минимальным, и может его несколько превосходить.
ДНФ Д реализующая функцию называется приближенным решением с точностью h для задачи построения кратчайших ДНФ, если Lk (D) - Lk (f) h, где Lk (D) - количество конъюнкций в D. Приближенное решение с точностью 1 является точным решением. Следующая теорема показывает, что получение приближенного решения с высокой точностью почти столь же сложно, как и решение точной задачи.
Теорема 2[8]. Задача построения кратчайшей ДНФ полиномиально сводится к такой же приближенной задаче с точностью t Б для произвольного фиксированного s О (/ - длина ДНФ исходной функции).
Таким образом, как точные, так и приближенные (с высокой точностью приближения) алгоритмы являются экспоненциальными. В связи с этим, нас прежде всего будет интересовать их поведение на реальных задачах. Проведем далее краткий обзор существующих точных и приближенных алгоритмов.
Точный алгоритм минимизации булевых функций в классе ДНФ
Разработанный точный алгоритм построения минимальной дизъюнктивной нормальной формы булевых функций, соответствующих множествам записей таблицы маршрутизации, основан на использовании двоичных диаграмм решения и метода ветвей и границ. В общем случае алгоритм получает на вход систему частично определенных булевых функций {0,1}" - {ОД, }7". Такая система может быть задана несколькими способами: 1. множества А,Всі{0,1}" точек, в которых не полностью определенная функция/ принимает значения 1 и 0 соответственно 2. множества А, В с: {0,1}" точек, в которых полностью определенная функция/ принимает значения 1 и 0 соответственно 3. множество А с {0,1}" точек, в которых полностью определенная функция/ принимает значения 1 4. ДНФ функции Выходом алгоритма является кратчайшая ДНФ, реализующая данную систему. В контексте данной работы частично определенная функция может быть представлена как интервал Для оперирования с системой функций {ОД}" -» {0,1, }W будем использовать характеристическую функцию JlflSL построения такой функции был использован подход, рассматриваемый в работе [80]. Не ограничивая общности, в дальнейшем будем рассматривать алгоритм минимизации полностью определенных булевых функций с одной выходной переменной. Алгоритм использует классическую схему минимизации, предложенную Квайном и Маккласки[10,66,71,72], которая состоит из двух этапов: 1.
Генерация всех простых импликант функции; 2. Поиск минимального покрытия множества точек, в которых функция принимает значение 1, множеством простых импликант. Схема разработанного алгоритма приведена на рисунке 2.1. Предлагаемый алгоритм минимизации использует для представления булевых функций упрощенные упорядоченные двоичные диаграммы решения (ROBDD)[29,30], а для покрытий - двоичные диаграммы с отбрасыванием незначащих нулей (ZDD)[60,61,62]. Двоичные диаграммы решения были выбраны в связи с тем, что они сочетают в себе два полезных качества - приемлемый расход памяти и, как правило, быстрое выполнение операций над реализуемыми функциями. Такой подход позволяет реализовать совместную обработку дискретных объектов. Это свойство, применительно к данной работе, имеет большое значение, т.к. количество записей в таблицах маршрутизации, а, следовательно, и количество конъюнкций в ДНФ-представлении соответствующих булевых функций является очень большим. Одним из важнейших моментов при построении эффективных алгоритмов минимизации ДНФ, является выбор подходящей структуры данных для представления булевых функций.
Основными критериями выбора, при этом, являются компактность представления и возможность быстрого выполнения основных операций над функциями (таких как И, ИЛИ, отрицание и т.д.). За исключением таблиц истинности, ROBDD-представление булевых функций является единственной структурой данных, которая имеет полиномиальные алгоритмы для всех базовых операций[59]. В связи с тем, что таблицы истинности всегда имеют экспоненциальный размер от количества переменных, на практике они применимы лишь для небольшого количества переменных. ROBDD же может быть экспоненциально меньше таблицы истинности для реализуемой функции. Любую булеву функцию можно представить в виде OBDD, причем такое представление, в общем случае, не является уникальным и это сильно усложняет такие алгоритмы, как, например, проверка эквивалентности. С помощью очень простого механизма упрощения, произвольное OBDD-представление функции можно привести к стандартной, или канонической форме. Очевидно, что OBDD-представление функции после применения следующих двух правил упрощения по-прежнему реализует исходную функцию: 1. Если 1-й 0-ребра вершины v указывают на одну и ту же вершину и, тогда удаляем v и перенаправляем все входящие ребра v к и. 2. Все терминальные вершины с заданным значением объединяются в одну вершину, входящие ребра перенаправляются к этой вершине. Если две нетерминальные вершины и и v, отмечены одной и той же переменной и их 0- и 1-ребра указывают на одни и те же вершины соответственно, то удаляем одну из них и перенаправляем входящие ребра к оставшейся вершине. OBDD называется упрощенной, если ни одно из перечисленных правил упрощения к ней неприменимо. Следующее основополагающее свойство каноничности[29,30], определяет важнейшие алгоритмические свойства упрощенных OBDD: для заданных булевой функции / и порядка переменных ж, существует единственная упрощенная OBDD.
Таким образом, не имеет значения, каким образом была изначально сконструирована OBDD, так как с помощью простого повторения применения правил упрощения можно привести ее к канонической форме (относительно заданного порядка переменных).
Программная реализация разработанного метода уменьшения таблиц маршрутизации
В данном параграфе исследуются вопросы программной реализации предложенных алгоритмов. В параграфе 3.2.1 рассматривается процесс проектирования программного пакета с помощью UML (unified modeling language). В 3.2.2 приводится описание разработанного пакета.
Центральным моментом при разработке программного обеспечения является моделирование. Построение модели позволяет выявить основные требования, желаемую структуру и поведение системы, не вдаваясь, при этом, в детали реализации. Моделирование позволяет решить следующие основные задачи[2]: Визуализация системы в ее текущем или желательном состоянии; Спецификация - определение структуры и поведения системы; Конструирование. Получить шаблон, позволяющий затем сконструировать систему; Документация принимаемых решений, на основе использования полученных моделей.
Наиболее современным подходом к логическому моделированию программных систем является объектно-ориентированный, основными концепциями которого являются понятия класса и объекта. В самом общем смысле объект - это некоторая сущность предметной области, а класс -является описанием множества однотипных объектов.
Преобладающим средством визуального моделирования, в настоящее время, является язык UML (Unified Modeling Language)[2], позволяющий моделировать систему с разных точек зрения и предлагающий разработчику набор соответствующих диаграмм. В рамках данной работы используются следующие диаграммы, отражающие основные аспекты проектируемой системы: диаграмма вариантов использования (Use Case Diagram), диаграмма классов (Class Diagram) и диаграмма последовательности) действий (Sequences Diagram).
Диаграмма вариантов использования документирует функциональные требования к программной системе. Вариант использования описывает последовательность выполняемых системой действий, производящую наблюдаемый результат, значимый для определенного актера (Actor), абстрагируясь при этом от ее внутренней структуры. На рис. 3.1 приведена диаграмма вариантов использования для программной системы оптимизации таблиц маршрутизации. В качестве актера выступает сущность Оператор. На диаграмме отображены не только основные функции, но и ряд вспомогательных: преобразование файлов, настройка программы и др.
Диаграмма вариантов использования, при этом рассматривается как концептуальная модель системы[2]. В системе реализованы следующие основные классы: RTProcessor - предназначен для взаимодействия с таблицей маршрутизации. Converter - предназначен для преобразования файлов различного формата. BF - булева функция. BFMinimizer — абстрактный класс, инкапсулирующий свойства и методы для минимизации ДНФ. PrimesGenerator — класс для генерации простых импликант булевой функции.
