Поиск порогового значения

Перед началом поиска порогового значения в методе MaskRule::compute неявно вводится дополнительный фиктивный диапазон Others, который по определению аккумулирует все адреса, не удовлетворяющие другим диапазонам. Далее делается проход по всем соединениям, и для каждого диапазона адресов (включая фиктивный) подсчитывается суммарный вес соединений, лежащих в нем. Следующим шагом из списка диапазонов удаляются те, вес которых равен нулю. Таким диапазонам не соответствует ни одного соединения, и они должны быть удалены, чтобы не тормозить работу правила.

Если после удаления нулевых диапазонов не осталось ничего, кроме Others — это признак того, что мы попали в вершину с чисто внешним трафиком, о которой говорилось выше. В этом случае правило масок отключается. Флаг отключения распространяется на клоны правила, т.е. идет дальше в поддереве, которое начинается в текущей вершине. Метод compute отключенного правила масок ничего не делает и всегда сообщает, что все пакеты прошли правило успешно, но деления найдено не было. Следует обратить внимание также на то, что правила масок для адресов отправителей и получателей — различные правила. Одно из них может быть отключено, а другое — продолжать функционировать. Благодаря этому успешно разбираются соединения с одним из адресов из внешней сети, а другим — из внутренней.

После того, как исключены все вырожденные случаи, происходит поиск деления. Фактически, имеется массив натуральных чисел (весов диапазонов), и нужно разделить его на две части, как можно меньше отличающиеся друг от друга по сумме. Задача при первом рассмотрении кажется эквивалентной задаче о суммах подмножеств, которая является NP-полной [14]. Но это не так. В нашем случае накладывается дополнительное ограничение, существенно упрощающее решение: одно из подмножеств, образованных в результате деления, должно целиком состоять из элемента(ов) с максимальным значением. Если это не выполняется, то средневзвешенное время прохождения пакетов через дерево правил не будет минимальным, ведь при делении в вершинах редкие соединения будут соседствовать с частыми. Но совсем упростить задачу — брать только один диапазон максимального веса, если таких больше трех — нельзя, потому что тогда соединения с равной частотой будут обрабатываться с применением существенно различного количества проверок.

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

Сложность метода MaskRule::compute оценивается как , где n — это мощность множества соединений, а m — количество диапазонов (т.к. присутствует цикл по всем соединениям с вложенным циклом по всем диапазонам — когда мы вычисляем их вес). Можно считать, что . Это может не выполняться для некоторых вершин дерева, близких к листьям (когда осталось уже немного соединений), но для большинства вершин это однозначно верно, причем m во много раз меньше n. Таким образом, сложность правила масок, как и сложность правила портов не превышает  (на самом деле, она гораздо меньше). Это подтверждает то, что общая сложность построения дерева правил не превышает .

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