[Cake] [RFC PATCH 0/5] patches for iproute2-net-next for netem slotting and cake

[Cake] [RFC PATCH 0/5] patches for iproute2-net-next for netem slotting and cake

[Dave Taht]

This has some work in progress towards finalizing the new netem 'slot'
feature (still needs to be made backward compatible with old kernels)
and a forward port of the existing tc-adv cake code to the latest iproute.

Dave Taht (5):
  Update to the actual net-next
  Add cake pkt_sched.h
  tc: support conversions to or from 64 bit nanosecond-based time
  q_netem: support delivering packets in delayed time slots
  netem: add documentation for the new slotting feature

 include/uapi/linux/pkt_sched.h | 68 ++++++++++++++++++++++++++++++++++++++++++
 man/man8/tc-netem.8            | 32 +++++++++++++++++++-
 tc/q_netem.c                   | 55 +++++++++++++++++++++++++++++++++-
 tc/tc_util.c                   | 60 +++++++++++++++++++++++++++++++++++++
 tc/tc_util.h                   |  3 ++
 5 files changed, 216 insertions(+), 2 deletions(-)

-- 
2.7.4

[Cake] [RFC PATCH 1/5] Update to the actual net-next

[Dave Taht]

---
 include/uapi/linux/pkt_sched.h | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/include/uapi/linux/pkt_sched.h b/include/uapi/linux/pkt_sched.h
index 6a2c5ea..af3cc2f 100644
--- a/include/uapi/linux/pkt_sched.h
+++ b/include/uapi/linux/pkt_sched.h
@@ -537,6 +537,9 @@ enum {
 	TCA_NETEM_ECN,
 	TCA_NETEM_RATE64,
 	TCA_NETEM_PAD,
+	TCA_NETEM_LATENCY64,
+	TCA_NETEM_JITTER64,
+	TCA_NETEM_SLOT,
 	__TCA_NETEM_MAX,
 };
 
@@ -574,6 +577,13 @@ struct tc_netem_rate {
 	__s32	cell_overhead;
 };
 
+struct tc_netem_slot {
+	__s64   min_delay; /* nsec */
+	__s64   max_delay;
+	__s32   max_packets;
+	__s32   max_bytes;
+};
+
 enum {
 	NETEM_LOSS_UNSPEC,
 	NETEM_LOSS_GI,		/* General Intuitive - 4 state model */
-- 
2.7.4

[Cake] [RFC PATCH 2/5] Add cake pkt_sched.h

[Dave Taht]

---
 include/uapi/linux/pkt_sched.h | 58 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)

diff --git a/include/uapi/linux/pkt_sched.h b/include/uapi/linux/pkt_sched.h
index af3cc2f..206af5e 100644
--- a/include/uapi/linux/pkt_sched.h
+++ b/include/uapi/linux/pkt_sched.h
@@ -935,4 +935,62 @@ enum {
 
 #define TCA_CBS_MAX (__TCA_CBS_MAX - 1)
 
+/* CAKE */
+enum {
+	TCA_CAKE_UNSPEC,
+	TCA_CAKE_BASE_RATE,
+	TCA_CAKE_DIFFSERV_MODE,
+	TCA_CAKE_ATM,
+	TCA_CAKE_FLOW_MODE,
+	TCA_CAKE_OVERHEAD,
+	TCA_CAKE_RTT,
+	TCA_CAKE_TARGET,
+	TCA_CAKE_AUTORATE,
+	TCA_CAKE_MEMORY,
+	TCA_CAKE_NAT,
+	TCA_CAKE_ETHERNET,
+	TCA_CAKE_WASH,
+	TCA_CAKE_MPU,
+	TCA_CAKE_INGRESS,
+	TCA_CAKE_ACK_FILTER,
+	__TCA_CAKE_MAX
+};
+#define TCA_CAKE_MAX	(__TCA_CAKE_MAX - 1)
+
+struct tc_cake_traffic_stats {
+	__u32 packets;
+	__u32 link_ms;
+	__u64 bytes;
+};
+
+#define TC_CAKE_MAX_TINS (8)
+struct tc_cake_xstats {
+	__u16 version;  /* == 5, increments when struct extended */
+	__u8  max_tins; /* == TC_CAKE_MAX_TINS */
+	__u8  tin_cnt;  /* <= TC_CAKE_MAX_TINS */
+
+	__u32 threshold_rate   [TC_CAKE_MAX_TINS];
+	__u32 target_us	       [TC_CAKE_MAX_TINS];
+	struct tc_cake_traffic_stats sent      [TC_CAKE_MAX_TINS];
+	struct tc_cake_traffic_stats dropped   [TC_CAKE_MAX_TINS];
+	struct tc_cake_traffic_stats ecn_marked[TC_CAKE_MAX_TINS];
+	struct tc_cake_traffic_stats backlog   [TC_CAKE_MAX_TINS];
+	__u32 interval_us      [TC_CAKE_MAX_TINS];
+	__u32 way_indirect_hits[TC_CAKE_MAX_TINS];
+	__u32 way_misses       [TC_CAKE_MAX_TINS];
+	__u32 way_collisions   [TC_CAKE_MAX_TINS];
+	__u32 peak_delay_us    [TC_CAKE_MAX_TINS]; /* ~= bulk flow delay */
+	__u32 avge_delay_us    [TC_CAKE_MAX_TINS];
+	__u32 base_delay_us    [TC_CAKE_MAX_TINS]; /* ~= sparse flows delay */
+	__u16 sparse_flows     [TC_CAKE_MAX_TINS];
+	__u16 bulk_flows       [TC_CAKE_MAX_TINS];
+	__u16 unresponse_flows [TC_CAKE_MAX_TINS]; /* v4 - was u32 last_len */
+	__u16 spare	       [TC_CAKE_MAX_TINS]; /* v4 - split last_len */
+	__u32 max_skblen       [TC_CAKE_MAX_TINS];
+	__u32 capacity_estimate;  /* version 2 */
+	__u32 memory_limit;       /* version 3 */
+	__u32 memory_used;	  /* version 3 */
+	struct tc_cake_traffic_stats ack_drops [TC_CAKE_MAX_TINS]; /* v5 */
+};
+
 #endif
-- 
2.7.4

[Cake] [RFC PATCH 3/5] tc: support conversions to or from 64 bit nanosecond-based time

[Dave Taht]

Using a 32 bit field to represent time in nanoseconds results in a
maximum value of about 4.3 seconds, which is well below many observed
delays in WiFi and LTE, and barely in the ballpark for a trip past the
Earth's moon, Luna.

Using 64 bit time fields in nanoseconds allows us to simulate
network diameters of several hundred light-years. However, only
conversions to and from ns, us, ms, and seconds are provided.
---
 tc/tc_util.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 tc/tc_util.h |  3 +++
 2 files changed, 63 insertions(+)

diff --git a/tc/tc_util.c b/tc/tc_util.c
index 472fc5d..ab344c8 100644
--- a/tc/tc_util.c
+++ b/tc/tc_util.c
@@ -322,6 +322,66 @@ char *sprint_ticks(__u32 ticks, char *buf)
 	return sprint_time(tc_core_tick2time(ticks), buf);
 }
 
+/* 64 bit times are represented internally in nanoseconds */
+
+#define USEC_PER_SEC 1000
+#define MSEC_PER_SEC (1000 * 1000)
+#define NSEC_PER_SEC (MSEC_PER_SEC * 1000)
+
+int get_time64(__u64 *time, const char *str)
+{
+	double t;
+	char *p;
+
+	t = strtod(str, &p);
+	if (p == str)
+		return -1;
+
+	if (*p) {
+		if (strcasecmp(p, "s") == 0 ||
+		    strcasecmp(p, "sec") == 0 ||
+		    strcasecmp(p, "secs") == 0)
+			t *= NSEC_PER_SEC;
+		else if (strcasecmp(p, "ms") == 0 ||
+			 strcasecmp(p, "msec") == 0 ||
+			 strcasecmp(p, "msecs") == 0)
+			t *= MSEC_PER_SEC;
+		else if (strcasecmp(p, "us") == 0 ||
+			 strcasecmp(p, "usec") == 0 ||
+			 strcasecmp(p, "usecs") == 0)
+			t *= USEC_PER_SEC;
+		else if (strcasecmp(p, "ns") == 0 ||
+			 strcasecmp(p, "nsec") == 0 ||
+			 strcasecmp(p, "nsecs") == 0)
+			t *= 1;
+		else
+			return -1;
+	}
+
+	*time = t;
+	return 0;
+}
+
+void print_time64(char *buf, int len, __u64 time)
+{
+	double tmp = time;
+
+	if (time >= NSEC_PER_SEC)
+		snprintf(buf, len, "%.3fs", tmp/NSEC_PER_SEC);
+	else if (time >= MSEC_PER_SEC)
+		snprintf(buf, len, "%.3fms", tmp/MSEC_PER_SEC);
+	else if (time >= USEC_PER_SEC)
+		snprintf(buf, len, "%.3fus", tmp/USEC_PER_SEC);
+	else
+		snprintf(buf, len, "%lldns", time);
+}
+
+char *sprint_time64(__u64 time, char *buf)
+{
+	print_time64(buf, SPRINT_BSIZE-1, time);
+	return buf;
+}
+
 int get_size(unsigned int *size, const char *str)
 {
 	double sz;
diff --git a/tc/tc_util.h b/tc/tc_util.h
index 583a21a..3d87e8d 100644
--- a/tc/tc_util.h
+++ b/tc/tc_util.h
@@ -72,12 +72,14 @@ int get_rate64(__u64 *rate, const char *str);
 int get_size(unsigned int *size, const char *str);
 int get_size_and_cell(unsigned int *size, int *cell_log, char *str);
 int get_time(unsigned int *time, const char *str);
+int get_time64(__u64 *time, const char *str);
 int get_linklayer(unsigned int *val, const char *arg);
 
 void print_rate(char *buf, int len, __u64 rate);
 void print_size(char *buf, int len, __u32 size);
 void print_qdisc_handle(char *buf, int len, __u32 h);
 void print_time(char *buf, int len, __u32 time);
+void print_time64(char *buf, int len, __u64 time);
 void print_linklayer(char *buf, int len, unsigned int linklayer);
 
 char *sprint_rate(__u64 rate, char *buf);
@@ -85,6 +87,7 @@ char *sprint_size(__u32 size, char *buf);
 char *sprint_qdisc_handle(__u32 h, char *buf);
 char *sprint_tc_classid(__u32 h, char *buf);
 char *sprint_time(__u32 time, char *buf);
+char *sprint_time64(__u64 time, char *buf);
 char *sprint_ticks(__u32 ticks, char *buf);
 char *sprint_linklayer(unsigned int linklayer, char *buf);
 
-- 
2.7.4

[Cake] [RFC PATCH 4/5] q_netem: support delivering packets in delayed time slots

[Dave Taht]

Slotting is a crude approximation of the behaviors of shared media such
as cable, wifi, and LTE, which gather up a bunch of packets within a
varying delay window and deliver them, relative to that, nearly all at
once.

It works within the existing loss, duplication, jitter and delay
parameters of netem. Some amount of inherent latency must be specified,
regardless.

The new "slot" parameter specifies a minimum and maximum delay between
transmission attempts.

The "bytes" and "packets" parameters can be used to limit the amount of
information transferred per slot.

Examples of use:

tc qdisc add dev eth0 root netem delay 200us \
        slot 800us 10ms bytes 64k packets 42

A more correct example, using stacked netem instances and a packet limit
to emulate a tail drop wifi queue with slots and variable packet
delivery, with a 200Mbit isochronous underlying rate, and 20ms path
delay:

tc qdisc add dev eth0 root handle 1: netem delay 20ms rate 200mbit \
         limit 10000
tc qdisc add dev eth0 parent 1:1 handle 10:1 netem delay 200us \
         slot 800us 10ms bytes 64k packets 42 limit 512
---
 tc/q_netem.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 54 insertions(+), 1 deletion(-)

diff --git a/tc/q_netem.c b/tc/q_netem.c
index 82eb46f..1524788 100644
--- a/tc/q_netem.c
+++ b/tc/q_netem.c
@@ -40,7 +40,10 @@ static void explain(void)
 "                 [ loss gemodel PERCENT [R [1-H [1-K]]]\n" \
 "                 [ ecn ]\n" \
 "                 [ reorder PRECENT [CORRELATION] [ gap DISTANCE ]]\n" \
-"                 [ rate RATE [PACKETOVERHEAD] [CELLSIZE] [CELLOVERHEAD]]\n");
+"                 [ rate RATE [PACKETOVERHEAD] [CELLSIZE] [CELLOVERHEAD]]\n" \
+"                 [ slot MIN_DELAY MAX_DELAY [packets MAX_PACKETS]" \
+" [bytes MAX_BYTES]]\n" \
+		);
 }
 
 static void explain1(const char *arg)
@@ -178,6 +181,7 @@ static int netem_parse_opt(struct qdisc_util *qu, int argc, char **argv,
 	struct tc_netem_gimodel gimodel;
 	struct tc_netem_gemodel gemodel;
 	struct tc_netem_rate rate = {};
+	struct tc_netem_slot slot = {};
 	__s16 *dist_data = NULL;
 	__u16 loss_type = NETEM_LOSS_UNSPEC;
 	int present[__TCA_NETEM_MAX] = {};
@@ -421,6 +425,36 @@ static int netem_parse_opt(struct qdisc_util *qu, int argc, char **argv,
 					return -1;
 				}
 			}
+		} else if (matches(*argv, "slot") == 0) {
+			NEXT_ARG();
+			present[TCA_NETEM_SLOT] = 1;
+			if (get_time64(&slot.min_delay, *argv)) {
+				explain1("slot min_delay");
+				return -1;
+			}
+			if (NEXT_IS_NUMBER()) {
+				NEXT_ARG();
+				if (get_time64(&slot.max_delay, *argv)) {
+					explain1("slot min_delay max_delay");
+					return -1;
+				}
+			}
+			if (slot.max_delay < slot.min_delay)
+				slot.max_delay = slot.min_delay;
+		} else if (matches(*argv, "packets") == 0) {
+			NEXT_ARG();
+			if (get_s32(&slot.max_packets, *argv, 0)) {
+				explain1("slot packets");
+				return -1;
+			}
+		} else if (matches(*argv, "bytes") == 0) {
+			unsigned int max_bytes;
+			NEXT_ARG();
+			if (get_size(&max_bytes, *argv)) {
+				explain1("slot bytes");
+				return -1;
+			}
+			slot.max_bytes = (int) max_bytes;
 		} else if (strcmp(*argv, "help") == 0) {
 			explain();
 			return -1;
@@ -481,6 +515,10 @@ static int netem_parse_opt(struct qdisc_util *qu, int argc, char **argv,
 	    addattr_l(n, 1024, TCA_NETEM_CORRUPT, &corrupt, sizeof(corrupt)) < 0)
 		return -1;
 
+	if (present[TCA_NETEM_SLOT] &&
+	    addattr_l(n, 1024, TCA_NETEM_SLOT, &slot, sizeof(slot)) < 0)
+		return -1;
+
 	if (loss_type != NETEM_LOSS_UNSPEC) {
 		struct rtattr *start;
 
@@ -535,6 +573,7 @@ static int netem_print_opt(struct qdisc_util *qu, FILE *f, struct rtattr *opt)
 	int *ecn = NULL;
 	struct tc_netem_qopt qopt;
 	const struct tc_netem_rate *rate = NULL;
+	const struct tc_netem_slot *slot = NULL;
 	int len;
 	__u64 rate64 = 0;
 
@@ -595,6 +634,11 @@ static int netem_print_opt(struct qdisc_util *qu, FILE *f, struct rtattr *opt)
 				return -1;
 			rate64 = rta_getattr_u64(tb[TCA_NETEM_RATE64]);
 		}
+		if (tb[TCA_NETEM_SLOT]) {
+			if (RTA_PAYLOAD(tb[TCA_NETEM_SLOT]) < sizeof(*slot))
+				return -1;
+		        slot = RTA_DATA(tb[TCA_NETEM_SLOT]);
+		}
 	}
 
 	fprintf(f, "limit %d", qopt.limit);
@@ -668,6 +712,15 @@ static int netem_print_opt(struct qdisc_util *qu, FILE *f, struct rtattr *opt)
 			fprintf(f, " celloverhead %d", rate->cell_overhead);
 	}
 
+	if (slot) {
+		fprintf(f, " slot %s", sprint_time64(slot->min_delay, b1));
+		fprintf(f, " %s", sprint_time64(slot->max_delay, b1));
+		if(slot->max_packets)
+			fprintf(f, " packets %d", slot->max_packets);
+		if(slot->max_bytes)
+			fprintf(f, " bytes %d", slot->max_bytes);
+	}
+
 	if (ecn)
 		fprintf(f, " ecn ");
 
-- 
2.7.4

[Cake] [RFC PATCH 5/5] netem: add documentation for the new slotting feature

[Dave Taht]

---
 man/man8/tc-netem.8 | 32 +++++++++++++++++++++++++++++++-
 1 file changed, 31 insertions(+), 1 deletion(-)

diff --git a/man/man8/tc-netem.8 b/man/man8/tc-netem.8
index b31384f..8c41d77 100644
--- a/man/man8/tc-netem.8
+++ b/man/man8/tc-netem.8
@@ -8,7 +8,8 @@ NetEm \- Network Emulator
 .I OPTIONS
 
 .IR OPTIONS " := [ " LIMIT " ] [ " DELAY " ] [ " LOSS \
-" ] [ " CORRUPT " ] [ " DUPLICATION " ] [ " REORDERING " ][ " RATE " ]"
+" ] [ " CORRUPT " ] [ " DUPLICATION " ] [ " REORDERING " ] [ " RATE \
+" ] [ " SLOT " ]"
 
 .IR LIMIT " := "
 .B limit
@@ -51,6 +52,14 @@ NetEm \- Network Emulator
 .B rate
 .IR RATE " [ " PACKETOVERHEAD " [ " CELLSIZE " [ " CELLOVERHEAD " ]]]]"
 
+.IR SLOT " := "
+.BR slot
+.IR MIN_DELAY " [ " MAX_DELAY " ] {["
+.BR packets
+.IR PACKETS " ] [ "
+.BR bytes
+.IR BYTES " ] }]"
+
 
 .SH DESCRIPTION
 NetEm is an enhancement of the Linux traffic control facilities
@@ -162,6 +171,27 @@ granularity avoid a perfect shaping at a specific level. This will show up in
 an artificial packet compression (bursts). Another influence factor are network
 adapter buffers which can also add artificial delay.
 
+.SS slot
+defer delivering accumulated packets to within a slot, with each available slot
+configured with a minimum delay to acquire, and an optional maximum delay.  Slot
+delays can be specified in nanoseconds, microseconds, milliseconds or seconds
+(e.g. 800us). Values for the optional parameters
+.I BYTES
+will limit the number of bytes delivered per slot, and/or
+.I PACKETS
+will limit the number of packets delivered per slot.
+
+These slot options can provide a crude approximation of bursty MACs such as
+DOCSIS, WiFi, and LTE.
+
+Note that slotting is limited by several factors: the kernel clock granularity,
+as with a rate, and attempts to deliver many packets within a slot will be
+smeared by the timer resolution, and by the underlying native bandwidth also.
+
+It is possible to combine slotting with a rate, in which case complex behaviors
+where either the rate, or the slot limits on bytes or packets per slot, govern
+the actual delivered rate.
+
 .SH LIMITATIONS
 The main known limitation of Netem are related to timer granularity, since
 Linux is not a real-time operating system.
-- 
2.7.4

Re: [Cake] [RFC PATCH 1/5] Update to the actual net-next

[Stephen Hemminger]

On Fri, 17 Nov 2017 13:19:24 -0800
Dave Taht <dave.taht@gmail.com> wrote:

> ---
>  include/uapi/linux/pkt_sched.h | 10 ++++++++++
>  1 file changed, 10 insertions(+)
> 
> diff --git a/include/uapi/linux/pkt_sched.h b/include/uapi/linux/pkt_sched.h
> index 6a2c5ea..af3cc2f 100644
> --- a/include/uapi/linux/pkt_sched.h
> +++ b/include/uapi/linux/pkt_sched.h
> @@ -537,6 +537,9 @@ enum {
>  	TCA_NETEM_ECN,
>  	TCA_NETEM_RATE64,
>  	TCA_NETEM_PAD,
> +	TCA_NETEM_LATENCY64,
> +	TCA_NETEM_JITTER64,
> +	TCA_NETEM_SLOT,
>  	__TCA_NETEM_MAX,
>  };
>  
> @@ -574,6 +577,13 @@ struct tc_netem_rate {
>  	__s32	cell_overhead;
>  };
>  
> +struct tc_netem_slot {
> +	__s64   min_delay; /* nsec */
> +	__s64   max_delay;
> +	__s32   max_packets;
> +	__s32   max_bytes;
> +};
> +
>  enum {
>  	NETEM_LOSS_UNSPEC,
>  	NETEM_LOSS_GI,		/* General Intuitive - 4 state model */

That is already in upstream

Re: [Cake] [RFC PATCH 1/5] Update to the actual net-next

[Dave Taht]

Heh. Didn't know you were on the list. It wasn't a day or three back!

Thx!

On Fri, Nov 17, 2017 at 1:26 PM, Stephen Hemminger
<stephen@networkplumber.org> wrote:
> On Fri, 17 Nov 2017 13:19:24 -0800
> Dave Taht <dave.taht@gmail.com> wrote:
>
>> ---
>>  include/uapi/linux/pkt_sched.h | 10 ++++++++++
>>  1 file changed, 10 insertions(+)
>>
>> diff --git a/include/uapi/linux/pkt_sched.h b/include/uapi/linux/pkt_sched.h
>> index 6a2c5ea..af3cc2f 100644
>> --- a/include/uapi/linux/pkt_sched.h
>> +++ b/include/uapi/linux/pkt_sched.h
>> @@ -537,6 +537,9 @@ enum {
>>       TCA_NETEM_ECN,
>>       TCA_NETEM_RATE64,
>>       TCA_NETEM_PAD,
>> +     TCA_NETEM_LATENCY64,
>> +     TCA_NETEM_JITTER64,
>> +     TCA_NETEM_SLOT,
>>       __TCA_NETEM_MAX,
>>  };
>>
>> @@ -574,6 +577,13 @@ struct tc_netem_rate {
>>       __s32   cell_overhead;
>>  };
>>
>> +struct tc_netem_slot {
>> +     __s64   min_delay; /* nsec */
>> +     __s64   max_delay;
>> +     __s32   max_packets;
>> +     __s32   max_bytes;
>> +};
>> +
>>  enum {
>>       NETEM_LOSS_UNSPEC,
>>       NETEM_LOSS_GI,          /* General Intuitive - 4 state model */
>
> That is already in upstream



-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619