[PATCH 2.6] (1/4) netem - update API for new features

[PATCH 2.6] (1/4) netem - update API for new features

[Stephen Hemminger]

Extend netem options to support new features.

Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

diff -Nru a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
--- a/include/linux/pkt_sched.h	2004-08-24 14:43:33 -07:00
+++ b/include/linux/pkt_sched.h	2004-08-24 14:43:33 -07:00
@@ -401,7 +401,8 @@
 
 #define TCA_ATM_MAX	TCA_ATM_STATE
 
-/* Network emulator */
+/* Network section */
+
 struct tc_netem_qopt
 {
 	__u32	latency;	/* added delay (us) */
@@ -409,6 +410,13 @@
 	__u32	loss;		/* random packet loss (0=none ~0=100%) */
 	__u32	gap;		/* re-ordering gap (0 for delay all) */
 	__u32   duplicate;	/* random packet dup  (0=none ~0=100%) */
-	__u32	jitter;		/* random jitter in latency (us) */
+	__u32	jitter;		/* delay sigma (us) */
+
+	__u32	delay_corr;	/* delay correllation (0=none ~0=100%) */
+	__u32	loss_corr;	/* packet loss correllation (0=none ~0=100%) */
+	__u32	dup_corr;	/* duplicate correlation (0=none ~0=100%) */
+
+	__s16	delay_dist[0];	/* delay distribution table (optional) */
+#define TCA_NETEM_TABLEFACTOR	8192
 };
 #endif

[PATCH 2.6] (2/4) netem - comment update

[Stephen Hemminger]

Update comments in netem.

Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c	2004-08-24 14:43:05 -07:00
+++ b/net/sched/sch_netem.c	2004-08-24 14:43:05 -07:00
@@ -6,6 +6,9 @@
  * 		as published by the Free Software Foundation; either version
  * 		2 of the License, or (at your option) any later version.
  *
+ *  		Many of the algorithms and ideas for this came from
+ *		NIST Net which is not copyrighted. 
+ *
  * Authors:	Stephen Hemminger <shemminger@osdl.org>
  *		Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
  */
@@ -22,11 +25,31 @@
 
 #include <net/pkt_sched.h>
 
-/*	Network emulator
- *
- *	This scheduler can alters spacing and order
- *	Similar to NISTnet and BSD Dummynet.
- */
+/*	Network Emulation Queuing algorithm.
+	====================================
+
+	Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based
+		 Network Emulation Tool
+		 [2] Luigi Rizzo, DummyNet for FreeBSD
+
+	 ----------------------------------------------------------------
+
+	 This started out as a simple way to delay outgoing packets to
+	 test TCP but has grown to include most of the functionality
+	 of a full blown network emulator like NISTnet. It can delay
+	 packets and add random jitter (and correlation). The random
+	 distribution can be loaded from a table as well to provide
+	 normal, Pareto, or experimental curves. Packet loss,
+	 duplication, and reordering can also be emulated.
+
+	 This qdisc does not do classification that can be handled in
+	 layering other disciplines.  It does not need to do bandwidth
+	 control either since that can be handled by using token
+	 bucket or other rate control.
+
+	 The simulator is limited by the Linux timer resolution
+	 and will create packet bursts on the HZ boundary (1ms).
+*/
 
 struct netem_sched_data {
 	struct Qdisc	*qdisc;

[PATCH 2.6] (3/4) netem - support packet duplication

[Stephen Hemminger]

Add support for duplicating packets.

Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c	2004-08-24 16:58:13 -07:00
+++ b/net/sched/sch_netem.c	2004-08-24 16:58:13 -07:00
@@ -62,6 +62,7 @@
 	u32 counter;
 	u32 gap;
 	u32 jitter;
+	u32 duplicate;
 };
 
 /* Time stamp put into socket buffer control block */
@@ -624,22 +625,13 @@
 /* Enqueue packets with underlying discipline (fifo)
  * but mark them with current time first.
  */
-static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+static int netem_add_packet(struct Qdisc *sch, struct sk_buff *skb)
 {
 	struct netem_sched_data *q = qdisc_priv(sch);
 	struct netem_skb_cb *cb = (struct netem_skb_cb *)skb->cb;
 	psched_time_t now;
 	long delay;
 
-	pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
-
-	/* Random packet drop 0 => none, ~0 => all */
-	if (q->loss && q->loss >= net_random()) {
-		sch->stats.drops++;
-		return 0;	/* lie about loss so TCP doesn't know */
-	}
-
-
 	/* If doing simple delay then gap == 0 so all packets
 	 * go into the delayed holding queue
 	 * otherwise if doing out of order only "1 out of gap"
@@ -671,7 +663,7 @@
 		sch->q.qlen++;
 		sch->stats.bytes += skb->len;
 		sch->stats.packets++;
-		return 0;
+		return NET_XMIT_SUCCESS;
 	}
 
 	sch->stats.drops++;
@@ -679,6 +671,31 @@
 	return NET_XMIT_DROP;
 }
 
+static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
+	struct netem_sched_data *q = qdisc_priv(sch);
+
+	pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
+
+	/* Random packet drop 0 => none, ~0 => all */
+	if (q->loss && q->loss >= net_random()) {
+		pr_debug("netem_enqueue: random loss\n");
+		sch->stats.drops++;
+		return 0;	/* lie about loss so TCP doesn't know */
+	}
+
+	/* Random duplication */
+	if (q->duplicate && q->duplicate >= net_random()) {
+		struct sk_buff *skb2 = skb_clone(skb, GFP_ATOMIC);
+
+		pr_debug("netem_enqueue: dup %p\n", skb2);
+		if (skb2)
+			netem_add_packet(sch, skb2);
+	}
+
+	return netem_add_packet(sch, skb);
+}
+
 /* Requeue packets but don't change time stamp */
 static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
 {
@@ -806,6 +823,7 @@
 		q->limit = qopt->limit;
 		q->gap = qopt->gap;
 		q->loss = qopt->loss;
+		q->duplicate = qopt->duplicate;
 	}
 	sch_tree_unlock(sch);
 
@@ -849,6 +867,7 @@
 	qopt.limit = q->limit;
 	qopt.loss = q->loss;
 	qopt.gap = q->gap;
+	qopt.duplicate = q->duplicate;
 
 	RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
 

[PATCH 2.6] (4/4) netem - change parameters shouldn't destroy child qdisc

[Stephen Hemminger]

Fix netem to allow changing parameters without zapping the underlying
qdisc.

Signed-off-by: Stephen Hemminger <shemminger@osdl.org>
 
diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c	2004-08-24 16:58:27 -07:00
+++ b/net/sched/sch_netem.c	2004-08-24 16:58:27 -07:00
@@ -795,37 +795,17 @@
 static int netem_change(struct Qdisc *sch, struct rtattr *opt)
 {
 	struct netem_sched_data *q = qdisc_priv(sch);
-	struct tc_netem_qopt *qopt = RTA_DATA(opt);
-	struct Qdisc *child;
-	int ret;
+	const struct tc_netem_qopt *qopt = RTA_DATA(opt);
 
 	if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
 		return -EINVAL;
 
-	child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
-	if (!child)
-		return -EINVAL;
-
-	ret = set_fifo_limit(child, qopt->limit);
-	if (ret) {
-		qdisc_destroy(child);
-		return ret;
-	}
-
-	sch_tree_lock(sch);
-	if (child) {
-		child = xchg(&q->qdisc, child);
-		if (child != &noop_qdisc)
-			qdisc_destroy(child);
-	
-		q->latency = qopt->latency;
-		q->jitter = qopt->jitter;
-		q->limit = qopt->limit;
-		q->gap = qopt->gap;
-		q->loss = qopt->loss;
-		q->duplicate = qopt->duplicate;
-	}
-	sch_tree_unlock(sch);
+	q->latency = qopt->latency;
+	q->jitter = qopt->jitter;
+	q->limit = qopt->limit;
+	q->gap = qopt->gap;
+	q->loss = qopt->loss;
+	q->duplicate = qopt->duplicate;
 
 	return 0;
 }
@@ -833,19 +813,42 @@
 static int netem_init(struct Qdisc *sch, struct rtattr *opt)
 {
 	struct netem_sched_data *q = qdisc_priv(sch);
+	const struct tc_netem_qopt *qopt;
+	int ret;
 
-	if (!opt)
+	if (!opt || opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
 		return -EINVAL;
 
 	skb_queue_head_init(&q->delayed);
-	q->qdisc = &noop_qdisc;
-
 	init_timer(&q->timer);
 	q->timer.function = netem_watchdog;
 	q->timer.data = (unsigned long) sch;
 	q->counter = 0;
 
-	return netem_change(sch, opt);
+	q->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+	if (!q->qdisc) {
+		pr_debug("netem: qdisc create failed\n");
+		return -ENOMEM;
+	}
+
+	qopt = RTA_DATA(opt);
+	ret = set_fifo_limit(q->qdisc, qopt->limit);
+	if (ret) {
+		pr_debug("netem: can't set fifo limit\n");
+		goto error;
+	}
+
+	ret = netem_change(sch, opt);
+	if (ret) {
+		pr_debug("netem: change failed\n");
+		goto error;
+	}
+
+	return 0;
+
+ error:
+	qdisc_destroy(q->qdisc);
+	return ret;
 }
 
 static void netem_destroy(struct Qdisc *sch)
@@ -862,6 +865,7 @@
 	unsigned char	 *b = skb->tail;
 	struct tc_netem_qopt qopt;
 
+	memset(&qopt, 0, sizeof(qopt));
 	qopt.latency = q->latency;
 	qopt.jitter = q->jitter;
 	qopt.limit = q->limit;

Re: [PATCH 2.6] netem - add correlated random number support

[Stephen Hemminger]

This patch adds correlated random number support (really just a sliding
average).  Like most of this stuff, the concept came from NISTnet.

Dave, this applies after "(4/4) netem - change parameters shouldn't destroy child qdisc"
but before the patch to add loadable distributions, sorry for the confusion.

Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c	2004-08-25 16:14:27 -07:00
+++ b/net/sched/sch_netem.c	2004-08-25 16:14:27 -07:00
@@ -63,6 +63,11 @@
 	u32 gap;
 	u32 jitter;
 	u32 duplicate;
+
+	struct crndstate {
+		unsigned long last;
+		unsigned long rho;
+	} delay_cor, loss_cor, dup_cor;
 };
 
 /* Time stamp put into socket buffer control block */
@@ -70,6 +75,34 @@
 	psched_time_t	time_to_send;
 };
 
+/* init_crandom - initialize correlated random number generator
+ * Use entropy source for initial seed.
+ */
+static void init_crandom(struct crndstate *state, unsigned long rho)
+{
+	state->rho = rho;
+	state->last = net_random();
+}
+
+/* get_crandom - correlated random number generator
+ * Next number depends on last value.
+ * rho is scaled to avoid floating point.
+ */
+static unsigned long get_crandom(struct crndstate *state)
+{
+	u64 value, rho;
+	unsigned long answer;
+
+	if (state->rho == 0)	/* no correllation */
+		return net_random();
+
+	value = net_random();
+	rho = (u64)state->rho + 1;
+	answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
+	state->last = answer;
+	return answer;
+}
+
 /* This is the distribution table for the normal distribution produced
  * with NISTnet tools.
  * The entries represent a scaled inverse of the cumulative distribution
@@ -678,14 +711,14 @@
 	pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
 
 	/* Random packet drop 0 => none, ~0 => all */
-	if (q->loss && q->loss >= net_random()) {
+	if (q->loss && q->loss >= get_crandom(&q->loss_cor)) {
 		pr_debug("netem_enqueue: random loss\n");
 		sch->stats.drops++;
 		return 0;	/* lie about loss so TCP doesn't know */
 	}
 
 	/* Random duplication */
-	if (q->duplicate && q->duplicate >= net_random()) {
+	if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor)) {
 		struct sk_buff *skb2 = skb_clone(skb, GFP_ATOMIC);
 
 		pr_debug("netem_enqueue: dup %p\n", skb2);
@@ -807,6 +840,10 @@
 	q->loss = qopt->loss;
 	q->duplicate = qopt->duplicate;
 
+	init_crandom(&q->delay_cor, qopt->delay_corr);
+	init_crandom(&q->loss_cor, qopt->loss_corr);
+	init_crandom(&q->dup_cor, qopt->dup_corr);
+
 	return 0;
 }
 
@@ -872,6 +909,9 @@
 	qopt.loss = q->loss;
 	qopt.gap = q->gap;
 	qopt.duplicate = q->duplicate;
+	qopt.delay_corr = q->delay_cor.rho;
+	qopt.loss_corr = q->loss_cor.rho;
+	qopt.dup_corr = q->dup_cor.rho;
 
 	RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
 

Re: [PATCH 2.6] netem - add correlated random number support

[David S. Miller]

On Wed, 25 Aug 2004 16:15:35 -0700
Stephen Hemminger <shemminger@osdl.org> wrote:

> Dave, this applies after "(4/4) netem - change parameters shouldn't destroy child qdisc"
> but before the patch to add loadable distributions, sorry for the confusion.

Just making sure you understand that I've rejected that whole
patch set because of the netem options structure breakage issue.

[PATCH 2.6] netem - configurable distributions

[Stephen Hemminger]

Instead of the hard coded normal distribution, allow the distribution
table to be loaded by tc.  The new version of tc/netem loads the data
from a file.

Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c	2004-08-25 11:08:08 -07:00
+++ b/net/sched/sch_netem.c	2004-08-25 11:08:08 -07:00
@@ -63,6 +63,12 @@
 	u32 gap;
 	u32 jitter;
 	u32 duplicate;
+	
+	struct dtable {
+		u32 size;
+		struct rcu_head rcu;
+		s16 table[0]; 
+	} *distribution;
 
 	struct crndstate {
 		unsigned long last;
@@ -103,556 +109,35 @@
 	return answer;
 }
 
-/* This is the distribution table for the normal distribution produced
- * with NISTnet tools.
- * The entries represent a scaled inverse of the cumulative distribution
- * function.
- */
-#define TABLESIZE	2048
-#define TABLEFACTOR	8192
-
-static const short disttable[TABLESIZE] = {
-	-31473,		-26739,		-25226,		-24269,
-	-23560,		-22993,		-22518,		-22109,
-	-21749,		-21426,		-21133,		-20865,
-	-20618,		-20389,		-20174,		-19972,
-	-19782,		-19601,		-19430,		-19267,
-	-19112,		-18962,		-18819,		-18681,
-	-18549,		-18421,		-18298,		-18178,
-	-18062,		-17950,		-17841,		-17735,
-	-17632,		-17532,		-17434,		-17339,
-	-17245,		-17155,		-17066,		-16979,
-	-16894,		-16811,		-16729,		-16649,
-	-16571,		-16494,		-16419,		-16345,
-	-16272,		-16201,		-16130,		-16061,
-	-15993,		-15926,		-15861,		-15796,
-	-15732,		-15669,		-15607,		-15546,
-	-15486,		-15426,		-15368,		-15310,
-	-15253,		-15196,		-15140,		-15086,
-	-15031,		-14977,		-14925,		-14872,
-	-14821,		-14769,		-14719,		-14669,
-	-14619,		-14570,		-14522,		-14473,
-	-14426,		-14379,		-14332,		-14286,
-	-14241,		-14196,		-14150,		-14106,
-	-14062,		-14019,		-13976,		-13933,
-	-13890,		-13848,		-13807,		-13765,
-	-13724,		-13684,		-13643,		-13604,
-	-13564,		-13525,		-13486,		-13447,
-	-13408,		-13370,		-13332,		-13295,
-	-13258,		-13221,		-13184,		-13147,
-	-13111,		-13075,		-13040,		-13004,
-	-12969,		-12934,		-12899,		-12865,
-	-12830,		-12796,		-12762,		-12729,
-	-12695,		-12662,		-12629,		-12596,
-	-12564,		-12531,		-12499,		-12467,
-	-12435,		-12404,		-12372,		-12341,
-	-12310,		-12279,		-12248,		-12218,
-	-12187,		-12157,		-12127,		-12097,
-	-12067,		-12038,		-12008,		-11979,
-	-11950,		-11921,		-11892,		-11863,
-	-11835,		-11806,		-11778,		-11750,
-	-11722,		-11694,		-11666,		-11639,
-	-11611,		-11584,		-11557,		-11530,
-	-11503,		-11476,		-11450,		-11423,
-	-11396,		-11370,		-11344,		-11318,
-	-11292,		-11266,		-11240,		-11214,
-	-11189,		-11164,		-11138,		-11113,
-	-11088,		-11063,		-11038,		-11013,
-	-10988,		-10964,		-10939,		-10915,
-	-10891,		-10866,		-10843,		-10818,
-	-10794,		-10770,		-10747,		-10723,
-	-10700,		-10676,		-10652,		-10630,
-	-10606,		-10583,		-10560,		-10537,
-	-10514,		-10491,		-10469,		-10446,
-	-10424,		-10401,		-10378,		-10356,
-	-10334,		-10312,		-10290,		-10267,
-	-10246,		-10224,		-10202,		-10180,
-	-10158,		-10137,		-10115,		-10094,
-	-10072,		-10051,		-10030,		-10009,
-	-9988,		-9967,		-9945,		-9925,
-	-9904,		-9883,		-9862,		-9842,
-	-9821,		-9800,		-9780,		-9760,
-	-9739,		-9719,		-9699,		-9678,
-	-9658,		-9638,		-9618,		-9599,
-	-9578,		-9559,		-9539,		-9519,
-	-9499,		-9480,		-9461,		-9441,
-	-9422,		-9402,		-9383,		-9363,
-	-9344,		-9325,		-9306,		-9287,
-	-9268,		-9249,		-9230,		-9211,
-	-9192,		-9173,		-9155,		-9136,
-	-9117,		-9098,		-9080,		-9062,
-	-9043,		-9025,		-9006,		-8988,
-	-8970,		-8951,		-8933,		-8915,
-	-8897,		-8879,		-8861,		-8843,
-	-8825,		-8807,		-8789,		-8772,
-	-8754,		-8736,		-8718,		-8701,
-	-8683,		-8665,		-8648,		-8630,
-	-8613,		-8595,		-8578,		-8561,
-	-8543,		-8526,		-8509,		-8492,
-	-8475,		-8458,		-8441,		-8423,
-	-8407,		-8390,		-8373,		-8356,
-	-8339,		-8322,		-8305,		-8289,
-	-8272,		-8255,		-8239,		-8222,
-	-8206,		-8189,		-8172,		-8156,
-	-8140,		-8123,		-8107,		-8090,
-	-8074,		-8058,		-8042,		-8025,
-	-8009,		-7993,		-7977,		-7961,
-	-7945,		-7929,		-7913,		-7897,
-	-7881,		-7865,		-7849,		-7833,
-	-7817,		-7802,		-7786,		-7770,
-	-7754,		-7739,		-7723,		-7707,
-	-7692,		-7676,		-7661,		-7645,
-	-7630,		-7614,		-7599,		-7583,
-	-7568,		-7553,		-7537,		-7522,
-	-7507,		-7492,		-7476,		-7461,
-	-7446,		-7431,		-7416,		-7401,
-	-7385,		-7370,		-7356,		-7340,
-	-7325,		-7311,		-7296,		-7281,
-	-7266,		-7251,		-7236,		-7221,
-	-7207,		-7192,		-7177,		-7162,
-	-7148,		-7133,		-7118,		-7104,
-	-7089,		-7075,		-7060,		-7046,
-	-7031,		-7016,		-7002,		-6988,
-	-6973,		-6959,		-6944,		-6930,
-	-6916,		-6901,		-6887,		-6873,
-	-6859,		-6844,		-6830,		-6816,
-	-6802,		-6788,		-6774,		-6760,
-	-6746,		-6731,		-6717,		-6704,
-	-6690,		-6675,		-6661,		-6647,
-	-6633,		-6620,		-6606,		-6592,
-	-6578,		-6564,		-6550,		-6537,
-	-6523,		-6509,		-6495,		-6482,
-	-6468,		-6454,		-6441,		-6427,
-	-6413,		-6400,		-6386,		-6373,
-	-6359,		-6346,		-6332,		-6318,
-	-6305,		-6291,		-6278,		-6264,
-	-6251,		-6238,		-6224,		-6211,
-	-6198,		-6184,		-6171,		-6158,
-	-6144,		-6131,		-6118,		-6105,
-	-6091,		-6078,		-6065,		-6052,
-	-6039,		-6025,		-6012,		-5999,
-	-5986,		-5973,		-5960,		-5947,
-	-5934,		-5921,		-5908,		-5895,
-	-5882,		-5869,		-5856,		-5843,
-	-5830,		-5817,		-5804,		-5791,
-	-5779,		-5766,		-5753,		-5740,
-	-5727,		-5714,		-5702,		-5689,
-	-5676,		-5663,		-5650,		-5638,
-	-5625,		-5612,		-5600,		-5587,
-	-5575,		-5562,		-5549,		-5537,
-	-5524,		-5512,		-5499,		-5486,
-	-5474,		-5461,		-5449,		-5436,
-	-5424,		-5411,		-5399,		-5386,
-	-5374,		-5362,		-5349,		-5337,
-	-5324,		-5312,		-5299,		-5287,
-	-5275,		-5263,		-5250,		-5238,
-	-5226,		-5213,		-5201,		-5189,
-	-5177,		-5164,		-5152,		-5140,
-	-5128,		-5115,		-5103,		-5091,
-	-5079,		-5067,		-5055,		-5043,
-	-5030,		-5018,		-5006,		-4994,
-	-4982,		-4970,		-4958,		-4946,
-	-4934,		-4922,		-4910,		-4898,
-	-4886,		-4874,		-4862,		-4850,
-	-4838,		-4826,		-4814,		-4803,
-	-4791,		-4778,		-4767,		-4755,
-	-4743,		-4731,		-4719,		-4708,
-	-4696,		-4684,		-4672,		-4660,
-	-4649,		-4637,		-4625,		-4613,
-	-4601,		-4590,		-4578,		-4566,
-	-4554,		-4543,		-4531,		-4520,
-	-4508,		-4496,		-4484,		-4473,
-	-4461,		-4449,		-4438,		-4427,
-	-4415,		-4403,		-4392,		-4380,
-	-4368,		-4357,		-4345,		-4334,
-	-4322,		-4311,		-4299,		-4288,
-	-4276,		-4265,		-4253,		-4242,
-	-4230,		-4219,		-4207,		-4196,
-	-4184,		-4173,		-4162,		-4150,
-	-4139,		-4128,		-4116,		-4105,
-	-4094,		-4082,		-4071,		-4060,
-	-4048,		-4037,		-4026,		-4014,
-	-4003,		-3992,		-3980,		-3969,
-	-3958,		-3946,		-3935,		-3924,
-	-3913,		-3901,		-3890,		-3879,
-	-3868,		-3857,		-3845,		-3834,
-	-3823,		-3812,		-3801,		-3790,
-	-3779,		-3767,		-3756,		-3745,
-	-3734,		-3723,		-3712,		-3700,
-	-3689,		-3678,		-3667,		-3656,
-	-3645,		-3634,		-3623,		-3612,
-	-3601,		-3590,		-3579,		-3568,
-	-3557,		-3545,		-3535,		-3524,
-	-3513,		-3502,		-3491,		-3480,
-	-3469,		-3458,		-3447,		-3436,
-	-3425,		-3414,		-3403,		-3392,
-	-3381,		-3370,		-3360,		-3348,
-	-3337,		-3327,		-3316,		-3305,
-	-3294,		-3283,		-3272,		-3262,
-	-3251,		-3240,		-3229,		-3218,
-	-3207,		-3197,		-3185,		-3175,
-	-3164,		-3153,		-3142,		-3132,
-	-3121,		-3110,		-3099,		-3088,
-	-3078,		-3067,		-3056,		-3045,
-	-3035,		-3024,		-3013,		-3003,
-	-2992,		-2981,		-2970,		-2960,
-	-2949,		-2938,		-2928,		-2917,
-	-2906,		-2895,		-2885,		-2874,
-	-2864,		-2853,		-2842,		-2832,
-	-2821,		-2810,		-2800,		-2789,
-	-2778,		-2768,		-2757,		-2747,
-	-2736,		-2725,		-2715,		-2704,
-	-2694,		-2683,		-2673,		-2662,
-	-2651,		-2641,		-2630,		-2620,
-	-2609,		-2599,		-2588,		-2578,
-	-2567,		-2556,		-2546,		-2535,
-	-2525,		-2515,		-2504,		-2493,
-	-2483,		-2472,		-2462,		-2451,
-	-2441,		-2431,		-2420,		-2410,
-	-2399,		-2389,		-2378,		-2367,
-	-2357,		-2347,		-2336,		-2326,
-	-2315,		-2305,		-2295,		-2284,
-	-2274,		-2263,		-2253,		-2243,
-	-2232,		-2222,		-2211,		-2201,
-	-2191,		-2180,		-2170,		-2159,
-	-2149,		-2139,		-2128,		-2118,
-	-2107,		-2097,		-2087,		-2076,
-	-2066,		-2056,		-2046,		-2035,
-	-2025,		-2014,		-2004,		-1994,
-	-1983,		-1973,		-1963,		-1953,
-	-1942,		-1932,		-1921,		-1911,
-	-1901,		-1891,		-1880,		-1870,
-	-1860,		-1849,		-1839,		-1829,
-	-1819,		-1808,		-1798,		-1788,
-	-1778,		-1767,		-1757,		-1747,
-	-1736,		-1726,		-1716,		-1706,
-	-1695,		-1685,		-1675,		-1665,
-	-1654,		-1644,		-1634,		-1624,
-	-1613,		-1603,		-1593,		-1583,
-	-1573,		-1563,		-1552,		-1542,
-	-1532,		-1522,		-1511,		-1501,
-	-1491,		-1481,		-1471,		-1461,
-	-1450,		-1440,		-1430,		-1420,
-	-1409,		-1400,		-1389,		-1379,
-	-1369,		-1359,		-1348,		-1339,
-	-1328,		-1318,		-1308,		-1298,
-	-1288,		-1278,		-1267,		-1257,
-	-1247,		-1237,		-1227,		-1217,
-	-1207,		-1196,		-1186,		-1176,
-	-1166,		-1156,		-1146,		-1135,
-	-1126,		-1115,		-1105,		-1095,
-	-1085,		-1075,		-1065,		-1055,
-	-1044,		-1034,		-1024,		-1014,
-	-1004,		-994,		-984,		-974,
-	-964,		-954,		-944,		-933,
-	-923,		-913,		-903,		-893,
-	-883,		-873,		-863,		-853,
-	-843,		-833,		-822,		-812,
-	-802,		-792,		-782,		-772,
-	-762,		-752,		-742,		-732,
-	-722,		-712,		-702,		-691,
-	-682,		-671,		-662,		-651,
-	-641,		-631,		-621,		-611,
-	-601,		-591,		-581,		-571,
-	-561,		-551,		-541,		-531,
-	-521,		-511,		-501,		-491,
-	-480,		-471,		-460,		-451,
-	-440,		-430,		-420,		-410,
-	-400,		-390,		-380,		-370,
-	-360,		-350,		-340,		-330,
-	-320,		-310,		-300,		-290,
-	-280,		-270,		-260,		-250,
-	-240,		-230,		-220,		-210,
-	-199,		-190,		-179,		-170,
-	-159,		-150,		-139,		-129,
-	-119,		-109,		-99,		-89,
-	-79,		-69,		-59,		-49,
-	-39,		-29,		-19,		-9,
-	1,		11,		21,		31,
-	41,		51,		61,		71,
-	81,		91,		101,		111,
-	121,		131,		141,		152,
-	161,		172,		181,		192,
-	202,		212,		222,		232,
-	242,		252,		262,		272,
-	282,		292,		302,		312,
-	322,		332,		342,		352,
-	362,		372,		382,		392,
-	402,		412,		422,		433,
-	442,		453,		462,		473,
-	483,		493,		503,		513,
-	523,		533,		543,		553,
-	563,		573,		583,		593,
-	603,		613,		623,		633,
-	643,		653,		664,		673,
-	684,		694,		704,		714,
-	724,		734,		744,		754,
-	764,		774,		784,		794,
-	804,		815,		825,		835,
-	845,		855,		865,		875,
-	885,		895,		905,		915,
-	925,		936,		946,		956,
-	966,		976,		986,		996,
-	1006,		1016,		1026,		1037,
-	1047,		1057,		1067,		1077,
-	1087,		1097,		1107,		1117,
-	1128,		1138,		1148,		1158,
-	1168,		1178,		1188,		1198,
-	1209,		1219,		1229,		1239,
-	1249,		1259,		1269,		1280,
-	1290,		1300,		1310,		1320,
-	1330,		1341,		1351,		1361,
-	1371,		1381,		1391,		1402,
-	1412,		1422,		1432,		1442,
-	1452,		1463,		1473,		1483,
-	1493,		1503,		1513,		1524,
-	1534,		1544,		1554,		1565,
-	1575,		1585,		1595,		1606,
-	1616,		1626,		1636,		1647,
-	1656,		1667,		1677,		1687,
-	1697,		1708,		1718,		1729,
-	1739,		1749,		1759,		1769,
-	1780,		1790,		1800,		1810,
-	1821,		1831,		1841,		1851,
-	1862,		1872,		1883,		1893,
-	1903,		1913,		1923,		1934,
-	1944,		1955,		1965,		1975,
-	1985,		1996,		2006,		2016,
-	2027,		2037,		2048,		2058,
-	2068,		2079,		2089,		2099,
-	2110,		2120,		2130,		2141,
-	2151,		2161,		2172,		2182,
-	2193,		2203,		2213,		2224,
-	2234,		2245,		2255,		2265,
-	2276,		2286,		2297,		2307,
-	2318,		2328,		2338,		2349,
-	2359,		2370,		2380,		2391,
-	2401,		2412,		2422,		2433,
-	2443,		2454,		2464,		2475,
-	2485,		2496,		2506,		2517,
-	2527,		2537,		2548,		2559,
-	2569,		2580,		2590,		2601,
-	2612,		2622,		2632,		2643,
-	2654,		2664,		2675,		2685,
-	2696,		2707,		2717,		2728,
-	2738,		2749,		2759,		2770,
-	2781,		2791,		2802,		2813,
-	2823,		2834,		2845,		2855,
-	2866,		2877,		2887,		2898,
-	2909,		2919,		2930,		2941,
-	2951,		2962,		2973,		2984,
-	2994,		3005,		3015,		3027,
-	3037,		3048,		3058,		3069,
-	3080,		3091,		3101,		3113,
-	3123,		3134,		3145,		3156,
-	3166,		3177,		3188,		3199,
-	3210,		3220,		3231,		3242,
-	3253,		3264,		3275,		3285,
-	3296,		3307,		3318,		3329,
-	3340,		3351,		3362,		3373,
-	3384,		3394,		3405,		3416,
-	3427,		3438,		3449,		3460,
-	3471,		3482,		3493,		3504,
-	3515,		3526,		3537,		3548,
-	3559,		3570,		3581,		3592,
-	3603,		3614,		3625,		3636,
-	3647,		3659,		3670,		3681,
-	3692,		3703,		3714,		3725,
-	3736,		3747,		3758,		3770,
-	3781,		3792,		3803,		3814,
-	3825,		3837,		3848,		3859,
-	3870,		3881,		3893,		3904,
-	3915,		3926,		3937,		3949,
-	3960,		3971,		3983,		3994,
-	4005,		4017,		4028,		4039,
-	4051,		4062,		4073,		4085,
-	4096,		4107,		4119,		4130,
-	4141,		4153,		4164,		4175,
-	4187,		4198,		4210,		4221,
-	4233,		4244,		4256,		4267,
-	4279,		4290,		4302,		4313,
-	4325,		4336,		4348,		4359,
-	4371,		4382,		4394,		4406,
-	4417,		4429,		4440,		4452,
-	4464,		4475,		4487,		4499,
-	4510,		4522,		4533,		4545,
-	4557,		4569,		4581,		4592,
-	4604,		4616,		4627,		4639,
-	4651,		4663,		4674,		4686,
-	4698,		4710,		4722,		4734,
-	4746,		4758,		4769,		4781,
-	4793,		4805,		4817,		4829,
-	4841,		4853,		4865,		4877,
-	4889,		4900,		4913,		4925,
-	4936,		4949,		4961,		4973,
-	4985,		4997,		5009,		5021,
-	5033,		5045,		5057,		5070,
-	5081,		5094,		5106,		5118,
-	5130,		5143,		5155,		5167,
-	5179,		5191,		5204,		5216,
-	5228,		5240,		5253,		5265,
-	5278,		5290,		5302,		5315,
-	5327,		5340,		5352,		5364,
-	5377,		5389,		5401,		5414,
-	5426,		5439,		5451,		5464,
-	5476,		5489,		5502,		5514,
-	5527,		5539,		5552,		5564,
-	5577,		5590,		5603,		5615,
-	5628,		5641,		5653,		5666,
-	5679,		5691,		5704,		5717,
-	5730,		5743,		5756,		5768,
-	5781,		5794,		5807,		5820,
-	5833,		5846,		5859,		5872,
-	5885,		5897,		5911,		5924,
-	5937,		5950,		5963,		5976,
-	5989,		6002,		6015,		6028,
-	6042,		6055,		6068,		6081,
-	6094,		6108,		6121,		6134,
-	6147,		6160,		6174,		6187,
-	6201,		6214,		6227,		6241,
-	6254,		6267,		6281,		6294,
-	6308,		6321,		6335,		6348,
-	6362,		6375,		6389,		6403,
-	6416,		6430,		6443,		6457,
-	6471,		6485,		6498,		6512,
-	6526,		6540,		6554,		6567,
-	6581,		6595,		6609,		6623,
-	6637,		6651,		6665,		6679,
-	6692,		6706,		6721,		6735,
-	6749,		6763,		6777,		6791,
-	6805,		6819,		6833,		6848,
-	6862,		6876,		6890,		6905,
-	6919,		6933,		6948,		6962,
-	6976,		6991,		7005,		7020,
-	7034,		7049,		7064,		7078,
-	7093,		7107,		7122,		7136,
-	7151,		7166,		7180,		7195,
-	7210,		7225,		7240,		7254,
-	7269,		7284,		7299,		7314,
-	7329,		7344,		7359,		7374,
-	7389,		7404,		7419,		7434,
-	7449,		7465,		7480,		7495,
-	7510,		7526,		7541,		7556,
-	7571,		7587,		7602,		7618,
-	7633,		7648,		7664,		7680,
-	7695,		7711,		7726,		7742,
-	7758,		7773,		7789,		7805,
-	7821,		7836,		7852,		7868,
-	7884,		7900,		7916,		7932,
-	7948,		7964,		7981,		7997,
-	8013,		8029,		8045,		8061,
-	8078,		8094,		8110,		8127,
-	8143,		8160,		8176,		8193,
-	8209,		8226,		8242,		8259,
-	8276,		8292,		8309,		8326,
-	8343,		8360,		8377,		8394,
-	8410,		8428,		8444,		8462,
-	8479,		8496,		8513,		8530,
-	8548,		8565,		8582,		8600,
-	8617,		8634,		8652,		8670,
-	8687,		8704,		8722,		8740,
-	8758,		8775,		8793,		8811,
-	8829,		8847,		8865,		8883,
-	8901,		8919,		8937,		8955,
-	8974,		8992,		9010,		9029,
-	9047,		9066,		9084,		9103,
-	9121,		9140,		9159,		9177,
-	9196,		9215,		9234,		9253,
-	9272,		9291,		9310,		9329,
-	9349,		9368,		9387,		9406,
-	9426,		9445,		9465,		9484,
-	9504,		9524,		9544,		9563,
-	9583,		9603,		9623,		9643,
-	9663,		9683,		9703,		9723,
-	9744,		9764,		9785,		9805,
-	9826,		9846,		9867,		9888,
-	9909,		9930,		9950,		9971,
-	9993,		10013,		10035,		10056,
-	10077,		10099,		10120,		10142,
-	10163,		10185,		10207,		10229,
-	10251,		10273,		10294,		10317,
-	10339,		10361,		10384,		10406,
-	10428,		10451,		10474,		10496,
-	10519,		10542,		10565,		10588,
-	10612,		10635,		10658,		10682,
-	10705,		10729,		10752,		10776,
-	10800,		10824,		10848,		10872,
-	10896,		10921,		10945,		10969,
-	10994,		11019,		11044,		11069,
-	11094,		11119,		11144,		11169,
-	11195,		11221,		11246,		11272,
-	11298,		11324,		11350,		11376,
-	11402,		11429,		11456,		11482,
-	11509,		11536,		11563,		11590,
-	11618,		11645,		11673,		11701,
-	11728,		11756,		11785,		11813,
-	11842,		11870,		11899,		11928,
-	11957,		11986,		12015,		12045,
-	12074,		12104,		12134,		12164,
-	12194,		12225,		12255,		12286,
-	12317,		12348,		12380,		12411,
-	12443,		12475,		12507,		12539,
-	12571,		12604,		12637,		12670,
-	12703,		12737,		12771,		12804,
-	12839,		12873,		12907,		12942,
-	12977,		13013,		13048,		13084,
-	13120,		13156,		13192,		13229,
-	13267,		13304,		13341,		13379,
-	13418,		13456,		13495,		13534,
-	13573,		13613,		13653,		13693,
-	13734,		13775,		13817,		13858,
-	13901,		13943,		13986,		14029,
-	14073,		14117,		14162,		14206,
-	14252,		14297,		14343,		14390,
-	14437,		14485,		14533,		14582,
-	14631,		14680,		14731,		14782,
-	14833,		14885,		14937,		14991,
-	15044,		15099,		15154,		15210,
-	15266,		15324,		15382,		15441,
-	15500,		15561,		15622,		15684,
-	15747,		15811,		15877,		15943,
-	16010,		16078,		16148,		16218,
-	16290,		16363,		16437,		16513,
-	16590,		16669,		16749,		16831,
-	16915,		17000,		17088,		17177,
-	17268,		17362,		17458,		17556,
-	17657,		17761,		17868,		17977,
-	18090,		18207,		18328,		18452,
-	18581,		18715,		18854,		18998,
-	19149,		19307,		19472,		19645,
-	19828,		20021,		20226,		20444,
-	20678,		20930,		21204,		21503,
-	21835,		22206,		22630,		23124,
-	23721,		24478,		25529,		27316,
-};
-
-/* tabledist - return a pseudo-randomly distributed value with mean mu and
+/* table_dist - return a pseudo-randomly distributed value with mean mu and
  * std deviation sigma.  Uses table lookup to approximate the desired
  * distribution, and a uniformly-distributed pseudo-random source.
  */
-static inline int tabledist(int mu, int sigma)
+static int table_dist(const struct dtable *dist,
+		       struct crndstate *state,
+		       int mu, int sigma)
 {
-	int x;
-	int index;
-	int sigmamod, sigmadiv;
+	int t, x;
+	unsigned long rnd;
 
 	if (sigma == 0)
 		return mu;
+	
+	rnd = get_crandom(state);
 
-	index = (net_random() & (TABLESIZE-1));
-	sigmamod = sigma%TABLEFACTOR;
-	sigmadiv = sigma/TABLEFACTOR;
-	x = sigmamod*disttable[index];
+	/* default uniform distribution */
+	if (dist == NULL)
+		return (rnd % (2*sigma)) - sigma + mu;
+
+	t = dist->table[rnd % dist->size];
+	x = (sigma % TCA_NETEM_TABLEFACTOR) * t;
 
 	if (x >= 0)
-		x += TABLEFACTOR/2;
+		x += TCA_NETEM_TABLEFACTOR/2;
 	else
-		x -= TABLEFACTOR/2;
+		x -= TCA_NETEM_TABLEFACTOR/2;
 
-	x /= TABLEFACTOR;
-	x += sigmadiv*disttable[index];
-	x += mu;
-	return x;
+	return (x + sigma * t)/TCA_NETEM_TABLEFACTOR + mu;
 }
 
 /* Enqueue packets with underlying discipline (fifo)
@@ -683,10 +168,14 @@
 	q->counter = 0;
 	
 	PSCHED_GET_TIME(now);
-	if (q->jitter) 
-		delay = tabledist(q->latency, q->jitter);
-	else
-		delay = q->latency;
+
+	rcu_read_lock();
+	delay = table_dist(rcu_dereference(q->distribution), 
+			   &q->delay_cor, q->latency, q->jitter);
+	rcu_read_unlock();
+
+	pr_debug("netem_enqueue: delay %ld (mu=%u sigma=%u)\n",
+		 delay, q->latency, q->jitter);
 
 	PSCHED_TADD2(now, delay, cb->time_to_send);
 	
@@ -825,13 +314,50 @@
 	return ret;
 }
 
+static struct dtable *new_dtable(int size, const __s16 *data)
+{
+	struct dtable *d;
+	int i;
+
+	d = kmalloc(sizeof(*d) + size*sizeof(d->table[0]), GFP_KERNEL);
+	if (d) {
+		d->size = size;
+		for (i = 0; i < size; i++)
+			d->table[i] = data[i];
+	}
+	return d;
+}
+
+static void dtable_rcu_free(struct rcu_head *rcu)
+{
+	kfree(container_of(rcu, struct dtable, rcu));
+}
+
 static int netem_change(struct Qdisc *sch, struct rtattr *opt)
 {
 	struct netem_sched_data *q = qdisc_priv(sch);
 	const struct tc_netem_qopt *qopt = RTA_DATA(opt);
+	long data_size = opt->rta_len - RTA_LENGTH(sizeof(*qopt));
+	struct dtable *dt;
+	
+	if (data_size < 0) {
+		pr_debug("netem: requested options < current api\n");
+		return -EINVAL;
+	}
 
-	if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
+	data_size /= sizeof(qopt->delay_dist[0]);
+	if (data_size > 16384) {
+		pr_debug("netem: bad distribution data size\n");
 		return -EINVAL;
+	}
+
+	if (data_size > 0) {
+		dt = new_dtable(data_size, qopt->delay_dist);
+		if (!dt)
+			return -ENOMEM;
+	} else
+		dt = NULL;
+
 
 	q->latency = qopt->latency;
 	q->jitter = qopt->jitter;
@@ -840,6 +366,11 @@
 	q->loss = qopt->loss;
 	q->duplicate = qopt->duplicate;
 
+	/* handle race with enqueue and change? */
+	dt = xchg(&q->distribution, dt);
+	if (dt) 
+		call_rcu(&dt->rcu, dtable_rcu_free);
+
 	init_crandom(&q->delay_cor, qopt->delay_corr);
 	init_crandom(&q->loss_cor, qopt->loss_corr);
 	init_crandom(&q->dup_cor, qopt->dup_corr);
@@ -861,7 +392,8 @@
 	q->timer.function = netem_watchdog;
 	q->timer.data = (unsigned long) sch;
 	q->counter = 0;
-
+	q->distribution = NULL;
+	
 	q->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
 	if (!q->qdisc) {
 		pr_debug("netem: qdisc create failed\n");
@@ -893,12 +425,14 @@
 	struct netem_sched_data *q = qdisc_priv(sch);
 
 	del_timer_sync(&q->timer);
+	
+	kfree(q->distribution);
 	qdisc_destroy(q->qdisc);
 }
 
 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
 {
-	struct netem_sched_data *q = qdisc_priv(sch);
+	const struct netem_sched_data *q = qdisc_priv(sch);
 	unsigned char	 *b = skb->tail;
 	struct tc_netem_qopt qopt;
 
@@ -913,6 +447,7 @@
 	qopt.loss_corr = q->loss_cor.rho;
 	qopt.dup_corr = q->dup_cor.rho;
 
+	/* don't dump out distribution table */
 	RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
 
 	return skb->len;

[PATCH 2.4] netem -- update to match new 2.6 version

[Stephen Hemminger]

This combines the previous 5 changes to netem for 2.6 to
support duplication, correlation and distribution tables.

Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

diff -Nru a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
--- a/include/linux/pkt_sched.h	2004-08-25 13:46:01 -07:00
+++ b/include/linux/pkt_sched.h	2004-08-25 13:46:01 -07:00
@@ -432,7 +432,8 @@
 
 #define TCA_ATM_MAX	TCA_ATM_STATE
 
-/* Network emulator */
+/* Network section */
+
 struct tc_netem_qopt
 {
 	__u32	latency;	/* added delay (us) */
@@ -440,7 +441,14 @@
 	__u32	loss;		/* random packet loss (0=none ~0=100%) */
 	__u32	gap;		/* re-ordering gap (0 for delay all) */
 	__u32   duplicate;	/* random packet dup  (0=none ~0=100%) */
-	__u32	jitter;		/* random jitter in latency (us) */
+	__u32	jitter;		/* delay sigma (us) */
+
+	__u32	delay_corr;	/* delay correllation (0=none ~0=100%) */
+	__u32	loss_corr;	/* packet loss correllation (0=none ~0=100%) */
+	__u32	dup_corr;	/* duplicate correlation (0=none ~0=100%) */
+
+	__s16	delay_dist[0];	/* delay distribution table (optional) */
+#define TCA_NETEM_TABLEFACTOR	8192
 };
 
 #endif
diff -Nru a/net/sched/sch_netem.c b/net/sched/sch_netem.c
--- a/net/sched/sch_netem.c	2004-08-25 13:46:01 -07:00
+++ b/net/sched/sch_netem.c	2004-08-25 13:46:01 -07:00
@@ -6,6 +6,9 @@
  * 		as published by the Free Software Foundation; either version
  * 		2 of the License, or (at your option) any later version.
  *
+ *  		Many of the algorithms and ideas for this came from
+ *		NIST Net which is not copyrighted. 
+ *
  * Authors:	Stephen Hemminger <shemminger@osdl.org>
  *		Catalin(ux aka Dino) BOIE <catab at umbrella dot ro>
  */
@@ -23,11 +26,31 @@
 
 #include <net/pkt_sched.h>
 
-/*	Network emulator
- *
- *	This scheduler can alters spacing and order
- *	Similar to NISTnet and BSD Dummynet.
- */
+/*	Network Emulation Queuing algorithm.
+	====================================
+
+	Sources: [1] Mark Carson, Darrin Santay, "NIST Net - A Linux-based
+		 Network Emulation Tool
+		 [2] Luigi Rizzo, DummyNet for FreeBSD
+
+	 ----------------------------------------------------------------
+
+	 This started out as a simple way to delay outgoing packets to
+	 test TCP but has grown to include most of the functionality
+	 of a full blown network emulator like NISTnet. It can delay
+	 packets and add random jitter (and correlation). The random
+	 distribution can be loaded from a table as well to provide
+	 normal, Pareto, or experimental curves. Packet loss,
+	 duplication, and reordering can also be emulated.
+
+	 This qdisc does not do classification that can be handled in
+	 layering other disciplines.  It does not need to do bandwidth
+	 control either since that can be handled by using token
+	 bucket or other rate control.
+
+	 The simulator is limited by the Linux timer resolution
+	 and will create packet bursts on the HZ boundary (1ms).
+*/
 
 struct netem_sched_data {
 	struct Qdisc	*qdisc;
@@ -40,6 +63,17 @@
 	u32 counter;
 	u32 gap;
 	u32 jitter;
+	u32 duplicate;
+	
+	struct dtable {
+		u32 size;
+		s16 table[0]; 
+	} *distribution;
+
+	struct crndstate {
+		unsigned long last;
+		unsigned long rho;
+	} delay_cor, loss_cor, dup_cor;
 };
 
 /* Time stamp put into socket buffer control block */
@@ -47,577 +81,75 @@
 	psched_time_t	time_to_send;
 };
 
-/* This is the distribution table for the normal distribution produced
- * with NISTnet tools.
- * The entries represent a scaled inverse of the cumulative distribution
- * function.
+/* init_crandom - initialize correlated random number generator
+ * Use entropy source for initial seed.
  */
-#define TABLESIZE	2048
-#define TABLEFACTOR	8192
+static void init_crandom(struct crndstate *state, unsigned long rho)
+{
+	state->rho = rho;
+	state->last = net_random();
+}
 
-static const short disttable[TABLESIZE] = {
-	-31473,		-26739,		-25226,		-24269,
-	-23560,		-22993,		-22518,		-22109,
-	-21749,		-21426,		-21133,		-20865,
-	-20618,		-20389,		-20174,		-19972,
-	-19782,		-19601,		-19430,		-19267,
-	-19112,		-18962,		-18819,		-18681,
-	-18549,		-18421,		-18298,		-18178,
-	-18062,		-17950,		-17841,		-17735,
-	-17632,		-17532,		-17434,		-17339,
-	-17245,		-17155,		-17066,		-16979,
-	-16894,		-16811,		-16729,		-16649,
-	-16571,		-16494,		-16419,		-16345,
-	-16272,		-16201,		-16130,		-16061,
-	-15993,		-15926,		-15861,		-15796,
-	-15732,		-15669,		-15607,		-15546,
-	-15486,		-15426,		-15368,		-15310,
-	-15253,		-15196,		-15140,		-15086,
-	-15031,		-14977,		-14925,		-14872,
-	-14821,		-14769,		-14719,		-14669,
-	-14619,		-14570,		-14522,		-14473,
-	-14426,		-14379,		-14332,		-14286,
-	-14241,		-14196,		-14150,		-14106,
-	-14062,		-14019,		-13976,		-13933,
-	-13890,		-13848,		-13807,		-13765,
-	-13724,		-13684,		-13643,		-13604,
-	-13564,		-13525,		-13486,		-13447,
-	-13408,		-13370,		-13332,		-13295,
-	-13258,		-13221,		-13184,		-13147,
-	-13111,		-13075,		-13040,		-13004,
-	-12969,		-12934,		-12899,		-12865,
-	-12830,		-12796,		-12762,		-12729,
-	-12695,		-12662,		-12629,		-12596,
-	-12564,		-12531,		-12499,		-12467,
-	-12435,		-12404,		-12372,		-12341,
-	-12310,		-12279,		-12248,		-12218,
-	-12187,		-12157,		-12127,		-12097,
-	-12067,		-12038,		-12008,		-11979,
-	-11950,		-11921,		-11892,		-11863,
-	-11835,		-11806,		-11778,		-11750,
-	-11722,		-11694,		-11666,		-11639,
-	-11611,		-11584,		-11557,		-11530,
-	-11503,		-11476,		-11450,		-11423,
-	-11396,		-11370,		-11344,		-11318,
-	-11292,		-11266,		-11240,		-11214,
-	-11189,		-11164,		-11138,		-11113,
-	-11088,		-11063,		-11038,		-11013,
-	-10988,		-10964,		-10939,		-10915,
-	-10891,		-10866,		-10843,		-10818,
-	-10794,		-10770,		-10747,		-10723,
-	-10700,		-10676,		-10652,		-10630,
-	-10606,		-10583,		-10560,		-10537,
-	-10514,		-10491,		-10469,		-10446,
-	-10424,		-10401,		-10378,		-10356,
-	-10334,		-10312,		-10290,		-10267,
-	-10246,		-10224,		-10202,		-10180,
-	-10158,		-10137,		-10115,		-10094,
-	-10072,		-10051,		-10030,		-10009,
-	-9988,		-9967,		-9945,		-9925,
-	-9904,		-9883,		-9862,		-9842,
-	-9821,		-9800,		-9780,		-9760,
-	-9739,		-9719,		-9699,		-9678,
-	-9658,		-9638,		-9618,		-9599,
-	-9578,		-9559,		-9539,		-9519,
-	-9499,		-9480,		-9461,		-9441,
-	-9422,		-9402,		-9383,		-9363,
-	-9344,		-9325,		-9306,		-9287,
-	-9268,		-9249,		-9230,		-9211,
-	-9192,		-9173,		-9155,		-9136,
-	-9117,		-9098,		-9080,		-9062,
-	-9043,		-9025,		-9006,		-8988,
-	-8970,		-8951,		-8933,		-8915,
-	-8897,		-8879,		-8861,		-8843,
-	-8825,		-8807,		-8789,		-8772,
-	-8754,		-8736,		-8718,		-8701,
-	-8683,		-8665,		-8648,		-8630,
-	-8613,		-8595,		-8578,		-8561,
-	-8543,		-8526,		-8509,		-8492,
-	-8475,		-8458,		-8441,		-8423,
-	-8407,		-8390,		-8373,		-8356,
-	-8339,		-8322,		-8305,		-8289,
-	-8272,		-8255,		-8239,		-8222,
-	-8206,		-8189,		-8172,		-8156,
-	-8140,		-8123,		-8107,		-8090,
-	-8074,		-8058,		-8042,		-8025,
-	-8009,		-7993,		-7977,		-7961,
-	-7945,		-7929,		-7913,		-7897,
-	-7881,		-7865,		-7849,		-7833,
-	-7817,		-7802,		-7786,		-7770,
-	-7754,		-7739,		-7723,		-7707,
-	-7692,		-7676,		-7661,		-7645,
-	-7630,		-7614,		-7599,		-7583,
-	-7568,		-7553,		-7537,		-7522,
-	-7507,		-7492,		-7476,		-7461,
-	-7446,		-7431,		-7416,		-7401,
-	-7385,		-7370,		-7356,		-7340,
-	-7325,		-7311,		-7296,		-7281,
-	-7266,		-7251,		-7236,		-7221,
-	-7207,		-7192,		-7177,		-7162,
-	-7148,		-7133,		-7118,		-7104,
-	-7089,		-7075,		-7060,		-7046,
-	-7031,		-7016,		-7002,		-6988,
-	-6973,		-6959,		-6944,		-6930,
-	-6916,		-6901,		-6887,		-6873,
-	-6859,		-6844,		-6830,		-6816,
-	-6802,		-6788,		-6774,		-6760,
-	-6746,		-6731,		-6717,		-6704,
-	-6690,		-6675,		-6661,		-6647,
-	-6633,		-6620,		-6606,		-6592,
-	-6578,		-6564,		-6550,		-6537,
-	-6523,		-6509,		-6495,		-6482,
-	-6468,		-6454,		-6441,		-6427,
-	-6413,		-6400,		-6386,		-6373,
-	-6359,		-6346,		-6332,		-6318,
-	-6305,		-6291,		-6278,		-6264,
-	-6251,		-6238,		-6224,		-6211,
-	-6198,		-6184,		-6171,		-6158,
-	-6144,		-6131,		-6118,		-6105,
-	-6091,		-6078,		-6065,		-6052,
-	-6039,		-6025,		-6012,		-5999,
-	-5986,		-5973,		-5960,		-5947,
-	-5934,		-5921,		-5908,		-5895,
-	-5882,		-5869,		-5856,		-5843,
-	-5830,		-5817,		-5804,		-5791,
-	-5779,		-5766,		-5753,		-5740,
-	-5727,		-5714,		-5702,		-5689,
-	-5676,		-5663,		-5650,		-5638,
-	-5625,		-5612,		-5600,		-5587,
-	-5575,		-5562,		-5549,		-5537,
-	-5524,		-5512,		-5499,		-5486,
-	-5474,		-5461,		-5449,		-5436,
-	-5424,		-5411,		-5399,		-5386,
-	-5374,		-5362,		-5349,		-5337,
-	-5324,		-5312,		-5299,		-5287,
-	-5275,		-5263,		-5250,		-5238,
-	-5226,		-5213,		-5201,		-5189,
-	-5177,		-5164,		-5152,		-5140,
-	-5128,		-5115,		-5103,		-5091,
-	-5079,		-5067,		-5055,		-5043,
-	-5030,		-5018,		-5006,		-4994,
-	-4982,		-4970,		-4958,		-4946,
-	-4934,		-4922,		-4910,		-4898,
-	-4886,		-4874,		-4862,		-4850,
-	-4838,		-4826,		-4814,		-4803,
-	-4791,		-4778,		-4767,		-4755,
-	-4743,		-4731,		-4719,		-4708,
-	-4696,		-4684,		-4672,		-4660,
-	-4649,		-4637,		-4625,		-4613,
-	-4601,		-4590,		-4578,		-4566,
-	-4554,		-4543,		-4531,		-4520,
-	-4508,		-4496,		-4484,		-4473,
-	-4461,		-4449,		-4438,		-4427,
-	-4415,		-4403,		-4392,		-4380,
-	-4368,		-4357,		-4345,		-4334,
-	-4322,		-4311,		-4299,		-4288,
-	-4276,		-4265,		-4253,		-4242,
-	-4230,		-4219,		-4207,		-4196,
-	-4184,		-4173,		-4162,		-4150,
-	-4139,		-4128,		-4116,		-4105,
-	-4094,		-4082,		-4071,		-4060,
-	-4048,		-4037,		-4026,		-4014,
-	-4003,		-3992,		-3980,		-3969,
-	-3958,		-3946,		-3935,		-3924,
-	-3913,		-3901,		-3890,		-3879,
-	-3868,		-3857,		-3845,		-3834,
-	-3823,		-3812,		-3801,		-3790,
-	-3779,		-3767,		-3756,		-3745,
-	-3734,		-3723,		-3712,		-3700,
-	-3689,		-3678,		-3667,		-3656,
-	-3645,		-3634,		-3623,		-3612,
-	-3601,		-3590,		-3579,		-3568,
-	-3557,		-3545,		-3535,		-3524,
-	-3513,		-3502,		-3491,		-3480,
-	-3469,		-3458,		-3447,		-3436,
-	-3425,		-3414,		-3403,		-3392,
-	-3381,		-3370,		-3360,		-3348,
-	-3337,		-3327,		-3316,		-3305,
-	-3294,		-3283,		-3272,		-3262,
-	-3251,		-3240,		-3229,		-3218,
-	-3207,		-3197,		-3185,		-3175,
-	-3164,		-3153,		-3142,		-3132,
-	-3121,		-3110,		-3099,		-3088,
-	-3078,		-3067,		-3056,		-3045,
-	-3035,		-3024,		-3013,		-3003,
-	-2992,		-2981,		-2970,		-2960,
-	-2949,		-2938,		-2928,		-2917,
-	-2906,		-2895,		-2885,		-2874,
-	-2864,		-2853,		-2842,		-2832,
-	-2821,		-2810,		-2800,		-2789,
-	-2778,		-2768,		-2757,		-2747,
-	-2736,		-2725,		-2715,		-2704,
-	-2694,		-2683,		-2673,		-2662,
-	-2651,		-2641,		-2630,		-2620,
-	-2609,		-2599,		-2588,		-2578,
-	-2567,		-2556,		-2546,		-2535,
-	-2525,		-2515,		-2504,		-2493,
-	-2483,		-2472,		-2462,		-2451,
-	-2441,		-2431,		-2420,		-2410,
-	-2399,		-2389,		-2378,		-2367,
-	-2357,		-2347,		-2336,		-2326,
-	-2315,		-2305,		-2295,		-2284,
-	-2274,		-2263,		-2253,		-2243,
-	-2232,		-2222,		-2211,		-2201,
-	-2191,		-2180,		-2170,		-2159,
-	-2149,		-2139,		-2128,		-2118,
-	-2107,		-2097,		-2087,		-2076,
-	-2066,		-2056,		-2046,		-2035,
-	-2025,		-2014,		-2004,		-1994,
-	-1983,		-1973,		-1963,		-1953,
-	-1942,		-1932,		-1921,		-1911,
-	-1901,		-1891,		-1880,		-1870,
-	-1860,		-1849,		-1839,		-1829,
-	-1819,		-1808,		-1798,		-1788,
-	-1778,		-1767,		-1757,		-1747,
-	-1736,		-1726,		-1716,		-1706,
-	-1695,		-1685,		-1675,		-1665,
-	-1654,		-1644,		-1634,		-1624,
-	-1613,		-1603,		-1593,		-1583,
-	-1573,		-1563,		-1552,		-1542,
-	-1532,		-1522,		-1511,		-1501,
-	-1491,		-1481,		-1471,		-1461,
-	-1450,		-1440,		-1430,		-1420,
-	-1409,		-1400,		-1389,		-1379,
-	-1369,		-1359,		-1348,		-1339,
-	-1328,		-1318,		-1308,		-1298,
-	-1288,		-1278,		-1267,		-1257,
-	-1247,		-1237,		-1227,		-1217,
-	-1207,		-1196,		-1186,		-1176,
-	-1166,		-1156,		-1146,		-1135,
-	-1126,		-1115,		-1105,		-1095,
-	-1085,		-1075,		-1065,		-1055,
-	-1044,		-1034,		-1024,		-1014,
-	-1004,		-994,		-984,		-974,
-	-964,		-954,		-944,		-933,
-	-923,		-913,		-903,		-893,
-	-883,		-873,		-863,		-853,
-	-843,		-833,		-822,		-812,
-	-802,		-792,		-782,		-772,
-	-762,		-752,		-742,		-732,
-	-722,		-712,		-702,		-691,
-	-682,		-671,		-662,		-651,
-	-641,		-631,		-621,		-611,
-	-601,		-591,		-581,		-571,
-	-561,		-551,		-541,		-531,
-	-521,		-511,		-501,		-491,
-	-480,		-471,		-460,		-451,
-	-440,		-430,		-420,		-410,
-	-400,		-390,		-380,		-370,
-	-360,		-350,		-340,		-330,
-	-320,		-310,		-300,		-290,
-	-280,		-270,		-260,		-250,
-	-240,		-230,		-220,		-210,
-	-199,		-190,		-179,		-170,
-	-159,		-150,		-139,		-129,
-	-119,		-109,		-99,		-89,
-	-79,		-69,		-59,		-49,
-	-39,		-29,		-19,		-9,
-	1,		11,		21,		31,
-	41,		51,		61,		71,
-	81,		91,		101,		111,
-	121,		131,		141,		152,
-	161,		172,		181,		192,
-	202,		212,		222,		232,
-	242,		252,		262,		272,
-	282,		292,		302,		312,
-	322,		332,		342,		352,
-	362,		372,		382,		392,
-	402,		412,		422,		433,
-	442,		453,		462,		473,
-	483,		493,		503,		513,
-	523,		533,		543,		553,
-	563,		573,		583,		593,
-	603,		613,		623,		633,
-	643,		653,		664,		673,
-	684,		694,		704,		714,
-	724,		734,		744,		754,
-	764,		774,		784,		794,
-	804,		815,		825,		835,
-	845,		855,		865,		875,
-	885,		895,		905,		915,
-	925,		936,		946,		956,
-	966,		976,		986,		996,
-	1006,		1016,		1026,		1037,
-	1047,		1057,		1067,		1077,
-	1087,		1097,		1107,		1117,
-	1128,		1138,		1148,		1158,
-	1168,		1178,		1188,		1198,
-	1209,		1219,		1229,		1239,
-	1249,		1259,		1269,		1280,
-	1290,		1300,		1310,		1320,
-	1330,		1341,		1351,		1361,
-	1371,		1381,		1391,		1402,
-	1412,		1422,		1432,		1442,
-	1452,		1463,		1473,		1483,
-	1493,		1503,		1513,		1524,
-	1534,		1544,		1554,		1565,
-	1575,		1585,		1595,		1606,
-	1616,		1626,		1636,		1647,
-	1656,		1667,		1677,		1687,
-	1697,		1708,		1718,		1729,
-	1739,		1749,		1759,		1769,
-	1780,		1790,		1800,		1810,
-	1821,		1831,		1841,		1851,
-	1862,		1872,		1883,		1893,
-	1903,		1913,		1923,		1934,
-	1944,		1955,		1965,		1975,
-	1985,		1996,		2006,		2016,
-	2027,		2037,		2048,		2058,
-	2068,		2079,		2089,		2099,
-	2110,		2120,		2130,		2141,
-	2151,		2161,		2172,		2182,
-	2193,		2203,		2213,		2224,
-	2234,		2245,		2255,		2265,
-	2276,		2286,		2297,		2307,
-	2318,		2328,		2338,		2349,
-	2359,		2370,		2380,		2391,
-	2401,		2412,		2422,		2433,
-	2443,		2454,		2464,		2475,
-	2485,		2496,		2506,		2517,
-	2527,		2537,		2548,		2559,
-	2569,		2580,		2590,		2601,
-	2612,		2622,		2632,		2643,
-	2654,		2664,		2675,		2685,
-	2696,		2707,		2717,		2728,
-	2738,		2749,		2759,		2770,
-	2781,		2791,		2802,		2813,
-	2823,		2834,		2845,		2855,
-	2866,		2877,		2887,		2898,
-	2909,		2919,		2930,		2941,
-	2951,		2962,		2973,		2984,
-	2994,		3005,		3015,		3027,
-	3037,		3048,		3058,		3069,
-	3080,		3091,		3101,		3113,
-	3123,		3134,		3145,		3156,
-	3166,		3177,		3188,		3199,
-	3210,		3220,		3231,		3242,
-	3253,		3264,		3275,		3285,
-	3296,		3307,		3318,		3329,
-	3340,		3351,		3362,		3373,
-	3384,		3394,		3405,		3416,
-	3427,		3438,		3449,		3460,
-	3471,		3482,		3493,		3504,
-	3515,		3526,		3537,		3548,
-	3559,		3570,		3581,		3592,
-	3603,		3614,		3625,		3636,
-	3647,		3659,		3670,		3681,
-	3692,		3703,		3714,		3725,
-	3736,		3747,		3758,		3770,
-	3781,		3792,		3803,		3814,
-	3825,		3837,		3848,		3859,
-	3870,		3881,		3893,		3904,
-	3915,		3926,		3937,		3949,
-	3960,		3971,		3983,		3994,
-	4005,		4017,		4028,		4039,
-	4051,		4062,		4073,		4085,
-	4096,		4107,		4119,		4130,
-	4141,		4153,		4164,		4175,
-	4187,		4198,		4210,		4221,
-	4233,		4244,		4256,		4267,
-	4279,		4290,		4302,		4313,
-	4325,		4336,		4348,		4359,
-	4371,		4382,		4394,		4406,
-	4417,		4429,		4440,		4452,
-	4464,		4475,		4487,		4499,
-	4510,		4522,		4533,		4545,
-	4557,		4569,		4581,		4592,
-	4604,		4616,		4627,		4639,
-	4651,		4663,		4674,		4686,
-	4698,		4710,		4722,		4734,
-	4746,		4758,		4769,		4781,
-	4793,		4805,		4817,		4829,
-	4841,		4853,		4865,		4877,
-	4889,		4900,		4913,		4925,
-	4936,		4949,		4961,		4973,
-	4985,		4997,		5009,		5021,
-	5033,		5045,		5057,		5070,
-	5081,		5094,		5106,		5118,
-	5130,		5143,		5155,		5167,
-	5179,		5191,		5204,		5216,
-	5228,		5240,		5253,		5265,
-	5278,		5290,		5302,		5315,
-	5327,		5340,		5352,		5364,
-	5377,		5389,		5401,		5414,
-	5426,		5439,		5451,		5464,
-	5476,		5489,		5502,		5514,
-	5527,		5539,		5552,		5564,
-	5577,		5590,		5603,		5615,
-	5628,		5641,		5653,		5666,
-	5679,		5691,		5704,		5717,
-	5730,		5743,		5756,		5768,
-	5781,		5794,		5807,		5820,
-	5833,		5846,		5859,		5872,
-	5885,		5897,		5911,		5924,
-	5937,		5950,		5963,		5976,
-	5989,		6002,		6015,		6028,
-	6042,		6055,		6068,		6081,
-	6094,		6108,		6121,		6134,
-	6147,		6160,		6174,		6187,
-	6201,		6214,		6227,		6241,
-	6254,		6267,		6281,		6294,
-	6308,		6321,		6335,		6348,
-	6362,		6375,		6389,		6403,
-	6416,		6430,		6443,		6457,
-	6471,		6485,		6498,		6512,
-	6526,		6540,		6554,		6567,
-	6581,		6595,		6609,		6623,
-	6637,		6651,		6665,		6679,
-	6692,		6706,		6721,		6735,
-	6749,		6763,		6777,		6791,
-	6805,		6819,		6833,		6848,
-	6862,		6876,		6890,		6905,
-	6919,		6933,		6948,		6962,
-	6976,		6991,		7005,		7020,
-	7034,		7049,		7064,		7078,
-	7093,		7107,		7122,		7136,
-	7151,		7166,		7180,		7195,
-	7210,		7225,		7240,		7254,
-	7269,		7284,		7299,		7314,
-	7329,		7344,		7359,		7374,
-	7389,		7404,		7419,		7434,
-	7449,		7465,		7480,		7495,
-	7510,		7526,		7541,		7556,
-	7571,		7587,		7602,		7618,
-	7633,		7648,		7664,		7680,
-	7695,		7711,		7726,		7742,
-	7758,		7773,		7789,		7805,
-	7821,		7836,		7852,		7868,
-	7884,		7900,		7916,		7932,
-	7948,		7964,		7981,		7997,
-	8013,		8029,		8045,		8061,
-	8078,		8094,		8110,		8127,
-	8143,		8160,		8176,		8193,
-	8209,		8226,		8242,		8259,
-	8276,		8292,		8309,		8326,
-	8343,		8360,		8377,		8394,
-	8410,		8428,		8444,		8462,
-	8479,		8496,		8513,		8530,
-	8548,		8565,		8582,		8600,
-	8617,		8634,		8652,		8670,
-	8687,		8704,		8722,		8740,
-	8758,		8775,		8793,		8811,
-	8829,		8847,		8865,		8883,
-	8901,		8919,		8937,		8955,
-	8974,		8992,		9010,		9029,
-	9047,		9066,		9084,		9103,
-	9121,		9140,		9159,		9177,
-	9196,		9215,		9234,		9253,
-	9272,		9291,		9310,		9329,
-	9349,		9368,		9387,		9406,
-	9426,		9445,		9465,		9484,
-	9504,		9524,		9544,		9563,
-	9583,		9603,		9623,		9643,
-	9663,		9683,		9703,		9723,
-	9744,		9764,		9785,		9805,
-	9826,		9846,		9867,		9888,
-	9909,		9930,		9950,		9971,
-	9993,		10013,		10035,		10056,
-	10077,		10099,		10120,		10142,
-	10163,		10185,		10207,		10229,
-	10251,		10273,		10294,		10317,
-	10339,		10361,		10384,		10406,
-	10428,		10451,		10474,		10496,
-	10519,		10542,		10565,		10588,
-	10612,		10635,		10658,		10682,
-	10705,		10729,		10752,		10776,
-	10800,		10824,		10848,		10872,
-	10896,		10921,		10945,		10969,
-	10994,		11019,		11044,		11069,
-	11094,		11119,		11144,		11169,
-	11195,		11221,		11246,		11272,
-	11298,		11324,		11350,		11376,
-	11402,		11429,		11456,		11482,
-	11509,		11536,		11563,		11590,
-	11618,		11645,		11673,		11701,
-	11728,		11756,		11785,		11813,
-	11842,		11870,		11899,		11928,
-	11957,		11986,		12015,		12045,
-	12074,		12104,		12134,		12164,
-	12194,		12225,		12255,		12286,
-	12317,		12348,		12380,		12411,
-	12443,		12475,		12507,		12539,
-	12571,		12604,		12637,		12670,
-	12703,		12737,		12771,		12804,
-	12839,		12873,		12907,		12942,
-	12977,		13013,		13048,		13084,
-	13120,		13156,		13192,		13229,
-	13267,		13304,		13341,		13379,
-	13418,		13456,		13495,		13534,
-	13573,		13613,		13653,		13693,
-	13734,		13775,		13817,		13858,
-	13901,		13943,		13986,		14029,
-	14073,		14117,		14162,		14206,
-	14252,		14297,		14343,		14390,
-	14437,		14485,		14533,		14582,
-	14631,		14680,		14731,		14782,
-	14833,		14885,		14937,		14991,
-	15044,		15099,		15154,		15210,
-	15266,		15324,		15382,		15441,
-	15500,		15561,		15622,		15684,
-	15747,		15811,		15877,		15943,
-	16010,		16078,		16148,		16218,
-	16290,		16363,		16437,		16513,
-	16590,		16669,		16749,		16831,
-	16915,		17000,		17088,		17177,
-	17268,		17362,		17458,		17556,
-	17657,		17761,		17868,		17977,
-	18090,		18207,		18328,		18452,
-	18581,		18715,		18854,		18998,
-	19149,		19307,		19472,		19645,
-	19828,		20021,		20226,		20444,
-	20678,		20930,		21204,		21503,
-	21835,		22206,		22630,		23124,
-	23721,		24478,		25529,		27316,
-};
+/* get_crandom - correlated random number generator
+ * Next number depends on last value.
+ * rho is scaled to avoid floating point.
+ */
+static unsigned long get_crandom(struct crndstate *state)
+{
+	u64 value, rho;
+	unsigned long answer;
 
-/* tabledist - return a pseudo-randomly distributed value with mean mu and
+	if (state->rho == 0)	/* no correllation */
+		return net_random();
+
+	value = net_random();
+	rho = (u64)state->rho + 1;
+	answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
+	state->last = answer;
+	return answer;
+}
+
+/* table_dist - return a pseudo-randomly distributed value with mean mu and
  * std deviation sigma.  Uses table lookup to approximate the desired
  * distribution, and a uniformly-distributed pseudo-random source.
  */
-static inline int tabledist(int mu, int sigma)
+static int table_dist(const struct dtable *dist,
+		       struct crndstate *state,
+		       int mu, int sigma)
 {
-	int x;
-	int index;
-	int sigmamod, sigmadiv;
+	int t, x;
+	unsigned long rnd;
 
 	if (sigma == 0)
 		return mu;
+	
+	rnd = get_crandom(state);
+
+	/* default uniform distribution */
+	if (dist == NULL)
+		return (rnd % (2*sigma)) - sigma + mu;
 
-	index = (net_random() & (TABLESIZE-1));
-	sigmamod = sigma%TABLEFACTOR;
-	sigmadiv = sigma/TABLEFACTOR;
-	x = sigmamod*disttable[index];
+	t = dist->table[rnd % dist->size];
+	x = (sigma % TCA_NETEM_TABLEFACTOR) * t;
 
 	if (x >= 0)
-		x += TABLEFACTOR/2;
+		x += TCA_NETEM_TABLEFACTOR/2;
 	else
-		x -= TABLEFACTOR/2;
+		x -= TCA_NETEM_TABLEFACTOR/2;
 
-	x /= TABLEFACTOR;
-	x += sigmadiv*disttable[index];
-	x += mu;
-	return x;
+	return (x + sigma * t)/TCA_NETEM_TABLEFACTOR + mu;
 }
 
 /* Enqueue packets with underlying discipline (fifo)
  * but mark them with current time first.
  */
-static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+static int netem_add_packet(struct Qdisc *sch, struct sk_buff *skb)
 {
 	struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 	struct netem_skb_cb *cb = (struct netem_skb_cb *)skb->cb;
 	psched_time_t now;
 	long delay;
 
-	pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
-
-	/* Random packet drop 0 => none, ~0 => all */
-	if (q->loss && q->loss >= net_random()) {
-		sch->stats.drops++;
-		return 0;	/* lie about loss so TCP doesn't know */
-	}
-
-
 	/* If doing simple delay then gap == 0 so all packets
 	 * go into the delayed holding queue
 	 * otherwise if doing out of order only "1 out of gap"
@@ -636,10 +168,12 @@
 	q->counter = 0;
 	
 	PSCHED_GET_TIME(now);
-	if (q->jitter) 
-		delay = tabledist(q->latency, q->jitter);
-	else
-		delay = q->latency;
+
+	delay = table_dist(q->distribution, 
+			   &q->delay_cor, q->latency, q->jitter);
+
+	pr_debug("netem_enqueue: delay %ld (mu=%u sigma=%u)\n",
+		 delay, q->latency, q->jitter);
 
 	PSCHED_TADD2(now, delay, cb->time_to_send);
 	
@@ -649,7 +183,7 @@
 		sch->q.qlen++;
 		sch->stats.bytes += skb->len;
 		sch->stats.packets++;
-		return 0;
+		return NET_XMIT_SUCCESS;
 	}
 
 	sch->stats.drops++;
@@ -657,6 +191,31 @@
 	return NET_XMIT_DROP;
 }
 
+static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
+	struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+
+	pr_debug("netem_enqueue skb=%p @%lu\n", skb, jiffies);
+
+	/* Random packet drop 0 => none, ~0 => all */
+	if (q->loss && q->loss >= get_crandom(&q->loss_cor)) {
+		pr_debug("netem_enqueue: random loss\n");
+		sch->stats.drops++;
+		return 0;	/* lie about loss so TCP doesn't know */
+	}
+
+	/* Random duplication */
+	if (q->duplicate && q->duplicate >= get_crandom(&q->dup_cor)) {
+		struct sk_buff *skb2 = skb_clone(skb, GFP_ATOMIC);
+
+		pr_debug("netem_enqueue: dup %p\n", skb2);
+		if (skb2)
+			netem_add_packet(sch, skb2);
+	}
+
+	return netem_add_packet(sch, skb);
+}
+
 /* Requeue packets but don't change time stamp */
 static int netem_requeue(struct sk_buff *skb, struct Qdisc *sch)
 {
@@ -753,90 +312,139 @@
 	return ret;
 }
 
-static int netem_change(struct Qdisc *sch, struct rtattr *opt)
+static struct dtable *new_dtable(int size, const __s16 *data)
 {
-	struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
-	struct tc_netem_qopt *qopt = RTA_DATA(opt);
-	struct Qdisc *child;
-	int ret;
+	struct dtable *d;
+	int i;
 
-	if (opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
-		return -EINVAL;
+	d = kmalloc(sizeof(*d) + size*sizeof(d->table[0]), GFP_KERNEL);
+	if (d) {
+		d->size = size;
+		for (i = 0; i < size; i++)
+			d->table[i] = data[i];
+	}
+	return d;
+}
 
-	child = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
-	if (!child)
+static int netem_change(struct Qdisc *sch, struct rtattr *opt)
+{
+ 	struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+	const struct tc_netem_qopt *qopt = RTA_DATA(opt);
+	long data_size = opt->rta_len - RTA_LENGTH(sizeof(*qopt));
+	struct dtable *dt;
+	
+	if (data_size < 0) {
+		pr_debug( "netem: requested options < current api\n");
 		return -EINVAL;
-
-	ret = set_fifo_limit(child, qopt->limit);
-	if (ret) {
-		qdisc_destroy(child);
-		return ret;
 	}
 
-	sch_tree_lock(sch);
-	if (child) {
-		child = xchg(&q->qdisc, child);
-		if (child != &noop_qdisc)
-			qdisc_destroy(child);
-	
-		q->latency = qopt->latency;
-		q->jitter = qopt->jitter;
-		q->limit = qopt->limit;
-		q->gap = qopt->gap;
-		q->loss = qopt->loss;
+	data_size /= sizeof(qopt->delay_dist[0]);
+	if (data_size > 16384) {
+		pr_debug("netem: bad distribution data size\n");
+		return -EINVAL;
 	}
-	sch_tree_unlock(sch);
+
+	if (data_size > 0) {
+		dt = new_dtable(data_size, qopt->delay_dist);
+		if (!dt)
+			return -ENOMEM;
+	} else
+		dt = NULL;
+
+
+	q->latency = qopt->latency;
+	q->jitter = qopt->jitter;
+	q->limit = qopt->limit;
+	q->gap = qopt->gap;
+	q->loss = qopt->loss;
+	q->duplicate = qopt->duplicate;
+
+	spin_lock_bh(&sch->dev->queue_lock);
+	dt = xchg(&q->distribution, dt);
+	kfree(dt);
+	spin_unlock_bh(&sch->dev->queue_lock);
+
+	init_crandom(&q->delay_cor, qopt->delay_corr);
+	init_crandom(&q->loss_cor, qopt->loss_corr);
+	init_crandom(&q->dup_cor, qopt->dup_corr);
 
 	return 0;
 }
 
 static int netem_init(struct Qdisc *sch, struct rtattr *opt)
 {
-	struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
-	int err;
+ 	struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+	const struct tc_netem_qopt *qopt;
+	int ret;
 
-	if (!opt)
+	if (!opt || opt->rta_len < RTA_LENGTH(sizeof(*qopt)))
 		return -EINVAL;
 
 	MOD_INC_USE_COUNT;
 	skb_queue_head_init(&q->delayed);
-	q->qdisc = &noop_qdisc;
-
 	init_timer(&q->timer);
 	q->timer.function = netem_watchdog;
 	q->timer.data = (unsigned long) sch;
 	q->counter = 0;
+	q->distribution = NULL;
+	
+	q->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
+	if (!q->qdisc) {
+		pr_debug("netem: qdisc create failed\n");
+		return -ENOMEM;
+	}
+
+	qopt = RTA_DATA(opt);
+	ret = set_fifo_limit(q->qdisc, qopt->limit);
+	if (ret) {
+		pr_debug("netem: can't set fifo limit\n");
+		goto error;
+	}
 
-	err = netem_change(sch, opt);
-	if (err != 0)
-		MOD_DEC_USE_COUNT;
-	return err;
+	ret = netem_change(sch, opt);
+	if (ret) {
+		pr_debug("netem: change failed\n");
+		goto error;
+	}
+
+	return 0;
+
+ error:
+	MOD_DEC_USE_COUNT;
+	qdisc_destroy(q->qdisc);
+	return ret;
 }
 
 static void netem_destroy(struct Qdisc *sch)
 {
-	struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+ 	struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
 
 	del_timer(&q->timer);
-
+	
+	kfree(q->distribution);
 	qdisc_destroy(q->qdisc);
-	q->qdisc = &noop_qdisc;
-
 	MOD_DEC_USE_COUNT;
 }
 
 static int netem_dump(struct Qdisc *sch, struct sk_buff *skb)
 {
-	struct netem_sched_data *q = (struct netem_sched_data *)sch->data;
+ 	const struct netem_sched_data *q
+		= (struct netem_sched_data *)sch->data;
 	unsigned char	 *b = skb->tail;
 	struct tc_netem_qopt qopt;
 
+	memset(&qopt, 0, sizeof(qopt));
 	qopt.latency = q->latency;
 	qopt.jitter = q->jitter;
 	qopt.limit = q->limit;
 	qopt.loss = q->loss;
 	qopt.gap = q->gap;
+	qopt.duplicate = q->duplicate;
+	qopt.delay_corr = q->delay_cor.rho;
+	qopt.loss_corr = q->loss_cor.rho;
+	qopt.dup_corr = q->dup_cor.rho;
 
+	/* don't dump out distribution table */
 	RTA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt);
 
 	return skb->len;

Re: [PATCH 2.6] (1/4) netem - update API for new features

[David S. Miller]

On Wed, 25 Aug 2004 10:53:39 -0700
Stephen Hemminger <shemminger@osdl.org> wrote:

> Extend netem options to support new features.

This breaks all existing tc binaries.  We have to stop
doing this.

Yes, you can extend the structure, but when you do that you
have to teach functions like netem_change() how to cope
with the old structure layout.

Re: [PATCH 2.6] (1/4) netem - update API for new features

[jamal]

On Wed, 2004-08-25 at 13:53, Stephen Hemminger wrote:
> Extend netem options to support new features.
> 

>  struct tc_netem_qopt
>  {
>  	__u32	latency;	/* added delay (us) */
> @@ -409,6 +410,13 @@
>  	__u32	loss;		/* random packet loss (0=none ~0=100%) */
>  	__u32	gap;		/* re-ordering gap (0 for delay all) */
>  	__u32   duplicate;	/* random packet dup  (0=none ~0=100%) */
> -	__u32	jitter;		/* random jitter in latency (us) */
> +	__u32	jitter;		/* delay sigma (us) */
> +
> +	__u32	delay_corr;	/* delay correllation (0=none ~0=100%) */
> +	__u32	loss_corr;	/* packet loss correllation (0=none ~0=100%) */
> +	__u32	dup_corr;	/* duplicate correlation (0=none ~0=100%) */
> +
> +	__s16	delay_dist[0];	/* delay distribution table (optional) */
> +#define TCA_NETEM_TABLEFACTOR	8192
>  };

You should really send the delay_dist in its own TLV to avoid
the kind of mistakes that showed up in u32 classifier.
Also allows you to extend that structure in the future.

cheers,
jamal

PS:- kudos on moving that stuff to user space.

Re: [PATCH 2.6] (1/4) netem - update API for new features

[Stephen Hemminger]

On 26 Aug 2004 08:08:51 -0400
jamal <hadi@cyberus.ca> wrote:

> On Wed, 2004-08-25 at 13:53, Stephen Hemminger wrote:
> > Extend netem options to support new features.
> > 
> 
> >  struct tc_netem_qopt
> >  {
> >  	__u32	latency;	/* added delay (us) */
> > @@ -409,6 +410,13 @@
> >  	__u32	loss;		/* random packet loss (0=none ~0=100%) */
> >  	__u32	gap;		/* re-ordering gap (0 for delay all) */
> >  	__u32   duplicate;	/* random packet dup  (0=none ~0=100%) */
> > -	__u32	jitter;		/* random jitter in latency (us) */
> > +	__u32	jitter;		/* delay sigma (us) */
> > +
> > +	__u32	delay_corr;	/* delay correllation (0=none ~0=100%) */
> > +	__u32	loss_corr;	/* packet loss correllation (0=none ~0=100%) */
> > +	__u32	dup_corr;	/* duplicate correlation (0=none ~0=100%) */
> > +
> > +	__s16	delay_dist[0];	/* delay distribution table (optional) */
> > +#define TCA_NETEM_TABLEFACTOR	8192
> >  };
> 
> You should really send the delay_dist in its own TLV to avoid
> the kind of mistakes that showed up in u32 classifier.
> Also allows you to extend that structure in the future.
> 
> cheers,
> jamal

It would be good but the whole qdisc api (init, change) is really structured
around a single TLV.

Re: [PATCH 2.6] (1/4) netem - update API for new features

[jamal]

On Thu, 2004-08-26 at 12:16, Stephen Hemminger wrote:
> On 26 Aug 2004 08:08:51 -0400
> jamal <hadi@cyberus.ca> wrote:
[..]
> > 
> > You should really send the delay_dist in its own TLV to avoid
> > the kind of mistakes that showed up in u32 classifier.
> > Also allows you to extend that structure in the future.
> > 
> > cheers,
> > jamal
> 
> It would be good but the whole qdisc api (init, change) is really structured
> around a single TLV.

Just pass nested attributes. The API is fine.

cheers,
jamal