Module: kamailio Branch: master Commit: cb0869db90c3e808dcd2f0a06d24544e32e26802 URL: https://github.com/kamailio/kamailio/commit/cb0869db90c3e808dcd2f0a06d24544… Author: Daniel-Constantin Mierla &lt;miconda(a)gmail.com&gt; Committer: GitHub &lt;noreply(a)github.com&gt; Date: 2017-09-17T10:05:13+02:00 Merge pull request #1236 from jchavanton/dispatcher_latency_fix dispatcher: latency fix stdev calculation --- Modified: src/modules/dispatcher/Makefile Modified: src/modules/dispatcher/dispatch.c Modified: src/modules/dispatcher/dispatch.h --- Diff: https://github.com/kamailio/kamailio/commit/cb0869db90c3e808dcd2f0a06d24544… Patch: https://github.com/kamailio/kamailio/commit/cb0869db90c3e808dcd2f0a06d24544… --- diff --git a/src/modules/dispatcher/Makefile b/src/modules/dispatcher/Makefile index 66520636d7..16ca65c34f 100644 --- a/src/modules/dispatcher/Makefile +++ b/src/modules/dispatcher/Makefile @@ -9,7 +9,7 @@ include ../../Makefile.defs auto_gen= NAME=dispatcher.so -LIBS= +LIBS=-lm DEFS+=-DKAMAILIO_MOD_INTERFACE diff --git a/src/modules/dispatcher/dispatch.c b/src/modules/dispatcher/dispatch.c index 04354476f9..a8ec1fd15b 100644 --- a/src/modules/dispatcher/dispatch.c +++ b/src/modules/dispatcher/dispatch.c @@ -2274,15 +2274,16 @@ int ds_mark_dst(struct sip_msg *msg, int state) return (ret == 0) ? 1 : -1; } - static inline void latency_stats_update(ds_latency_stats_t *latency_stats, int latency) { - float current_average, current_q; - /* after 2^21 smaples, ~24 days at 1s interval, the average becomes weighted moving average */ - if (latency_stats->count < 2097152) + /* after 2^21 ~24 days at 1s interval, the average becomes a weighted average */ + if (latency_stats->count < 2097152) { latency_stats->count++; + } else { /* We adjust the sum of squares used by the oneline algorithm proportionally */ + latency_stats->m2 -= latency_stats->m2/latency_stats->count; + } if (latency_stats->count == 1) { latency_stats->stdev = 0.0f; - latency_stats->last_q = 0.0f; + latency_stats->m2 = 0.0f; latency_stats->max = latency; latency_stats->min = latency; latency_stats->average = latency; @@ -2293,13 +2294,14 @@ static inline void latency_stats_update(ds_latency_stats_t *latency_stats, int l if (latency_stats->max < latency) latency_stats->max = latency; - /* standard deviation of the average/weighted moving average */ + /* standard deviation using oneline algorithm */ + /* https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_al… */ if (latency_stats->count > 1) { - current_average = latency_stats->average + (latency - latency_stats->average) / latency_stats->count; - current_q = latency_stats->last_q + (latency - latency_stats->average)*(latency - current_average); - latency_stats->average = current_average; - latency_stats->last_q = current_q; - latency_stats->stdev = sqrt(current_q/(latency_stats->count-1)); + float delta = latency - latency_stats->average; + latency_stats->average += delta/latency_stats->count; + float delta2 = latency - latency_stats->average; + latency_stats->m2 += delta*delta2; + latency_stats->stdev = sqrt(latency_stats->m2 / (latency_stats->count-1)); } /* exponentialy weighted moving average */ if (latency_stats->count < 10) { diff --git a/src/modules/dispatcher/dispatch.h b/src/modules/dispatcher/dispatch.h index fe03d6d379..419e7dcc5d 100644 --- a/src/modules/dispatcher/dispatch.h +++ b/src/modules/dispatcher/dispatch.h @@ -163,7 +163,7 @@ typedef struct _ds_latency_stats { float average; // weigthed average, estimate of the last few weeks float stdev; // last standard deviation float estimate; // short term estimate, EWMA exponential weighted moving average - float last_q; // q for N-1 + double m2; // sum of squares, used for recursive variance calculation int32_t count; uint32_t timeout; } ds_latency_stats_t;