linuxptp-devel

[Linuxptp-devel] [PATCH RFC 1/6] clock: save delay timestamps and correction.

[Miroslav L. <mli...@re...>]

Signed-off-by: Miroslav Lichvar <mli...@re...>
---
 clock.c | 22 ++++++++++++++++++----
 clock.h |  5 ++++-
 port.c  |  3 ++-
 3 files changed, 24 insertions(+), 6 deletions(-)

diff --git a/clock.c b/clock.c
index b841e81..9bc0352 100644
--- a/clock.c
+++ b/clock.c
@@ -108,8 +108,11 @@ struct clock {
 	double nrr;
 	tmv_t c1;
 	tmv_t c2;
+	tmv_t c3;
 	tmv_t t1;
 	tmv_t t2;
+	tmv_t t3;
+	tmv_t t4;
 	struct clock_description desc;
 	struct clock_stats stats;
 	int stats_interval;
@@ -1295,16 +1298,20 @@ void clock_path_delay(struct clock *c, struct timespec req, struct timestamp rx,
 	tmv_t c1, c2, c3, pd, t1, t2, t3, t4;
 	double rr;
 
+	c->t3 = timespec_to_tmv(req);
+	c->t4 = timestamp_to_tmv(rx);
+	c->c3 = correction_to_tmv(correction);
+
 	if (tmv_is_zero(c->t1))
 		return;
 
 	c1 = c->c1;
 	c2 = c->c2;
-	c3 = correction_to_tmv(correction);
+	c3 = c->c3;
 	t1 = c->t1;
 	t2 = c->t2;
-	t3 = timespec_to_tmv(req);
-	t4 = timestamp_to_tmv(rx);
+	t3 = c->t3;
+	t4 = c->t4;
 	rr = clock_rate_ratio(c);
 
 	/*
@@ -1341,10 +1348,13 @@ void clock_path_delay(struct clock *c, struct timespec req, struct timestamp rx,
 		stats_add_value(c->stats.delay, tmv_to_nanoseconds(pd));
 }
 
-void clock_peer_delay(struct clock *c, tmv_t ppd, double nrr)
+void clock_peer_delay(struct clock *c, tmv_t ppd, tmv_t req, tmv_t rx,
+		      double nrr)
 {
 	c->path_delay = ppd;
 	c->nrr = nrr;
+	c->t3 = req;
+	c->t4 = rx;
 
 	if (c->stats.delay)
 		stats_add_value(c->stats.delay, tmv_to_nanoseconds(ppd));
@@ -1453,6 +1463,8 @@ enum servo_state clock_synchronize(struct clock *c,
 		clockadj_step(c->clkid, -tmv_to_nanoseconds(c->master_offset));
 		c->t1 = tmv_zero();
 		c->t2 = tmv_zero();
+		c->t3 = tmv_zero();
+		c->t4 = tmv_zero();
 		if (c->sanity_check) {
 			clockcheck_set_freq(c->sanity_check, -adj);
 			clockcheck_step(c->sanity_check,
@@ -1534,6 +1546,8 @@ static void handle_state_decision_event(struct clock *c)
 		filter_reset(c->delay_filter);
 		c->t1 = tmv_zero();
 		c->t2 = tmv_zero();
+		c->t3 = tmv_zero();
+		c->t4 = tmv_zero();
 		c->path_delay = 0;
 		c->nrr = 1.0;
 		fresh_best = 1;
diff --git a/clock.h b/clock.h
index 4834464..b3a5c9f 100644
--- a/clock.h
+++ b/clock.h
@@ -179,9 +179,12 @@ void clock_path_delay(struct clock *c, struct timespec req, struct timestamp rx,
  * Provide the estimated peer delay from a slave port.
  * @param c           The clock instance.
  * @param ppd         The peer delay as measured on a slave port.
+ * @param req         The transmission time of the pdelay request message.
+ * @param rx          The reception time of the pdelay request message.
  * @param nrr         The neighbor rate ratio as measured on a slave port.
  */
-void clock_peer_delay(struct clock *c, tmv_t ppd, double nrr);
+void clock_peer_delay(struct clock *c, tmv_t ppd, tmv_t req, tmv_t rx,
+		      double nrr);
 
 /**
  * Poll for events and dispatch them.
diff --git a/port.c b/port.c
index 18a956d..7f9aa3d 100644
--- a/port.c
+++ b/port.c
@@ -1854,7 +1854,8 @@ calc:
 		port_nrate_calculate(p, t3, t4, tmv_add(c1, c2));
 
 	if (p->state == PS_UNCALIBRATED || p->state == PS_SLAVE) {
-		clock_peer_delay(p->clock, p->peer_delay, p->nrate.ratio);
+		clock_peer_delay(p->clock, p->peer_delay, t1, t2,
+				 p->nrate.ratio);
 	}
 
 	msg_put(p->peer_delay_req);
-- 
2.1.0

[Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Miroslav L. <mli...@re...>]

These patches should improve the synchronization of the clock with
larger jitters, e.g. with software timestamping, wireless networks,
etc.

The idea is to give smaller weights to samples where the sync and/or
delay messages were delayed significantly in the network and possibly
include a large error. The sample offset is based directly on the
sample delay instead of the long-term filtered delay and the sample
weight is set to the ratio of the sample delay to the long-term
average. E.g. if the measured delay is normally 1 ms and the new
sample has 10ms delay, the sample weight (and the clock adjustment
that will be made) will be 10 times smaller.

This "weighting" mode is enabled only when the sync interval is equal
or longer than the delay/pdelay request interval to not reuse the
delay timestamps too many times and keep the interval between sample
times stable. In some tests I saw an improvement also with 2:1
sync/delay rate and maybe even higher, but it would probably be tricky
to implement if it should be enabled automatically, possibly requiring
some cooperation with the delay filter.

In my testing I did so far it seems to work nicely. With the linreg
servo there should be no regression. With PI there can be worse
performance observed when the constants are not configured properly,
that is when the servo is too slow to track the frequency changes and
weighted samples make it even slower. Currently, the weighting mode is
enabled only when ki <= 0.01 to include the default SW timestamping
constant and not the HW constant. It could be always enabled or I
could add an option to override it if you think it would be useful,
I'm not sure.

What do you think? Does this make sense?


Miroslav Lichvar (6):
  clock: save delay timestamps and correction.
  clock: split out calculation of sample delay.
  servo: add support for weighted samples.
  clock: set sample weight.
  linreg: use sample weight.
  pi: use sample weight.

 clock.c         | 85 ++++++++++++++++++++++++++++++++++++++++++++-------------
 clock.h         | 10 +++++--
 linreg.c        | 64 +++++++++++++++++++++++++++++--------------
 ntpshm.c        |  1 +
 phc2sys.c       |  2 +-
 pi.c            | 20 ++++++++++++--
 port.c          | 10 +++++--
 servo.c         | 11 +++++++-
 servo.h         | 10 +++++++
 servo_private.h |  4 ++-
 10 files changed, 169 insertions(+), 48 deletions(-)

-- 
2.1.0

[Linuxptp-devel] [PATCH RFC 2/6] clock: split out calculation of sample delay.

[Miroslav L. <mli...@re...>]

Signed-off-by: Miroslav Lichvar <mli...@re...>
---
 clock.c | 33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)

diff --git a/clock.c b/clock.c
index 9bc0352..d42d604 100644
--- a/clock.c
+++ b/clock.c
@@ -1292,19 +1292,11 @@ int clock_poll(struct clock *c)
 	return 0;
 }
 
-void clock_path_delay(struct clock *c, struct timespec req, struct timestamp rx,
-		      Integer64 correction)
+static tmv_t clock_get_sample_delay(struct clock *c)
 {
 	tmv_t c1, c2, c3, pd, t1, t2, t3, t4;
 	double rr;
 
-	c->t3 = timespec_to_tmv(req);
-	c->t4 = timestamp_to_tmv(rx);
-	c->c3 = correction_to_tmv(correction);
-
-	if (tmv_is_zero(c->t1))
-		return;
-
 	c1 = c->c1;
 	c2 = c->c2;
 	c3 = c->c3;
@@ -1315,9 +1307,9 @@ void clock_path_delay(struct clock *c, struct timespec req, struct timestamp rx,
 	rr = clock_rate_ratio(c);
 
 	/*
-	 * c->path_delay = (t2 - t3) * rr + (t4 - t1);
-	 * c->path_delay -= c_sync + c_fup + c_delay_resp;
-	 * c->path_delay /= 2.0;
+	 * pd = (t2 - t3) * rr + (t4 - t1);
+	 * pd -= c_sync + c_fup + c_delay_resp;
+	 * pd /= 2.0;
 	 */
 
 	pd = tmv_sub(t2, t3);
@@ -1338,6 +1330,23 @@ void clock_path_delay(struct clock *c, struct timespec req, struct timestamp rx,
 		pr_debug("c3 %10" PRId64, c3);
 	}
 
+	return pd;
+}
+
+void clock_path_delay(struct clock *c, struct timespec req, struct timestamp rx,
+		      Integer64 correction)
+{
+	tmv_t pd;
+
+	c->t3 = timespec_to_tmv(req);
+	c->t4 = timestamp_to_tmv(rx);
+	c->c3 = correction_to_tmv(correction);
+
+	if (tmv_is_zero(c->t1))
+		return;
+
+	pd = clock_get_sample_delay(c);
+
 	c->path_delay = filter_sample(c->delay_filter, pd);
 
 	c->cur.meanPathDelay = tmv_to_TimeInterval(c->path_delay);
-- 
2.1.0

[Linuxptp-devel] [PATCH RFC 4/6] clock: set sample weight.

[Miroslav L. <mli...@re...>]

If there is (on average) at least one delay message for every sync
message and the servo prefers weighted samples, use the sample delay
directly instead of the long-term filtered delay and set the weight of
the sample to the ratio of the two delays.

Signed-off-by: Miroslav Lichvar <mli...@re...>
---
 clock.c | 38 +++++++++++++++++++++++++++++++-------
 clock.h |  5 ++++-
 port.c  |  7 ++++++-
 3 files changed, 41 insertions(+), 9 deletions(-)

diff --git a/clock.c b/clock.c
index 64ce562..acf159b 100644
--- a/clock.c
+++ b/clock.c
@@ -1418,10 +1418,11 @@ enum servo_state clock_synchronize(struct clock *c,
 				   struct timespec ingress_ts,
 				   struct timestamp origin_ts,
 				   Integer64 correction1,
-				   Integer64 correction2)
+				   Integer64 correction2,
+				   int sync_delay_rate)
 {
-	double adj;
-	tmv_t ingress, origin;
+	double adj, weight;
+	tmv_t ingress, origin, sample_delay;
 	enum servo_state state = SERVO_UNLOCKED;
 
 	ingress = timespec_to_tmv(ingress_ts);
@@ -1433,15 +1434,38 @@ enum servo_state clock_synchronize(struct clock *c,
 	c->c1 = correction_to_tmv(correction1);
 	c->c2 = correction_to_tmv(correction2);
 
+	if (!c->path_delay)
+		return state;
+
+	weight = 1.0;
+
+	/*
+	 * If there is (on average) at least one delay message for every sync
+	 * message and the servo prefers weighted samples, use the sample delay
+	 * directly instead of the long-term filtered delay and set the weight
+	 * of the sample to the ratio of the two delays.
+	 */
+	if (sync_delay_rate <= 0 && servo_weight_samples(c->servo)) {
+		/* Get new sample delay with updated t1 and t2 */
+		sample_delay = clock_get_sample_delay(c);
+
+		if (sample_delay > 0 && c->path_delay > 0) {
+			weight = (double)c->path_delay / sample_delay;
+			if (weight > 1.0)
+				weight = 1.0;
+			pr_debug("delay sample %9" PRId64 " filtered %9" PRId64
+				 " weight %f",
+				 sample_delay, c->path_delay, weight);
+			c->path_delay = sample_delay;
+		}
+	}
+
 	/*
 	 * c->master_offset = ingress - origin - c->path_delay - c->c1 - c->c2;
 	 */
 	c->master_offset = tmv_sub(ingress,
 		tmv_add(origin, tmv_add(c->path_delay, tmv_add(c->c1, c->c2))));
 
-	if (!c->path_delay)
-		return state;
-
 	if (clock_utc_correct(c, ingress))
 		return c->servo_state;
 
@@ -1451,7 +1475,7 @@ enum servo_state clock_synchronize(struct clock *c,
 		return clock_no_adjust(c);
 
 	adj = servo_sample(c->servo, tmv_to_nanoseconds(c->master_offset),
-			   tmv_to_nanoseconds(ingress), 1.0, &state);
+			   tmv_to_nanoseconds(ingress), weight, &state);
 	c->servo_state = state;
 
 	if (c->stats.max_count > 1) {
diff --git a/clock.h b/clock.h
index b3a5c9f..a5a70d3 100644
--- a/clock.h
+++ b/clock.h
@@ -223,13 +223,16 @@ int clock_switch_phc(struct clock *c, int phc_index);
  * @param correction1  The correction field of the sync message.
  * @param correction2  The correction field of the follow up message.
  *                     Pass zero in the case of one step operation.
+ * @param sync_delay_rate The number of expected sync messages per delay
+ *                     message, as a power of two.
  * @return             The state of the clock's servo.
  */
 enum servo_state clock_synchronize(struct clock *c,
 				   struct timespec ingress_ts,
 				   struct timestamp origin_ts,
 				   Integer64 correction1,
-				   Integer64 correction2);
+				   Integer64 correction2,
+				   int sync_delay_rate);
 
 /**
  * Inform a slaved clock about the master's sync interval.
diff --git a/port.c b/port.c
index 7f9aa3d..8cf52f7 100644
--- a/port.c
+++ b/port.c
@@ -1012,11 +1012,16 @@ static void port_synchronize(struct port *p,
 			     Integer64 correction1, Integer64 correction2)
 {
 	enum servo_state state;
+	int sync_delay_rate;
 
 	port_set_sync_rx_tmo(p);
 
+	sync_delay_rate = (p->delayMechanism == DM_P2P ?
+			   p->logMinPdelayReqInterval :
+			   p->logMinDelayReqInterval) - p->logSyncInterval;
+
 	state = clock_synchronize(p->clock, ingress_ts, origin_ts,
-				  correction1, correction2);
+				  correction1, correction2, sync_delay_rate);
 	switch (state) {
 	case SERVO_UNLOCKED:
 		port_dispatch(p, EV_SYNCHRONIZATION_FAULT, 0);
-- 
2.1.0

[Linuxptp-devel] [PATCH RFC 3/6] servo: add support for weighted samples.

[Miroslav L. <mli...@re...>]

Add weight parameter to the sample function and add a new function to
check if the servo prefers weighted (and more noisy) samples. Samples
with smaller weight are less reliable, they can be ignored or the
adjustments of the clock can be smaller.

Signed-off-by: Miroslav Lichvar <mli...@re...>
---
 clock.c         |  2 +-
 linreg.c        |  1 +
 ntpshm.c        |  1 +
 phc2sys.c       |  2 +-
 pi.c            |  1 +
 servo.c         | 11 ++++++++++-
 servo.h         | 10 ++++++++++
 servo_private.h |  4 +++-
 8 files changed, 28 insertions(+), 4 deletions(-)

diff --git a/clock.c b/clock.c
index d42d604..64ce562 100644
--- a/clock.c
+++ b/clock.c
@@ -1451,7 +1451,7 @@ enum servo_state clock_synchronize(struct clock *c,
 		return clock_no_adjust(c);
 
 	adj = servo_sample(c->servo, tmv_to_nanoseconds(c->master_offset),
-			   tmv_to_nanoseconds(ingress), &state);
+			   tmv_to_nanoseconds(ingress), 1.0, &state);
 	c->servo_state = state;
 
 	if (c->stats.max_count > 1) {
diff --git a/linreg.c b/linreg.c
index fde604d..3f7fe9a 100644
--- a/linreg.c
+++ b/linreg.c
@@ -209,6 +209,7 @@ static int get_best_size(struct linreg_servo *s)
 static double linreg_sample(struct servo *servo,
 			    int64_t offset,
 			    uint64_t local_ts,
+			    double weight,
 			    enum servo_state *state)
 {
 	struct linreg_servo *s = container_of(servo, struct linreg_servo, servo);
diff --git a/ntpshm.c b/ntpshm.c
index 21a11cf..8b18e2d 100644
--- a/ntpshm.c
+++ b/ntpshm.c
@@ -80,6 +80,7 @@ static void ntpshm_destroy(struct servo *servo)
 static double ntpshm_sample(struct servo *servo,
 			    int64_t offset,
 			    uint64_t local_ts,
+			    double weight,
 			    enum servo_state *state)
 {
 	struct ntpshm_servo *s = container_of(servo, struct ntpshm_servo, servo);
diff --git a/phc2sys.c b/phc2sys.c
index 23993ac..9ff5bf9 100644
--- a/phc2sys.c
+++ b/phc2sys.c
@@ -469,7 +469,7 @@ static void update_clock(struct node *node, struct clock *clock,
 	if (clock->sanity_check && clockcheck_sample(clock->sanity_check, ts))
 		servo_reset(clock->servo);
 
-	ppb = servo_sample(clock->servo, offset, ts, &state);
+	ppb = servo_sample(clock->servo, offset, ts, 1.0, &state);
 	clock->servo_state = state;
 
 	switch (state) {
diff --git a/pi.c b/pi.c
index c8b8587..9c7b148 100644
--- a/pi.c
+++ b/pi.c
@@ -64,6 +64,7 @@ static void pi_destroy(struct servo *servo)
 static double pi_sample(struct servo *servo,
 			int64_t offset,
 			uint64_t local_ts,
+			double weight,
 			enum servo_state *state)
 {
 	struct pi_servo *s = container_of(servo, struct pi_servo, servo);
diff --git a/servo.c b/servo.c
index f200f75..38a5729 100644
--- a/servo.c
+++ b/servo.c
@@ -75,14 +75,23 @@ void servo_destroy(struct servo *servo)
 	servo->destroy(servo);
 }
 
+int servo_weight_samples(struct servo *servo)
+{
+	if (servo->weight_samples)
+		return servo->weight_samples(servo);
+
+	return 0;
+}
+
 double servo_sample(struct servo *servo,
 		    int64_t offset,
 		    uint64_t local_ts,
+		    double weight,
 		    enum servo_state *state)
 {
 	double r;
 
-	r = servo->sample(servo, offset, local_ts, state);
+	r = servo->sample(servo, offset, local_ts, weight, state);
 
 	if (*state != SERVO_UNLOCKED)
 		servo->first_update = 0;
diff --git a/servo.h b/servo.h
index e054501..12eb249 100644
--- a/servo.h
+++ b/servo.h
@@ -100,16 +100,26 @@ struct servo *servo_create(enum servo_type type, int fadj, int max_ppb, int sw_t
 void servo_destroy(struct servo *servo);
 
 /**
+ * Check if a clock servo prefers weighted samples.
+ * @param servo    Pointer to a servo obtained via @ref servo_create().
+ * @return         1 if yes, 0 otherwise.
+ */
+int servo_weight_samples(struct servo *servo);
+
+/**
  * Feed a sample into a clock servo.
  * @param servo     Pointer to a servo obtained via @ref servo_create().
  * @param offset    The estimated clock offset in nanoseconds.
  * @param local_ts  The local time stamp of the sample in nanoseconds.
+ * @param weight    The weight of the sample, larger if more reliable,
+ *                  1.0 is the maximum value.
  * @param state     Returns the servo's state.
  * @return The clock adjustment in parts per billion.
  */
 double servo_sample(struct servo *servo,
 		    int64_t offset,
 		    uint64_t local_ts,
+		    double weight,
 		    enum servo_state *state);
 
 /**
diff --git a/servo_private.h b/servo_private.h
index 9a1a459..b98e7e7 100644
--- a/servo_private.h
+++ b/servo_private.h
@@ -29,8 +29,10 @@ struct servo {
 
 	void (*destroy)(struct servo *servo);
 
+	int (*weight_samples)(struct servo *servo);
+
 	double (*sample)(struct servo *servo,
-			 int64_t offset, uint64_t local_ts,
+			 int64_t offset, uint64_t local_ts, double weight,
 			 enum servo_state *state);
 
 	void (*sync_interval)(struct servo *servo, double interval);
-- 
2.1.0

[Linuxptp-devel] [PATCH RFC 5/6] linreg: use sample weight.

[Miroslav L. <mli...@re...>]

Signed-off-by: Miroslav Lichvar <mli...@re...>
---
 linreg.c | 63 +++++++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 43 insertions(+), 20 deletions(-)

diff --git a/linreg.c b/linreg.c
index 3f7fe9a..e2915c5 100644
--- a/linreg.c
+++ b/linreg.c
@@ -42,6 +42,7 @@
 struct point {
 	uint64_t x;
 	uint64_t y;
+	double w;
 };
 
 struct result {
@@ -70,6 +71,8 @@ struct linreg_servo {
 	uint64_t last_update;
 	/* Regression results for all sizes */
 	struct result results[MAX_SIZE - MIN_SIZE + 1];
+	/* Selected size */
+	unsigned int size;
 	/* Current frequency offset of the clock */
 	double clock_freq;
 	/* Expected interval between updates */
@@ -120,12 +123,13 @@ static void update_reference(struct linreg_servo *s, uint64_t local_ts)
 	s->last_update = local_ts;
 }
 
-static void add_sample(struct linreg_servo *s, int64_t offset)
+static void add_sample(struct linreg_servo *s, int64_t offset, double weight)
 {
 	s->last_point = (s->last_point + 1) % MAX_POINTS;
 
 	s->points[s->last_point].x = s->reference.x;
 	s->points[s->last_point].y = s->reference.y - offset;
+	s->points[s->last_point].w = weight;
 
 	if (s->num_points < MAX_POINTS)
 		s->num_points++;
@@ -133,11 +137,12 @@ static void add_sample(struct linreg_servo *s, int64_t offset)
 
 static void regress(struct linreg_servo *s)
 {
-	double x, y, y0, e, x_sum, y_sum, xy_sum, x2_sum;
+	double x, y, y0, e, x_sum, y_sum, xy_sum, x2_sum, w, w_sum, w2_sum;
 	unsigned int i, l, n, size;
 	struct result *res;
 
 	x_sum = 0.0, y_sum = 0.0, xy_sum = 0.0, x2_sum = 0.0;
+	w_sum = 0.0; w2_sum = 0.0;
 	i = 0;
 
 	y0 = (int64_t)(s->points[s->last_point].y - s->reference.y);
@@ -169,27 +174,31 @@ static void regress(struct linreg_servo *s)
 
 			x = (int64_t)(s->points[l].x - s->reference.x);
 			y = (int64_t)(s->points[l].y - s->reference.y);
-
-			x_sum += x;
-			y_sum += y;
-			xy_sum += x * y;
-			x2_sum += x * x;
+			w = s->points[l].w;
+
+			x_sum += x * w;
+			y_sum += y * w;
+			xy_sum += x * y * w;
+			x2_sum += x * x * w;
+			w_sum += w;
+			w2_sum += w * w;
 		}
 
 		/* Get new intercept and slope */
-		res->slope = (xy_sum - x_sum * y_sum / n) /
-				(x2_sum - x_sum * x_sum / n);
-		res->intercept = (y_sum - res->slope * x_sum) / n;
+		res->slope = (xy_sum - x_sum * y_sum / w_sum) /
+				(x2_sum - x_sum * x_sum / w_sum);
+		res->intercept = (y_sum - res->slope * x_sum) / w_sum;
 	}
 }
 
-/* Return largest size with smallest prediction error */
-static int get_best_size(struct linreg_servo *s)
+static void update_size(struct linreg_servo *s)
 {
 	struct result *res;
 	double best_err;
 	int size, best_size;
 
+	/* Find largest size with smallest prediction error */
+
 	best_size = 0;
 	best_err = 0.0;
 
@@ -203,7 +212,19 @@ static int get_best_size(struct linreg_servo *s)
 		}
 	}
 
-	return best_size;
+	s->size = best_size;
+}
+
+static int linreg_weight_samples(struct servo *servo)
+{
+	struct linreg_servo *s = container_of(servo, struct linreg_servo, servo);
+
+	/*
+	 * When the minimum size is selected, assume it is still too large
+	 * (frequency is changing too quickly) and weighted samples would make
+	 * it even more difficult to track.
+	 */
+	return s->size > MIN_SIZE;
 }
 
 static double linreg_sample(struct servo *servo,
@@ -214,7 +235,7 @@ static double linreg_sample(struct servo *servo,
 {
 	struct linreg_servo *s = container_of(servo, struct linreg_servo, servo);
 	struct result *res;
-	int size, corr_interval;
+	int corr_interval;
 
 	/*
 	 * The current time and the time when will be the frequency of the
@@ -225,21 +246,21 @@ static double linreg_sample(struct servo *servo,
 	 */
 
 	update_reference(s, local_ts);
-	add_sample(s, offset);
+	add_sample(s, offset, weight);
 	regress(s);
 
-	size = get_best_size(s);
+	update_size(s);
 
-	if (size < MIN_SIZE) {
+	if (s->size < MIN_SIZE) {
 		/* Not enough points, wait for more */
 		*state = SERVO_UNLOCKED;
 		return -s->clock_freq;
 	}
 
-	res = &s->results[size - MIN_SIZE];
+	res = &s->results[s->size - MIN_SIZE];
 
 	pr_debug("linreg: points %d slope %.9f intercept %.0f err %.0f",
-			1 << size, res->slope, res->intercept, res->err);
+		 1 << s->size, res->slope, res->intercept, res->err);
 
 	if ((servo->first_update &&
 	     servo->first_step_threshold &&
@@ -265,7 +286,7 @@ static double linreg_sample(struct servo *servo,
 	 * correction slowing down the clock will result in an overshoot. With
 	 * the system clock's maximum adjustment of 10% that's acceptable.
 	 */
-	corr_interval = size <= 4 ? 1 : size / 2;
+	corr_interval = s->size <= 4 ? 1 : s->size / 2;
 	s->clock_freq += res->intercept / s->update_interval / corr_interval;
 
 	/* Clamp the frequency to the allowed maximum */
@@ -293,6 +314,7 @@ static void linreg_reset(struct servo *servo)
 
 	s->num_points = 0;
 	s->last_update = 0;
+	s->size = 0;
 	s->frequency_ratio = 1.0;
 
 	for (i = MIN_SIZE; i <= MAX_SIZE; i++) {
@@ -331,6 +353,7 @@ struct servo *linreg_servo_create(int fadj)
 		return NULL;
 
 	s->servo.destroy = linreg_destroy;
+	s->servo.weight_samples = linreg_weight_samples;
 	s->servo.sample = linreg_sample;
 	s->servo.sync_interval = linreg_sync_interval;
 	s->servo.reset = linreg_reset;
-- 
2.1.0

[Linuxptp-devel] [PATCH RFC 6/6] pi: use sample weight.

[Miroslav L. <mli...@re...>]

Signed-off-by: Miroslav Lichvar <mli...@re...>
---
 pi.c | 19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)

diff --git a/pi.c b/pi.c
index 9c7b148..a8c6051 100644
--- a/pi.c
+++ b/pi.c
@@ -61,6 +61,20 @@ static void pi_destroy(struct servo *servo)
 	free(s);
 }
 
+static int pi_weight_samples(struct servo *servo)
+{
+	struct pi_servo *s = container_of(servo, struct pi_servo, servo);
+
+	if (s->count < 2)
+		return 0;
+
+	/*
+	 * Enable weights approximately at half way between default ki
+	 * values for HW and SW time stamping.
+	 */
+	return s->ki <= 0.01;
+}
+
 static double pi_sample(struct servo *servo,
 			int64_t offset,
 			uint64_t local_ts,
@@ -137,8 +151,8 @@ static double pi_sample(struct servo *servo,
 			break;
 		}
 
-		ki_term = s->ki * offset;
-		ppb = s->kp * offset + s->drift + ki_term;
+		ki_term = s->ki * offset * weight;
+		ppb = s->kp * offset * weight + s->drift + ki_term;
 		if (ppb < -servo->max_frequency) {
 			ppb = -servo->max_frequency;
 		} else if (ppb > servo->max_frequency) {
@@ -186,6 +200,7 @@ struct servo *pi_servo_create(int fadj, int sw_ts)
 		return NULL;
 
 	s->servo.destroy = pi_destroy;
+	s->servo.weight_samples = pi_weight_samples;
 	s->servo.sample  = pi_sample;
 	s->servo.sync_interval = pi_sync_interval;
 	s->servo.reset   = pi_reset;
-- 
2.1.0

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Keller, J. E <jac...@in...>]

On Fri, 2015-02-13 at 13:56 +0100, Miroslav Lichvar wrote:
> These patches should improve the synchronization of the clock with
> larger jitters, e.g. with software timestamping, wireless networks,
> etc.
> 
> The idea is to give smaller weights to samples where the sync and/or
> delay messages were delayed significantly in the network and possibly
> include a large error. The sample offset is based directly on the
> sample delay instead of the long-term filtered delay and the sample
> weight is set to the ratio of the sample delay to the long-term
> average. E.g. if the measured delay is normally 1 ms and the new
> sample has 10ms delay, the sample weight (and the clock adjustment
> that will be made) will be 10 times smaller.
> 

This seems like a good idea, to help in the case where spiked delays
could cause swings which take a while to settle out. A bit like dropping
the outlying parameters.

> This "weighting" mode is enabled only when the sync interval is equal
> or longer than the delay/pdelay request interval to not reuse the
> delay timestamps too many times and keep the interval between sample
> times stable. In some tests I saw an improvement also with 2:1
> sync/delay rate and maybe even higher, but it would probably be tricky
> to implement if it should be enabled automatically, possibly requiring
> some cooperation with the delay filter.
> 
> In my testing I did so far it seems to work nicely. With the linreg
> servo there should be no regression. With PI there can be worse
> performance observed when the constants are not configured properly,
> that is when the servo is too slow to track the frequency changes and
> weighted samples make it even slower. Currently, the weighting mode is
> enabled only when ki <= 0.01 to include the default SW timestamping
> constant and not the HW constant. It could be always enabled or I
> could add an option to override it if you think it would be useful,
> I'm not sure.
> 
> What do you think? Does this make sense?
> 

I like the idea, but I confess you do know more about the clock than I
do.

Regards,
Jake

> 
> Miroslav Lichvar (6):
>   clock: save delay timestamps and correction.
>   clock: split out calculation of sample delay.
>   servo: add support for weighted samples.
>   clock: set sample weight.
>   linreg: use sample weight.
>   pi: use sample weight.
> 
>  clock.c         | 85 ++++++++++++++++++++++++++++++++++++++++++++-------------
>  clock.h         | 10 +++++--
>  linreg.c        | 64 +++++++++++++++++++++++++++++--------------
>  ntpshm.c        |  1 +
>  phc2sys.c       |  2 +-
>  pi.c            | 20 ++++++++++++--
>  port.c          | 10 +++++--
>  servo.c         | 11 +++++++-
>  servo.h         | 10 +++++++
>  servo_private.h |  4 ++-
>  10 files changed, 169 insertions(+), 48 deletions(-)
> 

Re: [Linuxptp-devel] [PATCH RFC 4/6] clock: set sample weight.

[Richard C. <ric...@gm...>]

On Fri, Feb 13, 2015 at 01:56:16PM +0100, Miroslav Lichvar wrote:
> If there is (on average) at least one delay message for every sync
> message and the servo prefers weighted samples, use the sample delay
> directly instead of the long-term filtered delay and set the weight of
> the sample to the ratio of the two delays.
> 
> Signed-off-by: Miroslav Lichvar <mli...@re...>
> ---
>  clock.c | 38 +++++++++++++++++++++++++++++++-------
>  clock.h |  5 ++++-
>  port.c  |  7 ++++++-
>  3 files changed, 41 insertions(+), 9 deletions(-)
> 
> diff --git a/clock.c b/clock.c
> index 64ce562..acf159b 100644
> --- a/clock.c
> +++ b/clock.c
> @@ -1418,10 +1418,11 @@ enum servo_state clock_synchronize(struct clock *c,
>  				   struct timespec ingress_ts,
>  				   struct timestamp origin_ts,
>  				   Integer64 correction1,
> -				   Integer64 correction2)
> +				   Integer64 correction2,
> +				   int sync_delay_rate)
>  {
> -	double adj;
> -	tmv_t ingress, origin;
> +	double adj, weight;
> +	tmv_t ingress, origin, sample_delay;
>  	enum servo_state state = SERVO_UNLOCKED;
>  
>  	ingress = timespec_to_tmv(ingress_ts);
> @@ -1433,15 +1434,38 @@ enum servo_state clock_synchronize(struct clock *c,
>  	c->c1 = correction_to_tmv(correction1);
>  	c->c2 = correction_to_tmv(correction2);
>  
> +	if (!c->path_delay)
> +		return state;
> +
> +	weight = 1.0;
> +
> +	/*
> +	 * If there is (on average) at least one delay message for every sync
> +	 * message and the servo prefers weighted samples, use the sample delay
> +	 * directly instead of the long-term filtered delay and set the weight
> +	 * of the sample to the ratio of the two delays.
> +	 */
> +	if (sync_delay_rate <= 0 && servo_weight_samples(c->servo)) {
> +		/* Get new sample delay with updated t1 and t2 */
> +		sample_delay = clock_get_sample_delay(c);
> +
> +		if (sample_delay > 0 && c->path_delay > 0) {
> +			weight = (double)c->path_delay / sample_delay;
> +			if (weight > 1.0)
> +				weight = 1.0;
> +			pr_debug("delay sample %9" PRId64 " filtered %9" PRId64
> +				 " weight %f",
> +				 sample_delay, c->path_delay, weight);
> +			c->path_delay = sample_delay;

So now, c->path_delay is set once in clock_path_delay() using
averaging, and here the averaged value is used for the ratio, but then
you clobber c->path_delay with the new value?

Your intention would be more clear if you would not set c->path_delay
here, but rather use a local variable.

Thanks
Richard

> +		}
> +	}
> +
>  	/*
>  	 * c->master_offset = ingress - origin - c->path_delay - c->c1 - c->c2;
>  	 */
>  	c->master_offset = tmv_sub(ingress,
>  		tmv_add(origin, tmv_add(c->path_delay, tmv_add(c->c1, c->c2))));
>  
> -	if (!c->path_delay)
> -		return state;
> -
>  	if (clock_utc_correct(c, ingress))
>  		return c->servo_state;
>  
> @@ -1451,7 +1475,7 @@ enum servo_state clock_synchronize(struct clock *c,
>  		return clock_no_adjust(c);
>  
>  	adj = servo_sample(c->servo, tmv_to_nanoseconds(c->master_offset),
> -			   tmv_to_nanoseconds(ingress), 1.0, &state);
> +			   tmv_to_nanoseconds(ingress), weight, &state);
>  	c->servo_state = state;
>  
>  	if (c->stats.max_count > 1) {
> diff --git a/clock.h b/clock.h
> index b3a5c9f..a5a70d3 100644
> --- a/clock.h
> +++ b/clock.h
> @@ -223,13 +223,16 @@ int clock_switch_phc(struct clock *c, int phc_index);
>   * @param correction1  The correction field of the sync message.
>   * @param correction2  The correction field of the follow up message.
>   *                     Pass zero in the case of one step operation.
> + * @param sync_delay_rate The number of expected sync messages per delay
> + *                     message, as a power of two.
>   * @return             The state of the clock's servo.
>   */
>  enum servo_state clock_synchronize(struct clock *c,
>  				   struct timespec ingress_ts,
>  				   struct timestamp origin_ts,
>  				   Integer64 correction1,
> -				   Integer64 correction2);
> +				   Integer64 correction2,
> +				   int sync_delay_rate);
>  
>  /**
>   * Inform a slaved clock about the master's sync interval.
> diff --git a/port.c b/port.c
> index 7f9aa3d..8cf52f7 100644
> --- a/port.c
> +++ b/port.c
> @@ -1012,11 +1012,16 @@ static void port_synchronize(struct port *p,
>  			     Integer64 correction1, Integer64 correction2)
>  {
>  	enum servo_state state;
> +	int sync_delay_rate;
>  
>  	port_set_sync_rx_tmo(p);
>  
> +	sync_delay_rate = (p->delayMechanism == DM_P2P ?
> +			   p->logMinPdelayReqInterval :
> +			   p->logMinDelayReqInterval) - p->logSyncInterval;
> +
>  	state = clock_synchronize(p->clock, ingress_ts, origin_ts,
> -				  correction1, correction2);
> +				  correction1, correction2, sync_delay_rate);
>  	switch (state) {
>  	case SERVO_UNLOCKED:
>  		port_dispatch(p, EV_SYNCHRONIZATION_FAULT, 0);
> -- 
> 2.1.0
> 
> 
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming. The Go Parallel Website,
> sponsored by Intel and developed in partnership with Slashdot Media, is your
> hub for all things parallel software development, from weekly thought
> leadership blogs to news, videos, case studies, tutorials and more. Take a
> look and join the conversation now. http://goparallel.sourceforge.net/
> _______________________________________________
> Linuxptp-devel mailing list
> Lin...@li...
> https://lists.sourceforge.net/lists/listinfo/linuxptp-devel

Re: [Linuxptp-devel] [PATCH RFC 4/6] clock: set sample weight.

[Miroslav L. <mli...@re...>]

On Mon, Feb 16, 2015 at 08:48:15PM +0100, Richard Cochran wrote:
> On Fri, Feb 13, 2015 at 01:56:16PM +0100, Miroslav Lichvar wrote:
> > +	if (sync_delay_rate <= 0 && servo_weight_samples(c->servo)) {
> > +		/* Get new sample delay with updated t1 and t2 */
> > +		sample_delay = clock_get_sample_delay(c);
> > +
> > +		if (sample_delay > 0 && c->path_delay > 0) {
> > +			weight = (double)c->path_delay / sample_delay;
> > +			if (weight > 1.0)
> > +				weight = 1.0;
> > +			pr_debug("delay sample %9" PRId64 " filtered %9" PRId64
> > +				 " weight %f",
> > +				 sample_delay, c->path_delay, weight);
> > +			c->path_delay = sample_delay;
> 
> So now, c->path_delay is set once in clock_path_delay() using
> averaging, and here the averaged value is used for the ratio, but then
> you clobber c->path_delay with the new value?

Yes, I thought the displayed delay should correspond to the offset and
not mix the sample offset with filtered delay. Maybe it would be
cleaner to add a new field to the clock structure for this?

-- 
Miroslav Lichvar

Re: [Linuxptp-devel] [PATCH RFC 4/6] clock: set sample weight.

[Miroslav L. <mli...@re...>]

On Mon, Feb 16, 2015 at 08:48:15PM +0100, Richard Cochran wrote:
> On Fri, Feb 13, 2015 at 01:56:16PM +0100, Miroslav Lichvar wrote:
> > +		if (sample_delay > 0 && c->path_delay > 0) {
> > +			weight = (double)c->path_delay / sample_delay;
> > +			if (weight > 1.0)
> > +				weight = 1.0;
> > +			pr_debug("delay sample %9" PRId64 " filtered %9" PRId64
> > +				 " weight %f",
> > +				 sample_delay, c->path_delay, weight);
> > +			c->path_delay = sample_delay;
> 
> So now, c->path_delay is set once in clock_path_delay() using
> averaging, and here the averaged value is used for the ratio, but then
> you clobber c->path_delay with the new value?
> 
> Your intention would be more clear if you would not set c->path_delay
> here, but rather use a local variable.

Setting c->path_delay here is actually a bug breaking the weight
calculation if there is no delay measurement before next sync message,
the new weight will be 1.0 as the filtered delay will actually be the
raw delay.

-- 
Miroslav Lichvar

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Richard C. <ric...@gm...>]

On Fri, Feb 13, 2015 at 01:56:12PM +0100, Miroslav Lichvar wrote:
> These patches should improve the synchronization of the clock with
> larger jitters, e.g. with software timestamping, wireless networks,
> etc.

What kind of networks did you test this on?

> What do you think? Does this make sense?

This code pairs up the Sync measurement with the most recent Delay_Req
measurement.  The assumption here is that a randomly larger Sync delay
will be paired with a larger Delay_Req delay (if I understood).  But
that is not a valid assumption in general, is it?

I think the best way is to simply leave out (ignore) bad measurements
altogether.  This is what the mean filter does, and the servos are
supposed to mitigate the effects of outliers.

Overall, I wouldn't mind having extra filter options for noisy
networks.  Ideally this would be modular, just like the servos and
filters are now.  People have asked about discarding software
timestamping measurements that are too far out.

Come to think of it, can't your algorithm be implemented within the
current servo/filter modular architecture?  We can change the API to
provide t1, t2, t3, and t4.

Thanks
Richard

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Miroslav L. <mli...@re...>]

On Fri, Mar 06, 2015 at 06:11:25PM +0100, Miroslav Lichvar wrote:
> On Fri, Mar 06, 2015 at 04:05:08PM +0100, Richard Cochran wrote:
> > There are really two issues:
> > 
> > 1. The filter algorithm itself.
> > 2. How the new filter fits into the SW design.
> > 
> > Although I am not convinced about #1
> 
> Not convinced that the raw offset should be sent to the servo when the
> number of remote and local timestamps is balanced?

I prepared some graphs that I thought show why is this better.

https://mlichvar.fedorapeople.org/tmp/ptp/ptpdelay_exponential.png
https://mlichvar.fedorapeople.org/tmp/ptp/ptpdelay_normal.png
https://mlichvar.fedorapeople.org/tmp/ptp/ptpdelay_uniform.png

Each image (using a different delay distribution) includes graphs of
the actual network delay in both directions, delay as measured by the
slave, filtered delay (median with 10 samples), offset using the
measured delay and offset using the filtered delay.

I think the difference is clearly visible. With exponential
distribution you can also see how the asymmetry in the delay
distribution is included in the filtered offset.

The scripts I used to generate and plot the data in case you want to
play with it are here.

https://mlichvar.fedorapeople.org/tmp/ptp/ptpdelay.tar.gz

-- 
Miroslav Lichvar

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Richard C. <ric...@gm...>]

On Fri, Mar 06, 2015 at 06:11:25PM +0100, Miroslav Lichvar wrote:
> The trouble is the raw mode is not a filter that can be easily
> plugged in, it has a different input than servos. It's a fundamentally
> different approach in how are the timestamps handled. In the raw mode
> we use only the last four timestamps, in filtered mode we use the last
> two timestamps and a long term average of delays from past sets of
> four timestamps.

We can really rework clock.c to make it cleaner to implement this sort
of thing.  We don't have to store t1-4 in the struct clock at all.

Why not abstract the offset estimator:

		   +-------------+
              t1 --|             |
              t2 --|  offset     |
              t3 --|             |-- offset
              t4 --|  estimator  |
  smoothed delay --|             |
		   +-------------+

There has got to be a nicer way to arrange the code to make this
work.  Once we add a "balanced mode" that works better in some
situations, people will want other balanced mode algorithms.

Thanks,
Richard

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Miroslav L. <mli...@re...>]

On Mon, Feb 16, 2015 at 09:07:12PM +0100, Richard Cochran wrote:
> On Fri, Feb 13, 2015 at 01:56:12PM +0100, Miroslav Lichvar wrote:
> > These patches should improve the synchronization of the clock with
> > larger jitters, e.g. with software timestamping, wireless networks,
> > etc.
> 
> What kind of networks did you test this on?

Ethernet, with SW and HW timestamping, and simulations with jitters up
to hundreds of milliseconds.

> > What do you think? Does this make sense?
> 
> This code pairs up the Sync measurement with the most recent Delay_Req
> measurement.  The assumption here is that a randomly larger Sync delay
> will be paired with a larger Delay_Req delay (if I understood).  But
> that is not a valid assumption in general, is it?

The delay message doesn't have to be delayed for the sample to have a
smaller weight. The delay calculated from the four timestamps will be
larger than the average when the sync message is delayed, the delay
message is delayed, or both are delayed. Let's make some ASCII art,
maybe it can explain it better :).

time --->
         sync        delay  sync          delay   sync
          t1''         t4'   t1'           t4      t1
master   --+------------+-----+-------------+-------+-----------
            \          /       \           /          \
             \        /         \         /             \
              \      /           \       /                \
slave    ------+----+-------------+-----+-------------------+---
             t2''  t3'           t2'   t3                  t2

There are 6 combinations of four timestamps that can be used to make a
sample and get an offset with delay: t1''t2''t3't4', t1''t2''t3t4,
t1't2't3't4', t1't2't3t4, t1t2t3't4', t1t2t3t4.

Samples t1''t2''t3t4 and t1t2t3't4' are not very useful as it's better
to have the timestamp closer to each other to minimize the error in
the calculated delay due to frequency offset between master and slave.

In the current code the filtered path delay is updated from samples
t1''t2''t3't4' and t1't2't3t4. The offset is calculated from t1t2,
t1't2' and the current filtered value of the path delay. The problem
is this can't detect that the sync message was delayed. The extra
delay will be included in the following update of the path delay,
after the offset was used to update the clock.

With the change I'm proposing, the offsets/delays of t1't2't3't4' and
t1t2t3t4 samples are used directly to update the clock and the
filtered value is used just to determine the weight of the sample.

> I think the best way is to simply leave out (ignore) bad measurements
> altogether.  This is what the mean filter does, and the servos are
> supposed to mitigate the effects of outliers.

Dropping samples completely could be a nice feature too. The problem
is that the servos are currently not ready to have missed updates and
it's tricky to determine the right value of the delay at which the
samples should be dropped. If it's too large, there will be too few
servo updates, if it's too small, too many bad samples will get in.

> Come to think of it, can't your algorithm be implemented within the
> current servo/filter modular architecture?  We can change the API to
> provide t1, t2, t3, and t4.

It can, but it would duplicate the code. That's how I tried to do it
originally. The servo sample function would need to get the offset
from the filtered delay, the sync/delay rate and t1, t2, t3, t4 (or
the sample offset and delay).

-- 
Miroslav Lichvar

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Richard C. <ric...@gm...>]

On Mon, Mar 09, 2015 at 02:20:19PM +0100, Miroslav Lichvar wrote:
> I think the difference is clearly visible. With exponential
> distribution you can also see how the asymmetry in the delay
> distribution is included in the filtered offset.

The generated offsets from the script are the *inputs* to the PI
controller, and they don't look to far apart to my eyeball analysis.
(Yes, the dispersion looks a bit better in the "raw delay" plots.)

The really interesting comparision would be the actual offset after
PI servo control.  I am looking to compare the result of your patch
set on a small but real network...

Thanks,
Richard

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Miroslav L. <mli...@re...>]

On Mon, Mar 09, 2015 at 08:53:52PM +0100, Richard Cochran wrote:
> On Fri, Mar 06, 2015 at 06:11:25PM +0100, Miroslav Lichvar wrote:
> > The trouble is the raw mode is not a filter that can be easily
> > plugged in, it has a different input than servos. It's a fundamentally
> > different approach in how are the timestamps handled. In the raw mode
> > we use only the last four timestamps, in filtered mode we use the last
> > two timestamps and a long term average of delays from past sets of
> > four timestamps.
> 
> We can really rework clock.c to make it cleaner to implement this sort
> of thing.  We don't have to store t1-4 in the struct clock at all.

If t1-t4 are not stored in clock.c, where will be delay calculated?

> Why not abstract the offset estimator:
> 
> 		   +-------------+
>               t1 --|             |
>               t2 --|  offset     |
>               t3 --|             |-- offset
>               t4 --|  estimator  |
>   smoothed delay --|             |
> 		   +-------------+
>
> There has got to be a nicer way to arrange the code to make this
> work.  Once we add a "balanced mode" that works better in some
> situations, people will want other balanced mode algorithms.

Hm, are there any other algorithms suitable for that?

To me, it would make more sense to calculate the delay and offset at
one place. How about the following approach instead?

- introduce a "time stamp processor" (tsproc.c)
  - input is t1-t4, c1-c3, clock rate ratio and update rate of t1t2 to t3t4
  - output is offset, delay and weight
  - the delay filter is there
  - according to the configuration and t1t2/t3r4 rate, it either
    returns raw offset/delay or values based on filtered delay
  - weighting is configurable too
- clock.c doesn't store t1-t4 and doesn't filter delay, it only calls
  tsproc_update* functions with new input and tsproc_getsample() to
  get a sample for the servo, print it and update the statistics
- port.c can use this too, deduplicating the delay calculation and
  delay filtering

Does it make sense?

-- 
Miroslav Lichvar

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Richard C. <ric...@gm...>]

On Tue, Feb 17, 2015 at 12:31:44PM +0100, Miroslav Lichvar wrote:
> The delay message doesn't have to be delayed for the sample to have a
> smaller weight. The delay calculated from the four timestamps will be
> larger than the average when the sync message is delayed, the delay
> message is delayed, or both are delayed. Let's make some ASCII art,
> maybe it can explain it better :).

Nice chart.  (Looks just like one I made recently to explain PTP in a
private email ;)

> time --->
>          sync        delay  sync          delay   sync
>           t1''         t4'   t1'           t4      t1
> master   --+------------+-----+-------------+-------+-----------
>             \          /       \           /          \
>              \        /         \         /             \
>               \      /           \       /                \
> slave    ------+----+-------------+-----+-------------------+---
>              t2''  t3'           t2'   t3                  t2

> In the current code the filtered path delay is updated from samples
> t1''t2''t3't4' and t1't2't3t4. The offset is calculated from t1t2,
> t1't2' and the current filtered value of the path delay. The problem
> is this can't detect that the sync message was delayed. The extra
> delay will be included in the following update of the path delay,
> after the offset was used to update the clock.

The extra delay is included in the path delay, yes, but the median
filter should remove it again.

> With the change I'm proposing, the offsets/delays of t1't2't3't4' and
> t1t2t3t4 samples are used directly to update the clock and the
> filtered value is used just to determine the weight of the sample.

But in the case where the delay measurement has an error, you penalize
a perfectly good sync measurement?

> Dropping samples completely could be a nice feature too. The problem
> is that the servos are currently not ready to have missed updates and
> it's tricky to determine the right value of the delay at which the
> samples should be dropped. If it's too large, there will be too few
> servo updates, if it's too small, too many bad samples will get in.

Let the end user decide, just like with PI weights.
 
> It can, but it would duplicate the code. That's how I tried to do it
> originally. The servo sample function would need to get the offset
> from the filtered delay, the sync/delay rate and t1, t2, t3, t4 (or
> the sample offset and delay).

You mean that you would duplicate pi.c for example?  I would prefer
that to having the "weight" filter hard coded in line.  Possibly you
could stack the filter on top of the servos?

Thanks,
Richard

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Keller, J. E <jac...@in...>]

On Tue, 2015-02-17 at 20:25 +0100, Richard Cochran wrote:
> On Tue, Feb 17, 2015 at 12:31:44PM +0100, Miroslav Lichvar wrote:
> > The delay message doesn't have to be delayed for the sample to have a
> > smaller weight. The delay calculated from the four timestamps will be
> > larger than the average when the sync message is delayed, the delay
> > message is delayed, or both are delayed. Let's make some ASCII art,
> > maybe it can explain it better :).
> 
> Nice chart.  (Looks just like one I made recently to explain PTP in a
> private email ;)
> 
> > time --->
> >          sync        delay  sync          delay   sync
> >           t1''         t4'   t1'           t4      t1
> > master   --+------------+-----+-------------+-------+-----------
> >             \          /       \           /          \
> >              \        /         \         /             \
> >               \      /           \       /                \
> > slave    ------+----+-------------+-----+-------------------+---
> >              t2''  t3'           t2'   t3                  t2
> 
> > In the current code the filtered path delay is updated from samples
> > t1''t2''t3't4' and t1't2't3t4. The offset is calculated from t1t2,
> > t1't2' and the current filtered value of the path delay. The problem
> > is this can't detect that the sync message was delayed. The extra
> > delay will be included in the following update of the path delay,
> > after the offset was used to update the clock.
> 
> The extra delay is included in the path delay, yes, but the median
> filter should remove it again.
> 
> > With the change I'm proposing, the offsets/delays of t1't2't3't4' and
> > t1t2t3t4 samples are used directly to update the clock and the
> > filtered value is used just to determine the weight of the sample.
> 
> But in the case where the delay measurement has an error, you penalize
> a perfectly good sync measurement?
> 
> > Dropping samples completely could be a nice feature too. The problem
> > is that the servos are currently not ready to have missed updates and
> > it's tricky to determine the right value of the delay at which the
> > samples should be dropped. If it's too large, there will be too few
> > servo updates, if it's too small, too many bad samples will get in.
> 
> Let the end user decide, just like with PI weights.
>  
> > It can, but it would duplicate the code. That's how I tried to do it
> > originally. The servo sample function would need to get the offset
> > from the filtered delay, the sync/delay rate and t1, t2, t3, t4 (or
> > the sample offset and delay).
> 
> You mean that you would duplicate pi.c for example?  I would prefer
> that to having the "weight" filter hard coded in line.  Possibly you
> could stack the filter on top of the servos?
> 
> Thanks,
> Richard

You could have a "weighted-pi" and "weighted-linreg". Then the
"weighted.c" module would pick pi or linreg based on name but stack it
with weighted mode. Then change the api for servos to take enough data
to do weighted mode.

Then the weighted servo would simply call out to another servo under the
hood.

Regards,
Jake

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Miroslav L. <mli...@re...>]

On Mon, Mar 09, 2015 at 08:36:43PM +0100, Richard Cochran wrote:
> The really interesting comparision would be the actual offset after
> PI servo control.  I am looking to compare the result of your patch
> set on a small but real network...

Ok.

To give you an idea what difference you can expect with raw
delay/offset and weights, here are graphs from a simulation with
10us jitter and default PI constants with SW timestamping.

https://mlichvar.fedorapeople.org/tmp/ptp/ptp4l_error.png

The RMS time error improved from 2.71 us to 1.85 us and 1.46 us. The
RMS frequency error improved from 1.08 ppm to 0.73 ppm and 0.53 ppm.

-- 
Miroslav Lichvar

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Miroslav L. <mli...@re...>]

On Tue, Mar 10, 2015 at 10:29:43AM +0100, Miroslav Lichvar wrote:
> To give you an idea what difference you can expect with raw
> delay/offset and weights, here are graphs from a simulation with
> 10us jitter and default PI constants with SW timestamping.
> 
> https://mlichvar.fedorapeople.org/tmp/ptp/ptp4l_error.png
> 
> The RMS time error improved from 2.71 us to 1.85 us and 1.46 us. The
> RMS frequency error improved from 1.08 ppm to 0.73 ppm and 0.53 ppm.

And here is a simulation where every 100th packet is delayed by 1
millisecond to better show the effect of sample weighting.

https://mlichvar.fedorapeople.org/tmp/ptp/ptp4l_error2.png

-- 
Miroslav Lichvar

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Richard C. <ric...@gm...>]

On Wed, Mar 11, 2015 at 01:28:05PM +0100, Miroslav Lichvar wrote:
> On Mon, Mar 09, 2015 at 08:53:52PM +0100, Richard Cochran wrote:
> > There has got to be a nicer way to arrange the code to make this
> > work.  Once we add a "balanced mode" that works better in some
> > situations, people will want other balanced mode algorithms.
> 
> Hm, are there any other algorithms suitable for that?

I should think so.  Just looking at the first graph of

   https://mlichvar.fedorapeople.org/tmp/ptp/ptp4l_error2.png

I would think simply comparing the sampled offset with the average
offset and scaling (or pruning) it would be at least as effective as
looking at the delay.  Plus it would not depend on "balanced" rates.

> To me, it would make more sense to calculate the delay and offset at
> one place. How about the following approach instead?
> 
> - introduce a "time stamp processor" (tsproc.c)
>   - input is t1-t4, c1-c3, clock rate ratio and update rate of t1t2 to t3t4
>   - output is offset, delay and weight
>   - the delay filter is there
>   - according to the configuration and t1t2/t3r4 rate, it either
>     returns raw offset/delay or values based on filtered delay
>   - weighting is configurable too
> - clock.c doesn't store t1-t4 and doesn't filter delay, it only calls
>   tsproc_update* functions with new input and tsproc_getsample() to
>   get a sample for the servo, print it and update the statistics
> - port.c can use this too, deduplicating the delay calculation and
>   delay filtering

(The delay must be per port, for P2P mode.)

> Does it make sense?

Yes, that is the right direction.

Thanks,
Richard

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Miroslav L. <mli...@re...>]

On Wed, Mar 11, 2015 at 03:32:16PM +0100, Richard Cochran wrote:
>    https://mlichvar.fedorapeople.org/tmp/ptp/ptp4l_error2.png
> 
> I would think simply comparing the sampled offset with the average
> offset and scaling (or pruning) it would be at least as effective as
> looking at the delay.  Plus it would not depend on "balanced" rates.

I think that would be a filter working with already calculated
offset/delay samples, not time stamps directly. Spike filters work well
if the packets are delayed occasionally, but without looking at delay
it wouldn't be able to tell if the network is still congested or the
clock is really off that much.

> > - port.c can use this too, deduplicating the delay calculation and
> >   delay filtering
> 
> (The delay must be per port, for P2P mode.)

Each port would have its own time stamp processor.

> > Does it make sense?
> 
> Yes, that is the right direction.

Ok, I'll see if I can update the patches for this.

Thanks,

-- 
Miroslav Lichvar

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Miroslav L. <mli...@re...>]

On Tue, Feb 17, 2015 at 08:25:03PM +0100, Richard Cochran wrote:
> On Tue, Feb 17, 2015 at 12:31:44PM +0100, Miroslav Lichvar wrote:
> > With the change I'm proposing, the offsets/delays of t1't2't3't4' and
> > t1t2t3t4 samples are used directly to update the clock and the
> > filtered value is used just to determine the weight of the sample.
> 
> But in the case where the delay measurement has an error, you penalize
> a perfectly good sync measurement?

You mean that it's better to use the offset based on the filtered
delay as the current code does? The problem is that after the
filtering the delay is no longer random, there is an error that moves
slowly and is included in the offsets passed to the servo, which is
not able to remove the error. A longer filter would make this problem
smaller, but it's better to let the servo deal with the noise and not
make its job harder when not necessary.

Look at it in another way. There are two modes of synchronization
based on how many measurements are there on the remote and local side.

In "unbalanced" mode on one side there is a significantly larger
number of measurements, this happens when broadcast/multicast is used
to save server or network resources. The four timestamps are too far
apart for most samples, so an assumption is made that the delay is
constant and the offset is calculated just from the two timestamps and
an estimate of the delay.

In "balanced" mode the number of measurements is similar on both sides
and samples can be safely created from all four timestamps. Each
sample has a delay and offset that is independent from others. This is
a huge advantage over the unbalanced mode. It's possible to put an
upper bound on the error in the offset, the samples can be filtered,
or they can have weight.

> > It can, but it would duplicate the code. That's how I tried to do it
> > originally. The servo sample function would need to get the offset
> > from the filtered delay, the sync/delay rate and t1, t2, t3, t4 (or
> > the sample offset and delay).
> 
> You mean that you would duplicate pi.c for example?

I meant that the weight calculation would be duplicated. If we wanted to
improve it (e.g. square the weight or offset it by minimum delay),
we would have to do in multiple places.

> I would prefer
> that to having the "weight" filter hard coded in line.

It's not a really a filter, it provides the servo with extra
information that's available in the balanced mode.

> Possibly you
> could stack the filter on top of the servos?

How would the API look like? I don't mind reworking the patches, it's
just that adding a single parameter for weight to the servo function
looked to me like a simple and clean approach.

-- 
Miroslav Lichvar

Re: [Linuxptp-devel] [PATCH RFC 0/6] Improve accuracy with software timestamping

[Richard C. <ric...@gm...>]

On Wed, Feb 18, 2015 at 06:03:03PM +0100, Miroslav Lichvar wrote:
> On Tue, Feb 17, 2015 at 08:25:03PM +0100, Richard Cochran wrote:
> > But in the case where the delay measurement has an error, you penalize
> > a perfectly good sync measurement?
> 
> You mean that it's better to use the offset based on the filtered
> delay as the current code does? The problem is that after the
> filtering the delay is no longer random, there is an error that moves
> slowly and is included in the offsets passed to the servo, which is
> not able to remove the error. A longer filter would make this problem
> smaller, but it's better to let the servo deal with the noise and not
> make its job harder when not necessary.

By "error that moves slowly" you mean that a network with much packet
delay variation (PDV) will add an error into the Sync measurements?

Sure, but if the error can be removed in the path delay estimation by
filtering, then the offset servo's job becomes easier, not harder.  Or
what are trying to say?

> In "unbalanced" mode on one side there is a significantly larger
> number of measurements, this happens when broadcast/multicast is used
> to save server or network resources. The four timestamps are too far
> apart for most samples, so an assumption is made that the delay is
> constant and the offset is calculated just from the two timestamps and
> an estimate of the delay.

Yes, that is how PTP normally works.  The path delay is assumed to be
constant.  It must not be variable.  Actually, if it changes to a new
static value (like after a change in the network), ptp4l can handle
that too.  (In E2E mode there will be a momentary offset error.)

> In "balanced" mode the number of measurements is similar on both sides
> and samples can be safely created from all four timestamps. Each
> sample has a delay and offset that is independent from others. This is
> a huge advantage over the unbalanced mode. It's possible to put an
> upper bound on the error in the offset, the samples can be filtered,
> or they can have weight.

So I really have no idea what "balanced" can mean here.  Because the
PDV does not affect the two messages in the same way, you cannot
"safely" use them.  Maybe there is some special case where both
messages pick up the same PDV, but in general this isn't true.

For an example of what I mean, see the second graph and the following
text:

   http://phk.freebsd.dk/time/20141024.html

   This plot makes the important feature of NTP phase offset
   measurements very obvious: Notice how almost all these different
   blobs have the general shape of a blob near X=Y and a tail up and
   another tail right.

   This is because the probability of a packet getting delayed on the
   way to the server is quite independent of the packet going back
   being delayed. Not totally independent, but quite independent.

Unless I misunderstood, your scheme relies on the assumption that the
PDV will affect the {Sync, Delay_Req} pair in a uniform way.

> How would the API look like? I don't mind reworking the patches, it's
> just that adding a single parameter for weight to the servo function
> looked to me like a simple and clean approach.

Off the top of my head:

- expand the servo/filter APIs to include all of the parameters you
  will need.

- introduce CLOCK_SERVO_PI_BALANCED (or whatever)

- servo_create(CLOCK_SERVO_PI_BALANCED, ...) calls
  balanced_servo_create()

- balanced_servo_create() calls pi_servo_create() and stores the
  pointer in its private data area.

- the balanced->sample() method will chain to pi->sample(), but with
  the weight possibly different than the default 1.0.

Thoughts?

Thanks,
Richard