第二十七卷 第七期 - 2014年十月十日 PDF
Counter
使用Suffix B-Trie為架構之動態路由表之設計與實作
謝孫源1,2,3,*, 黃怡玲1, 楊盈琦1
1 國立成功大學電機資訊學院 資訊工程學系
2 國立成功大學製造資訊與系統研究所
3 國立成功大學醫學資訊研究所
 
字體放大
於網際網路的蓬勃發展,其應用程式所面對的巨量資料必需藉助高效率的資料結構及演算法才能有效地提升效能。位址查詢會影響一個進入封包決定出口的速度,因此位址查詢是路由表格設計的一個重要角色,由於網路的千變萬化,路由表格必須是動態支援快速地新增與刪除,在這篇論文中,我們設計出一個快速位址查詢與更新的動態路由表格資料結構,命名為Suffix B-tree。這個資料結構的特色是一個結點可以儲存不只一個前綴,此機制可以減少記憶體連結的次數,並且在位址查詢時,一個結點可以搜尋多個前綴,除此之外,當找尋最長前綴筆對時,可能不需要筆對到葉子節點,即可找到最佳的答案;當執行更新時,不需要重新建立路由表格外,路由表格的建立時間快速。我們所提出的資料結構,不但運算速度快,而且記憶體的連結次數少,位址查訊與位址新增的運算時間複雜度為 ,其中W是位址的長度,m是步幅,而位址刪除的運算時間複雜度為 。此外,以Suffix B-tree為基礎,我們也提出了一個延伸的資料結構,命名為Index Suffix B-tree,更能處理巨量資料與加速運算。
< 上一篇
下一篇 >
Copyright National Cheng Kung University