초록

본 논문에서는 TCAM을 이용해 패킷 필터링 시스템을 구현하는 경우 범위 규칙과 부정 규칙을 검색하는데 있어 기존의 방법보다 효율적으로 검색할 수 있는 방안을 제시하였다. 범위 규칙의 경우 그레이코드를 이용한 CRG(Converting Range rules using Gray code) 알고리즘을 제안하였으며, 부정 규칙을 효율적으로 검색하기 위한 방안으로는 nTCAM(TCAM with negation) 구조를 제안하였다. 또한 시뮬레이션을 통해 CRG 알고리즘과 nTCAM의 기능을 검증하였다. 성능 평가를 위해 제안 방안을 SNORT 규칙에 적용시킨 결과 IPv4와 IPv6 환경에서 기존의 방법과 비교할 때 각각 93%와 98%의 TCAM 엔트리를 절감하였다.

Abstract

The general packet filtering system using TCAM has some limitations such as range and negation rules filtering, so this paper proposes efficient searching schemes than existing methods. CRG(Converting Range rules using Gray code) algorithm, in the case of range rules, that takes advantage of the gray code and TCAM characteristics to save a number of TCAM entries is proposed, and a nTCAM(TCAM with negation) architecture for negation rules is proposed, implemented using a FPGA design tool, and verified through the wave simulation. According to the simulation with the SNORT rules, the CRG algorithm and nTCAM save TCAM entries about 93% in IPv4 and 98% in IPv6 than the existing method.

주제어

#Packet Filtering   #TCAM   #Range matching   #Negation matching  

저자의 다른 논문

참고문헌 (24)

1. Paul Francis Tsuchiya, 'A Search Algorithm for Table Entries with Non-eontiguous Wildcarding,' http : //citeseer.ist.psu.edu/tsuchiya91search.html, 1991 
2. Jan van Lunteren, Ton Engbersen, 'Fast and scalable packet classification,' IEEE Journal on Selected Areas in Communications, Vol.21, No.4, pp.560-571, May, 2003 
3. P. Gupta and N. McKeown, 'Packet Oassification Using Hierarchical Intelligent Cuttings,' Proc. Hot Interconnects VII, Aug. 1999; also available in IEEE Micro, Vol.20, No.1, pp.34-41, Jan./Feg., 2000 
4. V. Srinivasan, S. Suri and G. Varghese, 'Packet Classification using Tuple Space Search,' Proc. ACM Sigcomm, pp.135-146, Sept., 1999 
5. H. Che, Y. Wang, and Z. Wang, 'A Rule Grouping Technique for Weight-Based TCAM Coprocessors,' Proc. 11 th Hot Interconnects (HOTI), 2003 
6. Karthik Lakshminarayanan, Anand Rangarajan, Srinivasan Venkatachary, 'Algorithms for Advanced Packet Classification with Ternary CAMs,' SIGCOMM2005, Aug., 2005 
7. Yong Kwon Kim, Jang Geun Ki, Kyou Ho Lee, 'A Novel Scheme for Range Rule Matching in Ternary CAM,' ITC-CSCC 2005, Vol.4, pp. 1427-1428, July, 2005 
8. SNORT, at http://www.snort.org 
9. Myung-Sup Kim, Young J. Won, and James Woo-Ki Hong, 'Application-Level Traffic Monitoring and an Analysis on IP Networks,' ETRI Journal, Vol.27, No.1, pp.22-42, Feb. 2005 
10. Altera, 'Implementing High-Speed Search Appli- cations with Altera CAM,' Application note 119 at http://www.altera.com. July, 2001 
11. T. V. Lakshman and Dimitrios Stiliadis, 'High-speed policy-based packet forwarding using efficient multi-dimensional range matching,' In SIGCOMM, pp.203-214, 1998 
12. A. Natarajan, D. Jasinski, W. Burleson, and R. Tessier, 'A Hybrid Adiabatic Content Addressable Memory for Ultra-Low Power Applications,' in the Proceedings of the IEEE/ACM Great Lakes Symposium on VLSI, Apr., 2003 
13. I.Arsovski and A. Sheikholeslarni, 'A MismatchDependent Power Allocation Technique for MatchLine Sensing in Content-Addressable Memories IEEE Journal of Solid-State Circuits,' Vol.38, No. 11, pp.1958-1966, Nov., 2003 
14. David E. Taylor, Edward W. Spitznagel, 'On using content addressable memory for packet classification,' Technical Report WUCSE-2005-9, Wachington Univ., March 2005 
15. J. Quittek, T. Zseby, B. Claise, S. Zander, 'Requirements for IP Flow Information Export,' IETF IPFIX working group, RFC3917, Oct 2004 
16. Sumeet Singh, Florin Baboescu, George Varghese, and Jia Wang, 'Packet Classification Using Multidimensional Cutting,' Proc. ACM Sigcomm, Aug., 2003 
17. All About Circuits, 'CMOS gate Circuitry,' at http://www.allaboutcircuits.com/vol_4/chpt_3/8.html/cmos_gate_circuitry 
18. V. Srinivasan, George Varghese, Subhash Suri, Marcel Waldvogel, 'Fast and Scalable Layer Four Switching,' Proceedings of ACM SIGCOMM '98, pp.203-214, Sept., 1998 
19. Reto Zimmermann and Wolfgang Fichtner, 'Low-Power Logic Styles: CMOS Versus PassTransistor Logic,' IEEE Journal of Solid-State Circuits, Vol.32, No.7, pp.1079-1090, July, 1997 
20. Florin Baboescu, Sumeet Singh, George Varghese, 'Packet Classification for Core Routers : Is there an alternative to CAMs?,' INFOCOM 2003 
21. Mohanunad J. Akhbarizadeh, Mehrdad Nourani, Cyrus D. Cantrell, 'Segregating the Encompassing Prefixes to Enhance the Performance of Packet Forwarding Engines,' IEEE Communications Society Globecom pp.1612-1616, 2004 
22. Huan Liu, 'Efficient Mapping of Range Classifier into Ternary-CAM,' Proc. 10th Hot Interconnects (HOTI), 2002 
23. V. Srinivasan, G. Varghese, S. Suri, and M. Wald-vogel, 'Fast and scalable layer four switching,' In Proceedings of the ACM SIGCOMM '98, pp.191-202. ACM Press, 1998 
24. Pankaj Gupta and Nick McKeown, 'Packet classification on multiple fields,' In SIGCOMM, pp.147-160, 1999 

이 논문을 인용한 문헌 (0)

1. 이 논문을 인용한 문헌 없음