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

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

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

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