第二十九卷 第一期 - 2015年四月二十四日 PDF
Counter
使用多重索引混合鑑樹實作動態路由表之更新與查詢
林家弘1, 許家胤1, 謝孫源 1,2,3,*
1 國立成功大學資訊工程學系
2 國立成功大學資訊工程系暨製造資訊與系統研究所
3 國立成功大學醫學資訊研究所
 
字體放大
於網際網路的蓬勃發展,其應用程式所面對的巨量資料必需藉助高效率的資料結構及演算法才能有效地提升效能。其中,高效能路由器必須能夠提供高速的網路位址查詢。在這篇論文中,我們提出了一個動態的路由表資料結構,稱之為 Multi-Index Hybrid Trie (MIHT)。藉由賦予每筆前綴一個鍵值,使得我們能夠在平衡的搜尋樹上有效率地實施網路位址查詢。此外,由於樹高和需被比對的前綴數量同時減少了,使得動態路由表的各項運作變得更有效率。為了減少對記憶體容量大小的需求,我們只儲存後綴在我們的MIHT中而非整個的前綴字串。我們的實驗使用實際的網際網路通訊協定第四版(IPv4)及第六版(IPv6)的路由資料庫。透過實驗結果顯示,我們所提出的資料結構不但提供更小的記憶體需求,且在路由表的查詢以及更新運作的效能表現良好。在我們的實驗中所使用的四個前綴資料庫是AS1221、AS4637、AS6447和AS65000,它們分別有407,067、219,581、417,995和406,973筆前綴資料。
< 上一篇
下一篇 >
Copyright National Cheng Kung University