Efficient IP lookup using hybrid trie-based partitioning of TCAM-based open flow switches

详细信息    查看全文

• 作者：S. Veeramani ; Sk. Noor?Mahammad
• 关键词：IP lookup ; TCAM ; $$x$$ x ; fast trie ; $$y$$ y ; fast trie ; Longest prefix match
• 刊名：Photonic Network Communications
• 出版年：2014
• 出版时间：October 2014
• 年：2014
• 卷：28
• 期：2
• 页码：135-145
• 全文大小：1,210 KB
• 参考文献：1. Akhbarizadeh, Mohammad J., Nourani, M.: Hardware-based IP routing using partitioned lookup table. IEEE/ACM Trans. Netw. (TON) 13(4), 769-81 (2005)
  2. McAuley, A., Francis, P.: Fast routing table lookup using CAMs, INFOCOM 93. In: Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp. 1382-391 (1993)
  3. Gupta, P.: Algorithmic search solutions: Features and benefits. In: Proceedings of NPC-West, San Jose, California (2003)
  4. Wade, J., Sodini, C.: A ternary content addressable search engine. IEEE J. Solid-State Circuits 24, 1003-013 (1989) CrossRef
  5. Kasnavi, S., Gaudet, V., Berube, P., Amaral, J.: A hardware-based longest prefix matching scheme for TCAMs. IEEE Int. Symp. Circuits Syst. (ISCAS-2005) 4, 3339-342 (2005)
  6. Zane, F., Narlikar, G., Basu, A.: CoolCAMs: Power-efficient TCAMs for forwarding engines. In: INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications 1, pp. 42-2 (2003)
  7. Hsiao, Y.-M., Chen, M.-J., Hsiao, Y.-J., Su, H.-K., Chu, Y.-S.: A fast update scheme for TCAM-based IPv6 routing lookup architecture. In: 15th Asia-Pacific Conference on Communications (APCC 2009), pp. 857-61 (2009)
  8. Sun, Y., Liu, H., Kim, M.S.: Using TCAM efficiently for IP route lookup. IEEE International Conference on Consumer Communications and Networking Conference (CCNC), pp. 816-17 (2011)
  9. Waldvogel, M., Varghese, G., Turner, J., Plattner, B.: Scalable high speed IP routing lookups. ACM 27(4), pp. 25-6 (1997)
  10. Yazdani, N., Min, P.S.: Fast and scalable schemes for the IP address lookup problem. In: Proceedings of IEEE Conference on High Performance Switching and Routing, pp. 83-2 (2000)
  11. Lu, H.: Improved Trie partitioning for cooler TCAM. In: Proceedings of International Conference on Advances in Computer Science and Technology (IASTED), pp. 201-12 (2004)
  12. Pao, Derek, Lu, Z., Poon, Y.H.: Bit-shuffled trie: IP lookup with multi-level index tables. In: IEEE International Conference on Communications (ICC), pp. 1- (2011)
  13. http://www.iana.org/assignments/ipv6-multicast-addresses/ipv6-multicast-addresses.xml
  14. Doeringer, W., Karjoth, G., Nassehi, M.: Routing on longest-matching prefixes. IEEE/ACM Trans. Netw. (TON) 4(1), 86-7 (1996) CrossRef
  
• 作者单位：S. Veeramani (1)
  Sk. Noor?Mahammad (1)
  
  1. Department of Computer Science and Engineering, Indian Institute of Information Technology Design and Manufacturing (IIITDM) Kancheepuram, Chennai, 600 127, India
  
• ISSN：1572-8188

文摘

IP forwarding technique in open flow switch can be done by comparing the destination IP address, which is stored in forwarding table with the input IP prefix. Ternary content-addressable memory (TCAM) is one of the popular mechanisms to store and forward IP packet where flow entries are organized in sorted manner. Searching a prefix value in TCAM uses longest prefix match rather than exact match technique. The major drawback of TCAM is high power consumption (12-5 Watts per chip) due to increase in lookup time. The objective of this paper was to reduce the search time of a key, which is stored in the forwarding table. This paper also proposes an efficient way to represent data and to reduce the index TCAM size by using \(y\) -fast trie-partitioning algorithm, and it will take search time complexity of \(O(loglog~n)\) .