[evaal contest] computing reliability

[Francesco Potortì]

Here we define how to deal with jitter.  The first sample arrives by
definition at time 0.  We should define what happens when we get samples
arriving at times like this:

0   0.2   0.6   1.2   1.9   2.5   3.5   4.7   4.8   4.9   5.2   5.5   5.8   6.1

that is, with intersample intervals like this:

 0.2   0.4   0.6   0.7   0.7   1.0   1.2   0.1   0.1   0.3   0.3   0.3

I suggest a crude algorithm like the following one:

const minjitter = -0.25
const maxjitter = 0.25
const expectedintv = 0.5
var nexttime = 0
var goodsamples = 0

# first sample arrives at time 0, so sample.time will be 0
# subsequent samples have increasing sample.time
for (each sample arriving)

   # difference of time received with respect to expected
   jitter = sample.time - nexttime

   # too near to the previous one: ignore
   if (jitter < minjitter)
      continue

   # good sample: store it and increase number of good samples
   store(sample)
   goodsamples += 1

   # limited jitter: do not move the time base
   if (jitter < maxjitter)
      nexttime += expectedintv

   # too far from previous sample: adjust the time base
   else
      nexttime = sample.time + expectedintv

endfor


Then, for the above time sequence, we would discard the samples
arriving at 0.2, 4.8, 4.9, 5.8, yelding a 71% availability.

This algorithm gives 99% availability if the competitor's clock is 1%
faster than our clock, and 100% availability if it is slower, that is,
it compensates for slower clocks but does not allow for faster clocks.
This can be corrected, but the added complexity is in my opinion not
justified for our purposes.

The interval for allowed jitter can be expanded, let's say that the
algorithm would be more permissive with

const minjitter = -0.4
const maxjitter = 0.4

In this case, in the above sequence we would discard the samples
arriving at 4.9, 5.2, 6.1 yelding a 79% availability.  

-- 
Francesco Potortì (ricercatore)        Voice:  +39.050.315.3058 (op.2111)
ISTI - Area della ricerca CNR          Mobile: +39.348.8283.107
via G. Moruzzi 1, I-56124 Pisa         Fax:    +39.050.315.2040	 
(entrance 20, 1st floor, room C71)     Web:    http://fly.isti.cnr.it