閆夏莉,王 騫,呂萬(wàn)波,張海闊,岳巧麗,曹 爽

1(中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心,北京 100190)

2(國(guó)家稅務(wù)總局 電子政務(wù)管理中心,北京 100053)

DNS (Domain Name System)主要用于承載域名與IP地址之間的轉(zhuǎn)換,是互聯(lián)網(wǎng)的關(guān)鍵基礎(chǔ)設(shè)施之一.權(quán)威域名服務(wù)器的性能一直是DNS的研究重點(diǎn)之一.在面向DNS服務(wù)器性能的參數(shù)中,平均響應(yīng)時(shí)間是重要評(píng)價(jià)指標(biāo),也是用戶感受服務(wù)器性能的主要體現(xiàn).近年來(lái)性能測(cè)試中又引入了響應(yīng)時(shí)間百分比,即響應(yīng)時(shí)間小于期望時(shí)間的概率百分比來(lái)進(jìn)一步度量和表示其性能,以期為用戶帶來(lái)更好的體驗(yàn)[1,2],這也是本文研究的重要性能參數(shù).真實(shí)的響應(yīng)時(shí)間包括網(wǎng)絡(luò)傳輸時(shí)間、服務(wù)器處理時(shí)間等,用戶的網(wǎng)絡(luò)狀況千差萬(wàn)別,因此本文研究的重點(diǎn)是提升服務(wù)器處理時(shí)間的百分比.

本文提到的DNS服務(wù)器特指權(quán)威域名服務(wù)器,其查詢(xún)請(qǐng)求可分為兩類(lèi).一類(lèi)是針對(duì)特定資源記錄RR(Resource Record)的查詢(xún),如A記錄、NS記錄查詢(xún)等,查詢(xún)結(jié)果返回相應(yīng)的資源記錄,在本文中用“常規(guī)查詢(xún)”表示.另一類(lèi)為IXFR[3]/AXFR[4](Incremental Zone Transfer/Authoritative Zone Transfer)查詢(xún),用于主從服務(wù)器間的數(shù)據(jù)同步,查詢(xún)結(jié)果返回區(qū)域數(shù)據(jù)中變化的資源記錄甚至完整的區(qū)域數(shù)據(jù),該過(guò)程稱(chēng)為增量/全量區(qū)域數(shù)據(jù)傳送.以根服務(wù)器為例,全球共13臺(tái)根服務(wù)器及其鏡像服務(wù)器支撐根區(qū)數(shù)據(jù)解析服務(wù)[5].各服務(wù)器及其鏡像通過(guò)全量區(qū)域數(shù)據(jù)傳送來(lái)保障根區(qū)數(shù)據(jù)的一致性[6].

為了提高響應(yīng)時(shí)間百分比,有必要先確定其性能瓶頸,進(jìn)行針對(duì)性的優(yōu)化.在本文中,為了避免盲目的優(yōu)化,首先建立了基于排隊(duì)論[7]的數(shù)據(jù)模型,將DNS服務(wù)器抽象為一個(gè)M/M/c的隨機(jī)服務(wù)系統(tǒng),并依據(jù)此模型對(duì)響應(yīng)時(shí)間百分比進(jìn)行了分析,確定性能瓶頸之后,對(duì)DNS的數(shù)據(jù)特征進(jìn)行了分析,并結(jié)合基址重定位技術(shù)提出改進(jìn)算法.最后對(duì)提出的改進(jìn)算法進(jìn)行實(shí)驗(yàn)和性能評(píng)測(cè).

1 DNS服務(wù)器的數(shù)學(xué)模型

1.1 模型描述

排隊(duì)現(xiàn)象由兩方面構(gòu)成,一方請(qǐng)求服務(wù),另一方提供服務(wù).顧客通過(guò)排隊(duì)服務(wù)系統(tǒng)要依次經(jīng)過(guò)如下過(guò)程:顧客到達(dá)、排隊(duì)等待、接受服務(wù)和離去.DNS服務(wù)器的查詢(xún)應(yīng)答過(guò)程符合排隊(duì)服務(wù)系統(tǒng)的規(guī)律.服務(wù)器收到來(lái)自各客戶端的查詢(xún),請(qǐng)求按一定的速率到達(dá),經(jīng)服務(wù)器解析返回應(yīng)答包.DNS服務(wù)器可以是單個(gè)服務(wù)臺(tái),也可通過(guò)SO_REUSEPORT機(jī)制,將多個(gè)套接字綁定在同一個(gè)端口實(shí)現(xiàn)多個(gè)服務(wù)臺(tái).

假設(shè)DNS服務(wù)器為M/M/c隨機(jī)服務(wù)系統(tǒng),模型如圖1所示.該系統(tǒng)具有以下性質(zhì):(1)查詢(xún)請(qǐng)求為單個(gè)到達(dá),到達(dá)的時(shí)間間隔符合參數(shù)λ的泊松分布;(2)每個(gè)請(qǐng)求所需的服務(wù)時(shí)間獨(dú)立,服從μ的負(fù)指數(shù)分布(忽略常規(guī)查詢(xún)與IXFR/AXFR查詢(xún)的應(yīng)答差異);(3)系統(tǒng)有c(c≥1)個(gè)服務(wù)臺(tái),服務(wù)的順序按照先來(lái)先服務(wù)FcFs(First come First served)規(guī)則;(4)系統(tǒng)容量為N(N>c,緩沖隊(duì)列長(zhǎng)度為N-c),請(qǐng)求源無(wú)限;(5)如果請(qǐng)求到來(lái)時(shí)隊(duì)列已經(jīng)被占滿,則出現(xiàn)丟包,否則進(jìn)入隊(duì)列等候.

圖1 M/M/c隨機(jī)服務(wù)系統(tǒng)模型

表1顯示了建模過(guò)程用到的數(shù)學(xué)符號(hào)及相關(guān)說(shuō)明.其中系統(tǒng)負(fù)荷強(qiáng)度為本文只考慮穩(wěn)定平衡狀態(tài)( ρ<1)的情況.

表1 DNS服務(wù)器數(shù)學(xué)建模符號(hào)說(shuō)明

1.2 性能瓶頸分析

服務(wù)器對(duì)查詢(xún)請(qǐng)求的響應(yīng)時(shí)間Ws為請(qǐng)求等待時(shí)間Wq和解析時(shí)間之和.響應(yīng)時(shí)間百分比γ %可表示為其中為用戶期望時(shí)間.下面將分別針對(duì)單服務(wù)臺(tái)模型和多服務(wù)臺(tái)模型分析響應(yīng)時(shí)間百分比的分布概率.

1)c=1時(shí),為M/M/1排隊(duì)模型.

根據(jù)參考文獻(xiàn)[8],有:

或者

對(duì)于DNS服務(wù)器,如果不通過(guò)流量控制等策略進(jìn)行人工干預(yù),請(qǐng)求到達(dá)速率λ為不可控因素.為了分析的方便,在此假設(shè)λ不變,用戶期望時(shí)間也不變.根據(jù)式(2)可知,響應(yīng)時(shí)間百分比 γ %隨著解析速率μ的增加而增加.

2)c>1時(shí),為M/M/c排隊(duì)模型.

查詢(xún)請(qǐng)求到達(dá)時(shí),如果緩沖隊(duì)列已滿,新的請(qǐng)求無(wú)法響應(yīng),服務(wù)器出現(xiàn)丟包,此時(shí)的概率稱(chēng)為損失概率.由參考文獻(xiàn)[8]可知,損失概率與緩沖隊(duì)列長(zhǎng)度有關(guān),增加緩沖隊(duì)列的長(zhǎng)度可降低損失概率.為了分析的方便,本文重點(diǎn)討論沒(méi)有請(qǐng)求損失的場(chǎng)景.因此,可假設(shè)緩沖隊(duì)列的長(zhǎng)度無(wú)限大,推導(dǎo)出響應(yīng)時(shí)間的分布函數(shù)[7]為:

其中,

由上述公式可知,在請(qǐng)求到達(dá)速率λ不變的情況下,響應(yīng)時(shí)間與服務(wù)臺(tái)數(shù)量c和解析速率μ有關(guān).DNS服務(wù)器實(shí)現(xiàn)多服務(wù)臺(tái)處理查詢(xún)請(qǐng)求的原理是提高了多核CPU的利用率,多服務(wù)臺(tái)的數(shù)量與CPU數(shù)量相關(guān).考慮到運(yùn)行成本,增加多服務(wù)臺(tái)數(shù)量的方式不作考慮.在服務(wù)臺(tái)數(shù)量固定的情況下,需要通過(guò)提高解析速率μ,來(lái)優(yōu)化響應(yīng)時(shí)間百分比.

查詢(xún)請(qǐng)求的解析過(guò)程依次為:接收請(qǐng)求、解壓縮請(qǐng)求包、查找匹配資源記錄、組裝應(yīng)答包、域名壓縮和發(fā)送應(yīng)答包.解壓縮請(qǐng)求包和組裝應(yīng)答包規(guī)則簡(jiǎn)單,耗時(shí)少,在此不做討論.而數(shù)據(jù)包的接收發(fā)送依賴(lài)于網(wǎng)絡(luò)通信框架,查找匹配資源記錄依賴(lài)于數(shù)據(jù)結(jié)構(gòu)和查找算法,改進(jìn)這兩個(gè)過(guò)程成本較高.因此本文將對(duì)域名壓縮算法進(jìn)行針對(duì)性?xún)?yōu)化.

2 DNS域名壓縮現(xiàn)狀

2.1 傳統(tǒng)壓縮算法

為了分析域名壓縮,需要對(duì)DNS服務(wù)器的數(shù)據(jù)處理流水線進(jìn)行分析,見(jiàn)圖2.為了分析的完整性,流水線中同時(shí)考慮了服務(wù)器的數(shù)據(jù)來(lái)源和數(shù)據(jù)出口.DNS服務(wù)器通過(guò)動(dòng)態(tài)更新或區(qū)域數(shù)據(jù)傳送對(duì)本地區(qū)域數(shù)據(jù)進(jìn)行更新,收到更新數(shù)據(jù)后進(jìn)行解壓縮再存儲(chǔ)到本地.服務(wù)器收到查詢(xún)請(qǐng)求后在存儲(chǔ)數(shù)據(jù)中查找匹配資源記錄,然后對(duì)查找結(jié)果進(jìn)行組裝、壓縮,最后返回應(yīng)答包給請(qǐng)求端.對(duì)DNS服務(wù)器來(lái)說(shuō),數(shù)據(jù)更新頻率遠(yuǎn)低于查詢(xún)請(qǐng)求的頻率,即大部分的查詢(xún)使用同一版本的數(shù)據(jù)進(jìn)行應(yīng)答.

圖2 傳統(tǒng)DNS數(shù)據(jù)處理流程圖

域名壓縮通過(guò)減少DNS數(shù)據(jù)中域名的冗余來(lái)降低帶寬占用.不論是常規(guī)查詢(xún)應(yīng)答或IXFR/AXFR查詢(xún)應(yīng)答,其出口帶寬大于入口帶寬,尤其是AXFR查詢(xún)應(yīng)答,這種差異更加明顯.以根區(qū)的全量區(qū)域數(shù)據(jù)傳送為例,數(shù)據(jù)包共包含2萬(wàn)多條資源記錄.而CN、COM等頂級(jí)域的資源記錄總數(shù)則達(dá)到了千萬(wàn)數(shù)量級(jí),域名壓縮的重要性可見(jiàn)一斑.域名壓縮算法直接影響著解析性能.

傳統(tǒng)域名壓縮算法衍生于LZ77[9].該算法基于數(shù)據(jù)本身包含有重復(fù)的字符序列這個(gè)特性,使用指針來(lái)代替已經(jīng)出現(xiàn)過(guò)的字符序列來(lái)達(dá)到壓縮的目的.域名壓縮利用指向數(shù)據(jù)包中已經(jīng)出現(xiàn)過(guò)的域名的指針來(lái)代替整個(gè)域名或者部分域名[10].該壓縮算法的壓縮比高,但壓縮過(guò)程耗時(shí),主要消耗在域名的匹配過(guò)程[11].在高查詢(xún)量場(chǎng)景下,在解析過(guò)程進(jìn)行實(shí)時(shí)的域名壓縮非常消耗系統(tǒng)資源.這是制約解析速率的主要原因.

2.2 改進(jìn)壓縮算法

根據(jù)DNS數(shù)據(jù)的特點(diǎn),域名壓縮只能采用無(wú)信息損失的無(wú)損壓縮算法[12–14].本文對(duì)無(wú)損壓縮算法進(jìn)行了充分的調(diào)研[15–21],結(jié)果如表2所示,只有部分LZ77系列算法適用于DNS域名壓縮.統(tǒng)計(jì)編碼和字典編碼中的LZ78算法不符合DNS標(biāo)準(zhǔn)協(xié)議.

近年來(lái)LZ77算法的改進(jìn)方向可大致分為兩類(lèi):一類(lèi)是嘗試與其他算法結(jié)合以獲取更好的壓縮效果,如與霍夫曼編碼結(jié)合產(chǎn)生的DEFLATE算法等,這類(lèi)改進(jìn)由于結(jié)合了統(tǒng)計(jì)編碼同樣不符合DNS協(xié)議.另一類(lèi)則通過(guò)優(yōu)化數(shù)據(jù)結(jié)構(gòu)和算法等方式提高壓縮效率,如LZSS,LZO等,此類(lèi)算法適用于DNS,但是數(shù)據(jù)處理流程與傳統(tǒng)壓縮算法相比并未發(fā)生實(shí)質(zhì)性變化,因而同樣無(wú)法減少資源消耗,提升解析速率.

根據(jù)上述分析,為了提高壓縮速率,可以考慮將壓縮模塊前置,將實(shí)時(shí)壓縮轉(zhuǎn)為寫(xiě)時(shí)壓縮,即在數(shù)據(jù)存儲(chǔ)時(shí)進(jìn)行壓縮處理.結(jié)合DNS服務(wù)器的特征,壓縮前置可以充分利用讀寫(xiě)操作的不對(duì)稱(chēng)性,提高系統(tǒng)資源的利用率.但是,現(xiàn)有域名壓縮依賴(lài)于域名位于數(shù)據(jù)包中的絕對(duì)位置,對(duì)于查詢(xún)應(yīng)答,服務(wù)器無(wú)法提前預(yù)知需要回復(fù)的資源記錄,因而現(xiàn)有的壓縮算法無(wú)法實(shí)現(xiàn)壓縮模塊前置.

表2 常見(jiàn)無(wú)損壓縮算法列表

3 基于基址重定位的快速域名壓縮算法

3.1 DNS數(shù)據(jù)特征分析

為了改進(jìn)壓縮算法,需要對(duì)DNS域名壓縮的原理進(jìn)行分析.壓縮是基于數(shù)據(jù)的冗余度進(jìn)行的減小數(shù)據(jù)存儲(chǔ)空間的過(guò)程[9].DNS根據(jù)域名空間倒置的樹(shù)形結(jié)構(gòu)進(jìn)行區(qū)域的劃分.區(qū)域數(shù)據(jù)以資源記錄為最小單位進(jìn)行存儲(chǔ),區(qū)域內(nèi)資源記錄的所有者(owner)都是其區(qū)域頂點(diǎn)(zone apex)的子域[10],因此區(qū)域內(nèi)的域名具有冗余性,這是域名壓縮實(shí)施的基礎(chǔ).此外,DNS的資源記錄之間還有其他相關(guān)性,可以進(jìn)行進(jìn)一步的域名壓縮.

對(duì)權(quán)威域名服務(wù)器來(lái)說(shuō),無(wú)論是常規(guī)查詢(xún)還是IXFR/AXFR查詢(xún),其應(yīng)答包大部分情況下包含多條相關(guān)的資源記錄.這些資源記錄可能是查詢(xún)的特定類(lèi)型的資源記錄,也可能是幫助請(qǐng)求端進(jìn)一步獲取最終信息的相關(guān)記錄.AXFR查詢(xún)則為特殊情況,其應(yīng)答返回了區(qū)域內(nèi)的所有資源記錄.分析查詢(xún)應(yīng)答結(jié)果后,發(fā)現(xiàn)DNS數(shù)據(jù)具有以下相關(guān)性.圖3是域名相關(guān)性示意圖.

(1)I類(lèi):相同域名,相同類(lèi)型的資源記錄

DNS查詢(xún)應(yīng)答包中,域名和類(lèi)型都相同的資源記錄從不單獨(dú)出現(xiàn),稱(chēng)為RRset[10](資源記錄集合).AXFR查詢(xún)應(yīng)答時(shí)也同樣如此.因而,域名和類(lèi)型都相同的資源記錄具有最基本的相關(guān)性,稱(chēng)為I類(lèi)相關(guān)記錄.該類(lèi)記錄可以進(jìn)行域名壓縮.

(2)II類(lèi):相同域名,不同類(lèi)型的資源記錄

IXFR/AXFR查詢(xún)應(yīng)答常常包含域名相同但類(lèi)型不同的資源記錄.常規(guī)查詢(xún)應(yīng)答時(shí),A記錄/AAAA記錄也常作為glue記錄[10]一同返回.部署DNSSEC[22]后,RRSIG記錄與其相關(guān)記錄也會(huì)同時(shí)返回給請(qǐng)求端.這些相關(guān)記錄包含相同的域名,同樣可以進(jìn)行域名壓縮,稱(chēng)為II類(lèi)相關(guān)記錄.

(3)III類(lèi):NS記錄及其glue記錄

對(duì)大部分查詢(xún)請(qǐng)求來(lái)說(shuō),獲取IP地址才是其最終目的.因此,返回NS記錄時(shí),A記錄/AAAA記錄常作為附加信息同時(shí)返回給請(qǐng)求端.此時(shí),NS記錄中的授權(quán)服務(wù)器的域名(NSNAME[23])與A記錄/AAAA記錄的所有者是相同的,同樣可以進(jìn)行域名壓縮.這種相關(guān)記錄稱(chēng)為III類(lèi)相關(guān)記錄.

圖3 域名相關(guān)性示意圖

上述3類(lèi)相關(guān)記錄中的域名是域名壓縮的主要對(duì)象.以根區(qū)數(shù)據(jù)為例,其資源記錄類(lèi)型多為 NS記錄、DS記錄、A記錄/AAAA記錄.全量區(qū)域數(shù)據(jù)傳送時(shí)有82%的域名進(jìn)行了壓縮,其中根據(jù)上述3類(lèi)相關(guān)性進(jìn)行壓縮的域名占總壓縮域名中的95%(I類(lèi)、II類(lèi)、III類(lèi)分別占36.4%、31.6%、27%).除了上述3類(lèi)相關(guān)性外,根區(qū)數(shù)據(jù)還利用了NSEC記錄中的next owner[22]進(jìn)行域名壓縮,但此類(lèi)壓縮不具備通用性.NSEC記錄在其他區(qū)域的數(shù)據(jù)中并不常見(jiàn),通常DNSSEC部署更傾向于采用NSEC3機(jī)制[22].常規(guī)查詢(xún)應(yīng)答時(shí),利用NSEC記錄的next owner進(jìn)行壓縮的可能性也很小.因此該相關(guān)性在此不做考慮.類(lèi)似MX、SRV等類(lèi)型的資源記錄可參考NS記錄及其glue記錄的方式實(shí)現(xiàn)域名壓縮,在此不再贅述.

3.2 本文改進(jìn)算法

為了實(shí)現(xiàn)壓縮模塊前置,需要取消域名壓縮時(shí)對(duì)數(shù)據(jù)包的依賴(lài),因此,本文在新的算法中引入了基址重定位技術(shù).基址重定位[24]是把程序的邏輯地址空間變換成內(nèi)存中的實(shí)際物理地址空間的過(guò)程.重定位表(Relocation Table)用于記錄重定位時(shí)需要修改的地址的位置(重定位入口的偏移),以便進(jìn)行內(nèi)存地址的修正.類(lèi)似地,在域名壓縮時(shí),可以先進(jìn)行域名的相對(duì)壓縮,再利用重定位表,修正偏移量,最終完成傳統(tǒng)域名壓縮.

結(jié)合DNS數(shù)據(jù)特征的分析結(jié)果,本文改進(jìn)算法只需聚焦于I類(lèi)、II類(lèi)、III類(lèi)相關(guān)記錄的域名壓縮,即可保障原始?jí)嚎s比.首先,在數(shù)據(jù)更新時(shí)完成I類(lèi)相關(guān)記錄中域名的相對(duì)壓縮,稱(chēng)為分組壓縮.之后,在應(yīng)答時(shí)無(wú)需查找,直接利用重定位表實(shí)現(xiàn)I類(lèi)相關(guān)記錄中壓縮域名的壓縮偏移量修正以及II類(lèi)相關(guān)記錄中域名的壓縮.最后實(shí)現(xiàn)III類(lèi)相關(guān)記錄的快速壓縮,稱(chēng)為關(guān)聯(lián)壓縮.運(yùn)用本文改進(jìn)算法后,數(shù)據(jù)處理流程圖見(jiàn)圖4.

圖4 本文改進(jìn)算法的數(shù)據(jù)處理流程圖

本文改進(jìn)算法的具體步驟如下,

(1)分組壓縮

將區(qū)域數(shù)據(jù)根據(jù)RRset、域名進(jìn)行分組.對(duì)RRset中的域名進(jìn)行相對(duì)壓縮,偏移量以RRset首字節(jié)為基準(zhǔn),并為同一域名下的所有RRset建立重定位表.重定位表在系統(tǒng)啟動(dòng)后即可建立,并在數(shù)據(jù)更新時(shí)進(jìn)行同步更新.相對(duì)壓縮結(jié)果如圖5所示.重定位表如表3所示.

圖5 RRset相對(duì)壓縮示意圖

表3 重定位表

(2)利用重定位表修正壓縮偏移量

在組裝應(yīng)答包的過(guò)程中,利用重定位表修正相對(duì)壓縮的偏移量.同時(shí),完成II類(lèi)資源記錄的域名壓縮.上述過(guò)程支持零查找.

(3)關(guān)聯(lián)壓縮

對(duì)于III類(lèi)資源記錄,在存儲(chǔ)時(shí)如果不做特殊處理,無(wú)法提前完成關(guān)聯(lián)壓縮.在不改變解析軟件數(shù)據(jù)結(jié)構(gòu)的前提下,可以在應(yīng)答時(shí)通過(guò)動(dòng)態(tài)字典實(shí)現(xiàn)關(guān)聯(lián)壓縮.動(dòng)態(tài)字典只在應(yīng)答過(guò)程建立,保存已添加的NS記錄的相關(guān)信息.在添加NS記錄或A/AAAA記錄時(shí),通過(guò)搜索動(dòng)態(tài)字典,即可完成III類(lèi)資源記錄的域名壓縮.傳統(tǒng)壓縮算法會(huì)對(duì)應(yīng)答的資源記錄中的所有域名,甚至其父域名建立字典,進(jìn)行匹配域名的查找,字典量大,搜索速率低.而用于關(guān)聯(lián)壓縮的編碼字典只有少量數(shù)據(jù),搜索速率很高.表4和表5分別是相同域名資源記錄的壓縮結(jié)果和最終壓縮結(jié)果.

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文改進(jìn)算法的性能,本文使用一臺(tái)Linux服務(wù)器作為測(cè)試平臺(tái),CPU為Intel Xeon,2*16核,單核主頻2.00 GHz.測(cè)試軟件采用BIND,上文已經(jīng)闡述適合于DNS的改進(jìn)算法是LZO與LZSS,LZO與LZSS相比算法復(fù)雜度更低,本文選擇LZO算法進(jìn)行對(duì)比實(shí)驗(yàn).分別采用傳統(tǒng)算法,改進(jìn)算法(LZO)及本文算法實(shí)現(xiàn)壓縮過(guò)程,并以根區(qū)數(shù)據(jù)為樣本進(jìn)行測(cè)試.

表4 相同域名的資源記錄壓縮結(jié)果

表5 最終壓縮結(jié)果

4.1 壓縮比

壓縮比是衡量域名壓縮的重要參數(shù).本文對(duì)常規(guī)查詢(xún)和AXFR查詢(xún)分別做了測(cè)試,分析壓縮比變化.

對(duì)于常規(guī)查詢(xún)場(chǎng)景,測(cè)試結(jié)果如表6所示.表中(+ED)代表DNSSEC查詢(xún).結(jié)果表明,對(duì)于常規(guī)查詢(xún)3種算法的壓縮比相同.

對(duì)于AXFR查詢(xún),利用根區(qū)數(shù)據(jù)進(jìn)行了對(duì)比測(cè)試.采用傳統(tǒng)算法和改進(jìn)算法,根區(qū)的全量數(shù)據(jù)共79個(gè)數(shù)據(jù)包,1341 181字節(jié);采用本文算法時(shí),根區(qū)的全量數(shù)據(jù)共79個(gè)數(shù)據(jù)包,1350 026字節(jié).本文算法在全量區(qū)域數(shù)據(jù)傳送場(chǎng)景下,與另外兩種算法相比僅增加了0.6%的數(shù)據(jù)量.測(cè)試結(jié)果說(shuō)明本文算法完全滿足DNS服務(wù)器的壓縮比實(shí)際需求.

表6 壓縮比對(duì)比結(jié)果

4.2 ASL

域名查找算法對(duì)域名壓縮性能有重要影響.ASL(Average Search Length)[25]是衡量查找速率的主要標(biāo)準(zhǔn).ASL指平均查找長(zhǎng)度,其中查找成功的ASL指找到已有元素的平均探測(cè)次數(shù),查找失敗的ASL指找到元素插入位置的平均探測(cè)次數(shù).本文對(duì)4.1節(jié)常規(guī)查詢(xún)的相同場(chǎng)景做了ASL對(duì)比分析,結(jié)果如表7所示(“/”代表無(wú)壓縮,0代表不需要查找).

采用傳統(tǒng)算法和改進(jìn)算法時(shí),其字典保存了應(yīng)答數(shù)據(jù)包中的所有域名及其子域名.采用本文算法時(shí),其字典中只包含需要關(guān)聯(lián)壓縮的域名,保存的域名數(shù)要遠(yuǎn)小于另兩種算法.由結(jié)果可知,本文改進(jìn)算法減少了壓縮時(shí)查找算法的ASL,有效提高了壓縮速率.

表7 ASL對(duì)比

4.3 響應(yīng)時(shí)間百分比

圖6顯示了各不同查詢(xún)響應(yīng)時(shí)間的百分比的測(cè)試結(jié)果對(duì)比.

與傳統(tǒng)算法和改進(jìn)算法相比,本文的算法可以有效縮短響應(yīng)時(shí)間,將90%以上的耗時(shí)控制在0.5 ms以下,而傳統(tǒng)與改進(jìn)算法只能將90%以上的耗時(shí)控制在0.65 ms以下,只有20%的耗時(shí)分布在0.5 ms以下.采用本文算法后DNS服務(wù)器的查詢(xún)響應(yīng)性能有明顯提升,達(dá)到了預(yù)期目標(biāo).

5 結(jié)論

本文基于排隊(duì)模型的分析結(jié)果,提出了一種基于基址重定位的快速域名壓縮算法.新算法充分利用了DNS服務(wù)器的數(shù)據(jù)特征,在不改變?cè)袛?shù)據(jù)結(jié)構(gòu)的前提下,通過(guò)重定位表和動(dòng)態(tài)編碼字典實(shí)現(xiàn)快速壓縮,提高了壓縮速率.相比于傳統(tǒng)算法和改進(jìn)算法,本文算法提高了響應(yīng)時(shí)間百分比,可以為用戶帶來(lái)更好的體驗(yàn).

圖6 響應(yīng)時(shí)間百分比對(duì)比圖