Jump to content
Sign in to follow this  
Ineu

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

Recommended Posts

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

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

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

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

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

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

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

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

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, т.е. кол-во уровней сокращается до двух Sad

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

×
×
  • Create New...