命名數(shù)據(jù)網(wǎng)絡(luò)的路由查找算法研究.pdf

1、以IP包交換為核心的互聯(lián)網(wǎng)結(jié)構(gòu)設(shè)計(jì)已經(jīng)流行了數(shù)十年，網(wǎng)絡(luò)之間互聯(lián)最初的目標(biāo)是實(shí)現(xiàn)硬件資源的共享。然而，隨著技術(shù)飛速發(fā)展和信息的爆炸式增加，信息共享成為了如今的主要需求，硬件共享變得不再那么重要。命名數(shù)據(jù)網(wǎng)絡(luò)作為一種全新的網(wǎng)絡(luò)模式，其目的是為了更好的滿(mǎn)足用戶(hù)快速便捷的訪(fǎng)問(wèn)互聯(lián)網(wǎng)內(nèi)容的需求。
　　命名數(shù)據(jù)網(wǎng)絡(luò)通過(guò)內(nèi)容名字進(jìn)行路由查找與轉(zhuǎn)發(fā)。與IP網(wǎng)絡(luò)路由方法相比，名字查找有一些不同的特征。例如可變長(zhǎng)度、層次化的名字結(jié)構(gòu)；比IP網(wǎng)絡(luò)大2

2、~3個(gè)數(shù)量級(jí)的路由表規(guī)模；內(nèi)容頻繁的發(fā)布刪除導(dǎo)致的路由更新。這些特征使得實(shí)現(xiàn)快速名字路由查找算法成為一個(gè)重大而艱巨的任務(wù)。針對(duì)這一問(wèn)題，本課題結(jié)合命名數(shù)據(jù)網(wǎng)絡(luò)名字的特性，對(duì)名字結(jié)構(gòu)及算法進(jìn)行了改進(jìn)。
　　本課題先研究了常用的查找樹(shù)、哈希表、布隆過(guò)濾器三種經(jīng)典結(jié)構(gòu)的名字路由查找算法。針對(duì)查找樹(shù)存儲(chǔ)開(kāi)銷(xiāo)太大，哈希表存在碰撞且不滿(mǎn)足最長(zhǎng)前綴匹配等問(wèn)題，并結(jié)合名字層次結(jié)構(gòu)的特征，本課題設(shè)計(jì)了一種基于哈希查找樹(shù)的路由算法。這種方法通過(guò)哈希函

3、數(shù)將詞元組件而不是整個(gè)名字散列成哈希值，從而適用于最長(zhǎng)前綴匹配。同時(shí)每層詞元單獨(dú)設(shè)計(jì)哈希函數(shù)能保證哈希碰撞控制在一個(gè)很低的范圍內(nèi)。然后查找樹(shù)的狀態(tài)轉(zhuǎn)移不通過(guò)詞元而是通過(guò)哈希值匹配來(lái)確定，使得查找效率得到提升。此外哈希值比名字詞元將占用更少的存儲(chǔ)空間，從而降低了結(jié)構(gòu)的空間開(kāi)銷(xiāo)。同時(shí)哈希計(jì)算可以預(yù)處理，和名字查找處于并行結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明該結(jié)構(gòu)有效的提升了查找樹(shù)的空間效率并小幅度提升了查找效率。
　　為了進(jìn)一步解決名字可變長(zhǎng)度導(dǎo)致的查