前言: 如何测量两台主机之间的网络延迟？想必我们会第一时间想到Ping和Traceroute这两个工具。伴随着分布式应用的蓬勃发展，网络延迟测量的需求在游戏、内容分发等领域越来越大。此时，Ping和Traceroute并不能满足实际使用要求，因此关于任意主机间的网络延迟测量研究也吸引了众多研究者。

1. 初识King

King由来自华盛顿大学的Krishna P. Gummadi于2002年提出，源代码在这里，也可以在这里查看该研究的论文成果和详细介绍。King的核心思路是将测量任意两台主机间的网络延迟转化为测量两台DNS服务器之间的网络延迟，得到一个较精确的近似值。通过实验与实际情况下的值对比，这个测量值基本与实际的网络延迟值相差无几，准确率非常高。可以用下面的图来描述一下King的脑洞：

2. King是如何工作的

King的主要工作有两个阶段：第一阶段是找到被测算主机附近离它们最近的DNS服务器（一般是权威域名服务器）；第二阶段，使两台DNS服务器之间进行查询计算出网络延迟。

第一阶段，找到离一台主机最近的权威域名服务器。

如果已知一台主机的域名，可以通过其NS记录找到所在区域的权威域名服务器。在地理位置上，权威域名服务器一般都被部署在距离主机很近的地方。而如果已知一台主机的IP地址，可以构造其包含in-addr.arpa的逆向解析域，通过查询IP的PTR记录进而找到负责解析出该IP的权威域名服务器。

如果一台主机被多个权威域名服务器解析，类似于以下情况：

此时King会通过比较每个权威域名服务器的域名和IP做出合理选择，在上面的例子中King会选择IP为192.1.2.3的权威域名服务器ns.tcc.tophant.com作为测算服务器。

第二阶段，使两台权威域名服务器之间进行查询，计算两台域名服务器间的网络延迟

现假设我们将以第三方客户端C的身份测量主机A与B之间的网络延迟，通过第一阶段的工作，我们已经找到了分别位于A附近和B附近的两台DNS服务器NS_A、NS_B，它们分别负责a.com和b.com的权威域名解析。其中，L为A与B之间的网络延迟，L'为NS_A与NS_B之间的网络延迟，并且L≈L'。L1和L2分别为C与NS_A、NS_B间的网络延迟。

现阶段的目标，是要得到L'的值，那如何计算出L'呢？

我们可以做如下操作：

#1. 以C向NS_A发起一次递归DNS查询请求，令其解析一个b.com的随机子域名fh9fvnyro802sv.b.com。
#2. 由于NS_B负责对b.com进行权威解析，因此NS_A会将此次请求递归转发至NS_B。
#3. NS_B收到请求后无法解析出fh9fvnyro802sv.b.com，向NS_A反馈NXDOMAIN消息。
#4. NS_A向C转发NXDOMAIN。

图示如下：

然而上述操作仍需有一个前提。当C向NS_A发起fh9fvnyro802sv.b.com的查询请求时，如果NS_A本地并没有b.com的权威域名服务器缓存记录，其会遍历DNS树寻找NS_B，这将使测量结果不够准确。因此必须确保NS_A提前缓存b.com的权威域名服务器记录，只需要在上述操作之前提前进行一次即可。

最后，通过上面的操作，我们可以得到整个请求响应过程的网络延迟，也就是L1+L'，随后只需要由C向NS_A发起任意的DNS查询请求或者直接使用Ping，就能得到L1，进而最终得出L'的值。当然，将上述操作的NS_A和NS_B互换，通过向NS_B发起a.com的随机子域名得到L2+L'也能得出L'。

3. King的实际情况

King在源码中将测量过程分为4步：

STAGE1：构造逆向解析域查找负责解析两台主机的权威域名服务器，它们须能接收任意主机的递归查询请求

STAGE2：再次检查这两批权威域名服务器，确定测量的方向（L1+L'或者L2+L'）

STAGE3：从两批权威域名服务器列表里根据IP段匹配的情况找到最优的两个

STAGE4：开始构造DNS请求并计算出延迟

我们在CentOS7上编译了King的源码，并挑选一些IP进行了实际测试：

经过一番测试，我们发现King在实际使用过程中效果不尽人意，程序运行在STAGE1阶段基本就会发生错误而退出。

4. King存在的问题及其改进型

虽然King从理论上证明了方法的可行性，但却避免不了其本身存在的问题。而这些问题也间接说明网络延迟测量的工程应用是极其困难的。经过实际测试并查询资料，King还存在以下几个问题，同时也衍生出了一些改进的方法：

问题1：无法准确找到负责解析主机的权威域名服务器，以至于使结果准确性大打折扣

如果某个主机使用了类似于阿里云的DNS云解析产品，权威域名服务器默认由阿里云提供，其与主机之间的距离无法确定。

另外，一些DNS服务器仅仅配置了正向解析功能，而并未配置反向解析，因此通过构造逆向解析域寻找主机PTR记录的方法不可行。甚至可能某个主机并不需要提供Web服务，因此并没有对应的域名，PTR记录为空。

问题2：负责解析主机的权威域名服务器有多台，导致测量结果不准确

在DNS规范文档RFC1034和RFC1035中，建议将解析同一域名的多个权威域名服务器部署在不同地理位置上，以此确保域名解析服务的高可用性。对于这种情况，King无法保证每次测量的结果是准确的，因为发出的解析请求可能会被转发至不同的权威域名服务器进行解析，这些服务器在地理分布上可能是分散的。

问题3：大量无用的缓存对主机权威域名服务器造成性能影响

在上面的操作例子中，如果C向NS_A查询大量的b.com的随机子域名，将在NS_A缓存中插入大量无用的关于b.com的缓存，这将非常影响NS_A的性能，甚至可以理解为缓存污染攻击。

问题4：权威域名服务器之前存在转发器，使得测量结果受到影响

一些域名会在权威域名服务器之前配置转发器以降低对权威域名服务器的大量请求，而King无法感知到转发器的存在，因此在网络延迟测量时，两台权威域名服务器之间的查询可能是经过了转发器转发，类似于下图所示：

King在论文中也提到了解决此问题的第二种测量方法，该方法也被后来的研究者称为Direct King。

首先引入一个自己可以控制的DNS服务器NS_C，该服务器负责对我们自己的域名f.com进行权威解析。接下来我们做如下操作：

#1. 使用C向NS_A发出查询b.f.com的NS记录的请求（NS_A无缓存）。
#2. NS_A接收到查询请求，会将该请求递归至f.com权威域名解析服务器NS_C。
#3. 由于NS_C可控，我们可以随意改变并构造DNS响应消息，因此将b.f.com的NS记录伪造为NS_B。随后NS_C将NS_B的IP地址x.x.x.x告诉NS_A。
#4. NS_A收到此消息后反馈至C，并在本地缓存。
#5. 使用C向NS_A发出查询随机域名f39adf8.b.f.com的A记录的请求。
#6. 由于NS_A已经将b.f.com的NS记录进行缓存，因此会递归向NS_B查询f39adf8.b.f.com的A记录。
#7. 而NS_B必定无法找到f39adf8.b.f.com的A记录，因此会向NS_A反馈NXDOMAIN消息。
#8. NS_A收到NXDOMAIN消息后继续反馈给C。

上述操作的图示如下：

图中红色部分的请求响应网络延迟为L1+L'，随后使用相同的方法即可得出L'的值。

此过程最关键的两个操作是 伪造NS记录 以及 DNS缓存投毒 ，能让测量过程绕过转发器实现对NS_B的定向选择。由于f.com域名由我们控制，因此产生的缓存投毒影响也非常小。但是此过程的操作复杂度很高，几乎无法工程运用。

问题5：不能保证找到的服务器允许任意主机对其进行递归查询

从King的论文中可知，大约72%的DNS服务器接收任意客户端的递归查询请求，当然这已经是16年前的数据。经过实际测试，一些安全性较高的DNS服务器通常都会拒绝远端的递归查询请求。

为了解决上述问题，Derek Leonard和Dmitri Loguinov提出了一个King的改进型——Turbo King。

在开始网络延迟测量之前，Turbo King维护了一个互联网中所有递归域名服务器和非递归域名服务器的列表S，其采用自建的爬虫深度爬取，并且数据会不断更新。S中服务器数量越多，对Turbo King的测量就越有效。

第一阶段，找到离一台主机最近的递归域名服务器。

Turbo King通过将公开的BGP数据与列表S比对，将一个主机的IP关联至一个递归域名服务器上，如果无法找到合适的递归域名服务器，就通过IP前缀（A类、B类、C类）进行扫描查找，或者按照King的方法选择一个默认的权威域名服务器。

第二阶段，使两台域名服务器之间进行查询，计算两台域名服务器间的网络延迟

Turbo King有两种工作模式：被动模式（默认）和主动模式。被动模式下，通过等待请求记录时间戳的方式计算网络延迟；主动模式下，Turbo King直接采用列表S中的服务器，计算一个给定数量的N*N测量矩阵，并计算出N个样本数据。

Turbo King采用C/S的软件架构，分别将DNSClient和DNSServer部署在我们自己拥有的客户端C以及域名服务器NS_C上。其测量方法如下：

#1. 使用C向NS_A发出查询t.f.com的A记录的请求（NS_A无缓存），记录此时的时间戳t1。
#2. NS_A接收到查询请求，会向负责解析f.com的权威域名解析服务器NS_C进行迭代查询。
#3. 由于NS_C由我们控制，因此告诉NS_A负责此域名的权威域名服务器为NS_B，即x.x.x.x，同时将消息TTL值设置为0避免缓存，记录下此时的时间戳t2。
#4. NS_A收到此消息后向NS_B查询t.f.com。
#5. 而NS_B必定无法找到t.f.com的A记录，因此会向NS_A反馈NXDOMAIN消息。
#6. NS_A收到NXDOMAIN消息后继续反馈给C，记录下此时的时间戳t3。

上述操作图示如下：

最后，计算得到NS_A与NS_B之间的网络延迟L'即为(t3-t2)-(t2-t1)。

从Turbo King的操作过程来看，其基本解决了King存在的诸多问题，也避免了对域名服务器本身造成缓存污染，方法上算是对Direct King的一种精简化。但Turbo King需要维护一个拥有全网所有域名服务器的列表S，这部分工作量非常大，也需要耗费很多资源。

5. King的运用

目前已经有诸多与King相关的拓展研究成果和工程运用案例，例如Chris Chambers等人在King基础上提出一种分布式的网络坐标系统Vivaldi，以及一种在线游戏的网络重定向服务，L. Garc´es-Erice等人则使用King提出一种以拓扑为中心的P2P网络查找服务TOPLUS等等。

2015年，来自加州大学伯克利分校的Ryan Rasti在论文《Temporal Lensing and its Application in Pulsing Denial-of-Service Attacks》中提出了一种基于时间差排列数据包的脉冲型反射DDoS攻击技术——时间透镜，其中对网络延迟的测量采用了King。

6. 参考

King: Estimating Latency between Arbitrary Internet End Hosts
Turbo King: Framework for Large-Scale Internet Delay Measurements