맞춤기술찾기

홈으로 가기
맞춤기술찾기
이전대상기술
프린트하기

이전대상기술

다문자 병렬 데이터 스트림에 대한 패턴 매칭 방법 및 장치

  • 기술번호 : KST2015085634
  • 담당센터 : 대전기술혁신센터
  • 전화번호 : 042-610-2279
상담신청 PDF 받기
요약, Int. CL, CPC, 출원번호/일자, 출원인, 등록번호/일자, 공개번호/일자, 공고번호/일자, 국제출원번호/일자, 국제공개번호/일자, 우선권정보, 법적상태, 심사진행상태, 심판사항, 구분, 원출원번호/일자, 관련 출원번호, 기술이전 희망, 심사청구여부/일자, 심사청구항수의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 서지정보 표입니다.
요약 본 발명은 다문자 병렬 데이터 스트림에 대한 패턴 매칭 방법 및 장치에 관한 것이다.본 발명은 데이터가 1 클록에 n-바이트씩 고속으로 처리되는 높은 처리 용량의 통신 네트워크 장비 또는 시스템에서 메모리를 효율적으로 사용할 수 있는 패턴 매칭 방법 및 장치를 통해, 패턴 매칭 장치에 필요한 메모리를 보다 효율적으로 사용할 수 있으며, 문자열 매칭과 정규 패턴 매칭을 분리함으로써 필요한 경우 그 중 한 부분만 확장이 가능해질 수 있다.패턴 매칭, 문자열, 다문자, 병렬, CAM(Content Addressable Memory), 연쇄 회로
Int. CL H04L 29/06 (2014.01) H04L 12/22 (2014.01) G06F 17/00 (2014.01)
CPC H04L 63/1416(2013.01) H04L 63/1416(2013.01) H04L 63/1416(2013.01)
출원번호/일자 1020090079440 (2009.08.26)
출원인 한국전자통신연구원
등록번호/일자 10-1262337-0000 (2013.05.02)
공개번호/일자 10-2010-0062896 (2010.06.10) 문서열기
공고번호/일자 (20130508) 문서열기
국제출원번호/일자
국제공개번호/일자
우선권정보 대한민국  |   1020080121422   |   2008.12.02
법적상태 등록
심사진행상태 수리
심판사항
구분 신규
원출원번호/일자
관련 출원번호
심사청구여부/일자 Y (2009.08.26)
심사청구항수 25

출원인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 출원인 표입니다.
번호 이름 국적 주소
1 한국전자통신연구원 대한민국 대전광역시 유성구

발명자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 발명자 표입니다.
번호 이름 국적 주소
1 김정학 대한민국 대전광역시 유성구
2 최송인 대한민국 대전광역시 유성구
3 안지환 대한민국 대전광역시 유성구

대리인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 대리인 표입니다.
번호 이름 국적 주소
1 팬코리아특허법인 대한민국 서울특별시 강남구 논현로**길 **, 역삼***빌딩 (역삼동)

최종권리자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 최종권리자 표입니다.
번호 이름 국적 주소
1 (주)이지서티 서울특별시 구
번호, 서류명, 접수/발송일자, 처리상태, 접수/발송일자의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 행정처리 표입니다.
번호 서류명 접수/발송일자 처리상태 접수/발송번호
1 [특허출원]특허출원서
[Patent Application] Patent Application		 2009.08.26 수리 (Accepted) 1-1-2009-0524659-26
2 [대리인선임]대리인(대표자)에 관한 신고서
[Appointment of Agent] Report on Agent (Representative)		 2010.09.13 수리 (Accepted) 1-1-2010-0593789-73
3 선행기술조사의뢰서
Request for Prior Art Search		 2012.09.26 수리 (Accepted) 9-1-9999-9999999-89
4 선행기술조사보고서
Report of Prior Art Search		 2012.10.24 수리 (Accepted) 9-1-2012-0079857-90
5 의견제출통지서
Notification of reason for refusal		 2012.11.13 발송처리완료 (Completion of Transmission) 9-5-2012-0682207-15
6 [명세서등 보정]보정서
[Amendment to Description, etc.] Amendment		 2012.12.06 보정승인간주 (Regarded as an acceptance of amendment) 1-1-2012-1015065-38
7 [거절이유 등 통지에 따른 의견]의견(답변, 소명)서
[Opinion according to the Notification of Reasons for Refusal] Written Opinion(Written Reply, Written Substantiation)		 2012.12.06 수리 (Accepted) 1-1-2012-1015177-43
8 등록결정서
Decision to grant		 2013.04.22 발송처리완료 (Completion of Transmission) 9-5-2013-0267848-16
9 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2015.02.02 수리 (Accepted) 4-1-2015-0006137-44
번호, 청구항의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 청구항 표입니다.
번호 청구항
1 1
패턴 매칭 장치의 매턴 매칭 방법에 있어서,연속적으로 입력되는 문자열 스트림 내에 검색하고자 하는 패턴에 포함되는 제1 문자열이 있는지 확인하고, 상기 제1 문자열을 나타내는 문자열 인덱스 및 상기 문자열 인덱스에 대응되는 오프셋 신호를 출력하는 제1 문자열 매칭 단계;상기 제1 문자열을 나타내는 문자열 인덱스들로 구성될 수 있는 제2 문자열이 있는지 확인하고, 상기 제2 문자열을 나타내는 문자열 ID를 출력하는 제2 문자열 매칭 단계;상기 문자열 인덱스를 지연시키는 단계;상기 문자열 ID와 상기 지연시킨 문자열 인덱스를 이용하여 패턴 키를 생성하는 단계; 및생성한 상기 패턴 키들로 구성될 수 있는 정규 표현들 중에 검색하고자 하는 상기 패턴을 나타내는 정규 표현을 검출하는 단계를 포함하는 패턴 매칭 방법
2 2
제1항에 있어서,상기 패턴 매칭 장치는 복수의 엔트리에 검색하고자 하는 제1 문자열이 각각 컨텐트로 저장되어 있는 복수의 CAM(Content Addressable Memory)을 포함하며,상기 제1 문자열 매칭 단계는,상기 연속적으로 입력되는 제1 문자열들 사이의 시간 간격만큼, 상기 문자열 스트림을 지연시키는 단계;지연된 상기 문자열 스트림을 상위로 하고, 새로 입력되는 문자열 스트림을 하위로 하는 제3 문자열 스트림을 생성하는 단계;상기 제3 문자열 스트림을 상기 복수의 CAM에 각각 분배하여 제4 문자열 스트림을 출력하는 단계;상기 출력된 제4 문자열 스트림 내에 상기 제1 문자열에 해당하는 문자열이 있는지 검색하는 단계;상기 복수의 엔트리 중 상기 제1 문자열과 일치하는 문자열이 저장되어 있는 엔트리에 해당하는 히트 신호와 상기 문자열 인덱스를 발생시키는 단계; 및상기 히트 신호를 발생시킨 엔트리에 대한 문자열 인덱스 및 오프셋 신호를 출력하는 단계를 포함하는 패턴 매칭 방법
3 3
제2항에 있어서,상기 문자열 인덱스를 발생시키는 단계는,복수의 CAM에서 출력되는 복수의 히트 신호가 동시에 발생된 경우, 상기 복수의 히트 신호가 발생되기 바로 전에 검출된 제1 문자열에 대한 히트 신호를 발생시킨 CAM과 동일한 CAM에서 출력되는 히트 신호를 선택하여 출력하는 패턴 매칭 방법
4 4
제1항에 있어서,상기 패턴 매칭 장치는 복수의 엔트리에 문자열 인덱스 및 오프셋 신호를 각각 컨텐트로 저장하고 있는 CAM(Content Addressable Memory)을 포함하며, 상기 제2 문자열 매칭 단계는,상기 제1 문자열 매칭 단계에서 출력된 문자열 인덱스와 오프셋 신호가 입력되면, 상기 CAM에 포함된 복수의 엔트리에 각각 저장되어 있는 컨텐트들과 상기 입력된 문자열 인덱스 및 오프셋 신호를 비교하는 단계;상기 컨텐트들과 상기 입력된 문자열 인덱스 및 오프셋 신호 중 일치되는 엔트리가 존재하면, 상기 일치되는 엔트리에 해당하는 히트 신호를 발생하는 단계;상기 히트 신호들을 조합하여 상기 검색하고자 하는 패턴에 포함되는 상기 제2 문자열이 검출되었음을 알리는 검출 신호를 발생하는 단계; 및상기 검출 신호에 대응하는 인덱스를 포함하는 상기 문자열 ID를 출력하는 단계를 포함하는 패턴 매칭 방법
5 5
제4항에 있어서,상기 문자열 ID를 출력하는 단계는,상기 검출 신호가 발생하면, 상기 인덱스를 문자열 ID 형태로 변환하는 단계를 더 포함하는 패턴 매칭 방법
6 6
제1항에 있어서,상기 패턴 키를 생성하는 단계는,상기 제2 문자열이 검출되면, 상기 제2 문자열이 검출되었음을 알리는 검출 신호와 상기 검출한 제2 문자열에 해당되는 문자열 ID를 상기 패턴 키로 생성하는 단계; 및상기 제2 문자열이 검출되지 않으면, 상기 지연시킨 문자열 인덱스를 상기 패턴 키로서 생성하는 단계를 포함하는 패턴 매칭 방법
7 7
제1항에 있어서,상기 패턴 매칭 장치는 복수의 엔트리에 각각 패턴 키와 상태 변수를 컨텐트로 저장하고 있는 CAM을 포함하며,상기 정규 표현을 검출하는 단계는,상기 CAM에서 히트 신호가 발생되면, 상기 히트 신호에 따른 인덱스에 대응되는 상태 변수를 생성하고, 상기 인덱스에 대응되는 실행 정보를 출력하는 상태 천이 단계를 더 포함하는 패턴 매칭 방법
8 8
제7항에 있어서,상기 정규 표현을 검출하는 단계는,상기 상태 천이 단계를 통해 생성된 상태 변수와 상기 생성한 패턴 키가 입력되면 상기 복수의 엔트리에 저장되어 있는 컨텐트들과 비교하는 단계; 및상기 복수의 엔트리와 일치하는 상기 생성한 패턴 키가 존재하면, 일치하는 엔트리에 해당하는 히트 신호 및 상기 일치하는 엔트리에 대한 인덱스를 출력하는 단계를 포함하는 패턴 매칭 방법
9 9
제1항에 있어서,상기 패턴 매칭 장치는 복수의 엔트리에 패턴 키를 각각 컨텐트로 저장하고 있는 복수의 CAM을 포함하며,상기 정규 표현을 검출하는 단계는,상기 생성한 패턴 키가 입력되면, 상기 복수의 엔트리에 저장되어 있는 컨텐트 중 상기 패턴 키와 일치하는 컨텐트에 대한 엔트리가 존재하는지 판단하는 단계;일치하는 엔트리가 존재하면, 상기 일치하는 엔트리에 해당하는 히트 신호를 발생하는 단계;상기 복수의 엔트리에서 순차적으로 출력되는 히트 신호들을 조합하여, 상기 패턴이 검출되었음을 알리는 검출 신호를 발생하는 단계; 상기 검출 신호에 대응되는 인덱스를 발생하는 단계; 및상기 인덱스에 대응되는 실행 정보를 출력하는 단계를 포함하는 패턴 매칭 방법
10 10
제2항에 있어서,상기 연속적으로 입력되는 문자열 스트림, 제1 문자열, 제3 문자열 스트림 및 제4 문자열 스트림은 1 클록에 2바이트 이상씩 처리되는 패턴 매칭 방법
11 11
패턴 매칭 장치에 있어서,연속적으로 입력되는 문자열 스트림 내에 검색하고자 하는 패턴에 포함되는 제1 문자열이 있는지 확인하고, 상기 제1 문자열을 나타내는 문자열 인덱스 및 상기 제1 문자열 인덱스에 대응되는 오프셋 신호를 출력하는 제1 문자열 매칭부;상기 제1 문자열 매칭부로부터 출력되는 오프셋 신호 및 문자열 인덱스를 이용하여 상기 제1 문자열을 나타내는 문자열 인덱스들로 구성되는 제2 문자열이 있는지 확인하고, 상기 제2 문자열을 나타내는 문자열 ID를 출력하는 제2 문자열 매칭부;상기 문자열 인덱스를 지연시키는 지연부;상기 제2 문자열 매칭부에서 출력한 상기 문자열 ID와 상기 지연부에서 지연시킨 상기 문자열 인덱스를 이용하여 패턴 키를 생성하는 키 발생부; 및상기 키 발생부에서 생성한 상기 패턴 키들로 구성될 수 있는 정규 표현들 중에 검색하고자 하는 상기 패턴을 나타내는 정규 표현을 검출하는 정규 표현 매칭부를 포함하는 패턴 매칭 장치
12 12
제11항에 있어서,상기 제1 문자열 매칭부는,상기 연속적으로 입력되는 제1 문자열들 사이의 시간 간격만큼 상기 문자열 스트림을 지연시키는 지연기;상기 지연된 문자열 스트림을 상위로, 새로 입력되는 문자열 스트림을 하위로 하는 제3 문자열 스트림을 생성하고, 상기 생성한 제3 문자열 스트림을 분배하여 제4 문자열 스트림을 출력하는 분배기;상기 제1 문자열이 컨텐트로서 각각 저장되어 있는 복수의 엔트리를 포함하며, 상기 분배기로부터 분배되어 출력되는 제4 문자열 스트림과 상기 복수의 엔트리에 저장되어 있는 복수의 컨텐트를 비교하여 일치되는 엔트리에 해당하는 히트 신호 및 인덱스를 발생하는 복수의 CAM; 및상기 복수의 CAM에서 출력되는 인덱스들 중 우선 순위가 높은 인덱스 신호를 문자열 인덱스로 출력하고, 히트 신호들 중 우선 순위가 높은 히트 신호에 대한 오프셋 신호를 출력하는 오프셋 검사기를 포함하는 패턴 매칭 장치
13 13
제11항에 있어서,상기 제2 문자열 매칭부는,문자열 인덱스와 오프셋 신호가 컨텐트로서 각각 저장되어 있는 복수의 엔트리를 포함하며, 상기 제1 문자열 매칭부로부터 출력되는 상기 오프셋 신호 및 문자열 인덱스와 상기 복수의 엔트리에 저장되어 있는 복수의 컨텐트를 비교하여 일치되는 엔트리에 해당하는 히트 신호를 발생하는 CAM;상기 CAM으로부터 상기 히트 신호가 발생되면 상기 히트 신호를 조합하여 상기 제2 문자열이 검출되었음을 알리는 검출 신호를 발생하는 연쇄기; 및상기 연쇄기로부터 출력되는 인덱스를 문자열 ID로 변환하는 인덱스 변환기를 포함하는 패턴 매칭 장치
14 14
제13항에 있어서,상기 연쇄기는,상기 문자열 인덱스에 대응되는 히트 신호들이 입력되는 복수의 제1 입력 단자, 그리고 상기 검출 신호를 출력하는 제1 출력 단자를 가지는 복수의 연쇄 회로를 포함하는 패턴 매칭 장치
15 15
제14항에 있어서,상기 복수의 연쇄 회로는제2 입력 단자, 그리고 제2 출력 단자를 가지는 복수의 플립플롭; 및제3 및 제4 입력 단자, 그리고 제3 출력 단자를 가지는 복수의 논리곱 게이트를 포함하며,각 플립플롭의 제2 출력 단자가 각 논리곱 게이트의 제3 입력 단자에 연결되어 있고, 복수의 논리곱 게이트 중 마지막에 위치하는 논리곱 게이트를 제외한 나머지 논리곱 게이트의 제3 출력 단자가 상기 복수의 플립플롭 중 맨 앞에 위치하는 플립플롭을 제외한 나머지 플립플롭의 제2 입력 단자에 연결되어 있으며,상기 마지막에 위치하는 논리곱 게이트의 제3 출력 단자가 상기 제1 출력 단자를 형성하며, 상기 맨 앞에 위치하는 플립플롭의 제2 입력 단자와 상기 각 논리곱게이트의 제4 입력 단자가 각각 상기 복수의 제1 입력 단자를 형성하는 패턴 매칭 장치
16 16
제13항에 있어서,상기 연쇄기는,검색하고자 하는 제2 문자열에 각각 대응하는 복수의 연쇄 회로를 포함하고,각 연쇄 회로는,각각 제1 및 제2 입력 단자, 제1 및 제2 출력 단자, 그리고 제어 단자를 가지는 복수의 스테이지를 포함하며,각 스테이지의 상기 제1 입력 단자는 인접한 스테이지의 상기 제2 출력 단자에 연결되어 있으며,각 스테이지의 상기 제2 입력 단자는 검색하고자 하는 제2 문자열에 포함되는 각 문자열 인덱스에 대응하는 히트 신호를 입력받고, 상기 제어 단자는 제어 신호를 입력받으며, 상기 제1 출력 단자는 상기 검출 신호를 출력하며,상기 제어 신호에 의해 인접한 스테이지가 분리되는 패턴 매칭 장치
17 17
제16항에 있어서,각 스테이지는,상기 제1 및 제2 입력 단자로 입력되는 데이터를 논리곱 연산하여 출력 단자로 출력하는 논리곱 게이트;상기 논리곱 게이트의 출력 단자와 연결되어 있는 입력 단자, 그리고 출력 단자를 가지는 플립플롭;제1 데이터가 입력되는 제3 입력 단자, 상기 논리곱 게이트의 출력 단자와 연결되어 있는 제4 입력 단자, 그리고 상기 제1 출력 단자를 형성하는 제3 출력 단자를 가지는 제1 멀티플렉서; 및상기 플립플롭의 출력 단자에 연결되어 있는 제5 입력 단자, 제2 데이터가 입력되는 제6 입력 단자, 그리고 상기 제2 출력 단자를 형성하는 제4 출력 단자를 가지는 제2 멀티플렉서를 포함하는 패턴 매칭 장치
18 18
제16항에 있어서,상기 제어 신호에 의해 먼저 저장된 제2 문자열에 포함되는 마지막 문자열 인덱스와 다음 저장된 제2 문자열에 포함되는 첫 번째 문자열 인덱스 사이의 경계가 구분되는 패턴 매칭 장치
19 19
제11항에 있어서,상기 정규 표현 매칭부는,패턴 키와 상태 변수가 컨텐트로서 각각 저장되어 있는 복수의 엔트리를 포함하며, 상기 키 발생부에서 생성된 패턴 키와 상태 천이기에서 출력된 상태 변수가 입력되면, 상기 입력된 패턴 키 및 상태 변수를 복수의 엔트리에 저장되어 있는 컨텐트들과 비교하여 일치되는 엔트리에 해당하는 히트 신호를 발생시키고, 상기 히트 신호를 발생시킨 엔트리에 대응하는 인덱스를 출력하는 CAM; 및복수의 엔트리의 각 인덱스에 대응하는 상태 변수가 저장되어 있으며, 상기 CAM으로부터 출력된 인덱스에 대응하는 상태 변수를 상기 CAM으로 출력하는 상태 천이기를 포함하는 패턴 매칭 장치
20 20
제19항에 있어서,상기 상태 천이기는 상기 각 인덱스 중 특정 인덱스에 대응하는 실행 정보를 출력하며, 상기 실행 정보는 상기 패턴의 검출을 알리는 히트 신호를 포함하는 패턴 매칭 장치
21 21
제11항에 있어서,상기 정규 표현 매칭부는,패턴 키가 컨텐츠로서 각각 저장되어 있는 복수의 엔트리를 포함하며, 상기 키 발생부에서 생성된 패턴 키가 입력되면, 상기 패턴 키와 복수의 엔트리에 저장되어 있는 컨텐트들을 비교하여 일치되는 엔트리에 해당하는 히트 신호를 출력하는 CAM;상기 복수의 엔트리에서 순차적으로 출력되는 히트 신호를 조합하여 상기 패턴의 검출을 알리는 검출 신호를 발생시키며, 상기 검출 신호에 대응하는 인덱스를 출력하는 연쇄기; 및상기 인덱스에 대응하는 실행 정보를 출력하는 메모리부를 포함하는 패턴 매칭 장치
22 22
제21항에 있어서,상기 연쇄기는,상기 패턴에 포함되는 제2 문자열에 대응하는 히트 신호가 입력되는 복수의 제1 입력 단자, 그리고 상기 검출 신호를 출력하는 제1 출력 단자를 가지는 복수의 연쇄 회로를 포함하며, 각 연쇄 회로는,제2 입력 단자, 그리고 제2 출력 단자를 가지는 복수의 래치, 그리고제3 및 제4 입력 단자, 그리고 제3 출력 단자를 가지는 복수의 논리곱 게이트를 포함하며,각 래치의 제2 출력 단자가 각 논리 게이트의 제3 입력 단자에 연결되어 있고, 복수의 논리 게이트 중 마지막에 위치하는 논리곱 게이트를 제외한 나머지 논리곱 게이트의 제3 출력 단자가 상기 복수의 래치 중 맨 앞에 위치하는 래치를 제외한 나머지 래치의 제2 입력 단자에 연결되어 있으며,상기 마지막에 위치하는 논리곱 게이트의 제3 출력 단자가 상기 제1 출력 단자를 형성하며, 상기 맨 앞에 위치하는 래치의 제2 입력 단자와 상기 각 논리곱 게이트의 제4 입력 단자가 각각 상기 복수의 제1 입력 단자를 형성하는 패턴 매칭 장치
23 23
제21항에 있어서,상기 연쇄기는,상기 패턴에 각각 대응하는 복수의 연쇄 회로를 포함하고,각 연쇄 회로는,각각 제1 및 제2 입력 단자, 제1 및 제2 출력 단자, 그리고 제어 단자를 가지는 복수의 스테이지를 포함하며,각 스테이지의 상기 제1 입력 단자는 인접한 스테이지의 상기 제2 출력 단자에 연결되어 있으며,각 스테이지의 상기 제2 입력 단자는 상기 문자열 검출부에서 검출한 문자열에 대응하는 히트 신호를 입력 받고, 상기 제어 단자는 제어 신호를 입력 받으며, 상기 제1 출력 단자는 상기 검출 신호를 출력하며,상기 제어 신호에 의해 인접한 스테이지가 분리되는 패턴 매칭 장치
24 24
제23항에 있어서,상기 각 스테이지는,상기 제1 및 제2 입력 단자로 입력되는 데이터를 논리곱 연산하여 출력 단자로 출력하는 논리곱 게이트;상기 논리곱 게이트의 출력 단자와 연결되어 있는 입력 단자, 그리고 출력 단자를 가지는 래치;제1 데이터가 입력되는 제3 입력 단자, 상기 논리곱 게이트의 출력 단자와 연결되어 있는 제4 입력 단자, 그리고 상기 제1 출력 단자를 형성하는 제3 출력 단자를 가지는 제1 멀티플렉서; 및상기 래치의 출력 단자에 연결되어 있는 제5 입력 단자, 제2 데이터가 입력되는 제6 입력 단자, 그리고 상기 제2 출력 단자를 형성하는 제4 출력 단자를 가지는 제2 멀티플렉서를 포함하는 패턴 매칭 장치
25 25
제22항에 있어서,상기 래치는,두 입력 단자 및 출력 단자를 가지는 제3 멀티플렉서; 및상기 제3 멀티플렉서의 출력 단자에 연결되어 있는 입력 단자 및 상기 제3 멀티플렉서의 두 입력 단자 중 하나의 입력 단자에 연결되어 있는 출력 단자를 가지는 플립플롭을 포함하며,상기 제3 멀티플렉서의 두 입력 단자 중 다른 하나의 입력 단자가 상기 래치의 입력 단자를 형성하는 패턴 매칭 장치
지정국 정보가 없습니다
패밀리정보가 없습니다
순번, 연구부처, 주관기관, 연구사업, 연구과제의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 국가R&D 연구정보 정보 표입니다.
순번 연구부처 주관기관 연구사업 연구과제
1 지식경제부 한국전자통신연구원 IT성장동력기술개발 WiBro 네트워크 신뢰성 확보 및 위치 인식 기술 개발