路由轉(zhuǎn)發(fā)表是命名數(shù)據(jù)網(wǎng)絡轉(zhuǎn)發(fā)模塊中重要的組成部分,轉(zhuǎn)發(fā)表不僅要能被快速構建,還要支持高速的動態(tài)名字查找.所謂動態(tài)查找,是指當進行名字查找時,轉(zhuǎn)發(fā)表還需同時支持表項的插入、更新和刪除操作.設計二者兼顧的轉(zhuǎn)發(fā)表仍是一大挑戰(zhàn),當前的研究成果主要是通過先構建路由表,再新建一個路由表索引來實現(xiàn)快速的名字查找,但對于高速動態(tài)名字查找效果仍然不佳.在本文中,我們將改進后的自適應基數(shù)樹融合到轉(zhuǎn)發(fā)表中,使轉(zhuǎn)發(fā)表能利用基數(shù)樹的特點,實現(xiàn)快速構建和動態(tài)名字查找,這種新的轉(zhuǎn)發(fā)表稱為自索引轉(zhuǎn)發(fā)表.實驗評估表明,自索引轉(zhuǎn)發(fā)表有效提升了轉(zhuǎn)發(fā)表的構建速度,保證了動態(tài)名字查找的效率,并在一定程度上節(jié)省了新建額外索引的內(nèi)存開銷. 

【文章來源】：小型微型計算機系統(tǒng). 2017,38(06)北大核心CSCD

【文章頁數(shù)】：6 頁

【部分圖文】：

一個簡單的基數(shù)樹

通過路徑遍歷將key值還原出來．2．2AＲT數(shù)據(jù)結(jié)構原始基數(shù)樹的中間節(jié)點大小是固定的，即每個節(jié)點具有相同個數(shù)的指針，為保證每個字符都能正確指向下一個節(jié)點，通常中間節(jié)點會很大，例如生成ASCII字符集的基數(shù)樹，每個中間節(jié)點至少需要128個指針，稱之為Node128．當數(shù)據(jù)集過大時，隨著插入元素的增加，基數(shù)樹的內(nèi)存開銷也會急劇增加，同時由于每個節(jié)點的分支過多，插入和查找效率也會下降．AＲT是對基數(shù)樹的改進，其優(yōu)勢在于中間節(jié)點大小是可以自動調(diào)節(jié)的，這樣不僅節(jié)省了內(nèi)存開銷，還能提高元素的插入和查找效率．圖2AＲT中間節(jié)點的轉(zhuǎn)化過程Fig．2ConversionprocessofAＲT'sinnernodeAＲT中間節(jié)點從小到大排列分別為:Node4、Node16、Node48和Node256．Node4節(jié)點具有4個指向下個節(jié)點的指針，當指針分配完時，Node4節(jié)點將自動轉(zhuǎn)化成擁有16個指針的Node16節(jié)點，以滿足更多元素插入的需要;當Node16節(jié)點指針數(shù)少于4個時，節(jié)點又會轉(zhuǎn)變?yōu)镹ode4，以節(jié)省內(nèi)存空間．與此類似，Node48和Node256具有相同的功能，整個節(jié)點的轉(zhuǎn)化過程如圖2所示．AＲT的葉子節(jié)點仍用來存儲key值對應的value值．2．3AＲT基本操作AＲT的四個基本操作分別是:insert、lookup、update和de-lete．在操作描述過程中使用到的參數(shù)定義如下:定義1．＜Kn，V＞，Kn為包含n個字符的key值，字符分別為c1，c2，．．．ci，．．．cn，ci代表Kn的第i個字符;V為對應的value值;定義2．Nj，為AＲT中間節(jié)點，其中j為節(jié)點Nj的標識;定義3．Ｒ，為AＲT的根節(jié)點，Ｒ本質(zhì)上仍是一個中間節(jié)點，設Ｒ的節(jié)點標識為N0;定義4．L，為AＲT葉子節(jié)點，存儲對應的value值．2．3．1Insert(插入)插入一個鍵值對＜Kn，V＞的具體過程如下:①從根節(jié)點?

SIF的構建Fig．3ConstructionofSIF

【參考文獻】：
期刊論文
[1]信息中心網(wǎng)絡研究綜述[J]. 夏春梅,徐明偉.  計算機科學與探索. 2013(06)



本文編號：3562436