LARTC - May 2002 - More on qdiscs

I notice one other small problem with my modified version of SFQ.
The fact that packets can be dropped at dequeue time is incompatible
with the way HTB (and probably CBQ and others modeled on it) keep 
statistics.  When I fill a low rate queue causing packets to expire
and be dropped at dequeue I get interesting statistics like this:

This is my variant of SFQ
 qdisc plfq 8016: dev eth1
 ...
 Sent 17468 bytes 166 pkts (dropped 833, overlimits 0)
 ...
 qdisc htb 1: dev eth1 r2q 10 default 2 dcache 0
 deq_util 1/1000000 deq_rate 0 trials_per_deq 0
 dcache_hits 0 direct_packets 0
 Sent 32626 bytes 309 pkts (dropped 690, overlimits 1126)
 backlog 143p

Note that plfq, which is inside of htb, thinks it has dropped more
packets than htb has.  The reason is that htb considers a packet to be
"sent" when it''s enqueued.  I notice in retrospect that even
with
current SFQ, the statistics are not correct.  The reason is that it''s
possible to successfully enqueue packet#1 (at which point HTB adds its
length to the number of bytes "sent)", then fail to enqueue packet#2.
But within SFQ this "failure" might really mean that packet#2 was
accepted to be sent later and it displaced packet#1.  It happens that
this "replacement" keeps the packet count correct, but not the byte
count.  One can imagine another version of SFQ that, instead of
limiting the number of packets in the queue, limits the number of
bytes.  In that case the number of packets would not be correct
either. 

I think that HTB (and other classful qdiscs) should count the
number of bytes and packets "sent" when they''re dequeued, not
when
they''re enqueued.  It''s an interesting point that, at the
moment, I
don''t see any way for the classful qdisc to know how many packets and
bytes were dropped.  However, I think it would be useful to know
instead how many were passed to enqueue.  Then you''d get a report like
 Enqueued 32626 bytes 309 pkts, Dequeued 17468 bytes 166 pkts
where the difference is the sum of what''s been dropped and
what''s
still in the queue.

Hi,
only a few notes on the theme. You are right with the displacement
and bad enqueue byte counters. Maybe it would be better to cound
packets at dequeue time only in clasfull qdisc. It also makes better
sense because qdosc can also instruct SFQ to drop packet - this drop
is then not decremented from HTB/CBQ''s stats.
HTB uses enqueue time counting because CBQ does it too and at very
begining I based my work on CBQ. Seems it is time to change things.

Another important info: you really CAN''T drop packets in dequeue
routine if you don''t want to fool classfull parent. Many logic
in CBQ/HTB/ATM/PRIO qdisc is based on the existence of backlog.
When you drop in dequeue, parent will think that he itself still
has some packets somewhere (in children) and will constantly attempt
to find them. And will be confused by the fact that it can''t.

Enqueue routine can give you confirmation of packet enqueue, drop
routine the same. Only dequeue can''t say hey there is your skb and by
the way two others was dropped. What a pity.

SOLUTIONS:
One way is to monitor (store) q.qlen variable of all children of
classfull qdisc. When I call enqueue/drop/dequeue on it I''ll see
its discrepancy agains last stored value and will update my counter
accordingly. In the same way we could add q.bytelen and then we would be
able to do the same for bytes - but this is not neccessary probably
as we need to know only bytes dequeued ...

There is other way - add parameter to dequeue routine which tells us
how many packets we should out qlen decrease by. But I think that former
approach is simpler and prone to "silent" drops (for example by some
timer).
Don do you plan to implement these corrections for CBQ/PRIO ? I''ll do
the change for HTB.
devik

On Sat, 4 May 2002, Don Cohen wrote:
>
> I notice one other small problem with my modified version of SFQ.
> The fact that packets can be dropped at dequeue time is incompatible
> with the way HTB (and probably CBQ and others modeled on it) keep
> statistics.  When I fill a low rate queue causing packets to expire
> and be dropped at dequeue I get interesting statistics like this:
>
> This is my variant of SFQ
>  qdisc plfq 8016: dev eth1
>  ...
>  Sent 17468 bytes 166 pkts (dropped 833, overlimits 0)
>  ...
>  qdisc htb 1: dev eth1 r2q 10 default 2 dcache 0
>  deq_util 1/1000000 deq_rate 0 trials_per_deq 0
>  dcache_hits 0 direct_packets 0
>  Sent 32626 bytes 309 pkts (dropped 690, overlimits 1126)
>  backlog 143p
>
> Note that plfq, which is inside of htb, thinks it has dropped more
> packets than htb has.  The reason is that htb considers a packet to be
> "sent" when it''s enqueued.  I notice in retrospect that
even with
> current SFQ, the statistics are not correct.  The reason is that
it''s
> possible to successfully enqueue packet#1 (at which point HTB adds its
> length to the number of bytes "sent)", then fail to enqueue
packet#2.
> But within SFQ this "failure" might really mean that packet#2 was
> accepted to be sent later and it displaced packet#1.  It happens that
> this "replacement" keeps the packet count correct, but not the
byte
> count.  One can imagine another version of SFQ that, instead of
> limiting the number of packets in the queue, limits the number of
> bytes.  In that case the number of packets would not be correct
> either.
>
> I think that HTB (and other classful qdiscs) should count the
> number of bytes and packets "sent" when they''re
dequeued, not when
> they''re enqueued.  It''s an interesting point that, at the
moment, I
> don''t see any way for the classful qdisc to know how many packets
and
> bytes were dropped.  However, I think it would be useful to know
> instead how many were passed to enqueue.  Then you''d get a report
like
>  Enqueued 32626 bytes 309 pkts, Dequeued 17468 bytes 166 pkts
> where the difference is the sum of what''s been dropped and
what''s
> still in the queue.
>
> _______________________________________________
> LARTC mailing list / LARTC@mailman.ds9a.nl
> http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
>
>

Eh more info if you are interested:

I already do some backlog fixes in HTB2/3. In CBQ there
is possible to drop class which has backlog already. And
this packlog is not substracted from CBQ''s one.
I feel it as error however it needs to be tested. The
same holds for attaching inner qdisc - if previous one
had backlog then CBQ''s backlog will be probably messed up.

devik

Martin Devera writes:
  Hi,
  only a few notes on the theme. You are right with the displacement
  and bad enqueue byte counters. Maybe it would be better to cound
  packets at dequeue time only in clasfull qdisc. It also makes better
  sense because qdosc can also instruct SFQ to drop packet - this drop

I don''t understand.  What other qdisc instructs SFQ to drop?

  is then not decremented from HTB/CBQ''s stats.
  HTB uses enqueue time counting because CBQ does it too and at very

I figured that''s why it worked that way.

  begining I based my work on CBQ. Seems it is time to change things.

  Another important info: you really CAN''T drop packets in dequeue
  routine if you don''t want to fool classfull parent. Many logic
  in CBQ/HTB/ATM/PRIO qdisc is based on the existence of backlog.

I gather you only care whether this qdisc is waiting to send, not how
much is in the queue.

  When you drop in dequeue, parent will think that he itself still
  has some packets somewhere (in children) and will constantly attempt
  to find them. And will be confused by the fact that it can''t.

  Enqueue routine can give you confirmation of packet enqueue, drop
  routine the same. Only dequeue can''t say hey there is your skb and by
  the way two others was dropped. What a pity.

  SOLUTIONS:
  One way is to monitor (store) q.qlen variable of all children of
  classfull qdisc. When I call enqueue/drop/dequeue on it I''ll see
  its discrepancy agains last stored value and will update my counter

This seems like the right solution, except that you shouldn''t even
need to store a counter.  Just use the one in the child qdisc.
BTW, I think you are justified in assuming that this counter can only
change in two ways: decrease when dequeue is called (but possibly by
more than one packet) and increase by 1 when enqueue is called.
And I guess also requeue.  Which raises another problem, since that''s
not called by the parent, right?

  accordingly. In the same way we could add q.bytelen and then we would be
  able to do the same for bytes - but this is not neccessary probably
  as we need to know only bytes dequeued ...

My impression is that every qdisc is currently supposed to keep track
of # packets in the queue, but not necessarily # bytes.
Best not to change that, especially since we don''t even have any
currently proposed use for it.

  There is other way - add parameter to dequeue routine which tells us
  how many packets we should out qlen decrease by. But I think that former
  approach is simpler and prone to "silent" drops (for example by some
  timer).

I think you''re saying the former approach is better, but
"prone"
suggests otherwise.

I prefer the former approach.  It''s better for all the other qdiscs
out there to keep working without change.  There are only a few 
classful qdiscs that would have to change, and they could still work
unchanged with qdiscs that don''t do silent drops.

  Don do you plan to implement these corrections for CBQ/PRIO ?

Not any time soon.  The last time I tried to read CBQ it was in order
to figure out what all those parameters mean, and I didn''t get very
far.  Now that I no longer use it I have less incentive.

  I''ll do the change for HTB.
Thanks.
But which ones?
It sounds like you plan to
- count as sent only what''s returned from dequeue
- ignore the return value of enqueue and check the queue length to see
  whether it''s empty
I like those, but also suggested that HTB would be a good place to add
code for dropping stale packets.  If you''re interested in doing that I
should mention: 
Not all packets come with timestamps (e.g., locally generated ones).
Solution: at enqueue, if the timestamp is 0, set it to the current
time.

>   packets at dequeue time only in clasfull qdisc. It also makes better
>   sense because qdosc can also instruct SFQ to drop packet - this drop
>
> I don''t understand.  What other qdisc instructs SFQ to drop?
CBQ only at the moment. It can call q->ops->drop on inner
qdisc as response to overlimit event. It forces system to
converge faster to underlimit state
>   Another important info: you really CAN''T drop packets in dequeue
>   routine if you don''t want to fool classfull parent. Many logic
>   in CBQ/HTB/ATM/PRIO qdisc is based on the existence of backlog.
>
> I gather you only care whether this qdisc is waiting to send, not how
> much is in the queue.
yes ..
>   SOLUTIONS:
>   One way is to monitor (store) q.qlen variable of all children of
>   classfull qdisc. When I call enqueue/drop/dequeue on it I''ll see
>   its discrepancy agains last stored value and will update my counter
>
> This seems like the right solution, except that you shouldn''t even
> need to store a counter.  Just use the one in the child qdisc.
> BTW, I think you are justified in assuming that this counter can only
> change in two ways: decrease when dequeue is called (but possibly by
> more than one packet) and increase by 1 when enqueue is called.
> And I guess also requeue.  Which raises another problem, since
that''s
> not called by the parent, right?
No - you can''t use the q.qlen of inner. It is under inner''s
control
and you can''t change it. And the assumption how it can change should
not be used unless you have some rules for all qdisc how to change
it.
Somewhere in sources you can read that one of qdisc duties is
to ensure that it''s q.qlen value is correct. It doesn''t
restrict
how it can change and when.
I''d suggest for each leaf to maintain last_qlen variable which would
start with 0 (also q.qlen will be 0). Then time to time (in enqueue,
dequeue, drop ....) you can "repair" your own q.qlen by doing:
q.qlen += cl->q.qlen - cl->last_qlen; cl->last_qlen = cl->q.qlen;
for each leaf cl.
Hence xl->last_qlen tells you what part of total q.qlen is "owned"
by
cl.
Simple and robust, isn''t it ?
> I like those, but also suggested that HTB would be a good place to add
> code for dropping stale packets.  If you''re interested in doing
that I
> should mention:
> Not all packets come with timestamps (e.g., locally generated ones).
> Solution: at enqueue, if the timestamp is 0, set it to the current
> time.
It would be better done in fifo/sfq. It is because HTB can do it
only when dequeuing and at that time some packets were already dropped
by SFQ because if has had queues full of "old" packets.
SFQ should maintain pqio queue of all packets and look at head of
the list sometimes to keep its queues frre of old packets and thus
to have room for new ones.
devik

Martin Devera writes:

 > >   SOLUTIONS:
 > >   One way is to monitor (store) q.qlen variable of all children of
 > >   classfull qdisc. When I call enqueue/drop/dequeue on it
I''ll see
 > >   its discrepancy agains last stored value and will update my counter
 > >
 > > This seems like the right solution, except that you
shouldn''t even
 > > need to store a counter.  Just use the one in the child qdisc.
 > > BTW, I think you are justified in assuming that this counter can only
 > > change in two ways: decrease when dequeue is called (but possibly by
 > > more than one packet) and increase by 1 when enqueue is called.
 > > And I guess also requeue.  Which raises another problem, since
that''s
 > > not called by the parent, right?
 > 
 > No - you can''t use the q.qlen of inner. It is under
inner''s control
 > and you can''t change it. And the assumption how it can change
should
 > not be used unless you have some rules for all qdisc how to change
 > it.

The only way I can make sense of this is that we must be
miscommunicating.  I do not propose that HTB alter an SFQ q.qlen.
I propose that HTB read it.  I think you were suggesting that HTB
make its own copy of it, and I was just suggesting that there''s no
need for that copy.

 > Somewhere in sources you can read that one of qdisc duties is
 > to ensure that it''s q.qlen value is correct. It doesn''t
restrict
 > how it can change and when.

I think it''s pretty much necessary from the implementation viewpoint
to make some assumptions.  In particular, you don''t want to look at
all inactive leaves every time you do a dequeue, just to make sure
that they haven''t somehow manufactured their own packets.  Once the
queue is empty you expect it to stay empty until you call enqueue,
right? 

 > I''d suggest for each leaf to maintain last_qlen variable which
would
 > start with 0 (also q.qlen will be 0). Then time to time (in enqueue,
 > dequeue, drop ....) you can "repair" your own q.qlen by doing:
 > q.qlen += cl->q.qlen - cl->last_qlen; cl->last_qlen =
cl->q.qlen;
 > for each leaf cl.
 > Hence xl->last_qlen tells you what part of total q.qlen is
"owned" by
 > cl.
 > Simple and robust, isn''t it ?

I don''t get it.  A qdisc is already supposed to maintain its qlen.
You don''t think that''s being done correctly now?  Why do you
want this
other data?  You''re proposing something that will require changing
every existing qdisc?  Or is this the class (in htb code) trying to
keep a copy of the data in its qdisc?  If the latter, then I guess I
don''t object (since it''s only in your code and transparent to
me), but
I still don''t see why you need it.

 > > I like those, but also suggested that HTB would be a good place to
add
 > > code for dropping stale packets.  If you''re interested in
doing that I
 > > should mention:
 > > Not all packets come with timestamps (e.g., locally generated ones).
 > > Solution: at enqueue, if the timestamp is 0, set it to the current
 > > time.
 > 
 > It would be better done in fifo/sfq. It is because HTB can do it
 > only when dequeuing and at that time some packets were already dropped
 > by SFQ because if has had queues full of "old" packets.

I see, you suggest that I could do better if enqueue started with
something like 
 while (oldest packet expired) drop oldest packet
Of course this is still only an approximation.  There will still be
times when you have to drop a packet but it turns out that, before the
next one is dequeued another packet will have expired (so if you only
knew that you could have saved the packet you dropped before).

 > SFQ should maintain pqio queue of all packets and look at head of
 > the list sometimes to keep its queues frre of old packets and thus
 > to have room for new ones.

I suppose SFQ could still do something like above even if HTB were
dropping expired packets at dequeue.  And this would save all qdiscs
the work of dropping expired packets at dequeue, which is still needed
even if you also check at enqueue.  Also, only dropping at dequeue is
a good approximation to what you want in the common case where the
queue size is too large for the low rate assigned to the class.  I
argue it''s much better to do this in a few classful qdiscs than to ask
for it to be done by all the others.

Don Cohen wrote:
>  > > I like those, but also suggested that HTB would be a good place
to add
>  > > code for dropping stale packets.  If you''re interested
in doing that I
>  > > should mention:
>  > > Not all packets come with timestamps (e.g., locally generated
ones).
>  > > Solution: at enqueue, if the timestamp is 0, set it to the
current
>  > > time.
>  > 
>  > It would be better done in fifo/sfq. It is because HTB can do it
>  > only when dequeuing and at that time some packets were already
dropped
>  > by SFQ because if has had queues full of "old" packets.
> 
> I see, you suggest that I could do better if enqueue started with
> something like 
>  while (oldest packet expired) drop oldest packet
> Of course this is still only an approximation.  There will still be
> times when you have to drop a packet but it turns out that, before the
> next one is dequeued another packet will have expired (so if you only
> knew that you could have saved the packet you dropped before).
> 
>  > SFQ should maintain pqio queue of all packets and look at head of
>  > the list sometimes to keep its queues frre of old packets and thus
>  > to have room for new ones.
> 
> I suppose SFQ could still do something like above even if HTB were
> dropping expired packets at dequeue.  And this would save all qdiscs
> the work of dropping expired packets at dequeue, which is still needed
> even if you also check at enqueue.  Also, only dropping at dequeue is
> a good approximation to what you want in the common case where the
> queue size is too large for the low rate assigned to the class.  I
> argue it''s much better to do this in a few classful qdiscs than to
ask
> for it to be done by all the others.
I hope i got you right, here are my thoughts on this:

I don''t think dropping at dequeue is necessary. The goal is not to
provide
a maximum in-queue time, if the qdisc is able to send there is no reason 
to drop. The problem is if the qdisc is not able to send many packets 
can get queued until drops occur. This means it takes a long time until 
the sender receives indication of congestion. For TCP, congestion is 
indicated by either consequent ACKS with the same ACK number or SACKs. 
ACKs are only generated by the receiver if something was actualy 
received, so by dropping packets after some timeout the time until a 
duplicate ACK is generated becomes smaller.
If you assume the expiration time to be smaller than the time requried 
to fill the senders congestion window, it doesn''t makes sense anymore
to
drop packets during dequeue as this could possibly prevent a duplicate 
ACK from beeing generated -> relay indication of congestion.
It sounds better to me to check for expired packets during enqueue 
(timers would probably be too expensive i guess) and drop them before 
enqueueing the new packet.
With SFQ, what about not keeping a per-packet timeout but a per-flow 
congestion-indication timeout which would drop the first packet of a 
flow after max(age of any packet from this flow) >= timeout ? This would 
assure congestion indication to be delivered to the sender as soon as 
the flow is chosen to send again after the timeout occured (as long as 
qlen(flow) > 1 which is probably the case).

Bye,
Patrick

Patrick McHardy writes:

 > I don''t think dropping at dequeue is necessary. 
Here''s an example showing it is.
I have an SFQ with max queue size 128 and very low rate, say about
1 packet/sec that I use to limit the rate of SYN''s.
Now as part of a test I send a syn flood, say 200 packets in one
second.  In that first second SFQ drops 200-128 but the time limit
won''t drop any more on enqueue.  Now we''re sending one
packet/sec
and I try to open a tcp connection.
Suppose the age limit is 5 sec. and we drop on enqueue only.
If I try to open the tcp connection 3 sec after the flood, none of the
124 or so packets in the queue has expired and it''s going to take 2
min. for my syn to get through.  Whereas, if dequeue drops expired
packets then I can get through in 2 sec.

   The goal is not to provide
 > a maximum in-queue time, if the qdisc is able to send there is no reason 
 > to drop.
The reason to drop is that it''s a waste of time/bandwidth to send
expired packets, and even worse to make something unexpired wait for
them (and even worse yet if it has to wait long enough to expire
itself). 

    The problem is if the qdisc is not able to send many packets 
 > can get queued until drops occur. This means it takes a long time until 
 > the sender receives indication of congestion. For TCP, congestion is 
 > indicated by either consequent ACKS with the same ACK number or SACKs. 
In this case tcp should stop cause it doesn''t get any acks cause its
packets are not getting forwarded.  Or if the problem is the other
direction, it should stop cause it''s not getting the acks.

 > ACKs are only generated by the receiver if something was actualy 
 > received, so by dropping packets after some timeout the time until a 
 > duplicate ACK is generated becomes smaller.
I think now we''re getting into the subject of why it''s good to
drop packets that have been waiting for a long time.
If your objective is to generate a duplicate ack then I''m not sure
dropping packets is the right way.  After all, you might drop a packet
that would have generated one sooner.  For that matter, you might have
dropped one that would have generated a non-duplicate ack, which would
be even better for tcp.  Nevertheless, I do think it''s good to drop 
packets that are not forwarded in a timely fashion.  It''s just not a
simple argument.

 > If you assume the expiration time to be smaller than the time requried 
 > to fill the senders congestion window, it doesn''t makes sense
anymore to
 > drop packets during dequeue as this could possibly prevent a duplicate 
 > ACK from beeing generated -> relay indication of congestion.
 > It sounds better to me to check for expired packets during enqueue 
 > (timers would probably be too expensive i guess) and drop them before 
 > enqueueing the new packet.
I''m not sure what you have in mind for the check here.
I was expecting that no packets would actually take a long time
between being received/generated and being enqueued.  Rather, when you
enqueue one, you can look in the queue to find any others that have
been in the queue too long.  But this does not catch as many cases as
checking at dequeue.
I was not proposing to set any timers.  Just record the time the packet
arrives and when you dequeue, see how long ago that was.

 > With SFQ, what about not keeping a per-packet timeout but a per-flow 
 > congestion-indication timeout which would drop the first packet of a 
 > flow after max(age of any packet from this flow) >= timeout ? This
would
 > assure congestion indication to be delivered to the sender as soon as 
 > the flow is chosen to send again after the timeout occured (as long as 
 > qlen(flow) > 1 which is probably the case).

I don''t think I understand what you''re proposing.  If we
enqueue 50
packets from one flow all at once, and after sending 10 they all
expire (since they''re all about the same age), then you want to drop
one?  Why is it worth sending the rest?

>  > > This seems like the right solution, except that you
shouldn''t even
>  > > need to store a counter.  Just use the one in the child qdisc.
>  > > BTW, I think you are justified in assuming that this counter can
only
>  > > change in two ways: decrease when dequeue is called (but
possibly by
>  > > more than one packet) and increase by 1 when enqueue is called.
>  > > And I guess also requeue.  Which raises another problem, since
that''s
>  > > not called by the parent, right?
>  >
>  > No - you can''t use the q.qlen of inner. It is under
inner''s control
>  > and you can''t change it. And the assumption how it can
change should
>  > not be used unless you have some rules for all qdisc how to change
>  > it.
>
> The only way I can make sense of this is that we must be
> miscommunicating.  I do not propose that HTB alter an SFQ q.qlen.
> I propose that HTB read it.  I think you were suggesting that HTB
> make its own copy of it, and I was just suggesting that there''s no
> need for that copy.
I know. And yes I propose secondary copy for classfull ones and yes
there is problem reading inner''s (SFQ''s f.e.) q.qlen.
What I do jjust now - I read SFQ''s qlen. It is ok for detecting
backlog because SFQ MUST ensure that it is correct.
So that to be clear - I have NO problem reading backlog info.
However I (and CBQ too) have problem to maintain our own qlen !
>  > Somewhere in sources you can read that one of qdisc duties is
>  > to ensure that it''s q.qlen value is correct. It
doesn''t restrict
>  > how it can change and when.
>
> I think it''s pretty much necessary from the implementation
viewpoint
> to make some assumptions.  In particular, you don''t want to look
at
> all inactive leaves every time you do a dequeue, just to make sure
> that they haven''t somehow manufactured their own packets.  Once
the
> queue is empty you expect it to stay empty until you call enqueue,
> right?
right. What you know:
- each qdisc''s (own) qlen is valid at all (for us important) times
- qdisc''s qlen can increase only after successfull (!) enqueue

These are only guaranteed ones which I''ve seen described in sources.
But decrease can come from dequeue, drop (it is reality now) and
nothing prevent qdisc to drop some other packets (if it updates
qlen accordingly) - that''s what your "old dropper" wants to
do.
Consequences below ..

>  > I''d suggest for each leaf to maintain last_qlen variable
which would
>  > start with 0 (also q.qlen will be 0). Then time to time (in enqueue,
>  > dequeue, drop ....) you can "repair" your own q.qlen by
doing:
>  > q.qlen += cl->q.qlen - cl->last_qlen; cl->last_qlen =
cl->q.qlen;
>  > for each leaf cl.
>  > Hence xl->last_qlen tells you what part of total q.qlen is
"owned" by
>  > cl.
>  > Simple and robust, isn''t it ?
>
> I don''t get it.  A qdisc is already supposed to maintain its qlen.
> You don''t think that''s being done correctly now?  Why do
you want this
> other data?  You''re proposing something that will require changing
> every existing qdisc?  Or is this the class (in htb code) trying to
> keep a copy of the data in its qdisc?  If the latter, then I guess I
> don''t object (since it''s only in your code and
transparent to me), but
> I still don''t see why you need it.
Qdisc''s Q qlen is:

Q.qlen = Q.extra_qlen + sum over all children ch (ch.qlen)

Q.extra_qlen are skb''s in Q''s own queues (HTB''s
direct queue, SFQ''s hash,
PFIFO''s main queue, TBF''s queue, CBQ has no such one).
Because Q.enqueue enqueues packet into its own queue of into child
qdisc (and two rules above hold) you can simply increase Q.qlen in
case of Q.enqueue.
But say this scenario:
HTB.enqueue, skb goes to SFQ''s queue, HTB.qlen = SFQ.qlen = 1 [1]
HTB.enqueue, skb goes to SFQ''s queue, HTB.qlen = SFQ.qlen = 2 [2]
time passed
HTB.enqueue, skb goes to SFQ''s queue, SFQ decides to drop two too old
  skb''s, HTB.qlen = 3, SFQ.qlen = 1 [3]

Now HTB.qlen is bad!

Here is I would maintain copy of SFQ''s qlen [in brackets] I''d
catch that
SFQ.qlen decreased by two (under my hands) because 1-[3]=-2 and I can
correct HTB.qlen accordingly to 1.
It needs to be done only in equrur,dequeue and drop. If some inner
qdisc changes in time between, parent qdisc will ignore this change
in backlog size until next dequeue/enqueue of that class.
>  > > I like those, but also suggested that HTB would be a good place
to add
>  > > code for dropping stale packets.  If you''re interested
in doing that I
>  > > should mention:
>  > > Not all packets come with timestamps (e.g., locally generated
ones).
>  > > Solution: at enqueue, if the timestamp is 0, set it to the
current
>  > > time.
>  >
>  > It would be better done in fifo/sfq. It is because HTB can do it
>  > only when dequeuing and at that time some packets were already
dropped
>  > by SFQ because if has had queues full of "old" packets.
>
> I see, you suggest that I could do better if enqueue started with
> something like
>  while (oldest packet expired) drop oldest packet
> Of course this is still only an approximation.  There will still be
> times when you have to drop a packet but it turns out that, before the
> next one is dequeued another packet will have expired (so if you only
> knew that you could have saved the packet you dropped before).
yes somethink like :) If we would maintain these copies above then
you could drop any number of packets.
It would be helpful to drop all of these in both dequeue & enqueue
to assure that you will not dequeue old packet if too much time
passes between last enqueue and dequeue.
>  > SFQ should maintain pqio queue of all packets and look at head of
>  > the list sometimes to keep its queues frre of old packets and thus
>  > to have room for new ones.
>
> I suppose SFQ could still do something like above even if HTB were
> dropping expired packets at dequeue.  And this would save all qdiscs
> the work of dropping expired packets at dequeue, which is still needed
> even if you also check at enqueue.  Also, only dropping at dequeue is
as I write above, SFQ should do it at both sides ..
> a good approximation to what you want in the common case where the
> queue size is too large for the low rate assigned to the class.  I
> argue it''s much better to do this in a few classful qdiscs than to
ask
> for it to be done by all the others.
I agree. But as I said before - it will lead to dropping new
packets due to queue full of old packets. I''m not sure whether
it has any benefit then.
Simply hack this into HTB, measure and if it will make something
better the it is worth of implementing.
I''m not convinced about it. With fixed queue size and minimal
assured rate you always know how old packet can be in the queue ...
devik

> > I suppose SFQ could still do something like above even if HTB were
> > dropping expired packets at dequeue.  And this would save all qdiscs
> > the work of dropping expired packets at dequeue, which is still needed
> > even if you also check at enqueue.  Also, only dropping at dequeue is
> > a good approximation to what you want in the common case where the
> > queue size is too large for the low rate assigned to the class.  I
> > argue it''s much better to do this in a few classful qdiscs
than to ask
> > for it to be done by all the others.
>
> I hope i got you right, here are my thoughts on this:
>
> I don''t think dropping at dequeue is necessary. The goal is not to
provide
> a maximum in-queue time, if the qdisc is able to send there is no reason
> to drop. The problem is if the qdisc is not able to send many packets
> can get queued until drops occur. This means it takes a long time until
> the sender receives indication of congestion. For TCP, congestion is
> indicated by either consequent ACKS with the same ACK number or SACKs.
> ACKs are only generated by the receiver if something was actualy
> received, so by dropping packets after some timeout the time until a
> duplicate ACK is generated becomes smaller.
IIRC the congestion is also indicated by not recieving ACK for some
period (2*RTT is initial IIRC). So that when packet is delayed too much
TCP treats it as drop and sends dupliocate ACK requesting whole prev.
segment ...
> If you assume the expiration time to be smaller than the time requried
> to fill the senders congestion window, it doesn''t makes sense
anymore to
> drop packets during dequeue as this could possibly prevent a duplicate
> ACK from beeing generated -> relay indication of congestion.
right.
> It sounds better to me to check for expired packets during enqueue
> (timers would probably be too expensive i guess) and drop them before
> enqueueing the new packet.
exactly :)
> With SFQ, what about not keeping a per-packet timeout but a per-flow
> congestion-indication timeout which would drop the first packet of a
> flow after max(age of any packet from this flow) >= timeout ? This would
> assure congestion indication to be delivered to the sender as soon as
> the flow is chosen to send again after the timeout occured (as long as
> qlen(flow) > 1 which is probably the case).
Maybe I don''t remember some RFC correctly but ACKs with info
about congestion are sent in reverse direction .. (?)

But I still think that if ever do this machinery that it should
be done at bot enqueue and dequeue time. Don Cohen is right in
thing that in dequeue it''d be simpler to implement (at least
for testing).

devik

> I have an SFQ with max queue size 128 and very low rate, say about
> 1 packet/sec that I use to limit the rate of SYN''s.
> Now as part of a test I send a syn flood, say 200 packets in one
> second.  In that first second SFQ drops 200-128 but the time limit
> won''t drop any more on enqueue.  Now we''re sending one
packet/sec
> and I try to open a tcp connection.
> Suppose the age limit is 5 sec. and we drop on enqueue only.
> If I try to open the tcp connection 3 sec after the flood, none of the
> 124 or so packets in the queue has expired and it''s going to take
2
> min. for my syn to get through.  Whereas, if dequeue drops expired
> packets then I can get through in 2 sec.
Nice example :)
And it also shown that you want to drop at both enqueue & dequeue.
At enqueue because there is much higher rate of flood enqueues which
will keep your sfq full until next dequeue (which drains all oldies).
OTOH only after some time the packet will be old. So that checking
too often will not allow to drop anything ...
Probably testing is only way to go ..
devik

Martin Devera writes:
 > So that to be clear - I have NO problem reading backlog info.
 > However I (and CBQ too) have problem to maintain our own qlen !
Oh, of course.  Now everything makes sense.
When I asked whether all you care about inner qlen is whether it''s 0
you mislead me by confirming my incorrect guess.  Or perhaps it used
to be right but now is wrong.  You now need it (not just whether it''s
0) in order to figure out and maintain your own qlen.

 > right. What you know:
 > - each qdisc''s (own) qlen is valid at all (for us important)
times
 > - qdisc''s qlen can increase only after successfull (!) enqueue
But I think there''s another case - requeue.  Maybe you consider that
the same as enqueue.
(I''ve never seen evidence that it was executed, but it''s
called in
sch_generic.c)

 > > I see, you suggest that I could do better if enqueue started with
 > > something like
 > >  while (oldest packet expired) drop oldest packet
 > > Of course this is still only an approximation.  There will still be
 > > times when you have to drop a packet but it turns out that, before
the
 > > next one is dequeued another packet will have expired (so if you only
 > > knew that you could have saved the packet you dropped before).
 > 
 > yes somethink like :) If we would maintain these copies above then
 > you could drop any number of packets.
 > It would be helpful to drop all of these in both dequeue & enqueue
 > to assure that you will not dequeue old packet if too much time
 > passes between last enqueue and dequeue.

Unfortunately, for SFQ it''s not so easy to find all expired packets in
the queue.  We''d have to add a fifo data structure to do that in the
desired time (proportional to the number of expired packets).  
This is only important when the queue is full, of course.
I still think it''s reasonable to check only at dequeue.  Basically if
you know max time between dequeues is t, then a queue filled by a
flood can only remain full for time t + expire_time after the flood
ends.  After that there will be a dequeue that throws out all the
flood packets.  Then your next packet will be accepted and delayed at
most expire_time.

This is only slightly worse than the guarantee you get by expiring at
both enqueue and dequeue.  I see that the same could be said for only
expiring at enqueue, but that''s much harder.  In particular the
dequeue only solution can be done by the classful qdiscs on their own
while the enqueue only (or both) cannot.

Hi !
Don Cohen wrote:
> Patrick McHardy writes:
> 
>  > I don''t think dropping at dequeue is necessary. 
> Here''s an example showing it is.
> I have an SFQ with max queue size 128 and very low rate, say about
> 1 packet/sec that I use to limit the rate of SYN''s.
> Now as part of a test I send a syn flood, say 200 packets in one
> second.  In that first second SFQ drops 200-128 but the time limit
> won''t drop any more on enqueue.  Now we''re sending one
packet/sec
> and I try to open a tcp connection.
> Suppose the age limit is 5 sec. and we drop on enqueue only.
> If I try to open the tcp connection 3 sec after the flood, none of the
> 124 or so packets in the queue has expired and it''s going to take
2
> min. for my syn to get through.  Whereas, if dequeue drops expired
> packets then I can get through in 2 sec.
I don''t think this is a good example.
Why use SFQ for only SYNs ? For each connection (flow) only one SYN is 
going to get enqueued. SFQ distributes available bandwidth equal between 
flows if it the queue becomes full. Now, if each flow just consists of 
one packet it''s basically the same like fifo with higher overhead.
What if the Synflood lasts longer / your connection request happens 
during the synflood ? It will expire like the others.
Syncookies provide a much better protection against synfloods, you
won''t
have to wait at all.
>    The goal is not to provide
>  > a maximum in-queue time, if the qdisc is able to send there is no
reason
>  > to drop.
> The reason to drop is that it''s a waste of time/bandwidth to send
> expired packets, and even worse to make something unexpired wait for
> them (and even worse yet if it has to wait long enough to expire
> itself). 
> 
>     The problem is if the qdisc is not able to send many packets 
>  > can get queued until drops occur. This means it takes a long time
until
>  > the sender receives indication of congestion. For TCP, congestion is 
>  > indicated by either consequent ACKS with the same ACK number or
SACKs.
> In this case tcp should stop cause it doesn''t get any acks cause
its
> packets are not getting forwarded.  Or if the problem is the other
> direction, it should stop cause it''s not getting the acks.
> 
>  > ACKs are only generated by the receiver if something was actualy 
>  > received, so by dropping packets after some timeout the time until a 
>  > duplicate ACK is generated becomes smaller.
> I think now we''re getting into the subject of why it''s
good to
> drop packets that have been waiting for a long time.
> If your objective is to generate a duplicate ack then I''m not sure
> dropping packets is the right way.  After all, you might drop a packet
> that would have generated one sooner.  For that matter, you might have
> dropped one that would have generated a non-duplicate ack, which would
> be even better for tcp.  Nevertheless, I do think it''s good to
drop
> packets that are not forwarded in a timely fashion.  It''s just not
a
> simple argument.
I think maybe we misunderstood.
What i want to achieve is that flows respond more quickly to changes in 
available bandwidth. I assume that i am the bottleneck, otherwise it 
wouldn''t make much sense at all. You write "After all, you might
drop a
packet that would have generated one sooner.  For that matter, you might 
have dropped one that would have generated a non-duplicate ack, which 
would be even better for tcp.". If we leave packets dropped on the path 
to us for reasons besides congestion out of sight it''s unlikely that we
drop a packet that would have generated a duplicate ack earlier. After 
all, we are the bottleneck so we control packet drops. Also, i don''t 
want to generate a non-duplicate ACK, i want to tell the remote LESS 
bandwidth is available.

>  > If you assume the expiration time to be smaller than the time
requried
>  > to fill the senders congestion window, it doesn''t makes
sense anymore to
>  > drop packets during dequeue as this could possibly prevent a
duplicate
>  > ACK from beeing generated -> relay indication of congestion.
>  > It sounds better to me to check for expired packets during enqueue 
>  > (timers would probably be too expensive i guess) and drop them before
>  > enqueueing the new packet.
> I''m not sure what you have in mind for the check here.
> I was expecting that no packets would actually take a long time
> between being received/generated and being enqueued.  Rather, when you
> enqueue one, you can look in the queue to find any others that have
> been in the queue too long.  But this does not catch as many cases as
> checking at dequeue.
> I was not proposing to set any timers.  Just record the time the packet
> arrives and when you dequeue, see how long ago that was.
> 
>  > With SFQ, what about not keeping a per-packet timeout but a per-flow 
>  > congestion-indication timeout which would drop the first packet of a 
>  > flow after max(age of any packet from this flow) >= timeout ? This
would
>  > assure congestion indication to be delivered to the sender as soon as
>  > the flow is chosen to send again after the timeout occured (as long
as
>  > qlen(flow) > 1 which is probably the case).
> 
> I don''t think I understand what you''re proposing.  If we
enqueue 50
> packets from one flow all at once, and after sending 10 they all
> expire (since they''re all about the same age), then you want to
drop
> one?  Why is it worth sending the rest?
I don''t want to drop unneccasary much. If i drop the first one, the 
sender will receive notification of congestion as soon as possible and 
slow down. But i haven''t put very much thought in this so it will 
probably not work like this.

Bye,
Patrick

Patrick McHardy writes:
 > I don''t think this is a good example.
 > Why use SFQ for only SYNs ?
Ok, use pfifo instead.

 > What if the Synflood lasts longer / your connection request happens 
 > during the synflood ? It will expire like the others.
I wasn''t trying to solve the flooding problem in this example.
(As it turns out, I am trying to solve that problem, and this is
related to that subject, but I won''t go into details here.  Anyone
who wants to know more should see http://www.cs3-inc.com/ddos.html)

 > Syncookies provide a much better protection against synfloods, you
won''t
 > have to wait at all.
Ok, change syn to ping.

 > I think maybe we misunderstood.
 > What i want to achieve is that flows respond more quickly to changes in 
 > available bandwidth.
In the case of tcp this adjustment happens automatically because the
acks slow down (or speed up).  It''s much better for tcp to adjust the
rate without having to drop.

 > > I don''t think I understand what you''re proposing. 
If we enqueue 50
 > > packets from one flow all at once, and after sending 10 they all
 > > expire (since they''re all about the same age), then you want
to drop
 > > one?  Why is it worth sending the rest?
 > 
 > I don''t want to drop unneccasary much. If i drop the first one,
the
 > sender will receive notification of congestion as soon as possible and 
 > slow down. But i haven''t put very much thought in this so it will
 > probably not work like this.
Dropping has a pretty drastic effect on tcp.  If the communicating
tcp''s support various features, dropping one packet might not cause
any significant slowdown, whereas in other implementations dropping
one could cause a major slowdown with lots of stuff having to be
retransmitted.  It''s not the case that you can expect a small number
of drops to cause a small amount of slowdown.

>  > right. What you know:
>  > - each qdisc''s (own) qlen is valid at all (for us important)
times
>  > - qdisc''s qlen can increase only after successfull (!)
enqueue
> But I think there''s another case - requeue.  Maybe you consider
that
> the same as enqueue.
> (I''ve never seen evidence that it was executed, but it''s
called in
> sch_generic.c)
It should be handled in the same way as requeue only should not increase
stats.
> I still think it''s reasonable to check only at dequeue.  Basically
if
> you know max time between dequeues is t, then a queue filled by a
> flood can only remain full for time t + expire_time after the flood
> ends.  After that there will be a dequeue that throws out all the
> flood packets.  Then your next packet will be accepted and delayed at
> most expire_time.
It might be. Why don''t you try it ? I feel still the same about it: I
think that experiment is the only way to test the idea.

devik

> It should be handled in the same way as requeue only should not increase
 > stats.
I guess you mean requeue should be the same as enqueue.

 > > I still think it''s reasonable to check only at dequeue. 
Basically if
 > > you know max time between dequeues is t, then a queue filled by a
 > > flood can only remain full for time t + expire_time after the flood
 > > ends.  After that there will be a dequeue that throws out all the
 > > flood packets.  Then your next packet will be accepted and delayed at
 > > most expire_time.
 > 
 > It might be. Why don''t you try it ? I feel still the same about
it: I
 > think that experiment is the only way to test the idea.

What experiments would you like to see?

On Thu, 9 May 2002, Don Cohen wrote:
>  > It should be handled in the same way as requeue only should not
increase
>  > stats.
> I guess you mean requeue should be the same as enqueue.
err of course, yes
>  > > I still think it''s reasonable to check only at dequeue.
Basically if
>  > > you know max time between dequeues is t, then a queue filled by
a
>  > > flood can only remain full for time t + expire_time after the
flood
>  > > ends.  After that there will be a dequeue that throws out all
the
>  > > flood packets.  Then your next packet will be accepted and
delayed at
>  > > most expire_time.
>  >
>  > It might be. Why don''t you try it ? I feel still the same
about it: I
>  > think that experiment is the only way to test the idea.
>
> What experiments would you like to see?
Implement your idea and measure difference in delay, jitter, thoughtput of
TCP and reaction to flooding.
In other words show that your idea can do better that current approach.
When I was speking about idea like HTB nobody listened. I''ve to
implement
it ..
devik