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

Stephen Hemminger
2011-01-10T17:31:27Z

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.

--