Re: [PATCH] CHOKe flow scheduler (0.9)

[Stephen Hemminger <shemminger@vyatta.com>]

On Sat, 15 Jan 2011 08:45:42 +0100
Eric Dumazet <eric.dumazet@gmail.com> wrote:

> Le vendredi 14 janvier 2011 à 15:45 -0800, Stephen Hemminger a écrit :
> > CHOKe ("CHOose and Kill" or "CHOose and Keep") is an alternative
> > packet scheduler based on the Random Exponential Drop (RED) algorithm.
> > 
> > The core idea is:
> >   For every packet arrival:
> >   	Calculate Qave
> > 	if (Qave < minth) 
> > 	     Queue the new packet
> > 	else 
> > 	     Select randomly a packet from the queue 
> > 	     if (both packets from same flow)
> > 	     then Drop both the packets
> > 	     else if (Qave > maxth)
> > 	          Drop packet
> > 	     else
> > 	       	  Admit packet with proability p (same as RED)
> > 
> > See also:
> >   Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
> >    queue management scheme for approximating fair bandwidth allocation", 
> >   Proceeding of INFOCOM'2000, March 2000.
> > 
> > Help from:
> >      Eric Dumazet <eric.dumazet@gmail.com>
> >      Patrick McHardy <kaber@trash.net>
> > 
> > Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
> > 
> > ---
> > This version is based on net-next, and assumes Eric's patch for
> > corrected bstats is already applied.
> > 
> > 0.9 incorporate patches from Patrick/Eric
> >     rework the peek_random and drop code to simplify and fix bug where
> >     random_N needs to called with full length (including holes).
> 
> Nice catch, I now have more "matched" counts after my test :
> 
> qdisc choke 11: parent 1:11 limit 130000b min 10833b max 32500b ewma 13 Plog 21 Scell_log 30
>  Sent 93944198 bytes 170889 pkt (dropped 829140, overlimits 436686 requeues 0) 
>  rate 48bit 0pps backlog 0b 0p requeues 0 
>   marked 0 early 436686 pdrop 0 other 0 matched 196227
> 
> You missed the qdisc_bstats_update() move from enqueue() to dequeue()
> 
> And some minor CodingStyle / checkpatch.pl changes, here is my
> latest diff on top of 0.9
> 
> I believe you can release v1 :)
> 
> Thanks !

I rolled in your changes. But there is one more change I want to make.
The existing flow match based on hash is vulnerable to side-channel DoS attack.
It is possible for a hostile flow to send packets that match the same
hash value which would effectively kill a targeted flow.

The solution is to match based on full source and destination, not hash value.
Still coding that up.



--