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

Eric Dumazet
2011-01-10T17:49:28Z

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.