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