跳到主要内容

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

时钟过滤算法 (clock filter algorithm) 是对等体过程 (peer process) 的一部分. 它整理线上 (on-wire) 数据流, 从中选择最可能表示准确时间的样本. 该算法产生的变量包括偏移 (offset, theta), 延迟 (delay, delta), 离散度 (dispersion, epsilon), 抖动 (jitter, psi) 和到达时间 (time of arrival, t). 这些数据由缓解算法 (mitigation algorithms) 使用, 用于确定规训系统时钟时采用的最佳最终偏移. 它们也用于判断服务器健康状态, 以及服务器是否适合同步.

10.1. 过滤器结构 (Filter Structure)​

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

以下机制用于确保过滤器中有足够样本, 并丢弃过旧的失效数据:

  • 初始化 (Initialization): 所有级的元组都设置为哑元组 (dummy tuple) (0, MAXDISP, MAXDISP, 0).
  • 样本到达 (Sample Arrival): 当有效分组到达时, 元组移入过滤器, 旧元组被丢弃, 因此最终只会留下有效元组.
  • 超时处理 (Timeout Handling): 如果可达寄存器 (reach register) 的低三位为零, 表示三个轮询间隔 (poll interval) 内没有收到有效分组, 轮询过程 (poll process) 将使用哑元组调用时钟过滤算法. 如果这种状态持续八个轮询间隔, 寄存器将回到初始状态.

10.2. 离散度计算 (Dispersion Calculation)​

下一步, 将移位寄存器各级复制到一个临时列表, 并按 delta 递增排序. 令 i 从 delta 最低的级开始索引. 如果第一个元组的历元 (epoch) t_0 不晚于最后一个有效样本的历元 tp, 该例程退出, 且不影响当前对等体变量. 否则, 令 epsilon_i 为第 i 个条目的离散度, 则对等体离散度 (peer dispersion) p.disp 为:

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

观察结果 (Observations):

a) 如果所有级都包含离散度为 MAXDISP 的哑元组, 则计算得到的离散度略小于 16 s.

b) 每当一个有效元组移入寄存器, 离散度会下降到略低于原来一半的程度, 具体取决于该有效元组的离散度.

c) 第四个有效分组之后, 离散度通常略小于 1 s, 这是选择算法 (selection algorithm) 使用的 MAXDIST 参数的假定值.

10.3. 抖动计算 (Jitter Calculation)​

令排序列表中第一级的偏移为 theta_0; 对于其它级, 无论顺序如何, 抖动都是以下 RMS 平均值:

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

其中 n 是过滤器中有效元组的数量 (n > 1). 为保证一致性并避免除法异常, psi 的下界为以秒表示的系统精度 (system precision) s.rho.

虽然通常不把抖动视为服务器质量排序的主要因素, 但它是基础计时性能和网络拥塞状态的重要指标.

10.4. 同步距离 (Synchronization Distance)​

同步距离 (synchronization distance) lambda 由延迟和离散度计算:

lambda = (delta / 2) + epsilon

说明 (Notes):

  • epsilon 以及由此得到的 lambda 以 PHI 速率增加.
  • lambda 不是状态变量 (state variable), 因为 lambda 每次使用时都会重新计算.
  • 它是根同步距离 (root synchronization distance) 的组成部分, 缓解算法将其作为指标, 用于评估每个服务器可提供时间的质量.

10.5. NTPv4 与 NTPv3 的差异​

需要注意, 与 NTPv3 不同, NTPv4 关联 (associations) 不会通过将层级 (stratum) 设置为 16 并将闰秒指示符 (leap indicator) 设置为 3 来表示超时条件. 关联变量 (association variables) 会保留最后一个分组到达时确定的值.

在 NTPv4 中:

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

时钟过滤算法的示例实现在 Appendix A.5.2 的 clock_filter() 例程中给出.