KR101582050B1

KR101582050B1 - Apparatus and method for searching name using bloom filter pre-searching

Info

Publication number: KR101582050B1
Application number: KR1020140145334A
Authority: KR
Inventors: 임혜숙; 심미란
Original assignee: 이화여자대학교 산학협력단
Priority date: 2014-10-24
Filing date: 2014-10-24
Publication date: 2015-12-31
Anticipated expiration: 2034-10-24

Abstract

블룸 필터 선-검색을 이용한 이름 검색 장치 및 방법이 개시된다.
복수의 레벨로 구성된 이름 프리픽스 트리(Name Prefix Trie: NPT)를 이용한 이름 검색 방법은 NPT의 레벨들 별로 생성된 블룸 필터로 콘텐츠 이름을 검색하는 단계; 및 상기 블룸 필터의 검색 결과에 기초하여 상기 블룸 필터에 대응하는 해시 테이블에서 상기 콘텐츠 이름을 검색하는 단계를 포함할 수 있다.A name searching apparatus and method using Bloom filter line-search are disclosed.
A name search method using a name prefix trie (NPT) composed of a plurality of levels includes: searching for a content name using a bloom filter generated for each level of the NPT; And retrieving the content name from the hash table corresponding to the Bloom filter based on the search result of the Bloom filter.

Description

[0001] APPARATUS AND METHOD FOR SEARCHING NAME USING BLOOM FILTER PRE-SEARCHING [0002]

본 발명은 이름 검색 장치 및 방법에 관한 것으로, 보다 상세하게는 콘텐츠 중심 네트워킹 기술에서 콘텐츠 이름을 검색하는 장치 및 방법에 관한 것이다. BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a name search apparatus and method, and more particularly, to an apparatus and method for searching for a content name in a content-oriented networking technology.

미래 인터넷으로 최근 각광 받고 있는 콘텐츠 중심 네트워킹(Content Centric Networking, CCN) 기술은 콘텐츠 중심의 전송 방식을 제공함으로써 대용량 정보를 빠르고 효율적으로 전송하고자 하는 기술이다. Recently, Content Centric Networking (CCN) technology, which is being watched for the future of the Internet, is a technology for quickly and efficiently transmitting large amount of information by providing a content-oriented transmission method.

CCN은 송수신자라는 개념 대신 정보를 생성한 콘텐츠 생성자와 정보를 수신하여 소비하는 콘텐츠 소비자의 개념을 도입하였고, 라우터는 IP 주소 대신 콘텐츠 이름을 사용하여 라우팅을 수행할 수 있다. 이때, CCN 라우터는 네트워크상에서 정보를 일시 저장하는 캐시 역할을 수행하며, 콘텐츠를 저장하고 있다가 콘텐츠를 요구하는 인근의 새로운 소비자들에게 콘텐츠를 배포할 수 있다. CCN introduces the concept of a content creator that generates information instead of a sender / receiver, and a content consumer that consumes and consumes information, and routers can perform routing using content names instead of IP addresses. At this time, the CCN router serves as a cache for temporarily storing information on the network, and can distribute the content to nearby new consumers who are requesting the contents while storing the contents.

즉, CCN 라우터가 캐시 역할까지 수행함으로써, CCN은 소비자들에게 빠른 서비스를 제공할 수 있으며 동일한 콘텐츠가 네트워크 상에서 반복적으로 전송되는 횟수를 줄일 수 있다. In other words, the CCN router can also serve as a cache, so that the CCN can provide fast service to consumers and reduce the number of times the same content is repeatedly transmitted over the network.

그리고, CCN 라우터는 콘텐츠 전송을 위하여 CS(Contents Store), PIT(Pending Interest Table), FIB(Forwarding Information Base)의 3종류의 테이블을 사용할 수 있다. 이때, CS는 콘텐츠를 저장하는 캐시이고, PIT는 요청 받은 콘텐츠 중에서 소비자에게 제공하지 못한 콘텐츠들의 리스트이며, FIB는 소비자의 콘텐츠 요청 패킷을 전달해야 하는 출력 인터페이스(output interface) 리스트일 수 있다. 그리고, PIT와 FIB를 검색할 때에는 콘텐츠 이름과 가장 길게 일치하는 엔트리를 찾아야 하며, 선속도로 수행되어야 하므로 콘텐츠 이름을 빠른 속도로 검색할 수 있는 방법이 요청되고 있다.The CCN router can use three kinds of tables for content transmission: a contents store (CS), a pending interest table (PIT), and a forwarding information base (FIB). In this case, the CS is a cache for storing content, the PIT is a list of contents requested by the consumer, and the FIB may be a list of output interfaces through which a content request packet of a consumer should be transmitted. When retrieving PIT and FIB, it is required to find an entry having the longest match with the content name, and a method of searching the content name at a high speed is required because it must be performed at a linear speed.

본 발명은 해시 테이블을 이용하여 NPT에 기초한 콘텐츠 이름을 검색할 수 있는 장치 및 방법을 제공할 수 있다.The present invention can provide an apparatus and method for retrieving a content name based on NPT using a hash table.

또한, 본 발명은 블룸 필터의 검색 결과에 따라 해시 테이블의 검색 여부를 결정함으로써, 해시 테이블의 접근 회수를 감소시켜 검색 속도를 향상 시킬 수 있는 장치 및 방법을 제공할 수 있다.In addition, the present invention can provide an apparatus and method for improving the retrieval speed by decreasing the number of hash table accesses by determining whether or not to search the hash table according to the search result of the Bloom filter.

그리고, 본 발명은 NPT의 레벨 별로 생성된 블룸 필터를 연속으로 검색하여 최종 레벨을 검색하고, 최종 레벨의 해시 테이블을 검색함으로써, 해시 테이블의 접근 회수를 최소화시킬 수도 있는 장치 및 방법을 제공할 수 있다.The present invention can provide an apparatus and method for minimizing the number of hash table accesses by continuously searching for the bloom filter generated for each level of NPT, searching for the final level, and retrieving the hash table of the final level have.

본 발명의 일실시예에 따른 이름 검색 방법은 해시 함수를 사용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환하는 단계; 및 NPT의 레벨들 별로 생성된 해시 테이블에서 상기 해시 함수를 사용하여 변환된 컴포넌트를 검색하는 단계를 포함할 수 있다.A method for searching for a name according to an embodiment of the present invention includes converting a component of a content name corresponding to each level of NPT using a hash function; And retrieving the transformed component using the hash function in a hash table generated for each level of the NPT.

본 발명의 일실시예에 따른 이름 검색 방법의 컴포넌트를 변환하는 단계는 NPT의 레벨들 별로 생성된 해시 테이블에서 해시 인덱스의 생성에 이용된 해시 함수를 이용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환할 수 있다.The step of converting a component of the name search method according to an exemplary embodiment of the present invention includes converting a content name corresponding to each level of the NPT using a hash function used for generating a hash index in a hash table generated for each level of the NPT Can be converted.

본 발명의 일실시예에 따른 이름 검색 방법의 컴포넌트를 변환하는 단계는 NPT의 레벨이 두 번째 레벨 이상인 경우, 해시 함수를 사용하여 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 콘텐츠 이름의 컴포넌트가 연속된 문자열을 변환할 수 있다.In the step of converting a component of the name search method according to an exemplary embodiment of the present invention, when the level of the NPT is equal to or higher than the second level, a component of the content name corresponding to the previous level and a content name Can convert a contiguous string.

본 발명의 일실시예에 따른 이름 검색 방법의 컴포넌트를 검색하는 단계는 현재 레벨에 대응하는 해시 테이블에서 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 콘텐츠 이름의 컴포넌트가 연속된 문자열이 해시 함수로 변환된 해시 인덱스를 검색할 수 있다.The searching of the component of the name search method according to an embodiment of the present invention may include searching for a component of the content name corresponding to the previous level and a string of the content of the content name corresponding to the current level in the hash table corresponding to the current level You can search for a hash index that has been converted to a hash function.

본 발명의 일실시예에 따른 이름 검색 방법은 현재 레벨에 대응하는 해시 테이블에서 상기 해시 함수를 사용하여 변환된 컴포넌트가 검색되지 않는 경우, 이전 레벨의 해시 태이블에 포함된 마지막으로 검색된 출력 페이스로 상기 콘텐츠 이름에 대응하는 콘텐츠 요청 패킷을 전송하는 단계를 더 포함할 수 있다.The name search method according to an embodiment of the present invention is a method in which when a component that is transformed using the hash function in the hash table corresponding to the current level is not searched, And transmitting a content request packet corresponding to the content name.

본 발명의 일실시예에 따른 이름 검색 방법은 NPT의 레벨들 별로 생성된 블룸 필터로 콘텐츠 이름을 검색하는 단계; 및 상기 블룸 필터의 검색 결과에 기초하여 상기 블룸 필터에 대응하는 해시 테이블에서 상기 콘텐츠 이름을 검색하는 단계를 포함할 수 있다.A method for searching for names according to an exemplary embodiment of the present invention includes searching for a content name using a bloom filter generated for each level of NPT; And retrieving the content name from the hash table corresponding to the Bloom filter based on the search result of the Bloom filter.

본 발명의 일실시예에 따른 이름 검색 방법의 블룸 필터로 콘텐츠 이름을 검색하는 단계는, NPT의 현재 레벨의 블룸 필터에 대응하는 해시 테이블에서 상기 콘텐츠 이름이 검색되는 경우, NPT의 다음 레벨의 블룸 필터로 콘텐츠 이름을 검색할 수 있다.The step of searching for a content name using a Bloom filter of a name search method according to an exemplary embodiment of the present invention may include searching for a content name in a hash table corresponding to a Bloom filter of a current level of NPT, You can search for content names with filters.

본 발명의 일실시예에 따른 이름 검색 방법의 해시 테이블에서 상기 콘텐츠 이름을 검색하는 단계는 상기 블룸 필터의 검색 결과가 양성인 경우, 상기 블룸 필터에 대응하는 해시 테이블에서 상기 콘텐츠 이름을 검색하는 단계; 및 상기 블룸 필터의 검색 결과가 음성이거나, 상기 해시 테이블에서 상기 콘텐츠 이름이 검색되지 않는 경우, 검색을 종료하는 단계를 포함할 수 있다.The searching of the content name in the hash table of the name search method according to an exemplary embodiment of the present invention may include searching for the content name in the hash table corresponding to the Bloom filter when the search result of the Bloom filter is positive. And terminating the search if the search result of the Bloom filter is negative or the content name is not found in the hash table.

본 발명의 일실시예에 따른 이름 검색 방법의 검색을 종료하는 단계는 콘텐츠 이름이 마지막으로 검색된 해시 테이블에 포함된 출력 페이스로 상기 콘텐츠 이름에 대응하는 콘텐츠 요청 패킷을 전송할 수 있다.In the step of terminating the search of the name search method according to an embodiment of the present invention, the content request packet corresponding to the content name may be transmitted at an output face included in the hash table in which the content name was last searched.

본 발명의 일실시예에 따른 이름 검색 방법의 블룸 필터는 상기 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 컴포넌트가 연속된 문자열을 포함할 수 있다.The bloom filter of the name search method according to an embodiment of the present invention may include a string of a component corresponding to the previous level and a string corresponding to a component corresponding to the current level.

본 발명의 일실시예에 따른 이름 검색 방법은 NPT의 레벨들 별로 생성된 블룸 필터들에서 콘텐츠 이름을 연쇄적으로 검색하는 단계; 및 상기 블룸 필터들의 검색 결과에 따른 해시 테이블에서 상기 콘텐츠 이름을 검색하는 단계를 포함할 수 있다.A method for searching for names according to an embodiment of the present invention includes searching for a content name categorically in bloom filters generated for each level of NPT; And retrieving the content name from a hash table according to a search result of the Bloom filters.

본 발명의 일실시예에 따른 이름 검색 방법의 콘텐츠 이름을 연쇄적으로 검색하는 단계는, NPT의 현재 레벨에 대응하는 블룸 필터로 콘텐츠 이름에 포함된 컴포넌트를 검색하는 단계; 상기 블룸 필터의 검색 결과가 양성인 경우, NPT의 다음 레벨의 블룸 필터로 콘텐츠 이름에 포함된 컴포넌트를 검색하는 단계; 및 상기 블룸 필터의 검색 결과가 음성이거나, 현재 레벨이 NPT의 마지막 레벨인 경우, 콘텐츠 이름의 연쇄 검색을 종료하는 단계를 포함할 수 있다.The step of searching for a content name cascade of a name search method according to an exemplary embodiment of the present invention includes searching for a component included in a content name with a bloom filter corresponding to a current level of the NPT; If the search result of the Bloom filter is positive, searching for a component included in the content name with a Bloom filter of the next level of the NPT; And terminating the cascade search of the content name if the search result of the Bloom filter is voice or the current level is the last level of the NPT.

본 발명의 일실시예에 따른 이름 검색 방법의 해시 테이블에서 상기 콘텐츠 이름을 검색하는 단계는, 상기 블룸 필터의 검색 결과가 음성인 경우, 이전 레벨의 블룸 필터에 대응하는 해시 테이블에서 상기 콘텐츠 이름을 검색할 수 있다.The searching of the content name in the hash table of the name search method according to an embodiment of the present invention may include searching the hash table corresponding to the bloom filter of the previous level, You can search.

본 발명의 일실시예에 따른 이름 검색 방법의 해시 테이블에서 상기 콘텐츠 이름을 검색하는 단계는, 블룸 필터의 검색 결과가 양성이며, 현재 레벨이 NPT의 마지막 레벨인 경우, 현재 레벨의 블룸 필터에 대응하는 해시 테이블에서 상기 콘텐츠 이름을 검색할 수 있다.The step of searching for the content name in the hash table of the name search method according to an embodiment of the present invention may include searching for a content name corresponding to the current level of Bloom filter when the search result of the Bloom filter is positive and the current level is the last level of NPT The content name can be retrieved from the hash table.

본 발명의 일실시예에 따른 이름 검색 방법의 해시 테이블에서 상기 콘텐츠 이름을 검색하는 단계는, 블룸 필터들의 검색 결과에 따른 해시 테이블에서 콘텐츠 이름이 검색되지 않는 경우, 이전 레벨의 블룸 필터에 대응하는 해시 테이블에서 상기 콘텐츠 이름을 검색할 수 있다.The searching of the content name in the hash table of the name search method according to an embodiment of the present invention may include searching for a content name in the hash table corresponding to the previous level Bloom filter The content name can be retrieved from the hash table.

본 발명의 일실시예에 의하면, 해시 테이블을 이용하여 NPT에 기초한 콘텐츠 이름을 검색할 수 있다. According to an embodiment of the present invention, a hash table can be used to retrieve the NPT-based content name.

또한, 본 발명의 일실시예에 의하면, 블룸 필터의 검색 결과에 따라 해시 테이블의 검색 여부를 결정함으로써, 해시 테이블의 접근 회수를 감소시켜 검색 속도를 향상 시킬 수 있다.According to an embodiment of the present invention, it is possible to improve the retrieval speed by decreasing the number of hash table accesses by determining whether or not to search the hash table according to the search result of the Bloom filter.

그리고, 본 발명의 일실시예에 의하면, NPT의 레벨 별로 생성된 블룸 필터를 연속으로 검색하여 최종 레벨을 검색하고, 최종 레벨의 해시 테이블을 검색함으로써, 해시 테이블의 접근 회수를 최소화시킬 수도 있다.According to an embodiment of the present invention, the number of accesses to the hash table can be minimized by continuously searching for the bloom filter generated for each level of the NPT, searching for the final level, and searching the hash table of the final level.

도 1은 본 발명의 일실시예에 따른 이름 검색 시스템을 나타내는 도면이다.
도 2는 본 발명의 일실시예에 따른 NPT의 일례이다.
도 3은 본 발명의 일실시예에 따른 이름 검색 정보 구축 과정에서 사용하는 코드의 일례이다.
도 4는 본 발명의 일실시예에 따른 블룸 필터 정보 구축 과정에서 사용하는 의사 코드의 일례이다.
도 5는 본 발명의 제1 실시예에 따른 이름 검색 장치를 나타내는 도면이다.
도 6은 본 발명의 제1 실시예에 따라 구축한 이름 검색 정보의 일례이다.
도 7은 본 발명의 제1 실시예에 따른 이름 검색 과정에서 사용하는 의사 코드의 일례이다.
도 8은 본 발명의 제2 실시예에 따른 이름 검색 장치를 나타내는 도면이다.
도 9는 본 발명의 제2 실시예에 따라 구축한 이름 검색 정보의 일례이다.
도 10은 본 발명의 일실시예에 따른 블룸 필터가 콘텐츠 이름 검색 과정에서 사용하는 코드의 일례이다.
도 11은 본 발명의 제2 실시예에 따른 이름 검색 과정에서 사용하는 의사 코드의 일례이다.
도 12는 본 발명의 제3 실시예에 따른 이름 검색 장치를 나타내는 도면이다.
도 13은 본 발명의 제3 실시예에 따른 이름 검색 과정에서 사용하는 의사 코드의 일례이다.
도 14는 본 발명의 일실시예에 따른 이름 검색 과정에서 해시 테이블에 접근한 회수의 일례이다.
도 15는 본 발명의 일실시예에 따른 이름 검색 과정에서 해시 테이블의 메모리 요구량의 일례이다.
도 16은 본 발명의 제1 실시예에 따른 이름 검색 방법을 도시한 플로우차트이다.
도 17은 본 발명의 제2 실시예에 따른 이름 검색 방법을 도시한 플로우차트이다.
도 18은 본 발명의 제3 실시예에 따른 이름 검색 방법을 도시한 플로우차트이다.1 is a diagram illustrating a name search system according to an embodiment of the present invention.
2 is an example of an NPT according to an embodiment of the present invention.
3 is an example of a code used in the name search information building process according to an embodiment of the present invention.
4 is an example of a pseudo code used in the process of building bloom filter information according to an embodiment of the present invention.
5 is a diagram illustrating a name search apparatus according to a first embodiment of the present invention.
6 is an example of name search information constructed according to the first embodiment of the present invention.
7 is an example of a pseudo code used in a name search process according to the first embodiment of the present invention.
FIG. 8 is a diagram illustrating a name search apparatus according to a second embodiment of the present invention.
9 is an example of name search information constructed according to the second embodiment of the present invention.
10 is an example of a code used by the Bloom filter in the process of searching for a content name according to an embodiment of the present invention.
11 is an example of a pseudo code used in the name searching process according to the second embodiment of the present invention.
12 is a diagram illustrating a name search apparatus according to a third embodiment of the present invention.
13 is an example of a pseudo code used in the name searching process according to the third embodiment of the present invention.
FIG. 14 is an example of the number of times the hash table is accessed in the name search process according to an embodiment of the present invention.
15 is an example of a memory requirement of a hash table in a name search process according to an embodiment of the present invention.
16 is a flowchart illustrating a name search method according to the first embodiment of the present invention.
17 is a flowchart illustrating a name search method according to a second embodiment of the present invention.
18 is a flowchart illustrating a method for searching for names according to a third embodiment of the present invention.

이하, 본 발명의 실시예를 첨부된 도면을 참조하여 상세하게 설명한다. 본 발명의 일실시예에 따른 이름 검색 방법은 이름 검색 장치에 의해 수행될 수 있다. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings. The name search method according to an embodiment of the present invention can be performed by a name search apparatus.

도 1은 본 발명의 일실시예에 따른 이름 검색 시스템을 나타내는 도면이다. 1 is a diagram illustrating a name search system according to an embodiment of the present invention.

도 1을 참고하면, 본 발명의 일실시예에 따른 이름 검색 시스템은 이름 검색 정보 구축 장치(110) 및 이름 검색 장치(120)를 포함할 수 있다. 이때, 이름 검색 시스템은 콘텐츠 중심 네트워킹 기술에서 콘텐츠가 저장된 노드로 요청 패킷을 전달하기 위한 출력 페이스를 검색하기 위하여 사용될 수 있다.Referring to FIG. 1, the name search system according to an embodiment of the present invention may include a name search information construction apparatus 110 and a name search apparatus 120. At this time, the name retrieval system can be used in content-based networking technology to retrieve the output face for delivering the request packet to the node where the content is stored.

이름 검색 정보 구축 장치(110)는 복수의 레벨로 구성된 이름 프리픽스 트리(Name Prefix Trie: NPT)에 따라 콘텐츠 이름을 해시 테이블, 또는 블룸 필터에 저장하여 이름 검색 정보를 구축할 수 있다.The name search information construction apparatus 110 can construct name search information by storing the content name in a hash table or a bloom filter according to a name prefix tree (NPT) composed of a plurality of levels.

도 1을 참고하면, 본 발명의 일실시예에 따른 이름 검색 정보 구축 장치(110)는 해시 테이블 생성부(111) 및 블룸 필터 생성부(112)를 포함할 수 있다.Referring to FIG. 1, the name search information construction apparatus 110 according to an embodiment of the present invention may include a hash table generation unit 111 and a bloom filter generation unit 112.

해시 테이블 생성부(111)는 NPT의 레벨 별로 해시 테이블을 생성할 수 있다. 그리고, 해시 테이블 생성부(111)는 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 해시 함수로 변환하여 해시 테이블에 저장할 수 있다.The hash table generation unit 111 can generate a hash table for each level of the NPT. The hash table generation unit 111 may convert the component of the content name corresponding to each level of the NPT into a hash function and store the hash table in the hash table.

이때, 해시 테이블 생성부(111)는 NPT의 레벨이 두 번째 레벨 이상인 경우, 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 콘텐츠 이름의 컴포넌트가 연속된 문자열을 해시 함수로 변환할 수 있다.At this time, if the level of the NPT is equal to or higher than the second level, the hash table generation unit 111 may convert the string of the components of the content name corresponding to the previous level and the content of the content name corresponding to the current level into a hash function have.

예를 들어, 해시 테이블 생성부(111)는 NPT의 첫 번째 레벨에 대응하는 콘텐츠 이름의 첫 번째 컴포넌트를 해시 함수로 변환하여 제1 해시 테이블에 저장할 수 있다. 그리고, 해시 테이블 생성부(111)는 콘텐츠 이름의 첫 번째 컴포넌트와 NPT의 두 번째 레벨에 대응하는 콘텐츠 이름의 두 번째 컴포넌트가 연속된 문자열을 해시 함수로 변환하여 제2 해시 테이블에 저장할 수 있다.For example, the hash table generation unit 111 may convert the first component of the content name corresponding to the first level of the NPT into a hash function and store the hash function in the first hash table. The hash table generation unit 111 may convert the first component of the content name and the second component of the content name corresponding to the second level of the NPT into a hash function and store the converted hash function in the second hash table.

해시 테이블 생성부(111)의 동작은 이하 도 6을 참조하여 상세히 설명한다.The operation of the hash table generation unit 111 will be described in detail with reference to FIG.

블룸 필터 생성부(112)는 콘텐츠 이름의 컴포넌트가 해시 테이블 생성부(111)가 생성한 해시 테이블에 포함되었는지 여부를 나타내는 블룸 필터를 생성할 수 있다.The bloom filter generation unit 112 may generate a bloom filter indicating whether a component of the content name is included in the hash table generated by the hash table generation unit 111. [

블룸 필터는 어떤 원소들의 집합이 주어졌을 때 주어진 집합에 속하는 원소들의 존재를 비트-벡터 형식으로 나타내는 정보 구조일 수 있다. 그리고, 블룸 필터는 입력과 일치하는 원소가 검색하는 대상인 집합 내에 존재하는지의 여부를 판단할 수 있다. 이때, 블룸 필터는 해시 함수를 이용하여 획득한 해시 인덱스에 검색한 원소를 저장하지 않고, 해시 인덱스에서 해당하는 비트 값을 1로 하여 원소의 존재를 표시할 수 있다.A Bloom filter can be an information structure that represents the existence of elements belonging to a given set in a bit-vector format given a set of elements. Then, the Bloom filter can determine whether or not an element matching the input exists in the set to be searched. At this time, the Bloom filter can display the existence of an element by storing the retrieved element in the hash index obtained by using the hash function, and setting the corresponding bit value in the hash index to 1.

이때, 블룸 필터 생성부(112)는 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트들을 미리 정해진 규칙에 따라 프로그래밍하여 블룸 필터를 생성할 수 있다. 그리고, 블룸 필터는 블룸 필터에 입력되는 정보들을 미리 정해진 규칙에 따라 인덱스로 변환할 수 있다. 또한, 블룸 필터는 인덱스로 변환된 입력 정보가 프로그래밍된 컴포넌트와 일치하는 경우, 해시 테이블에 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트가 포함된 것으로 판단할 수 있다.At this time, the bloom filter generating unit 112 may generate the bloom filter by programming the components of the content name corresponding to the levels of the NPT according to predetermined rules. The Bloom filter can convert information input to the Bloom filter into an index according to predetermined rules. In addition, if the input information converted into the index matches the programmed component, the Bloom filter can determine that the hash table includes the component of the content name corresponding to each level of the NPT.

블룸 필터 생성부(112)가 블룸 필터를 생성하는 과정은 이하 도 4를 참조하여 상세히 설명한다.The process of generating the bloom filter by the bloom filter generating unit 112 will be described in detail with reference to FIG.

이름 검색 장치(120)는 이름 검색 정보 구축 장치(110)가 구축한 이름 검색 정보의 해시 테이블, 또는 블룸 필터로 콘텐츠 이름을 검색하여 콘텐츠가 저장된 노드로 요청 패킷을 전달하기 위한 출력 페이스를 검색할 수 있다.The name searching apparatus 120 searches a hash table of name search information constructed by the name search information establishing apparatus 110 or an output face for transmitting a request packet to a node where contents are stored by searching for a content name using a bloom filter .

이때, 이름 검색 장치(120)는 해시 테이블만 이용하여 콘텐츠 이름을 검색할 수 있다. 이름 검색 장치(120)가 해시 테이블만 이용하여 콘텐츠 이름을 검색하는 구체적인 구성 및 동작은 이하 도 5를 참조하여 상세히 설명한다.At this time, the name search apparatus 120 can search for the content name using only the hash table. The specific configuration and operation in which the name search apparatus 120 searches for a content name using only a hash table will be described in detail with reference to FIG.

또한, 이름 검색 장치(120)는 블룸 필터를 선 필터로 이용하여 해시 테이블이 콘텐츠 이름이 포함되었는지 여부를 확인할 수 있다. 그리고, 이름 검색 장치(120)는 블룸 필터의 확인 결과에 따라 콘텐츠 이름을 검색할 수 있다. In addition, the name search apparatus 120 can use the Bloom filter as a line filter to check whether the hash table includes the content name. Then, the name searching apparatus 120 can search for the content name according to the result of the bloom filter check.

예를 들어, 이름 검색 장치(120)는 블룸 필터로 콘텐츠 이름이 포함된 것으로 확인된 해시 테이블에서 콘텐츠 이름을 검색하는 과정을 NPT의 레벨들 별로 콘텐츠 이름의 마지막 컴포넌트가 검색될 때까지 반복할 수 있다. 이름 검색 장치(120)가 블룸 필터로 콘텐츠 이름이 포함된 것으로 확인된 해시 테이블에서 콘텐츠 이름을 검색하는 구체적인 구성 및 동작은 이하 도 8을 참조하여 상세히 설명한다.For example, the name retrieval device 120 may repeat the process of retrieving a content name from a hash table identified as containing a content name with a Bloom filter, until the last component of the content name is retrieved by the levels of the NPT have. The specific configuration and operation for the name search apparatus 120 to search for a content name in a hash table identified as containing a content name with a Bloom filter will be described in detail below with reference to FIG.

또한, 이름 검색 장치(120)는 블룸 필터로 해시 테이블에 콘텐츠 이름이 포함된 것으로 확인된 경우, 해시 테이블에서 콘텐츠 이름을 검색하는 과정을 생략하고, 하위 레벨에서 블룸 필터를 적용함으로써, 블룸 필터를 연속으로 적용할 수 있다. 이때, 이름 검색 장치(120)는 블룸 필터를 연속으로 적용하여 콘텐츠 이름의 마지막 컴포넌트가 포함된 NPT의 레벨을 먼저 검색하고, 마지막 컴포넌트가 포함된 레벨의 해시 테이블에서 콘텐츠 이름을 검색할 수 있다. 이름 검색 장치(120)가 블룸 필터를 연속으로 적용하여 콘텐츠 이름을 검색하는 구체적인 구성 및 동작은 이하 도 12를 참조하여 상세히 설명한다.In addition, if it is confirmed that the content name is included in the hash table by the Bloom filter, the name searching apparatus 120 skips the process of searching for the content name in the hash table and applies the Bloom filter at the lower level, It can be applied continuously. At this time, the name search apparatus 120 can search for the level of the NPT including the last component of the content name first by applying Bloom filter successively, and search for the content name from the hash table of the level including the last component. The detailed configuration and operation of the name searching apparatus 120 for searching for the content name by successively applying the Bloom filter will be described in detail with reference to FIG.

도 2는 본 발명의 일실시예에 따른 NPT의 일례이다.2 is an example of an NPT according to an embodiment of the present invention.

콘텐츠가 저장된 위치를 나타내는 콘텐츠 이름은 복수의 컴포넌트로 구성될 수 있다. 예를 들어, 콘텐츠 이름은 URL에 기초하여 결정될 수 있다. 이때, URL은 URL을 구성하는 각각의 컴포넌트를 슬래시(/) 또는 점(.)으로 구분할 수 있다. 예를 들어, "youtube.com/user/PewDiePie"와 같은 URL은 youtube, com, user, PewDiePie, 4개의 컴포넌트로 구성될 수 있다.The content name indicating the location where the content is stored may be composed of a plurality of components. For example, the content name can be determined based on the URL. At this time, the URL can distinguish each component constituting the URL by a slash (/) or a dot (.). For example, a URL such as "youtube.com/user/PewDiePie" can consist of four components: youtube, com, user, PewDiePie.

이때, 이름 검색 정보 구축 장치(110)는 URL에서 온점(.)으로 구분되는 컴포넌트는 역방향으로 뒤집고, 슬래시(/) 이후의 컴포넌트들의 순서는 유지함으로써, 이름 검색 정보의 콘텐츠 이름으로 사용할 수 있다. 또한, 콘텐츠 이름을 구성하는 컴포넌트 간 구분은 슬래시(/)를 이용할 수 있다.At this time, the name search information construction apparatus 110 can use the content name of the name search information by reversing the component separated by the on-point from the URL in the reverse direction and maintaining the order of the components after the slash (/). In addition, a slash (/) can be used to distinguish between components constituting a content name.

예를 들어, 이름 검색 정보 구축 장치(110)는 "youtube.com/user/PewDiePie"와 같은 URL을 기초로 "com/youtube/user/PewDiePie"라는 콘텐츠 이름을 결정할 수 있다.For example, the name search information construction apparatus 110 can determine the content name "com / youtube / user / PewDiePie" based on a URL such as "youtube.com/user/PewDiePie".

NPT는 트라이 기반의 이름 검색 알고리즘이며, 도 2는 이름 검색 정보 구축 장치(110)가 결정한 10개의 콘텐츠 이름을 이용하여 구성된 NPT의 일례이다.NPT is a tri-based name search algorithm, and FIG. 2 is an example of an NPT configured by using ten content names determined by the name search information construction apparatus 110.

이때, NPT는 콘텐츠 이름에 포함된 컴포넌트의 수에 따라 최대 레벨이 결정될 수 있다.At this time, the NPT can be determined at a maximum level according to the number of components included in the content name.

예를 들어, 콘텐츠 이름(210)은 구성하는 컴포넌트가 "kr", "or", "visitkorea"의 3개이므로, 콘텐츠 이름(210)의 최대 레벨은 3일 수 있다. 또한, 콘텐츠 이름(220)은 구성하는 컴포넌트가 "com", "youtube", "user", "PewDiePie"의 4개이므로, 콘텐츠 이름(220)의 최대 레벨은 4일 수 있다.For example, the content name 210 may have a maximum level of 3 because the constituent components are three of "kr", "or", and "visitkorea". In addition, since the content name 220 has four components of "com", "youtube", "user", and "PewDiePie", the maximum level of the content name 220 may be four.

즉, NPT는 콘텐츠 이름에 따라 최대 레벨이 서로 다를 수 있다.That is, the NPTs may have different maximum levels depending on the content name.

도 3은 본 발명의 일실시예에 따른 이름 검색 정보 구축 과정에서 사용하는 코드의 일례이다.3 is an example of a code used in the name search information building process according to an embodiment of the present invention.

먼저 해시 테이블 생성부(111)는 NPT의 레벨 별로 해시 테이블을 생성할 수 있다.First, the hash table generating unit 111 can generate a hash table for each level of the NPT.

다음으로, 해시 테이블 생성부(111)는 도 3의 코드에 도시된 바와 같이 NPT의 레벨 별로 생성된 해시 테이블에 FIB의 엔트리에 해당하는 콘텐츠 이름을 저장할 수 있다. 이때, 해시 테이블 생성부(111)는 첫 번째 레벨 해시 테이블부터 마지막 레벨 해시 테이블까지 순차적으로 콘텐츠 이름을 저장할 수 있다.Next, the hash table generation unit 111 may store a content name corresponding to an entry of the FIB in the hash table generated for each level of the NPT, as shown in the code of FIG. At this time, the hash table generation unit 111 may sequentially store the content names from the first level hash table to the last level hash table.

구체적으로, 해시 테이블 생성부(111)는 콘텐츠 이름의 첫 번째 컴포넌트로 구성된 문자열을 해시 함수로 변환하여 제1 해시 인덱스를 얻을 수 있다. 그리고, 해시 테이블 생성부(111)는 첫 번째 해시 테이블에서 제1 해시 인덱스에 대응하는 인덱스에 첫 번째 컴포넌트로 구성된 문자열을 저장할 수 있다.Specifically, the hash table generation unit 111 may obtain a first hash index by converting a string composed of the first component of the content name into a hash function. The hash table generation unit 111 may store a string composed of the first component in the index corresponding to the first hash index in the first hash table.

다음으로, 해시 테이블 생성부(111)는 콘텐츠 이름의 첫 번째 컴포넌트와 두 번째 컴포넌트가 연속된(concatenation) 문자열을 해시 함수로 변환하여 제2 해시 인덱스를 얻을 수 있다. 그리고, 해시 테이블 생성부(111)는 두 번째 해시 테이블에서 제2 해시 인덱스에 대응하는 인덱스에 콘텐츠 이름의 첫 번째 컴포넌트와 두 번째 컴포넌트가 연속된 문자열을 저장할 수 있다.Next, the hash table generation unit 111 may obtain a second hash index by converting a concatenated string of the first component and the second component of the content name into a hash function. The hash table generation unit 111 may store the first and second components of the content name in the index corresponding to the second hash index in the second hash table.

그리고, 해시 테이블 생성부(111)는 상기 과정을 콘텐츠 이름의 첫 번째 컴포넌트에서 마지막 컴포넌트까지 연속된 문자열이 해시 테이블에 저장될 때까지 수행할 수 있다. 또한, 해시 테이블 생성부(111)는 콘텐츠 이름의 마지막 컴포넌트가 해시 테이블에 저장될 때, 출력 페이스(face)의 정보를 함께 저장할 수 있다.The hash table generation unit 111 may perform the above process until a sequence of characters from the first component to the last component of the content name is stored in the hash table. In addition, the hash table generation unit 111 may store the information of the output face when the last component of the content name is stored in the hash table.

그리고, 해시 테이블 생성부(111)는 콘텐츠 이름들 각각을 도 3의 코드에 입력하여 콘텐츠 이름에 대응하는 해시 테이블들을 생성할 수 있다.The hash table generation unit 111 may input each of the content names into the code of FIG. 3 to generate hash tables corresponding to the content name.

도 4는 본 발명의 일실시예에 따른 블룸 필터 정보 구축 과정에서 사용하는 의사 코드의 일례이다.4 is an example of a pseudo code used in the process of building bloom filter information according to an embodiment of the present invention.

먼저, 블룸 필터 생성부(112)는 블룸 필터의 모든 색인의 비트-벡터 값을 0으로 초기화할 수 있다.First, the bloom filter generation unit 112 may initialize the bit-vector values of all indexes of the bloom filter to zero.

다음으로, 블룸 필터 생성부(112)는 도 4의 코드에 도시된 바와 같이 문자열에 포함된 컴포넌트 x의 정보를 해시 함수에 입력하여 블룸 필터를 프로그래밍할 위치를 나타내는 색인(for i = 1, …, k) 를 출력할 수 있다. 이때, 미리 프로그래밍된 컴포넌트와 동일한 색인이 출력되는 경우, 블룸 필터 생성부(112)는 해당 색인의 비트-벡터 값을 1로 유지할 수 있다.Next, the bloom filter generating unit 112 inputs the information of the component x contained in the character string into the hash function as shown in the code of Fig. 4, and outputs an index (for i = 1, ..., , k). At this time, when the same index as the preprogrammed component is output, the bloom filter generation unit 112 can maintain the bit-vector value of the index as 1. [

그리고, 블룸 필터 생성부(112)는 문자열에 포함된 모든 컴포넌트에 대해서, 해당 색인에 대응되는 비트-벡터 값을 1로 지정하여 블룸 필터를 생성할 수 있다.The bloom filter generation unit 112 may generate a bloom filter for all components included in the character string by designating a bit-vector value corresponding to the index as 1.

도 5는 본 발명의 제1 실시예에 따른 이름 검색 장치를 나타내는 도면이다. 5 is a diagram illustrating a name search apparatus according to a first embodiment of the present invention.

본 발명의 제1 실시예에 따른 이름 검색 장치(120)는 해시 테이블만 이용하여 콘텐츠 이름을 검색하는 해싱 기반-NPT 알고리즘을 수행할 수 있다.The name search apparatus 120 according to the first embodiment of the present invention may perform a hashing-based -NPT algorithm for searching for a content name using only a hash table.

도 5를 참고하면, 본 발명의 제1 실시예에 따른 이름 검색 장치(120)는 콘텐츠 이름 변환부(510), 및 해시 테이블 검색부(520)를 포함할 수 있다.Referring to FIG. 5, the name search apparatus 120 according to the first embodiment of the present invention may include a content name conversion unit 510 and a hash table search unit 520.

콘텐츠 이름 변환부(510)는 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 해시 함수로 변환할 수 있다.The content name conversion unit 510 may convert a component of the content name corresponding to each of the levels of the NPT into a hash function.

이때, 콘텐츠 이름 변환부(510)는 해시 테이블 생성부(111)가 NPT의 레벨들 별로 해시 테이블을 생성하는 과정에서 해시 인덱스의 생성에 이용된 해시 함수를 이용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환할 수 있다.At this time, the hash table generation unit 111 generates a hash table using the hash function used for generating the hash index in the process of generating the hash table for each level of the NPT, You can convert the component of the content name.

또한, NPT의 레벨이 두 번째 레벨 이상인 경우, 콘텐츠 이름 변환부(510)는 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 콘텐츠 이름의 컴포넌트가 연속된 문자열을 해시 함수로 변환할 수 있다.If the level of the NPT is equal to or higher than the second level, the content name conversion unit 510 can convert the string of the components of the content name corresponding to the previous level and the content of the content name corresponding to the current level into a hash function have.

해시 테이블 검색부(520)는 NPT의 레벨들 별로 생성된 해시 테이블에서 콘텐츠 이름 변환부(510)가 해시 함수로 변환한 컴포넌트를 검색할 수 있다. 이때, 해시 테이블 검색부(520)는 현재 레벨에 대응하는 해시 테이블에서 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 콘텐츠 이름의 컴포넌트가 연속된 문자열이 해시 함수로 변환된 해시 인덱스를 검색할 수 있다.The hash table retrieving unit 520 can retrieve the component converted by the content name converting unit 510 into the hash function in the hash table generated for each level of the NPT. At this time, the hash table search unit 520 searches the hash table corresponding to the current level for a hash index obtained by converting the component of the content name corresponding to the previous level and the content name of the component corresponding to the current level, You can search.

또한, 해시 테이블 검색부(520)는 현재 레벨의 해시 테이블에서 컴포넌트가 검색되는 경우, 다음 레벨의 해시 테이블에서 컴포넌트를 검색할 수 있다. In addition, the hash table search unit 520 can search a component in the next level hash table when a component is searched in the hash table of the current level.

이때, 해시 테이블 검색부(520)는 현재 레벨의 해시 테이블에서 컴포넌트가 검색되지 않거나, 현재 레벨이 콘텐츠 이름에 대응하는 NPT의 마지막 레벨이 될 때까지 상기 과정을 반복할 수 있다.At this time, the hash table search unit 520 may repeat the above process until no component is found in the hash table of the current level, or the current level becomes the last level of the NPT corresponding to the content name.

그리고, 현재 레벨에 대응하는 해시 테이블에서 상기 해시 함수로 변환된 컴포넌트가 검색되지 않는 경우, 해시 테이블 검색부(520)는 이전 레벨의 해시 테이블에 포함된 출력 페이스 중에서 마지막으로 검색된 출력 페이스로 상기 콘텐츠 이름에 대응하는 콘텐츠 요청 패킷을 전송할 수 있다.If the component having been converted into the hash function is not found in the hash table corresponding to the current level, the hash table search unit 520 searches the hash table of the current level for the content It is possible to transmit a content request packet corresponding to the name.

도 6은 본 발명의 제1 실시예에 따라 구축한 이름 검색 정보의 일례이다.6 is an example of name search information constructed according to the first embodiment of the present invention.

이름 검색 정보 구축 장치(110)의 해시 테이블 생성부(111)는 NPT(610)의 레벨 별로 해시 테이블(620)을 생성할 수 있다.The hash table generation unit 111 of the name search information construction apparatus 110 can generate the hash table 620 for each level of the NPT 610. [

다음으로, 해시 테이블 생성부(111)는 NPT의 레벨 별로 생성된 해시 테이블(620)에 콘텐츠 이름을 저장할 수 있다. Next, the hash table generation unit 111 may store the content name in the hash table 620 generated for each level of the NPT.

구체적으로, 해시 테이블 생성부(111)는 콘텐츠 이름의 첫 번째 컴포넌트인 "com"으로 구성된 문자열을 해시 함수로 변환하여 제1 해시 인덱스를 얻을 수 있다. 그리고, 해시 테이블 생성부(111)는 첫 번째 해시 테이블(621)에서 제1 해시 인덱스에 대응하는 인덱스에 "com"으로 구성된 문자열을 저장할 수 있다.Specifically, the hash table generation unit 111 can obtain a first hash index by converting a string composed of "com" as the first component of the content name into a hash function. The hash table generation unit 111 may store a string composed of "com" in the index corresponding to the first hash index in the first hash table 621. [

다음으로, 해시 테이블 생성부(111)는 콘텐츠 이름의 첫 번째 컴포넌트인 "com"와 두 번째 컴포넌트인 "facebook"가 연속된 문자열인 "com/facebook" 을 해시 함수로 변환하여 제2 해시 인덱스를 얻을 수 있다. 그리고, 해시 테이블 생성부(111)는 두 번째 해시 테이블(622)에서 제2 해시 인덱스에 대응하는 인덱스에 문자열 "com/facebook"을 저장할 수 있다. 이때, 문자열 "com/facebook" 와 관련된 콘텐츠 이름(611)는 도 6에 도시된 바와 같이 2레벨이 NPT의 마지막 레벨일 수 있다. 따라서, 해시 테이블 생성부(111)는 문자열 "com/facebook"과 관련된 이름 검색 정보의 구축을 종료할 수 있다.Next, the hash table generation unit 111 converts the " com / facebook ", which is a sequence of the first component "com" of the content name and the second component "facebook " Can be obtained. The hash table generating unit 111 may store the string "com / facebook" in the index corresponding to the second hash index in the second hash table 622. [ At this time, the content name 611 related to the string "com / facebook " may be the last level of the NPT at the second level as shown in FIG. Thus, the hash table generation unit 111 can terminate the construction of the name search information associated with the string "com / facebook ".

또한, 콘텐츠 이름(612)이 "com/youtube/user/PewDiePie"인 경우, 콘텐츠 이름(612)는 4개의 컴포넌트로 구성될 수 있다. 따라서, 해당 콘텐츠는 도 6에 도시된 바와 같이 4레벨이 NPT의 마지막 레벨일 수 있다. 그리고, 해시 테이블 생성부(111)는 도 6에 도시된 바와 같이 네 번째 해시 테이블(623)에서 제4 해시 인덱스에 대응하는 인덱스에 문자열" com/youtube/user/PewDiePie"를 저장할 수 있다.Further, when the content name 612 is "com / youtube / user / PewDiePie ", the content name 612 may be composed of four components. Therefore, the corresponding content may be the last level of the NPT, as shown in FIG. The hash table generating unit 111 may store the string "com / youtube / user / PewDiePie" in the index corresponding to the fourth hash index in the fourth hash table 623 as shown in FIG.

도 7은 본 발명의 제1 실시예에 따른 이름 검색 과정에서 사용하는 의사 코드의 일례이다.7 is an example of a pseudo code used in a name search process according to the first embodiment of the present invention.

해시 테이블 검색부(520)는 도 7의 코드에 도시된 바와 같이 수신한 정보 요청 패킷에 따라 패킷의 콘텐츠 이름의 첫 번째 컴포넌트를 사용하여 첫 번째 레벨부터 해시 테이블 검색을 시작할 수 있다.The hash table search unit 520 may start the hash table search from the first level using the first component of the content name of the packet according to the received information request packet as shown in the code of FIG.

첫 번째 레벨의 해시 테이블에 정보 요청 패킷과 일치하는 콘텐츠 이름의 컴포넌트가 존재하는 경우, 해시 테이블 검색부(520)는 두 번째 레벨의 해시 테이블에서 콘텐츠 이름을 검색할 수 있다. 이때, 해시 테이블 검색부(520)가 두 번째 레벨의 해시 테이블에서 검색하는 이름은 콘텐츠의 이름에 포함된 처음 두 개 컴포넌트가 연속된 문자열일 수 있다.If there is a component of the content name matching the information request packet in the first level hash table, the hash table search unit 520 may search for the content name in the second level hash table. At this time, the name retrieved from the second level hash table by the hash table search unit 520 may be a string of the first two components included in the name of the content.

그리고, 해시 테이블 검색부(520)는 상기 과정을 해시 테이블에서 일치하는 문자열을 발견하지 못했거나 마지막 레벨에 도달할 때까지 반복할 수 있다.The hash table search unit 520 may repeat the above process until the matching string is not found in the hash table or the last level is reached.

또한, FIB의 콘텐츠 이름 검색 방법은 IP 주소 검색에서와 마찬가지로 최장 길이 일치(Longest Prefix Matching) 룰이 적용될 수 있다. 따라서, 해시 테이블에서 검색된 인덱스에 인터레스트(Interest) 패킷을 내보내야 할 페이스가 저장된 경우, 해시 테이블 검색부(520)는 해시 테이블에 저장된 페이스를 저장할 수 있다. 그리고, NPT는 이전 레벨의 문자열이 다음 레벨의 문자열을 포함하는 특성을 가지고 있으므로, 현재 레벨의 해시 테이블에서 콘텐츠 이름과 일치하는 문자열을 검색하지 못한 경우, NPT의 다음 레벨에서도 일치하는 문자열이 검색되지 않는다. 따라서, 현재 레벨의 해시 테이블에서 콘텐츠 이름과 일치하는 문자열을 검색하지 못한 경우, 해시 테이블 검색부(520)는 검색을 종료하고 가장 최근에 저장된 페이스로 정보 요청 패킷을 전송할 수 있다.In addition, the content name search method of the FIB can be applied to the longest prefix matching rule as in the IP address search. Accordingly, if a pace for sending an interest packet to an index retrieved from the hash table is stored, the hash table retrieving unit 520 can store the pace stored in the hash table. In addition, NPT has the property that the previous level string contains the next level string, so if the hash table of the current level does not retrieve a string that matches the content name, the matching string is not searched at the next level of NPT Do not. Therefore, if a string matching the content name can not be retrieved from the hash table of the current level, the hash table search unit 520 may terminate the search and transmit the information request packet to the most recently stored face.

도 8은 본 발명의 제2 실시예에 따른 이름 검색 장치를 나타내는 도면이다. FIG. 8 is a diagram illustrating a name search apparatus according to a second embodiment of the present invention.

본 발명의 제2 실시예에 따른 이름 검색 장치(120)는 블룸 필터로 콘텐츠 이름이 포함된 것으로 확인된 해시 테이블에서 콘텐츠 이름을 검색하는 NPT-BF(Bloom Filter) 알고리즘을 수행할 수 있다.The name searching apparatus 120 according to the second embodiment of the present invention may perform an NPT-BF (Bloom Filter) algorithm for searching for a content name in a hash table confirmed to contain a content name by a Bloom filter.

도 8을 참고하면, 본 발명의 제2 실시예에 따른 이름 검색 장치(120)는 콘텐츠 이름 변환부(810), 블룸 필터 검색부(820) 및 해시 테이블 검색부(830)를 포함할 수 있다.8, the name search apparatus 120 according to the second embodiment of the present invention may include a content name conversion unit 810, a bloom filter search unit 820, and a hash table search unit 830 .

콘텐츠 이름 변환부(810)는 해시 함수를 사용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환할 수 있다.The content name conversion unit 810 can convert the component of the content name corresponding to each of the levels of the NPT using the hash function.

이때, 콘텐츠 이름 변환부(810)는 해시 테이블 생성부(111)가 NPT의 레벨들 별로 해시 테이블을 생성하는 과정에서 해시 인덱스의 생성에 이용된 해시 함수 및 블룸 필터 생성부(112)가 NPT의 레벨들 별로 해시 테이블에 대응하는 블룸 필터를 생성하는 과정에서 블룸 필터의 생성에 이용된 해시 함수를 이용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환할 수 있다.In this case, the hash table generation unit 111 generates a hash function used for generating a hash index and a hash function used by the bloom filter generation unit 112 in the process of generating a hash table for each level of the NPT, The component of the content name corresponding to each level of the NPT can be converted using the hash function used for generating the Bloom filter in the process of generating the Bloom filter corresponding to the hash table for each level.

블룸 필터 검색부(820)는 NPT의 레벨들 별로 생성된 블룸 필터로 콘텐츠 이름을 검색할 수 있다. 이때, 블룸 필터는 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 컴포넌트가 연속된 문자열을 포함할 수 있다.The bloom filter search unit 820 can search for a content name using a bloom filter generated for each level of the NPT. At this time, the bloom filter may include a series of components of the content name corresponding to the previous level and a series of components corresponding to the current level.

해시 테이블 검색부(830)는 블룸 필터 검색부(820)의 검색 결과에 기초하여 블룸 필터에 대응하는 해시 테이블에서 콘텐츠 이름을 검색할 수 있다.The hash table search unit 830 may search for a content name in the hash table corresponding to the bloom filter based on the search result of the bloom filter search unit 820. [

블룸 필터의 검색 결과가 양성인 경우, 해시 테이블 검색부(830)는 블룸 필터에 대응하는 해시 테이블에서 콘텐츠 이름을 검색할 수 있다. If the search result of the bloom filter is positive, the hash table search unit 830 can search for the content name in the hash table corresponding to the bloom filter.

또한, 블룸 필터의 검색 결과가 음성이거나, 해시 테이블에서 콘텐츠 이름이 검색되지 않는 경우, 해시 테이블 검색부(830)는 콘텐츠 이름의 검색을 종료할 수 있다. 이때, 해시 테이블 검색부(830)는 콘텐츠 이름이 마지막으로 검색된 해시 테이블에 포함된 출력 페이스로 콘텐츠 이름에 대응하는 콘텐츠 요청 패킷을 전송할 수 있다.If the search result of the Bloom filter is voice or the content name is not found in the hash table, the hash table search unit 830 may terminate the search of the content name. At this time, the hash table search unit 830 may transmit the content request packet corresponding to the content name at the output face included in the hash table in which the content name was last searched.

그리고, 해시 테이블 검색부(830)가 해시 테이블에서 콘텐츠 이름을 검색 성공한 경우, 블룸 필터 검색부(820)는 NPT의 다음 레벨의 블룸 필터로 콘텐츠 이름을 검색할 수 있다.If the hash table retrieving unit 830 has succeeded in retrieving the contents name from the hash table, the bloom filter retrieving unit 820 can retrieve the contents name with the bloom filter of the next level of NPT.

본 발명의 제2 실시예에 따른 이름 검색 장치(120)는 블룸 필터를 선 필터로 사용하여 해시 테이블에 콘텐츠 이름이 포함될 가능성을 식별할 수 있다. 그리고, 이름 검색 장치(120)는 해시 테이블에 콘텐츠 이름이 포함될 가능성이 높은 경우에만 해시 테이블에서 콘텐츠 이름을 검색함으로써, 콘텐츠 이름이 저장되지 않은 해시 테이블을 검색하기 위한 시간, 및 처리 능력 낭비를 최소화할 수 있다.The name searching apparatus 120 according to the second embodiment of the present invention can use the Bloom filter as a line filter to identify the possibility of including the content name in the hash table. Then, the name search apparatus 120 searches the hash table for the content name only when the hash table is highly likely to include the content name, thereby minimizing the time for searching for the hash table in which the content name is not stored, can do.

도 9는 본 발명의 제2 실시예에 따라 구축한 이름 검색 정보의 일례이다.9 is an example of name search information constructed according to the second embodiment of the present invention.

이름 검색 정보 구축 장치(110)의 해시 테이블 생성부(111)는 NPT(920)의 레벨 별로 해시 테이블(930)을 생성할 수 있다. The hash table generation unit 111 of the name search information construction apparatus 110 can generate the hash table 930 for each level of the NPT 920. [

다음으로, 해시 테이블 생성부(111)는 NPT의 레벨 별로 생성된 해시 테이블(930)에 콘텐츠 이름을 저장할 수 있다. 이때, 해시 테이블 생성부(111)는 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 해시 함수로 변환하여 해시 테이블에 저장할 수 있다. 또한, 해시 테이블 생성부(111)는 NPT의 레벨이 두 번째 레벨 이상인 경우, 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 콘텐츠 이름의 컴포넌트가 연속된 문자열을 해시 함수로 변환할 수 있다.Next, the hash table generation unit 111 may store the content name in the hash table 930 generated for each level of the NPT. At this time, the hash table generation unit 111 may convert the component of the content name corresponding to each level of the NPT into a hash function and store the hash function in the hash table. If the level of the NPT is equal to or higher than the second level, the hash table generating unit 111 may convert the string of components of the content name corresponding to the previous level and the content of the content name corresponding to the current level into a hash function have.

또한, 블룸 필터 생성부(111)는 NPT의 레벨 및 해시 테이블(930)에 대응하는 블룸 필터(910)를 생성할 수 있다. 이때, 블룸 필터 생성부(111)는 해시 테이블(930)에 저장된 문자열을 미리 정해진 해시 함수, 또는 해시 테이블 생성부(111)가 사용한 해시 함수로 프로그래밍하여 블룸 필터를 생성할 수 있다.In addition, the bloom filter generation unit 111 may generate the bloom filter 910 corresponding to the level of the NPT and the hash table 930. At this time, the bloom filter generating unit 111 may generate the bloom filter by programming the string stored in the hash table 930 with a predetermined hash function or a hash function used by the hash table generating unit 111. [

도 10은 본 발명의 일실시예에 따른 블룸 필터가 콘텐츠 이름 검색 과정에서 사용하는 코드의 일례이다.10 is an example of a code used by the Bloom filter in the process of searching for a content name according to an embodiment of the present invention.

블룸 필터 검색부(820)는 NPT의 레벨들 별로 생성된 블룸 필터로 콘텐츠 이름을 검색할 수 있다.The bloom filter search unit 820 can search for a content name using a bloom filter generated for each level of the NPT.

이때, 블룸 필터 검색부(820)는 도 10의 코드에 도시된 바와 같이 입력과 블룸 필터에 저장된 값을 비교하는 쿼리 과정을 진행할 수 있다. 이때, 블룸 필터의 입력은 콘텐츠 이름 변환부(810)가 콘텐츠 이름을 변환하여 생성한 블룸 필터 색인일 수 있다.At this time, the bloom filter search unit 820 may perform a query process for comparing the input and the values stored in the bloom filter as shown in the code of Fig. At this time, the input of the bloom filter may be the bloom filter index generated by the content name conversion unit 810 by converting the content name.

콘텐츠 이름 변환부(810)는 블룸 필터 생성부(112)가 블룸 필터 프로그래밍 과정에서 사용했던 해시 함수와 동일한 해시 함수로 콘텐츠 이름을 변환하여 블룸 필터 색인을 출력할 수 있다. 또한, 콘텐츠 이름 변환부(810)가 출력하는 블룸 필터 색인의 개수는 블룸 필터 생성부(112)가 블룸 필터를 프로그래밍 될 때의 색인 개수와 동일하다.The content name conversion unit 810 can output the Bloom filter index by converting the content name into a hash function that is the same as the hash function used by the Bloom filter generation unit 112 in the Bloom filter programming process. Also, the number of bloom filter indexes output by the content name conversion unit 810 is the same as the number of bloom filter generation units 112 when the bloom filter is programmed.

그리고, 블룸 필터 검색부(820)는 블룸 필터에서 콘텐츠 이름 변환부(810)가 출력하는 블룸 필터 색인의 위치에 해당하는 비트-벡터 값을 확인할 수 있다.The bloom filter search unit 820 can check the bit-vector value corresponding to the position of the bloom filter index output from the content name conversion unit 810 in the bloom filter.

이때, 블룸 필터의 입력에 따라 블룸 필터 검색부(820)가 확인한 모든 색인의 비트-벡터 값이 1인 경우, 블룸 필터의 입력은 블룸 필터를 통과할 수 있다. 그리고, 블룸 필터 검색부(820)는 블룸 필터의 검색 결과를 양성이라고 한다.In this case, when the bit-vector value of all indexes checked by the bloom filter search unit 820 according to the input of the bloom filter is 1, the input of the bloom filter can pass through the bloom filter. The Bloom filter search unit 820 determines that the search result of the Bloom filter is positive.

또한, 블룸 필터의 입력에 따라 블룸 필터 검색부(820)가 확인한 색인의 비트-벡터 값 중 적어도 하나의 0이 포함된 경우, 블룸 필터의 입력은 블룸 필터를 통과할 수 없다. 그리고, 블룸 필터 검색부(820)는 블룸 필터의 검색 결과를 음성이라고 한다.In addition, when at least one of the bit-vector values of the index determined by the bloom filter search unit 820 according to the input of the bloom filter is included, the input of the bloom filter can not pass through the bloom filter. The bloom filter search unit 820 refers to the search result of the bloom filter as speech.

도 11은 본 발명의 제2 실시예에 따른 이름 검색 과정에서 사용하는 의사 코드의 일례이다.11 is an example of a pseudo code used in the name searching process according to the second embodiment of the present invention.

블룸 필터 검색부(820)는 도 11의 코드에 도시된 바와 같이 블룸 필터를 먼저 검색할 수 있다. 그리고, 해시 테이블 검색부(830)는 블룸 필터의 검색 결과가 양성인 경우에만 해시 테이블에 접근하여 콘텐츠 이름이 해시 테이블에 존재하는지 확인할 수 있다.The bloom filter search unit 820 can search for the bloom filter first as shown in the code of Fig. The hash table search unit 830 can access the hash table only if the search result of the bloom filter is positive, and confirm whether the content name exists in the hash table.

콘텐츠 이름이 해시 테이블에 존재하는 경우, 블룸 필터 쿼리 결과가 참-양성이므로 블룸 필터 검색부(820)는 다음 레벨의 블룸 필터를 쿼리할 수 있다.If the content name exists in the hash table, the Bloom filter search unit 820 can query the next level Bloom filter because the Bloom filter query result is true-positive.

그러나, 콘텐츠 이름이 해시 테이블에 존재하지 않는 경우, 블룸 필터 쿼리 결과가 음성이거나 거짓-양성이므로 블룸 필터 검색부(820)는 검색을 종료할 수 있다. 이전 레벨에서 검색하여 저장, 또는 기억한 출력 페이스가 존재하는 경우, 해시 테이블 검색부(830)는 저장한 출력 페이스를 출력할 수 있다.However, if the content name does not exist in the hash table, the Bloom filter search unit 820 can terminate the search because the Bloom filter query result is speech or false-positive. If there is an output face that is searched, stored, or stored at the previous level, the hash table search unit 830 can output the stored output face.

즉, 이름 검색 장치(120)는 해시 테이블에 콘텐츠 이름이 포함될 가능성이 없는 경우, 해당 해시 테이블에 접근하지 않고 검색을 종료할 수 있다. 따라서, 이름 검색 장치(120)는 해시 테이블 접근회수를 감소시킴으로써 검색 성능을 향상시킬 수 있다. That is, if there is no possibility that the content name is included in the hash table, the name search apparatus 120 can terminate the search without accessing the hash table. Therefore, the name searching apparatus 120 can improve the search performance by reducing the number of hash table accesses.

도 12는 본 발명의 제3 실시예에 따른 이름 검색 장치를 나타내는 도면이다. 12 is a diagram illustrating a name search apparatus according to a third embodiment of the present invention.

본 발명의 제3 실시예에 따른 이름 검색 장치(120)는 블룸 필터를 연속으로 적용하여 콘텐츠 이름을 검색하는 NPT-BF-Chaining 알고리즘을 수행할 수 있다. 이때, NPT-BF-Chaining 알고리즘은 블룸 필터의 거짓양성의 확률이 매우 적다는 점을 이용한 알고리즘이다. The name searching apparatus 120 according to the third embodiment of the present invention can perform an NPT-BF-Chaining algorithm for searching for a content name by continuously applying a Bloom filter. In this case, the NPT-BF-Chaining algorithm is based on the fact that the probability of false positives of the Bloom filter is very small.

구체적으로 블룸 필터가 양성을 출력한 경우, 이름 검색 장치(120)는 블룸 필터의 결과를 잠정적으로 참-양성이라 판단하고, 다음 레벨로 블룸 필터 쿼리를 계속 진행할 수 있다.Specifically, if the Bloom filter outputs a positive result, the name search device 120 may determine that the Bloom filter result is provisionally true-positive and continue the Bloom filter query to the next level.

즉, 이름 검색 장치(120)는 블룸 필터 검색을 통하여 최장 길이 일치 콘텐츠 이름이 있는 레벨을 먼저 식별할 수 있다. 그리고, 이름 검색 장치(120)는 식별한 레벨에 해당하는 해시 테이블에서 콘텐츠 이름을 검색함으로써, 빠르게 콘텐츠 이름을 검색할 수 있다. 또한, 식별한 레벨에 해당하는 해시 테이블에 콘텐츠 이름이 존재하지 않는 경우, 백-트래킹(back-tracking)을 통하여 이전 레벨로 검색을 진행할 수 있다.That is, the name searching apparatus 120 can first identify the level having the longest-length matching content name through the Bloom filter search. Then, the name searching apparatus 120 can quickly search for a content name by searching for a content name in a hash table corresponding to the identified level. In addition, if there is no content name in the hash table corresponding to the identified level, the search can be performed at the previous level through back-tracking.

도 12를 참고하면, 본 발명의 제3 실시예에 따른 이름 검색 장치(120)는 콘텐츠 이름 변환부(1210), 블룸 필터 검색부(1220) 및 해시 테이블 검색부(1230)를 포함할 수 있다.12, the name search apparatus 120 according to the third embodiment of the present invention may include a content name conversion unit 1210, a bloom filter search unit 1220, and a hash table search unit 1230 .

콘텐츠 이름 변환부(1210)는 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 해시 함수로 변환할 수 있다.The content name conversion unit 1210 may convert a component of the content name corresponding to each of the levels of the NPT into a hash function.

이때, 콘텐츠 이름 변환부(1210)는 해시 테이블 생성부(111)가 NPT의 레벨들 별로 해시 테이블을 생성하는 과정에서 해시 인덱스의 생성에 이용된 해시 함수 및 블룸 필터 생성부(112)가 NPT의 레벨들 별로 해시 테이블에 대응하는 블룸 필터를 생성하는 과정에서 블룸 필터의 생성에 이용된 해시 함수를 이용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환할 수 있다.At this time, the content name conversion unit 1210 converts the hash function used for generating the hash index and the hash function used by the bloom filter generation unit 112 in the process of generating the hash table for each level of the NPT by the hash table generation unit 111, The component of the content name corresponding to each level of the NPT can be converted using the hash function used for generating the Bloom filter in the process of generating the Bloom filter corresponding to the hash table for each level.

블룸 필터 검색부(1220)는 NPT의 레벨들 별로 생성된 블룸 필터들에서 콘텐츠 이름을 연쇄적으로 검색할 수 있다. 이때, 블룸 필터는 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 컴포넌트가 연속된 문자열을 포함할 수 있다.The bloom filter search unit 1220 can sequentially search for the content name in the bloom filters generated for each level of the NPT. At this time, the bloom filter may include a series of components of the content name corresponding to the previous level and a series of components corresponding to the current level.

또한, 블룸 필터 검색부(1220)는 NPT의 현재 레벨에 대응하는 블룸 필터로 콘텐츠 이름에 포함된 컴포넌트를 검색할 수 있다. 이때, 블룸 필터의 검색 결과가 양성인 경우, 블룸 필터 검색부(1220)는 NPT의 다음 레벨의 블룸 필터로 콘텐츠 이름에 포함된 컴포넌트를 검색할 수 있다. In addition, the bloom filter search unit 1220 can search for a component included in the content name with a bloom filter corresponding to the current level of the NPT. At this time, when the search result of the Bloom filter is positive, the Bloom filter search unit 1220 can search for a component included in the content name with the Bloom filter of the next level of the NPT.

그리고, 블룸 필터의 검색 결과가 음성이거나, 현재 레벨이 NPT의 마지막 레벨인 경우, 블룸 필터 검색부(1220)는 콘텐츠 이름의 연쇄 검색을 종료할 수 있다.If the search result of the Bloom filter is voice or the current level is the last level of the NPT, the Bloom filter search unit 1220 may terminate the chained search of the content name.

해시 테이블 검색부(1230)는 블룸 필터 검색부(1220)의 검색 결과에 따른 해시 테이블에서 콘텐츠 이름을 검색할 수 있다.The hash table search unit 1230 may search for a content name in the hash table according to the search result of the bloom filter search unit 1220. [

블룸 필터 검색부(1220)의 블룸 필터의 검색 결과가 음성인 경우, 해시 테이블 검색부(1230)는 이전 레벨의 블룸 필터에 대응하는 해시 테이블에서 콘텐츠 이름을 검색할 수 있다.If the search result of the bloom filter of the bloom filter search unit 1220 is negative, the hash table search unit 1230 may search for the content name in the hash table corresponding to the bloom filter of the previous level.

또한, 현재 레벨이 NPT의 마지막 레벨인 경우, 해시 테이블 검색부(1230)는 현재 레벨의 블룸 필터에 대응하는 해시 테이블에서 콘텐츠 이름을 검색할 수 있다. 이때, 현재 레벨의 블룸 필터에 대응하는 해시 테이블이 블룸 필터들의 검색 결과에 따른 해시 테이블일 수 있다. 그리고, 현재 레벨의 블룸 필터에 대응하는 해시 테이블에서 콘텐츠 이름이 검색되지 않는 경우, 해시 테이블 검색부(1230)는 백-트래킹(back-tracking)을 통하여 이전 레벨의 블룸 필터에 대응하는 해시 테이블에서 콘텐츠 이름을 검색할 수 있다.Also, if the current level is the last level of the NPT, the hash table search unit 1230 may search for a content name in the hash table corresponding to the current level of Bloom filter. At this time, the hash table corresponding to the bloom filter of the current level may be a hash table according to the search results of the bloom filters. If the content name is not found in the hash table corresponding to the current level bloom filter, the hash table search unit 1230 performs back-tracking on the hash table corresponding to the previous level bloom filter You can search for content names.

즉, 본 발명의 제3 실시예에 따른 이름 검색 장치(120)는 NPT의 레벨들 별로 생성된 블룸 필터들에서 콘텐츠 이름을 연쇄적으로 검색하여 음성의 결과가 나온 경우 혹은 NPT의 마지막 레벨인 경우와 같이 최장 길이 일치 콘텐츠 이름이 있는 레벨을 먼저 식별할 수 있다. 그리고, 이름 검색 장치(120)는 식별한 레벨에 해당하는 해시 테이블에서 콘텐츠 이름을 검색함으로써, 빠르게 콘텐츠 이름을 검색할 수 있다.That is, the name searching apparatus 120 according to the third embodiment of the present invention sequentially searches the content names in the bloom filters generated for each level of the NPT, and when the result of the voice is output, or when the result is the last level of the NPT The level with the longest match content name can be identified first. Then, the name searching apparatus 120 can quickly search for a content name by searching for a content name in a hash table corresponding to the identified level.

도 13은 본 발명의 제3 실시예에 따른 이름 검색 과정에서 사용하는 의사 코드의 일례이다.13 is an example of a pseudo code used in the name searching process according to the third embodiment of the present invention.

블룸 필터 검색부(1220)는 도 13의 코드에 도시된 바와 같이 블룸 필터를 먼저 검색할 수 있다. 그리고, 블룸 필터의 검색 결과가 양성인 경우, 블룸 필터 검색부(1220)는 다음 레벨의 블룸 필터를 연쇄적으로 검색할 수 있다.The bloom filter search unit 1220 can search for the bloom filter first as shown in the code of Fig. When the search result of the Bloom filter is positive, the Bloom filter search unit 1220 can sequentially search Bloom filters of the next level.

이때, 블룸 필터 검색부(1220)는 블룸 필터의 검색 결과로 음성이 출력되거나, NPT의 마지막 레벨의 블룸 필터를 검색할 때까지 연쇄적으로 다음 레벨 블룸 필터를 검색할 수 있다.At this time, the bloom filter search unit 1220 can search for the next level bloom filter in a cascade until a voice is output as a search result of the bloom filter or a bloom filter of the last level of the NPT is searched.

블룸 필터의 검색 결과로 음성이 출력되었다는 것은 콘텐츠 이름과 일치하는 컴포넌트들의 연속된 문자열이 현재 레벨 및 다음 레벨들의 해시 테이블에 존재하지 않는 다는 의미이다. 따라서, 블룸 필터의 검색 결과로 음성이 출력되는 경우, 해시 테이블 검색부(1230)는 이전 레벨의 해시 테이블에서 콘텐츠 이름을 검색할 수 있다.The output of a voice as a search result of the bloom filter means that a continuous string of components matching the content name does not exist in the hash table of the current level and the next level. Therefore, when a voice is output as a search result of the Bloom filter, the hash table search unit 1230 can search for the content name in the hash table of the previous level.

이전 레벨의 해시 테이블에 콘텐츠 이름이 존재하는 경우, 이전 레벨의 블룸 필터 검색 결과가 참-양성이라는 의미이다. 따라서, 해시 테이블 검색부(1230)는 출력 페이스를 반환하고 검색을 종료할 수 있다.If there is a content name in the hash table of the previous level, it means that the previous level Bloom filter search result is true-positive. Thus, the hash table search unit 1230 can return the output face and terminate the search.

그러나, 이전 레벨의 해시 테이블에 콘텐츠 이름이 존재하지 않는 경우, 이전 레벨의 블룸 필터 검색 결과가 거짓-양성이라는 의미이다. 따라서, 해시 테이블 검색부(1230)는 콘텐츠 이름이 검색될 때까지 이전 레벨의 해시 테이블을 연쇄적으로 재 검색하는 백-트래킹을 수행할 수 있다.However, if there is no content name in the hash table of the previous level, it means that the previous level Bloom filter search result is false-positive. Thus, the hash table search unit 1230 can perform back-tracking, which chainedly re-searches the hash table of the previous level until the content name is retrieved.

본 발명의 제3 실시예에 따른 이름 검색 장치(120)는 레벨 별로 생성된 블룸 필터를 연쇄적으로 검색하여 콘텐츠 이름이 존재할 가능성이 있는 최종 레벨을 알아낼 수 있다. 따라서, 본 발명의 제3 실시예에 따른 이름 검색 장치(120)는 백-트래킹이 발생하지 않는 경우, 하나의 입력 당 한 번의 해시 테이블에 접근하여 검색을 완료할 수 있다. The name searching apparatus 120 according to the third embodiment of the present invention can sequentially search the bloom filter generated for each level to find the final level at which a content name may exist. Therefore, the name search apparatus 120 according to the third embodiment of the present invention can access the hash table once per input and complete the search if back-tracking does not occur.

도 14는 본 발명의 일실시예에 따른 이름 검색 과정에서 해시 테이블에 접근한 회수의 일례이다.FIG. 14 is an example of the number of times the hash table is accessed in the name search process according to an embodiment of the present invention.

도 14는 CCN 콘텐츠 이름과 같이 계층적 특성을 가지는 URL을 이용하여 본 발명의 제1 실시예, 제2 실시예 및 제3 실시예의 성능 평가를 수행한 결과의 일례이다.FIG. 14 is an example of a result of performance evaluation of the first, second, and third embodiments of the present invention using a URL having a hierarchical characteristic such as a CCN content name.

이때, 제1 실시예에 따른 이름 검색 장치(120)가 수행하는 해싱 기반-NPT, 제2 실시예에 따른 이름 검색 장치(120)가 수행하는 NPT-BF 알고리즘 및 제3 실시예에 따른 이름 검색 장치(120)가 수행하는 NPT-BF-Chaining 알고리즘은 10,000 개, 50,000 개, 100,000 개, 또는 300,000 개의 콘텐츠 이름을 이용해 시뮬레이션될 수 있다. 이때, 콘텐츠 이름의 개수를 각각 10k, 50k, 100k, 300k로 간단하게 표현될 수 있다.In this case, the hashing-based NPT performed by the name searching apparatus 120 according to the first embodiment, the NPT-BF algorithm performed by the name searching apparatus 120 according to the second embodiment, The NPT-BF-Chaining algorithm performed by the device 120 may be simulated using 10,000, 50,000, 100,000, or 300,000 content names. At this time, the number of content names can be simply expressed as 10k, 50k, 100k, and 300k, respectively.

또한, 콘텐츠 이름을 검색할 경우, 각각 30,000 개, 150,000 개, 300,000 개, 또는 900,000 개의 콘텐츠 이름을 입력으로 이용할 수 있다.Also, when searching for content names, 30,000, 150,000, 300,000, or 900,000 content names, respectively, are available as input.

표 1은 해시 테이블에 저장된 엔트리와 해시 인덱스 충돌로 인해 연결 리스트에 저장된 엔트리들의 정보 구조를 나타내고 있다. 표 2는 각각의 실험에서 level-1부터 level-8까지에 저장된 콘텐츠 이름들의 개수를 나타내고 있다. 표 3은 구축된 트라이의 특성을 보인다.Table 1 shows the information structure of the entries stored in the linked list due to the hash index conflict and the entries stored in the hash table. Table 2 shows the number of content names stored in level-1 to level-8 in each experiment. Table 3 shows the characteristics of the trie constructed.

이름 검색 장치(120)는 해시 함수로 CRC-64 생성기를 사용할 수 있다. 이때, CRC 내의 모든 플립-플랍(flip-flop)은 0으로 초기화 되어 있으며 입력 값이 한 비트씩 들어오면서 플립-플랍에 저장된 값과 차례로 XOR할 수 있다. 그리고, 입력 비트열의 마지막 비트까지 들어오면 CRC 생성기의 연산 수행을 종료하고 플립-플랍에 저장되어 있는 값을 CRC 코드로 출력할 수 있다.The name search device 120 may use a CRC-64 generator as a hash function. At this time, all the flip-flops in the CRC are initialized to zero, and input values are input one bit at a time, and XOR can be sequentially performed with the values stored in the flip-flops. When the last bit of the input bit string is received, the operation of the CRC generator is terminated and the value stored in the flip-flop can be output as the CRC code.

또한, 블룸 필터의 프로그래밍에 사용된 해시 함수의 개수 k는 블룸 필터의 크기에 따라서 정해질 수 있다. 만약 컴포넌트 하나당 k개의 해시 함수를 사용했다면 프로그래밍 해야 할 위치 색인을 k개 얻을 수 있다.In addition, the number k of hash functions used in the programming of the Bloom filter can be determined according to the size of the Bloom filter. If you have used k hash functions per component, you can get k position indexes to be programmed.

그리고, 블룸 필터에 저장되어야 하는 전체 노드의 개수를 N이라고 할 때 N보다 큰 2의 배수를 블룸 필터의 기본크기로 정하면, 블룸 필터의 기본크기인 N'는 수학식 1로 결정될 수 있다.If the number of all nodes to be stored in the Bloom filter is N, if N is a multiple of 2 larger than N, the basic size of the Bloom filter, N ', can be determined by Equation (1).

또한, 기본 블룸 필터의 크기에 확장배수를 곱하여 크기가 M인 블룸 필터를 사용할 경우, 프로그래밍 되는 색인의 개수도 늘어나야 올바른 성능을 얻을 수 있다. 이때, 프로그래밍 해야 할 색인은 블룸 필터의 크기에 비례하여 증가할 수 있다. 예를 들어, 블룸 필터의 해시 함수의 개수 k는 수학식 2로 결정될 수 있다.Also, if you use a Bloom filter with a size of M by multiplying the size of the default Bloom filter by an expansion multiple, the number of indexes that are programmed must also be increased to get the right performance. At this time, the index to be programmed may increase in proportion to the size of the Bloom filter. For example, the number k of hash functions of the Bloom filter can be determined by Equation (2).

블룸 필터의 크기를 기본 크기 N’에 확장배수 4, 8, 16을 곱하여 4N’, 8N’, 16N’으로 변화시키는 경우, 블룸 필터의 크기가 FIB 검색 속도에 어떤 영향을 주는지 확인할 수 있다. If the size of the Bloom filter is changed to 4N ', 8N', 16N 'by multiplying the basic size N' by the expansion multiples of 4, 8, and 16, it is possible to confirm how the size of the Bloom filter affects the FIB search speed.

표 4는 10,000개의 콘텐츠 이름을 사용하여 구축하고 구축에 사용된 10,000개의 콘텐츠 이름과 구축에 사용되지 않은 20,000개의 콘텐츠 이름을 추가해 총 30,000개의 콘텐츠 이름으로 검색한 결과일 수 있다.Table 4 can be the result of a search with a total of 30,000 content names, using 10,000 content names to build and add 10,000 content names used in the build and 20,000 content names not used in the build.

표 4에서 해싱기반-NPT 알고리즘은 평균 2.11번 해시 테이블에 접근하였는데 이는 10,000개의 콘텐츠 이름 중 약 90%가 level-2에 저장되어 있어 level-3에서 일치하는 노드가 없는 경우 검색을 종료할 수 있기 때문이다. In Table 4, the hashing-based NPT algorithm averaged 2.11 hash tables, which means that about 90% of the 10,000 content names are stored in level-2, so that if there are no matching nodes in level-3, Because.

표 4에서 NPT-BF 알고리즘은 블룸 필터의 크기가 4N’, 8N’, 16N’ 일 때 해시 테이블에 평균적으로 1.46번, 1.43번, 1.43번 접근하여 출력 페이스를 찾았다. 블룸 필터의 크기가 클수록 전체 해시 테이블 접근 횟수가 43771번에서 42908번으로, 그리고 42860번으로 감소하였다. 그리고 거짓-양성의 수는 4N’일 때 884번 이었으나 8N’일 때는 47번으로 감소하고 16N’일 때는 0번이 된다. 거짓 양성이 줄어든 숫자만큼 해시 테이블 접근 횟수가 함께 감소하였다. In Table 4, the NPT-BF algorithm approaches the hash table 1.46 times, 1.43 times, 1.43 times when the Bloom filter size is 4N ', 8N', 16N ', and finds the output face. As the size of Bloom filter increases, the total number of hash table accesses decreases from 43771 to 42908 and to 42860. And the number of false-positive is 884 when it is 4N ', but it decreases to 47 when it is 8N' and it becomes 0 when it is 16N '. The number of hash table accesses decreased as the number of false positives decreased.

반면, 음성의 결과가 나올 때까지 블룸 필터 쿼리를 연쇄적으로 진행한 후에 해시 테이블에 접근하는 NPT-BF-Chaining 알고리즘은 평균 0.997 접근하였다. 즉, 대부분 한 번만 해시 테이블에 접근하거나 아예 접근하지 않았다. On the other hand, the NPT-BF-Chaining algorithm approaching the hash table after approx. In other words, most once did not access the hash table or access it at all.

즉, NPT-BF-Chaining 알고리즘은 선-필터 검색과정을 통해 콘텐츠 이름이 존재할 가능성이 있는 최장 레벨을 알아낼 수 있기 때문에 최장 레벨의 해시 테이블에 접근함으로써 단 한 번의 오프-칩 접근으로 원하는 검색 결과를 찾아낼 수 있었다. 또한 첫 번째 레벨의 블룸 필터 검색 결과가 음성인 경우, 해시 테이블에 콘텐츠 이름이 존재하지 않는다는 의미이므로, 해시 테이블에 접근할 필요가 없게 되어 단 한 번도 오프-칩 메모리에 접근하지 않을 수 있다. In other words, the NPT-BF-Chaining algorithm can find the longest possible level of content name through the pre-filter search process. Therefore, by accessing the longest level hash table, I could find it. Also, if the first-level Bloom filter search result is speech, it means that there is no content name in the hash table, so there is no need to access the hash table, and the user may not access the off-chip memory even once.

거짓-양성이 일어나지 않으면 해시 테이블에 한 번만 검색해서 결과를 찾을 수 있지만 거짓-양성이 일어날 때에는 거짓-양성이 일어난 만큼 백-트래킹을 해야 하며 백-트래킹을 많이 할수록 해시 테이블 검색 횟수가 증가해 검색 성능을 저하시킨다. False - If the test does not occur, you can search the hashtable only once and find the result, but when false-positive occurs, you need to backtrack as much as false-positive. As the backtracking increases, the number of hashtable searches increases Degrade performance.

표 5 내지 표 7은 콘텐츠 이름의 개수가 각각 50k, 100k, 300k인 경우의 실험 결과일 수 있다. 표 5 내지 표 7에 따르면, 거짓-양성이 가장 많이 일어나는 4N’ 블룸 필터에서도 최대 3번의 백-트래킹이 일어나는 것으로 확인될 수 있다.Tables 5 to 7 can be experimental results when the number of content names is 50k, 100k, and 300k, respectively. According to Tables 5 to 7, it can be confirmed that up to three back-tracking occur even in the 4N 'bloom filter in which the most false-positive occurs.

또한, 블룸 필터의 메모리 사용량은 빌드에 사용되는 입력의 개수가 같을 때 NPT-BF 알고리즘과 NPT-BF-Chaining 알고리즘에서 동일하다. 왜냐하면 블룸 필터와 해시 테이블은 동일하고 블룸 필터와 해시 테이블의 검색 방식만 다르기 때문이다. In addition, the memory usage of the Bloom filter is the same in the NPT-BF and NPT-BF-Chaining algorithms when the number of inputs used in the build is the same. This is because Bloom filters and hash tables are identical, and Bloom filters and hash tables are different.

도 14는 블룸 필터 사이즈를 16N으로 고정하고 프로그래밍에 사용된 컴포넌트의 개수를 증가시킬 경우, 해시 테이블에 접근한 총 횟수를 각 알고리즘 별로 나타낸 그래프이다. 도 14에 도시된 바에 따르면, 입력 트레이스가 적을수록 해시 테이블에 접근하는 횟수도 적을 수 있다. 또한 NPT, NPT-BF, NPT-BF-Chaining 알고리즘 순으로 해시 테이블의 접근 횟수가 감소함을 볼 수 있다. 14 is a graph showing the total number of accesses to the hash table by each algorithm when the Bloom filter size is fixed to 16N and the number of components used for programming is increased. As shown in FIG. 14, the smaller the number of input traces, the smaller the number of accesses to the hash table. In addition, it can be seen that the number of hash table accesses decreases in the order of NPT, NPT-BF, and NPT-BF-Chaining algorithm.

도 15는 본 발명의 일실시예에 따른 이름 검색 과정에서 해시 테이블의 메모리 요구량의 일례이다.15 is an example of a memory requirement of a hash table in a name search process according to an embodiment of the present invention.

표 8은 NPT의 레벨 별 해시 테이블의 데이터 구조의 일례이다. 또한, 표 9는 콘텐츠 이름의 개수에 따른 해시 테이블의 메모리 요구량일 수 있다. 그리고, 도 15는 표 9를 그래프로 나타낸 도면일 수 있다. 이때, 해시 테이블의 크기는 빌드에 사용되는 입력의 개수가 같다면 NPT, NPT-BF, NPT-BF-Chaining 알고리즘에서 동일할 수 있다. 그리고, 콘텐츠 이름의 개수에 비례하여 해시 테이블의 크기가 증가할 수 있다.Table 8 is an example of the data structure of the level-specific hash table of the NPT. Table 9 may be the memory requirement of the hash table according to the number of content names. 15 is a graph showing Table 9. In this case, the size of the hash table can be the same in the NPT, NPT-BF, and NPT-BF-Chaining algorithms if the number of inputs used in the build is the same. The size of the hash table can be increased in proportion to the number of the content names.

도 16은 본 발명의 제1 실시예에 따른 이름 검색 방법을 도시한 플로우차트이다.16 is a flowchart illustrating a name search method according to the first embodiment of the present invention.

단계(1610)에서 콘텐츠 이름 변환부(510)는 해시 함수를 사용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환 할 수 있다. 이때, 콘텐츠 이름 변환부(510)는 해시 테이블 생성부(111)가 NPT의 레벨들 별로 해시 테이블을 생성하는 과정에서 해시 인덱스의 생성에 이용된 해시 함수를 이용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환할 수 있다. 또한, NPT의 레벨이 두 번째 레벨 이상인 경우, 콘텐츠 이름 변환부(510)는 이전 레벨에 대응하는 콘텐츠 이름의 컴포넌트와 현재 레벨에 대응하는 콘텐츠 이름의 컴포넌트가 연속된 문자열을 해시 함수로 변환할 수 있다.In step 1610, the content name translator 510 may use a hash function to convert the component of the content name corresponding to each of the levels of the NPT. At this time, the hash table generation unit 111 generates a hash table using the hash function used for generating the hash index in the process of generating the hash table for each level of the NPT, You can convert the component of the content name. If the level of the NPT is equal to or higher than the second level, the content name conversion unit 510 can convert the string of the components of the content name corresponding to the previous level and the content of the content name corresponding to the current level into a hash function have.

단계(1620)에서 해시 테이블 검색부(520)는 단계(1610)에서 해시 함수로 변환한 컴포넌트를 NPT의 레벨들 별로 생성된 해시 테이블에서 검색할 수 있다.In step 1620, the hash table search unit 520 may search the hash table created in step 1610 for the components converted into the hash function for each level of the NPT.

단계(1630)에서 해시 테이블 검색부(520)는 단계(1620)에서 콘텐츠 이름의 컴포넌트가 검색되었는지 여부를 확인할 수 있다. 단계(1620)에서 콘텐츠 이름의 컴포넌트가 검색된 경우, 해시 테이블 검색부(520)는 단계(1640)을 수행할 수 있다. 또한, 단계(1620)에서 콘텐츠 이름의 컴포넌트가 검색되지 않은 경우, 해시 테이블 검색부(520)는 단계(1660)을 수행할 수 있다.In step 1630, the hash table search unit 520 can check in step 1620 whether a component of the content name has been retrieved. If the component of the content name is retrieved in step 1620, the hash table retrieval unit 520 may perform step 1640. [ Also, if the component of the content name is not retrieved at step 1620, the hash table retrieval unit 520 may perform step 1660. [

단계(1640)에서 해시 테이블 검색부(520)는 현재 레벨이 NPT의 마지막 레벨인지 여부를 확인할 수 있다. 현재 레벨이 NPT의 마지막 레벨인 경우, 해시 테이블 검색부(520)는 단계(1660)을 수행할 수 있다. 또한, 현재 레벨이 NPT의 마지막 레벨이 아닌 경우, 해시 테이블 검색부(520)는 단계(1650)을 수행할 수 있다.In step 1640, the hash table search unit 520 may check whether the current level is the last level of the NPT. If the current level is the last level of the NPT, the hash table search unit 520 may perform step 1660. [ Also, if the current level is not the last level of the NPT, the hash table search unit 520 may perform step 1650.

단계(1650)에서 해시 테이블 검색부(520)는 NPT의 레벨을 증가시킬 수 있다. 즉, 해시 테이블 검색부(520)는 다음 레벨의 해시 테이블에서 단계(1610) 내지 단계(1640)을 수행할 수 있다.In step 1650, the hash table search unit 520 may increase the level of the NPT. That is, the hash table search unit 520 may perform steps 1610 to 1640 in the next level hash table.

단계(1660)에서 해시 테이블 검색부(520)는 마지막으로 콘텐츠 이름이 검색된 레벨에 따라 콘텐츠 이름을 식별하고, 식별된 콘텐츠 이름에 해당하는 출력 페이스로 요청 패킷을 전달할 수 있다. 이때, 단계(1630)에서 콘텐츠 이름이 검색되지 않은 경우, 마지막으로 콘텐츠 이름이 검색된 이전 레벨의 해시 테이블에 포함된 출력 페이스로 상기 콘텐츠 이름에 대응하는 콘텐츠 요청 패킷을 전송할 수 있다.In step 1660, the hash table search unit 520 may finally identify the content name according to the level at which the content name is searched, and deliver the request packet at the output face corresponding to the identified content name. At this time, if the content name is not retrieved in step 1630, the content request packet corresponding to the content name may be transmitted at the output face included in the hash table of the previous level where the content name was last searched.

그리고, 현재 레벨이 NPT의 마지막 레벨인 경우, 마지막으로 콘텐츠 이름이 검색된 레벨은 현재 레벨이고, 해시 테이블 검색부(520)는 현재 레벨의 해시 테이블에서 콘텐츠 이름을 검색하여 식별할 수 있다.If the current level is the last level of the NPT, the level at which the content name is finally searched is the current level, and the hash table search unit 520 can search for and identify the content name in the hash table of the current level.

도 17은 본 발명의 제2 실시예에 따른 이름 검색 방법을 도시한 플로우차트이다.17 is a flowchart illustrating a name search method according to a second embodiment of the present invention.

단계(1710)에서 콘텐츠 이름 변환부(810)는 해시 함수를 사용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환 할 수 있다. 이때, 콘텐츠 이름 변환부(810)는 해시 테이블 생성부(111)가 NPT의 레벨들 별로 해시 테이블을 생성하는 과정에서 해시 인덱스의 생성에 이용된 해시 함수 및 블룸 필터 생성부(112)가 NPT의 레벨들 별로 해시 테이블에 대응하는 블룸 필터를 생성하는 과정에서 블룸 필터의 생성에 이용된 해시 함수를 이용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환할 수 있다.In step 1710, the content name conversion unit 810 may convert the component of the content name corresponding to each of the levels of the NPT using a hash function. In this case, the hash table generation unit 111 generates a hash function used for generating a hash index and a hash function used by the bloom filter generation unit 112 in the process of generating a hash table for each level of the NPT, The component of the content name corresponding to each level of the NPT can be converted using the hash function used for generating the Bloom filter in the process of generating the Bloom filter corresponding to the hash table for each level.

단계(1720)에서 블룸 필터 검색부(820)는 NPT의 레벨들 별로 생성된 블룸 필터로 단계(1710)에서 변환된 콘텐츠 이름을 검색할 수 있다. 이때, 블룸 필터의 출력이 양성인 경우, 블룸 필터 검색부(820)는 콘텐츠 이름이 검색되었다고 판단할 수 있다. 또한, 블룸 필터의 출력이 음성인 경우, 블룸 필터 검색부(820)는 콘텐츠 이름이 검색되지 않았다고 판단할 수 있다.In step 1720, the bloom filter search unit 820 may search for the content name converted in step 1710 with the bloom filter generated for each level of the NPT. At this time, if the output of the bloom filter is positive, the bloom filter search unit 820 may determine that the content name is searched. Also, when the output of the bloom filter is voice, the bloom filter search unit 820 can determine that the content name is not found.

단계(1730)에서 해시 테이블 검색부(830)는 단계(1720)에서 콘텐츠 이름이 검색되었는지 여부를 확인할 수 있다. 단계(1720)에서 콘텐츠 이름의 컴포넌트가 검색된 경우, 해시 테이블 검색부(830)는 단계(1740)을 수행할 수 있다. 또한, 단계(1720)에서 콘텐츠 이름이 검색되지 않은 경우, 해시 테이블 검색부(830)는 단계(1780)을 수행할 수 있다.In step 1730, the hash table search unit 830 can check in step 1720 whether the content name is retrieved. If the component of the content name is retrieved at step 1720, the hash table retrieval unit 830 may perform step 1740. [ If the content name is not found in step 1720, the hash table search unit 830 may perform step 1780. [

단계(1740)에서 해시 테이블 검색부(830)는 블룸 필터에 대응하는 해시 테이블에서 콘텐츠 이름을 검색할 수 있다.In step 1740, the hash table search unit 830 may retrieve the content name from the hash table corresponding to the Bloom filter.

단계(1750)에서 해시 테이블 검색부(830)는 단계(1740)에서 콘텐츠 이름의 컴포넌트가 검색되었는지 여부를 확인할 수 있다. 단계(1740)에서 콘텐츠 이름의 컴포넌트가 검색된 경우, 해시 테이블 검색부(830)는 단계(1760)을 수행할 수 있다. 또한, 단계(1740)에서 콘텐츠 이름의 컴포넌트가 검색되지 않은 경우, 해시 테이블 검색부(830)는 단계(1780)을 수행할 수 있다.In step 1750, the hash table search unit 830 can check in step 1740 whether a component of the content name has been retrieved. If the component of the content name is retrieved at step 1740, the hash table retrieval unit 830 may perform step 1760. [ In addition, if the component of the content name is not retrieved at step 1740, the hash table retrieval unit 830 may perform step 1780. [

단계(1760)에서 해시 테이블 검색부(830)는 현재 레벨이 NPT의 마지막 레벨인지 여부를 확인할 수 있다. 현재 레벨이 NPT의 마지막 레벨인 경우, 해시 테이블 검색부(830)는 단계(1780)을 수행할 수 있다. 또한, 현재 레벨이 NPT의 마지막 레벨이 아닌 경우, 해시 테이블 검색부(830)는 단계(1770)을 수행할 수 있다.In step 1760, the hash table search unit 830 can check whether the current level is the last level of the NPT. If the current level is the last level of the NPT, the hash table search unit 830 may perform step 1780. [ In addition, if the current level is not the last level of the NPT, the hash table search unit 830 may perform step 1770. [

단계(1770)에서 해시 테이블 검색부(830)는 NPT의 레벨을 증가시킬 수 있다. 즉, 해시 테이블 검색부(830)는 다음 레벨의 해시 테이블에서 단계(1710) 내지 단계(1760)을 수행할 수 있다.In step 1770, the hash table search unit 830 may increase the level of the NPT. That is, the hash table search unit 830 may perform steps 1710 to 1760 in the next level hash table.

단계(1780)에서 해시 테이블 검색부(830)는 마지막으로 콘텐츠 이름이 검색된 레벨에 따라 콘텐츠 이름을 식별하고, 식별된 콘텐츠 이름에 해당하는 출력 페이스로 요청 패킷을 전달할 수 있다. 이때, 단계(1750)에서 콘텐츠 이름이 검색되지 않은 경우, 마지막으로 콘텐츠 이름이 검색된 이전 레벨의 해시 테이블에 포함된 출력 페이스로 상기 콘텐츠 이름에 대응하는 콘텐츠 요청 패킷을 전송할 수 있다.In step 1780, the hash table search unit 830 may finally identify the content name according to the level at which the content name is searched, and deliver the request packet at the output face corresponding to the identified content name. At this time, if the content name is not found in step 1750, the content request packet corresponding to the content name may be transmitted to the output face included in the hash table of the previous level where the content name was searched last.

그리고, 현재 레벨이 NPT의 마지막 레벨인 경우, 마지막으로 콘텐츠 이름이 검색된 레벨은 현재 레벨이고, 해시 테이블 검색부(830)는 현재 레벨의 해시 테이블에서 콘텐츠 이름을 검색하여 식별할 수 있다.If the current level is the last level of the NPT, the level at which the content name is searched last is the current level, and the hash table search unit 830 can search for and identify the content name in the hash table of the current level.

도 18은 본 발명의 제3 실시예에 따른 이름 검색 방법을 도시한 플로우차트이다.18 is a flowchart illustrating a method for searching for names according to a third embodiment of the present invention.

단계(1810)에서 콘텐츠 이름 변환부(1210)는 해시 함수를 사용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환 할 수 있다. 이때, 콘텐츠 이름 변환부(1210)는 해시 테이블 생성부(111)가 NPT의 레벨들 별로 해시 테이블을 생성하는 과정에서 해시 인덱스의 생성에 이용된 해시 함수 및 블룸 필터 생성부(112)가 NPT의 레벨들 별로 해시 테이블에 대응하는 블룸 필터를 생성하는 과정에서 블룸 필터의 생성에 이용된 해시 함수를 이용하여 NPT의 레벨들 각각에 대응하는 콘텐츠 이름의 컴포넌트를 변환할 수 있다.In step 1810, the content name conversion unit 1210 may convert the component of the content name corresponding to each of the levels of the NPT using a hash function. At this time, the content name conversion unit 1210 converts the hash function used for generating the hash index and the hash function used by the bloom filter generation unit 112 in the process of generating the hash table for each level of the NPT by the hash table generation unit 111, The component of the content name corresponding to each level of the NPT can be converted using the hash function used for generating the Bloom filter in the process of generating the Bloom filter corresponding to the hash table for each level.

단계(1820)에서 블룸 필터 검색부(1220)는 NPT의 레벨들 별로 생성된 블룸 필터로 단계(1810)에서 변환된 콘텐츠 이름을 검색할 수 있다. 이때, 블룸 필터의 출력이 양성인 경우, 블룸 필터 검색부(1220)는 콘텐츠 이름이 검색되었다고 판단할 수 있다. 또한, 블룸 필터의 출력이 음성인 경우, 블룸 필터 검색부(1220)는 콘텐츠 이름이 검색되지 않았다고 판단할 수 있다.In step 1820, the bloom filter search unit 1220 may retrieve the converted content name in step 1810 with the bloom filter generated for each level of the NPT. At this time, if the output of the bloom filter is positive, the bloom filter search unit 1220 can determine that the content name is searched. When the output of the Bloom filter is voice, the Bloom filter search unit 1220 can determine that the content name is not found.

단계(1830)에서 블룸 필터 검색부(1220)는 단계(1820)에서 콘텐츠 이름이 검색되었는지 여부를 확인할 수 있다. 단계(1820)에서 콘텐츠 이름의 컴포넌트가 검색된 경우, 블룸 필터 검색부(1220)는 단계(1840)을 수행할 수 있다. 또한, 단계(1820)에서 콘텐츠 이름이 검색되지 않은 경우, 블룸 필터 검색부(1220)는 단계(1835)을 수행할 수 있다.In step 1830, the bloom filter search unit 1220 can check in step 1820 whether or not the content name has been retrieved. If a component of the content name is retrieved in step 1820, the bloom filter searcher 1220 may perform step 1840. [ Also, if the content name is not retrieved in step 1820, the bloom filter search unit 1220 may perform step 1835.

단계(1835)에서 해시 테이블 검색부(1230)는 NPT의 레벨을 감소시킬 수 있다. 즉, 해시 테이블 검색부(1230)는 이전 레벨의 해시 테이블에서 단계(1860) 내지 단계(1870)을 수행하여 이전 레벨의 해시 테이블 중에서 콘텐츠 이름을 연쇄적으로 검색할 수 있다.In step 1835, the hash table search unit 1230 may reduce the level of the NPT. That is, the hash table retrieving unit 1230 may perform the steps 1860 to 1870 in the hash table of the previous level to sequentially retrieve the content name from the hash table of the previous level.

단계(1840)에서 블룸 필터 검색부(1220)는 현재 레벨이 NPT의 마지막 레벨인지 여부를 확인할 수 있다. 현재 레벨이 NPT의 마지막 레벨인 경우, 블룸 필터 검색부(1220)는 단계(1860)을 수행할 수 있다. 또한, 현재 레벨이 NPT의 마지막 레벨이 아닌 경우, 블룸 필터 검색부(1220)는 단계(1850)을 수행할 수 있다.In step 1840, the bloom filter search unit 1220 can check whether the current level is the last level of the NPT. If the current level is the last level of the NPT, the bloom filter search unit 1220 may perform step 1860. Also, if the current level is not the last level of NPT, the Bloom filter search unit 1220 may perform step 1850. [

단계(1850)에서 블룸 필터 검색부(1220)는 NPT의 레벨을 증가시킬 수 있다. 즉, 블룸 필터 검색부(1220)는 다음 레벨의 블룸 필터에서 단계(1810) 내지 단계(1820)을 수행하여 콘텐츠 이름을 연쇄적으로 검색할 수 있다. In step 1850, the bloom filter search unit 1220 may increase the level of the NPT. That is, the bloom filter search unit 1220 may perform the steps 1810 to 1820 in the bloom filter of the next level to sequentially search for the content name.

단계(1860)에서 해시 테이블 검색부(1230)는 블룸 필터 검색부(1220)의 검색 결과에 따른 해시 테이블에서 콘텐츠 이름을 검색할 수 있다. 구체적으로, 단계(1830)에서 블룸 필터 검색부(1220)의 블룸 필터의 검색 결과가 음성인 경우, 해시 테이블 검색부(1230)는 이전 레벨의 블룸 필터에 대응하는 해시 테이블에서 콘텐츠 이름을 검색할 수 있다. 또한, 현재 레벨이 NPT의 마지막 레벨인 경우, 해시 테이블 검색부(1230)는 현재 레벨의 블룸 필터에 대응하는 해시 테이블에서 콘텐츠 이름을 검색할 수 있다. In step 1860, the hash table search unit 1230 may search for a content name in the hash table according to the search result of the bloom filter search unit 1220. [ Specifically, if the search result of the bloom filter of the bloom filter search unit 1220 is negative in step 1830, the hash table search unit 1230 searches the hash table corresponding to the previous level bloom filter for the content name . Also, if the current level is the last level of the NPT, the hash table search unit 1230 may search for a content name in the hash table corresponding to the current level of Bloom filter.

단계(1870)에서 해시 테이블 검색부(1230)는 단계(1860)에서 콘텐츠 이름이 검색되었는지 여부를 확인할 수 있다. 단계(1860)에서 콘텐츠 이름이 검색된 경우, 해시 테이블 검색부(1230)는 단계(1890)을 수행할 수 있다. 또한, 단계(1860)에서 콘텐츠 이름이 검색되지 않은 경우, 해시 테이블 검색부(1230)는 단계(1880)을 수행할 수 있다.In step 1870, the hash table search unit 1230 may check in step 1860 whether the content name has been retrieved. If the content name is retrieved in step 1860, the hash table retrieval unit 1230 may perform step 1890. If the content name is not found in step 1860, the hash table search unit 1230 may perform step 1880. [

단계(1880)에서 해시 테이블 검색부(1230)는 백 트래킹을 수행할 수 있다. 구체적으로, 단계(1830)에서 콘텐츠 이름이 검색되고, 단계(1870)에서 콘텐츠 이름이 검색되지 않는 경우, 해시 테이블 검색부(1230)는 단계(1830)의 검색 결과를 거짓 양성으로 판단할 수 있다. 이때, 해시 테이블 검색부(1230)는 NPT의 레벨을 감소시켜 백트래킹을 수행할 수 있다. In step 1880, the hash table search unit 1230 may perform backtracking. Specifically, if the content name is retrieved in step 1830 and the content name is not retrieved in step 1870, the hash table retrieval section 1230 can judge the retrieval result of step 1830 as false positive . At this time, the hash table search unit 1230 may perform back tracking by reducing the level of the NPT.

단계(1890)에서 해시 테이블 검색부(1230)는 단계(1860)에서 검색된 콘텐츠 이름을 식별하고, 식별된 콘텐츠 이름에 해당하는 출력 페이스로 요청 패킷을 전달할 수 있다. In step 1890, the hash table search unit 1230 identifies the content name retrieved in step 1860 and delivers the request packet to the output face corresponding to the identified content name.

본 발명은 해시 테이블을 이용하여 NPT에 기초한 콘텐츠 이름을 검색할 수 있다. 또한, 본 발명은 블룸 필터의 검색 결과에 따라 해시 테이블의 검색 여부를 결정함으로써, 해시 테이블의 접근 회수를 감소시켜 검색 속도를 향상 시킬 수 있다.The present invention can retrieve the NPT-based content name using a hash table. In addition, according to the present invention, it is possible to improve the retrieval speed by decreasing the number of accesses to the hash table by determining whether to search the hash table according to the search result of the Bloom filter.

그리고, 본 발명은 NPT의 레벨 별로 생성된 블룸 필터를 연속으로 검색하여 최종 레벨을 검색하고, 최종 레벨의 해시 테이블을 검색함으로써, 해시 테이블의 접근 회수를 최소화시킬 수도 있다.The present invention can minimize the number of hash table accesses by continuously searching for the bloom filter generated for each level of the NPT, searching for the final level, and searching the hash table of the final level.

이상과 같이 본 발명은 비록 한정된 실시예와 도면에 의해 설명되었으나, 본 발명은 상기의 실시예에 한정되는 것은 아니며, 본 발명이 속하는 분야에서 통상의 지식을 가진 자라면 이러한 기재로부터 다양한 수정 및 변형이 가능하다.While the invention has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims. This is possible.

그러므로, 본 발명의 범위는 설명된 실시예에 국한되어 정해져서는 아니 되며, 후술하는 특허청구범위뿐 아니라 이 특허청구범위와 균등한 것들에 의해 정해져야 한다.Therefore, the scope of the present invention should not be limited to the described embodiments, but should be determined by the equivalents of the claims, as well as the claims.

110: 이름 검색 정보 구축 장치
120: 이름 검색 장치
820: 블룸 필터 검색부
830: 해시 테이블 검색부110: name search information construction apparatus
120: name search device
820: Bloom filter search unit
830: Hash table search unit

Claims

A name search method using a name prefix trie (NPT) comprising a plurality of levels,
Transforming a component of a content name corresponding to each of the levels of the NPT using a hash function; And
Searching for a transformed component using the hash function in a hash table generated for each level of NPT
Lt; / RTI >
Wherein transforming the component comprises:
And a component of the content name corresponding to the current level and a component of the content name corresponding to the current level are converted using the hash function when the level of the NPT is equal to or higher than the second level.

The method according to claim 1,
Wherein transforming the component comprises:
A name retrieval method for transforming a component of a content name corresponding to each level of an NPT using a hash function used for generating a hash index in a hash table generated for each level of the NPT.

delete

The method according to claim 1,
The method of claim 1,
A hash index in which a string of components of a content name corresponding to a previous level and a component of a content name corresponding to a current level are converted into a hash function is retrieved from a hash table corresponding to a current level.

A name search method using a name prefix trie (NPT) comprising a plurality of levels,
Transforming a component of a content name corresponding to each of the levels of the NPT using a hash function;
Retrieving a transformed component using the hash function in a hash table generated for each level of the NPT; And
If the converted component is not found using the hash function in the hash table corresponding to the current level, the content request packet corresponding to the content name is transmitted in the last retrieved output face contained in the hash table of the previous level step
&Lt; / RTI >

A name search method using a name prefix trie (NPT) comprising a plurality of levels,
Retrieving a content name with a Bloom filter generated for each level of the NPT; And
Retrieving the content name from the hash table corresponding to the Bloom filter based on the search result of the Bloom filter
Lt; / RTI >
The step of retrieving a content name with the Bloom filter comprises:
And searching for a content name by a Bloom filter of the next level of the NPT when the content name is retrieved from a hash table corresponding to a Bloom filter of a current level of the NPT.

delete

A name search method using a name prefix trie (NPT) comprising a plurality of levels,
Retrieving a content name with a Bloom filter generated for each level of the NPT; And
Retrieving the content name from the hash table corresponding to the Bloom filter based on the search result of the Bloom filter
Lt; / RTI >
The step of retrieving the content name from the hash table includes:
Retrieving the content name from a hash table corresponding to the Bloom filter if the search result of the Bloom filter is positive; And
Ending the search if the search result of the Bloom filter is voice or the content name is not found in the hash table
&Lt; / RTI >

9. The method of claim 8,
The step of terminating the search comprises:
And transmits the content request packet corresponding to the content name to the output face included in the hash table in which the content name was last searched.

A name search method using a name prefix trie (NPT) comprising a plurality of levels,
Retrieving a content name with a Bloom filter generated for each level of the NPT; And
Retrieving the content name from the hash table corresponding to the Bloom filter based on the search result of the Bloom filter
Lt; / RTI >
Wherein the bloom filter comprises:
And a component of the content name corresponding to the previous level and a component corresponding to the current level are consecutive.

A name search method using a name prefix trie (NPT) comprising a plurality of levels,
Categorizing the content names in the bloom filters generated for each level of the NPT; And
Retrieving the content name from a hash table according to a search result of the Bloom filters
Lt; / RTI >
The method of claim 1,
Searching for a component included in the content name with a Bloom filter corresponding to the current level of the NPT;
If the search result of the Bloom filter is positive, searching for a component included in the content name with a Bloom filter of the next level of the NPT; And
Terminating the chained search of the content name if the search result of the Bloom filter is voice or the current level is the last level of the NPT
&Lt; / RTI >

delete

12. The method of claim 11,
The step of retrieving the content name from the hash table includes:
And searching the hash table corresponding to the bloom filter of the previous level for the content name if the search result of the bloom filter is negative.

12. The method of claim 11,
The step of retrieving the content name from the hash table includes:
Searching the content name in a hash table corresponding to a bloom filter of the current level if the search result of the bloom filter is positive and the current level is the last level of the NPT.

A name search method using a name prefix trie (NPT) comprising a plurality of levels,
Categorizing the content names in the bloom filters generated for each level of the NPT; And
Retrieving the content name from a hash table according to a search result of the Bloom filters
Lt; / RTI >
The step of retrieving the content name from the hash table includes:
And if the content name is not found in the hash table according to the search result of the bloom filters, the content name is searched in the hash table corresponding to the bloom filter of the previous level.