臺灣博碩士論文加值系統

由於網際網路的快速成長，使得網路的骨幹路由器(Backbone Router)內的路徑表(Routing Table)呈指數般地增加，在2006年10月已經正式突破20萬筆，這也代表著使用簡單並支援快速路徑更新的演算法搭配高度管線化硬體架構最為適合處理如此大量的路徑查詢。
在本篇論文中，我們以Level Smart-Compression Trie[2]的路徑查詢為基礎，提出一個字首支配範圍字串(Prefix Dominant String)的資料結構來降低因為大型路徑表所產生的大量記憶體儲存需求，因而得以提升原本路徑查詢的效能，以期達到快速路徑查詢、低記憶體需求、支援快速路徑更新與可擴充性。利用本方法在281032筆資料的測試下(N=4，M=8)與LS-Compression Trie[2]架構相比，記憶體的使用由6,220 KB減少至601 KB，節省了90.33% 的空間，對於路徑查詢的效能則由45 MPPS增加至100 MPPS。

Due to the fast development of Internet, the routing table in backbone router of core network increases exponentially and reaches 200,000 entries formally. This means that the simple algorithm supporting fast incremental update with high pipelined hardware architecture is suitable to process huge IP routing lookups.
In the thesis, we present a data structure based on Level Smart-Compression Trie[2] scheme for IP lookup, which is called Prefix Dominant String (PDS), to decrease a large number of memory space requirement for big routing table. Therefore, it can raise the performance of original scheme and be expected to achieve fast IP lookup, low memory space requirement, supporting incremental update, and scalability. To utilize our scheme with 281,032 routing table entries (N=4, M=8) in popular platform and compare with LS-Compression Trie[2] scheme, the usage of memory space decreases from 6,220 KB to 601 KB, which saves 90.33% memory space. The performance for IP lookup increases from 45 MPPS to 100 MPPS.

第一章 緒論 1
1.1 研究動機 1
1.2 IP路徑查詢 1
1.3 研究目的 3
1.4 章節概要 3
第二章 相關研究 5
2.1 Binary Trie 6
2.2 Path-Compressed Trie (Patricia) 7
2.3 Franzon’s Scheme 9
2.4 Level Smart-Compression Trie 11
第三章 基本架構 14
3.1 資料結構 14
3.1.1 Node 15
3.1.2 Prefix Dominant String (PDS) 16
3.1.3 Next Hop Array (NHA) 21
3.1.4 完整的資料結構 22
3.2 建立轉送表 22
3.2.1 轉送表建構主程式 23
3.2.2 Node追蹤副程式 26
3.2.3 Leaf追蹤副程式 27
3.2.4 PDS追蹤副程式 29
3.3 網路路徑查詢 32
3.4 PDS區塊化簡 36
3.4.1 化簡具有相同Next Hop的剩餘區塊 37
3.4.2 合併帶有兩個最大字首範圍的區塊 37
3.4.3 取消Leaf中全部相同Next Hop的PDS結構 38
3.4.4 合併開頭結尾區塊以外連續最小字首範圍的區塊 38
3.5 轉送表建構與查詢實例 39
第四章 效能評估與實作 43
4.1 模擬環境 43
4.2 所選擇的路徑表 44
4.2.1 AS1221 Telstra IPv4 BGP Table 45
4.2.2 AS4637 Reach IPv4 BGP Table 47
4.2.3 AS6447 (route-views.oregon-ix.net) IPv4 BGP Table 49
4.2.4 Synthetic IPv6 BGP Table 51
4.2.5 PDS分佈圖觀察結果 51
4.3 分析結果 52
4.3.1 效能評估表 53
4.3.2 最佳參數效能評估表 57
4.3.3 與其他架構的效能比較表 58
4.4 硬體實作 60
4.4.1 IP路徑查詢硬體架構圖 60
4.4.2 IP路徑查詢流程圖與合成圖 61
4.4.3 模擬結果 65
第五章 結論 69
參考文獻 70

[1]Y. Rekhter and T. Li, “An Architecture for IP Address Allocation with CIDR,” RFC 1518, September 1993.
[2]P. C. Wang, C. T. Chan, W. C. Tseng, and Y. C. Chen, “Fast Trie-based Routing Lookup with Tiny Searchable Core,” IEEE Global Telecommunications Conference (GLOBECOM''02), November 2002, pp. 2328-2332.
[3]M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small Forwarding Tables for Fast Routing Lookups,” Proceedings of ACM SIGCOMM ''97, pp. 3-14, Cannes, France, Sep. 1997.
[4]P. Mehrotra and P. D. Franzon, “Novel Hardware Architecture for Fast Address Lookups,” IEEE Communications Magazine, vol. 40, no. 11, Nov. 2002, pp. 66-71.
[5]W. Eatherton, “Fast IP Lookup Using Tree Bitmap,” Washington University Master Thesis, 1999.
[6]H. Song, J. Turner, and J. Lockwood, “Shape Shifting Tries for Faster IP Route Lookup,” Proceedings of ICNP''05, Nov. 2005.
[7]B. Lampson, V. Srinivasan, and G. Varghese, “IP Lookups Using Multiway and Multicolumn Search,” IEEE/ACM Transactions on Networking, 7(4):323-334, June 1999.
[8]V. Srinivasan and G. Varghese, “Fast Address Lookups using Controlled Prefix Expansion,” ACM Transaction on Computer Systems, vol. 17, Feb. 1999.
[9]D. R. Morrison, “PATRICIA-Practical Algorithm to Retrieve Information Coded in Alphanumeric,“ Journal of the ACM, vol. 15, no. 4, Oct. 1968, pp. 514-34.
[10]S. Nilsson and G. Karlsson, “IP-Address Lookup Using LC-Tries,” IEEE JSAC, 17(6):1083-1092, June 1999.
[11]JEDEC Standard, “Double Data Rate (DDR) SDRAM Specification,” in http://www.jedec.org/download/search/JESD79E.pdf.
[12]“BGP Routing Table Analysis Reports,” in http://bgp.potaroo.net/.
[13]“University of Oregon Route Views Archive Project,” in http://archive.routeviews.org/.
[14]P. C. Wang, C. T. Chan, S. C. Hu, Y. C. Shih, and Y. C. Chen, “Hardware-based IP Routing Lookup with Incremental Update,“ IEEE International Conference on Parallel and Distributed Systems (ICPADS’02), December 2002, pp. 183-188.
[15]“PCMark05,” in http://www.futuremark.com/products/pcmark05/tests/.
[16]“Intel® 64 and IA-32 Architectures Software Developer''s Manuals,” in http://www.intel.com/products/processor/manuals/index.htm.
[17]A. Basu and G. Narlikar, “Fast Incremental Updates for Pipelined Forwarding Engines,” IEEE/ACM Transactions on Networking (TON), vol. 13, no. 3, pp. 690-703, June 2005.
[18]V. Srinivasan and G. Varghese, “Fast Address Lookups Using Controlled Prefix Expansion,” ACM Transactions on Computer Systems, vol. 17, no. 1, pp. 1-40, February 1999.