[en] As network link rates are being pushed beyond 40 Gb/s, IP lookup in high-speed routers is moving to hardware. The ternary content addressable memory (TCAM)-based IP lookup engine and the static random access memory (SRAM)-based IP lookup pipeline are the two most common ways to achieve high throughput. However, route updates in both engines degrade lookup performance and may lead to packet drops. Moreover, there is a growing interest in virtual IP routers where more frequent updates happen. Finding solutions that achieve both fast lookup and low update overhead becomes critical. In this paper, we propose a hybrid IP lookup architecture to address this challenge. The architecture is based on an efficient trie partitioning scheme that divides the forwarding information base (FIB) into two prefix sets: a large disjoint leaf prefix set mapped into an external TCAM-based lookup engine and a small overlapping prefix set mapped into an on-chip SRAM-based lookup pipeline. Critical optimizations are developed on both IP lookup engines to reduce the update overhead. We show how to extend the proposed hybrid architecture to support virtual routers. Our implementation shows a throughput of 250 million lookups per second (equivalent to 128 Gb/s with 64-B packets). The update overhead is significantly lower than that of previous work, the memory consumption is reasonable, and the utilization ratio of most external TCAMs is up to 100%.
Disciplines :
Computer science
Author, co-author :
Luo, Layong; Chinese Academy of Sciences - CAS > Institute of Computing Technology - ICT
Xie, Gaogang; Chinese Academy of Sciences - CAS > Institute of Computing Technology - ICT
Xie, Yingke; Chinese Academy of Sciences - CAS > Institute of Computing Technology - ICT
Mathy, Laurent ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes informatiques répartis et sécurité
Salamatian, Kavé; Université de Savoie
Language :
English
Title :
A Hybrid Hardware Architecture for High-speed IP Lookups and Fast Route Updates
Publication date :
2013
Journal title :
IEEE/ACM Transactions on Networking
ISSN :
1063-6692
eISSN :
1558-2566
Publisher :
Institute of Electrical and Electronics Engineers, New York, United States - New York
W. Jiang, Q. Wang, and V. K. Prasanna, "Beyond TCAMs: An SRAM-based parallel multi-pipeline architecture for terabit IP lookup," in Proc. IEEE INFOCOM, 2008, pp. 2458-2466.
G. Xie, P.He, H. Guan, Z. Li, Y.Xie, L. Luo, J. Zhang, Y.Wang, and K. Salamatian, "PEARL: A programmable virtual router platform," IEEE Commun. Mag., vol. 49, no. 7, pp. 71-77, 2011.
Z. J. Wang, H. Che, M. Kumar, and S. K. Das, "Coptua: Consistent policy table update algorithm for TCAM without locking," IEEE Trans. Comput., vol. 53, no. 12, pp. 1602-1614, Dec. 2004.
D. Shah and P. Gupta, "Fast updating algorithms for TCAM," IEEE Micro, vol. 21, no. 1, pp. 36-47, Jan.-Feb. 2001.
G.Wang and N. F. Tzeng, "TCAM-based forwarding engine with minimum independent prefix set (MIPS) for fast updating," in Proc. IEEE ICC, 2006, pp. 103-109.
V. Srinivasan and G. Varghese, "Fast address lookups using controlled prefix expansion," Trans. Comput. Syst., vol. 17, no. 1, pp. 1-40, Feb. 1999.
S. Sikka and G. Varghese, "Memory-efficient state lookups with fast updates," Comput. Commun. Rev., vol. 30, no. 4, pp. 335-347, 2000.
W. Jiang and V. K. Prasanna, "Towards practical architectures for SRAM-based pipelined lookup engines," in Proc. IEEE INFOCOM Work-in-Progress Track, 2010, pp. 1-5.
F. Baboescu, D. M. Tullsen,G. Rosu, and S. Singh, "A tree based router search engine architecture with single port memories," in Proc. ICSA, 2005, pp. 123-133.
S. Kumar, M. Becchi, P. Crowley, and J. Turner, "CAMP: Fast and efficient IP lookup architecture," in Proc. ACM/IEEE ANCS, 2006, pp. 51-60.
W. Jiang and V. K. Prasanna, "A memory-balanced linear pipeline architecture for trie-based IP lookup," in Proc. IEEE HOTI, 2007, pp. 83-90.
N. Futamura, R. Sangireddy, S. Aluru, and A. K. Somani, "Scalable, memory efficient, high-speed lookup and update algorithms for IP routing," in Proc. ICCCN, 2003, pp. 257-263.
R. Sangireddy, N. Futamura, S. Aluru, and A. Somani, "Scalable, memory efficient, high-speed IP lookup algorithms," IEEE/ACM Trans. Netw., vol. 13, no. 4, pp. 802-812, Aug. 2005.
H. Le, T. Ganegedara, and V. K. Prasanna, "Memory-efficient and scalable virtual routers using FPGA," in Proc. ACM/SIGDA FPGA, 2011, pp. 257-266.
A. Basu and G. Narlikar, "Fast incremental updates for pipelined forwarding engines," IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 690-703, Jun. 2005.
J. Hasan and T. N. Vijaykumar, "Dynamic pipelining: Making IP-lookup truly scalable," in Proc. ACM SIGCOMM, 2005, pp. 205-216.
"The BGP instability report," [Online]. Available: http://bgpupdates. potaroo.net/instability/bgpupd.html
Xilinx, San Jose, CA, USA, "Xilinx FPGA," [Online]. Available: http://www.xilinx.com/
J. Fu and J. Rexford, "Efficient IP-address lookup with a shared forwarding table for multiple virtual routers," in Proc. ACM CoNEXT, 2008, pp. 211-2112.
RIPE NCC, Amsterdam, The Netherlands, "RIPE RIS raw data," 2011 [Online]. Available: http://www.ripe.net/data-tools/stats/ris/ris-rawdata