[sr-dev] git:master:b103fefd: dispatcher: latency fix stdev calculation

[Julien Chavanton]

Module: kamailio
Branch: master
Commit: b103fefdd871af95c3f7e1ac7b1605b5ea5b402a
URL: https://github.com/kamailio/kamailio/commit/b103fefdd871af95c3f7e1ac7b1605b5ea5b402a

Author: Julien Chavanton <jchavanton at gmail.com>
Committer: Julien Chavanton <jchavanton at gmail.com>
Date: 2017-09-16T07:38:30-07:00

dispatcher: latency fix stdev calculation

- adding linking to lm library

---

Modified: src/modules/dispatcher/Makefile
Modified: src/modules/dispatcher/dispatch.c
Modified: src/modules/dispatcher/dispatch.h

---

Diff:  https://github.com/kamailio/kamailio/commit/b103fefdd871af95c3f7e1ac7b1605b5ea5b402a.diff
Patch: https://github.com/kamailio/kamailio/commit/b103fefdd871af95c3f7e1ac7b1605b5ea5b402a.patch

---

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_algorithm */
 	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;