第三十一卷 第四期 - 2017年三月三日 PDF
Counter
使用多重索引混和鍵樹實作路由表查詢與更新
林家弘1、許家胤1謝孫源1,2*
1 國立成功大學資訊工程學系
2 國立成功大學製造資訊與系統研究所
 
字體放大
於網際網路的普及化及其應用程式常需要巨量資料的傳輸,需要高效率的路由表來幫忙資料的傳輸,以避免網路的壅塞。位址查詢會影響一個進入封包的速度,因此位址查詢是路由表格設計的一個重要角色,由於網路的千變萬化,路由表格必須是動態支援快速地新增與刪除。隨著網際網路流量的快速成長,除了高效率的路由表設計之外,我們亦需要一個有效率之網路位址查詢技術。結合 B*樹的新觀念,提出了一個動態的路由表資料結構,稱之為 Multi-Index Hybrid Trie (MIHT),圖一為(4,4)-MIHT的架構。
圖一:(4,4)-MIHT

藉由賦予每筆前綴一個鍵值,使其能夠在平衡的搜尋樹上有效率的實施網路位址查詢。此外,由於樹高和需被比對的前綴數量同時減少了,使得動態路由表的各項運作變得更快速。我們的實驗使用實際的網際網路通訊協定第四版(IPv4)的路由資料庫。由表一至表三的實驗結果可以得知,我們所提出的資料結構不但提供更小的記憶體需求,且在路由表的查詢以及更新運作的效能表現良好。在我們的實驗中所使用的四個前綴資料庫是AS1221、AS4637、AS6447和AS65000,它們分別有407,067、219,581、417,995和406,973筆前綴資料。

表一:平均樹高與空間需求的比較


表二:查詢與記憶體需求的比較


表三:更新與記憶體需求的比較
< 上一篇
下一篇 >
Copyright National Cheng Kung University