From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm0-x244.google.com (mail-wm0-x244.google.com [IPv6:2a00:1450:400c:c09::244]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id B01CF3B2A4 for ; Mon, 30 Jul 2018 05:14:08 -0400 (EDT) Received: by mail-wm0-x244.google.com with SMTP id c14-v6so12290217wmb.4 for ; Mon, 30 Jul 2018 02:14:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=heistp.net; s=google; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=pQIK415m5xQA9kPABqGppoHGQRycgCNmQiwxdh0ej1Y=; b=R5qN/uvJAvWGGdKw1JUZrD717sghdZvYOdNVJquKJXoQ6JnMk5NBw56k1EWD6LfEGr lyAIj7cZBV2Mnpgt8CaJJZZBFVduEr6TmQXm10moMt+0Z+Kl2BQSwlw1T8L4qSmOzDVG 7vs83Oep5vZsJlQwWlHTMCtqUz1LY3XqKryR7Z8M/YaSqw1cco2++vNgFpfY9PadUMhl U8orP6KWP6+4MdWA0WAD3RBAzz3woOxdigtHG8hzpGy+slbTrGknBtwtrpHYjCxElcQS jARrf9/soc3Z6HmzBqH3+0ZClG7EA7INo+OSz4sYhjEsGfsy6KRAIjNgOzH948t14jUm 41xg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=pQIK415m5xQA9kPABqGppoHGQRycgCNmQiwxdh0ej1Y=; b=CuB8Hn/HSB5XhYUOuN3SQ8sbmsT88ItYZXg9CIO9Kru5VJBj1W5/vbsZHAksuK8N8+ fsHeCKShHK03CHym4lPr6SFgxpANo2drpg+RuMxuKkHbn7tExIrEKWUWghJdc/SNGSbG olMmhucSyhfg+XZ4s9XB8ehKfKkN9WiGnBrtFh9HLzhwCbeox4vLFNORzHZeL9T8IJC2 7x1lD4Dms6zUtmit6CtLSITcDfkJmSYAW2kkGic2HarGCv1vnqozLe25869UAjRWxCDV DhKqgdLsfOAiB8jH8WIZaOhjVGbHab0q8La7uGJs726+4FXkCU+Sw3l3NFY82IceTD5s OYZA== X-Gm-Message-State: AOUpUlGat+gagWUgUqXXqbhZ+rbr43W2klKHI+MFnHArOd0HZVmB+yxY /iinOwNfvwbU4skSYqaMHZR/HQ== X-Google-Smtp-Source: AAOMgpe0akwOZCKAmWE7sGY7lpkS7kVTYI0Tv40Bud/q9CniWYQPlk8/NNMDALtG4mBfZKJme9GCeA== X-Received: by 2002:a1c:f46:: with SMTP id 67-v6mr13809413wmp.122.1532942047787; Mon, 30 Jul 2018 02:14:07 -0700 (PDT) Received: from tron.luk.heistp.net (h-1169.lbcfree.net. [185.193.85.130]) by smtp.gmail.com with ESMTPSA id q3-v6sm11825544wmf.21.2018.07.30.02.14.06 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 30 Jul 2018 02:14:06 -0700 (PDT) From: Pete Heist Message-Id: <305C8083-A170-42E8-BC96-120D3B0065EA@heistp.net> Content-Type: multipart/alternative; boundary="Apple-Mail=_C3D8F03F-4770-4E60-B9B6-5C16D828F284" Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.1\)) Date: Mon, 30 Jul 2018 11:14:05 +0200 In-Reply-To: <87r2jlzwew.fsf@toke.dk> Cc: Dave Taht , Cake List To: =?utf-8?Q?Toke_H=C3=B8iland-J=C3=B8rgensen?= References: <1357421162.31089.1531812291583@webmail.strato.de> <1c323544b3076c0ab31b887d6113f25f572e41ae.camel@coverfire.com> <87woth28rw.fsf@toke.dk> <87tvol1z6h.fsf@toke.dk> <87wotfzql8.fsf@toke.dk> <87r2jlzwew.fsf@toke.dk> X-Mailer: Apple Mail (2.3445.9.1) Subject: Re: [Cake] =?utf-8?q?Using_cake_to_shape_1000=E2=80=99s_of_users=2E?= X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 30 Jul 2018 09:14:08 -0000 --Apple-Mail=_C3D8F03F-4770-4E60-B9B6-5C16D828F284 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 > On Jul 29, 2018, at 9:14 PM, Toke H=C3=B8iland-J=C3=B8rgensen = wrote: >>=20 >> Caveats that I know of: >> - Limited to 1024 members >> - No fairness between flows >=20 > You could assign more than one queue per customer and hash traffic > between them in BPF=E2=80=A6 True. There will always be that limit of 1024 (in my case I=E2=80=99ll = need 800). >> - Non-member traffic would have to be dealt with somehow, maybe put = in >> its own queue or split among multiple queues, otherwise there can be >> hash collisions with member queues >=20 > Yeah, an "overflow queue" is definitely needed in this kind of > deployment :) Yep, I=E2=80=99d like to hash the non-member flows across the remaining = queues. > I actually wrote an eBPF classifier a few months back, that can lookup > subnets in a BPF map and map them into different classes: > https://github.com/tohojo/tc-classifier = Nice! That along with Dave=E2=80=99s ack classifier will help me write = one for MAC addresses. I got as far as =E2=80=9Cmy first no-panic = bpf=E2=80=9D, but for starters I wasn=E2=80=99t sure of the right way to = set classid, so I see TC_H_MAKE. The documentation one finds on BPF = varies a lot in correctness, so I messed around a while. I think regardless of whether ISP cake is a new qdisc or changes to the = current one, it would be good to provide a common tool like this for = mapping both MACs and IP subnets. Maybe I can just expand tc-classifier = a bit for my needs and try to think of others also? Here=E2=80=99s how = it could work: Userspace tool: - accepts as input from stdin or file, space or comma separated mappings = of one of (MAC address, IPv4 subnet or IPv6 subnet) to both classid = (flow) and priority (tin), so three fields total - accepts as an optional argument tin to place unclassified traffic in = (defaults to 0) - returns an error if no queues available for unclassified traffic - puts mappings into up to three global BPF maps (for MAC, IPv4 and = IPv6) - puts unclassified traffic tin, if non-zero, into a global - should lock globals here so updates can be made without removing / = re-adding qdisc BPF filter: - tries to classify first using MAC address map, then IPv4 or IPv6 maps = for IP traffic - spreads any unclassified traffic in unclassified traffic tin across = remaining classids from max(classid)+1 to 1023 Lastly, although it's natural to use classid for flow (subscriber) and = priority for tin, we have a hard maximum of 2^16 subscribers in a given = tin (minor classid is 16 bits). It doesn=E2=80=99t matter now because we = only have 1024 flows per tin, but for ISP cake, is a limit of ~2^16 = subscribers in one tin enough? Otherwise we=E2=80=99d have to change the = way we specify this. --Apple-Mail=_C3D8F03F-4770-4E60-B9B6-5C16D828F284 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8
On = Jul 29, 2018, at 9:14 PM, Toke H=C3=B8iland-J=C3=B8rgensen <toke@toke.dk> = wrote:

Caveats that I know = of:
- Limited to 1024 members
- No fairness = between flows

You could assign more than one queue per customer and hash = traffic
between them = in BPF=E2=80=A6

True. There will always be that limit of 1024 (in = my case I=E2=80=99ll need 800).

- Non-member traffic would have to be = dealt with somehow, maybe put in
its own queue or split = among multiple queues, otherwise there can be
hash = collisions with member queues

Yeah, an "overflow queue" is = definitely needed in this kind of
deployment :)

Yep, I=E2=80=99d like to hash the non-member flows = across the remaining queues.

I actually wrote an eBPF classifier a few months back, that = can lookup
subnets in a = BPF map and map them into different classes:
https://github.com/tohojo/tc-classifier

Nice! = That along with Dave=E2=80=99s ack classifier will help me write one for = MAC addresses. I got as far as =E2=80=9Cmy first no-panic bpf=E2=80=9D, = but for starters I wasn=E2=80=99t sure of the right way to set classid, = so I see TC_H_MAKE. The documentation one finds on BPF varies a lot in = correctness, so I messed around a while.

I think regardless of whether ISP cake = is a new qdisc or changes to the current one, it would be good to = provide a common tool like this for mapping both MACs and IP subnets. = Maybe I can just expand tc-classifier a bit for my needs and try to = think of others also? Here=E2=80=99s how it could work:

Userspace = tool:
- accepts as input from stdin or file, space = or comma separated mappings of one of (MAC address, IPv4 subnet or IPv6 = subnet) to both classid (flow) and priority (tin), so three fields = total
- accepts as an optional argument tin to = place unclassified traffic in (defaults to 0)
- = returns an error if no queues available for unclassified = traffic
- puts mappings into up to three global BPF = maps (for MAC, IPv4 and IPv6)
- puts unclassified = traffic tin, if non-zero, into a global
- should = lock globals here so updates can be made without removing / re-adding = qdisc

BPF = filter:
- tries to classify first using MAC address = map, then IPv4 or IPv6 maps for IP traffic
- = spreads any unclassified traffic in unclassified traffic tin across = remaining classids from max(classid)+1 to 1023

Lastly, although it's natural to use = classid for flow (subscriber) and priority for tin, we have a hard = maximum of 2^16 subscribers in a given tin (minor classid is 16 bits). = It doesn=E2=80=99t matter now because we only have 1024 flows per tin, = but for ISP cake, is a limit of ~2^16 subscribers in one tin enough? = Otherwise we=E2=80=99d have to change the way we specify this.

= --Apple-Mail=_C3D8F03F-4770-4E60-B9B6-5C16D828F284--