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

[Stephen Hemminger <shemminger@vyatta.com>]

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.


--