4. 过滤和选择算法 (Filtering and Selection Algorithms)

影响时间分发准确性和可靠性的一个最重要因素, 是一组用于降低统计误差以及误报时钟 (falseticker) 影响的算法. 这些误报时钟可能由各种子网组件, 参考源或传播介质故障导致. 本节建议的算法是在 Internet 中多年运行期间, 在差异很大的拓扑, 速度和流量条件下开发并改进而来的. 虽然这些算法被认为是目前可用的最佳算法, 但它们并不是 NTP 规范不可分割的一部分, 因为未来可能设计出性能相似或更优的其他算法.

不过, 必须注意, NTP 同步子网中的并非所有时间服务器或客户端都必须实现这些算法. 例如, 如果准确性和可靠性需求允许, 简单工作站可以为了简化而省略其中一个或两个算法. 然而, 对于向规模较大的群体提供同步的 NTP 服务器, 例如大学校园或研究实验室, 预期应实现这些算法, 或者实现已证明具有等价功能的其他算法. [MIL91a] 给出了设计原则和性能的全面讨论.

为了让 NTP 过滤和选择算法有效运行, 为每个对等体记录近期样本方差的度量是有用的. 采用的度量基于一阶差分, 它易于计算, 且能有效服务预期目的. 共有两个度量, 一个称为过滤离散度 (filter dispersion) ε_σ, 另一个称为选择离散度 (select dispersion) ε_ξ. 二者都按同步距离排序的临时列表中的时钟偏移加权和计算. 如果 θ_i (0 <= i < n) 是第 i 个条目的偏移, 则第 i 个条目相对于第 j 个条目的样本差 ε_ij 定义为 ε_ij = |θ_i - θ_j|. 相对于第 j 个条目的离散度定义为 ε_j, 并按如下加权和计算:

ε_j = Σ(i=0 to n-1) ε_ij w^(i+1)

其中 w 是用于控制同步距离在离散度预算中影响的加权因子. 在 NTP 算法中, w 选择为小于 1/2: 对过滤离散度使用 w = NTP.FILTER, 对选择离散度使用 w = NTP.SELECT. NTP 算法中使用的绝对离散度 ε_σ 和 ε_ξ 定义为相对于第 0 个条目 ε_0.

下面描述两个过程: 时钟过滤过程 (clock-filter procedure), 用于从给定时钟中选择最佳偏移样本; 时钟选择过程 (clock-selection procedure), 用于在分层的一组时钟中选择最佳时钟.

4.1. 时钟过滤过程 (Clock-Filter Procedure)

时钟过滤过程在收到 NTP 消息或其他导致新数据样本产生的事件时执行. 它接受形式为 (θ, δ, ε) 的参数, 其中 θ 是样本时钟偏移测量值, δ 和 ε 是关联的往返延迟和离散度. 它确定过滤后的时钟偏移 (peer.offset), 往返延迟 (peer.delay) 和离散度 (peer.dispersion). 它还更新已记录样本的离散度, 并保存当前时间 (peer.update).

时钟过滤过程的基础是过滤移位寄存器 (peer.filter), 它由 NTP.SHIFT 个阶段组成, 每个阶段包含一个 3 元组 [θ_i, δ_i, ε_i], 索引从左侧的 0 开始编号. clear 过程会把所有阶段初始化为 [0, 0, NTP.MAXDISPERSE]. 新数据样本从左端移入过滤器, 先让 NULL, 再让旧样本从右端移出. 随着新更新到达, packet 过程提供形式为 (θ, δ, ε) 的样本; 当两个轮询间隔过去仍没有新更新时, transmit 过程提供形式为 [0, 0, NTP.MAXDISPERSE] 的样本. 虽然这里对参数, 时钟过滤器内容和对等体变量使用相同符号 (θ, δ, ε), 其含义可由上下文明确. 以下伪代码描述该过程.

begin clock-filter procedure (θ, δ, ε)

    for (i from NTP.SIZE - 1 to 1) begin        /* update dispersion */
        [θ_i, δ_i, ε_i] <- [θ_(i-1), δ_(i-1), ε_(i-1)];
        ε_i = ε_i + φτ;
        add [λ_i = ε_i + |δ_i|/2, i] to temporary list;
    endfor;
    [θ_0, δ_0, ε_0] <- [θ, δ, ε];           /* insert new sample */
    add [λ = ε + |δ|/2, 0] to temporary list;
    peer.update <- sys.clock;                   /* reset base time */
    sort temporary list by increasing [distance || index];
    
    ε_σ <- 0;
    for (i from NTP.SHIFT-1 to 0)              /* compute filter dispersion */
        if (peer.dispersion_index[i] >= NTP.MAXDISPERSE or
            |θ_i - θ_0| > NTP.MAXDISPERSE)
            ε_σ <- (ε_σ + NTP.MAXDISPERSE) × NTP.FILTER;
        else
            ε_σ <- (ε_σ + |θ_i - θ_0|) × NTP.FILTER;
    
    peer.offset <- θ_0;                        /* update peer variables */
    peer.delay <- δ_0;
    peer.dispersion <- min(ε_0 + ε_σ, NTP.MAXDISPERSE);
end clock-filter procedure

peer.offset 和 peer.delay 变量表示本地时钟相对于对等体时钟的时钟偏移和往返延迟. 二者都是精密量, 通常可以在较长时间间隔内求平均, 以提高准确性和稳定性, 且不会积累偏差, 参见附录 H. peer.dispersion 变量表示由测量误差, 偏斜误差累积和样本方差造成的最大误差. 这三个变量都用于时钟选择和时钟组合过程, 以选择用于同步的对等体时钟, 并最大化指示值的准确性和稳定性.

4.2. 时钟选择过程 (Clock-Selection Procedure)

时钟选择过程使用对等体变量 THETA, DELTA, EPSILON 和 τ, 并在这些变量发生变化或可达性状态变化时调用. 它由两个算法组成: 交集算法 (intersection algorithm) 和聚类算法 (clustering algorithm). 交集算法构造有资格成为同步源的候选对等体列表, 为每个候选者计算置信区间, 并使用改编自 Marzullo 和 Owicki [MAR85] 的技术剔除误报时钟. 聚类算法按层级 (stratum) 和同步距离对幸存候选者列表排序, 并基于选择离散度反复剔除离群值, 直到只剩下最准确, 最精密且最稳定的候选者. 每个幸存者都会设置一个位, 表示选择过程的结果. 系统变量 sys.peer 被设置为指向最可能的幸存者, 如果存在的话; 否则设置为 NULL.

4.2.1. 交集算法 (Intersection Algorithm)

begin clock-selection procedure

    m <- 0;
    for (each peer)                     /* calling all peers */
        if (peer.reach != 0 and peer.dispersion < NTP.MAXDISPERSE and
            not (peer.stratum > 1 and peer.refid = peer.hostaddr)) begin
            LAMBDA <- distance(peer);    /* make list entry */
            add [THETA - LAMBDA, -1] to endpoint list;
            add [THETA, 0] to endpoint list;
            add [THETA + LAMBDA, 1] to endpoint list;
            m <- m + 1;
        endif
    endfor
    if (m = 0) begin                    /* skedaddle if no candidates */
        sys.peer <- NULL;
        sys.stratum <- 0 (undefined);
        exit;
    endif
    sort endpoint list by increasing endpoint||type;

逐一检查每个对等体, 只有通过若干健全性检查后才会加入端点列表. 这些检查用于避免环路, 并避免使用噪声异常大的数据. 如果没有对等体通过健全性检查, 该过程会退出, 且不会找到同步源. 对每个 m 个幸存者, 会向端点列表添加三个形式为 [endpoint, type] 的条目: [THETA - LAMBDA, -1], [THETA, 0] 和 [THETA + LAMBDA, 1]. 因此列表中会有 3m 个条目, 随后按 endpoint 递增排序.

以下算法改编自 DTS [DEC89], 旨在产生只包含真时钟 (truechimer) 的最大单一交集. 算法先把值 f 以及计数器 i 和 c 初始化为零. 然后从已排序端点列表的最低端点开始, 对每个条目 [endpoint, type], 从计数器 i 中减去 type 的值; i 表示交集数量. 如果 type 为零, 则递增 c, c 表示误报时钟数量, 参见附录 H. 如果对某个条目有 i >= m - f, 该条目的 endpoint 成为交集的下端点; 否则 f 增加 1, 并重复上述过程. 在不重置 f 或 c 的情况下, 使用类似过程寻找上端点, 只是这次把 type 的值加到计数器. 如果两个端点确定后 c <= f, 该过程继续, 认为已经找到 m - f 个真时钟; 否则 f 增加 1, 整个过程重复.

    for (f from 0 to f >= m/2) begin        /* calling all truechimers */
        c <- 0;
        i <- 0;
        for (each [endpoint, type] from lowest) begin   /* find low endpoint */
            i <- i - type;
            low <- endpoint;
            if (i >= m - f) break;
            if (type = 0) c <- c + 1;
        endfor;
        i <- 0;
        
        for (each [endpoint, type] from highest) begin  /* find high endpoint */
            i <- i + type;
            high <- endpoint;
            if (i >= m - f) break;
            if (type = 0) c <- c + 1;
        endfor;
        if (c <= f) break;              /* continue until all falsetickers found */
    endfor;
    if (low > high) begin               /* quit if no intersection found */
        sys.peer <- NULL;
        exit;
    endif;

注意, 只有当交集数量超过 m/2 时, 处理才会继续越过这一点. 不过, 仍有可能, 尽管概率不高, 在交集中剩余的真时钟少于 m/2.

4.2.2. 聚类算法 (Clustering Algorithm)

在原始 DTS 算法中, 时钟选择过程会在此处退出, 并把推定正确时间设置为计算得到的交集 [low, high] 的中点. 然而, 这可能导致准确性和稳定性显著损失, 因为各个对等体的统计信息会丢失. 因此在 NTP 中, 前面步骤幸存的候选者会被进一步处理. 候选列表以 [distance, index] 形式的条目重建, 其中 distance 根据缩放后的对等体层级和同步距离 LAMBDA 计算. 缩放因子提供了一种对层级和距离组合加权的机制. 通常, 层级会占主导, 除非一个或多个幸存者具有异常高的距离. 随后列表按 distance 递增排序.

    m <- 0;
    for (each peer) begin               /* calling all peers */
        if (low <= θ <= high) begin
            LAMBDA <- distance(peer);   /* make list entry */
            dist <- peer.stratum × NTP.MAXDISPERSE + LAMBDA
            add [dist, peer] to candidate list;
            m <- m + 1;
        endif;
    endfor;
    sort candidate list by increasing dist;

接下来的步骤用于剔除相对于候选列表其他成员表现出显著离散度的离群值, 同时尽量减少游移 (wander), 尤其是在有许多时间服务器的高速 LAN 上. 游移会造成不必要的网络开销, 因为每次选择新的对等体用于同步时, 轮询间隔会被限制在 sys.poll, 并且只有当该对等体不再被选择时才会缓慢增加. 实际经验表明, 幸存到此处的候选者数量可能变得相当大, 并消耗大量处理器周期, 却并不会实质性增强稳定性和准确性. 因此, 候选列表会被截断为最多 NTP.MAXCLOCK 个条目.

注意, ε_ξi 是相对于候选列表中第 i 个对等体的选择样本离散度, 可用类似前述过滤离散度的方式计算. EPSILON_j 是列表中第 j 个对等体的离散度, 包含由测量误差, 偏斜误差累积和过滤离散度造成的组成部分. 如果最大 ε_ξi 大于最小 EPSILON_j, 且幸存者数量大于 NTP.MINCLOCK, 则从列表中丢弃第 i 个对等体并重复该过程. 如果当前同步源是幸存者之一, 且没有其他更低层级的幸存者, 则该过程不再做任何操作而退出. 否则, 同步源设置为候选列表中的第一个幸存者. 以下 i, j, k, l 是对等体索引, 其中 k 是当前同步源的索引, 如果没有则为 NULL, l 是候选列表中第一个幸存者的索引.

    while begin
        for (each survivor [distance, index]) begin     /* compute dispersions */
            find index i for max ε_ξi;
            find index j for min EPSILON_j;
        endfor
        if (ε_ξi <= EPSILON_j or m <= NTP.MINCLOCK) break;
        peer.survivor[i] <- 0;          /* discard ith peer */
        if (i = k) sys.peer <- NULL;
        delete the ith peer from the candidate list;
        m <- m - 1;
    endwhile
    if (peer.survivor[k] = 0 or peer.stratum[k] > peer.stratum[l]) begin
        sys.peer <- l;                  /* new clock source */
        call poll-update;
    endif
end clock-select procedure;

该算法旨在偏向候选列表前部的对等体, 这些对等体具有最低层级和最低距离, 因而大概能提供最准确且最稳定的时间. 如果权重因子 v, 也称为 NTP.SELECT, 选择适当, 列表条目会从尾部被修剪; 除非少数离群值与剩余条目显著不一致, 在这种情况下会优先丢弃离群值. 终止条件的设计目标是在统计上没有充分理由时避免同步源之间不必要的切换, 同时仍保持对低层级, 低距离对等体的偏向.