Re: [RFC] sched: CHOKe packet scheduler (v0.2)

[Eric Dumazet <eric.dumazet@gmail.com>]

Le lundi 10 janvier 2011 à 09:31 -0800, Stephen Hemminger a écrit :
> On Mon, 10 Jan 2011 14:46:50 +0100
> Eric Dumazet <eric.dumazet@gmail.com> wrote:
> 
> > Le jeudi 06 janvier 2011 à 20:55 -0800, Stephen Hemminger a écrit :
> > 
> > > 
> > > The problem is that large tables of pointers in kernel require either
> > > contiguous allocation or some indirect table algorithm.
> > > 
> > 
> > Here is a v3 version with an array based queue for O(1) peek_random
> > complexity.
> > 
> > Could you send the iproute2 patch so that I can test it ?
> > 
> > Thanks !
> > 
> > 
> > diff --git a/net/sched/sch_choke.c b/net/sched/sch_choke.c
> > index e69de29..ea9db00 100644
> > --- a/net/sched/sch_choke.c
> > +++ b/net/sched/sch_choke.c
> > @@ -0,0 +1,388 @@
> > +/*
> > + * net/sched/sch_choke.c	CHOKE scheduler
> > + *
> > + * Copyright (c) 2011 Stephen Hemminger <shemminger@vyatta.com>
> > + * Copyright (c) 2011 Eric Dumazet <eric.dumazet@gmail.com>
> > + *
> > + * This program is free software; you can redistribute it and/or
> > + * modify it under the terms of the GNU General Public License
> > + * version 2 as published by the Free Software Foundation.
> > + *
> > + */
> > +
> > +#include <linux/module.h>
> > +#include <linux/types.h>
> > +#include <linux/kernel.h>
> > +#include <linux/skbuff.h>
> > +#include <linux/reciprocal_div.h>
> > +#include <net/pkt_sched.h>
> > +#include <net/inet_ecn.h>
> > +#include <net/red.h>
> > +
> > +/*	CHOKe stateless AQM for fair bandwidth allocation
> > +        =================================================
> > +
> > +   CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for
> > +   unresponsive flows) is a variant of RED that penalizes misbehaving flows but
> > +   maintains no flow state. The difference from RED is an additional step
> > +   during the enqueuing process. If average queue size is over the
> > +   low threshold (qmin), a packet is chosen at random from the queue.
> > +   If both the new and chosen packet are from the same flow, both
> > +   are dropped. Unlike RED, CHOKe is not a "classful" qdisc because it
> > +   needs to access packets in queue randomly.
> > +
> > +   Source:
> > +   R. Pan, B. Prabhakar, and K. Psounis, "CHOKe, A Stateless
> > +   Active Queue Management Scheme for Approximating Fair Bandwidth Allocation",
> > +   IEEE INFOCOM, 2000.
> > +
> > +   A. Tang, J. Wang, S. Low, "Understanding CHOKe: Throughput and Spatial
> > +   Characteristics", IEEE/ACM Transactions on Networking, 2004
> > +
> > + */
> > +
> > +struct choke_sched_data {
> > +	u32		 limit;
> > +	unsigned char	 flags;
> > +
> > +	struct red_parms parms;
> > +	struct red_stats stats;
> > +
> > +	unsigned int	 head;
> > +	unsigned int	 tail;
> > +	unsigned int	 holes;
> > +	unsigned int	 tab_mask; /* size - 1 */
> > +	struct sk_buff **tab;
> > +};
> > +
> > +static inline unsigned int choke_len(const struct choke_sched_data *q)
> > +{
> > +	return (q->tail - q->head) & q->tab_mask;
> > +}
> > +
> > +/* deliver a random number between 0 and N - 1 */
> > +static inline u32 random_N(unsigned int N)
> > +{
> > +	return reciprocal_divide(random32(), N);
> > +}
> > +
> > +/* Select a packet at random from the queue in O(1) */
> > +static struct sk_buff *choke_peek_random(struct choke_sched_data *q, unsigned int *pidx)
> > +{
> > +	*pidx = (q->head + random_N(choke_len(q))) & q->tab_mask;
> > +	return q->tab[*pidx];
> > +}
> 
> I don't think this works right. The choke_peek_random could find a hole.
> Either the data structure has to change, or the peek_random has to retry,
> or if quick peek fails then compress the slot with memmove and retry.
> 
> 

Yes, this "compress only if peek_random() finds a hole seems good, I'll
try this.

As number of holes is known, we could have :

if (holes_proportion_is_less_than_20_percent())
	try another random number X times
else
	compress table to remove holes.