Skip to main content

10. Clock Filter Algorithm (时钟过滤算法)

时钟过滤算法是对等体进程的一部分。它对线上数据流进行筛选，选择最可能代表准确时间的样本。该算法生成图19中显示的变量，包括偏移(offset, theta)、延迟(delay, delta)、离散(dispersion, epsilon)、抖动(jitter, psi)和到达时间(time of arrival, t)。这些数据被缓解算法用来确定用于调节系统时钟的最佳和最终偏移。它们还用于确定服务器健康状况以及是否适合同步。

10.1. 过滤器结构​

时钟过滤算法将最近的样本元组 (theta, delta, epsilon, t) 保存在过滤器结构中，该结构作为8级移位寄存器运行。元组按数据包到达的顺序保存。这里的 t 是根据秒计数器的数据包到达时间，不应与对等体变量 tp 混淆。

使用以下方案来确保过滤器中有足够的样本并丢弃旧的过时数据：

  • 初始化：所有级的元组都设置为虚拟元组 (0, MAXDISP, MAXDISP, 0)
  • 样本到达：当有效数据包到达时，元组被移入过滤器，导致旧元组被丢弃，因此最终只剩下有效元组
  • 超时处理：如果到达寄存器(reach register)的三个低位为零，表示三个轮询间隔已过期且未收到有效数据包，则轮询进程使用虚拟元组调用时钟过滤算法。如果这种情况持续八个轮询间隔，寄存器将返回初始状态

10.2. 离散计算​

在下一步中，移位寄存器的各级被复制到临时列表，并按 delta 递增排序。设 i 索引从最低 delta 开始的各级。如果第一个元组时期 t_0 不晚于最后一个有效样本时期 tp，则例程退出而不影响当前对等体变量。否则，设 epsilon_i 为第 i 个条目的离散，则对等体离散 p.disp 的计算公式为：

         i=n-1
         ---     epsilon_i
epsilon =  \     ----------
          /        (i+1)
         ---     2
         i=0

观察要点：

a) 如果所有级都包含离散为 MAXDISP 的虚拟元组，则计算的离散略小于 16 秒

b) 每次将有效元组移入寄存器时，离散会减少略少于一半（取决于有效元组的离散）

c) 在第四个有效数据包之后，离散通常略小于 1 秒，这是选择算法使用的 MAXDIST 参数的假定值，用于确定对等体变量是否可接受

10.3. 抖动计算​

设排序列表中第一级的偏移为 theta_0；然后，对于任何顺序的其他级，抖动(jitter)是均方根(RMS)平均值：

              +-----                 -----+^1/2
              |  n-1                      |
              |  ---                      |
      1       |  \                     2  |
psi = ---- *  |  /    (theta_0-theta_j)   |
    (n-1)     |  ---                      |
              |  j=1                      |
              +-----                 -----+

其中 n 是过滤器中有效元组的数量 (n > 1)。为了确保一致性并避免其他计算中的除法异常，psi 从下方受系统精度 s.rho（以秒表示）的限制。

虽然抖动通常不被认为是服务器质量排名的主要因素，但它是基本计时性能和网络拥塞状态的有价值指标。对缓解算法特别重要的是对等体同步距离(peer synchronization distance)。

10.4. 同步距离​

同步距离 lambda 从延迟和离散计算得出：

lambda = (delta / 2) + epsilon

注意事项：

  • epsilon 因此 lambda 以 PHI 的速率增加
  • lambda 不是状态变量，因为 lambda 在每次使用时都会重新计算
  • 它是根同步距离的一个组成部分，缓解算法使用它作为评估每个服务器可用时间质量的度量

10.5. NTPv4 与 NTPv3 的差异​

重要的是要注意，与 NTPv3 不同，NTPv4 关联不会通过将层级设置为 16 和闰秒指示器设置为 3 来显示超时条件。关联变量保留最后一个数据包到达时确定的值。

在 NTPv4 中：

  • lambda 随时间增加
  • 最终同步距离超过距离阈值 MAXDIST
  • 此时关联被认为不适合同步

时钟过滤算法的示例实现显示在附录 A.5.2 的 clock_filter() 例程中。

Last updated on