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

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

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

【部分圖文】：

一個(gè)簡(jiǎn)單的基數(shù)樹(shù)

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

SIF的構(gòu)建Fig．3ConstructionofSIF

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



本文編號(hào)：3562436