曹紹華,薛華威

(1.中國石油大學計算機與通信工程學院,山東青島　266580; 2.國防科技大學計算機學院,長沙 410073)

?

工程與應用

基于DTTL模型的DNS自適應緩存機制研究

曹紹華1,薛華威2

(1.中國石油大學計算機與通信工程學院,山東青島266580; 2.國防科技大學計算機學院,長沙 410073)

為了減少帶寬使用和提升用戶體驗度，DNS緩存采用TTL機制，緩存資源在有限TTL時間內(nèi)訪問命中，過期刪除。TTL設置很關鍵，設置過小，在訪問量突增時，造成權(quán)威域名服務器過載；TTL設置過大，訪問量減少時候，一致性得不到保證。傳統(tǒng)的DNS通過不斷的修改權(quán)威域名服務器區(qū)域文件來改變TTL數(shù)值，然后緩存不命中時候，將TTL值傳給遞歸域名服務器，這給管理人員帶來不便。本文針對這一問題，首次提出了一種基于DTTL模型的DNS自適應緩存TTL機制，能夠根據(jù)訪問量的實時變化，對TTL動態(tài)調(diào)整，而不改變權(quán)威域名服務器的區(qū)域文件，并且在一致性和命中率取得平衡。

DNS緩存；DTTL；自適應緩存；TTL

TP393

A

1673-5692(2016)02-199-05

0　引　言

域名服務器是目前網(wǎng)絡重要的基礎設施[1]，將用戶使用較為方便的域名映射為具體的IP地址，從而為用戶提供服務。為了減少DNS解析占用的網(wǎng)絡帶寬及DNS解析時間，DNS緩存作為一種有效的機制被廣泛應用到域名服務器的設計中[2]。DNS緩存能夠緩解權(quán)威域名服務器特別是根域名服務器的帶寬壓力，并且縮短從域名到IP的解析時間，DNS緩存采用TTL策略對緩存進行控制，過期刪除響應的緩存，RFC1033建議最小的TTL的設置為1天-1周[3]，RFC1912則認為除非區(qū)域文件經(jīng)常更新，否則至少將最小的TTL設置為3天以上，對哪些不經(jīng)常變化或很少變化的服務器，如郵件服務器，甚至可以將TTL設置為2周[4]。

LotterM認為DNS的TTL合適數(shù)值設置很重要，設置過小，會造成服務器過載，設置過低，存在一致性問題。因此如何在命中率和一致性取得平衡是本文研究問題[5]。

本文根據(jù)以上的問題，提出基于DTTL模型的DNS自適應策略，能有效的解決以上的問題，主要的貢獻是：(1)提出DTTL模型的DNS應用，并給出相應算法。(2)能夠應對易變的訪問量并動態(tài)調(diào)整TTL。(3)在命中率和一致性取得平衡。(4)向后兼容，并支持漸進部署。

本文首先介紹了相關的研究工作，然后分析當前DNS緩存機制面臨問題并提出自適應緩存模型。隨后從miss率和TTL數(shù)值方面分析傳統(tǒng)DNS和自適應DNS模型,進而評估實現(xiàn)。最后對該模型進行總結(jié)。

1　相關研究

在DNS中，為了減輕根服務器的負擔，遞歸服務器會緩存一部分資源記錄(RR)。如果由于網(wǎng)絡擁塞或者其他因素．遞歸服務器與權(quán)威服務器之間的通信中斷，那么遞歸服務器中的RR緩存將開始起作用，并最終決定其解析服務的質(zhì)量(QoRS)。通過對RR緩存失效過程進行理論分析和數(shù)學建模，TTL起關鍵的作用，設置越大，QoRS越好[6]。ZhengWang基于查詢分布模型對DNS緩存進行分析，當請求一個滿足Zipf模型的域名時候，該域名TTL的大小和該域名的排名也滿足Zipf模型[7]。JaeyeonJung假設請求服從獨立同分布，并解釋了：命中率隨TTL快速增加，15min時候就達到了80%[8]。DanielS.Berger對目前三種TTL的模型進行了理論分析，討論緩存中的命中率，內(nèi)存占有[9]。EdithCohen提出通過增加一個信譽值，當訪存命中時候，信譽數(shù)字增加，TTL到期時候先看信譽數(shù)字是否為0，如果不為0，延長一個TTL，并將信譽數(shù)字減少，如果為0，刪除緩存記錄[10]。但是該方法不能對訪問量實時做出調(diào)整，并且在訪問量很大情況下，一致性很難得到保證。

2　問題分析

2.1DNS緩存

DNS請求有兩種方式：遞歸和迭代，下面我們以遞歸請求進行分析傳統(tǒng)DNS緩存。

以客戶端請求www.example.com為例，如圖1，客戶通過瀏覽器給本地域名服務器發(fā)送請求，如果本地域名服務器的緩存中沒有該域名資源的記錄，則本地域名服務器就去請求根域名服務器root，根域名服務器返回頂級域名服務器.com的IP，本地域名服務器根據(jù)返回結(jié)果，去請求頂級域名服務器.com，頂級域名服務器返回.example.com的IP，然后本地域名服務器去訪問.example.com服務器獲得www.example.com的域名解析結(jié)果，本地域名服務器將解析結(jié)果存入緩存，失效期限是一個TTL。在有效期內(nèi)，再次請求該域名www.example.com，本地域名服務器會直接返回結(jié)果，不需要請求根域名。但是失效時，繼續(xù)按照上面流程進行請求，最后將請求結(jié)果存入緩存。

圖1　客戶端遞歸請求DNS

根據(jù)DanielS.Berger的緩存分析模型，我們設Xi為對同一域名的(i-1)th和ith的訪問時間間隔，{Xi}獨立同分布。N(t)表示在一個[0,t]時間內(nèi)的請求數(shù)，為了簡化，我們認為N(t)是一個計數(shù)過程，M(t)是[0,t]時間內(nèi)不命中請求數(shù)。則命中率為：

(1)

在泊松分布情況下為:

(2)

由式(2)可知道，在訪問量很高的情況下，我們可以通過增加TTL數(shù)值來提高命中，在訪問量低的時候，因為服務器負載低，我們可以減少TTL來增加一致性。如何動態(tài)的根據(jù)訪問量動態(tài)調(diào)整TTL是我們研究問題。

2.2DTTL 模型

在提出DNS自適應DTTL模型之前，先分析兩個常見的TTL更新策略，分別為α和β：

α：只要有該域名的請求到達，就重新計時，到期刪除緩存。

β：只有當請求的域名不命中時候，才重新計時，到期刪除緩存。

Min(α,β)：采用α和β策略，但是只要有一個TTL到期就刪除緩存記錄。

α策略對于經(jīng)常被訪問的域名，命中率明顯提高，但是由于長時間的滯留緩存中，所以一致性得不到很好的保證。β策略雖然能保證一致性，域名的命中率低。Min(α,β)在一致性和命中率取得平衡。

Min(α,β)在兩個方面取得應用。在SDN的流表中通過設計idel_timeout(模型α)和hard_timeout(模型β)來實現(xiàn)對流表的定時清除控制操作[11]；在AmazonElastiCache機制中，在網(wǎng)頁緩存中采用LRU(模型α)，而Tβ是由用戶進行設置。

DNS自適應DTTL模型就是建立在第三種TTL更新策略基礎上。

2.3DNS自適應TTL算法

設在[0,t1]時間區(qū)間內(nèi)(0是某一次訪問不命中的時刻)，Sn=X1+X2+…+Xn。

(1)在該區(qū)間內(nèi)?Xi=1)，?Sn>Tβ∧Sn-1<=Tβ,則DTTL=Tβ；

(2)在該區(qū)間內(nèi)?Xi>Tα(i>=1)，則DTTL=Τα；

(3)在該區(qū)間?Xi>Tα∧Xj<(i,j)=1)，則DTTL∈(Tα,Tβ)。

詳細的算法描述如下：

Timer:

1.if(aflag==1&&bflag==0){

2.if(Tβ==0)removefromthecache;

3.if(Tβ==0)removefromthecache;

4.}

5.if(aflag==0&&bflag==1){

6. Tα--;

7.if(Tα==0)removefromthecache;

8. }

9.if(aflag==0&&bflag==0){

10. Tα--; Tβ--;

11.if(Tα==0||Tβ==0)removefromthecache;

12. }

13. //endoftimer

14.GetrequestwithdomainnameitemAfromclient,recordcurrenttimeti;

15.flag=select_from_cache(itemA);

16.if(flag==0){//notinthecache

17.Getresponsecache_itemAfromNS;

18.insert_cache(cache_itemA);

19.if(Tβ==0)bflag=1;

20.if(Tα==0)aflag=1;

21.tempttl=Tα;

22. }//endofif

23.else{//inthecache

24.if(ti-ti-1

25. }//endelse

3　實驗分析

為了評估DTTL模型的有效性和性能，我們將該機制加入到Bind[12]。

3.1實驗設計

構(gòu)建100個客戶端，如圖2,所示，請求的域名是www.example.com。將該機制加入到DNSserver中，并設置兩個TTL，分別是10sec，360sec。作為對比，在傳統(tǒng)的TTL設置為10sec。在實驗中測試DTTL是否隨請求間隔動態(tài)改變，以及比較DTTL模式和傳統(tǒng)DNSMiss率。

圖2　客戶端請求DNS

3.2評價指標

從下面兩個方面進行評估：DTTL數(shù)值和Miss率N(t)是一個更新過程，滿足N(t)服從參數(shù)為λt的泊松分布。

3.2.1DTTL

由前面分析得知：

(3)

K正比于單位時間訪問量

3.2.2Miss率

命中率由公式(1)得出：

對于策略α命中率：

(4)

策略β命中率：

(5)

策略Min(α,β)命中率：

(6)

γ正比與單位時間內(nèi)訪問量。

不命中率可以作為權(quán)威域名服務器的負載情況的衡量：

3.3實驗分析

分別對14個不同請求樣本，每組樣本有100個請求，且按照某一間隔時間進行請求。圖3，顯示了DNS傳統(tǒng)模式與DTTL模式下不同請求速率下的miss率。

圖3　DNS傳統(tǒng)模式和DTTL模式對比

圖4　DDL數(shù)值隨時間間隔的動態(tài)調(diào)整

我們另外構(gòu)建一組請求樣本是，100個請求，且每次的請求間隔隨機不再是以固定速率。圖4，顯示DTTL模式下的DTTL數(shù)值是如何隨時間間隔而發(fā)生動態(tài)調(diào)整的。

從圖3中，我們看出當請求速率比較大(即間隔時間<10sec)時候，傳統(tǒng)的和DTLL模式下的Miss率都會降低，與公式(5)和(6)吻合。但DTTL模式比傳統(tǒng)模式Miss率降低了10%～50%左右。即應對高速率請求的情況，DTTL表現(xiàn)的更出色，可以有效降低Miss率。

當請求速率降低時候，也就是10sec以后(因為TTL設置為10sec)，可以看出DTTL和傳統(tǒng)的DNS和Miss率幾乎100%，即在請求速率較低情況下，DTTL的一致性得到保證。

從3.3中，我們可以看到TTL數(shù)值隨請求速率動態(tài)變化，當兩次請求間隔小于10sec時候，TTL重置，緩存時間得到了延長，從而提高命中率；當請求間隔大于10sec時候，TTL為0，刪除緩存，提高一致性。即TTL數(shù)值隨請求速率實時進行調(diào)整。

4　機制實現(xiàn)

DTTL機制實現(xiàn)起來并不困難，只需要在域名服務器中設置兩個TTL，并將更新算法加入到DNS實現(xiàn)軟件。

我們可以使用AdditionalRR字段，將另外一個TTL加入到該字段的最后面，如圖5所示。

圖5 增加字段

當傳統(tǒng)的服務器接受到一個在AdditionalRRs最后一個記錄是數(shù)字的響應報文，認為該記錄有問題，默認不處理。如果是實現(xiàn)DTTL的服務器接受到該報文，會根據(jù)請求進行動態(tài)調(diào)整TTL。若DTTL服務器接受到一個傳統(tǒng)的DNS的響應報文，則會解析報文，分析AdditionalRR最后一個記錄不是數(shù)字，則按照傳統(tǒng)的處理方式進行緩存。

因此，DTTL模型支持向后兼容和漸進部署。

5　結(jié)　語

通過實驗得出DTTL在一致性和命中率取得平衡，并實時的根據(jù)請求速率，對TTL進行動態(tài)調(diào)整，而且是向后兼容和支持漸進部署。

未來將把該機制部署到真實的環(huán)境中，測試命中率，一致性以及對請求速率的反應情況。

[1]MockapetrisP.RFC1034:Domainnames:conceptsandfacilities(November1987)[J].Status:Standard, 2003.

[2]MockapetrisP.RFC1035—Domainnames—implementationandspecification,November1987[J].http://www.

ietf.org/rfc/rfc1035.txt, 2004.

[3]LotterM.RFC1033domainadministratorsoperationsguide[J].InternationalEngineeringTaskForce, 1987.

[4]BarrD.CommonDNSoperationalandconfigurationerrors[J]. 1996.

[5]劉柯.多核處理器Cache一致性的改進[J]。西安郵電大學學報, 2015, 20(2):98-104.

[6]危婷, 冷峰, 張躍冬, 等.DNS服務器緩存失效過程的研究[J]. 電信科學, 2013, 29(9): 94-97.

[7]WangZ.Analysisofdnscacheeffectsonquerydistribution[J].TheScientificWorldJournal, 2013, 2013.

[8]JungJ,BergerAW,BalakrishnanH.ModelingTTL-basedInternetcaches[C]//INFOCOM2003.Twenty-SecondAnnualJointConferenceoftheIEEEComputerandCommunications.IEEESocieties.IEEE, 2013, 1: 417-426.

[9]BergerDS,GlandP,SinglaS,etal.ExactanalysisofTTLcachenetworks[J].PerformanceEvaluation, 2014, 79: 2-23.

[10]CohenE,KaplanH.ProactivecachingofDNSrecords:Addressingaperformancebottleneck[J].ComputerNetworks, 2003, 41(6): 707-726.

[11]Specification-VersionOFS. 1.4. 0[J]. 2013.

[12]P.AlbitzandC.Liu,DNSandBIND,O’ReillyandAssociates,Cambridge,Mass,USA, 1998.

曹紹華(1978-),男，山東省聊城人，碩士，主要研究方向為網(wǎng)絡性能優(yōu)化、下一代網(wǎng)絡；

E-mail:caoshaohua2009@163.com

薛華威(1991—)，男，河南省駐馬店人，碩士，主要研究方向為虛擬化、云計算網(wǎng)絡。

Research on DNS Adaptive Caching Mechanism Based on DTTL Model

CAOShao-hua1,XUEHua-wei2

(1.CollegeofComputerandCommunicationEngineering,ChinaUniversityofPetroleum,Qingdao,Shandong266580,China;2.CollegeofComputer,NationalUniversityofDefenseTechnology,Changsha,Hunan410073,China)

Inordertoreducethebandwidthusageandenhancetheuserexperience,theDNScacheusestheTTLmechanism,andthecacheresourcesareaccessedbythelimitedTTLtime.TTLsettingsareverycritical,settoosmall,thesuddenincreaseintheamountofaccess,resultinginanauthoritativedomainnameserveroverload;TTLsettingsaretoolarge,whentheamountofaccessreduce,consistencyisnotguaranteed.TraditionalDNSchangestothedomainnameserverdomainfileconstantlytochangetheTTLvalue,ifthecacheisnotaccessed,theTTLvalueispassedtotherecursivedomainnameserver,whichbringsinconveniencetothemanagementstaff.Inthispaper,wefocusontheproblems.Forthefirsttime,aDNSadaptivecacheTTLmechanismbasedonDTTLmodelisproposed,itcanbechangedbythereal-timetraffic,dynamicadjustmentforTTLwithoutchangingtheauthoritativenameserverareaofthefile,andachieveabalancewiththeconsistencyandthehitrate.

DNScache;DTTL;Adaptivecache;TTL

10.3969/j.issn.1673-5692.2016.02.015

2016-01-05

2016-03-16

山東省優(yōu)秀中青年科學家科研獎勵基金計劃項目(BS2014DX021)