sch_htb.c consume the classes's tokens bellow the HTB_CAN_SEND level
Subsystems (3)
PATCH 1/1 sch_htb.c consume the classes's tokens bellow the HTB_CAN_SEND level
sch_htb.c consume the classes's tokens bellow the HTB_CAN_SEND level.
When a class enters HTB_MAY_BORROW state, it relies on its parents to sent packets. The parent class in HTB_CAN_SEND state only consumes itself and its parents's tokens, but ADD tokens to the classes under its level. It is totally wrong. It means that a class, which sends packets in ceil rate, can also enter HTB_CAN_SEND state now and then.
----net/sched/sch_htb.c | 3 +--
1 file changed, 1 insertion(+), 2 deletions(-)
net/sched/sch_htb.c +1 -2
@@ -629,11 +629,10 @@ static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,if (cl->level >= level) {if (cl->level == level) cl->xstats.lends++; -htb_accnt_tokens (cl, bytes, diff); }else { cl->xstats.borrows++; - cl->tokens += diff;/* we moved t_c; update tokens */ } +htb_accnt_tokens (cl, bytes, diff);htb_accnt_ctokens (cl, bytes, diff); cl->t_c = q->now;
Quoted 6 lines · Changli Gao
sch_htb.cconsume the classes's tokens bellow theHTB_CAN_SENDlevel.When a class enters
HTB_MAY_BORROWstate, it relies on its parents to sent packets. The parent class inHTB_CAN_SENDstate only consumes itself and its parents's tokens, but ADD tokens to the classes under its level. It is totally wrong.
Current code is OK.
Quoted 2 lines
It means that a class, which sends packets
in ceil rate, can also enterHTB_CAN_SENDstate now and then.
Yes, a class is entitled to send on it's own then with it's guaranteed rate, without depending on borrowing.
Jarek P.
Quoted 24 lines
Signed-off-by Changli Gao <[email protected]>----
net/sched/sch_htb.c| 3 +--1 file changed, 1 insertion(+), 2 deletions(-)net/sched/sch_htb.c +1
-2@@ -629,11 +629,10 @@ static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,if (cl->level >= level) {if (cl->level == level) cl->xstats.lends++; -htb_accnt_tokens (cl, bytes, diff); }else { cl->xstats.borrows++; - cl->tokens += diff;/* we moved t_c; update tokens */ } +htb_accnt_tokens (cl, bytes, diff);htb_accnt_ctokens (cl, bytes, diff); cl->t_c = q->now;
Quoted 6 lines · Jarek Poplawski
Quoted 3 lines
It means that a class, which sends packets
in ceil rate, can also enterHTB_CAN_SENDstate now and then.Yes, a class is entitled to send on it's own then with it's guaranteed rate, without depending on borrowing.
I don't think so. The class should _NOT_ enter HTB_CAN_SEND mode when its data rate is higher than its rate specification. In other word, a class should enter HTB_CAN_SEND mode only when its data rate isn't higher than its rate specification. Otherwise, it will get additional tokens and reach a higher data rate than its ceil specification. This may affect other classes.
Signature · 2 lines
Regards， Changli Gao([email protected])
Quoted 8 lines · Changli Gao
Quoted 6 lines · Jarek Poplawski
Quoted 3 lines
It means that a class, which sends packets
in ceil rate, can also enterHTB_CAN_SENDstate now and then.Yes, a class is entitled to send on it's own then with it's guaranteed rate, without depending on borrowing.
Quoted 6 lines
I don't think so. The class should _NOT_ enter
HTB_CAN_SENDmode when its data rate is higher than its rate specification. In other word, a class should enterHTB_CAN_SENDmode only when its data rate isn't higher than its rate specification. Otherwise, it will get additional tokens and reach a higher data rate than its ceil specification. This may affect other classes.
The ceil specification is controlled only by ctokens, which are always updated, so no such risk.
Regards,
Jarek P.
Quoted 4 lines · Jarek Poplawski
The ceil specification is controlled only by ctokens, which are always updated, so no such risk.
Nevertheless, updating tokens is necessary too.
Signature · 2 lines
Regards， Changli Gao([email protected])
Quoted 6 lines · Changli Gao
Quoted 4 lines · Jarek Poplawski
The ceil specification is controlled only by ctokens, which are always updated, so no such risk.
Nevertheless, updating tokens is necessary too.
If it's really necessary you should present some test case fixed by your patch, I guess.
In the meantime let's consider what could be broken:
class 1:1 (parent) rate 10 packets/sec
class 1:2 rate 5 packets/sec ceil 10 packets/sec class 1:3 rate 5 packets/sec ceil 10 packets/sec
class 1:2 doesn't use all its rate, and sends every other second
(in even seconds)
class 1:3 sends 10 packets during the first second, so with your
patch it will use its tokens for 2 seconds
class 1:2 uses its rate in the second second..., so class 1:1
can't lend anything
class 1:3 can only borrow, so it won't be able to send during
this second anything
So, the effect would be class 1:3 sending every odd second 10 packets while every even second - nothing...
Of course the example is a simplification of the htb algorithm. There should be also considered priority of borrowing, which should add similar effects even with regular traffic. But generally the guaranteed rates would be simply... less guaranteed.
Regards,
Jarek P.
Quoted 25 lines · Jarek Poplawski
Quoted 6 lines · Changli Gao
Quoted 4 lines · Jarek Poplawski
The ceil specification is controlled only by ctokens, which are always updated, so no such risk.
Nevertheless, updating tokens is necessary too.
If it's really necessary you should present some test case fixed by your patch, I guess.
In the meantime let's consider what could be broken:
class 1:1 (parent) rate 10 packets/sec
class 1:2 rate 5 packets/sec ceil 10 packets/sec class 1:3 rate 5 packets/sec ceil 10 packets/secclass 1:2 doesn't use all its rate, and sends every other second (in even seconds)
class 1:3 sends 10 packets during the first second, so with your patch it will use its tokens for 2 seconds class 1:2 uses its rate in the second second..., so class 1:1 can't lend anything
class 1:3 can only borrow, so it won't be able to send during this second anything
Quoted 2 lines
So, the effect would be class 1:3 sending every odd second 10 packets while every even second - nothing...
class 1:3 can send, as its parent rate is 10, but class 1:2 only uses half of it, and class 1:1 is still in HTB_CAN_SEND mode.
The result is, hasn't any difference with or without my patch :
class 1:1 sends 10 packets in odd seconds, and 5 packets in even seconds. class 1:2 sends 5 packets in even seconds.
class 1:1 (parent) sends 10 packets in every second.
Let's think this case in another way: which class sends packets in even seconds first, class 1:2 or class 1:3.
With my patch, as 1:3 in HTB_MAY_BORROW mode, and 1:2 in HTB_CAN_SEND mode, so 1:2 sends all its 5 packets first.
Without my patch, as 1:2 and 1:3 are both in HTB_CAN_SEND mode, the sequence is undetermined. In other word, 1:2 and 1:3 are treated fairly, and it isn't fair for 1:2, because 1:2 sends nothing in odd seconds, and has no deficit in rate as 1:3.
Signature · 2 lines
Regards， Changli Gao([email protected])
Quoted 26 lines · Changli Gao
Quoted 25 lines · Jarek Poplawski
Quoted 6 lines · Changli Gao
Quoted 4 lines · Jarek Poplawski
The ceil specification is controlled only by ctokens, which are always updated, so no such risk.
Nevertheless, updating tokens is necessary too.
If it's really necessary you should present some test case fixed by your patch, I guess.
In the meantime let's consider what could be broken:
class 1:1 (parent) rate 10 packets/sec
class 1:2 rate 5 packets/sec ceil 10 packets/sec class 1:3 rate 5 packets/sec ceil 10 packets/secclass 1:2 doesn't use all its rate, and sends every other second (in even seconds)
class 1:3 sends 10 packets during the first second, so with your patch it will use its tokens for 2 seconds class 1:2 uses its rate in the second second..., so class 1:1 can't lend anything
class 1:3 can only borrow, so it won't be able to send during this second anything
Quoted 8 lines
Quoted 2 lines
So, the effect would be class 1:3 sending every odd second 10 packets while every even second - nothing...
class 1:3 can send, as its parent rate is 10, but class 1:2 only uses half of it, and class 1:1 is still in
HTB_CAN_SENDmode.The result is, hasn't any difference with or without my patch :
class 1:1 sends 10 packets in odd seconds, and 5 packets in even seconds.
I guess you meant class 1:3, and there is a difference: it sends 5 packets in even seconds only if it manages to borrow from 1:1, but it's not _guaranteed_ at all. In this particular case it's quite probable class 1:2 will send 10 packets in even seconds instead, or with some finer borrowing control it could be: class 1:2 8 packets, class 1:3 2 packets, as well.
Quoted 11 lines
class 1:2 sends 5 packets in even seconds. class 1:1 (parent) sends 10 packets in every second.
Let's think this case in another way: which class sends packets in even seconds first, class 1:2 or class 1:3.
With my patch, as 1:3 inHTB_MAY_BORROWmode, and 1:2 inHTB_CAN_SENDmode, so 1:2 sends all its 5 packets first.
Without my patch, as 1:2 and 1:3 are both inHTB_CAN_SENDmode, the sequence is undetermined. In other word, 1:2 and 1:3 are treated fairly, and it isn't fair for 1:2, because 1:2 sends nothing in odd seconds, and has no deficit in rate as 1:3.
The token bucket (cl->buffer) is just to account distinctly when a class is entitled to send and when it actually does send within its rate. The fairness is controlled by classes itself with HTB_CAN_SEND state. Using this bucket to account for borrowed sending deprives us of this precise information. "The fairness" would be controlled by priorities of borrowing instead (see above).
Regards,
Jarek P.
Quoted 21 lines · Jarek Poplawski
Quoted 21 lines
Quoted 20 lines
If it's really necessary you should present some test case fixed by your patch, I guess.
In the meantime let's consider what could be broken:
class 1:1 (parent) rate 10 packets/sec
class 1:2 rate 5 packets/sec ceil 10 packets/sec class 1:3 rate 5 packets/sec ceil 10 packets/secclass 1:2 doesn't use all its rate, and sends every other second (in even seconds)
class 1:3 sends 10 packets during the first second, so with your patch it will use its tokens for 2 seconds class 1:2 uses its rate in the second second..., so class 1:1 can't lend anything
class 1:3 can only borrow, so it won't be able to send during this second anythingSo, the effect would be class 1:3 sending every odd second 10 packets while every even second - nothing...
Quoted 7 lines
Quoted 5 lines
class 1:3 can send, as its parent rate is 10, but class 1:2 only uses half of it, and class 1:1 is still in
HTB_CAN_SENDmode.The result is, hasn't any difference with or without my patch :
class 1:1 sends 10 packets in odd seconds, and 5 packets in even seconds.I guess you meant class 1:3.
You are right. :)
Quoted 6 lines
and there is a difference: it sends 5
packets in even seconds only if it manages to borrow from 1:1, but it's not _guaranteed_ at all. In this particular case it's quite probable class 1:2 will send 10 packets in even seconds instead, or with some finer borrowing control it could be: class 1:2 8 packets, class 1:3 2 packets, as well.
It is just correct. You focus on 1 second fairness, while I focus on 2 seconds fairness.
Quoted 13 lines
Quoted 4 lines
class 1:2 sends 5 packets in even seconds. class 1:1 (parent) sends 10 packets in every second.
Quoted 8 lines
Let's think this case in another way: which class sends packets in even seconds first, class 1:2 or class 1:3.
With my patch, as 1:3 inHTB_MAY_BORROWmode, and 1:2 inHTB_CAN_SENDmode, so 1:2 sends all its 5 packets first.
Without my patch, as 1:2 and 1:3 are both inHTB_CAN_SENDmode, the sequence is undetermined. In other word, 1:2 and 1:3 are treated fairly, and it isn't fair for 1:2, because 1:2 sends nothing in odd seconds, and has no deficit in rate as 1:3.
Quoted 7 lines
The token bucket (
cl->buffer) is just to account distinctly when a class is entitled to send and when it actually does send within its rate. The fairness is controlled by classes itself withHTB_CAN_SENDstate. Using this bucket to account for borrowed sending deprives us of this precise information. "The fairness" would be controlled by priorities of borrowing instead (see above).
The token bucket and ctoken bucket both use cl->mbuffer to control rate granularities. If we don't account token bucket when the corresponding class in HTB_MAY_BORROW mode, the cl->mbuffer will become useless.
Signature · 2 lines
Regards， Changli Gao([email protected])
On Wed, Nov 04, 2009 at 05:16:42PM +0800, Changli Gao wrote:
...
Quoted 2 lines
It is just correct. You focus on 1 second fairness, while I focus on 2 seconds fairness.
The whole example was very simplified, so it all would certainly differ in time and real sends, especially with an interaction of more classes. But, generally, main HTB algorithm seems to be quite well tested against various fair and unfair cases, starting from the author's examples:
http://luxik.cdi.cz/~devik/qos/htb/manual/userg.htm
so, I guess, this type of a bug would really show somewhere long time ago.
Quoted 4 lines
The token bucket and ctoken bucket both use
cl->mbufferto control rate granularities. If we don't account token bucket when the corresponding class inHTB_MAY_BORROWmode, thecl->mbufferwill become useless.
cl->mbuffer is only to limit some extreme effects, so more of an exception, not a main tool of rate control. (It really should be useless most of the time if classes don't stop sending and aren't deprived of their full rate for really long time.)
Regards,
Jarek P.
Quoted 19 lines · Jarek Poplawski
On Wed, Nov 04, 2009 at 05:16:42PM +0800, Changli Gao wrote:
...Quoted 2 lines
It is just correct. You focus on 1 second fairness, while I focus on 2 seconds fairness.
The whole example was very simplified, so it all would certainly differ in time and real sends, especially with an interaction of more classes. But, generally, main HTB algorithm seems to be quite well tested against various fair and unfair cases, starting from the author's examples:
http://luxik.cdi.cz/~devik/qos/htb/manual/userg.htm
so, I guess, this type of a bug would really show somewhere long time ago.Quoted 4 lines
The token bucket and ctoken bucket both use
cl->mbufferto control rate granularities. If we don't account token bucket when the corresponding class inHTB_MAY_BORROWmode, thecl->mbufferwill become useless.
Quoted 4 lines
cl->mbufferis only to limit some extreme effects, so more of an exception, not a main tool of rate control. (It really should be useless most of the time if classes don't stop sending and aren't deprived of their full rate for really long time.)
Hello,
yes you are right. If I remember correctly, I tried to charge "rate"
tokens up to root in early versions (which makes some sense) but problem
is with many interior classes stuck at extreme mbuffer value, losing
responsivity. Also it didn't played well with prio settings (class
stalls).
Bacause we don't charge "rate" now, some amount of burst can accumulate
in each interior class and decrease fairness at the same prio level a bit. However from measurments I did, these bursts of unfairness are hidded by regular "bursting" of rate and ceil token buckets.
devik
Quoted 7 lines · Martin Devera
Hello,
yes you are right. If I remember correctly, I tried to charge "rate" tokens up to root in early versions (which makes some sense) but problem is with many interior classes stuck at extreme mbuffer value, losing responsivity.
It is strange. Would you like describe it more clearly?
Quoted 2 lines
Also it didn't played well with prio settings (class stalls).
Was it the cause?
Quoted 5 lines
Bacause we don't charge "rate" now, some amount of burst can accumulate in each interior class and decrease fairness at the same prio level a bit. However from measurments I did, these bursts of unfairness are hidded by regular "bursting" of rate and ceil token buckets.
One case for unfairness.
Signature · 2 lines
Regards， Changli Gao([email protected])
Quoted 9 lines · Changli Gao
Quoted 6 lines · Martin Devera
Hello,
yes you are right. If I remember correctly, I tried to charge "rate" tokens up to root in early versions (which makes some sense) but problem is with many interior classes stuck at extreme mbuffer value, losing responsivity.
It is strange. Would you like describe it more clearly?
oops, forget it, I mixed it with different problem I remember :-) The idea is to charge classe's tokens when it sends.
It always must be under ceil thus when it sends we can charge ctokens (it must have some in order to be in CAN_SEND). If it borrows, we don't charge it because doesn't send from its own rate but rather from parent's rate. Thus charge only parent. Because parent gave it rate as gift, free of charge, it has it in addition to its own rate.
Quoted 9 lines · Changli Gao
Quoted 6 lines · Martin Devera
Hello,
yes you are right. If I remember correctly, I tried to charge "rate" tokens up to root in early versions (which makes some sense) but problem is with many interior classes stuck at extreme mbuffer value, losing responsivity.
It is strange. Would you like describe it more clearly?
Ahh I'm starting to understand. You are concerned mainly with
cl->tokens += diff; /* we moved t_c; update tokens */
am I right ?
Quoted 7 lines · Martin Devera
Ahh I'm starting to understand. You are concerned mainly with
cl->tokens+= diff; /* we movedt_c; update tokens */am I right ?
If we don't need to charge the tokens, updating it is necessary. I am arguing the tokens isn't updated with the ctokens when the corresponding class is in HTB_MAY_BORROW mode.
Signature · 2 lines
Regards， Changli Gao([email protected])
Quoted 12 lines · Changli Gao
Quoted 6 lines · Martin Devera
Ahh I'm starting to understand. You are concerned mainly with
cl->tokens+= diff; /* we movedt_c; update tokens */am I right ?
If we don't need to charge the tokens, updating it is necessary. I am arguing the tokens isn't updated with the ctokens when the corresponding class is in
HTB_MAY_BORROWmode.
Ok, then the reason is in "logic". When you have parent P and children
A,B each with half of rate and only A is sending, than we want A to use
its own rate and also B's rate. B's rate is available as excess in P.
Here I see correct to charge part to A and part to P, while you want
to charge one P and twice A. Only mbuffer will limit the duplicity.
And it is not good idea because tokens can go very negative and then ittroduce A's stall for some time. I see no principial benefit...
Quoted 11 lines · Martin Devera
Changli Gao wrote:
Ok, then the reason is in "logic". When you have parent P and children A,B each with half of rate and only A is sending, than we want A to use its own rate and also B's rate. B's rate is available as excess in P. Here I see correct to charge part to A and part to P, while you want to charge one P and twice A. Only mbuffer will limit the duplicity. And it is not good idea because tokens can go very negative and then ittroduce A's stall for some time.
I see no principial benefit...
I get it. After reviewing the code, I find mbuffer is 1 minute. It means that bandwidth will be unfair between A and B(A/B = 1/3) for at least 2 minute long. It is unacceptable. I'm wrong, and need to think it again!
Signature · 2 lines
Regards， Changli Gao([email protected])
Quoted 5 lines · Jarek Poplawski
On Wed, Nov 04, 2009 at 05:16:42PM +0800, Changli Gao wrote:
...Quoted 2 lines
It is just correct. You focus on 1 second fairness, while I focus on 2 seconds fairness.
Quoted 9 lines
The whole example was very simplified, so it all would certainly differ in time and real sends, especially with an interaction of more classes. But, generally, main HTB algorithm seems to be quite well tested against various fair and unfair cases, starting from the author's examples:
http://luxik.cdi.cz/~devik/qos/htb/manual/userg.htm
so, I guess, this type of a bug would really show somewhere long time ago.
This documentation is old, and after the last update 5.5.2002, there were still bugs: http://luxik.cdi.cz/~devik/qos/htb/ .
Quoted 10 lines
Quoted 4 lines
The token bucket and ctoken bucket both use
cl->mbufferto control rate granularities. If we don't account token bucket when the corresponding class inHTB_MAY_BORROWmode, thecl->mbufferwill become useless.
cl->mbufferis only to limit some extreme effects, so more of an exception, not a main tool of rate control. (It really should be useless most of the time if classes don't stop sending and aren't deprived of their full rate for really long time.)
I don't think so. Although a class's tokens may be negative, but its ctokens may be positive. Charging its tokens is to prevent its cmode from being changed to HTB_CAN_SEND from HTB_CANT_SEND directly.
Signature · 2 lines
Regards， Changli Gao([email protected])
On Wed, Nov 04, 2009 at 07:21:48PM +0800, Changli Gao wrote:
...
Quoted 9 lines
Quoted 5 lines
cl->mbufferis only to limit some extreme effects, so more of an exception, not a main tool of rate control. (It really should be useless most of the time if classes don't stop sending and aren't deprived of their full rate for really long time.)I don't think so. Although a class's tokens may be negative, but its ctokens may be positive. Charging its tokens is to prevent its cmode from being changed to
HTB_CAN_SENDfromHTB_CANT_SENDdirectly.
I think, you should really better show some tests proving your patch is needed and doesn't affect a case I described, instead of trying to discuss the meaninig of all HTB variables here.
Regards,
Jarek P.
Quoted 10 lines · Jarek Poplawski
Quoted 4 lines · Changli Gao
I don't think so. Although a class's tokens may be negative, but its ctokens may be positive. Charging its tokens is to prevent its cmode from being changed to
HTB_CAN_SENDfromHTB_CANT_SENDdirectly.I think, you should really better show some tests proving your patch is needed and doesn't affect a case I described, instead of trying to discuss the meaninig of all HTB variables here.
I test it before sending it here, but it doesn't show any obvious difference as Martin said, no worse and no better. I don't know how to construct a test to show you the bad effect you worry about. Any suggestion about the test?
Signature · 2 lines
Regards， Changli Gao([email protected])
Quoted 7 lines · Changli Gao
Quoted 6 lines · Jarek Poplawski
Quoted 4 lines · Changli Gao
I don't think so. Although a class's tokens may be negative, but its ctokens may be positive. Charging its tokens is to prevent its cmode from being changed to
HTB_CAN_SENDfromHTB_CANT_SENDdirectly.
Quoted 7 lines
Quoted 4 lines
I think, you should really better show some tests proving your patch is needed and doesn't affect a case I described, instead of trying to discuss the meaninig of all HTB variables here.
I test it before sending it here, but it doesn't show any obvious difference as Martin said, no worse and no better.
Strange... How this patch could be needed or even "necessary", and do "no worse and no better" at the same time.
Quoted 3 lines
I don't know how to
construct a test to show you the bad effect you worry about. Any suggestion about the test?
E.g. something like I described, but only rates 50kbit and 100kbit instead of 5 and 10 packets/sec.
Regards,
Jarek P.