Tong Yang
Abstract
The Forwarding Information Base (FIB) of backbone routers has been rapidly growing in size. An ideal IP lookup algorithm should achieve constant, yet small, IP lookup time and on-chip memory usage. However, no prior IP lookup algorithm achieves both requirements at the same time. In this paper, we first propose SAIL, a Splitting Approach to IP Lookup. One splitting is along the dimension of the lookup process, namely finding the prefix length and finding the next hop, and another splitting is along the dimension of prefix length, namely IP lookup on prefixes of length less than or equal to 24 and IP lookup on prefixes of length longer than 24. Second, we propose a suite of algorithms for IP lookup based on our SAIL framework. Third, we implemented our algorithms on four platforms: CPU, FPGA, GPU, and many-core. We conducted extensive experiments to evaluate our algorithms using real FIBs and real traffic from a major ISP in China. Experimental results show that our SAIL algorithms are several times or even two orders of magnitude faster than well known IP lookup algorithms.
- FPGA data sheet {on line}. Available: http://www.xilinx.com.Google Scholar
- Quagga routing suite {on line}. Available: http://www.nongnu.org/quagga/.Google Scholar
- RIPE network coordination centre {on line}. Available: http://www.ripe.net.Google Scholar
- SAIL webpage. http://fi.ict.ac.cn/firg.php?n=PublicationsAmpTalks. OpenSource.Google Scholar
- Tilera datasheet {on line}. Available: http://www.tilera.com/sites/default/files/productbriefs/TILE-Gx8036PB033-02web.pdf.Google Scholar
- K. Adam and M. Michael. Less hashing, same performance: Building a better bloom filter. In Algorithms--ESA 2006, pages 456--467. Springer, 2006. Google ScholarDigital Library
- P. Derek, L. Ziyan, and P. Hang. IP address lookup using bit-shuffled trie. IEEE Computer Communications, 2014.Google Scholar
- S. Devavrat and G. Pankaj. Fast incremental updates on ternary-cams for routing lookups and packet classification. In Proc. Hot Interconnects, 2000.Google Scholar
- W. Feng and H. Mounir. Matching the speed gap between sram and dram. In Proc. IEEE HSPR, pages 104--109, 2008.Google Scholar
- B. Florin, T. Dean, R. Grigore, and S. Sumeet. A tree based router search engine architecture with single port memories. In Proc. IEEE ISCA, 2005. Google ScholarDigital Library
- Z. Francis, N. Girija, and B. Anindya. Coolcams: Power-efficient tcams for forwarding engines. In Proc. IEEE INFOCOM, pages 42--52, 2003.Google Scholar
- R. Gabor, T. Janos, A. Korosi, A. Majdan, and Z. Heszberger. Compressing IP forwarding tables: Towards entropy bounds and beyond. In Proc. ACM SIGCOMM, 2013. Google ScholarDigital Library
- P. Gupta, S. Lin, and N. McKeown. Routing lookups in hardware at memory access speeds. In Proc. IEEE INFOCOM, pages 1240--1247, 1998.Google ScholarCross Ref
- F. Hamid, Z. M. Saheb, and S. Masoud. A novel reconfigurable hardware architecture for IP address lookup. In Proc. ACM/IEEE ANCS, pages 81--90, 2005. Google ScholarDigital Library
- S. Haoyu, K. Murali, H. Fang, and L. TV. Scalable IP lookups using shape graphs. In Proc. ACM/IEEE ICNP, pages 73--82, 2009. Google ScholarDigital Library
- L. Hoang, J. Weirong, and P. V. K. A sram-based architecture for trie-based IP lookup using fpga. In Proc. IEEE FCCM, pages 33--42, 2008. Google ScholarDigital Library
- L. Hyesook, Y. Changhoon, and S. Earl. Priority tries for IP address lookup. IEEE Transactions on Computers, 59(6):784--794, 2010. Google ScholarDigital Library
- F. Jing and R. Jennifer. Efficient IP-address lookup with a shared forwarding table for multiple virtual routers. In Proc. ACM CoNEXT. ACM, 2008. Google ScholarDigital Library
- Z. Kai, H. Chengchen, L. Hongbin, and L. Bin. A tcam-based distributed parallel IP lookup scheme and performance analysis. IEEE/ACM Transactions on Networking, 14(4):863--875, 2006. Google ScholarDigital Library
- S. Keith. A tree-based packet routing table for berkeley unix. In USENIX Winter, pages 93--99, 1991.Google Scholar
- L. Layong, X. Gaogang, S. Kave, U. Steve, M. Laurent, and X. Yingke. A trie merging approach with incremental updates for virtual routers. In Proc. IEEE INFOCOM, pages 1222--1230, 2013.Google Scholar
- H. Lim, K. Lim, N. Lee, and K.-H. Park. On adding bloom filters to longest prefix matching algorithms. IEEE Transactions on Computers (TC), 63(2):411--423, 2014. Google ScholarDigital Library
- M. Mahmoud and M. Massato. A new hardware algorithm for fast IP routing targeting programmable routers. In Network control and engineering for Qos, security and mobility II, pages 164--179. Springer, 2003. Google ScholarDigital Library
- W. Marcel, V. George, T. Jon, and P. Bernhard. Scalable high speed IP routing lookups. In Proc. ACM SIGCOMM, 1997. Google ScholarDigital Library
- Z. Marko, R. Luigi, and M. Miljenko. Dxr: towards a billion routing lookups per second in software. ACM SIGCOMM Computer Communication Review, 42(5):29--36, 2012. Google ScholarDigital Library
- B. Masanori and C. H. Jonathan. Flashtrie: hash-based prefix-compressed trie for IP route lookup beyond 100gbps. In Proc. IEEE INFOCOM, 2010. Google ScholarDigital Library
- R. Miguel, B. Ernst, and D. Walid. Survey and taxonomy of IP address lookup algorithms. Network, IEEE, 15(2), 2001. Google ScholarDigital Library
- D. Mikael, B. Andrej, C. Svante, and P. Stephen. Small forwarding tables for fast routing lookups. In Proc. ACM SIGCOMM, pages 3--14, 1997. Google ScholarDigital Library
- A. Mohammad, N. Mehrdad, P. Rina, and S. Samar. A tcam-based parallel architecture for high-speed packet forwarding. IEEE Transactions on Computers, 56(1):58--72, 2007. Google ScholarDigital Library
- NVIDIA Corporation. NVIDIA CUDA C Best Practices Guide, Version 5.0, Oct. 2012.Google Scholar
- C. Pierluigi, D. Leandro, and G. Roberto. IP address lookupmade fast and simple. In Algorithms-ESA'99, pages 65--76. Springer, 1999. Google ScholarDigital Library
- W. Priyank, S. Subhash, and V. George. Multiway range trees: scalable IP lookup with fast updates. Computer Networks, 44(3):289--303, 2004. Google ScholarDigital Library
- S. Rama, F. Natsuhiko, A. Srinivas, and S. Arun. Scalable, memory efficient, high-speed IP lookup algorithms. IEEE/ACM Transactions on Networking, 13(4):802--812, 2005. Google ScholarDigital Library
- P. Rina and S. Samar. Reducing tcam power consumption and increasing throughput. In Proc. High Performance Interconnects, pages 107--112, 2002. Google ScholarDigital Library
- H. Sangjin, J. Keon, P. KyoungSoo, and M. Sue. Packetshader: a gpu-accelerated software router. In Proc. ACM SIGCOMM, pages 195--206, 2010. Google ScholarDigital Library
- D. Sarang, K. Praveen, and T. D. E. Longest prefix matching using bloom filters. In Proc. ACM SIGCOMM, pages 201--212, 2003. Google ScholarDigital Library
- H. Song, M. Kodialam, F. Hao, and T. Lakshman. Building scalable virtual routers with trie braiding. In Proc. IEEE INFOCOM, 2010. Google ScholarDigital Library
- N. Stefan and K. Gunnar. IP-address lookup using lc-tries. Selected Areas in Communications, IEEE Journal on, 17(6):1083--1092, 1999. Google ScholarDigital Library
- S. Venkatachary and V. George. Fast address lookups using controlled prefix expansion. ACM TOCS, 17(1):1--40, 1999. Google ScholarDigital Library
- E. Will, V. George, and D. Zubin. Tree bitmap: hardware/software IP lookups with incremental updates. ACM SIGCOMM Computer Communication Review, 34(2):97--122, 2004. Google ScholarDigital Library
- T. Yang, Z. Mi, R. Duan, X. Guo, J. Lu, S. Zhang, X. Sun, and B. Liu. An ultra-fast universal incremental update algorithm for trie-based routing lookup. In Proc. ACM/IEEE ICNP, 2012. Google ScholarDigital Library
- J. Zhao, X. Zhang, X. Wang, and X. Xue. Achieving O(1) IP lookup on gpu-based software routers. In ACM SIGCOMM Computer Communication Review, volume 40, pages 429--430. ACM, 2010. Google ScholarDigital Library
Index Terms
- Guarantee IP lookup performance with FIB explosion
Recommendations
Guarantee IP lookup performance with FIB explosion
SIGCOMM '14: Proceedings of the 2014 ACM conference on SIGCOMMThe Forwarding Information Base (FIB) of backbone routers has been rapidly growing in size. An ideal IP lookup algorithm should achieve constant, yet small, IP lookup time and on-chip memory usage. However, no prior IP lookup algorithm achieves both ...
Constant IP Lookup With FIB Explosion
With the fast development of Internet, the forwarding tables in backbone routers have been growing fast in size. An ideal IP lookup algorithm should achieve constant, yet small, IP lookup time, and on-chip memory usage. However, no prior IP lookup ...
Achieving O(1) IP lookup on GPU-based software routers
SIGCOMM '10: Proceedings of the ACM SIGCOMM 2010 conferenceIP address lookup is a challenging problem due to the increasing routing table size, and higher line rate. This paper investigates a new way to build an efficient IP lookup scheme using graphics processor units(GPU). Our contribution here is to design a ...
Comments