臺灣博碩士論文加值系統

IP搜尋為目前路由器效能上最主要的瓶頸，對於每一個進入路由器的封包，都必須使用該封包上的目的位址 (Destination address，DA) 與forwarding table做比對，並選出prefix最長且符合DA的entry (longest prefix matching)，以決定該封包的next-hop。
在本篇論文中，我們設計以含蓋清單作為IP搜尋方法 (IP Lookup based on Cover-list, IPLC) 的架構來建立forwarding table。此架構使用cover list來儲存prefixes之間的covering關係，凡是有含蓋關係的prefixes皆會存入同一個cover list，之後在執行IP lookup時，只要在cover list內找到含蓋DA且含蓋範圍最小的prefix，即可滿足longest prefix matching特性。本論文是以prefix範圍作為執行IP lookup的基礎，我們使用4-level階層式架構，每個節點 (node) 均存有一筆或更多的prefix資訊，在執行IP lookup時將memory access次數限制在3次以內，使得平均搜尋一個DA所需的時間降低，而達成高效能搜尋目標。整體而言，我們的IPLC架構具有以下特性：在模擬環境下，具有執行每秒11百萬次IP lookup能力、快速更新轉送表、無預先處理時間、搜尋深度限制在3層以內。最後經由效能比較分析後，證明IPLC比MRT[20]及PIBT[21]有更高的搜尋效能、更高的更新效能，及較低的記憶體需求量。

IP lookup is the chief bottleneck affecting performance of current routers. A router examines the destination address (DA) of each incoming packet against its forwarding table whereby the longest prefix matching entry would be chosen, and the next-hop decision for this packet is made.
In this paper we have designed a scheme named IP Lookup based on Cover-list (IPLC) to construct the forwarding table. The cover list is used to store the covering relation among prefixes. That is, if only a prefix is covered, it will be stored into a cover list with all the prefixes covering it. Hence when we perform IP lookup for a DA, finding the longest prefix matching amounts to seek the prefix which covers the DA and its covering range is the narrowest in the cover list. The fundamental idea to this paper is that IP lookup is executable on prefix ranges. IPLC is a kind of 4-level scheme; each node is equipped with the room to store more than one prefixes. The number of memory access during an IP lookup is restricted to 3 at most, so the average time to search for a DA is reduced, and the goal of high-perofrmance search is achieved. IPLC as a whole has the characteristics as follows: the ability of 11 millions of IP lookup per second in the experimental environment, fast updating to the forwarding table, nonpreprocessing time, equal to or less than 3 levels accessed during a search. The experimental results have shown that IPLC outperforms MRT[20] and PIBT[21] in terms of search performance, update performance, and memory requirement.

一、緒論
1.1　研究動機
1.2　IP搜尋 (IP Lookup)
1.3　IP搜尋之相關研究
1.4　研究目的
1.5　論文結構
二、相關研究
2.1　Trie
2.2　Multiway Range Tree (MRT)
2.3　Prefix in B-tree (PIBT)
三、IP Lookup based on Cover-list
3.1　IPLC的基本概念
3.2　資料結構
3.3　IPLC運作流程
四、效能評估
4.1　模擬環境
4.2　IP lookup效能比較
4.3　記憶體需求量比較
4.4　更新 (update) 效能比較
五、結論
參考文獻

[1]Internet traffic growth: A gale or a hurricane?, RHK StarTrax conference, Palm Springs, California. (Nov. 2, 2000). [Online]. Available: http://www.dtc.umn.edu/~odlyzko/talks, 2008.
[2]Internet Systems Consortium, Internet Domain Survey. http://www.isc.org/, 2008.
[3]Bellcore, "Synchronous Optical Network (SONET) Transport Systems: Common Generic Criteria (GR-253-CORE)", Issue 3, Sep. 2000.
[4]BGP Routing Table Analysis Reports, http://bgp.potaroo.net/, 2008.
[5]F. Baker, “Requirements for IP Version 4 Routers,” RFC 1812, 1995.
[6]S. Deering and R. Hinden, “Internet Protocol, Version 6 (IPv6) Specification, Request for Comments (Proposed Standard),” RFC 1883, 1996.
[7]Y. Rekhter and T. Li, An Architecture for IP Address Allocation with CIDR, IETF RFC 1518, Sep. 1993.
[8]S. Fuller, T. Li, J. Yu, and K. Varadhan, Classless Inter-Domain Routing (CIDR): An Address Assignment and Aggregation Strategy, IETF RFC 1519, Sep. 1993.
[9]M. A. Ruiz-Sanchez, E.W. Biersack, and W. Dabbous, “Survey and taxonomy of IP address lookup algorithms,” IEEE Network, vol. 15, no. 2, pp. 8-23, Mar.-Apr. 2001.
[10]A. McAuley, P. Tsuchiya, and D. Wilson, “Fast multilevel hierarchical routing table using content-addressable memory,” U.S. Patent 5,386,413, Jan. 31, 1995.
[11]P. Gupta, S. Lin, and N. McKeown, “Routing lookups in hardware at memory access speeds,” Proceedings of IEEE Infocom, San Francisco, U.S.A., pp. 1240-1247, 1998.
[12]V. Srinivasan, G. Varghese, “Fast address lookups using controlled prefix expansion,” ACM Trans. Computer Systems, vol. 17, no.1, pp. 1-40, 1999.
[13]S. Sahni, K.S. Kim, “Efficient construction of multibit tries for IP lookup,” IEEE/ACM Trans. Networking, vol. 11, no. 4, pp. 650-662, Aug. 2003.
[14]M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small forwarding tables for fast routing lookups, ” ACM SIGCOMM, pp. 3-14, 1997.
[15]N.F. Huang and S.M. Zhao, “A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 6, pp. 1093-1104, Jun. 1999.
[16]J. Hennessy and D. Patterson, Computer Architecture: A Quantitative Approach, 2nd ed., Morgan Kaufmann, San Francisco, 1996.
[17]B. Lampson, V. Srinivasan, and G. Varghese, “IP Lookups Using Multiway and Multicolumn Search,” IEEE/ACM Trans. Networking, pp. 324-334, Jun. 1999.
[18]S. Nilsson and G. Karlsson, “IP-address lookup using LC-tries,” IEEE Journal on Selected Areas in Communications, vol 17, no 6, pp. 1083-1092, Jun. 1999.
[19]K. Sklower, “A Tree-Based Packet Routing Table for Berkeley UNIX,” technical report, Univ. of California, Berkeley, 1993.
[20]P. Warkhede, S. Suri, and G. Varghese, “Multiway Range Trees: Scalable IP Lookup with Fast Updates,” Computer Networks, vol. 44, no. 3, pp. 289-303, Feb. 2004.
[21]H. Lu and S. Sahni, “A B-Tree Dynamic Router-Table Design,” IEEE Trans. Computers, vol. 54, no. 7, pp. 813-824, Jul. 2005.
[22]T. Cormen, C. Lieserson, R. Rivest, and C. Stein, Introduction to Algorithms, second ed. MIT Press, 2001.
[23]E. Horowitz, S. Sahni, SA Freed, “Fundamentals of data structure in C,” Computer Science Press, 2003.
[24]L.C. Wuu, T.J. Liu, and K.M. Chen, “A Longest Prefix First Search Tree for IP Lookup,” Computer Networks, vol. 51, Issue 12, pp. 3354-3367 Aug. 2007.
[25]Merit Networks, Inc. Internet Performance Measurement and Analysis (IPMA) Statistics and Daily Reports, http://www.merit.edu/ipma/routing_table/.
[26]D. Meyer Univ. of Oregon Route Views Archive Project, http://archive.routeviews.org/.
[27]Y. Chang and Y. Lin, “Dynamic Segment Trees for Ranges and Prefixes,” IEEE Trans. Computers, vol. 56, no. 6, pp. 769-784, Jun. 2007.
[28]G. Alefeld and J. Herzberger, “Introduction to interval computations,” New York, Academic Press,1983