基于DTTL模型的DNS自适应缓存机制研究

曹绍华,薛华威

(1.中国石油大学计算机与通信工程学院,山东青岛　266580; 2.国防科技大学计算机学院,长沙 410073)



工程与应用

基于DTTL模型的DNS自适应缓存机制研究

曹绍华1,薛华威2

(1.中国石油大学计算机与通信工程学院,山东青岛266580; 2.国防科技大学计算机学院,长沙 410073)

为了减少带宽使用和提升用户体验度，DNS缓存采用TTL机制，缓存资源在有限TTL时间内访问命中，过期删除。TTL设置很关键，设置过小，在访问量突增时，造成权威域名服务器过载；TTL设置过大，访问量减少时候，一致性得不到保证。传统的DNS通过不断的修改权威域名服务器区域文件来改变TTL数值，然后缓存不命中时候，将TTL值传给递归域名服务器，这给管理人员带来不便。本文针对这一问题，首次提出了一种基于DTTL模型的DNS自适应缓存TTL机制，能够根据访问量的实时变化，对TTL动态调整，而不改变权威域名服务器的区域文件，并且在一致性和命中率取得平衡。

DNS缓存；DTTL；自适应缓存；TTL

TP393

A

1673-5692(2016)02-199-05

0　引　言

域名服务器是目前网络重要的基础设施[1]，将用户使用较为方便的域名映射为具体的IP地址，从而为用户提供服务。为了减少DNS解析占用的网络带宽及DNS解析时间，DNS缓存作为一种有效的机制被广泛应用到域名服务器的设计中[2]。DNS缓存能够缓解权威域名服务器特别是根域名服务器的带宽压力，并且缩短从域名到IP的解析时间，DNS缓存采用TTL策略对缓存进行控制，过期删除响应的缓存，RFC1033建议最小的TTL的设置为1天-1周[3]，RFC1912则认为除非区域文件经常更新，否则至少将最小的TTL设置为3天以上，对哪些不经常变化或很少变化的服务器，如邮件服务器，甚至可以将TTL设置为2周[4]。

LotterM认为DNS的TTL合适数值设置很重要，设置过小，会造成服务器过载，设置过低，存在一致性问题。因此如何在命中率和一致性取得平衡是本文研究问题[5]。

本文根据以上的问题，提出基于DTTL模型的DNS自适应策略，能有效的解决以上的问题，主要的贡献是：(1)提出DTTL模型的DNS应用，并给出相应算法。(2)能够应对易变的访问量并动态调整TTL。(3)在命中率和一致性取得平衡。(4)向后兼容，并支持渐进部署。

本文首先介绍了相关的研究工作，然后分析当前DNS缓存机制面临问题并提出自适应缓存模型。随后从miss率和TTL数值方面分析传统DNS和自适应DNS模型,进而评估实现。最后对该模型进行总结。

1　相关研究

在DNS中，为了减轻根服务器的负担，递归服务器会缓存一部分资源记录(RR)。如果由于网络拥塞或者其他因素．递归服务器与权威服务器之间的通信中断，那么递归服务器中的RR缓存将开始起作用，并最终决定其解析服务的质量(QoRS)。通过对RR缓存失效过程进行理论分析和数学建模，TTL起关键的作用，设置越大，QoRS越好[6]。ZhengWang基于查询分布模型对DNS缓存进行分析，当请求一个满足Zipf模型的域名时候，该域名TTL的大小和该域名的排名也满足Zipf模型[7]。JaeyeonJung假设请求服从独立同分布，并解释了：命中率随TTL快速增加，15min时候就达到了80%[8]。DanielS.Berger对目前三种TTL的模型进行了理论分析，讨论缓存中的命中率，内存占有[9]。EdithCohen提出通过增加一个信誉值，当访存命中时候，信誉数字增加，TTL到期时候先看信誉数字是否为0，如果不为0，延长一个TTL，并将信誉数字减少，如果为0，删除缓存记录[10]。但是该方法不能对访问量实时做出调整，并且在访问量很大情况下，一致性很难得到保证。

2　问题分析

2.1DNS缓存

DNS请求有两种方式：递归和迭代，下面我们以递归请求进行分析传统DNS缓存。

以客户端请求www.example.com为例，如图1，客户通过浏览器给本地域名服务器发送请求，如果本地域名服务器的缓存中没有该域名资源的记录，则本地域名服务器就去请求根域名服务器root，根域名服务器返回顶级域名服务器.com的IP，本地域名服务器根据返回结果，去请求顶级域名服务器.com，顶级域名服务器返回.example.com的IP，然后本地域名服务器去访问.example.com服务器获得www.example.com的域名解析结果，本地域名服务器将解析结果存入缓存，失效期限是一个TTL。在有效期内，再次请求该域名www.example.com，本地域名服务器会直接返回结果，不需要请求根域名。但是失效时，继续按照上面流程进行请求，最后将请求结果存入缓存。

图1　客户端递归请求DNS

根据DanielS.Berger的缓存分析模型，我们设Xi为对同一域名的(i-1)th和ith的访问时间间隔，{Xi}独立同分布。N(t)表示在一个[0,t]时间内的请求数，为了简化，我们认为N(t)是一个计数过程，M(t)是[0,t]时间内不命中请求数。则命中率为：

(1)

在泊松分布情况下为:

(2)

由式(2)可知道，在访问量很高的情况下，我们可以通过增加TTL数值来提高命中，在访问量低的时候，因为服务器负载低，我们可以减少TTL来增加一致性。如何动态的根据访问量动态调整TTL是我们研究问题。

2.2DTTL 模型

在提出DNS自适应DTTL模型之前，先分析两个常见的TTL更新策略，分别为α和β：

α：只要有该域名的请求到达，就重新计时，到期删除缓存。

β：只有当请求的域名不命中时候，才重新计时，到期删除缓存。

Min(α,β)：采用α和β策略，但是只要有一个TTL到期就删除缓存记录。

α策略对于经常被访问的域名，命中率明显提高，但是由于长时间的滞留缓存中，所以一致性得不到很好的保证。β策略虽然能保证一致性，域名的命中率低。Min(α,β)在一致性和命中率取得平衡。

Min(α,β)在两个方面取得应用。在SDN的流表中通过设计idel_timeout(模型α)和hard_timeout(模型β)来实现对流表的定时清除控制操作[11]；在AmazonElastiCache机制中，在网页缓存中采用LRU(模型α)，而Tβ是由用户进行设置。

DNS自适应DTTL模型就是建立在第三种TTL更新策略基础上。

2.3DNS自适应TTL算法

设在[0,t1]时间区间内(0是某一次访问不命中的时刻)，Sn=X1+X2+…+Xn。

(1)在该区间内∀Xi=1)，∃Sn>Tβ∧Sn-1<=Tβ,则DTTL=Tβ；

(2)在该区间内∀Xi>Tα(i>=1)，则DTTL=Τα；

(3)在该区间∃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实验设计

构建100个客户端，如图2,所示，请求的域名是www.example.com。将该机制加入到DNSserver中，并设置两个TTL，分别是10sec，360sec。作为对比，在传统的TTL设置为10sec。在实验中测试DTTL是否随请求间隔动态改变，以及比较DTTL模式和传统DNSMiss率。

图2　客户端请求DNS

3.2评价指标

从下面两个方面进行评估：DTTL数值和Miss率N(t)是一个更新过程，满足N(t)服从参数为λt的泊松分布。

3.2.1DTTL

由前面分析得知：

(3)

K正比于单位时间访问量

3.2.2Miss率

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

对于策略α命中率：

(4)

策略β命中率：

(5)

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

(6)

γ正比与单位时间内访问量。

不命中率可以作为权威域名服务器的负载情况的衡量：

3.3实验分析

分别对14个不同请求样本，每组样本有100个请求，且按照某一间隔时间进行请求。图3，显示了DNS传统模式与DTTL模式下不同请求速率下的miss率。

图3　DNS传统模式和DTTL模式对比

图4　DDL数值随时间间隔的动态调整

我们另外构建一组请求样本是，100个请求，且每次的请求间隔随机不再是以固定速率。图4，显示DTTL模式下的DTTL数值是如何随时间间隔而发生动态调整的。

从图3中，我们看出当请求速率比较大(即间隔时间<10sec)时候，传统的和DTLL模式下的Miss率都会降低，与公式(5)和(6)吻合。但DTTL模式比传统模式Miss率降低了10%～50%左右。即应对高速率请求的情况，DTTL表现的更出色，可以有效降低Miss率。

当请求速率降低时候，也就是10sec以后(因为TTL设置为10sec)，可以看出DTTL和传统的DNS和Miss率几乎100%，即在请求速率较低情况下，DTTL的一致性得到保证。

从3.3中，我们可以看到TTL数值随请求速率动态变化，当两次请求间隔小于10sec时候，TTL重置，缓存时间得到了延长，从而提高命中率；当请求间隔大于10sec时候，TTL为0，删除缓存，提高一致性。即TTL数值随请求速率实时进行调整。

4　机制实现

DTTL机制实现起来并不困难，只需要在域名服务器中设置两个TTL，并将更新算法加入到DNS实现软件。

我们可以使用AdditionalRR字段，将另外一个TTL加入到该字段的最后面，如图5所示。

图5 增加字段

当传统的服务器接受到一个在AdditionalRRs最后一个记录是数字的响应报文，认为该记录有问题，默认不处理。如果是实现DTTL的服务器接受到该报文，会根据请求进行动态调整TTL。若DTTL服务器接受到一个传统的DNS的响应报文，则会解析报文，分析AdditionalRR最后一个记录不是数字，则按照传统的处理方式进行缓存。

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

5　结　语

通过实验得出DTTL在一致性和命中率取得平衡，并实时的根据请求速率，对TTL进行动态调整，而且是向后兼容和支持渐进部署。

未来将把该机制部署到真实的环境中，测试命中率，一致性以及对请求速率的反应情况。

[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-),男，山东省聊城人，硕士，主要研究方向为网络性能优化、下一代网络；

E-mail:caoshaohua2009@163.com

薛华威(1991—)，男，河南省驻马店人，硕士，主要研究方向为虚拟化、云计算网络。

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

山东省优秀中青年科学家科研奖励基金计划项目(BS2014DX021)