Ng_multicar или шейпинг трафика для большого числа ip адресов

Обычный ng_car довольно удобно использовать для шейпинга небольшого количества отдельных полос, в случае же увеличения количества полос поиск хука, в который будет отправлено правило будет занимать довольно много времени, т.к. для этого используется линейный список (ng_ipfw.c):

/* Look up hook by name */
hook_p
ng_ipfw_findhook(node_p node, const char *name)
{
        u_int16_t n;    /* numeric representation of hook */
        char *endptr;

        n = (u_int16_t)strtol(name, &endptr, 10);
        if (*endptr != '\0')
                return NULL;
        return ng_ipfw_findhook1(node, n);
}

/* Look up hook by rule number */
static hook_p
ng_ipfw_findhook1(node_p node, u_int16_t rulenum)
{
        hook_p  hook;
        hpriv_p hpriv;

        LIST_FOREACH(hook, &node->nd_hooks, hk_hooks) {
                hpriv = NG_HOOK_PRIVATE(hook);
                if (NG_HOOK_IS_VALID(hook) && (hpriv->rulenum == rulenum))
                        return (hook);
        }

        return (NULL);
}

Кроме этого, такое использование ng_car подходит только для ipfw с его ng_ipfw. В моем случае для pf'а необходимо направлять весь трафик в netgraph ноду (например, с ng_ether), поэтому задача разделения полос и ip адресов возлагается целиком на netgraph модуль. Возникли следующие идеи по реализации такого шейпера:

• Использовать для хранения информации о полосе для ip judy массив для ускорения поиска


• Для загрузки и выгрузки информации о полосах и соответствующих им ip использовать либо отдельные команды, либо парсить некоторый загрузочный файл



• Поддерживать создание динамических полос для сетей, например, если аргумент - сеть в CIDR формате, то создавать полосу для ip по получению пакета от данного ip из данной сети (нечто вроде динамических пайпов dummynet'а)

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