A high-throughput and high-capacity IPv6 routing lookup system

J. Yu, V. Fuller, T. Li, K. Varadhan, RFC1519: Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy, Internet Engineering Task Force (IETF), September 1993. Doeringer, 1996, Routing on longest-matching prefixes, IEEE/ACM Trans. Netw., 4, 86, 10.1109/90.503764 Cisco Router T1600. <http://www.cisco.com>. BGP Routing Table. <http://bgp.potaroo.net/>. CIDR Report. <http://www.cidr-report.org/>. Cisco Global IP Traffic Report. <http://www.cisco.com/en/US/netsol/ns827/networking_solutions_sub_solution.html>. Singhal, 2002, Terabit switching: a survey of techniques and current products, Comput. Commun., 25, 547, 10.1016/S0140-3664(01)00423-6 H. Song, F. Hao, M. Kodialam, T.V. Lakshman, IPv6 lookups using distributed and load balanced bloom filters for 100Gbps core router line cards, in: Proc. IEEE INFOCOM, 2009. Bando, 2012, FlashTrie: beyond 100-Gb/s IP route lookup using hash-based prefix-compressed trie, IEEE/ACM Trans. Netw., 20, 1262, 10.1109/TNET.2012.2188643 K. Huang, G. Xie, Y. Li, Alex X. Liu, Offset addressing approach to memory-efficient IP address lookup, in: Proc. IEEE INFOCOM, 2011. L. Luo, G. Xie, Y. Li, L. Mathy, K. Salamatian, A hybrid IP lookup architecture with fast updates, in: Proc. IEEE INFOCOM, 2012. Varghese, 1999, IP lookups using multiway and multicolumn search, IEEE/ACM Trans. Netw., 7, 324, 10.1109/90.779199 J. Turner M. Waldvogel, G. Varghese, B. Plattner, Scalable high speed IP routing lookups, in: Proc. ACM SIGCOMM’97, 1997. Somani, 2003, High-speed IP routing with binary decision diagrams based hardware address lookup engine, IEEE J. Sel. Areas Commun., 21, 513, 10.1109/JSAC.2003.810516 Wuu, 2007, A longest prefix first search tree for IP lookup, Comput. Netw., 51, 3354, 10.1016/j.comnet.2007.01.023 Z. Li, D. Zheng, Y. Ma, Tree, Segment table, and route bucket: a multi-stage algorithm for IPv6 routing table, in: Proc. IEEE INFOCOM, 2007. Chang, 2007, Fast binary and multiway prefix searches for packet forwarding, Comput. Netw., 51, 588, 10.1016/j.comnet.2006.05.005 X. Huang, X. Zhao, G. Zhao, W. Jiang, D. Zheng, Q. Sun, Y. Ma, A novel level-based IPv6 routing lookup algorithm, in: Proc. IEEE GLOBECOM, 2008. Park, 2012, An efficient IP address lookup algorithm based on a small balanced tree using entry reduction, Comput. Netw., 56, 231, 10.1016/j.comnet.2011.09.004 Lim, 2003, High speed IP address lookup architecture using hashing, IEEE Commun. Lett., 7, 502, 10.1109/LCOMM.2003.818885 Chang, 2005, A small and fast IP forwarding table using hashing, IEICE Trans. Commun., E88-B, 10.1093/ietcom/E88-B.1.239 Q. Sun, X.Huang, X. Zhou, Y. Ma, A dynamic binary hash scheme for IPv6 lookup, in: Proc. IEEE GLOBECOM, 2008. Z. Huang, J.-K. Peir, S. Chen, Approximately-perfect hashing: improving network throughput through efficient off-chip routing table lookup, in: Proc. IEEE INFOCOM, 2011. S. Lin, P. Gupta, N. McKeown, Routing lookups in hardware at memory access speeds, in Proc. IEEE INFOCOM, 1998. Chang, 2004, Efficient IP routing table VLSI design for multigigabit routers, IEEE Trans. Circ. Syst. I: Fundam. Theor. Appl., 51, 10.1109/TCSI.2004.823660 Fadishei, 2008, A fast IP routing lookup architecture for multi-gigabit switching routers based on reconfigurable systems, Microprocess. Microsyst., 32, 223, 10.1016/j.micpro.2008.01.001 W. Jiang, Q. Wang, V.K. Prasanna, Beyond TCAMs: an SRAM-based parallel multi-pipeline architecture for terabit IP lookup, in: Proc. IEEE INFOCOM, 2008. P. Francis, A.J. McAuley, Fast routing table lookup using CAMs, in: Proc. IEEE INFOCOM, 1993. Pagiamtzis, 2006, Content-addressable memory (CAM) circuits and architectures: a tutorial and survey, IEEE J. Solid-State Circ., 41, 712, 10.1109/JSSC.2005.864128 M. Tan, Z. Gong, High speed IP lookup algorithm with scalability and parallelism based on CAM array and TCAM, in: Proc. IEEE ICC, 2004. Akhbarizadeh, 2007, A TCAM-based parallel architecture for high-speed packet forwarding, IEEE Trans. Comput., 56, 58, 10.1109/TC.2007.250623 W. Lu, S. Sahni, Low power TCAMs for very large forwarding tables, in: Proc. IEEE INFOCOM, 2008. S. Deering, R. Hinden, E. Nordmark, RFC3587: IPv6 Global Unicast Address Format, Internet Engineering Task Force (IETF), August. 2003. 6NET, Large-Scale International IPv6 Pilot Network. <http://www.6net.org/>. University of Oregon Route Views Project. <http://www.routeviews.org/>. RIPE RIS. <http://www.ripe.net/data-tools/stats/ris/routing-information-service>. M.V. Ramakrishna, An exact probability model for finite hash table, in: Proc. IEEE Fourth International Conference on Data Engineering, February 1991. K. Zheng, B. Liu, A Scalable IPv6 prefix generator for route lookup algorithm, in: Proc. IEEE Advanced Information Networking and Applications, 2006. Tanenbaum, 1996 H. Liu, Reducing cache miss ratio for routing prefix cache, in: Proc. IEEE GLOBECOM, 2002. A. Akaaboune, J. Alghazo, N. Botros, Sf-lru cache replacement algorithm, in: Proc. International Workshop on Memory Technology Design and Testing, 2004. C.-S. Wu, W.-L. Shyu, T.-C. Hou, Efficiency analyses on routing cache replacement algorithms, in Proc. IEEE ICC, 2002. Nlnar Measurement and Network Analysis. <http://pma.nlanr.net/>. Wang, 2008, High-speed and low-power design techniques for TCAM macros, IEEE J. Solid-State Circ., 43, 530, 10.1109/JSSC.2007.914330 Jain, 1992, A comparison of hashing schemes for address lookup in computer networks, IEEE Trans. Commun., 40, 1570, 10.1109/26.168785 The Computer Center of the Ministry of Education. <http://www.edu.tw/tanet/introduction.html>. The SoC group of Electrical Engineering department in National Chung Cheng University. <http://www.soc.ccu.edu.tw>. Renesas TCAM. <http://tw.renesas.com/media/products/memory/TCAM/p20_tcam_products.pdf>. Micron DRAM, 256Mb DDR SDRAM, MT46V32M8P-5B. <http://www.micron.com>.