* Re: [RESEND PATCH 1/3] netem/iproute2 solving correlated loss issue
2009-12-29 19:59 [RESEND PATCH 0/3] netem/iproute2 solving correlated loss issue Fabio Ludovici
@ 2009-12-29 20:00 ` Fabio Ludovici
2010-01-04 5:50 ` David Miller
2009-12-29 20:01 ` [RESEND PATCH 2/3] " Fabio Ludovici
2009-12-29 20:02 ` [RESEND PATCH 3/3] " Fabio Ludovici
2 siblings, 1 reply; 5+ messages in thread
From: Fabio Ludovici @ 2009-12-29 20:00 UTC (permalink / raw)
To: netdev
enhances netem module as follows:
- add deterministic loss generation according to a pattern that can be
specified in a file in the iproute2 command line
- new statistical models for generation of correlated loss (the existing
model does not work), including loss models commonly used in literature
(bernoulli, Gilbert, Gilbert Elliot) and the new GI (General and
Intuitive model)
- enhanced logging functionality for loss events in dmesg
Signed-off-by: Stefano Salsano <stefano.salsano@uniroma2.it>
Signed-off-by: Fabio Ludovici <fabio.ludovici@yahoo.it>
---
include/linux/pkt_sched.h | 33 ++++++
net/sched/sch_netem.c | 277
+++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 310 insertions(+), 0 deletions(-)
diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index d51a2b3..b492fd3 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -466,6 +466,10 @@ enum
TCA_NETEM_DELAY_DIST,
TCA_NETEM_REORDER,
TCA_NETEM_CORRUPT,
+ TCA_NETEM_LOSS_GI,
+ TCA_NETEM_LOSS_GILBELL,
+ TCA_NETEM_LOSS_PATTERN,
+ TCA_NETEM_LOGGING,
__TCA_NETEM_MAX,
};
@@ -500,6 +504,35 @@ struct tc_netem_corrupt
__u32 correlation;
};
+struct tc_netem_loss_GI
+{
+ __u32 p13;
+ __u32 p31;
+ __u32 p32;
+ __u32 p23;
+ __u32 p14;
+};
+
+struct tc_netem_loss_gilbell
+{
+ __u32 p;
+ __u32 r;
+ __u32 h;
+ __u32 k;
+};
+
+struct tc_netem_loss_pattern
+{
+ __u16 pattern_length;
+ __u32 pattern_repetitions;
+ __u16 *user_pattern;
+};
+
+struct tc_netem_logging
+{
+ __u8 level;
+};
+
#define NETEM_DIST_SCALE 8192
/* DRR */
diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 2b88295..c897ce3 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -62,6 +62,29 @@ struct netem_sched_data {
u32 duplicate;
u32 reorder;
u32 corrupt;
+ // GI loss model transition probabilities
+ u32 p13;
+ u32 p31;
+ u32 p23;
+ u32 p32;
+ u32 p14;
+ // Gilbert and Gilbert-Elliot loss models parameters
+ u32 p;
+ u32 r;
+ u32 h;
+ u32 k;
+ // Markov chain state for GI, Gilbert and Gilbert-Elliot models
+ u8 chain_state;
+ // Deterministic pattern parameters
+ u16 pattern_length; //deterministic loss length
+ u32 pattern_repetitions; //deterministic loss pattern repetitions
+ u32 *kernel_pattern; //deterministic loss pattern
+ // Logging parameters and variables
+ u8 logging_level;
+ u32 num_of_drops; //number of dropped packets
+ u32 num_of_transmissions; //number of correctly transmitted packets
+ u32 pattern_counter; //deterministic loss counter
+ u32 repetitions_done; //deterministic loss repetitions counter
struct crndstate {
u32 last;
@@ -159,6 +182,9 @@ static int netem_enqueue(struct sk_buff *skb, struct
Qdisc *sch)
struct sk_buff *skb2;
int ret;
int count = 1;
+
+ u32 GI_random; //GI loss model random number
+ u32 gilbell_random; //Gilbert-Elliot loss model random number
pr_debug("netem_enqueue skb=%p\n", skb);
@@ -170,6 +196,159 @@ static int netem_enqueue(struct sk_buff *skb,
struct Qdisc *sch)
if (q->loss && q->loss >= get_crandom(&q->loss_cor))
--count;
+ /* General and Intuitive loss generator, Gilbert-Elliot generator,
deterministic pattern
+ ====================================
+
+ Sources: [1] S. Salsano, F. Ludovici, A. Ordine: "Definition of a
general and
+ intuitive loss model for packet networks and its implementation in
the Netem
+ module in the Linux kernel" available at
+
http://netgroup.uniroma2.it/twiki/bin/view.cgi/Main/NetEm2#TechnicalReports
+
+ ----------------------------------------------------------------
+
+ This code generates packet losses according to the 4-state Markov
chain adopted
+ in the GI (General and Intuitive) loss model. To decide if a
packet will be lost
+ a random value GI_random is compared to the transition
probabilities outgoing from
+ the current state. The four states correspond to: successfully
transmitted packets
+ within a gap period (State 1), isolated losses within a gap period
(State 4),
+ lost packets within a burst period (State 3), successfully
transmitted packets
+ within a burst period (State 2).
+ */
+
+ if (q->p13) {
+
+ GI_random=net_random();
+
+ switch (q->chain_state) {
+ case 1:
+ q->num_of_transmissions++;
+ if((0<GI_random)&&(GI_random<q->p13)) {
+ q->chain_state=3;
+ break;
+ }
+ else if((q->p13<GI_random)&&(GI_random<(4294967295u-q->p14))) {
+ q->chain_state=1;
+ break;
+ }
+ else if(((4294967295u-q->p14)<GI_random) &&
(GI_random<4294967295u)) {
+ q->chain_state=4;
+ break;
+ }
+ case 2:
+ q->num_of_transmissions++;
+ if(GI_random<q->p23) {
+ q->chain_state=3;
+ break;
+ }
+ else {
+ q->chain_state=2;
+ break;
+ }
+ case 3:
+ --count;
+ q->num_of_drops++;
+ if (q->logging_level==1)
+ printk("netem loss event GI burst %d RFPLE %d\n",
+ q->num_of_drops, q->num_of_transmissions);
+ q->num_of_transmissions=0;
+ if((0<GI_random)&&(GI_random<q->p32)){
+ q->chain_state=2;
+ break;
+ }
+ else if((q->p32<GI_random) && (GI_random<(q->p31+q->p32))){
+ q->chain_state=1;
+ break;
+ }
+ else if(((q->p31+q->p32)<GI_random) && (GI_random<4294967295u)){
+ q->chain_state=3;
+ break;
+ }
+ case 4:
+ --count;
+ q->num_of_drops++;
+ q->chain_state=1;
+ if (q->logging_level==1)
+ printk("netem loss event GI isolated %d RFPLE %d\n",
+ q->num_of_drops, q->num_of_transmissions);
+ break;
+ }
+ }
+
+ /* Gilbert-Elliot loss generator algorithm
+ This code generates packet losses according to the Gilbert-Elliot loss
+ model and its special cases (like the Gilbert or the Simple Gilbert)
+ */
+
+ if (q->p) {
+
+ switch(q->chain_state) {
+ case 1:
+ gilbell_random=net_random();
+ if(gilbell_random<4294967295u-q->k){
+ --count;
+ q->num_of_drops++;
+ if (q->logging_level==1)
+ printk("netem loss event gilbell %d RFPLE %d\n",
+ q->num_of_drops, q->num_of_transmissions);
+ q->num_of_transmissions=0;
+ }
+ else {
+ q->num_of_transmissions++;
+ }
+ gilbell_random=net_random();
+ if(gilbell_random<q->p){
+ q->chain_state=2;
+ }
+ break;
+
+ case 2:
+ gilbell_random=net_random();
+ if(gilbell_random<4294967295u-q->h){
+ --count;
+ q->num_of_drops++;
+ if (q->logging_level==1)
+ printk("netem loss event gilbell %d RFPLE %d\n",
+ q->num_of_drops, q->num_of_transmissions);
+ q->num_of_transmissions=0;
+ }
+ else {
+ q->num_of_transmissions++;
+ }
+ gilbell_random=net_random();
+ if(gilbell_random<q->r) {
+ q->chain_state=1;
+ }
+ break;
+ }
+ }
+
+ /* Deterministic loss pattern algorithm
+ This code generates packet losses according to a deterministic
sequence
+ of 0 and 1 where 0 represents a transmitted packet and 1 represents a
+ loss event. The pattern can be repeated for a fixed number of times or
+ indefinitely (if pattern_repetitions=0).
+ */
+
+ if ((0<q->pattern_length) & ((q->pattern_repetitions==0)||
+ (q->repetitions_done<q->pattern_repetitions)) &
+ (q->pattern_counter<q->pattern_length)){
+
+ if (0<q->kernel_pattern[q->pattern_counter-1]){
+ --count;
+ q->num_of_drops++;
+ if (q->logging_level==1)
+ printk("netem loss event deterministic %d RFPLE %d\n",
+ q->num_of_drops, q->num_of_transmissions);
+ q->num_of_transmissions=0;
+ }
+ else q->num_of_transmissions++;
+ q->pattern_counter++;
+ if (q->pattern_counter==q->pattern_length-1){
+ q->repetitions_done++;
+ q->pattern_counter=1;
+ }
+ }
+
if (count == 0) {
sch->qstats.drops++;
kfree_skb(skb);
@@ -369,10 +548,72 @@ static void get_corrupt(struct Qdisc *sch, const
struct nlattr *attr)
init_crandom(&q->corrupt_cor, r->correlation);
}
+static void get_loss_GI(struct Qdisc *sch, const struct nlattr *attr)
+{
+ struct netem_sched_data *q = qdisc_priv(sch);
+ const struct tc_netem_loss_GI *GI = nla_data(attr);
+
+ q->p13 = GI->p13;
+ q->p31 = GI->p31;
+ q->p32 = GI->p32;
+ q->p23 = GI->p23;
+ q->p14 = GI->p14;
+ q->num_of_drops=0;
+ q->num_of_transmissions=0;
+ q->chain_state=1;
+}
+
+static void get_loss_gilbell(struct Qdisc *sch, const struct nlattr *attr)
+{
+ struct netem_sched_data *q = qdisc_priv(sch);
+ const struct tc_netem_loss_gilbell *ge = nla_data(attr);
+
+ q->p = ge->p;
+ q->r = ge->r;
+ q->h = ge->h;
+ q->k = ge->k;
+ q->num_of_drops=0;
+ q->num_of_transmissions=0;
+ q->chain_state=1;
+}
+
+static void get_loss_pattern(struct Qdisc *sch, const struct nlattr *attr)
+{
+ struct netem_sched_data *q = qdisc_priv(sch);
+ const struct tc_netem_loss_pattern *pt = nla_data(attr);
+ int pattern_element;
+ q->pattern_length = pt->pattern_length;
+ q->pattern_repetitions = pt->pattern_repetitions;
+ q->kernel_pattern=kmalloc(q->pattern_length*sizeof(size_t),
+ GFP_KERNEL);
+
+ for (pattern_element=1; pattern_element<q->pattern_length;
+ pattern_element++) {
+ q->kernel_pattern[pattern_element-1] =
+ pt->user_pattern[pattern_element-1];
+ }
+ q->num_of_drops=0;
+ q->num_of_transmissions=0;
+ q->pattern_counter=1;
+ q->repetitions_done=0;
+}
+
+static void get_logging(struct Qdisc *sch, const struct nlattr *attr)
+{
+ struct netem_sched_data *q = qdisc_priv(sch);
+ const struct tc_netem_logging *lo = nla_data(attr);
+
+ q->logging_level = lo->level;
+}
+
static const struct nla_policy netem_policy[TCA_NETEM_MAX + 1] = {
[TCA_NETEM_CORR] = { .len = sizeof(struct tc_netem_corr) },
[TCA_NETEM_REORDER] = { .len = sizeof(struct tc_netem_reorder) },
[TCA_NETEM_CORRUPT] = { .len = sizeof(struct tc_netem_corrupt) },
+ [TCA_NETEM_LOSS_GI] = { .len = sizeof(struct tc_netem_loss_GI) },
+ [TCA_NETEM_LOSS_GILBELL]= { .len = sizeof(struct
tc_netem_loss_gilbell) },
+ [TCA_NETEM_LOSS_PATTERN]= { .len = sizeof(struct
tc_netem_loss_pattern) },
+ [TCA_NETEM_LOGGING] = { .len = sizeof(struct tc_netem_logging) },
};
static int parse_attr(struct nlattr *tb[], int maxtype, struct nlattr
*nla,
@@ -440,6 +681,18 @@ static int netem_change(struct Qdisc *sch, struct
nlattr *opt)
if (tb[TCA_NETEM_CORRUPT])
get_corrupt(sch, tb[TCA_NETEM_CORRUPT]);
+ if (tb[TCA_NETEM_LOSS_GI])
+ get_loss_GI(sch, tb[TCA_NETEM_LOSS_GI]);
+
+ if (tb[TCA_NETEM_LOSS_GILBELL])
+ get_loss_gilbell(sch, tb[TCA_NETEM_LOSS_GILBELL]);
+
+ if (tb[TCA_NETEM_LOSS_PATTERN])
+ get_loss_pattern(sch, tb[TCA_NETEM_LOSS_PATTERN]);
+
+ if (tb[TCA_NETEM_LOGGING])
+ get_logging(sch, tb[TCA_NETEM_LOGGING]);
+
return 0;
}
@@ -571,6 +824,10 @@ static int netem_dump(struct Qdisc *sch, struct
sk_buff *skb)
struct tc_netem_corr cor;
struct tc_netem_reorder reorder;
struct tc_netem_corrupt corrupt;
+ struct tc_netem_loss_GI GI;
+ struct tc_netem_loss_gilbell gilbell;
+ struct tc_netem_loss_pattern pattern;
+ struct tc_netem_logging logging;
qopt.latency = q->latency;
qopt.jitter = q->jitter;
@@ -593,6 +850,26 @@ static int netem_dump(struct Qdisc *sch, struct
sk_buff *skb)
corrupt.correlation = q->corrupt_cor.rho;
NLA_PUT(skb, TCA_NETEM_CORRUPT, sizeof(corrupt), &corrupt);
+ GI.p13=q->p13;
+ GI.p31=q->p31;
+ GI.p23=q->p23;
+ GI.p32=q->p32;
+ GI.p14=q->p14;
+ NLA_PUT(skb, TCA_NETEM_LOSS_GI, sizeof(GI), &GI);
+
+ gilbell.p=q->p;
+ gilbell.r=q->r;
+ gilbell.h=q->h;
+ gilbell.k=q->k;
+ NLA_PUT(skb, TCA_NETEM_LOSS_GILBELL, sizeof(gilbell), &gilbell);
+
+ pattern.pattern_length = q->pattern_length;
+ pattern.pattern_repetitions = q->pattern_repetitions;
+
+ NLA_PUT(skb, TCA_NETEM_LOSS_PATTERN, sizeof(pattern), &pattern);
+ logging.level=q->logging_level;
+ NLA_PUT(skb, TCA_NETEM_LOGGING, sizeof(logging), &logging);
+
nla->nla_len = skb_tail_pointer(skb) - b;
return skb->len;
--
1.6.3.3
--
Fabio Ludovici
^ permalink raw reply related [flat|nested] 5+ messages in thread* Re: [RESEND PATCH 2/3] netem/iproute2 solving correlated loss issue
2009-12-29 19:59 [RESEND PATCH 0/3] netem/iproute2 solving correlated loss issue Fabio Ludovici
2009-12-29 20:00 ` [RESEND PATCH 1/3] " Fabio Ludovici
@ 2009-12-29 20:01 ` Fabio Ludovici
2009-12-29 20:02 ` [RESEND PATCH 3/3] " Fabio Ludovici
2 siblings, 0 replies; 5+ messages in thread
From: Fabio Ludovici @ 2009-12-29 20:01 UTC (permalink / raw)
To: netdev
enhances iproute2 to work the the following new features of netem:
- deterministic loss according to a pattern that can be specified in a
file in the iproute2 command line
- new models for generation of correlated loss (the existing model does
not work)
- parameter converter between intuitive parameters and Markov transition
probabilities (query mode)
- enhanced logging functionality for loss events in dmesg
Examples of new iproute2 syntax is reported hereafter (see the man page
for the full list):
1) generate loss according to a deterministic pattern:
tc qdisc add/change dev eth0 root netem loss_pattern filename
2) generate loss according to different loss models including the ones
commonly used in the literature (bernoulli, gilbert, gilbert-elliot...)
and the new GI (General and Intuitive) model
tc qdisc add/change dev eth0 root netem loss_bern p
tc qdisc add/change dev eth0 root netem loss_gilb p r [1-h]
tc qdisc add/change dev eth0 root netem loss_gilbell p r [1-h [1-k]]
tc qdisc add/change dev eth0 root netem loss_GI ploss
[burst_length [density [pisol [good_burst_length]]]]
tc qdisc add/change dev eth0 root netem loss_GI_tran p13 p31 [p32 p23
[p14]]
3) parameter converter between intuitive and Markov transition
probabilities (query mode)
this applies to loss_GI and loss_GI_tran options. If the query label is
specified before the model label the transition probabilities or the GI
parameters that corresponds to the specified input parameters are
calculated and printed to screen, but no operation is done on the qdisc.
In this way the user can understands what he would obtain with certain
input parameters without necessarily make changes to the network's
behaviour.
4) enable enhanced logging in dmesg:
tc qdisc add/change dev eth0 root netem logging 1 loss_GI 5 10
for each loss event the kernel logs will include a line like "netem2
loss event loss_GI 30 RFPLE 15" where RFPLE stands for "Received From
Previous Loss Event" and it counts the number y of good packets received
between two loss events while x is the number of all lost packets
Signed-off-by: Stefano Salsano <stefano.salsano@uniroma2.it>
Signed-off-by: Fabio Ludovici <fabio.ludovici@yahoo.it>
---
include/linux/pkt_sched.h | 33 ++++
tc/q_netem.c | 396
+++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 429 insertions(+), 0 deletions(-)
diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index d51a2b3..85232c5 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -466,6 +466,10 @@ enum
TCA_NETEM_DELAY_DIST,
TCA_NETEM_REORDER,
TCA_NETEM_CORRUPT,
+ TCA_NETEM_LOSS_GI,
+ TCA_NETEM_LOSS_GILBELL,
+ TCA_NETEM_LOSS_PATTERN,
+ TCA_NETEM_LOGGING,
__TCA_NETEM_MAX,
};
@@ -500,6 +504,35 @@ struct tc_netem_corrupt
__u32 correlation;
};
+struct tc_netem_loss_GI
+{
+ __u32 p13;
+ __u32 p31;
+ __u32 p32;
+ __u32 p23;
+ __u32 p14;
+};
+
+struct tc_netem_loss_gilbell
+{
+ __u32 p;
+ __u32 r;
+ __u32 h;
+ __u32 k;
+};
+
+struct tc_netem_loss_pattern
+{
+ __u16 pattern_length;
+ __u32 pattern_repetitions;
+ __u16 *user_pattern;
+};
+
+struct tc_netem_logging
+{
+ __u8 level;
+};
+
#define NETEM_DIST_SCALE 8192
/* DRR */
diff --git a/tc/q_netem.c b/tc/q_netem.c
index 33b3d2a..5ad1ab3 100644
--- a/tc/q_netem.c
+++ b/tc/q_netem.c
@@ -32,6 +32,12 @@ static void explain(void)
" [ delay TIME [ JITTER [CORRELATION]]]\n" \
" [ distribution {uniform|normal|pareto|paretonormal}
]\n" \
" [ drop PERCENT [CORRELATION]] \n" \
+" [ loss_GI ploss [burst_length [density [pisol
[good_burst_length]]]]] \n" \
+" [ loss_GI_tran p13 p31 [p32 p23 [p14]]] \n" \
+" [ loss_bern p] \n" \
+" [ loss_gilb p r [1-h]] \n" \
+" [ loss_gilbell p r [1-h [1-k]]] \n" \
+" [ loss_pattern [filename [repetitions]]] \n" \
" [ corrupt PERCENT [CORRELATION]] \n" \
" [ duplicate PERCENT [CORRELATION]]\n" \
" [ reorder PRECENT [CORRELATION] [ gap DISTANCE ]]\n");
@@ -133,14 +139,23 @@ static int netem_parse_opt(struct qdisc_util *qu,
int argc, char **argv,
struct tc_netem_corr cor;
struct tc_netem_reorder reorder;
struct tc_netem_corrupt corrupt;
+ struct tc_netem_loss_GI GI;
+ struct tc_netem_loss_gilbell gilbell;
+ struct tc_netem_loss_pattern pattern;
+ struct tc_netem_logging logging;
__s16 *dist_data = NULL;
int present[__TCA_NETEM_MAX];
+ int query=0;
memset(&opt, 0, sizeof(opt));
opt.limit = 1000;
memset(&cor, 0, sizeof(cor));
memset(&reorder, 0, sizeof(reorder));
memset(&corrupt, 0, sizeof(corrupt));
+ memset(&GI, 0, sizeof(GI));
+ memset(&gilbell, 0, sizeof(gilbell));
+ memset(&pattern, 0, sizeof(pattern));
+ memset(&logging, 0, sizeof(logging));
memset(present, 0, sizeof(present));
while (argc > 0) {
@@ -150,6 +165,15 @@ static int netem_parse_opt(struct qdisc_util *qu,
int argc, char **argv,
explain1("limit");
return -1;
}
+ } else if (matches(*argv, "logging") == 0) {
+ NEXT_ARG();
+ ++present[TCA_NETEM_LOGGING];
+ if (get_size(&logging.level, *argv)) {
+ explain1("logging");
+ return -1;
+ }
+ } else if (matches(*argv, "query") == 0) {
+ query=1;
} else if (matches(*argv, "latency") == 0 ||
matches(*argv, "delay") == 0) {
NEXT_ARG();
@@ -189,6 +213,315 @@ static int netem_parse_opt(struct qdisc_util *qu,
int argc, char **argv,
return -1;
}
}
+ } else if (matches(*argv, "loss_GI") == 0) {
+ NEXT_ARG();
+ double p13=0;
+ double p31=1;
+ double p32=0;
+ double p23=1;
+ double p14=0;
+ double ploss=0;
+ double burst_length=1;
+ double rho=1;
+ double pisol=0;
+ double good_burst_length=1;
+
+ ploss=strtod(*argv,(char **)NULL)/100;
+
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ burst_length=strtod(*argv,(char **)NULL);
+
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ rho=strtod(*argv,(char **)NULL)/100;
+
+ if (ploss>rho) {
+ printf("\nError: ploss>density \n");
+ break;
+ }
+
+ if(NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ pisol=strtod(*argv,(char **)NULL)/100;
+
+ if (pisol>ploss) {
+ printf("\nError: pisol>ploss \n");
+ break;
+ }
+
+ if (ploss>(rho-pisol*(rho-1))) {
+ printf("\nError: ploss>density-pisol(density-1) \n");
+ break;
+ }
+
+ if(NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ good_burst_length=strtod(*argv,(char **)NULL);
+ if(good_burst_length>burst_length) {
+ printf("\nError: good burst length>burst length \n ");
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ if(burst_length==0) {
+ p13=ploss;
+ p31=1-ploss;
+ }
+
+ else if((burst_length!=0) & (rho==1) & (pisol==0)) {
+ p13=ploss/(burst_length*(1-ploss));
+ p31=1/burst_length;
+ }
+
+ else if ((burst_length!=0) & (rho!=1) & (pisol==0)) {
+ p13=(-ploss)/(burst_length*ploss-burst_length*rho);
+ p31=1/(burst_length*rho);
+ }
+
+ else if ((burst_length!=0) & (rho!=1) & (pisol!=0)) {
+ p13=(pisol-ploss)/(burst_length*(pisol-1)*(rho-ploss));
+ p31=1/(burst_length*rho);
+ p14=pisol/(1-pisol);
+ }
+
+ if((burst_length!=0) & (rho!=1)) {
+ if(good_burst_length==0) {
+ p23=(burst_length*rho-1) / (burst_length-1);
+ p32=(1+rho*rho*burst_length-rho-burst_length*rho) /
+ (rho-rho*burst_length);
+ }
+ }
+ else {
+ p23=1/good_burst_length;
+ p32=(1-rho) / (rho*good_burst_length);
+ }
+
+ if (burst_length==0) burst_length=1/p31;
+ printf("\nTransition probabilities are:\n ");
+ printf("--------------------------------");
+ printf("\np13 is %.3f%% ", 100*p13);
+ printf("\np31 is %.3f%% ", 100*p31);
+ printf("\np32 is %.3f%% ", 100*p32);
+ printf("\np23 is %.3f%% ", 100*p23);
+ printf("\np14 is %.3f%%\n ", 100*p14);
+
+ printf("\nGI (General and Intuitive) parameters will be: \n");
+ printf("--------------------------------");
+ printf("\nploss is %.3f%% ", 100*ploss);
+ printf("\nburst length is %.3f", burst_length);
+ printf("\nburst density is %.3f%% ", 100*rho);
+ printf("\nisolated ploss is %.3f%% ", 100*pisol);
+ printf("\ngood burst length is %.3f\n ", good_burst_length);
+
+ if(query==0) {
+ present[TCA_NETEM_LOSS_GI] = 1;
+ GI.p13=4294967295u*p13;
+ GI.p31=4294967295u*p31;
+ GI.p32=4294967295u*p32;
+ GI.p23=4294967295u*p23;
+ GI.p14=4294967295u*p14;
+ }
+
+ if(query==1) return -1;
+
+ } else if (matches(*argv, "loss_GI_tran") == 0) {
+ double p13=0;
+ double p31=1;
+ double p32=0;
+ double p23=1;
+ double p14=0;
+ double ploss;
+ double burst_length;
+ double rho=1;
+ double pisol=0;
+ double good_burst_length=1;
+
+ NEXT_ARG();
+ p13=strtod(*argv,(char **)NULL)/100;
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ p31=strtod(*argv,(char **)NULL)/100;
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ p32=strtod(*argv,(char **)NULL)/100;
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ p23=strtod(*argv,(char **)NULL)/100;
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ p14=strtod(*argv,(char **)NULL)/100;
+ }
+ }
+ }
+ }
+ else p31=1-p13;
+
+ printf("\nTransition probabilities are:\n ");
+ printf("--------------------------------");
+ printf("\np13 is %.3f%% ", 100*p13);
+ printf("\np31 is %.3f%% ", 100*p31);
+ printf("\np32 is %.3f%% ", 100*p32);
+ printf("\np23 is %.3f%% ", 100*p23);
+ printf("\np14 is %.3f%%\n ", 100*p14);
+
+ ploss=(p13*p23+p14*p23*p31) /
(p13*p23+p23*p31+p14*p23*p31+p13*p32);
+ burst_length=(p32+p23) / (p23*p31);
+ rho=(p13*p23) / (p13*p23+p13*p32);
+ pisol=(p14*p23*p31) / (p14*p23*p31+p23*p31);
+ good_burst_length=1/p23;
+
+ printf("\nGI (General and Intuitive) parameters will be: \n");
+ printf("--------------------------------");
+ printf("\nploss is %.3f%%", 100*ploss);
+ printf("\nburst length is %.3f", burst_length);
+ printf("\nburst density is %.3f%% ", 100*rho);
+ printf("\nisolated ploss is %.3f%% ", 100*pisol);
+ printf("\ngood burst length is %.3f\n ", good_burst_length);
+
+ if(query==0) {
+ present[TCA_NETEM_LOSS_GI] = 1;
+ GI.p13=4294967295u*p13;
+ GI.p31=4294967295u*p31;
+ GI.p32=4294967295u*p32;
+ GI.p23=4294967295u*p23;
+ GI.p14=4294967295u*p14;
+ }
+
+ if(query==1) return -1;
+
+ } else if (matches(*argv, "loss_gilb") == 0) {
+
+ double p=0;
+ double r=0;
+ double h=0;
+
+ NEXT_ARG();
+ p=strtod(*argv,(char **)NULL)/100;
+
+ NEXT_ARG();
+ r=strtod(*argv,(char **)NULL)/100;
+
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ h=(100-strtod(*argv,(char **)NULL))/100;
+ }
+
+ present[TCA_NETEM_LOSS_GILBELL] = 1;
+ gilbell.p=4294967295u*p;
+ gilbell.r=4294967295u*r;
+ gilbell.h=4294967295u*h;
+
+ } else if (matches(*argv, "loss_gilbell") == 0) {
+
+ double p=0;
+ double r=0;
+ double h=0;
+ double k=1;
+
+ NEXT_ARG();
+ p=strtod(*argv,(char **)NULL)/100;
+
+ NEXT_ARG();
+ r=strtod(*argv,(char **)NULL)/100;
+
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ h=(100-strtod(*argv,(char **)NULL))/100;
+
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ k=(100-strtod(*argv,(char **)NULL))/100;
+ }
+ }
+
+ present[TCA_NETEM_LOSS_GILBELL] = 1;
+ gilbell.p=4294967295u*p;
+ gilbell.r=4294967295u*r;
+ gilbell.h=4294967295u*h;
+ gilbell.k=4294967295u*k;
+
+ } else if (matches(*argv, "loss_bern") == 0) {
+
+ double p=0;
+ double r=0;
+ double ploss=0;
+ double burst_length=1;
+ double p13=0;
+ double p31=0;
+
+ NEXT_ARG();
+ p=strtod(*argv,(char **)NULL)/100;
+ r=1-p;
+
+ ploss=p/(p+r);
+ burst_length=1/r;
+
+ p13=p;
+ p31=r;
+
+ printf("\nTransition probabilities are:\n ");
+ printf("--------------------------------");
+ printf("\np13 is %.3f%% ", 100*p13);
+ printf("\np31 is %.3f%% ", 100*p31);
+ printf("\np32 is 0.000%% ");
+ printf("\np23 is 100.000%% ");
+ printf("\np14 is 0.000%%\n ");
+
+ printf("\nGI (General and Intuitive) parameters will be: \n");
+ printf("--------------------------------");
+ printf("\nploss is %.3f%% ", 100*ploss);
+ printf("\nburst length is %.3f", burst_length);
+ printf("\nburst density is 100.000%% ");
+ printf("\nisolated ploss is 0.000%% ");
+ printf("\ngood burst length is 1.000%%\n ");
+
+ if(query==0) {
+ present[TCA_NETEM_LOSS_GI] = 1;
+ GI.p13=4294967295u*p13;
+ GI.p31=4294967295u*p31;
+ GI.p32=0;
+ GI.p23=4294967295u;
+ GI.p14=0;
+ }
+
+ if(query==1) return -1;
+
+ } else if (matches(*argv, "loss_pattern") == 0) {
+ NEXT_ARG();
+
+ int i;
+
+ FILE *sequence;
+
+ sequence=fopen(*argv, "r");
+
+ if (sequence == NULL) {
+ printf("Could not open the file %s \n", *argv);
+ exit(1); }
+
+ fseek(sequence, 0, SEEK_END);
+ fgetpos(sequence, &pattern.pattern_length);
+ rewind(sequence);
+
+ pattern.user_pattern=malloc(pattern.pattern_length*sizeof(int));
+ pattern.pattern_repetitions=0;
+
+ for(i=1; i<pattern.pattern_length; i++) {
+ if(fgetc(sequence)=='1') pattern.user_pattern[i-1]=1;
+ else pattern.user_pattern[i-1]=0; }
+
+ fclose(sequence);
+
+ if (NEXT_IS_NUMBER()) {
+ NEXT_ARG();
+ pattern.pattern_repetitions=strtod(*argv,(char **)NULL);
+ }
+ present[TCA_NETEM_LOSS_PATTERN] = 1;
+
} else if (matches(*argv, "reorder") == 0) {
NEXT_ARG();
present[TCA_NETEM_REORDER] = 1;
@@ -292,6 +625,22 @@ 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_LOSS_GI] &&
+ addattr_l(n, 1024, TCA_NETEM_LOSS_GI, &GI, sizeof(GI)) < 0)
+ return -1;
+
+ if (present[TCA_NETEM_LOSS_GILBELL] &&
+ addattr_l(n, 1024, TCA_NETEM_LOSS_GILBELL, &gilbell,
sizeof(gilbell)) < 0)
+ return -1;
+
+ if (present[TCA_NETEM_LOSS_PATTERN] &&
+ addattr_l(n, 1024, TCA_NETEM_LOSS_PATTERN, &pattern,
sizeof(pattern)) < 0)
+ return -1;
+
+ if (present[TCA_NETEM_LOGGING] &&
+ addattr_l(n, 1024, TCA_NETEM_LOGGING, &logging,
sizeof(logging)) < 0)
+ return -1;
+
if (dist_data) {
if (addattr_l(n, MAX_DIST * sizeof(dist_data[0]),
TCA_NETEM_DELAY_DIST,
@@ -308,6 +657,10 @@ static int netem_print_opt(struct qdisc_util *qu,
FILE *f, struct rtattr *opt)
const struct tc_netem_corr *cor = NULL;
const struct tc_netem_reorder *reorder = NULL;
const struct tc_netem_corrupt *corrupt = NULL;
+ const struct tc_netem_loss_GI *GI = NULL;
+ const struct tc_netem_loss_gilbell *gilbell = NULL;
+ const struct tc_netem_loss_pattern *pattern = NULL;
+ const struct tc_netem_logging *logging = NULL;
struct tc_netem_qopt qopt;
int len = RTA_PAYLOAD(opt) - sizeof(qopt);
SPRINT_BUF(b1);
@@ -341,6 +694,26 @@ static int netem_print_opt(struct qdisc_util *qu,
FILE *f, struct rtattr *opt)
return -1;
corrupt = RTA_DATA(tb[TCA_NETEM_CORRUPT]);
}
+ if (tb[TCA_NETEM_LOSS_GI]) {
+ if (RTA_PAYLOAD(tb[TCA_NETEM_LOSS_GI]) < sizeof(*GI))
+ return -1;
+ GI = RTA_DATA(tb[TCA_NETEM_LOSS_GI]);
+ }
+ if (tb[TCA_NETEM_LOSS_GILBELL]) {
+ if (RTA_PAYLOAD(tb[TCA_NETEM_LOSS_GILBELL]) <
sizeof(*gilbell))
+ return -1;
+ gilbell = RTA_DATA(tb[TCA_NETEM_LOSS_GILBELL]);
+ }
+ if (tb[TCA_NETEM_LOSS_PATTERN]) {
+ if (RTA_PAYLOAD(tb[TCA_NETEM_LOSS_PATTERN]) <
sizeof(*pattern))
+ return -1;
+ pattern = RTA_DATA(tb[TCA_NETEM_LOSS_PATTERN]);
+ }
+ if (tb[TCA_NETEM_LOGGING]) {
+ if (RTA_PAYLOAD(tb[TCA_NETEM_LOGGING]) < sizeof(*logging))
+ return -1;
+ logging = RTA_DATA(tb[TCA_NETEM_LOGGING]);
+ }
}
fprintf(f, "limit %d", qopt.limit);
@@ -387,6 +760,29 @@ static int netem_print_opt(struct qdisc_util *qu,
FILE *f, struct rtattr *opt)
if (qopt.gap)
fprintf(f, " gap %lu", (unsigned long)qopt.gap);
+ if (GI && GI->p13) {
+ fprintf(f, " p13 %s", sprint_percent(GI->p13, b1));
+ fprintf(f, " p31 %s", sprint_percent(GI->p31, b1));
+ fprintf(f, " p32 %s", sprint_percent(GI->p32, b1));
+ fprintf(f, " p23 %s", sprint_percent(GI->p23, b1));
+ fprintf(f, " p14 %s", sprint_percent(GI->p14, b1));
+ }
+
+ if (gilbell && gilbell->p) {
+ fprintf(f, " p %s", sprint_percent(gilbell->p, b1));
+ fprintf(f, " r %s", sprint_percent(gilbell->r, b1));
+ fprintf(f, " h %s", sprint_percent(gilbell->h, b1));
+ if (gilbell->k)
+ fprintf(f, " k %s", sprint_percent(gilbell->k, b1));
+ }
+
+ if(logging && logging->level)
+ fprintf(f, " logging %d", logging->level);
+ if(pattern && pattern->pattern_length)
+ fprintf(f, " pattern_length %d", pattern->pattern_length);
+ if(pattern && pattern->pattern_repetitions)
+ fprintf(f, " pattern_repetitions %d", pattern->pattern_repetitions);
+
return 0;
}
--
1.6.3.3
--
Fabio Ludovici
^ permalink raw reply related [flat|nested] 5+ messages in thread* Re: [RESEND PATCH 3/3] netem/iproute2 solving correlated loss issue
2009-12-29 19:59 [RESEND PATCH 0/3] netem/iproute2 solving correlated loss issue Fabio Ludovici
2009-12-29 20:00 ` [RESEND PATCH 1/3] " Fabio Ludovici
2009-12-29 20:01 ` [RESEND PATCH 2/3] " Fabio Ludovici
@ 2009-12-29 20:02 ` Fabio Ludovici
2 siblings, 0 replies; 5+ messages in thread
From: Fabio Ludovici @ 2009-12-29 20:02 UTC (permalink / raw)
To: netdev
man page for iproute2/netem, including all the existing documentation
and the latest features:
- deterministic loss generation according to a pattern that can be
specified in a file in the iproute2 command line
- new statistical models for generation of correlated loss (the existing
model does not work), including loss models commonly used in literature
(bernoulli, Gilbert, Gilbert Elliot) and the new GI (General and
Intuitive) model
- parameter converter between intuitive parameters and Markov transition
probabilities (query mode)
- enhanced logging functionality for loss events in dmesg
Signed-off-by: Stefano Salsano <stefano.salsano@uniroma2.it>
Signed-off-by: Fabio Ludovici <fabio.ludovici@yahoo.it>
---
man/man8/tc-netem.8 | 225
+++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 225 insertions(+), 0 deletions(-)
create mode 100644 man/man8/tc-netem.8
diff --git a/man/man8/tc-netem.8 b/man/man8/tc-netem.8
new file mode 100644
index 0000000..4fbe579
--- /dev/null
+++ b/man/man8/tc-netem.8
@@ -0,0 +1,225 @@
+.TH NETEM 8 "28 December 2009" "iproute2" "Linux"
+.SH NAME
+NetEm \- Network Emulator
+.SH SYNOPSIS
+.B tc qdisc ... dev
+dev
+.B ] add netem [ limit
+packets
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ logging
+LEVEL ]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ delay
+TIME [ JITTER [CORRELATION]]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ distribution
+{uniform|normal|pareto|paretonormal} ]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ drop
+PERCENT [CORRELATION]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ loss
+PERCENT [CORRELATION]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ query
+]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ loss_GI
+ploss [burst_length [density [pisol [good_burst_length]]]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ loss_GI_tran
+p13 p31 [p32 p23 [p14]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ loss_bern
+p
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ loss_gilb
+p r [1-h]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ loss_gilbell
+p r [1-h [1-k]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ loss_pattern
+FILENAME [REPETITIONS]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ corrupt
+PERCENT [CORRELATION]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ duplicate
+PERCENT [CORRELATION]]
+.B ]
+
+.B tc qdisc ... dev
+dev
+.B ] add netem [ reorder
+PRECENT [CORRELATION] [ gap DISTANCE ]]
+.B ]
+
+.SH DESCRIPTION
+NetEm is an enhancment of the Linux traffic control facilities
+that allow to add delay, packet loss, duplication and more other
+characteristics to packets outgoing from a selected network
+interface. NetEm is build using the existing Quality Of Service (QOS)
+and Differentiated Services (diffserv) facilities in the Linux
+kernel.
+
+.SH netem OPTIONS
+netem has the following options:
+
+.B limit
+packets
+
+limits the effect of selected options to the indicated number of next
packets.
+
+.B logging
+LEVEL
+
+sets a logging level. Actually it works with loss_GI, loss_GI_tran,
loss_bern, loss_gilb, loss_gilbell, loss_pattern options. If not
specified, level 0 will be used, then no data will be logged. When
logging level is set to 1 the kernel logs will include, for each loss
event, a line like "netem loss event algorithm [type] x RFPLE y" where
RFPLE stands for "Received From Previous Loss Event" and it counts the
number y of good packets received between two loss events while x is the
number of all lost packets and algorithm refers to the selected loss
generation algorithm (GI, gilbell or deterministic). The type label
applies only to the GI algorithm and can be burst or isolated.
+
+.B delay
+TIME [ JITTER [CORRELATION]]]
+
+adds the chosen delay to the packets outgoing to chosen network
interface. The optional parameters allows to introduce a delay variation
and a correlation. Delay and jitter values are expressed in ms while
correlation is percentage.
+
+.B distribution
+{uniform|normal|pareto|paretonormal}
+
+allow the choose the delay distribution. If not specified, the default
distribution is normal. Additional parameters allow to consider
situations in which network has variable delays depending on traffic
flows concurring on the same path, that causes severeal delay peaks and
a tail.
+
+.B drop
+PERCENT [CORRELATION]
+
+OR
+
+.B loss
+PERCENT [CORRELATION]
+
+using drop or loss is the same. It adds the chosen independent loss
probability to packets outgoing from the chosen network interface. It is
also possibile to add a correlation, through the proper parameter.
However this option is now deprecated due to the noticed bad behaviour.
To have introduce independent packet losses, which corresponds to the
Bernoulli loss model, please use the loss_bern option.
+
+.B query
+
+enables the query mode. It works with loss_GI, loss_GI_tran, loss_bern,
loss_gilb, loss_gilbell options. When the query mode is enabled and one
of the supported options are selected, the correspondent transition
probabilities and GI parameters are calculated and printed to screen
without passing the parameters to the qdisc. So this option works like a
parameters converter. If the option is not specified the query mode will
be disabled, then the parameters will be regularly passed to the netem
qdisc.
+
+.B loss_GI
+ploss [burst_length [density [pisol [good_burst_length]]]]
+
+adds packet losses according to the GI (General and Intuitive) loss
model, using the intuitive parameters. The parameter ploss is mandatory
and if used alone corresponds to the Bernoulli model while the optional
parameters allows to extend the model to 2-state (burst_length), 3-state
(density), and 4-state (pisol). If the good_burst_length is not
specified the hyphotesis of statistical independence for the losses
within the burst will be used.
+
+.B loss_GI_tran
+p13 p31 [p32 p23 [p14]]
+
+adds packet losses according to the GI (General and Intuitive) loss
model, using the 4-state Markov transition probabilities as input
parameters. The first two parameters p13 and p31 are mandatory and if
used alone corresponds to a 2-state model while the optional parameters
allows to extend the model to 3-state (p23 and p32) and 4-state (p14).
State 1 corresponds to good reception, State 4 to independent losses,
State 3 to burst losses and State 2 to good reception within a burst.
+
+.B loss_bern
+p
+
+adds packet losses according to the Bernoulli loss model. Allows to
introduce, through the p parameter, an independent loss probability to
packets outgoing from chosen network interface. This option is
equivalent to the now deprecated drop / loss
+option used without the correlation parameter.
+
+.B loss_gilb
+p r [1-h]
+
+adds packet losses according to the Gilbert loss model through the two
mandatory parameters p and r and the optional 1-h. This model has two
states: "good" and "bad". If only the mandatory parameters are
specified, the Simple Gilbert model will be used, while to use the full
Gilbert model it is needed to specify the whole set of three parameters.
+
+.B loss_gilbell
+p r [1-h [1-k]]
+
+adds packet losses according to the Gilbert-Elliot loss model through
the two mandatory parameters p and r and the optional 1-h and 1-k where
1-k is an independent loss probability in the "good" state while 1-h is
the loss density within the "bad" state. This model is a more general
version of the Gilbert model.
+
+.B loss_pattern
+FILENAME [REPETITIONS]
+
+adds packet losses according to a deterministic loss pattern. It reads
from the text file FILENAME a sequence of "1" and "0" where "1" are the
loss events and "0" are the regular transmission of packets . The
parameter repetitions is optional and is the number of "replicas" of the
loss pattern file. It is optional and by default is 0 which means
infinite repetition of the loss pattern.
+
+.B corrupt
+PERCENT [CORRELATION]]
+
+allows the emulate the random noise introducing an error in a random
position for a chosen percent of packets. It is also possible to add a
correlation through the proper parameter.
+
+.B duplicate
+PERCENT [CORRELATION]]
+
+using this option the chosen percent of packets is duplicated before
queueing them. It is also possible to add a correlation through the
proper parameter.
+
+.B reorder
+PRECENT [CORRELATION] [ gap DISTANCE ]]
+
+there are two ways to use this option:
+
+.B reorder
+gap 5 10 ms
+
+in this first example every 5th (10th, 15th) packet is sent immediately
while other packets are delayed by 10 ms
+
+.B reorder
+25% 50%
+
+in this second example 25% of packets are sent immediately (with
correlation of 50%) while the other are delayed by 10 ms.
+
+.SH LIMITATIONS
+The main known limitation of Netem are related to timer granularity,
since Linux is not a real-time operating system; to the choice of
Pseudo-Random Number Generator (PRNG) and the original loss model.
+
+.SH SOURCES
+.TP
+o
+Hemminger S. , "Network Emulation with NetEm", Open Source Development
Lab, April 2005
(http://devresources.linux-foundation.org/shemminger/netem/LCA2005_paper.pdf)
+
+.TP
+o
+Netem page from Linux foundation,
(http://www.linuxfoundation.org/en/Net:Netem)
+
+.TP
+o
+Salsano S., Ludovici F., Ordine A., "Definition of a general and
intuitive loss model for packet
+networks and its implementation in the Netem module in the Linux
kernel",
(http://netgroup.uniroma2.it/twiki/pub/Main/netem2/TR-loss-netem.pdf)
+
+
+.SH SEE ALSO
+.BR tc (8)
+
+.SH AUTHOR
+Netem was written by Stephen Hemminger at OSDL and is based on NISTnet.
This manpage was created by Fabio Ludovici <fabio.ludovici AT yahoo DOT
it>.
+
+
--
1.6.3.3
--
Fabio Ludovici
^ permalink raw reply related [flat|nested] 5+ messages in thread