基于DTTL模型的DNS自適應(yīng)緩存機(jī)制研究

曹紹華,薛華威

(1.中國(guó)石油大學(xué)計(jì)算機(jī)與通信工程學(xué)院,山東青島　266580; 2.國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院,長(zhǎng)沙 410073)

?

工程與應(yīng)用

基于DTTL模型的DNS自適應(yīng)緩存機(jī)制研究

曹紹華1,薛華威2

(1.中國(guó)石油大學(xué)計(jì)算機(jī)與通信工程學(xué)院,山東青島266580; 2.國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院,長(zhǎng)沙 410073)

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

DNS緩存；DTTL；自適應(yīng)緩存；TTL

TP393

A

1673-5692(2016)02-199-05

0　引　言

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

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

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

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

1　相關(guān)研究

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

2　問(wèn)題分析

2.1DNS緩存

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

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

圖1　客戶端遞歸請(qǐng)求DNS

根據(jù)DanielS.Berger的緩存分析模型，我們?cè)O(shè)Xi為對(duì)同一域名的(i-1)th和ith的訪問(wèn)時(shí)間間隔，{Xi}獨(dú)立同分布。N(t)表示在一個(gè)[0,t]時(shí)間內(nèi)的請(qǐng)求數(shù)，為了簡(jiǎn)化，我們認(rèn)為N(t)是一個(gè)計(jì)數(shù)過(guò)程，M(t)是[0,t]時(shí)間內(nèi)不命中請(qǐng)求數(shù)。則命中率為：

(1)

在泊松分布情況下為:

(2)

由式(2)可知道，在訪問(wèn)量很高的情況下，我們可以通過(guò)增加TTL數(shù)值來(lái)提高命中，在訪問(wèn)量低的時(shí)候，因?yàn)榉?wù)器負(fù)載低，我們可以減少TTL來(lái)增加一致性。如何動(dòng)態(tài)的根據(jù)訪問(wèn)量動(dòng)態(tài)調(diào)整TTL是我們研究問(wèn)題。

2.2DTTL 模型

在提出DNS自適應(yīng)DTTL模型之前，先分析兩個(gè)常見(jiàn)的TTL更新策略，分別為α和β：

α：只要有該域名的請(qǐng)求到達(dá)，就重新計(jì)時(shí)，到期刪除緩存。

β：只有當(dāng)請(qǐng)求的域名不命中時(shí)候，才重新計(jì)時(shí)，到期刪除緩存。

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

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

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

DNS自適應(yīng)DTTL模型就是建立在第三種TTL更新策略基礎(chǔ)上。

2.3DNS自適應(yīng)TTL算法

設(shè)在[0,t1]時(shí)間區(qū)間內(nèi)(0是某一次訪問(wèn)不命中的時(shí)刻)，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β)。

詳細(xì)的算法描述如下：

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　實(shí)驗(yàn)分析

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

3.1實(shí)驗(yàn)設(shè)計(jì)

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

圖2　客戶端請(qǐng)求DNS

3.2評(píng)價(jià)指標(biāo)

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

3.2.1DTTL

由前面分析得知：

(3)

K正比于單位時(shí)間訪問(wèn)量

3.2.2Miss率

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

對(duì)于策略α命中率：

(4)

策略β命中率：

(5)

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

(6)

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

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

3.3實(shí)驗(yàn)分析

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

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

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

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

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

當(dāng)請(qǐng)求速率降低時(shí)候，也就是10sec以后(因?yàn)門TL設(shè)置為10sec)，可以看出DTTL和傳統(tǒng)的DNS和Miss率幾乎100%，即在請(qǐng)求速率較低情況下，DTTL的一致性得到保證。

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

4　機(jī)制實(shí)現(xiàn)

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

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

圖5 增加字段

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

因此，DTTL模型支持向后兼容和漸進(jìn)部署。

5　結(jié)　語(yǔ)

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

未來(lái)將把該機(jī)制部署到真實(shí)的環(huán)境中，測(cè)試命中率，一致性以及對(duì)請(qǐng)求速率的反應(yīng)情況。

[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ìn)[J]。西安郵電大學(xué)學(xué)報(bào), 2015, 20(2):98-104.

[6]危婷, 冷峰, 張躍冬, 等.DNS服務(wù)器緩存失效過(guò)程的研究[J]. 電信科學(xué), 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-),男，山東省聊城人，碩士，主要研究方向?yàn)榫W(wǎng)絡(luò)性能優(yōu)化、下一代網(wǎng)絡(luò)；

E-mail:caoshaohua2009@163.com

薛華威(1991—)，男，河南省駐馬店人，碩士，主要研究方向?yàn)樘摂M化、云計(jì)算網(wǎng)絡(luò)。

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)秀中青年科學(xué)家科研獎(jiǎng)勵(lì)基金計(jì)劃項(xiàng)目(BS2014DX021)