본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

효율적인 패킷 필터링 시스템을 위한 CRG 알고리즘과 nTCAM
CRG Algorithm and nTCAM for the Efficient Packet Filtering System

김용권   (공주대학교 정보통신공학부UU0000178  ); 이순석   (한국전자통신연구원CC0186800  ); 김영선   (한국전자통신연구원CC0186800  ); 기장근   (공주대학교 정보통신공학부UU0000178  );
  • 초록

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


    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 

 저자의 다른 논문

  • 김용권 (4)

    1. 2002 "통합LAN 구성 방식의 제어 알고리즘에 따른 성능 분석" 전기전자학회논문지 = Journal of IKEEE 6 (1): 1~9    
    2. 2004 "차세대 방 SIP 서버 시험을 위한 성능 지표 및 시험기 구현" 한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스 29 (b4): 411~423    
    3. 2004 "레이저를 이용한 이동차량의 속도/거리 측정용 임베디드 시스템 구현" 전기전자학회논문지 = Journal of IKEEE 8 (1): 108~116    
    4. 2005 "패킷 필터링 시스템에서 범위 규칙의 효율적 TCAM 엔트리 변환 알고리즘 연구" 전기전자학회논문지 = Journal of IKEEE 9 (1): 19~30    
  • 이순석 (15)

  • Kim, Youngsun (27)

  • 기장근 (28)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기