[Netem] deterministic pruning patch proposal

Marie Laurent laurent.marie at thomson.net
Thu Sep 13 09:33:54 PDT 2007


   Hello,

Three years ago I have submitted a deterministic drop patch to the
nistnet community. It drops n packets in a row every p incoming packets.

By the time, we have switched to netem but we still needed the
deterministic drop feature. I have ported the patch to netem some months
ago. It runs on kernels 2.6.9 and 2.6.11 (Red Hat Entreprise 4) and it
has been heavily tested 24 hours a day.

The patch has been renamed "deterministic pruning patch" because both
loss and drop keywords were used.

The patch has been upgraded to the 2.6.20 kernel level. Unfortunately, I
do not have a 2.6.22 linux box.

SYNOPSYS
--------
The prune keyword has been added to the iproute2 tc command interpreter
(iproute2-2.6.20-070313.tar.gz package). 
It requires two parameters: the period and the length (i.e. the number
of frames dropped in a row).
   e.g. /usr/sbin/tc qdisc add dev eth1 parent 1:1 handle 10: netem
prune 11 2
   2 packets will be discarded every 11 frames coming into the netem
queue.

Those parameters are also displayed by the show command, e.g.:
/usr/sbin/tc -s qdisc show dev eth1
qdisc prio 1: bands 9 priomap  8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
 Sent 11430417716 bytes 8324686 pkt (dropped 1486475, overlimits 0
requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0
qdisc netem 10: parent 1:1 limit 1000 prune {period=11, length=2}
reorder 100%
 Sent 9164119332 bytes 6689138 pkt (dropped 1486475, overlimits 0
requeues 0)
 rate 0bit 0pps backlog 0b 0p requeues 0

The prune parameters (period and length) are transmitted to the netem
scheduler at kernel level (linux 2.6.20 net/sched/sch_netem.c). If the
period is not null, the netem schedulers counts the incoming buffers
(skb) and notices to remove the required frames (length) every period of
frames.

PATCHES:
--------
The patch is divided in two parts: iproute2 user level and kernel level.
The patch is done according to diff -u standard.

iproute2-2.6.20-070313.tar.gz patch:
------------------------------------
diff -ru iproute-2.6.20-070313/include/linux/pkt_sched.h
iproute-2.6.20-prune/include/linux/pkt_sched.h
--- iproute-2.6.20-070313/include/linux/pkt_sched.h	2007-03-13
22:50:56.000000000 +0100
+++ iproute-2.6.20-prune/include/linux/pkt_sched.h	2007-08-16
10:28:19.204907000 +0200
@@ -443,6 +443,8 @@
 	__u32	gap;		/* re-ordering gap (0 for none) */
 	__u32   duplicate;	/* random packet dup  (0=none ~0=100%)
*/
 	__u32	jitter;		/* random jitter in latency (us) */
+	__u32	prune_period;	/* prune period in packets */
+	__u32	prune_length;	/* prune length in packets */
 };
 
 struct tc_netem_corr
diff -ru iproute-2.6.20-070313/tc/q_netem.c
iproute-2.6.20-prune/tc/q_netem.c
--- iproute-2.6.20-070313/tc/q_netem.c	2007-03-13 22:50:56.000000000
+0100
+++ iproute-2.6.20-prune/tc/q_netem.c	2007-08-16 10:32:09.046934000
+0200
@@ -32,6 +32,7 @@
 "                 [ delay TIME [ JITTER [CORRELATION]]]\n" \
 "                 [ distribution {uniform|normal|pareto|paretonormal}
]\n" \
 "                 [ drop PERCENT [CORRELATION]] \n" \
+"                 [ prune PERIOD LENGTH\n" \
 "                 [ corrupt PERCENT [CORRELATION]] \n" \
 "                 [ duplicate PERCENT [CORRELATION]]\n" \
 "                 [ reorder PRECENT [CORRELATION] [ gap DISTANCE
]]\n");
@@ -185,6 +186,19 @@
 					return -1;
 				}
 			}
+		} else if (matches(*argv, "prune") == 0) {
+			NEXT_ARG();
+			if (get_u32(&opt.prune_period, *argv, 0)) {
+				explain1("prune");
+				return -1;
+			}
+			if (NEXT_IS_NUMBER()) {
+				NEXT_ARG();
+				if (get_u32(&opt.prune_length, *argv,
0)) {
+					explain1("prune");
+					return -1;
+				}
+			}
 		} else if (matches(*argv, "reorder") == 0) {
 			NEXT_ARG();
 			present[TCA_NETEM_REORDER] = 1;
@@ -353,6 +367,9 @@
 			fprintf(f, " %s", sprint_percent(cor->loss_corr,
b1));
 	}
 
+	if (qopt.prune_period)
+		fprintf(f, " prune {period=%lu, length=%lu}", (unsigned
long)qopt.prune_period, (unsigned long)qopt.prune_length);
+
 	if (qopt.duplicate) {
 		fprintf(f, " duplicate %s",
 			sprint_percent(qopt.duplicate, b1));



linux-2.6.20 sch_netem kernel patch
-----------------------------------
IMPORTANT NOTE: The linux/pkt_sched.h file SHOULD be identical at user
level (iproute2) and kernel level.


--- linux-2.6.20-ipipe/include/linux/pkt_sched.h	2007-02-04
19:44:54.000000000 +0100
+++ iproute-2.6.20-prune/include/linux/pkt_sched.h	2007-08-16
10:28:19.204907000 +0200
@@ -443,6 +443,8 @@
 	__u32	gap;		/* re-ordering gap (0 for none) */
 	__u32   duplicate;	/* random packet dup  (0=none ~0=100%)
*/
 	__u32	jitter;		/* random jitter in latency (us) */
+	__u32	prune_period;	/* prune period in packets */
+	__u32	prune_length;	/* prune length in packets */
 };
 
 struct tc_netem_corr


--- linux-2.6.20-ipipe/net/sched/sch_netem.c	2007-02-04
19:44:54.000000000 +0100
+++ sch_netem.c	2007-09-13 17:37:09.580671000 +0200
@@ -65,6 +65,9 @@
 	u32 duplicate;
 	u32 reorder;
 	u32 corrupt;
+	u32 prune_period;	/* prune period in packets */
+	u32 prune_length;	/* prune length in packets */
+	u32 packet_number;      /* packet number [0..prune_period] */
 
 	struct crndstate {
 		unsigned long last;
@@ -164,6 +167,19 @@
 	if (q->loss && q->loss >= get_crandom(&q->loss_cor))
 		--count;
 
+	/* periodic pruning */
+	if (q->prune_period) 
+        {
+           /* Compute the packet number modulo the prune period */
+           q->packet_number = (q->packet_number+1) % q->prune_period;
+           /* Packet numbers from 0 to prune_length-1 are dropped */
+           if (q->packet_number < q->prune_length)
+           {
+		pr_debug("netem_enqueue: periodic pruning\n");
+		--count;
+	   }
+	}
+
 	if (count == 0) {
 		sch->qstats.drops++;
 		kfree_skb(skb);
@@ -437,6 +453,8 @@
 	q->counter = 0;
 	q->loss = qopt->loss;
 	q->duplicate = qopt->duplicate;
+	q->prune_period = qopt->prune_period;
+	q->prune_length = qopt->prune_length;
 
 	/* for compatiablity with earlier versions.
 	 * if gap is set, need to assume 100% probablity
@@ -611,6 +629,8 @@
 	qopt.loss = q->loss;
 	qopt.gap = q->gap;
 	qopt.duplicate = q->duplicate;
+	qopt.prune_period = q->prune_period;
+	qopt.prune_length = q->prune_length;
 	RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
 
 	cor.delay_corr = q->delay_cor.rho;


TEST SHELLS:
------------
Once you have recompiled and installed the patch at both user and kernel
level, you may test the new prune option. This option is usually
associated to a tc filter. You often want to destroy some packets on a
dedicated stream.

Here are two shells, one to set up a netem prune rule and its associated
filter and the other to remove everything and bring the default
pfifo_fast queue.

Test_prune_patch.sh
-------------------
#!/bin/sh

# Installed TC release
TC=/usr/sbin/tc

# remove prior qdisc if it exists
$TC qdisc del dev eth1 root
# wait for completion of the deletion command
sleep 1
# remove the netem kernel module
/sbin/rmmod sch_netem
sleep 1

# Create a PRIO queue on the output (eth1) with 9 queues.
# All traffic will go to the last queue if no rule applies
# The 8 first FIFO may be bound to netem emulators
$TC qdisc add dev eth1 root handle 1: prio bands 9 priomap 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8

#Create a netem queue on prio 1/class 1:1 periodic pruning : delete 2
packets every 11 on UDP port 5004
$TC qdisc add dev eth1 parent 1:1 handle 10: netem prune 11 2
# Create a rule to forward output packets to netem queue
$TC filter add dev eth1 protocol ip parent 1: prio 1 u32 match ip dst
239.1.1.1/32 match ip dport 5004 0xffff flowid 1:1

# add below other pair of netem and filter rules
# ...

# show qdisc configuration
$TC -s qdisc show dev eth1

# show filter configuration
$TC -s filter show dev eth1


Rm_prune_patch.sh
-----------------
#!/bin/sh

# Installed TC release
TC=/usr/sbin/tc

# remove prior qdisc if it exists
$TC qdisc del dev eth1 root
# wait for completion of the deletion command
sleep 1
# remove the netem kernel module
/sbin/rmmod sch_netem
sleep 1

# show qdisc configuration
$TC -s qdisc show dev eth1

# show filter configuration
$TC -s filter show dev eth1


ARCHIVES:
---------
I may supply on request the experimental 2.6.9 and 2.6.11 deterministic
pruning patches.

I wish this simple piece of code will help you.

Yours sincerely,

Mr. Laurent MARIE



More information about the Netem mailing list