QoS: new per flow queue

Hi,

I write a per flow rate control qdisc. I posted it to LARTC list. Some discussion about it is here

    http://mailman.ds9a.nl/pipermail/lartc/2005q2/015381.html

I think I need more feedback and suggestion on it so I repost the patch here. Please read the thread and get a picture about why and how.

The kernel patch is agains kernel 2.6.11, the iproute2 patch is against iproute2-2.6.11-050314.

The test scenario is like this

      www server <- [ eth0   eth1 ] -> www clients

The attached t.sh is used to generate test rules. Clients download a big ISO file from www server, so flows' rate can be estimated by view progress.

I have some test on it and it works well. It provides good fairness. When all slot being used, in most time, the real rate can keep at specified guaranteed rate. But I know it should receive more test.

I have some consideration though

1. In the test sometimes there a pair of unbalanced stream and don't get balanced quickly. One stream get 8.4kbps and another get 11.5kbps. How to find the flow with highest traffic and punish it most?

2. The default ceil equals to rate. Should I calculate it as ceil = rate * 1.05 * limit, or
ceil = rate * 1.05?

3. when flow slots are full, optionally reclassify untraceable traffic into another specified class, instead of dropping it?

TODO:

1. rtnetlink related code should be improved;
2. dump() and dump_stat();

Regards

I quickly scanned the kernel portion. I dont think this is the best way to achieve this - your qdisc is both a classifier and scheduler. I think this is the major drwback.
And if you take out the classifier - whats left in your qdisc cant beat htb or hfsc or cbq in terms of being proven to be accurate.

If you could write a meta action instead which is a simple dynamic setter of something like fwmark that would suffice i.e something along the lines of:

example:
----
tc filter ip u32 match ip sport 80 0xffff flowid 1:12 \
action dynfwmark continue
tc filter fwmark 0x1 .. classid aaaa
tc filter fwmark 0x2 .. classid bbbb
..
..

tc qdisc htb/hfsc/cbq .... your rate parameters here.
---

dynfwmark will maintain your state table which gets deleted when timers expire and will hash based on the current jenkins hash
Do you have to queue the packets? if not you could instead have the police action (attached to fwmark) drop the packet once it exceeds certain rate and then use any enqueueing scheme you want. The drawback with above scheme is you will have as many entries for fwmark as you want to have queues - each selecting its own queue.

cheers,
jamal

Quoted 45 lines · Wang Jian

Hi,

I write a per flow rate control qdisc. I posted it to LARTC list. Some discussion about it is here

    http://mailman.ds9a.nl/pipermail/lartc/2005q2/015381.html

I think I need more feedback and suggestion on it so I repost the patch here. Please read the thread and get a picture about why and how.

The kernel patch is agains kernel 2.6.11, the iproute2 patch is against iproute2-2.6.11-050314.

The test scenario is like this

      www server <- [ eth0   eth1 ] -> www clients

The attached t.sh is used to generate test rules. Clients download a big ISO file from www server, so flows' rate can be estimated by view progress.

I have some test on it and it works well. It provides good fairness. When all slot being used, in most time, the real rate can keep at specified guaranteed rate. But I know it should receive more test.

I have some consideration though

1. In the test sometimes there a pair of unbalanced stream and don't get balanced quickly. One stream get 8.4kbps and another get 11.5kbps. How to find the flow with highest traffic and punish it most?

2. The default ceil equals to rate. Should I calculate it as ceil = rate * 1.05 * limit, or
ceil = rate * 1.05?

3. when flow slots are full, optionally reclassify untraceable traffic into another specified class, instead of dropping it?

TODO:

1. rtnetlink related code should be improved;
2. dump() and dump_stat();

Regards

Hi jamal,

I know your concern. Actually, I first try to implement it like you point out, but then I dismiss that scheme, because it is hard to maintain for the userspace.

But if the dynfwmark can dynamically alloc htb class in the given class id range. For example

tc filter ip u32 tc filter ip u32 match ip sport 80 0xffff flowid 1:12 \
action dynfwmark major 1 range 1:1000 <flow parameter> continue

When it detects a new flow, it creates the necessary htb class? So the userspace work is simple. But when we have segmented class id space, we may not get such an enough empty range.

I think per flow control in nature means that classifier must be intimately coupled with scheduler. There is no way around it. If you seperate them, you must provide a way to link them together again. The dynfwmark way you suggested actually does so, but not clean (because you choose to use existing nfmark infrastructure). If it carries an unique id or something like in its own namespace, then it can be clean and friendly for userspace, but I bet it is unnecessarily bloated.

In my test, HTB performs very well. I intensionally requires a HTB
class to enclose a perflow queue to provide guaranteed sum bandwidth. The queue is proven to be fair enough and can guarantee rate internally for its flows (if the per flow rate is at or above 10kbps).

I haven't tested rate lower than 10kbps, because my test client is not that accurate to show the number. It's simply a "lftpget <url>".

There are short threads before in which someone asked for a per flow control solution, and was suggested to use HTB + SFQ. My test reveals that SFQ is far away from fairness and can't meet the requirement of bandwidth assurance.

For HFSC, I haven't any experience with it because the documentation is lacked.

Wang,

Quoted 9 lines · Wang Jian

Hi jamal,

I know your concern. Actually, I first try to implement it like you point out, but then I dismiss that scheme, because it is hard to maintain for the userspace.

But if the dynfwmark can dynamically alloc htb class in the given class id range. For example

Quoted 3 lines

tc filter ip u32 tc filter ip u32 match ip sport 80 0xffff flowid 1:12 \
action dynfwmark major 1 range 1:1000 <flow parameter> continue

Yes, this looks better except for the <flow parameter> part - why do you need that? The syntax may have to explicitly say min 1 max 1000 for usability, but thats not a big deal.

Essentially rewrite the classid/flowid. In the action just set skb->tc_classid and u32 will make sure the packet goes to the correct major:minor queue. This already works with kernels >= 2.6.10.

Quoted 4 lines

When it detects a new flow, it creates the necessary htb class? So the userspace work is simple. But when we have segmented class id space, we may not get such an enough empty range.

Yes, I thought about this too when i was responding to you earlier. Theres two ways to do it in my opinion:
1) create apriori at setup time 1024 or whatever number of HTB classes. So when u32 selects the major:minor its already there.
OR
2) do what you are suggesting to dynamically create classes; i.e "classifier returned a non-existing class, create default class using that major/minor number".
Default class could be defined from user space to be one that is initialized to 10 Kbps rate burst 1kbps etc. You may have to teach the qdisc the maximum number of classes it should create.

#1 above will work immediately and you dont have to hack any of the qdiscs. The disadvantage is your user space app will have to create every class individualy - so if you have 1024 queues then 1024 queues are needed.
#2 is nice because it avoids the above problem - disadvantage is you need to manage creation and deletion of these queues and write code.

I do think the idea of dynamically creating the flow queues is interesting and useful as well. It would be nice if it can be done for all classful qdiscs.

One thing i noticed is that you dont have multiple queues actually in your code - did i misread that? i.e multiple classes go to the same queue.

Quoted 9 lines

I think per flow control in nature means that classifier must be intimately coupled with scheduler. There is no way around it. If you seperate them, you must provide a way to link them together again. The dynfwmark way you suggested actually does so, but not clean (because you choose to use existing nfmark infrastructure). If it carries an unique id or something like in its own namespace, then it can be clean and friendly for userspace, but I bet it is unnecessarily bloated.

The only unfriendliness to user space is in #1 where you end up having a script creating as many classes as you need. It is _not_ bloat because you dont add any code at all. It is anti-bloat actually ;->

Look at above - and based on your suggestion; lets reset the flowid/classid.

Quoted 5 lines

In my test, HTB performs very well. I intensionally requires a HTB
class to enclose a perflow queue to provide guaranteed sum bandwidth. The queue is proven to be fair enough and can guarantee rate internally for its flows (if the per flow rate is at or above 10kbps).

Well, HTB is just a replica of the token bucket scheduler with additional knobs - so i suspect the numbers will look the same with TB as well. Someone needs to be test all of them and see how accurate they are. The clock sources at compile time and your hardware will also affect you.

Quoted 8 lines

I haven't tested rate lower than 10kbps, because my test client is not that accurate to show the number. It's simply a "lftpget <url>".

There are short threads before in which someone asked for a per flow control solution, and was suggested to use HTB + SFQ. My test reveals that SFQ is far away from fairness and can't meet the requirement of bandwidth assurance.

I dont think SFQ will give you per flow; actually I should say - depends on your definition of flow - seems yours is the 5 tuple { src/dst IP, src/dst port, proto=UDP/TCP/SCTP}. SFQ will work for a subset of these tuples and is therefore not fair at the granularity that you want.

Quoted 3 lines

For HFSC, I haven't any experience with it because the documentation is lacked.

I am suprised no one has compared all the rate control schemes.

btw, would policing also suffice for you? The only difference is it will drop packets if you exceed your rate. You can also do hierachical sharing.

Hi jamal,

Quoted 4 lines · jamal

Essentially rewrite the classid/flowid. In the action just set skb->tc_classid and u32 will make sure the packet goes to the correct major:minor queue. This already works with kernels >= 2.6.10.

One question:

Can I set skb->tc_classid in a qdisc and pass this skb to the specified class to handle?

My idea is that the action itself dynamically creates classes. So you don't need any other rules. It is looks like #2 but the work is done in dynfwmark action. The workflow

0. setup, and create flow entry hash;
1. when a packet arrives, check if it is a flow or should be a new flow;
2. alloc a class id for this flow;

3. dynamically create a htb class using the <flow parameter>
4. skb->tc_classid = allocated_ht_class_id

1.5 if can't create flow, skb->tc_classid = default_class_id

Quoted 4 lines

One thing i noticed is that you dont have multiple queues actually in your code - did i misread that? i.e multiple classes go to the same queue.

Didn't you notice that it is a classless qdisc? The queue is per qdisc, not per class :)

It is the parent class's duty to define what kind of
flow this qdisc handle. It is very generic, you can even mix UDP/TCP flows together but I don't think it is good idea.

Think the scenario

1. You have VoIP flows (UDP)
2. You have pptp vpn flows (eh, per flow can't handle it at this time, I think)

You create HTBs for them, and use filter to classify them. And then, use per flow qdisc as the only child of these HTBs. per flow qdisc will guarantee the per flow QoS.

Quoted 4 lines

The only unfriendliness to user space is in #1 where you end up having a script creating as many classes as you need. It is _not_ bloat because you dont add any code at all. It is anti-bloat actually ;->

In this way, it is very hard to write good user interface in userspace. My current implementation takes good user-friendly (or user space scripter/programmer friendly) into serious consideration.

The 'bloated' comment is on the

"If it carries an unique id or something like in its own namespace, then it can be clean and friendly for userspace"

I think too much and my thought is jumpy ;) You even didn't notice that I gave another suggestion on implementation in this sentence.

Quoted 5 lines

I am suprised no one has compared all the rate control schemes.

btw, would policing also suffice for you? The only difference is it will drop packets if you exceed your rate. You can also do hierachical sharing.

policy suffices, but doesn't serve the purpose of per flow queue.

Quoted 6 lines

One question:

Can I set skb->tc_classid in a qdisc and pass this skb to the specified class to handle?

Well, remember the qdisc asks the filter what class a packet belongs to every time. The best place to change things is at that point. Why not tell the qdisc whatever class you want it to know instead of passing metadata like skb->tc_classid for it to further intepret?

Quoted 3 lines

Didn't you notice that it is a classless qdisc? The queue is per qdisc, not per class :)

Sorry missed that ;->

Quoted 4 lines

It is the parent class's duty to define what kind of
flow this qdisc handle. It is very generic, you can even mix UDP/TCP flows together but I don't think it is good idea.

Doesnt that defeat the purpose of it being "per flow queue" ;->

Quoted 11 lines

Think the scenario

1. You have VoIP flows (UDP)
2. You have pptp vpn flows (eh, per flow can't handle it at this time, I think)

You create HTBs for them, and use filter to classify them. And then, use per flow qdisc as the only child of these HTBs. per flow qdisc will guarantee the per flow QoS.

I got this. Of course you understand creating all these filters and queues is taking system resources. It may be sufficient to create heuristics like a simple priority qdisc where you put voip as first class citizen, vpn as second and rest as best effort.

Quoted 10 lines

Quoted 5 lines

The only unfriendliness to user space is in #1 where you end up having a script creating as many classes as you need. It is _not_ bloat because you dont add any code at all. It is anti-bloat actually ;->

In this way, it is very hard to write good user interface in userspace. My current implementation takes good user-friendly (or user space scripter/programmer friendly) into serious consideration.

It is not hard - its annoying in user space ;-> You could write a for loop to produce them. such as:

for i stating from 1 to 1000
tc class add .... rate 10Kbps classid 1:$i
endfor

Trying to list those classes will list at least a 1000 lines of course. But this listing issue will happen even when you dynamically create these classes.
So annoyance is more descriptive.

Quoted 7 lines

Quoted 6 lines

I am suprised no one has compared all the rate control schemes.

btw, would policing also suffice for you? The only difference is it will drop packets if you exceed your rate. You can also do hierachical sharing.

Quoted 2 lines

policy suffices, but doesn't serve the purpose of per flow queue.

Policing will achieve the goal of rate control without worrying about any queueing. I like the idea of someone trying to create dynamic queues though ;->

1. a flow (in my perflow queue implementation) is a tuple of five elements, but, for some reason, if the users misused this queue and send non-flow packet, e.g. ICMP packet here;

2. a queue is configured to handle 100 flows, but the 101st flow comes;

For this two situations, currently, the implementation just drops packets. However, a clean way is to reclassify the packet into another class (default) and provides no per flow guarantee.

Quoted 1 line

Doesnt that defeat the purpose of it being "per flow queue" ;->

Per flow queue, is not one queue per flow ;) It is queue which can provide bandwidth assurance and constraint per flow.

The implementation can be either one queue per flow, or all flows fit into one queue.

As I already said, this approach has drawbacks

1. when flow count overlimit, no guarantee
2. when flow count is underlimit, the guaranteed sum bandwidth can be exploited to waste bandwidth.

So, thinking of per flow queue, it is "queue which can provide bandwidth assurance and constraint per flow", and with only one queue!

You only need to create one HTB, one filter and one per flow queue for VoIP; and one HTB, one filter and one per flow queue for VPN.

I think the "per flow" name does confuse you ;) My fault.

The problem occurs when you delete and add, and so on. It not good idea to reuse a used classid when there is stream classified as old.

For example, you give class 1:1000 htb rate 200kbps ceil 200kbps for http, and you delete the class 1:1000 and redefine 1:1000 htb rate 30kbps ceil 30kbps for ftp.

At this time, the remained http streams carries a CONNMARK and restore to MARK and then classified as 1:0000. Then 1:1000 is not what you want.

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines

I am suprised no one has compared all the rate control schemes.

btw, would policing also suffice for you? The only difference is it will drop packets if you exceed your rate. You can also do hierachical sharing.

Quoted 7 lines

Quoted 2 lines

policy suffices, but doesn't serve the purpose of per flow queue.

Policing will achieve the goal of rate control without worrying about any queueing. I like the idea of someone trying to create dynamic queues though ;->

You need per flow queue to control something, like VoIP streams, or VPN streams. If you just use policy, mixed traffic is send to per flow queue. That is definitely not the purpose of per flow queue.

The dynamic queue creating is another way to implement the per flow control (yes, one class and queue per flow). I think it is more complex and wastes resources.

Quoted 6 lines · Wang Jian

1. a flow (in my perflow queue implementation) is a tuple of five elements, but, for some reason, if the users misused this queue and send non-flow packet, e.g. ICMP packet here;

2. a queue is configured to handle 100 flows, but the 101st flow comes;

Quoted 4 lines

For this two situations, currently, the implementation just drops packets. However, a clean way is to reclassify the packet into another class (default) and provides no per flow guarantee.

The reclassification or #1 will best be left to the user. This is not hard to do.

Ok, stop calling it per-flow-queue then ;-> You should call it per-flow-rate-guarantee.

Quoted 6 lines

As I already said, this approach has drawbacks

1. when flow count overlimit, no guarantee
2. when flow count is underlimit, the guaranteed sum bandwidth can be exploited to waste bandwidth.

Quoted 3 lines

So, thinking of per flow queue, it is "queue which can provide bandwidth assurance and constraint per flow", and with only one queue!

Sharing is not a big challenge - and should be policy driven. HTB and CBQ both support it. I am not sure about HFSC.

Quoted 5 lines

You only need to create one HTB, one filter and one per flow queue for VoIP; and one HTB, one filter and one per flow queue for VPN.

I think the "per flow" name does confuse you ;) My fault.

The "queue" part is confusing - the "perflow" is fine. Lets stick with per-flow-rate-guarantee as the description.

So it seems you want by all means to avoid entering something that will take forever to list. Did i understand this correctly?

We can probably avoid insisting on dynamically creating classes maybe. You can rate control before you enqueue and we can use fwmark perhaps. Earlier i also asked whether policing will suffice. Heres an example (maybe dated syntax, but concept still valid) that shows sharing using policers:
http://www.cyberus.ca/~hadi/patches/action/README

look at the example where it says "--cut here --"

The only difference in this case is instead of creating 1000 classes you create 1000 policers as a result of the hash. Something along:

    u32 classify for port 80 prio high \
       action dymfwmark create range min 1 max 1000 \
       action police to some rate if result is drop we stop here \
       else continue \
    fwmark classify prio low\
       select one of two queues (high prio or low prio Q)

Very small script but still doesnt avoid the "seeing 1000 things". In this case if you list actions you see 1000.
The lockings in this case are more bearable than having the dynamic marker creating queues.
Typically the actions in a topology graph are stiched together at policy init time for efficiency reasons - so we dont have to do lookups at runtime. In this case it will need to have static lookup instead because depending on what the hash selects you want to select a different policer instance. I think i know an easy way of doing this (example storing per hash policer pointer in the dynmark table and doing the invoke from within dynmark).

Quoted 7 lines

The problem occurs when you delete and add, and so on. It not good idea to reuse a used classid when there is stream classified as old.

For example, you give class 1:1000 htb rate 200kbps ceil 200kbps for http, and you delete the class 1:1000 and redefine 1:1000 htb rate 30kbps ceil 30kbps for ftp.

Quoted 3 lines

At this time, the remained http streams carries a CONNMARK and restore to MARK and then classified as 1:0000. Then 1:1000 is not what you want.

I would think the number 1000 should be related to hash of flow header, no? In which case there should be no collision unless the hash of ftp and http are 1000.

Quoted 20 lines

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines

I am suprised no one has compared all the rate control schemes.

btw, would policing also suffice for you? The only difference is it will drop packets if you exceed your rate. You can also do hierachical sharing.

Quoted 7 lines

Quoted 2 lines

policy suffices, but doesn't serve the purpose of per flow queue.

Policing will achieve the goal of rate control without worrying about any queueing. I like the idea of someone trying to create dynamic queues though ;->

You need per flow queue to control something, like VoIP streams, or VPN streams. If you just use policy, mixed traffic is send to per flow queue. That is definitely not the purpose of per flow queue.

Quoted 4 lines

The dynamic queue creating is another way to implement the per flow control (yes, one class and queue per flow). I think it is more complex and wastes resources.

Look at the above suggestion - what you will waste in that case is polices. You should actually not use HTB but rather strict prio qdisc with policers.

cheers,
jamal

Hi jamal,

Sorry for the late reply. I am occupied by other things and just have time back to this topic.

Quoted 5 lines

The reclassification or #1 will best be left to the user. This is not hard to do.

I scan through other code and find no easy way to redirect non-handled traffic to another class. Can you give me some hint on that?

Quoted 3 lines

Ok, stop calling it per-flow-queue then ;-> You should call it per-flow-rate-guarantee.

I have renamed it to frg (flow rate guarantee) per your suggestion. After the above reclassification is done, I will post new patch here.

I will extend the concept of flow to include GRE, so pptp VPN can be supported. There are other 'flows' to consider.

Quoted 3 lines

Sharing is not a big challenge - and should be policy driven. HTB and CBQ both support it. I am not sure about HFSC.

Still, I am not clear if you understand me. How it works for this purpose:

guarantee and only guarantee rate * n when there are n flows?

When there only 1 flow, guarantee only rate * 1
When there only 2 flows, guarantee only rate * 2
...
and so on

If always guarantee rate * limit, then the excessive guaranteed rate can be abused.

But if always guarantee only rate * 1, then it is not enough.

Quoted 2 lines

So it seems you want by all means to avoid entering something that will take forever to list. Did i understand this correctly?

Yes. It is special purpose but general enough. I think it's worthy of adding a new qdisc for it to avoid the dirty long listing part.

Quoted 7 lines

We can probably avoid insisting on dynamically creating classes maybe. You can rate control before you enqueue and we can use fwmark perhaps. Earlier i also asked whether policing will suffice. Heres an example (maybe dated syntax, but concept still valid) that shows sharing using policers:
http://www.cyberus.ca/~hadi/patches/action/README

I will look at it later.

If we can do it with one thing, we should avoid creating 1000 things. The policy way works but is dirty.

Quoted 4 lines

I would think the number 1000 should be related to hash of flow header, no? In which case there should be no collision unless the hash of ftp and http are 1000.

To save netfilter rule matching work, if the CONNMARK is set, then it will be used to set nfmark.

If a CONNMARK is already set on this http stream, it will be kept. Then if you redefine 1:1000 as another meaning, then this http carrying 1:1000 will be mis-classified.

I think you should start by decoupling the classification away from your qdisc.

Sorry for entering this discussion so late.

* jamal <[email protected]> 2005-04-18 09:14

Quoted 2 lines

I think you should start by decoupling the classification away from your qdisc.

Here are my thoughts on per flow queueing, actually the name "classification controlled queues" is be more accurate.

First of all the whole problem must be divided into two parts:

1) queueing with per flow specific queueing parameters, i.e. the flow serves a certain purpose and is known by static parameters.
2) queueing with generic parameters, i.e. the purpose of a flow is solely to be fair, there is no difference between each flow.

Both these cases can be handled with the current set of qdiscs and classificiation tools but often a combination of both is needed and that's where my thought begins:

We use tc_classid to describe a flow but also to describe its assignment to the corresponding flow group (n flows are grouped together into a group to define a namespace, generally at the level of a qdisc).

The tc_classid can be set via actions, either by using a generic action that creates a flowid out of the common tuple or by providing an own simple-action for customization, e.g. one could construct tc_classid ::= nfmark << 16 + hash(flowid)

tc_classid is interpreted by either one of the existing qdiscs for static assignment or a new qdisc named "alloctor"

The purpose of the allocator is to create qdiscs on demand, destroy them after they expired and to act as a muxer to enqueue into the dynamic leaf qdiscs. The alloactor can be configured to interpet the MSB 16bits of tc_classid as a flow group id and enqueue the skb to the corresponding clasfull qdisc with matches TC_H_MAJ_MASK bits.

The following is in attempt to convert my scribbling on paper into ASCII:

Use Case 1: Per flow queues using TBF

                   2. +-----------+  +------------+
                   +->| cls_basic |->| act_flowid |
                   |  +-----------+  +------------+
      1.    +---------------+              |
  --------->| sch_allocator |<-------------+
            +---------------+        3. tc_classid=<flowid>
                   |4.
       +-----------+---------+- - - - - -
       |           |         |           |
    +-----+     +-----+   +-----+     + - - +
    | TBF |     | TBF |   | TBF |     | TBF |
    +-----+     +-----+   +-----+     + - - +

sch_alloctor configuration:
- no flow group map
- default policy: allocate TBF for every tc_classid && enqueue to new qdisc
- default template: tbf add rtnetlink message
- default deletion template: tbf del rtnetlink message

cls_basic configuration:
- always true

act_flowid configuration:
- default: generate flowid hash and store in tc_classid

Use Case 2: Flow groups

                     3. +---------+
                     +->| em_meta |
                     |  +---------+
                     +----+  |
                          |  v           4.
                   2. +-----------+  +-----------------+
                   +->| cls_basic |->| act_cust_flowid |
                   |  +-----------+  +-----------------+
      1.    +-----------------+               |
  --------->| sch_allocator_1 |<--------------+
            +-----------------+         5. tc_classid=(nfmark<<16)+(flowid&0xFF)
                   |6.
       +-----------+---+----------------+
       | 11:/12:       | 13:            | *:
    +-----+     +-----------------+ +---------+
    | HTB |     | sch_allocator_2 | | default |
    +-----+     +-----------------+ +---------+
       |               |
       |       +-------+- - - -     
       |       |       |       |
       |    +-----+ +-----+ + - - +
       |    | TBF | | TBF | | TBF |
       |    +-----+ +-----+ + - - +
       |
       |
       +------------------+
                          |
               +----------+--------------+
               |                         |
         +------------+            +------------+
         | Class 20:1 |            | Class 20:2 |
         +------------+            +------------+
               |                         |
     +---------+- - - - -              .....
     |         |         |
 +-------+ +-------+ +- - - -+
 | Class | | Class | | Class |
 +-------+ +-------+ +- - - -+

sch_alloctor_1 configuration:
- flow group map:

     [11:] create class HTB parent 20:1 && enqueue to 20:
     [12:] create class HTB parent 20:2 && enqueue to 20:
     [13:] enqueue to sch_allocator_2

- default policy: enqueue to default qdisc

sch_allocator_2 configuration:
- no flow group map
- default policy: allocate TBF for every tc_classid && enqueue to new qdisc
- default template: tbf add rtnetlink message
- default deletion template: tbf del rtnetlink message

cls_basic configuration:
- always true

em_meta configuration:
- filter out unknown nfmarks

act_cust_flowid configuration:
- (nfmark<<16)+(flowid&0xff)

So basically what sch_allocator does is look at tc_classid, lookup the corresponding flow in the flow map or use the default action, execute the action, i.e. process the netlink message via a worker thread, rewrite tc_classid if needed, manage the created qdiscs/classes, account their last activity and destroy them eventually after no activity for a certain configurable time by executing the corresponding deletion netlink message.

Thoughts?

In your big piture,

1. the dynamic allocated classids prepresent streams (I avoid using flow here ntentionally)
2. the dynamic created TBFs are mapped 1:1 to classids, to provide rate control

Let's simplify it to

1. namespace represent streams
2. rate controls for every name in the namespace (1:1 map)

1. there is no necessity that namespace must be classid space.

2. considering the resemblance of streams (they usually are the same application), the rate control can be simplified. TBF or HTB is overkill.

3. grouped rate control method is not suitable for single stream.

4. fairness on streams, and total guarantee ( rate * n) can guarantee n streams very well

5. per stream rate limit and total limit ( rate * n * 1.xx ) make sense for bandwidth efficiency.

6. precisely counting of streams is necessary (when streams is more than expected, existing streams are guaranteed, new streams are not guaranteed, so at least some will work, not all don't work)

What FRG does:

1. the namespace is conntracks of streams;
2. rate control algorithm is very simple, based on the token bucket;
3. grouped rate control (HTB) is only used to do total guarantee
4. provides fairness on streams, and there is m * rate guarantee for dynamic m streams;
5. per stream rate limit, total limit ( rate * max_streams * 1.05)
6. precisely counting of streams, and guarantees existing max_streams stream.

* Wang Jian <[email protected]> 2005-04-19 02:01

Quoted 9 lines

In your big piture,

1. the dynamic allocated classids prepresent streams (I avoid using flow here ntentionally)
2. the dynamic created TBFs are mapped 1:1 to classids, to provide rate control

Let's simplify it to

Quoted 2 lines

1. namespace represent streams
2. rate controls for every name in the namespace (1:1 map)

This is only true for use 1 where the allocator creates indepdendent qdiscs. Look at use case 2 where a major classid of 11: and 12: create htb class siblings, this even allows to divided one big flow namespaces into various group but still respecting global policies.

I understand all of your arguments but I would like to, if possible, avoid to add yet another quite specific qdisc which could have been implemented in a generic way for everyone to use. Your FRG basically does what the alloctor + classifier + action + qdiscs can do but it is orientied at one specific use case.

Let's analyze your enqueue()

1) perflow_is_valid() // BTW, I think you have a typo in there, 2 times TCP ;-> Should be done in the classifier with ematches:
... ematch meta(PROTOCOL eq IP) AND
(cmp(ip_proto eq TCP) OR cmp(ip_proto eq UDP) ..)

2) perflow_(fill|find|new)_tuple()
Should be done in the classifier as an action

3) qsch->q.qlen >= q->qlen
Must be done in the qdisc after classification so this would go into the allocator.

4) flow->timer
Must be handled by the alloctor

5) rate limiting
IMHO: Should be done in separate qdiscs

Advantages?
- What happens if you want to allow yet another protocol in your flow? You have to change sources etc.
- Protocol specific flow hashing? No problem, replace the action.
- ...

The only disadvantage I can see is a possible performance bottleneck but this must be proved first by numbers.

So basically the direction we want to go is to strict separate the classification from the queueing to allow the user to customize everything by replacing small components. It might be worth to read up on the discussion on "ematch" and "action" over the last 3 months.

Quoted 5 lines

I understand all of your arguments but I would like to, if possible, avoid to add yet another quite specific qdisc which could have been implemented in a generic way for everyone to use. Your FRG basically does what the alloctor + classifier + action + qdiscs can do but it is orientied at one specific use case.

Agree. I will maintain my code out of kernel tree, in case someone feels my frg is usefull for his/her special case.

The other disadvantage is that the dynamic classid used is not predicted by user space, it is very tricky for user space to handle the classid allocation then (I mean for the management system like web management). That is what I try to avoid so far.

I agree to this. But I must iterate one thing: the design should be friendly to user space management for a heavy usage.

I had another look at your code and noticed the GFP_KERNEL masked kmalloc call in perflow_new_flow() called from perflow_enqueue(), you must change that to GFP_ATOMIC due to softirq context.

Quoted 10 lines · jamal

Quoted 5 lines

The reclassification or #1 will best be left to the user. This is not hard to do.

I scan through other code and find no easy way to redirect non-handled traffic to another class. Can you give me some hint on that?

There are two constructs at the classifier level: the first one is "reclassify" which basically asks the classification activity to restart. Another one is the " continue" construct which basically asks for the classification to continue where the last one ended. Does this explanation help?

Quoted 3 lines

I will extend the concept of flow to include GRE, so pptp VPN can be supported. There are other 'flows' to consider.

I think you should start by decoupling the classification away from your qdisc.

Lets say you have 8 flows; each to be guaranteed 100Kbps. Lets say your wire rate is only 1Mbps.

Then you create policies so that each gets 100Kbps. If they all use their quota you still have 200Kbps to play with. You could then say that out of that 200Kps, 100kbps is to be shared amongst the 8 flows if they exceed their allocated 100Kbps(sharing) and the other 100kbps is for best effort traffic.
In this case, each flow is _guaranteed_ 100Kbps and upto 100Kbps from shared quota if no-one else is using that shared quota.
If multi flows are using the shared 100Kbps then, its given out on first come basis. "Guaranteed" in this case means it is _reserved_ i.e if flow #3 is not using its allocation, flow #2 cant use it.

Ok, so now tell me where you and i are differing on semantics? Is the above what you are also saying?

Quoted 7 lines

Quoted 3 lines

So it seems you want by all means to avoid entering something that will take forever to list. Did i understand this correctly?

Yes. It is special purpose but general enough. I think it's worthy of adding a new qdisc for it to avoid the dirty long listing part.

I am not sure about the "general enough" part. You need to know what is happening at any instance in time if this is to be useful. So that information for listing should be available - you may wish not to display it unless someone asks for verbose output.

Quoted 8 lines

Quoted 7 lines

We can probably avoid insisting on dynamically creating classes maybe. You can rate control before you enqueue and we can use fwmark perhaps. Earlier i also asked whether policing will suffice. Heres an example (maybe dated syntax, but concept still valid) that shows sharing using policers:
http://www.cyberus.ca/~hadi/patches/action/README

Quoted 2 lines

I will look at it later.

Please do so we can have a synchronized discussion.

Quoted 3 lines

If we can do it with one thing, we should avoid creating 1000 things. The policy way works but is dirty.

yes, but that hiding can be hidden at user space for example. There are several levels of verbosity if you insist:
- See nothing
- just see info which says "at the moment we have 234 classes dynamically created"
- get a full listing for each of 234 classes and their attributes.
- get a full listing for each 234 class and their attributes as well as stats.

your policy management/scripts are then responsible to make sure everything is synchronized between iptables and tc.

Once we have the tracker action, this would only need to be doen via tc.