Added check in CompareTimes for case when one node solution hasn't moved
Returns kInvalid in that case. Also added tests around CompareTimes and
InvalidDistance calcs
Rebased with the extrapolated time calcs and fix for normalized times
Change-Id: Ibfc4df5355c059cc66a334ea3d127a4a956ca89c
diff --git a/aos/network/multinode_timestamp_filter.cc b/aos/network/multinode_timestamp_filter.cc
index a042d35..aa580e7 100644
--- a/aos/network/multinode_timestamp_filter.cc
+++ b/aos/network/multinode_timestamp_filter.cc
@@ -646,6 +646,7 @@
bool is_less = false;
bool is_greater = false;
bool is_eq = true;
+ bool some_eq = false;
for (size_t i = 0; i < ta.size(); ++i) {
if (ignore_min_time && tb[i] == monotonic_clock::min_time) {
continue;
@@ -656,12 +657,20 @@
} else if (ta[i] > tb[i]) {
is_greater = true;
is_eq = false;
+ } else {
+ some_eq = true;
}
}
if (is_eq) {
return TimeComparison::kEq;
}
+ if (some_eq) {
+ // if at least one, but not all, are equal, then consider this invalid
+ // This represents a case where the solution on at least one node
+ // has not moved forward
+ return TimeComparison::kInvalid;
+ }
if (is_less && !is_greater) {
return TimeComparison::kBefore;
}
@@ -697,10 +706,6 @@
return dt;
}
-// Returns the amount of time that ta and tb are out of order by. The primary
-// direction is defined to be the direction of the average of the offsets. So,
-// if the average is +, and we get 1 - outlier, the absolute value of that -
-// outlier is the invalid distance.
chrono::nanoseconds InvalidDistance(
const std::vector<monotonic_clock::time_point> &ta,
const std::vector<monotonic_clock::time_point> &tb) {
diff --git a/aos/network/multinode_timestamp_filter.h b/aos/network/multinode_timestamp_filter.h
index 1ceb25c..b9467ec 100644
--- a/aos/network/multinode_timestamp_filter.h
+++ b/aos/network/multinode_timestamp_filter.h
@@ -254,15 +254,24 @@
enum class TimeComparison { kBefore, kAfter, kInvalid, kEq };
-// Compares two times.
+// Compares two sets of times, optionally ignoring times that are min_time
TimeComparison CompareTimes(const std::vector<monotonic_clock::time_point> &ta,
- const std::vector<monotonic_clock::time_point> &tb);
+ const std::vector<monotonic_clock::time_point> &tb,
+ bool ignore_min_time);
// Returns the maximum amount of elapsed time between the two samples in time.
std::chrono::nanoseconds MaxElapsedTime(
const std::vector<monotonic_clock::time_point> &ta,
const std::vector<monotonic_clock::time_point> &tb);
+// Returns the amount of time by which ta and tb are out of order. The primary
+// direction is defined to be the direction of the average of the offsets. So,
+// if the average is +, and we get a -ve outlier, the absolute value of that -ve
+// outlier is the invalid distance.
+std::chrono::nanoseconds InvalidDistance(
+ const std::vector<monotonic_clock::time_point> &ta,
+ const std::vector<monotonic_clock::time_point> &tb);
+
// Class to hold a NoncausalOffsetEstimator per pair of communicating nodes, and
// to estimate and set the overall time of all nodes.
//
diff --git a/aos/network/multinode_timestamp_filter_test.cc b/aos/network/multinode_timestamp_filter_test.cc
index 07d3712..b2eaf0f 100644
--- a/aos/network/multinode_timestamp_filter_test.cc
+++ b/aos/network/multinode_timestamp_filter_test.cc
@@ -75,9 +75,7 @@
return ss.str();
}
- void Debug() const {
- LOG(INFO) << DebugString();
- }
+ void Debug() const { LOG(INFO) << DebugString(); }
// Returns the offset at a given time.
// TODO(austin): get_d() ie double -> int64 can't be accurate...
@@ -154,6 +152,72 @@
}
}
+// Tests solution time(s) comparison and measure of invalid / inconsistent times
+TEST(TimestampProblemTest, CompareTimes) {
+ const monotonic_clock::time_point e = monotonic_clock::epoch();
+
+ // Create two sets of times, offset by 1000ns
+ std::vector<monotonic_clock::time_point> time_list;
+ for (int i = 0; i < 10; i++) {
+ time_list.push_back(e + std::chrono::nanoseconds(i * 1000));
+ }
+
+ std::vector<monotonic_clock::time_point> times_a = {time_list.begin(),
+ time_list.end() - 1u};
+ std::vector<monotonic_clock::time_point> times_b = {time_list.begin() + 1u,
+ time_list.end()};
+
+ CHECK_EQ(static_cast<int>(CompareTimes(times_a, times_b, true)),
+ static_cast<int>(TimeComparison::kBefore));
+ CHECK_EQ(static_cast<int>(CompareTimes(times_a, times_b, false)),
+ static_cast<int>(TimeComparison::kBefore));
+
+ CHECK_EQ(static_cast<int>(CompareTimes(times_b, times_a, true)),
+ static_cast<int>(TimeComparison::kAfter));
+ CHECK_EQ(static_cast<int>(CompareTimes(times_b, times_a, false)),
+ static_cast<int>(TimeComparison::kAfter));
+
+ CHECK_EQ(static_cast<int>(CompareTimes(times_a, times_a, true)),
+ static_cast<int>(TimeComparison::kEq));
+ CHECK_EQ(static_cast<int>(CompareTimes(times_b, times_b, false)),
+ static_cast<int>(TimeComparison::kEq));
+
+ std::vector<monotonic_clock::time_point> times_b_min = times_b;
+ times_b_min[5] = monotonic_clock::min_time;
+
+ CHECK_EQ(static_cast<int>(CompareTimes(times_a, times_b_min, true)),
+ static_cast<int>(TimeComparison::kBefore));
+ CHECK_EQ(static_cast<int>(CompareTimes(times_a, times_b_min, false)),
+ static_cast<int>(TimeComparison::kInvalid));
+
+ // Test if one of the elements is equal
+ std::vector<monotonic_clock::time_point> times_b_some_eq = times_b_min;
+ times_b_some_eq[2] = times_a[2];
+
+ CHECK_EQ(static_cast<int>(CompareTimes(times_a, times_b_some_eq, true)),
+ static_cast<int>(TimeComparison::kInvalid));
+ CHECK_EQ(static_cast<int>(CompareTimes(times_b, times_b_some_eq, false)),
+ static_cast<int>(TimeComparison::kInvalid));
+
+ // Test if elements are out of order
+ std::vector<monotonic_clock::time_point> times_b_mixed = times_b_min;
+ times_b_mixed[3] = times_a[0];
+
+ CHECK_EQ(static_cast<int>(CompareTimes(times_a, times_b_mixed, true)),
+ static_cast<int>(TimeComparison::kInvalid));
+ CHECK_EQ(static_cast<int>(CompareTimes(times_b, times_b_mixed, false)),
+ static_cast<int>(TimeComparison::kInvalid));
+
+ CHECK_EQ(InvalidDistance(times_a, times_a).count(), 0);
+ CHECK_EQ(InvalidDistance(times_a, times_b).count(), -1000);
+ CHECK_EQ(InvalidDistance(times_b, times_a).count(), -1000);
+ CHECK_EQ(InvalidDistance(times_a, times_b_min).count(), -1000);
+ CHECK_EQ(InvalidDistance(times_a, times_b_some_eq).count(), 0);
+ CHECK_EQ(InvalidDistance(times_b_some_eq, times_a).count(), 0);
+ CHECK_EQ(InvalidDistance(times_a, times_b_mixed).count(), 3000);
+ CHECK_EQ(InvalidDistance(times_b_mixed, times_a).count(), 3000);
+}
+
// Tests that an infinite precision solution matches our numeric solver solution
// for a couple of simple problems.
TEST(TimestampProblemTest, Solve) {
@@ -375,31 +439,25 @@
time_converter.FromDistributedClock(0, de + kDefaultHistoryDuration / 2));
// Double check we can read things from before the start
- EXPECT_EQ(
- de - kDt,
- time_converter.ToDistributedClock(0, me - kDt));
- EXPECT_EQ(
- me - kDt,
- time_converter.FromDistributedClock(0, de - kDt));
+ EXPECT_EQ(de - kDt, time_converter.ToDistributedClock(0, me - kDt));
+ EXPECT_EQ(me - kDt, time_converter.FromDistributedClock(0, de - kDt));
// And at and after the origin.
EXPECT_EQ(de, time_converter.ToDistributedClock(0, me));
EXPECT_EQ(me, time_converter.FromDistributedClock(0, de));
- EXPECT_EQ(
- de + chrono::milliseconds(10),
- time_converter.ToDistributedClock(0, me + kDt));
- EXPECT_EQ(
- me + chrono::milliseconds(10),
- time_converter.FromDistributedClock(0, de + kDt));
+ EXPECT_EQ(de + chrono::milliseconds(10),
+ time_converter.ToDistributedClock(0, me + kDt));
+ EXPECT_EQ(me + chrono::milliseconds(10),
+ time_converter.FromDistributedClock(0, de + kDt));
// Force 10.1 seconds now. This will forget the 0th point at the origin.
EXPECT_EQ(
de + kDefaultHistoryDuration + kDt,
time_converter.ToDistributedClock(0, me + kDefaultHistoryDuration + kDt));
- EXPECT_EQ(
- me + kDefaultHistoryDuration + kDt,
- time_converter.FromDistributedClock(0, de + kDefaultHistoryDuration + kDt));
+ EXPECT_EQ(me + kDefaultHistoryDuration + kDt,
+ time_converter.FromDistributedClock(
+ 0, de + kDefaultHistoryDuration + kDt));
// Yup, can't read the origin anymore.
EXPECT_DEATH({ LOG(INFO) << time_converter.ToDistributedClock(0, me); },
@@ -408,12 +466,8 @@
"forgotten");
// But can still read the next point.
- EXPECT_EQ(
- de + kDt,
- time_converter.ToDistributedClock(0, me + kDt));
- EXPECT_EQ(
- me + kDt,
- time_converter.FromDistributedClock(0, de + kDt));
+ EXPECT_EQ(de + kDt, time_converter.ToDistributedClock(0, me + kDt));
+ EXPECT_EQ(me + kDt, time_converter.FromDistributedClock(0, de + kDt));
}
// Tests unity time with 1 node.