ACM通信

实践

因特网上的鲁棒定时原理

作者:Julien Ridoux, Darryl Veitch
ACM通信，2010年5月，53卷第5期，54-61页
10.1145/1735223.1735241
评论

每个人，几乎所有的东西都需要一个时钟，电脑也不例外。然而，时钟往往最终会漂移，因此有必要通过与其他一些更高精度的参考时钟同步，周期性地使它们跟上。一种既便宜又方便的方法是通过计算机网络。

自互联网早期以来，一种统称为NTP(网络时间协议)的系统一直被用于允许客户端计算机(如pc)连接到安装了高质量时钟的其他计算机(NTP服务器)。通过交换以ntp格式的包在网络上传输的包时间戳，PC可以使用服务器的时钟来纠正自己的时钟。作为NTP时钟软件，尤其ntpd它是一项非常成功的技术，其用户基数相当于全球计算机人口的数量。

尽管NTP系统多年来在通用用途上运行良好，但其准确性和稳健性都低于底层硬件所能达到的水平，并不足以应对未来的挑战。其中一个领域是电信行业，该行业正忙于用廉价的异步以太网线路取代移动基站同步回程系统(该系统曾经作为副产品提供亚微秒级的基于硬件的同步)。另一个是金融行业的高速交易，减少交易所和交易中心之间的延迟与利用它们获利的能力之间存在直接关系。在这里，准确的交易时间戳至关重要。更一般地说，时间是非常重要的，因为光速是有限的，网络节点之间的延迟受到硬约束，这不会被未来更快的处理器或带宽的增加所击败。不能规避的必须严格管理，而这没有精确的同步是不可能的。

回到顶部

的发条

当讨论转向时钟时，困惑往往很快就会出现。为了避免迷失在钟表上，让我们定义一些术语。通过t我们指的是牛顿宇宙中以秒为单位的真实时间，原点在任意时间点。我们说时钟C读取C (t)在真正的时间t．图1展示了一些时钟在(真)时间流逝时所读取的内容。黑色的时钟C_p(t)是完美的:C_pt (t) =，而蓝色的钟C_年代(t)＝C₀+ (1 +x）t是由C₀当t= 0。事实上，当它以一个恒定但过快的速率运行时，它会变得更糟，速率误差就是斜x。红色的钟C_d(t)＝t + E (t)是比较现实的，它的错误E (t)随着时间的变化而变化，时钟被称为漂移．漂移远非无目的的，事实上它与温度变化密切相关。图6(稍后将详细讨论)给出了漂移的近距离观察E (t)(黑色曲线)为Pentium PC在两天时间内的时钟不同步。

每个时钟的核心都是硬件。在个人电脑中，这是主板上的一个振荡器。振荡器以几乎恒定的速率“滴答”，实际上，平均变化只有0.1 ppm(百万分之一)。硬件计数器如HPET(高性能事件计时器)计算这些刻度，使操作系统能够访问一个缓慢漂移的计时源。从这样的计数器中，可以定义一个时钟，粗略地说，将计数器单位转换为秒，并添加一个常数来设置时间原点:

在哪里p (t)为HPET计数器的(缓慢时间变化)秒周期。时钟同步算法的作用是设置和定期更新的值C₀而且p (t)减少漂移或误差E (t)＝C t (t)，尽可能多。

进入互联网。同步算法没有办法修正的漂移C (t)从计数器继承而来，而不求助于任何独立的专家:参考计时源或大师。附加额外的硬件是可能的，但昂贵，而且没有意义，除非它是可靠的。当你说服建筑监督人员将一个高质量的GPS安装在屋顶上，并通过电缆连接到你的办公室时，一个卫星能见度一贯良好的GPS可能要花费数千美元。哦，你至少要花六个月的时间才能完成。原子钟甚至更贵，而且仍然需要GPS来避免在每周或更长时间内漂移。相比之下，通过网络进行同步不需要时间，不需要资金，也不需要太多努力。

回到顶部

关键挑战:延迟可变性

时钟同步在原理上很简单。你问专家现在几点了，他看了看表，告诉你，你就对了表。简单。问题是每一个步骤都需要时间，而在互联网上，这些延迟可能很大，不可预测，并且高度可变。对于同步算法来说，关键的挑战几乎是唯一的挑战，就是能够应对这些变化，稳健而精确地消除由延迟变化引起的误差。

定时包所遭受的延迟是在主机和网络(以及服务器，但我们将慷慨地假设一个完美的参考时钟)中产生的。在主机中，延迟来自NIC(网络接口卡)行为、操作系统进程调度和包时间戳代码的体系结构，大约为几十微秒。在网络中，它们是由IP路由器和第二层交换机等网络元素的排队引起的，在千兆以太网局域网中，它们的时间相差很大，在网络拥塞严重且服务器距离几跳远的情况下，它们的时间可能只有几百毫秒。

在我们这里关注的双向同步范型中(另一种方法是仅从服务器进行广播)，定时包是双向交换的(参见图2)．转发(主机到服务器)中的单向延迟:d)和向后(服务器到主机:d)方向有自己独立的主机和网络组件。在每个方向上添加owd得到hostserverhost RTT(往返时间)。

图3提供了一个实例，当主机和服务器都在局域网中时，以及主机组件本身。每个变量的变化都远远超过了它的最小值，这意味着同步算法必须以某种方式看穿一个大的“噪声”。

回到顶部

适合工作的时间

时钟的三个主要用途是:

• 在事件之间建立严格的顺序，
• 度量事件之间的时间持续时间和
• 定义一个具有普遍可比性和可触发性的事件标签，即“一天中的时间”。

一个完美的时钟理想地适用于这些目的，但在现实世界中，硬件和软件的限制意味着最好的性能是由专门的时钟实现的。为工作选择合适的时间是至关重要的，但这一点并没有被广泛理解。

当人们想到时钟时，通常会想到它的第三种用途:告诉人们时间的时钟绝对时间。然而，面对延迟的可变性，同步这样的时钟本身就很困难。因此，绝对时钟的精确度C_一个(t)可以是低的，随时间变化很大的，并从属于网络条件。绝对时钟还必须支持跳复位的能力，包括向后复位。虽然这种情况可能很少，但这使它们不太适合使用。

建立时间秩序的更好选择是行为良好的原始计数器，如HPET(t)，单调递增。同样地，我们可以将这种计数器缩放成一个简单的因果时钟，以秒为单位进行校准:C_c(t)＝p₀·HPET (t),p₀是一个永不更新的常量。这样的时钟告诉错误的时间和漂移，但在使用1方面做得很好，并且完全独立于网络条件，实际上根本不需要服务器时间戳!

绝对时钟的误差C_一个(t)也使其不适合使用2。最好通过一个例子来了解这一点:如果计数器的速率误差为0.1 ppm(这在合理温度环境下的PC中非常典型)，那么在一秒钟的间隔内，漂移的误差仅为10⁷·1 = 0.1 s。另一方面，错误在C_一个(t)，因此在持续时间测量中，可能是几s到几ms，在极端情况下可能大于一秒，这取决于诸如网络拥塞和算法鲁棒性等因素。

为了测量时差的目的，更好的选择是使用区别钟表，也就是不因漂移而修正的钟表。一个简单的例子是:

在哪里C₀是常量(从不更新)，和p_av是对长期平均利率的估计，我们可以把它看作一个常数(为了清楚起见，我们在这里稍微简化了一下;参见Veitch等人。⁴详情)。这样的时钟只告诉大约正确的时间和漂移，但在使用2的条件下，它做了很好的工作p_av可以稳健而准确地估计(这是可以的)。它是依赖于服务器时间戳，但以一种更不敏感和更健壮的方式C_一个(t)，因为它直接利用了本地硬件的高稳定性(速率常数高达0.1 ppm)。

图4比较从GPS接收器进入PC串行端口的脉冲之间的时间误差(名义上精确间隔一秒)与用精确绝对时钟和精确差时钟测量的时间误差。尽管服务器距离很近(最小RTT约为1毫秒)，但它们的数量级不同。事实上，操作系统/串口为这些测量增加了大约2秒的噪声，因此实际上掩盖了误差C_d(t)差差时钟在一秒刻度上如此出色，以至于测量它的误差是一项严峻的挑战!

最后一个关键点:差值时钟的工作原理是战略性地忽略漂移，但随着时间的推移，产生的误差会增加，因此差值时钟会失去精度。一个好的经验法则是交叉发生在= 1000秒。超过这个刻度的持续时间应该使用绝对时钟来计算。这个交叉值可以通过寻找最小值来计算艾伦偏差图，测量振荡器的稳定性(作为时间尺度的函数的变异性)。

回到顶部

范例时间:反馈还是前馈?

考虑以下同步绝对时钟的方法C_一个(t)．定时数据包在使用的主机上进行时间戳C_一个．将这些时间戳与服务器获取的时间戳进行比较，并对时钟错误进行评估。的速度C_一个然后稍作调整，随着时间的推移使误差为零。这是一个例子反馈方法，因为前一轮时钟修正直接作为输入反馈给算法，因为它就是时钟C_一个本身，它用于生成主机时间戳。

另一种方法是使用底层计数器来生主机中的包时间戳(即计数器读数)。然后根据这些和服务器时间戳估计时钟错误，并在读取时钟时“减去”。这是一个前馈方法，因为错误是根据后处理输出纠正的，而这些输出本身不会反馈到下一轮输入中。换句话说，原始时间戳与时钟状态无关。有人可能会说，硬件的现实是直接可见的，而不是通过算法眼镜看到它。

NTP同步算法是一种反馈设计。它使用PLL(锁相环)和FLL(锁频环)的组合方法来锁定服务器时钟的节奏。²前馈设计的一个例子是RADclock，这是一种双向、最小rtt滤波、基于前馈的绝对和差分同步算法，这是我们在墨尔本大学的RADclock项目的核心。⁴

在Internet环境中，反馈方法有两个显著的缺点，其中延迟很大且高度可变，反馈速率很低(定时包之间的周期通常在64到1024秒之间，因为为了可伸缩性，我们不能用定时包使网络饱和)。第一个缺点是经典的控制方法如锁相环和FLL的稳定性不能得到保证。换句话说，如果条件不够好，它们可能会失去锁，导致转向高错误模式，这种模式可能会持续很长一段时间，甚至是永久性的。图5给出一个例子，比较误差ntpd以及绝对RADclock(在不拥塞的局域网上向服务器共享完全相同的计时包)超过两周。的反馈稳定性ntpd在许多情况下丢失，导致更大的错误。

第二个缺点是时钟不同甚至无法定义在反馈框架中，我们失去了它们的好处，不仅包括更高的准确性，而且还包括更高的鲁棒性。值得注意的是，在网络中，时差可以说比绝对时间更常用。延迟抖动、rtt、到达间时间和代码执行时间都是用差分时钟最好测量的时间差的例子。

前馈方法的一个缺点是，它本身并不能保证时钟永远不会后退;然而，因果关系强制时钟读取函数可以在不影响核心设计的情况下解决这个问题。

回到顶部

支持的问题

NTP系统是主流的，所有主流操作系统都支持NTP。让我们看看一些内核支持问题，重点关注FreeBSD和Linux。

由内核维护的系统时钟(它提供了众所周知的gettimeofday ()函数调用)，以及对算法的内核支持来约束它，在过去和现在都与的需求密切相关ntpd守护进程。特别是反抽象(timecounter在FreeBSD和clocksource在Linux中)，它允许进程访问系统中可用的不同硬件计数器，但却无法提供直接对原始计数器值的访问。相反，它们只能通过使用底层计数器的系统时钟所获取的时间戳进行访问。换句话说，内核api只支持反馈范式;很简单，前馈算法被禁止参与。

另一个重要的结果ntpd现有系统时钟同步体系结构的面向对象特性是，反馈循环鼓励分离用户空间和内核之间的算法“智能”。的ntpdDaemon在前者中运行，但是系统时钟有它自己的自适应过程，实际上是一个辅助同步系统。通过反馈回路连接的两个反馈系统很难保持稳定、维护甚至理解。相比之下，通过使用户空间访问原始计数器值，前馈算法可以完全避免辅助系统，并将算法智能和设计集中在一个定义良好的单一位置。这样分工就很清晰了:同步算法负责同步;内核处理时间戳。

注意，就像在因果时钟中一样C_c(t)，计数器可以按一个常数缩放，从而读取更方便和通用的单位，这不会影响前馈算法基于它进行同步的能力。Linux的时钟单调乏味，提供了这样一个按比例计算的计数器，它以(近似的和漂移的)纳秒计时。

目前，RADclock通过提供补丁以最小的方式扩展FreeBSD和Linux中的这些机制来解决前馈支持的不足，从而允许对内核和用户空间的原始计数器访问。RADclock API包括基于直接计数器时间戳的差值和绝对时钟读取函数，结合最新时钟参数和漂移估计。

回到顶部

被遗忘的挑战

在继续之前，我们应该指出一个恼人的事实:网络上的同步实际上是不可能的。为了理解这一点，让我们通过假设零网络拥塞和系统负载来减少问题的本质，以便所有延迟都取其恒定的最小值。

让一个＝dd表示真实路径不对称，其中d而且d分别是到服务器和从服务器的真正的最小单向延迟;,让r＝d+d为最小RTT(见图2)．问题在于存在一种基本的模糊性，因为路径不对称不能独立于时钟误差进行测量。其本质如下:如果我收到一个时间戳T从服务器t= 1.1阅读T= 1，我不知道我是否完美地同步到一个服务器d= 0.1秒，或者，如果我落后真实时间1秒(包实际到达t= 2.1)，服务器在1.1秒之外。

即使在原则上，任何算法都不能避免这种不对称的模糊性。不过，也有一些好消息。首先，这个问题只困扰绝对时钟;差异时钟不受影响。其次，双向交换允许来自因果关系(数据包在发送之前不能到达)的约束起作用。因此，不对称和相关的时钟误差是固定的，即使他们不能精确地知道。

问题仍然是，绝对时钟是如何实现不可能的?他们归还的是什么?在实践中，在没有任何外部信息的情况下一个，我们必须猜测一个值，和一个= 0通常对应于对称路径。这允许时钟同步，但只能同步到未知的错误E在[r，r］．在某些情况下，这个范围可能是几十毫秒宽，可以使其他错误相形见绌。

这里还有一个要点需要记住。真正的不对称(比如由于路由的改变)或算法使用的对不对称的估计的任何改变都会使时钟跳变。例如，基于主机和服务器之间路由的一些知识r= 15毫秒之外，一个无畏的管理员可以替换默认值一个= 0，最好的猜测是一个= 3 ms，导致3/2 = 1.5 ms的跳跃。另一个例子是服务器选择的改变，这不可避免地带来了不对称的变化。关键在于，即使跳跃能够改善同步性，但它本身也是一种邪恶。这样的不对称的抖动不仅会使这个主机上的软件感到困惑，而且还会使其他主机上的软件感到困惑，因为所有测量到主机和从主机发出的OWD也会发生跳跃。

总之，网络同步包括两个非常不同的方面。同步算法的作用是看穿并消除延迟的可变性。如果它成功做到这一点，即使不对称误差和最终时钟误差很大，它也被认为是准确的，因为它不能对此做任何事情。不对称抖动问题不是关于可变性，而是一个未知常数。这就简单多了;但是，即使是在原则上，也无法规避，因此从本质上来说很难。这就是挑战:尽管它无法被消除，不对称的实际影响很大程度上取决于如何管理它。这两个截然不同的问题在一个关键方面有交集:它们都受益于附近的服务器。

健壮的算法设计

下面是可靠同步的关键元素列表。

不要忘记物理。时钟的基础是本地硬件。任何自重的算法都应该从使用一个有物理意义的模型来整合其行为的本质开始。特别重要的是其稳定性的以下简单表征:大尺度速率误差界限(0.1 ppm)和振荡器变异性最小的时间尺度(= 1000秒)。这些特征在PC架构中非常稳定，但算法应该对它们的精确值不敏感。

---

有了前馈，硬件现实就可以直接看到，而不是通过算法眼镜来观察。

---

另一个基本的物理组成部分是延迟的性质。对于排队延迟，以及OWD和RTT，一个好的通用模型是一个常数加上一个正的随机噪声。这个常数(最小值)在图3在RTT的例子中。

使用前馈。前馈方法提供了更高的鲁棒性，这在像Internet这样嘈杂的不可预测的环境中是必不可少的。它还允许定义差分时钟，这反过来是绝对时钟的鲁棒滤波的关键，对大多数计时应用程序(包括网络测量(owd除外))具有直接价值。

差异时钟是第一位的。同步差时钟相当于测量长期平均周期p_av．这种“速率同步”比绝对同步更基本、更重要，也容易得多。一个健壮的解决方案是一个坚实的基础，可以在此基础上构建更加复杂的绝对同步。

请注意,由速度同步我们指的是低噪声估计长期平均利率/周期，不要与短期利率混淆，它本质上简化为(导数)漂移，因此是绝对同步。

使用最小的基于rt的过滤。如果一个定时包足够幸运地经历了最小的延迟，那么它的时间戳就没有被损坏，可以用来直接将绝对时钟设置为正确的值(不对称除外)。问题是，我们如何确定哪些包是幸运包?

不幸的是，这是一个先有鸡还是先有蛋的问题，因为要测量OWD，我们必须使用绝对时钟C_一个(t)，这是我们首先要同步的。幸运的是，rtt的情况不同，它可以通过差分时钟来测量C_d(t)．关键的结果是，不需要首先完全同步时钟，就可以获得包质量的可靠度量。一种方法是衡量给定定时包的RTT超过最小RTT的程度:差距越小，包的“质量”越高。

眼尖的读者会注意到，一个鸡生蛋还是蛋生鸡的问题仍然存在。差分时钟也需要过滤以同步它，那么我们如何在它同步之前使用它呢?答案是即使是一个很差的估计p_av足以执行有意义的过滤。例如，想象一下p_av已知的精度为100ppm(这真的很糟糕)，RTT=10ms。那么RTT测量的误差(包括漂移引起的误差)在1 s量级，这远远低于操作系统引起的噪声(大约10 s)。

速度同步。让我们假设我们的过滤是成功的，所以我们可以可靠地测量定时包的质量水平。

速率同步的关键(即测量)p_av)，这是一个长期的平均水平，这意味着我们可以有耐心!因此，可靠的速率同步非常简单，只需在大间隔的两端收集合理质量的时间戳(理想情况下是几天，但甚至更短也可以)。时间戳错误和质量评估中的错误被间隔的大小压缩，进入0.001-ppm区域，在那里它们再也不会打扰您。

一旦同步,p_av价值的寿命很长。一个后果是，即使与服务器的连接丢失，差异时钟也会保持良好的同步。使用经过硬件验证的测试平台，我们进行的测试表明，即使在与服务器断开20天后，RAD-clock差时钟测量的间隔时间也达到了一秒以下的精度。将这种级别的鲁棒性与绝对同步的鲁棒性进行比较，在绝对同步的时间间隔内，本地时钟将不可避免地发生相当大的漂移，甚至更糟。

绝对同步。漂移是不断发生的，时钟必须随时准备好被读取。由此可见，耐心在这里不是一个选项:即使拥塞严重，计时数据包延迟，也必须在糟糕的情况下取得最好的结果;漂移问题必须解决。

有两个主要的考虑因素。第一种方法是利用定时包质量来控制其对时钟误差估计的贡献。控制必须非常严格:如果包的RTT仅略高于最小值，则该间隙直接对应于要避免的错误。

第二个要考虑的是时间尺度。最基本的权衡是需要来自尽可能多的定时数据包的数据来增加幸运的机会，而不是需要这些数据是最近的，以便估计当前的错误，而不是来自过去的过时的错误。在这方面，时间尺度起着关键作用，因为它对回溯过去的时间设定了一个有意义的限制。

绝对时钟可以简单地如下定义:

在哪里E (t)是误差的估计吗C_d(t)，当绝对时钟被进程读取时，它会被移除。图6显示E (t)如蓝色曲线所示，这是基于噪声未过滤的每包错误估计(绿色峰值)计算的。真正的错误E (t)是使用外部gps同步DAG捕获卡测量的黑色曲线吗¹在我们的试验台上。

一台服务器就足够了。到目前为止，我们讨论了同步到单个服务器。人们当然可以连接多个服务器，并在其中进行选择，以获得更好的结果吗?原则上这是对的;在互联网实践中，至少就目前的技术水平而言，它绝对不是，原因有二。

最根本的是，切换服务器意味着路径不对称的改变，因此时钟会跳变。想象一下，服务器选择算法在质量相似的候选服务器之间移动。结果是不断跳动，这是典型的不对称抖动。这种抖动并不难观察到ntpd，实际上建议连接到多个对等体。

其次，一旦性能调优到接近系统和网络噪声限制，任何干扰都会降低性能。例如，停止查询服务器一段时间，然后返回到它，就可以称为中等到较大的中断。

给管理员的重要信息是:如果您想提高系统时钟性能，只需确保配置只指向单个(附近的)服务器。

看你的路线。服务器确实会改变，即使它们不会改变，到它们的路由最终也会改变。这不仅会导致不可避免的跳跃，因为不对称的原因，这也是对同步算法本身的挑战。需要精心设计，以便速率和绝对同步算法能够优雅而健壮地过渡到新环境。这必须从一个经过深思熟虑的筛选质量评估方法开始。如果这种情况发生了，那么质量包可以被评估为好和坏，并且潜在的损害是没有限制的。

相信自己。是的，服务器是专家，没有它同步是不可能的。然而，它不应该被信任。服务器可以也确实有不好的时期，对他们的盲目信任会导致严重的麻烦。幸运的是，还有另一个权威可用:计数器模型。如果RTT过滤告诉您拥塞很低，但服务器时间戳却告诉您突然出现了问题，那么请信任硬件，并使用模型对服务器进行健康检查。基本上，一个远远超过1ppm的漂移是不可信的，算法应该闻到了老鼠。

有疑问时，就随波逐流。如果拥塞变得如此之高，以致所有可用的时间戳都不具有可接受的质量，该怎么办?如果我不信任服务器，或者与服务器完全失去联系，该怎么办?

只有一件事可以做:坐下来放松。什么坏事都不会发生，除非算法选择让它发生。在前馈范式中实现不作为反应是微不足道的，结果只是让计数器优雅地漂移。记住，计数器是高度稳定的，在最坏的情况下，每秒只能积累大约1秒。

更一般地说，算法应该被设计成永远不会对任何事情反应过度。请记住，它对世界的看法总是近似的，可能是错误的，所以当不作为如此有效时，为什么要试图太聪明?不幸的是，反馈算法如ntpd有更多的反应性策略，使时钟更强烈地朝他们的观点方向移动。这是它们对破坏性事件的非鲁棒性的主要来源。

回到顶部

更大的图景

到目前为止，我们已经考虑了网络上的单个主机到服务器的同步，但是整个系统又是怎样的呢?在NTP中，主要的系统方面是服务器层次结构。简而言之，Stratum-1服务器使用额外的硬件(例如，带有GPS接收器的PC或带有GPS的专用同步盒)进行本地同步，而不是通过网络进行同步。根据定义，Stratum-2服务器同步到Stratum-1, Stratum-3同步到Stratum-2，以此类推，主机同步到它们能找到的任何东西(通常是Stratum-2或公共Stratum-1)。

在系统一级，有一些重要和突出的挑战。strata -1服务器之间不通信，而是作为独立的孤岛(除了在有限情况下的负载平衡)。单独查询服务器以获取基本信息的能力是有限的，例如它是否连接到其硬件，是否认为它是同步的，而且没有能力将服务器集作为一个整体进行查询。一个相互连接和不对称感知的strata -1基础设施可以为客户提供许多有价值的服务。这些建议包括关于最适合客户机的服务器的建议、考虑到不对称抖动的备份服务器的自动提供以及关于服务器质量的验证信息。目前，没有人能把矛头指向不可靠的服务器，但它们确实存在。

---

是的，服务器是专家，没有它同步是不可能的。然而，它不应该被信任。服务器可以也确实有不好的时期，对他们的盲目信任会导致严重的麻烦。

---

RADclock项目建立在RADclock算法的基础上^3.旨在解决这些问题，并作为推动在两年内为网络计时提供一个健壮的新系统的一部分。有关下载现有客户端和服务器软件(用于FreeBSD和Linux的软件包)、文档和出版物的详细信息，可以在RADclock项目页面上找到。

回到顶部

致谢

RADclock项目得到了澳大利亚研究委员会发现项目资助计划(项目编号DP0985673)、硅谷社区基金会思科大学研究计划基金和谷歌研究奖的部分支持。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2010 ACM, Inc。