Если у вас возникла потребность в большом количестве правил, например, когда у вас много клиентов, причем все имеют различные спецификации QoS (от англ. Quality of Service — Качество Обслуживания), то может сложиться ситуация, когда ядро будет тратить недопустимо большое количество времени на поиск подходящего правила в наборе.
По-умолчанию, все фильтры находятся в одной большой цепочке, и располагаются в порядке убывания приоритетов. Если набор содержит 1000 правил, то для некоторых пакетов может потребоваться выполнить 1000 проверок, чтобы решить, что с ними делать дальше.
Поиск шел бы гораздо быстрее, если бы было 256 цепочек, по четыре правила в каждой, при условии, что вы сможете направить пакет в нужную цепочку.
В этом случае вам поможет хеширование. Представим, что у нас имеется сеть из 1024 компьютеров, с IP-адресами от 1.2.0.0 до 1.2.3.255, причем каждый компьютер может быть отнесен к одному из 3-х предопределенных классов качества обслуживания, например 'lite', 'regular' и 'premium'. Решение "в лоб" дает 1024 правила:
># tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
> 1.2.0.0 classid 1:1
># tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
> 1.2.0.1 classid 1:1
>…
># tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
> 1.2.3.254 classid 1:3
># tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
> 1.2.3.255 classid 1:2
Чтобы уменьшить число проверок, можно использовать последний байт IP-адреса в качестве хеш-ключа. В результате получается 256 таблиц, первая из которых:
># tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
> 1.2.0.0 classid 1:1
># tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
> 1.2.1.0 classid 1:1
># tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
> 1.2.2.0 classid 1:3
># tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
> 1.2.3.0 classid 1:2
Следующая:
># tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
> 1.2.0.1 classid 1:1
>…
Таким образом каждый пакет должен пройти не более 4-х проверок.
Реальная конфигурация намного сложнее, но она стоит того. Первым создается корневой фильтр, а затем — таблица на 256 записей: