이름 프리픽스 검색 장치가 수행하는 우선순위 이름 프리픽스 트라이 기반의 비트맵 생성 방법에 있어서,이름 프리픽스 검색 장치의 프로세서가 이름 프리픽스 트라이(Name Prefix Trie, NPT)에서 도출된 우선순위 노드 및 비우선순위 노드를 포함하는 우선순위-이름 프리픽스 트라이(Priority-Name Prefix Trie, P-NPT)를 결정하는 단계;이름 프리픽스 검색 장치의 프로세서가 상기 우선순위-이름 프리픽스 트라이로부터 비트맵 테이블, 인코딩 테이블 및 노드 테이블를 포함하는 비트맵을 생성하는 단계; 및이름 프리픽스 검색 장치의 프로세서가 상기 생성된 비트맵을 저장하는 단계를 포함하는 우선순위 이름 프리픽스 트라이 기반의 비트맵 생성 방법.

제1항에 있어서,상기 결정하는 단계는,이름 프리픽스 검색 장치의 프로세서가 상기 이름 프리픽스 트라이에서 이름 프리픽스를 가지지 않는 빈 노드가 루트 노드로 설정된 서브 트라이를 결정하는 단계; 및이름 프리픽스 검색 장치의 프로세서가 상기 서브 트라이에서 이름 프리픽스를 가지는 적어도 하나의 삽입 노드들 중 가장 많은 컴포넌트를 갖는 이름 프리픽스가 저장된 삽입 노드를 우선순위 노드로 결정하여 상기 서브 트라이의 루트 노드로 대체하는 단계를 포함하는 우선순위 이름 프리픽스 트라이 기반의 비트맵 생성 방법.

제1항에 있어서,상기 생성하는 단계는,이름 프리픽스 검색 장치의 프로세서가 상기 우선순위-이름 프리픽스 트라이에 포함된 우선순위 노드 및 상기 우선순위 노드를 제외한 삽입 노드를 나타내는 비우선순위 노드의 노드 번호를 상기 비트맵 테이블의 인덱스 번호 및 노드 테이블의 인덱스 번호 각각에 매칭하는 우선순위 이름 프리픽스 트라이 기반의 비트맵 생성 방법.

제1항에 있어서,상기 비트맵 테이블은,(i) 상기 우선순위-이름 프리픽스 트라이에 포함된 노드들이 우선순위 노드 또는 비우선순위 노드인지 여부를 나타내는 노드 타입, (ii) 우선순위-이름 프리픽스 트라이에 포함된 노드들 각각에 저장된 이름 프리픽스를 구성하는 컴포넌트의 개수를 나타내는 컴포넌트, (iii) 우선순위-이름 프리픽스 트라이에 포함된 노드들 각각에 저장된 이름 프리픽스에 해시 함수를 적용하여 도출된 핑거프린트(fingerprint)를 나타내는 해시브리프, (iv) 우선순위-이름 프리픽스 트라이에 포함된 노드들에 대한 자식 노드의 개수를 나타내는 차일드 개수 정보 및 (iv) 우선순위-이름 프리픽스 트라이에 포함된 노드들의 첫번째 자식 노드로의 경로에 해당하는 인코딩 테이블의 주소값을 나타내는 차일드 포인터 정보 중 적어도 하나의 정보를 포함하는 우선순위 이름 프리픽스 트라이 기반의 비트맵 생성 방법.

제1항에 있어서,상기 인코딩 테이블은,상기 우선순위-이름 프리픽스 트라이에 포함된 우선순위 노드와 비우선순위 노드 각각의 자식 노드에 대한 에지(edge) 정보 및 상기 우선순위 노드 및 비우선순위 노드와 상기 자식 노드 간의 인덱스 번호 차이를 나타내는 인코딩 번호를 포함하는 우선순위 이름 프리픽스 트라이 기반의 비트맵 생성 방법.

제1항에 있어서,상기 노드 테이블은,상기 우선순위-이름 프리픽스 트라이의 우선순위 노드와 비우선순위 노드 각각에 포함된 이름 프리픽스와 상기 이름 프리픽스에 대응하는 출력 페이스를 포함하는 우선순위 이름 프리픽스 트라이 기반의 비트맵 생성 방법.

제1항에 있어서,상기 저장하는 단계는,이름 프리픽스 검색 장치의 프로세서가 상기 비트맵 테이블 및 인코딩 테이블은 이름 프리픽스를 검색하는 칩의 내부 메모리에 저장하고, 상기 노드 테이블은 이름 프리픽스를 검색하는 칩의 외부 메모리에 저장하는 우선순위 이름 프리픽스 트라이 기반의 비트맵 생성 방법.

이름 프리픽스 검색 장치가 수행하는 이름 프리픽스 검색 방법은,이름 프리픽스 검색 장치의 프로세서가 이름 프리픽스 트라이에서 도출된 우선순위 노드 및 비우선순위 노드를 포함하는 우선순위-이름 프리픽스 트라이에 기초하여 생성된 비트맵을 식별하는 단계;이름 프리픽스 검색 장치의 프로세서가 상기 식별된 비트맵을 이용하여 입력 패킷의 이름 프리픽스와 가장 많은 컴포넌트가 일치하는 우선순위-이름 프리픽스 트라이 내의 이름 프리픽스를 검색하는 단계를 포함하고,상기 비트맵은,비트맵 테이블, 인코딩 테이블 및 노드 테이블로 구성되는 이름 프리픽스 검색 방법.

제8항에 있어서,상기 검색하는 단계는,이름 프리픽스 검색 장치의 프로세서가 상기 입력 패킷의 이름 프리픽스를 검색하기 위해 접근한 상기 비트맵 테이블의 노드 타입에 기초하여 상기 우선순위-이름 프리픽스 트라이에 포함된 노드가 우선순위- 노드인지 또는 비우선순위 노드인지 확인하는 단계; 및이름 프리픽스 검색 장치의 프로세서가 상기 우선순위-이름 프리픽스 트라이에 포함된 노드가 비우선순위 노드로 확인되면, 상기 확인된 비우선순위 노드의 인덱스 번호와 동일한 노드 테이블의 인덱스 번호에 접근하여 출력 페이스를 추출하는 단계를 포함하는 이름 프리픽스 검색 방법.

제9항에 있어서,상기 추출하는 단계 이후에,이름 프리픽스 검색 장치의 프로세서가 상기 입력 패킷의 이름 프리픽스를 검색하기 위해 접근한 상기 비트맵 테이블의 비우선순위 노드가 자식 노드를 가지는지 여부를 확인하는 단계;이름 프리픽스 검색 장치의 프로세서가 상기 비우선순위 노드가 자식 노드를 가지는 것으로 확인된 경우, 상기 비트맵 테이블의 차일드 포인터 정보를 이용하여 인코딩 테이블에 접근하고, 상기 인코딩 테이블을 이용하여 다음에 검색을 진행할 경로와 일치하는 자식 노드에 대한 에지 정보를 확인하는 단계; 및이름 프리픽스 검색 장치의 프로세서가 상기 일치하는 자식 노드에 대한 에지 정보가 확인된 경우, 상기 입력 패킷의 이름 프리픽스를 검색하기 위해 접근한 상기 비트맵 테이블의 비우선순위 노드에 대한 인덱스 번호와 상기 확인된 에지 정보에 대응하는 인코딩 번호를 이용하여 다음에 검색을 진행할 비트맵 테이블의 인덱스를 결정하는 단계를 더 포함하는 이름 프리픽스 검색 방법.

제8항에 있어서,상기 검색하는 단계는,이름 프리픽스 검색 장치의 프로세서가 상기 입력 패킷의 이름 프리픽스를 검색하기 위해 접근한 상기 비트맵 테이블의 노드 타입에 기초하여 상기 우선순위-이름 프리픽스 트라이에 포함된 노드가 우선순위 노드인지 비우선순위 노드인지 확인하는 단계;이름 프리픽스 검색 장치의 프로세서가 상기 우선순위-이름 프리픽스 트라이에 포함된 노드가 우선순위 노드로 확인되면, 상기 입력 패킷의 이름 프리픽스에 대한 해시 값과 상기 비트맵 테이블에 포함된 해시브리프가 일치하는지 비교하는 단계;이름 프리픽스 검색 장치의 프로세서가 상기 입력 패킷의 이름 프리픽스에 대한 해시 값과 상기 비트맵 테이블에 포함된 해시브리프가 일치하는 경우, 상기 입력 패킷의 이름 프리픽스와 상기 노드 테이블에 저장된 이름 프리픽스와 일치하는지 비교하는 단계; 및이름 프리픽스 검색 장치의 프로세서가 상기 입력 패킷의 이름 프리픽스와 상기 노드 테이블에 저장된 이름 프리픽스와 일치하는 경우, 상기 확인된 우선순위-이름 프리픽스 트라이에 포함된 노드의 인덱스 번호와 동일한 노드 테이블의 인덱스 번호에 접근하여 출력 페이스를 추출하는 단계를 포함하는 이름 프리픽스 검색 방법.

제8항에 있어서,상기 우선순위-이름 프리픽스 트라이는,상기 이름 프리픽스 트라이에서 이름 프리픽스를 가지지 않는 빈 노드를 루트 노드로 설정하는 서브 트라이를 결정하고, 상기 서브 트라이에서 이름 프리픽스를 가지는 적어도 하나의 삽입 노드들 중 가장 많은 컴포넌트를 갖는 이름 프리픽스가 저장된 삽입 노드를 우선순위 노드로 결정하여 상기 서브 트라이의 루트 노드로 대체함으로써 생성되는 이름 프리픽스 검색 방법.

제8항에 있어서,상기 비트맵은,상기 우선순위-이름 프리픽스 트라이에 포함된 우선순위 노드 및 상기 우선순위 노드를 제외한 삽입 노드를 나타내는 비우선순위 노드의 노드 번호를 상기 비트맵 테이블의 인덱스 번호 및 인코딩 테이블의 인덱스 번호 각각에 매칭함으로써 생성되는 이름 프리픽스 검색 방법.

제8항에 있어서,비트맵 테이블은,(i) 상기 우선순위-이름 프리픽스 트라이에 포함된 노드들이 우선순위 노드 또는 비우선순위 노드인지 여부를 나타내는 노드 타입, (ii) 우선순위-이름 프리픽스 트라이에 포함된 노드들 각각에 저장된 이름 프리픽스를 구성하는 컴포넌트의 개수를 나타내는 컴포넌트, (iii) 우선순위-이름 프리픽스 트라이에 포함된 노드들 각각에 저장된 이름 프리픽스에 해시 함수를 적용하여 도출된 핑거프린트(fingerprint)를 나타내는 해시브리프, (iv) 우선순위-이름 프리픽스 트라이에 포함된 노드들에 대한 자식 노드의 개수를 나타내는 차일드 개수 정보 및 (iv) 우선순위-이름 프리픽스 트라이에 포함된 노드들의 첫번째 자식 노드로의 경로에 해당하는 인코딩 테이블의 주소값을 나타내는 차일드 포인터 정보 중 적어도 하나의 정보를 포함하는 이름 프리픽스 검색 방법.

제8항에 있어서,상기 인코딩 테이블은,상기 우선순위-이름 프리픽스 트라이에 포함된 우선순위 노드와 비우선순위 노드 각각의 자식 노드에 대한 에지(edge) 정보 및 상기 우선순위 노드 및 비우선순위 노드와 상기 자식 노드 간의 인덱스 번호 차이를 나타내는 인코딩 번호를 포함하는 이름 프리픽스 검색 방법.

제8항에 있어서,상기 노드 테이블은,상기 우선순위-이름 프리픽스 트라이의 우선순위 노드와 비우선순위 노드 각각에 포함된 이름 프리픽스와 상기 이름 프리픽스에 대응하는 출력 페이스를 포함하는 이름 프리픽스 검색 방법.

제8항에 있어서,상기 비트맵 테이블 및 인코딩 테이블은 이름 프리픽스를 검색하는 칩의 내부 메모리에 저장되고, 상기 노드 테이블은 이름 프리픽스를 검색하는 칩의 외부 메모리에 저장되는 이름 프리픽스 검색 방법.