王圣元+張宇+李東

摘要： 關(guān)鍵詞： 中圖分類號： 文獻標志碼： 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引言

伴隨著因特網(wǎng)的快速發(fā)展，人們的生活早已與網(wǎng)絡(luò)息息相關(guān)。各種各樣的網(wǎng)絡(luò)服務(wù)給人們帶來無窮的便利。域名系統(tǒng)作為因特網(wǎng)最重要的基礎(chǔ)設(shè)施之一，提供域名到IP地址的轉(zhuǎn)換服務(wù)，是一切網(wǎng)絡(luò)服務(wù)正常運行的基石，其穩(wěn)定性及其它性能對因特網(wǎng)有重要的影響[1]。

當DNS遞歸服務(wù)器對一個擁有多個DNS權(quán)威服務(wù)器的域進行查詢時，DNS遞歸服務(wù)器需要選擇其中一個開展進一步的查詢。其選擇的結(jié)果對查詢的響應(yīng)時間有很大的影響[2]，各個版本的DNS服務(wù)器對權(quán)威服務(wù)器的選擇算法會直接影響其性能。

本文分析了常見的服務(wù)器選擇算法，并對各個版本DNS服務(wù)器采用的算法進行了研究。發(fā)現(xiàn)了對算法選擇結(jié)果產(chǎn)生影響的多個因素，并對全國范圍內(nèi)開放DNS遞歸服務(wù)器對權(quán)威服務(wù)器的選擇方式進行測量和分析。

1DNS權(quán)威服務(wù)器選擇算法

1.1權(quán)威服務(wù)器選擇算法分類

在有多個備選的DNS服務(wù)器可供選擇的情況下，相關(guān)的RFC文檔[3]沒有對選擇的方法做出明確規(guī)定，各個版本DNS服務(wù)器選擇方式不同，主要有平均選擇算法和RTT（Round trip time）相關(guān)的選擇算法兩個類別。平均選擇算法不考慮遞歸服務(wù)器到各個權(quán)威服務(wù)器的延遲或跳數(shù)，無差別地選擇DNS權(quán)威服務(wù)器進行查詢。這種方法的優(yōu)點在于實現(xiàn)簡單，且由于查詢的DNS權(quán)威服務(wù)器為隨機選擇，可以使得一些DNS攻擊方式更加難以實施，例如Kaminsky緩存攻擊[4]。其缺點在于遞歸服務(wù)器不能選擇延遲較小的權(quán)威服務(wù)器進行查詢，整體性能較差[5]。RTT相關(guān)的算法以往返時間RTT為度量方式來對同一個域的多個DNS權(quán)威服務(wù)器進行選擇，可以直接選擇RTT值最小的DNS權(quán)威服務(wù)器進行查詢，也可以按照RTT值的大小給出概率，并按照概率的大小選擇，通常RTT值越小的DNS權(quán)威服務(wù)器被選擇的概率越大，以此來達到更好的性能，即更快地獲得查詢結(jié)果。

1.2SRTT算法

在與RTT相關(guān)的服務(wù)器選擇算法中，最常見的是SRTT（Smoothed Round Trip Time）算法。BIND（Berkeley Internet Name Domain）服務(wù)器采用SRTT選擇算法。SRTT算法動態(tài)地維護一個備選的DNS權(quán)威服務(wù)器的IP列表，并通過這些DNS權(quán)威服務(wù)器的SRTT時間來選擇其中一個進行查詢，其中SRTT為平滑的RTT時延，而具體的計算規(guī)則可表述如下：

1）初始化。 當某個備選的DNS權(quán)威服務(wù)器不存在于遞歸服務(wù)器的緩存中時，需要對其賦一個初始值SRTTinit。數(shù)學計算公式如下：SRTTinit=31^R μsec（1）其中，R為一個32比特的隨機數(shù)。公式所計算出的SRTT初始值遠小于實際網(wǎng)絡(luò)中的往返時間，這使得每個備選的DNS權(quán)威服務(wù)器都能被選擇至少一次，以獲得其實際的往返延遲。

2）SRTT的計算。當DNS遞歸服務(wù)器發(fā)出的某個查詢收到應(yīng)答時，給出應(yīng)答的DNS權(quán)威服務(wù)器的SRTT會依據(jù)本次查詢所獲得的新的RTT和之前已有的SRTT加權(quán)求和計算得出。研究得到公式如下：SRTTnew=αSRTTold+1-αRTTnew（2）在BIND服務(wù)器（版本9.8.0）中，α取值為0.7[6]。

3）SRTT衰減。為了防止在查詢時只選擇某個SRTT最小的DNS權(quán)威服務(wù)器，在收到某次查詢的應(yīng)答時，該次查詢未被選擇的權(quán)威服務(wù)器的SRTT需要按照一定的規(guī)則衰減。推導(dǎo)可得公式如下：SRTTnew=βSRTTold（3）在BIND服務(wù)器（版本9.8.0）中，β取值為0.98。而在PowerDNS[7]中，β的計算公式如下：β=etn-tn+1c（4）其中， c為常數(shù)，tn-tn+1為兩次查詢的時間間隔。endprint

由于網(wǎng)絡(luò)處在不斷變化中，原本RTT較大的DNS權(quán)威服務(wù)器可能會變?yōu)镽TT較小的。為了探測到這一變化，DNS遞歸服務(wù)器需要先對其進行選擇，但如果沒有探測到該變化，則不會對其設(shè)定選擇。這就造成了死鎖的狀態(tài)，為了解決這一問題，大多數(shù)RTT相關(guān)的選擇算法都會采取RTT衰減的策略，即對于沒有被選擇的DNS權(quán)威服務(wù)器，其記錄的RTT值會按照一定的方式逐漸變小，使得每個DNS權(quán)威服務(wù)器都有被選擇的機會。

2可控環(huán)境下權(quán)威服務(wù)器選擇算法的測量和分析

2.1測量環(huán)境

為了研究DNS遞歸服務(wù)器對DNS權(quán)威服務(wù)器選擇的算法及效果，在獨立的網(wǎng)絡(luò)環(huán)境下進行實驗。實驗環(huán)境如圖1所示。其中，a.xxx.cn為xxx.cn的子域，a.xxx.cn有五個DNS權(quán)威服務(wù)器負責解析該子域下的域名，這五臺DNS權(quán)威服務(wù)器向外發(fā)送的報文分別設(shè)置有不同的延遲時間。由于實驗在同一網(wǎng)段下進行，原本服務(wù)器間的往返時間可以忽略不計，遞歸服務(wù)器到權(quán)威服務(wù)器的實際RTT只取決于各個權(quán)威服務(wù)器的延遲時間的設(shè)定。

客戶端向DNS遞歸服務(wù)器發(fā)送子域a.xxx.cn下的域名的查詢，觸發(fā)DNS遞歸服務(wù)器訪問備選的五臺DNS權(quán)威服務(wù)器之一。統(tǒng)計各個版本的DNS遞歸服務(wù)器對數(shù)個DNS權(quán)威服務(wù)器選擇的分布情況。所測量的DNS遞歸服務(wù)器版本如表1所示。

2.2不同版本DNS服務(wù)器的權(quán)威服務(wù)器選擇結(jié)果

將DNS遞歸服務(wù)器到各個權(quán)威服務(wù)器的RTT大小設(shè)置為60 ms、80 ms、100 ms、120 ms、140 ms，查詢速率為40次/s，測量表1中的各版本DNS服務(wù)器對權(quán)威服務(wù)器的選擇分布情況，實驗結(jié)果如圖2所示。

其中，圖2（a）為BIND 9.8實驗結(jié)果，圖2（b）為BIND 9.7實驗結(jié)果。此二者在選擇DNS權(quán)威服務(wù)器時，都更多地選擇RTT較小的權(quán)威服務(wù)器。BIND服務(wù)器采用SRTT算法對權(quán)威服務(wù)器進行選擇， BIND 9.8直接選擇SRTT值最小的權(quán)威服務(wù)器進行查詢，BIND 9.7則按照SRTT的大小設(shè)置概率，并依據(jù)概率選擇權(quán)威服務(wù)器進行查詢。兩者選擇的結(jié)果相差不大，各個權(quán)威服務(wù)器被選擇的比例都與RTT成反比。Windows DNS Server采用平均選擇的方式選擇權(quán)威服務(wù)器進行查詢，各個權(quán)威服務(wù)器基本被均勻選擇，結(jié)果如圖2（c）所示。PowerDNS和BIND 9.1服務(wù)器的實驗結(jié)果如圖2（d）和圖2（e）所示。BIND 9.1雖然也采用SRTT算法，但并沒進行SRTT衰減，因此其結(jié)果與其他版本BIND服務(wù)器不同。PowerDNS采用了SRTT衰減的策略，但其衰減的速度過慢，大量的查詢?nèi)员话l(fā)往RTT最小的權(quán)威服務(wù)器。雖然具體原因不同，但這2種服務(wù)器的表現(xiàn)形式都為選擇最優(yōu)（RTT最小）的權(quán)威服務(wù)器。

如果用實驗中每次查詢所用的平均時間（平均往返時延）代表DNS遞歸服務(wù)器的查詢效率，利用DNS遞歸服務(wù)器發(fā)往各個權(quán)威服務(wù)器上的查詢所占比例的標準差代表查詢分布的離散情況。則Windows DNS Server采用隨機選擇的方式，查詢效率最低，查詢分布得最均勻。BIND 9.1和PowerDNS在選擇DNS權(quán)威服務(wù)器進行查詢時，表現(xiàn)出的形式為選擇最優(yōu)服務(wù)器，這種方式查詢的效率最高，其查詢分布得最不均勻，標準差最大。

2.3查詢速率和查詢時延對算法效果的影響

2.3.1查詢速率對算法選擇結(jié)果的影響

在保持DNS遞歸服務(wù)器到各個DNS權(quán)威服務(wù)器往返時延不變的情況下，改變客戶端的查詢速率，分別設(shè)置為40次/s、80次/s、160次/s、240次/s、300次/s查詢。在這些不同的客戶端查詢速率下，統(tǒng)計BIND 9.8和BIND 9.7服務(wù)器的平均查詢時間，結(jié)果如圖3所示。

可以看出，隨著客戶端查詢速率的加快，BIND 9.8服務(wù)器和BIND 9.7服務(wù)器的平均查詢時間都逐漸增大，而BIND 9.8服務(wù)器增加的幅度更大。兩者在查詢速率變高時，選擇較小往返延遲的DNS權(quán)威服務(wù)器進行查詢的比例逐漸減少，而選擇較大往返延遲的比例逐漸增加。由于BIND 9.7服務(wù)器采用的是根據(jù)與RTT相關(guān)的概率隨機選擇，因此變化的幅度沒有BIND 9.8大。

BIND 9.8服務(wù)器在高查詢速率下，出現(xiàn)了更多地選擇高RTT的DNS權(quán)威服務(wù)器進行查詢的現(xiàn)象，在查詢速率為300次/s的情況下，BIND 9.7和BIND 9.8實驗結(jié)果如圖4所示。這是由于SRTT算法本身導(dǎo)致的。具體原因在2.3.3小節(jié)中進行分析。

2.3.2往返時延大小對算法選擇結(jié)果的影響

除了客戶端的查詢速率可能會對實驗結(jié)果產(chǎn)生影響之外，往返時延的大小本身也會對DNS權(quán)威服務(wù)器的選擇結(jié)果產(chǎn)生影響。將客戶端的查詢速率設(shè)置為80次/s，并改變DNS遞歸服務(wù)器到DNS權(quán)威服務(wù)器的往返延遲。觀察BIND 9.8服務(wù)器對DNS權(quán)威服務(wù)器的選擇結(jié)果。

首先，將DNS遞歸服務(wù)器到各個DNS權(quán)威服務(wù)器的往返延遲的比例固定，改變其大小，分別設(shè)置為20 ms、40 ms、60 ms、80 ms、100 ms和100 ms、200 ms、300 ms、400 ms、500 ms，實驗結(jié)果如圖5（a）所示。再將DNS遞歸服務(wù)器到各個DNS權(quán)威服務(wù)器的往返延遲的差值固定，改變其大小，分別設(shè)置為 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三組，實驗結(jié)果如圖5（b）所示。

從圖5的實驗結(jié)果中可以看出，在DNS遞歸服務(wù)器與備選的DNS權(quán)威服務(wù)器之間的往返時延等比例地擴大時，DNS遞歸服務(wù)器趨向于平均選擇DNS權(quán)威服務(wù)器進行查詢。當各個備選DNS權(quán)威服務(wù)器往返時延的差值不變，而絕對值增加時，DNS遞歸服務(wù)器發(fā)往各個DNS權(quán)威服務(wù)器的查詢比例趨向于相等。具體的原因在2.3.3小節(jié)中進行分析。endprint

2.3.3SRTT算法的分析

在BIND 9.8采用的SRTT算法當中，當一個DNS權(quán)威服務(wù)器被緩存后，如果對應(yīng)的SRTT值不是最小的，則進行SRTT值衰減至最小，再選擇其進行查詢；如果對應(yīng)的SRTT值是最小的，則選擇該服務(wù)器進行查詢，并根據(jù)實際查詢的往返時延來更新SRTT值。因此，可以將一個DNS權(quán)威服務(wù)器的SRTT值的變化分為SRTT衰減、被選擇、SRTT更新三個階段。

假設(shè)某個域有n臺DNS權(quán)威服務(wù)器負責解析，分別為NS1， NS2， …， NSn，對應(yīng)的往返時延分別為RTT1， RTT2， …， RTTn，其中某個權(quán)威服務(wù)器NSi的SRTT值為SRTTi，其SRTT變化曲線如圖6所示。在SRTT衰減階段，DNS權(quán)威服務(wù)器NSi的SRTT值不是最小的，當DNS遞歸服務(wù)器收到一個該域的查詢請求時，會選擇該域的其他DNS權(quán)威服務(wù)器進行查詢，此時，每當收到一個該域權(quán)威服務(wù)器的應(yīng)答，權(quán)威服務(wù)器NSi的SRTT按照一定的方式進行衰減，通常為乘以一個小于1的衰減系數(shù)。SRTT衰減階段對應(yīng)圖6中的t1～t2階段。DNS遞歸服務(wù)器在t′2時發(fā)出一次查詢，在t3時刻收到查詢的應(yīng)答并對NSi的SRTT進行衰減，此次衰減使SRTTi比該域其他DNS權(quán)威服務(wù)器的SRTT值都小，進入到被選擇階段。

在被選擇階段，每當DNS遞歸服務(wù)器收到一個該域的遞歸查詢時，都會選擇NSi進行進一步查詢。當客戶端的查詢速率較高時，在t′2～t2間仍有許多發(fā)往其他DNS權(quán)威服務(wù)器的請求尚未收到應(yīng)答，當遞歸服務(wù)器收到這些查詢的應(yīng)答時，NSi的SRTT仍然會減小，對應(yīng)圖6中的t2～t3階段。從t3開始，DNS遞歸服務(wù)器收到在t2～t3階段發(fā)送給NSi的查詢的應(yīng)答，并根據(jù)實際的往返時延對NSi的SRTT值進行更新。經(jīng)過數(shù)次更新后，從t4開始，NSi的SRTT不再是最小的，此時進入SRTT更新階段。

在SRTT更新階段中，遞歸服務(wù)器不會再選擇NSi進行查詢。但DNS遞歸服務(wù)器可能會繼續(xù)收到NSi的應(yīng)答報文，并對NSi的SRTT進行更新。到t5時，收到被選擇階段中遞歸服務(wù)器發(fā)往NSi的查詢的所有應(yīng)答后，NSi再次進入SRTT衰減階段。

若有一個備選的DNS權(quán)威服務(wù)器NSi，其SRTT衰減階段所占時間為tdecay=t2-t1，被選擇階段所占時間為tselect=t4-t2，選擇后的SRTT更新階段所占時間為tupdate=t5-t4，則選擇該權(quán)威服務(wù)器進行查詢的占比Pi為：Pi=tselecttdecay+tselect+tupdate（5）DNS遞歸服務(wù)器從t2時刻開始向NSi發(fā)送查詢，到t3時刻收到NSi返回的應(yīng)答，t2與t3間的時間間隔取決于DNS遞歸服務(wù)器與NSi間的往返時延。在BIND 9.8中，進行SRTT衰減時的系數(shù)為0.98，SRTT在增長時采用與實際RTT加權(quán)平均的方式。當實際的RTT與衰減后得到的SRTT相差較大時，只要收到少數(shù)幾個NSi的應(yīng)答并對SRTTi進行更新后，SRTTi就不再是最小的SRTT值。因此，tselect的大小主要取決于DNS遞歸服務(wù)器與NSi間的RTT大小。

參考文獻：

[1]孫瑞. 基于分布式平臺的DNS信息探測系統(tǒng)設(shè)計與實現(xiàn)[D]. 哈爾濱：哈爾濱工業(yè)大學， 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遞歸服務(wù)器的主動測量與分析[D]. 哈爾濱：哈爾濱工業(yè)大學， 2016.endprint