臺灣博碩士論文加值系統

路由器上IP位址快速找尋機制
研究生：賓少鈺 指導教授：伍麗樵
國立雲林科技大學
電子與資訊工程研究所碩士班
摘要
近幾年來由於World Wide Web的快速成長與網路上多媒體應用程式的劇增，網路上的流量每三個月就成長一倍，因此路由器每秒需處理百萬或10百萬筆以上的封包，才能符合未來的網路需求。對下一代的高速IP routers而言，IP位址找尋(IP lookup)機制就是其中最關鍵的議題，因為IP lookup是目前router效能上最主要的瓶頸。
在此論文中，我們提出一個快速的IP lookup機制來找尋最長前置位元(Longest-Matching Prefix)，其中的轉送表(forwarding table)使用所謂的分層及壓縮的技術來設計以節省所需的記憶體空間；本機制最少需要1次記憶體存取(memory access)而最多只需4次記憶體存取即可完成IP lookup的動作。在IPv4骨幹網路的路由器(backbone router)，若它有40,000 routing entries利用本機制只需約260Kbytes的記憶體空間；以10ns的靜態存取記憶體來做評估，IP lookups的速度可達100×1000000 packets per second。此外，我們改良以往的壓縮技術使得routing table更新時可不需重建整個forwarding table，快速地完成更新的動作。

A Fast IP Lookup Scheme for Longest-Matching Prefix
Lih-Chyau Wuu, Shou-Yu Pin
Institute of Electronic and Information Engineering
National Yunlin University of Science and Technology
wuulc@el.yuntech.edu.tw
Abstract
One of the key design issues for the next generation IP routers is the IP Lookup mechanism. IP lookup is an important action in router that is to find the next hop of each incoming packet with a longest-prefix-match address in the routing table. In this paper, we propose an IP lookup mechanism with the number of memory access for an IP lookup being one in the best case and being four in the worst case. The forwarding table needed by our mechanism is small enough to fit in the SRAM. For example, a large routing table with 40000 routing entries can be compacted to a forwarding table of 260KBytes in our scheme. Moreover, the data structure of the forwarding table makes the updating operating quickly compared with other schemes since it can be updated without reconstructing from scratch when the routing table changes.
Keywords─IP lookup, routing table, CIDR, forwarding table, trie

目 錄
中文摘要 ……………………………………………………………... i
英文摘要 ……………………………………………………………... ii
誌謝 ……………………………………………………………... iii
目錄 ……………………………………………………………... iv
圖目錄 ……………………………………………………………... vii
表目錄 ……………………………………………………………... viii
一、 緒論…………………………………………………………………... 1
1.1 研究動機 ………………………………………………………... 2
1.2 何謂IP搜尋 ……………………………………………………. 2
1.3 IP搜尋之相關研究 .……………………………………………. 4
1.4 研究目的 ………………………………………………………... 8
1.5 論文架構 ………………………………………………………... 8
二、 路由器IP位址快速找尋架構及運作流程…………………… 9
2.1 IP Lookup之基本架構 ……….………………………………… 9
2.2 Segment array的建構方法[7] …..………………………………. 10
2.3 Next hop array(NHA)的建構方法[7] …...………………………. 12
2.4 L1FT/L2FT的建構方法 ………..………………………………. 14
2.5 L3FT/L4FT的建構方法 ………………………………………... 17
2.6 IP Lookup的運作流程 …………………………………………. 20
2.7 IP Lookup的硬體架構 …………………………………………. 23
三、 IP Lookup模擬環境之實作..………………………………………… 25
3.1 模擬環境之介紹……... …………………………………………. 25
3.2 模擬程式之介紹……... …………………………………………. 26
3.3 計憶體需求評估程式之介紹…….……………………………… 39
四、 效能評估...………………………………………….……………….. 42
五、 結論…………………………………………………………... 46
參考文獻
附錄

參考文獻
1. F. Baker, “Requirements for IP version 4 routers” RFC 1812, June 1995.
2. Y. Rekhter and T. Li, “An architecture for IP address allocation with CIDR”, RFC 1518, Sept 1993.
3. V. Fuller, T. Li, J. Yu, K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy", September 1993.
4. K. Sklower, A Tree-Based Routing Table for Berkeley Unix, Tchnical report, University of California, Berkeley, 1993.
5. P. Gupta, S. Lin, and N. McKeown, “Routing Lookups in Hardware at Memory Access Speeds”, In Proc. IEEE INFOCOM ’98, USA, March 1998, page 1240-1247.
6. M. Degermark, A. Brodnik, S.Carlsson, and S. Pink, “Small Forwarding Tables for Fast Routing Lookups”, In Proc. ACM SIGCOMM ’97, Sept. 1997, page 3-14.
7. N.-F. Huang, S.-M. Zhao, “A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Router”, In IEEE Journal on Selected Areas in Communications, JUNE 1999.
8. Merit Networks, Inc. Internet Performance Measurement and Analysis(IPMA) Statistics and Daily Reports. See http://www.merit.edu/ipma/routing_table/.
9. The Routing Arbiter Project, Internet routing and network statistic. See http://www.re.net/statistics/.
10. S. Deering and R. Hinden, “Internet Protocol, Version 6 (IPv6) Specification, Request for Comments (Proposed Standard)“ RFC 1883, Internet Engineering Task Force, Jan 1996.
11. P. Newman, G. Minshall, T. Lyon, and L. Huston, “IP switching and gigabit routers”, IEEE Commun. Magazine, Jane 1997, pp. 64-69.
12. C. Partridge, P. P. Carvey, E. Burgess, “A 50-Gb/s IP router”, IEEE/ACM Trans. Networking, June 1998, PP. 237-248.
13. A. Asthana, C. Delph, H. V. Jagadish, and P. Krzyzanowski, “Toward a gigabit IP router”, J. High Speed Networks, 1992, pp. 281-288.
14. H. Hong-Yi, T. Przygienda, “On Fast Address-Lookup Algorithms”, In IEEE
Journal on Selected Areas in Communications, JUNE 1999.
15. S. Nilsson and G. Karlsson, “Fast address lookup for internet routers”, in Proc. IFIP
4th Int. Conf. Broadband Communications, Stuttgart, Germany, Apr. 1998, pp. 11-22.
16. A. Przygienda, R. Shekhar, and R. Coltun, ”Fast IP address lookup using multi-resolution trees”, Fore Systems, Tech. Rep., Jan. 1997.
17. E. Filippi, V. Innocenti, and V. Vercellone, “Address lookup solutions for gigabit
switch/router”, CSELT, Tech. Rep., 1998.
18. A. McAuley and P. Francis, “Fast routing table lookup using CAM’s”, in Proc. IEEE
INFOCOM’88 Conf., New Orleans, LA.
19. T.-B. Pei and C. Zukowski, “Putting routing tables in silicon”, IEEE Network Mag., Jan. 1992, pp. 42-50.
20. H.-Y. Tzeng, “An efficient IP routing table lookup algorithm”, Bell Labs, Lucent Technologies, Tech. Rep., July 1997.
21. H.-Y. Tzeng, “Longest prefix search using compressed trees”, in Proc. IEEE Global
Communication’98 Conf., Sydney, Australia.
22. W. Doeringer, G. Karjoth, and M. Nassehi, “Routing on longest-matching prefixes”,
IEEE/ACM Trans. Networking, Feb. 1996, pp. 86-97.
23. V. Kumar, T. V. Lakshman, and D. Stiliadis, “Beyond best effort: Router architectures for the differentiated services of tomorrow’s Internet”, IEEE Commun. Mag., May 1998, pp. 152-164.