Размышление об именовании узлов графа в tc

[Ineu]

Доброго времени суток!

Думаю, не только у меня при усложнении дерева классов в tc возникает сабжевый вопрос. Если кто-нибудь его красиво и эффективно решил, просьба поделиться опытом.

Имхо, все, кто может ответить на этот вопрос, не нуждаются в рассказах, что это и как работает, но тем не менее приведу несколько замечаний, которые могут помочь в размышлениях. Заодно прошу меня поправить, если что-то пропущу или скажу неточно. Итак

1. Набор правил управления трафиком строится в виде дерева. Узлами его являются пары класс/присоединенная к нему дисциплина. Каждая дисциплина (речь не идет о простейших бесклассовых дисциплинах) может иметь в принципе неограниченное кол-во подклассов, каждый из которых - свою дисциплину и т.д.

2. Каждый элемент узла (дисциплина/класс) имеет уникальный дескриптор, использующийся для дальнейшего построения дерева и в фильтрах. Дескриптор состоит из двух двухбайтных величин - старшего и младшего номеров.

3. Старший номер класса повторяет старший номер родительской дисциплины. Младший номер любой дисциплины равен 0.

4. Корневой дисциплине назначается дескриптор 1:0 (не отступая от канонов )

Интересует система назначения дескрипторов. Вытекающие из вышесказанного ограничения:

1. Дескриптор корневой дисциплины - 1:0

2. Количество классов на каждом уровне неограничено.

3. Количество уровней дерева неограничено

4. Максимальное значение старшего/младшего номера - 2**16

5. Необходима возможность добавления ветки на любой из уровней дерева без необходимости изменения системы именования

5. Необходима возможность определения ветки/родителя по дескриптору

Стандартная система, приводимая во многих статья по tc, состоит в том, что при переходе на каждый новый уровень старший номер дескриптора увеличивается на один ноль. Например, для дерева

*

/ \

* *

/ \ \

* * *

..............

получаем следущую систему нумерации (для ветки 2):

0 root qdisc 1:0

1

1.1 class 1:2

1.2 qdisc 20:0

2

2.1 class 20:1

2.2 qdisc 200:0

3

3.1 class 200:1

3.2 qdisc 2000:0

4

4.1 class 2000:1

4.2 qdisc 20000:0

5

5.1 class 20000:1

5.2 qdisc 200000:0 # 200 000 > 65536

Такая схема не устраивает, поскольку уже на пятом уровне происходит превышение старшего номера над максимально возможным.

Теоретически количество подклассов для каждого уровня может достигать 2**16, а практически это нарушает ограничение 5, т.к. в такой схеме старшие номера дескрипторов следующего уровня определяются как номер ветки * (10 ** уровень), что уже для 200 класса на первом уровне (и, соотв, для 200 ветки) потребует дескриптора потомка 200 * (10 ** 1) = 2000, а для следующего уровня - 200 * (10 ** 2) = 20000, т.е. кол-во уровней сокращается до двух

Если есть мысли насчет другой системы именования - прошу высказываться