[en] As network link rates are being pushed beyond 40 Gbps, IP lookup in high-speed routers is moving to hardware. The TCAM (Ternary Content Addressable Memory)-based IP lookup engine and the SRAM (Static Random Access Memory)- 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 (MLPS). The update overhead is significantly lower than that of previous work 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é; University of Savoie
Language :
English
Title :
A Hybrid IP Lookup Architecture with Fast Updates
Publication date :
March 2012
Event name :
IEEE INFOCOM
Event place :
Orlando, United States - Florida
Event date :
from 25-3-2012 to 30-3-2012
Audience :
International
Main work title :
Annual International Conference on Computer Communications
W. Jiang, Q. Wang, and V. K. Prasanna, "Beyond TCAMs: An SRAM-based parallel multi-pipeline architecture for terabit IP lookup," in INFOCOM'08: Proceedings of the 27th Conference on Computer Communications, pp. 2458-2466, 2008.
Z. J. Wang, H. Che, M. Kumar, and S. K. Das, "CoPTUA: Consistent policy table update algorithm for TCAM without locking," Ieee Transactions on Computers, vol. 53, pp. 1602-1614, Dec 2004.
D. Shah and P. Gupta, "Fast updating algorithms for TCAMs," IEEE Micro, vol. 21, pp. 36-47, 2001.
G. Wang and N. F. Tzeng, "TCAM-based forwarding engine with minimum independent prefix set (MIPS) for fast updating," in ICC'06: 2006 IEEE International Conference on Communications, Vols 1-12, pp. 103-109, 2006.
V. Srinivasan and G. Varghese, "Fast address lookups using controlled prefix expansion," Acm Transactions on Computer Systems, vol. 17, pp. 1-40, Feb 1999.
S. Sikka and G. Varghese, "Memory-efficient state lookups with fast updates," Computer Communication Review, vol. 30, pp. 335-347, Oct 2000.
W. Jiang and V. K. Prasanna, "Towards practical architectures for SRAM-based pipelined lookup engines," in INFOCOM IEEE Conference on Computer Communications Workshops, pp. 1-5, 2010.
F. Baboescu, D. M. Tullsen, G. Rosu, and S. Singh, "A tree based router search engine architecture with single port memories," in ISCA'05: Proceedings of the 32nd International Symposium on Computer Architecture, pp. 123-133, 2005.
S. Kumar, M. Becchi, P. Crowley, and J. Turner, "CAMP: fast and efficient IP lookup architecture," in ANCS'06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, San Jose, California, USA, pp. 51-60, 2006.
W. Jiang and V. K. Prasanna, "A memory-balanced linear pipeline architecture for trie-based IP lookup," 15th Annual IEEE Symposium on High-Performance Interconnects, Proceedings, pp. 83-90, 2007.
A. Basu and G. Narlikar, "Fast incremental updates for pipelined forwarding engines," in IEEE INFOCOM 2003, pp. 64-74.
J. Hasan and T. N. Vijaykumar, "Dynamic pipelining: Making IP-lookup truly scalable," in Proc. ACM SIGCOMM 2005, pp. 205-216.
K. Huang, G. Xie, Y. Li, and A. X. Liu, "Offset addressing approach to memory-efficient IP address lookup," in IEEE INFOCOM Mini-Conference, pp. 306-310, 2011.
J. Fu and J. Rexford, "Efficient IP-address lookup with a shared forwarding table for multiple virtual routers," in CoNEXT'08: Proceedings of the 2008 ACM CoNEXT Conference, Madrid, Spain, pp. 1-12, 2008.
H. Y. Song, M. Kodialam, F. Hao, and T. V. Lakshman, "Building scalable virtual routers with trie braiding," in INFOCOM'10: Proceedings of the 29th Conference on Computer Communications, pp. 1-9, 2010.
The BGP Instability Report. Available: http://bgpupdates.potaroo.net/ instability/bgpupd.html
H. Le, T. Ganegedara, and V. K. Prasanna, "Memory-efficient and scalable virtual routers using FPGA," in FPGA'11: Proceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays, Monterey, CA, USA, pp. 257-266, 2011.
G. Xie, et al. PEARL: A programmable virtual router platform. IEEE Comm. Magazine, Special Issue on Future Internet Architectures: Design and Deployment Perspectives, 2011.
Xilinx FPGA. Available: http://www.xilinx.com/
RIPE RIS Raw Data. Available: http://www.ripe.net/datatools/stats/ris/ ris-raw-data.
NetLogic, "NL9000 RA knowledge-based processors," 2009.
M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous, "Survey and taxonomy of IP address lookup algorithms," Ieee Network, vol. 15, pp. 8-23, Mar-Apr 2001.
