一種改進(jìn)的NAT-PT地址映射表查找算法

王相林,王慧娟

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院,浙江杭州310018)

0 引 言

IPv4網(wǎng)絡(luò)向IPv6網(wǎng)絡(luò)過渡已經(jīng)成為一種迫切需要,NAT-PT(網(wǎng)絡(luò)地址轉(zhuǎn)換和協(xié)議轉(zhuǎn)換)[1]是一種較好的過渡機(jī)制,它通過采用網(wǎng)絡(luò)地址轉(zhuǎn)換和協(xié)議轉(zhuǎn)換技術(shù)來實(shí)現(xiàn)IPv6網(wǎng)絡(luò)和IPv4網(wǎng)絡(luò)的互通。隨著轉(zhuǎn)換條目日漸增多,存儲空間變大,使得建立和維護(hù)地址映射表所需的CPU時(shí)間變長,因此地址映射表查找算法的性能問題已成為NAT-PT的瓶頸。該文通過分析路由查找算法和IPv4網(wǎng)絡(luò)中使用的網(wǎng)絡(luò)地址轉(zhuǎn)換(Network Adress Translation,NAT)技術(shù),提出了一種基于哈希表和多位樹的地址映射表查找算法,該算法具有較好的時(shí)間復(fù)雜度和空間復(fù)雜度,加快了地址轉(zhuǎn)換的速度,可以很好的滿足NAT-PT的高性能要求。

1 NAT-PT中的網(wǎng)絡(luò)地址轉(zhuǎn)換(NAT)技術(shù)

NAT-PT處于IPv4和IPv6網(wǎng)絡(luò)的交界處,不需要對現(xiàn)有的節(jié)點(diǎn)進(jìn)行改動,就能實(shí)現(xiàn)IPv4和IPv6節(jié)點(diǎn)之間的互通[1]。NAT模塊的主要功能是建立和維護(hù)地址映射,IPv6網(wǎng)絡(luò)向IPv4網(wǎng)絡(luò)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí),IPv6首先要訪問IPv4的DNS系統(tǒng)獲得地址解析,從地址池中獲取一個(gè)IPv4地址,把IPv6的源地址轉(zhuǎn)換成IPv4地址,然后把該轉(zhuǎn)換條目記錄在地址映射表中。當(dāng)IPv4網(wǎng)絡(luò)向IPv6網(wǎng)絡(luò)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí),查找地址映射表中的換條目進(jìn)行轉(zhuǎn)換[2]。

2 傳統(tǒng)的地址映射表查找算法及其缺陷

目前,常用的地址映射表查找算法主要有以下4種:線性查找、哈希表查找、檢索樹查找和路徑壓縮樹查找[3、4]。

線性表結(jié)構(gòu)是最簡單的查找數(shù)據(jù)結(jié)構(gòu),每一次查找需要遍歷線性表中的所有表項(xiàng),不利于條目的增減,而且查找時(shí)間和條目的長度成線性關(guān)系,適用于網(wǎng)絡(luò)環(huán)境比較慢的情況。哈希表算法的擴(kuò)展性不好,而且找到一個(gè)沖突盡可能小的良好性能的哈希函數(shù)并不容易。檢索樹是用樹的路徑表示表項(xiàng)中存放的地址,處于第L層的節(jié)點(diǎn)代表了比特均相同的地址空間,這L個(gè)比特串就是由從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)路徑上的L比特組成,如圖1所示。其內(nèi)存訪問的最壞的情形為IP地址的長度,在這種架構(gòu)下需要大量的內(nèi)存空間。路徑壓縮樹壓縮掉了檢索樹結(jié)構(gòu)中的單子節(jié)點(diǎn),減小了樹的平均深度。最差情況下,一次查找所需要操作是Q(w2)(w為樹的深度),這種查找算法如果成功,效率將很高,否則會因?yàn)榛厮?效率很低,如圖2所示。可見單一地應(yīng)用傳統(tǒng)算法,地址映射表的查詢效率較低,影響包的轉(zhuǎn)發(fā)率和延時(shí),已經(jīng)不能滿足NAT-PT高性能轉(zhuǎn)換的要求,設(shè)計(jì)一個(gè)合理的算法以保證網(wǎng)關(guān)在系統(tǒng)繁忙時(shí)的性能很有必要。

3 基于哈希表和多位樹的地址映射表查找算法設(shè)計(jì)

3.1 算法設(shè)計(jì)思想和實(shí)現(xiàn)過程

如果每次關(guān)鍵字查詢并不只是一位而是同時(shí)使用多位,能大大提高樹的檢索速度,例如IPv4地址,一次檢查4位,8次內(nèi)存訪問就可以。每一步被檢查的位數(shù)稱作步長,有動態(tài)步長和固定步長之分,允許多位同時(shí)查找的樹稱作多位樹。多位樹一次遍歷多位,不支持任意長度的前綴,需要把前綴集合擴(kuò)展成等價(jià)的數(shù)據(jù)結(jié)構(gòu)新集合。多位樹如圖3所示,步長為2-1,樹的高度減少了,相應(yīng)地訪問內(nèi)存的次數(shù)也減少了。

圖1 檢索樹

圖2 路徑壓縮樹

圖3 多位樹

通過分析6Bone上前綴長度的分布情形,并結(jié)合IPv6的地址分配政策,發(fā)現(xiàn)前綴長度等于24位的前綴大約占了58.48%,而且IPv6全球單播地址的前3位是001,所以用路由前綴的第4—24位的值構(gòu)建一個(gè)哈希表,哈希表中的表項(xiàng)指向一個(gè)對應(yīng)的改進(jìn)后的多位樹的根節(jié)點(diǎn),樹中所有節(jié)點(diǎn)均具有相同的前4-24位。兼顧內(nèi)存存取次數(shù)與存儲空間的需求,把剩余地址構(gòu)造成動態(tài)步寬的多位樹,以限制最壞情況下查找的訪問次數(shù)。這種改進(jìn)方法將會需要更多一點(diǎn)的內(nèi)存,但是相應(yīng)的查找速度也會得到提高,這也就是在內(nèi)存和速度之間尋找平衡。因?yàn)镮Pv4地址和IPv6的多播地址只用到最后32位,可以直接由地址組織成哈希表和步寬為8的多位樹進(jìn)行地址映射的查找。同時(shí)考慮到計(jì)算機(jī)的整個(gè)存儲系統(tǒng)的各種存儲介質(zhì)在速度和容量上存在的差異,把實(shí)時(shí)性要求比較高的查找表內(nèi)容置入Cache,將其建成靜態(tài)條目,可以獲得更高的查找速度,也減少了數(shù)據(jù)結(jié)構(gòu)所占據(jù)的存儲容量。改進(jìn)后的哈希

表和多位樹的數(shù)據(jù)結(jié)構(gòu)如圖4所示,Cache機(jī)制如圖5所示。

圖4 哈希表和多位樹的數(shù)據(jù)結(jié)構(gòu)

圖5 Cache機(jī)制

Hash表和多位樹的數(shù)據(jù)結(jié)構(gòu)定義如下:Struct Hash{//Hash表的數(shù)據(jù)結(jié)構(gòu)

u_int32_t key;//以地址前24位值構(gòu)建的哈希表的關(guān)鍵字struct Treenode*T//樹的根節(jié)點(diǎn),該樹具有相同的前24位比特值};

Struct Treenode{//多位樹的數(shù)據(jù)結(jié)構(gòu)Unsigned int stride;//查找的步長

Bool flag;//flag為標(biāo)志位,值為1或0

Union{

u_int32_t ip4addr;

u_int16_t ip6addr[8];

}u;

Struct Treenode*leaf[256];//指向分支節(jié)點(diǎn)的指針};

查找一個(gè)IP地址時(shí),先在cache中查找,若未命中,以前24位的地址作為key值從哈希表中查找匹配表項(xiàng),找到相應(yīng)的根節(jié)點(diǎn),然后從多位樹的根節(jié)點(diǎn)開始查找,查找的每一步根據(jù)stride的值查找地址中的多個(gè)比特,當(dāng)該節(jié)點(diǎn)中flag的值為1時(shí),表示已經(jīng)找到精確匹配的地址映射條目,無需再繼續(xù)查找;當(dāng)flag值為0時(shí),表示還未找到匹配項(xiàng),繼續(xù)查找,直到節(jié)點(diǎn)中指針leaf=NULL,查找結(jié)束,若存在精確匹配項(xiàng),則返回當(dāng)前節(jié)點(diǎn)中地址的映射地址。若不存在匹配項(xiàng),則新建并記錄一個(gè)轉(zhuǎn)換條目。

對于IPv6向IPv4轉(zhuǎn)發(fā)的數(shù)據(jù)包,具體實(shí)現(xiàn)過程如下:

(1)根據(jù)數(shù)據(jù)包中IPv6目的地址在Cache中搜索,如果命中,則得到映射地址IPv4地址,轉(zhuǎn)4,否則轉(zhuǎn)2;

(2)通過IPv6地址關(guān)鍵字在哈希表和多位樹中查找,若搜索成功,則得到映射地址IPv4地址。轉(zhuǎn)4,否則轉(zhuǎn)3;

(3)由程序產(chǎn)生地址池IPv4地址,在哈希表和多位樹中增加一個(gè)NAT轉(zhuǎn)換條目,如果是實(shí)時(shí)應(yīng)用或靜態(tài)條目則更新Cache;

(4)修改數(shù)據(jù)包中的目的地址為IPv4地址,并記錄新增轉(zhuǎn)換條目,發(fā)送數(shù)據(jù)包,結(jié)束。

對于IPv4向IPv6轉(zhuǎn)發(fā)的數(shù)據(jù)包,具體實(shí)現(xiàn)過程如下[5、6]:

(1)根據(jù)數(shù)據(jù)包中IPv4目的地址在Cache中查找,如果命中,則得到映射地址IPv6地址,轉(zhuǎn)3,否則轉(zhuǎn)2;

(2)在哈希表和多位樹中查找,若找到匹配項(xiàng)目,則得到映射地址IPv6地址,轉(zhuǎn)3,否則對數(shù)據(jù)包做非NAT處理,結(jié)束;

(3)修改包中的目的地址為IPv6地址,發(fā)送數(shù)據(jù)包,結(jié)束。整個(gè)查找算法的流程如圖6所示:

圖6 查找算法流程圖

3.2 算法性能分析

將NAT轉(zhuǎn)換條目按目的地址組織哈希表,并輔之以多位樹,直接使用24位比特的關(guān)鍵字key做為Hash表的查找索引,只需要一次存儲器訪問。同時(shí)采用多位樹的數(shù)據(jù)結(jié)構(gòu),每次查詢時(shí)使用動態(tài)步寬的關(guān)鍵字,大大減少了存儲器的訪問次數(shù),因而提高了查找效率。并且引入Cache機(jī)制,將實(shí)時(shí)性要求比較高的轉(zhuǎn)換條目置入存儲容量更小,讀取速度更快的Cache,將其建成靜態(tài)條目,不僅加快了搜索速度,而且減少了條目的數(shù)量,占用的存儲空間也更少。

將各算法的復(fù)雜度如表1所示。其中w為關(guān)鍵字的比特位數(shù),n為存儲表項(xiàng)的數(shù)目,k為多位樹的步寬。哈希索引表只需一次內(nèi)存訪問,查找復(fù)雜度為常量O(1),多位樹的查找操作的復(fù)雜度為O(w/k),故總的查找復(fù)雜度為O(w/k)。每一個(gè)前綴有長度為w/k的路徑和大小為2k的一層子樹組成,故被消耗的內(nèi)存的空間為O(2Knw/K)[7、8]。從表1中可以看出,當(dāng)路由表項(xiàng)n較大時(shí),基于樹的查找復(fù)雜度遠(yuǎn)遠(yuǎn)小于線性表和哈希表,基于表的查找算法已經(jīng)顯示出不足。盡管本算法的空間復(fù)雜度不如路徑壓縮樹,但因?yàn)橐隿ache,空間復(fù)雜度可作為次要考慮因素,且改進(jìn)后的算法具有很好的查找效率,通過適當(dāng)增加一定的內(nèi)存加快查找速度是值得的。

表1 算法復(fù)雜度對比表

4 結(jié)束語

該文從NAT-PT的實(shí)際應(yīng)用出發(fā),提出了一種基于哈希表和多位樹的地址映射表查找算法,與傳統(tǒng)的線性查找、哈希表查找、檢索樹查找和路徑壓縮樹查找算法相比,能大大加快地址轉(zhuǎn)換的操作,且所需存儲空間較少。特別是在有大量數(shù)據(jù)流經(jīng)NAT-PT網(wǎng)關(guān)時(shí),改進(jìn)算法的效率明顯優(yōu)于傳統(tǒng)算法,很好的滿足了NAT-PT網(wǎng)關(guān)在系統(tǒng)繁忙時(shí)的高性能要求。當(dāng)轉(zhuǎn)換條目更多時(shí),還可以對地址映射表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化,比如采用兩級哈希表或者對多位樹進(jìn)行層次壓縮。

[1] Tsirtsis G,Srisuresh P.Network Address Translation-Protocol Translation(NAT-PT)[S].RFC 2766,2000.

[2] Srisuresh P,Egevang K.Traditional IPNetwork Address Translator(Traditional NAT)[S].RFC 3022,2001.

[3] 趙凱輝.基于NAT-PT技術(shù)的翻譯網(wǎng)關(guān)的研究與實(shí)現(xiàn)[D].南京:東南大學(xué),2005.

[4] 華偉臣.IPv6路由器快速路徑查找算法[D].成都:四川大學(xué),2006.

[5] 韓玲,段曉東.一種基于NAT/PT的IPv6與IPv4轉(zhuǎn)換網(wǎng)關(guān)[J].計(jì)算機(jī)工程,2004,30(14):86-112.

[6] 陳行,陶軍,吳強(qiáng).基于混合映射機(jī)制的NAT-PT的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué),2009,36(5):33-64.

[7] 姚興苗,李樂民.一種快速IPv6路由查找方案[J].計(jì)算機(jī)學(xué)報(bào),2005,28(2):214-216.

[8] Ruiz-Sanchez M A,Biersack E W.Survey and taxonomy of IP add ress lookup algorithms[J].IEEE Network,2001,15(2):8-20.