DNS权威服务器选择方式研究

王圣元+张宇+李东

摘要： 关键词： 中图分类号： 文献标志码： A文章编号： 2095-2163（2017）06-0122-06

Abstract： This paper studies the selection of authoritative DNS server. In order to enhance the robustness and performance of a domain name， most domains are configured with multiple authoritative DNS servers. When the DNS recursive server receives a query for the domain name， it needs to select one of the authoritative DNS server to query. However， the specific manner of choice is unclear， and the relevant RFC standards do not stipulate the way in which the recursive server chooses the authoritative DNS server. This paper analyzes the selection algorithm of each common DNS server version for the authoritative server， and discusses the selection effects of these algorithms and the factors influencing the selection effect. The paper also measures the open DNS recursive server throughout China and analyzes its selection effect on the authoritative server.

0引言

伴隨着因特网的快速发展，人们的生活早已与网络息息相关。各种各样的网络服务给人们带来无穷的便利。域名系统作为因特网最重要的基础设施之一，提供域名到IP地址的转换服务，是一切网络服务正常运行的基石，其稳定性及其它性能对因特网有重要的影响[1]。

当DNS递归服务器对一个拥有多个DNS权威服务器的域进行查询时，DNS递归服务器需要选择其中一个开展进一步的查询。其选择的结果对查询的响应时间有很大的影响[2]，各个版本的DNS服务器对权威服务器的选择算法会直接影响其性能。

本文分析了常见的服务器选择算法，并对各个版本DNS服务器采用的算法进行了研究。发现了对算法选择结果产生影响的多个因素，并对全国范围内开放DNS递归服务器对权威服务器的选择方式进行测量和分析。

1DNS权威服务器选择算法

1.1权威服务器选择算法分类

在有多个备选的DNS服务器可供选择的情况下，相关的RFC文档[3]没有对选择的方法做出明确规定，各个版本DNS服务器选择方式不同，主要有平均选择算法和RTT（Round trip time）相关的选择算法两个类别。平均选择算法不考虑递归服务器到各个权威服务器的延迟或跳数，无差别地选择DNS权威服务器进行查询。这种方法的优点在于实现简单，且由于查询的DNS权威服务器为随机选择，可以使得一些DNS攻击方式更加难以实施，例如Kaminsky缓存攻击[4]。其缺点在于递归服务器不能选择延迟较小的权威服务器进行查询，整体性能较差[5]。RTT相关的算法以往返时间RTT为度量方式来对同一个域的多个DNS权威服务器进行选择，可以直接选择RTT值最小的DNS权威服务器进行查询，也可以按照RTT值的大小给出概率，并按照概率的大小选择，通常RTT值越小的DNS权威服务器被选择的概率越大，以此来达到更好的性能，即更快地获得查询结果。

1.2SRTT算法

在与RTT相关的服务器选择算法中，最常见的是SRTT（Smoothed Round Trip Time）算法。BIND（Berkeley Internet Name Domain）服务器采用SRTT选择算法。SRTT算法动态地维护一个备选的DNS权威服务器的IP列表，并通过这些DNS权威服务器的SRTT时间来选择其中一个进行查询，其中SRTT为平滑的RTT时延，而具体的计算规则可表述如下：

1）初始化。 当某个备选的DNS权威服务器不存在于递归服务器的缓存中时，需要对其赋一个初始值SRTTinit。数学计算公式如下：SRTTinit=31^R μsec（1）其中，R为一个32比特的随机数。公式所计算出的SRTT初始值远小于实际网络中的往返时间，这使得每个备选的DNS权威服务器都能被选择至少一次，以获得其实际的往返延迟。

2）SRTT的计算。当DNS递归服务器发出的某个查询收到应答时，给出应答的DNS权威服务器的SRTT会依据本次查询所获得的新的RTT和之前已有的SRTT加权求和计算得出。研究得到公式如下：SRTTnew=αSRTTold+1-αRTTnew（2）在BIND服务器（版本9.8.0）中，α取值为0.7[6]。

3）SRTT衰减。为了防止在查询时只选择某个SRTT最小的DNS权威服务器，在收到某次查询的应答时，该次查询未被选择的权威服务器的SRTT需要按照一定的规则衰减。推导可得公式如下：SRTTnew=βSRTTold（3）在BIND服务器（版本9.8.0）中，β取值为0.98。而在PowerDNS[7]中，β的计算公式如下：β=etn-tn+1c（4）其中， c为常数，tn-tn+1为两次查询的时间间隔。endprint

由于网络处在不断变化中，原本RTT较大的DNS权威服务器可能会变为RTT较小的。为了探测到这一变化，DNS递归服务器需要先对其进行选择，但如果没有探测到该变化，则不会对其设定选择。这就造成了死锁的状态，为了解决这一问题，大多数RTT相关的选择算法都会采取RTT衰减的策略，即对于没有被选择的DNS权威服务器，其记录的RTT值会按照一定的方式逐渐变小，使得每个DNS权威服务器都有被选择的机会。

2可控环境下权威服务器选择算法的测量和分析

2.1测量环境

为了研究DNS递归服务器对DNS权威服务器选择的算法及效果，在独立的网络环境下进行实验。实验环境如图1所示。其中，a.xxx.cn为xxx.cn的子域，a.xxx.cn有五个DNS权威服务器负责解析该子域下的域名，这五台DNS权威服务器向外发送的报文分别设置有不同的延迟时间。由于实验在同一网段下进行，原本服务器间的往返时间可以忽略不计，递归服务器到权威服务器的实际RTT只取决于各个权威服务器的延迟时间的设定。

客户端向DNS递归服务器发送子域a.xxx.cn下的域名的查询，触发DNS递归服务器访问备选的五台DNS权威服务器之一。统计各个版本的DNS递归服务器对数个DNS权威服务器选择的分布情况。所测量的DNS递归服务器版本如表1所示。

2.2不同版本DNS服务器的权威服务器选择结果

将DNS递归服务器到各个权威服务器的RTT大小设置为60 ms、80 ms、100 ms、120 ms、140 ms，查询速率为40次/s，测量表1中的各版本DNS服务器对权威服务器的选择分布情況，实验结果如图2所示。

其中，图2（a）为BIND 9.8实验结果，图2（b）为BIND 9.7实验结果。此二者在选择DNS权威服务器时，都更多地选择RTT较小的权威服务器。BIND服务器采用SRTT算法对权威服务器进行选择， BIND 9.8直接选择SRTT值最小的权威服务器进行查询，BIND 9.7则按照SRTT的大小设置概率，并依据概率选择权威服务器进行查询。两者选择的结果相差不大，各个权威服务器被选择的比例都与RTT成反比。Windows DNS Server采用平均选择的方式选择权威服务器进行查询，各个权威服务器基本被均匀选择，结果如图2（c）所示。PowerDNS和BIND 9.1服务器的实验结果如图2（d）和图2（e）所示。BIND 9.1虽然也采用SRTT算法，但并没进行SRTT衰减，因此其结果与其他版本BIND服务器不同。PowerDNS采用了SRTT衰减的策略，但其衰减的速度过慢，大量的查询仍被发往RTT最小的权威服务器。虽然具体原因不同，但这2种服务器的表现形式都为选择最优（RTT最小）的权威服务器。

如果用实验中每次查询所用的平均时间（平均往返时延）代表DNS递归服务器的查询效率，利用DNS递归服务器发往各个权威服务器上的查询所占比例的标准差代表查询分布的离散情况。则Windows DNS Server采用随机选择的方式，查询效率最低，查询分布得最均匀。BIND 9.1和PowerDNS在选择DNS权威服务器进行查询时，表现出的形式为选择最优服务器，这种方式查询的效率最高，其查询分布得最不均匀，标准差最大。

2.3查询速率和查询时延对算法效果的影响

2.3.1查询速率对算法选择结果的影响

在保持DNS递归服务器到各个DNS权威服务器往返时延不变的情况下，改变客户端的查询速率，分别设置为40次/s、80次/s、160次/s、240次/s、300次/s查询。在这些不同的客户端查询速率下，统计BIND 9.8和BIND 9.7服务器的平均查询时间，结果如图3所示。

可以看出，随着客户端查询速率的加快，BIND 9.8服务器和BIND 9.7服务器的平均查询时间都逐渐增大，而BIND 9.8服务器增加的幅度更大。两者在查询速率变高时，选择较小往返延迟的DNS权威服务器进行查询的比例逐渐减少，而选择较大往返延迟的比例逐渐增加。由于BIND 9.7服务器采用的是根据与RTT相关的概率随机选择，因此变化的幅度没有BIND 9.8大。

BIND 9.8服务器在高查询速率下，出现了更多地选择高RTT的DNS权威服务器进行查询的现象，在查询速率为300次/s的情况下，BIND 9.7和BIND 9.8实验结果如图4所示。这是由于SRTT算法本身导致的。具体原因在2.3.3小节中进行分析。

2.3.2往返时延大小对算法选择结果的影响

除了客户端的查询速率可能会对实验结果产生影响之外，往返时延的大小本身也会对DNS权威服务器的选择结果产生影响。将客户端的查询速率设置为80次/s，并改变DNS递归服务器到DNS权威服务器的往返延迟。观察BIND 9.8服务器对DNS权威服务器的选择结果。

首先，将DNS递归服务器到各个DNS权威服务器的往返延迟的比例固定，改变其大小，分别设置为20 ms、40 ms、60 ms、80 ms、100 ms和100 ms、200 ms、300 ms、400 ms、500 ms，实验结果如图5（a）所示。再将DNS递归服务器到各个DNS权威服务器的往返延迟的差值固定，改变其大小，分别设置为 20 ms、40 ms、60 ms、80 ms、100 ms， 40 ms、60 ms、80 ms、100 ms、120 ms和60 ms、80 ms、100 ms、120 ms、140 ms三组，实验结果如图5（b）所示。

从图5的实验结果中可以看出，在DNS递归服务器与备选的DNS权威服务器之间的往返时延等比例地扩大时，DNS递归服务器趋向于平均选择DNS权威服务器进行查询。当各个备选DNS权威服务器往返时延的差值不变，而绝对值增加时，DNS递归服务器发往各个DNS权威服务器的查询比例趋向于相等。具体的原因在2.3.3小节中进行分析。endprint

2.3.3SRTT算法的分析

在BIND 9.8采用的SRTT算法当中，当一个DNS权威服务器被缓存后，如果对应的SRTT值不是最小的，则进行SRTT值衰减至最小，再选择其进行查询；如果对应的SRTT值是最小的，则选择该服务器进行查询，并根据实际查询的往返时延来更新SRTT值。因此，可以将一个DNS权威服务器的SRTT值的变化分为SRTT衰减、被选择、SRTT更新三个阶段。

假设某个域有n台DNS权威服务器负责解析，分别为NS1， NS2， …， NSn，对应的往返时延分别为RTT1， RTT2， …， RTTn，其中某个权威服务器NSi的SRTT值为SRTTi，其SRTT变化曲线如图6所示。在SRTT衰减阶段，DNS权威服务器NSi的SRTT值不是最小的，当DNS递归服务器收到一个该域的查询请求时，会选择该域的其他DNS权威服务器进行查询，此时，每当收到一个该域权威服务器的应答，权威服务器NSi的SRTT按照一定的方式进行衰减，通常为乘以一个小于1的衰减系数。SRTT衰减阶段对应图6中的t1～t2阶段。DNS递归服务器在t′2时发出一次查询，在t3时刻收到查询的应答并对NSi的SRTT进行衰减，此次衰减使SRTTi比该域其他DNS权威服务器的SRTT值都小，进入到被选择阶段。

在被选择阶段，每当DNS递归服务器收到一个该域的递归查询时，都会选择NSi进行进一步查询。当客户端的查询速率较高时，在t′2～t2间仍有许多发往其他DNS权威服务器的请求尚未收到应答，当递归服务器收到这些查询的应答时，NSi的SRTT仍然会减小，对应图6中的t2～t3阶段。从t3开始，DNS递归服务器收到在t2～t3阶段发送给NSi的查询的应答，并根据实际的往返时延对NSi的SRTT值进行更新。经过数次更新后，从t4开始，NSi的SRTT不再是最小的，此时进入SRTT更新阶段。

在SRTT更新阶段中，递归服务器不会再选择NSi进行查询。但DNS递归服务器可能会继续收到NSi的应答报文，并对NSi的SRTT进行更新。到t5时，收到被选择阶段中递归服务器发往NSi的查询的所有应答后，NSi再次进入SRTT衰减阶段。

若有一个备选的DNS权威服务器NSi，其SRTT衰减阶段所占时间为tdecay=t2-t1，被选择阶段所占时间为tselect=t4-t2，选择后的SRTT更新阶段所占时间为tupdate=t5-t4，则选择该权威服务器进行查询的占比Pi为：Pi=tselecttdecay+tselect+tupdate（5）DNS递归服务器从t2时刻开始向NSi发送查询，到t3时刻收到NSi返回的应答，t2与t3间的时间间隔取决于DNS递归服务器与NSi间的往返时延。在BIND 9.8中，进行SRTT衰减时的系数为0.98，SRTT在增长时采用与实际RTT加权平均的方式。当实际的RTT与衰减后得到的SRTT相差较大时，只要收到少数几个NSi的应答并对SRTTi进行更新后，SRTTi就不再是最小的SRTT值。因此，tselect的大小主要取决于DNS递归服务器与NSi间的RTT大小。

参考文献：

[1]孙瑞. 基于分布式平台的DNS信息探测系统设计与实现[D]. 哈尔滨：哈尔滨工业大学， 2013.

[2] SOMEGAWA R， CHO K， SEKIYA Y， et al. The effects of server placement and server selection for Internet services[J]. Ieice Transactions on Communications， 2003， 86（2）：542-552.

[3] Mockapetris P. Domain namesConcepts and facilities[EB/OL]. [1987-11]. http：//tools.ietf.org/html/rfc1034.

[4] Friedl S. An illustrated guide to the kaminsky dns vulnerability[EB/OL]. [2008-08-07].http：//unixwiz.net/techtips/iguidekaminskydnsvuln.html.

[5] MIYACHI T， CHO K， SHINODA Y. On the stability of server selection algorithms against network fluctuations[M]//CHO K， JACQUET P. Technologies for advanced heterogeneous networks. Berlin/Heidelberg： Springer， 2005：210-224.

[6] AN OX COMPANY. PowerDNS[EB/OL].[2015]. http：//www.powerdns.com.

[7] HAY R， KALECHSTEIN J， NAKIBLY G. Subverting BIND's SRTT algorithm derandomizing NS selection[C]// WOOT'13 Proceedings of the 7th USENIX conference on Offensive Technologies. Washigton， D.C. ：USENIX Association， 2013：3.

[8] 李秉睿. 開放DNS递归服务器的主动测量与分析[D]. 哈尔滨：哈尔滨工业大学， 2016.endprint