Re: [RFC] sched: CHOKe packet scheduler

Eric Dumazet
2011-01-05T06:02:30Z

Le mardi 04 janvier 2011 à 16:29 -0800, Stephen Hemminger a écrit :
> This implements the CHOKe packet scheduler based on the existing
> Linux RED scheduler based on the algorithm described in the paper.
> Configuration is the same as RED; only the name changes.
>
> 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 for their flow id
> Compare arriving packet with a randomly selected packet.
> If they have the same flow id {
> Drop both the packets
> }
> Else {
> if (Qave ≥ maxth) {

you mean if (Qave is less than maxth) ?

> Calculate the dropping probability pa
> Drop the packet with probability pa
> }
> Else {
> Drop the new packet
> }
> }
> }
>
> This an early access version.
>

No ECN support at all ? even RED supports it :)

> Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
>
> ---
> net/sched/Kconfig | 11 +
> net/sched/Makefile | 1
> net/sched/sch_choke.c | 364 ++++++++++++++++++++++++++++++++++++++++++++++++++
> 3 files changed, 376 insertions(+)
>
> --- a/net/sched/Kconfig 2011-01-04 16:25:18.000000000 -0800
> +++ b/net/sched/Kconfig 2011-01-04 16:26:02.335973715 -0800
> @@ -205,6 +205,17 @@ config NET_SCH_DRR
>
> If unsure, say N.
>
> +config NET_SCH_CHOKE
> + tristate "CHOose and Keep responsive flow scheduler (CHOKE)"
> + help
> + Say Y here if you want to use the CHOKe packet scheduler (CHOose
> + and Keep for responsive flows, CHOose and Kill for unresponsive
> + flows). This is a variation of RED which trys to penalize flows
> + that monopolize the queue.
> +
> + To compile this code as a module, choose M here: the
> + module will be called sch_choke.
> +
> config NET_SCH_INGRESS
> tristate "Ingress Qdisc"
> depends on NET_CLS_ACT
> --- a/net/sched/Makefile 2011-01-04 16:25:18.000000000 -0800
> +++ b/net/sched/Makefile 2011-01-04 16:26:16.048938937 -0800
> @@ -32,6 +32,7 @@ obj-$(CONFIG_NET_SCH_MULTIQ) += sch_mult
> obj-$(CONFIG_NET_SCH_ATM) += sch_atm.o
> obj-$(CONFIG_NET_SCH_NETEM) += sch_netem.o
> obj-$(CONFIG_NET_SCH_DRR) += sch_drr.o
> +obj-$(CONFIG_NET_SCH_CHOKE) += sch_choke.o
> obj-$(CONFIG_NET_CLS_U32) += cls_u32.o
> obj-$(CONFIG_NET_CLS_ROUTE4) += cls_route.o
> obj-$(CONFIG_NET_CLS_FW) += cls_fw.o
> --- /dev/null 1970-01-01 00:00:00.000000000 +0000
> +++ b/net/sched/sch_choke.c 2011-01-04 16:25:33.913971468 -0800
> @@ -0,0 +1,364 @@
> +/*
> + * net/sched/sch_choke.c CHOKE scheduler
> + *
> + * Copyright (c) 2011 Stephen Hemminger <shemminger@vyatta.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/ipv6.h>
> +#include <linux/jhash.h>
> +#include <net/pkt_sched.h>
> +#include <net/ip.h>
> +#include <net/red.h>
> +#include <net/ipv6.h>
> +
> +/* CHOKe stateless AQM for fair bandwidth allocation
> + =================================================
> +
> + 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
> +
> + ADVANTAGE:
> + - Penalizes unfair flows
> + - Random drop provide gradual feedback
> +
> + DRAWBACKS:
> + - Small queue for single flow
> + - Can be gamed by opening lots of connections
> + - Hard to get correct paremeters (same problem as RED)

Big packets are really unfair. Must disable TSO/GRO :)

> +
> + */
> +
> +struct choke_sched_data
> +{
> + u32 limit;
> + unsigned char flags;
> +
> + struct red_parms parms;
> + struct red_stats stats;
> +};
> +
> +/* Select a packet at random from the list.
> + * Same caveats as skb_peek.
> + */
> +static struct sk_buff *skb_peek_random(struct sk_buff_head *list)
> +{
> + struct sk_buff *skb = list->next;
> + unsigned int idx = net_random() % list->qlen;
> +
> + while (skb && idx-- > 0)
> + skb = skb->next;

Ouch... A linked list (using in skb anchors) is not appropriate data
structure. Thats too many cache lines misses.

Maybe using a q->limit array of skb pointers ?

> +
> + return skb;
> +}
> +
> +/* Given IP header and size find src/dst port pair */
> +static inline u32 get_ports(const void *hdr, size_t hdr_size, int offset)
> +{
> + return *(u32 *)(hdr + hdr_size + offset);
> +}
> +
> +
> +static bool same_flow(struct sk_buff *nskb, const struct sk_buff *oskb)
> +{
> + if (nskb->protocol != oskb->protocol)
> + return false;
> +
> + switch (nskb->protocol) {
> + case htons(ETH_P_IP):
> + {
> + const struct iphdr *iph1, *iph2;
> + int poff;
> +
> + if (!pskb_network_may_pull(nskb, sizeof(*iph1)))
> + return false;

Why isnt it necessary to also may_pull test oskb ?

> +
> + iph1 = ip_hdr(nskb);
> + iph2 = ip_hdr(oskb);
> +
> + if (iph1->protocol != iph2->protocol ||
> + iph1->daddr != iph2->daddr ||
> + iph1->saddr != iph2->saddr)
> + return false;
> +
> + /* Be hostile to new fragmented packets */
> + if (iph1->frag_off & htons(IP_MF|IP_OFFSET))
> + return true;
> +
> + if (iph2->frag_off & htons(IP_MF|IP_OFFSET))
> + return false;
> +
> + poff = proto_ports_offset(iph1->protocol);
> + if (poff >= 0 &&
> + pskb_network_may_pull(nskb, iph1->ihl * 4 + 4 + poff)) {
> + iph1 = ip_hdr(nskb);
> +
> + return get_ports(iph1, iph1->ihl * 4, poff)
> + == get_ports(iph2, iph2->ihl * 4, poff);
> + }
> +
> + return false;
> + }
> +
> + case htons(ETH_P_IPV6):
> + {
> + const struct ipv6hdr *iph1, *iph2;
> + int poff;
> +
> + if (!pskb_network_may_pull(nskb, sizeof(*iph1)))
> + return false;

same here.

> +
> + iph1 = ipv6_hdr(nskb);
> + iph2 = ipv6_hdr(oskb);
> +
> + if (iph1->nexthdr != iph2->nexthdr ||
> + ipv6_addr_cmp(&iph1->daddr, &iph2->daddr) != 0 ||
> + ipv6_addr_cmp(&iph1->saddr, &iph2->saddr) != 0)
> + return false;
> +
> + poff = proto_ports_offset(iph1->nexthdr);
> + if (poff >= 0 &&
> + pskb_network_may_pull(nskb, sizeof(*iph1) + 4 + poff)) {
> + iph1 = ipv6_hdr(nskb);
> +
> + return get_ports(iph1, sizeof(*iph1), poff)
> + == get_ports(iph2, sizeof(*iph2), poff);
> + }
> + return false;
> + }
> + default:
> + return false;
> + }
> +
> +}
> +
> +/*
> + * Decide what to do with new packet based on queue size.
> + * returns 1 if packet should be admitted
> + * 0 if packet should be dropped
> + */
> +static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch)
> +{
> + struct choke_sched_data *q = qdisc_priv(sch);
> + struct red_parms *p = &q->parms;
> +
> + p->qavg = red_calc_qavg(p, skb_queue_len(&sch->q));
> + if (red_is_idling(p))
> + red_end_of_idle_period(p);
> +
> + if (p->qavg <= p->qth_min)
> + p->qcount = -1;
> + else {
> + struct sk_buff *oskb;
> +
> + /* Draw a packet at random from queue */
> + oskb = skb_peek_random(&sch->q);
> +
> + /* Both packets from same flow? */
> + if (same_flow(skb, oskb)) {
> + /* Drop both packets */
> + __skb_unlink(oskb, &sch->q);
> + qdisc_drop(oskb, sch);
> + goto congestion_drop;
> + }
> +
> + if (p->qavg > p->qth_max) {

ok, maybe CHOKe paper used : if (p->qavg >= p->qth_max) ?

> + p->qcount = -1;
> +
> + sch->qstats.overlimits++;
> + q->stats.forced_drop++;
> + goto congestion_drop;
> + }
> +
> + if (++p->qcount) {
> + if (red_mark_probability(p, p->qavg)) {
> + p->qcount = 0;
> + p->qR = red_random(p);
> +
> + sch->qstats.overlimits++;
> + q->stats.prob_drop++;
> + goto congestion_drop;
> + }
> + } else
> + p->qR = red_random(p);
> + }
> +
> + /* Admit new packet */
> + if (likely(skb_queue_len(&sch->q) < q->limit))
> + return qdisc_enqueue_tail(skb, sch);
> +
> + q->stats.pdrop++;
> + sch->qstats.drops++;
> + kfree_skb(skb);
> + return NET_XMIT_DROP;
> +
> + congestion_drop:
> + qdisc_drop(skb, sch);
> + return NET_XMIT_CN;
> +}
> +