NTP网络时间校准对时器的4个核心算法

NTP网络时间校准对时器涉及的4个算法：数据过滤算法(Datafilteralgorithm)、时钟选择算法(Clockselectionalgorithm)、合并算法(Clusteringalgorithm)和时钟调节算法(Clockdisciplinealgorithm)。严格地说，这些算法并不是协议的固有部分，但是NTP的实现却有赖于这些算法。

1、NTP协议概述

时间信息的传输都使用UDP协议，每一个时间数据包内包含客户端时钟记录的发送NTP报文和接收NTP报文的时间，服务器端时钟记录的接收和发送NTP请求报文的时间。客户端在收到上述数据包后即可计算出时间的偏差量与传递数据包的时间延迟。时间服务器利用一个过滤算法，及先前8组时间同步资料计算出时间参考值，判断后续校时包的精确性，一个相对较低的离散程度，表示一个对时数据包的可信度比较高。

在不稳定的网络中，仅从一个时间服务器获得校时信息，不能校正通讯过程所造成的时间偏差，而同时与多台时间服务器通信校时，就可利用过滤算法找出相对较可靠的时间源，然后采用这个时钟源的时间来校正本地时间。

2、数据过滤算法

数据过滤算法主要负责过滤这个模块接收到的服务器信息，然后根据数理统计方法从具体服务器提供的一组数据中，选出最能体现服务器性质的信息。在网络时间协议中，本算法按照相应的规则从**服务器提供的8对数据报文中，选出质量最优的一组数据。实际上，可以对这种规则做相应的改进，以便改善数据滤波算法效率，因此，这种滤波规则就至关重要。

在网络时间协议第三版中，这种选取规则就是最小时延准则。最小时延准则就是在所有的数据中选取网络传输时延最小的偏移量数据。该算法的功能是确认数据包的有效性和从某个给定的时间参考源的时间样本中选取最佳的样本。它可以分成健全性校验和滤波两个部分。健全性主要是指数据是否具有**性、相关通信参数是否合理等。滤波主要是指根据当前的四个时间戳计算出当前的时间偏移、路径延迟和离差，并更新寄存器数组，计算滤波离差、同步距离等以降低偏移的均方误差。

3、时钟选择算法

时钟选择算法主要用在网络时间协议的系统处理模块的时钟选择部分，本算法检查所有时间服务器的相关变量，排除质量不好的时间服务器留下几个质量最好的时间服务器。为了保证系统时间同步的可靠性，设计两台或多台NTP授时服务器，通过时钟选择算法确定所采用的时间服务器。

本算法具体包括Intersection算法和Clustering算法。其中Intersection算法构造一个符合成为同步源条件的候选时钟列表，分别为每个时钟计算置信区间，并淘汰错误的时钟。Clustering算法则是通过对时间服务器的质量信息进行排序，选出质量最好的一组服务器。

3.1 Intersection算法

NTP用一张时间参考源的表格来记录可供访问的所有时间参考源。这些参考源中最为优秀的才能作为候选者进入参考源的优选目录。聚类算法根据前面数据滤波算法，针对每一个服务器得出其最佳的偏移量θ，而通过以上同步原理的分析，准确的时钟偏移量一定在误差区间内。通过这一结论如果现行候选者真正的偏移量存在于正确时间服务器区间的交集中则留用，反过来，也可以通过这一结论来淘汰错误的服务器，所以Intersection算法主要是抛弃错误信息的服务器。算法示意图如图2.1所示：

2.1Intersection算法示意图

其中A、B、C表示正确时钟，其交集表示包含正确时钟的最大交集，D表示错误时钟。

3.2 Clustering算法

Clustering算法是通过对时间服务器的相关参数进行排序，选出质量最好的一组服务器。一般来说，最高的可靠性通常与最小的层和同步离差有关系，最高的准确度通常与最小的层和同步距离有关系。从Intersection算法得出正确服务器后，Clustering算法先按层(Stratum)排序再按离差排序。其离差的计算公式是这样的：其中w是一个因子，在NTP中一般小于1/2，用来控制由同步距离带来的影响。令m>0是候选时钟列表中时钟服务器的数目，(0)iθ≤i<m是第i个候选点的偏移，ijε是第i个候选点与第j个候选点的偏移量之差，即ijijε=θ−θ，则第j个候选点的离差jε计算公式如下：110mijijiεεw−+==∑(2-1)在这个算法中，排除jε大的候选点，保留**数目的时间服务器，这样就得到了一组质量最好的时间服务器。

4、合并算法

时钟选择算法工作在网络时间协议中，利用加权平均算法分析所有提供时间服务的主机产生一个合并的估计值，得到一组精度最好的服务器，候选服务器列表中包含的对等点的偏移量是统计相等的，所以它们中的任一个都可以被用来调整本地时钟。聚合算法得到的列表中保存了精度最高的m个时钟源(10≥m≥1)，并在系统变量Source中存放了m个时钟源中间性能最好的一个时钟的ID。若合并算法没有执行，ID号等于Source的时钟源作为主同步时钟源，客户机和它通讯得到的时间偏差将成为本地时钟校正的最终数据。但是在时间同步网络中，经常出现由于NTP报文发送和接收的路径不对称导致的时间偏差值的系统误差。误差的范围在微秒级到秒级之间。

实验证明，多个时间源的时间偏差值的合并结果可以大大抵消不对称系统误差。这也是合并算法产生的主要目的。虽然只有一个时钟被挑选为主同步时钟源，本地时钟的最终修正值还是受所有通过了聚合算法的时钟源影响。最后得到偏移量Θ的合并算法公式如下：10111miiimii−θ=−=ΛΘ=Λ∑∑(2-2)其中m—选择算法之后剩余的候选服务器个数，iθ—本地时钟相对于第i个候选服务器的偏移量；iΛ—本地计算机相对于第i个服务器同步距离(0≤i<m)。

5、时钟调节算法

本算法主要负责对系统时钟进行校正，在很大程度上影响着本地时钟调整的精度，本算法并不是简单的将前面三种算法得到的时钟偏移量补偿到本地系统时钟，而是采用现行相位调整和非线性相位调整两种方式来调整时钟。线性调整是指渐进地对时钟进行调整，实现“微调”的效果，使系统时钟单调增加。服务器1服务器2服务器n数据过滤1数据过滤2数据过滤nIntersection算法和Clustering算法合并算法LoopFilterVFONTP报文。

线性调整通过把本地时钟偏移量划分成多个微小的偏移量来调整系统时钟，这样的渐进调整方法，在时钟偏移量比较小的时候，效果要优于一次性调整，这也说明了校正本地时钟偏移量是一个需要很长时间的过程。而非线性调整就是直接把各种算法计算出的时间偏移量直接补偿到系统时钟上，这种方式比较适合时钟偏移量较大的情况使用。时钟校正是实现网络时间同步的重要环节，影响时间同步精度的因素还有网络响应能力变化产生的抖动和振荡器频率稳定度产生的漂移。可以使用锁相环路和锁频环路来补偿固有频率误差。锁相环路能够消除抖动但调节偏移的效果不好，锁频环路则正好相反。客户机启动时通常会有较大的时间偏差，适合直接在客户端软件主界面中选择立即同步函数一次同步到位，即采用非线性调整方式调整时钟。

当系统逐渐运行稳定后，采用线性调整方式调整系统时钟，通常它由两个循环组成：外循环和内循环。外循环每隔校正周期m时间对系统时钟进行修改，内循环每隔微量调整间隔n对时钟进行微调。如果时间偏差的预测值远大于期望的精度，则m取值过大，振荡器的稳定度不能维持该精度的要求，不用增加调整的次数，只需通过减少m值来满足精度间偏差的预测值达到所需精度水平；如果预测值远小于测量值，则校正周期值明显偏小，晶振的稳定度能维持该精度，应增加m的值来减少系统开销。

6、网络时间校准算法

西安同步作为网络时间校准对时器生产厂家，我们针对局域网系统的时钟同步算法进行了较为深入的分析。时钟同步算法包括数据过滤算法、时钟选择算法(Intersection算法和Clustering算法)、合并算法和时钟调节算法，希望帮助到感兴趣的朋友。

7、网络对时器及厂家

西安同步电子科技有限公司生产的网络对时器应用于全国各地，最长的有近10年运行历史，一直稳定可靠运行。我们的网络对时器采用金属外壳设计，基于Linux系统ntp网络对时，ntp包实时更新协议版本，支持1000m网口，SYN2151型NTP时间同步服务器是销售非常好的一款网络对时器。