Оптимізація шейпера (HTB) — hashing filters

У мене є дуже непоганий шейпер :-)

Як саме працює мій конфігуратор — окрема розмова, тут я лише опишу процес створення шейпера з фільтрами на базі хеш-таблиць.

  1. Вступ
  2. Механізм
  3. Постановка задачі
  4. Конфігурування
  5. Реальна ситуація
  6. Зауваження

Вступ

Коротко:

Шейпер — це, взагалі кажучи, дисципліна обслуговування черги пакетів. Дисципліна може бути безкласовою (classless) чи класовою (classful) (до більшовиків — ніякого відношення; краще було б сказати «без класів» та «з класами»). «З класами» — це означає, що певний трафік може бути «зашейплений» певним класом.

Для того, щоб певний трафік був зашейплений певним класом, має спрацювати фільтр.

Тобто, можна казати, що «класова» дисципліна обслуговування — це два дерева, дерево класів та дерево фільтрів. Фільтри кидають пакети у класи, класи вже «шейплять» отримані пакети.

Це все краще читати у нормальній документації :-)

Чому хеші.

«Дерево фільтрів» — це якась послідовність фільтрів, можливі переходи між піддеревами… Але якщо фільтрів багато, то перевірка пакета на відповідність фільтрові може займати відносно багато часу.

Якщо все дерево фільтрів є послідовною перевіркою IP адреси, то значно ефективніше використовувати хеші. Хеш — це таблиця відповідності «значень» певним «ключам». У нашому випадку ключем є IP адреса, а значенням, фактично, фільтр, який вже перекидає пакет у відповідний клас. Тобто, по ключу-адресі ми швидко знаходимо (ну, не ми, а ядро) той фільтр, який вже перекидає у клас.

Також дивимося документацію.

Механізм

Тобто, якщо для мережі /24 створити таблицю на 256 комірок, та шукати (вибирати) потрібну по адресі, то кожен потрібний фільтр для кожної адреси ми знаходитимемо за один крок. А не 128 (у середньому).

Якщо нам треба обслуговувати дві мережі /24, то робимо табличку на дві комірки (вибір мережі), а з неї перекидаємо на одну з двох інших таблиць, кожна на 256 комірок… Дивимося конкретніше.

Візьмемо, наприклад, 192.168.1.0/24 та 192.168.2.0/24.

Мережі ми можемо розрізняти за третім байтом — 00000001 та 00000010 (у двійковій) відповідно.

Тобто, ядро (все це робить саме воно) бере перший фільтр, який за третім байтом адреси «вибирає» одну з двох комірок першої таблиці. У комірці лежить фільтр, який (коли ядро «задіює» його) «вибирає» вже з потрібної таблиці на 256 адрес вже за четвертим байтом IP адреси остаточний результат — певний клас.

Постановка задачі

Маємо:

  • П’ять мереж /24: 192.168.1.0/24, 192.168.2.0/24 .. 192.168.5.0/24
  • Інтерфейс $DEV , через який ці мережі доступні

Треба:

  • Залежно від IP адреси шейпити пакети «певним чином».
  • Весь трафік на «вільні» адреси (не надані нікому) шейпити окремо.

Конфігурування

Ми захочемо створити скрипт, який потім можна буде виконувати для конфігурування… Чи ми можемо захотіти одразу конфігурувати шейпер:

# it may be useful to distinct between
# configuring and creating script:
#tc="/sbin/tc"
tc="/bin/echo /sbin/tc"

Створимо кореневу дисципліну («лівий» трафік — у клас 90):

$tc qdisc add dev $DEV root handle 1: htb default 90

Кореневий клас:

$tc class add dev $DEV parent 1:0 classid 1:1 htb rate 100Mbit

Тепер треба створити «кореневий» фільтр — до нього потім чіплятимемо інші фільтри:

$tc filter add dev $DEV parent 1:0 prio 10 protocol ip u32

Створюємо таблицю на п’ять комірок, по комірці на кожну мережу:

# divisor 5 --- table for 5 cells:
$tc filter add dev $DEV parent 1:0 protocol ip prio 10 handle 8: u32 divisor 5

Тепер створюємо п’ять таблиць — для кожної мережі одну таблицю на 256 комірок:

for i in 1 2 3 4 5; do
    $tc filter add dev $DEV parent 1:0 prio 10 handle ${i}: protocol ip u32 divisor 256
done

Тепер заповнимо верхню таблицю (ту, яка на п’ять комірок), запишемо в неї фільтри-переходи на таблиці по 256 комірок:

for i in 1 2 3 4 5; do
    $tc filter add dev $DEV parent 1:0 protocol ip prio 10 \
        u32 ht 8:$[i-1]: \
        match ip dst 192.168.${i}.0/24 \
        hashkey mask 0x000000ff at 16 \
        link $i:
done

Це означає: записуємо у комірку $[i-1] таблиці 8 (ht 8:$[i-1]:) фільтр, який бере останній байт (hashkey mask 0x000000ff) адреси призначення (match ip dst 192.168.${i}.0/24), використовує його як ключ для пошуку у таблиці $i (link $i:).

Тепер — «головний» фільтр, який «дивиться» у таблицю на п’ять комірок:

$tc filter add dev $DEV parent 1:0 protocol ip prio 100 u32 ht 800:: \
    match ip dst 192.168.0.0/21 \
    hashkey mask 0x00000700 at 16 link 8:

Це означає — кореневий фільтр (ht 800::) має перевіряти адреси одержувача, і якщо це задані мережі (match ip dst 192.168.0.0/21) використовувати останні три біти третього байта адреси (hashkey mask 0x00000700 at 16) як ключ для пошуку у таблиці 8 (link 8:).

Тепер можна створювати класи/фільтри для клієнтів.

Оскільки цей процес «індивідуальний» (кожен адміністратор сам вирішує, у якій базі і у якому вигляді тримати інформацію про клієнтів, їхні смуги тощо), просто для прикладу створимо один клієнтський клас і визначимо фільтр:

# class 1: 320 --- parent for clients' classes:
$tc class add dev $DEV parent 1:1 classid 1:230 htb rate 30Mbit ceil 50Mbit quantum 1500 . . .
#
# particular client:
$tc class add dev $DEV parent 1:230 classid 1:431 htb rate 2Mbit ceil 10Mbit quantum 1500 burst . . .
$tc filter add dev $DEV protocol ip parent 1:0 prio 100 u32 ht 3:4: match ip dst 192.168.3.4 flowid 1:431

Останній рядок означає — у п’яту комірку (вони нумеруються з нуля!) третьої таблиці записати фільтр, який буде пакети на 192.168.3.4 відкидати у клас 1:431.

Тобто, у циклі можна (треба, напевно) створювати класи та фільтри для кожного клієнта — при цьому цими фільтрами ми фактично заповнюємо таблиці для мереж, по 256 комірок.

Реальна ситуація

У реальній ситуації адміністратор може захотіти тримати конфігурацію у якійсь базі даних, скрипти можуть бути десь зовсім не такими, але реалізовувати саме таку конструкцію. На момент написання такий шейпер у мене працює із 32-ма мережами /24, на каналі 1Gbit/s (реального трафіку — вже біля 200Mbit/s, часом підскакує).

«Було вирішено», що шейпер має бути шейпером — все це зібрано на комутаторі (linux bridge), HTB чудово працює на комутаторі.

Зауваження

  • Коли я все це відпрацьовував — щоб працювало, треба було створювати «кругле число» таблиць на 256 комірок, а саме: у наведеному прикладі ми опрацьовуємо 5 мереж, але реально треба було б створювати 7 таблиць, повні три біти для маски для ключа.
    Тобто, якщо для маски, по якій «фільтруємо» мережу (ключі для таблиці першого рівня, на кількість комірок, що відповідає кількості мереж /24), треба n бітів, то треба робити 2^^n – 1 таблиць. Тобто, треба було створювати «зайві» таблиці, які реально не використовуються. Інакше не працювало. Як зараз, не знаю :-)
  • Комірки у таблиці номеруються з нуля; номер комірки завжди треба писати у hex’і. У наведеному вище прикладі (остання команда, створення фільтра для «клієнтського» пакета на 192.168.3.5) — також у hex’і :-)
  • Це — перша чернетка :-)

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *

Цей сайт використовує Akismet для зменшення спаму. Дізнайтеся, як обробляються ваші дані коментарів.