netdev - Re: [PATCH] CHOKe flow scheduler (0.9)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20110117092532.7d5f5a5b@nehalam>
Date:	Mon, 17 Jan 2011 09:25:32 -0800
From:	Stephen Hemminger <shemminger@...tta.com>
To:	Eric Dumazet <eric.dumazet@...il.com>
Cc:	Patrick McHardy <kaber@...sh.net>,
	David Miller <davem@...emloft.net>, netdev@...r.kernel.org
Subject: Re: [PATCH] CHOKe flow scheduler (0.9)

On Sat, 15 Jan 2011 08:45:42 +0100
Eric Dumazet <eric.dumazet@...il.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@...il.com>
> >      Patrick McHardy <kaber@...sh.net>
> > 
> > Signed-off-by: Stephen Hemminger <shemminger@...tta.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.



-- 
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html