KR100662254B1

KR100662254B1 - 라우팅 시스템에서의 패킷 분류 장치 및 이를 위한 룰 구축 방법

Info

Publication number: KR100662254B1
Application number: KR1020030098289A
Authority: KR
Inventors: 최병철; 곽동용
Original assignee: 한국전자통신연구원
Priority date: 2003-12-27
Filing date: 2003-12-27
Publication date: 2007-01-02
Also published as: KR20050066807A

Abstract

본 발명은 비트맵 트리 기반의 교차적 패킷 분류 기법에서 백트래킹이 발생하지 않도록 룰 테이블을 구축하는 라우팅 시스템에서의 패킷 분류 장치 및 이를 위한 룰 구축 방법에 관한 것으로, IP 헤더 분석/추출 수단; 패킷 데이터 제어수단; 패킷 저장수단; 상기 수신된 패킷을 분류하는데 필요한 비트맵 정보와 링크시켜놓은 다음 하위 노드의 포인터 정보를 저장하는 것으로, 발신지 주소 최상위 멀티비트 그룹의 각 노드가 자기 자신의 프리픽스 외에 다른 노드가 가지는 프리픽스를 포함하도록 트리 구조로 구성한 상기 비트맵 정보를 저장하는 룰 저장수단; 상기 IP 헤더 분석/추출 수단으로부터 전달된 IP 패킷 헤더의 목적지 주소, 발신지 주소를 일정한 크기의 비교 단위(Stride)로 나누고, 각 비교 단위마다 목적지 주소와 발신지 주소의 상위비교 단위부터 계층적으로 서로 교차하면서 상기 룰 저장수단에 저장된 트리 비트맵과 비교하여 베스트 매칭 룰을 찾아 패킷을 분류하는 패킷 분류 수단; 및 상기 패킷 분류 수단에 의해 찾아진 베스트 매칭 룰의 정보를 저장하는 넥스트 홉 정보 저장수단을 포함한다.

라우터, 네트워크, 패킷, 분류, 백트랙킹, 멀티, 비트, 목적지, 주소, 발신지

Description

라우팅 시스템에서의 패킷 분류 장치 및 이를 위한 룰 구축 방법{Apparatus and Method for Packet Classification in Router}

도 1 은 본 발명에 따른 라우팅 시스템에서 패킷 처리 장치를 나타낸 일실시예 구성도.

도 2 는 본 발명에 따른 룰 구축에 적용되는 룰 검색을 위한 IP 주소의 구조를 나타낸 일실시예 설명도.

도 3 은 본 발명에 따른 룰 구축에 적용되는 룰 검색 구조를 나타낸 일실시예 설명도.

도 4 는 상기 도 3의 룰 구성을 나타낸 일실시예 설명도.

도 5 는 상기 도 4의 룰에 대한 백트랙킹이 존재하는 멀티비트 트리 비트맵 테이블 구조를 나타낸 일실시예 설명도.

도 6 은 상기 도 4의 룰에 대한 백트랙킹이 없는 멀티비트 트리 비트맵 테이블 구조를 나타낸 일실시예 설명도.

도 7 은 본 발명에 따른 룰 구축 방법에 대한 일실시예 흐름도.

* 도면의 주요 부분에 대한 부호의 설명

101 : 룰테이블 102 : 넥스트 홉 정보 메모리

103 : 패킷 데이터 제어부 104 : 패킷 메모리

105 : 패킷 분류 엔진 106 : 패킷 헤더 편집부

107 : IP Packet

본 발명은, 라우팅 시스템에서의 패킷 분류 장치 및 이를 위한 룰 구축 방법에 관한 것으로, 더욱 상세하게는 검색 대상 필드 및 패킷 분류 룰을 구성하는 프리픽스를 비교 단위가 되는 멀티비트로 나누고, 일정한 크기의 멀티비트 단위로 트리 비트맵 기반의 룰 검색 기능을 수행하는 패킷 분류 기법의 룰 구축시 백트랙킹이 발생하지 않도록 하는 라우팅 시스템에서의 패킷 분류 장치 및 이를 위한 룰 구축 방법에 관한 것이다.

패킷 분류는 인터넷 망에서 서비스품질(QoS)보장, 가상사설망(VPN) 등과 같은 사용자들의 다양한 서비스를 수용하기 위한 중요한 요소이다.

패킷 분류는 기본적으로 IP 패킷 헤더 내의 목적지 주소(Destination Address)뿐만 아니라 발신지 주소(Source Address), 프로토콜, TCP포트 번호(Port Number) 등 여러 필드(멀티 필드)들을 조합하여 룰테이블로부터 베스트 매칭(Best Matching) 룰을 찾는 것이다.

라우팅 시스템에서 QoS 보장을 위해서는 IP 헤더의 목적지 주소, 발신지 주소, TCP 포트번호, 프로토콜 등 여러필드를 조합하여 플로우 정보를 획득하여야 한다. 또한, 수Gbps급의 패킷 전달 처리 능력을 가지기 위해서는 패킷 분류 처리 기능도 고속처리가 가능해야 한다.

그러나, 패킷 분류 과정에서 룰 검색시 룰 미스매치가 발생하여 상위의 매치된 프리픽스 포인터로 되돌아가서 다시 검색을 계속해야 하는 백트랙킹이 발생하여 검색 시간이 많이 소요되는 문제점이 있었다.

본 발명은, 상기한 바와 같은 문제점을 해결하기 위하여 제안된 것으로, 비트맵 트리 기반의 교차적 패킷 분류 기법에서 백트래킹이 발생하지 않도록 룰테이블을 구축하는 라우팅 시스템에서의 패킷 분류 장치 및 이를 위한 룰 구축 방법을 제공하는데 그 목적이 있다.

상기 목적을 달성하기 위한 본 발명의 장치는, 라우팅 시스템에서의 패킷 분류 장치에 있어서, 수신되는 IP(Internet Protocol) 패킷의 헤더 영역만을 분리하여 패킷 분류 수단으로 전달하고 전체 IP 패킷은 패킷 저장수단에 저장하도록 패킷 데이터 제어수단으로 전달하는 IP 헤더 분석/추출 수단; 상기 IP 헤더 분석/추출 수단으로부터 전달되는 IP 패킷을 상기 패킷 저장수단에 저장하고, 상기 패킷 분류 수단으로부터 패킷 분류 검색이 완료되었다는 신호를 전달받으면 상기 저장된 IP 패킷을 패킷 헤더 편집수단으로 전달하는 상기 패킷 데이터 제어수단; 수신되는 패킷을 일시 저장하는 상기 패킷 저장수단; 상기 수신된 패킷을 분류하는데 필요한 비트맵 정보와 링크시켜놓은 다음 하위 노드의 포인터 정보를 저장하는 것으로, 발신지 주소 최상위 멀티비트 그룹의 각 노드가 자기 자신의 프리픽스 외에 다른 노드가 가지는 프리픽스를 포함하도록 트리 구조로 구성한 상기 비트맵 정보를 저장하는 룰 저장수단; 상기 IP 헤더 분석/추출 수단으로부터 전달된 IP 패킷 헤더의 목적지 주소, 발신지 주소를 일정한 크기의 비교 단위(Stride)로 나누고, 각 비교 단위마다 목적지 주소와 발신지 주소의 상위비교 단위부터 계층적으로 서로 교차하면서 상기 룰 저장수단에 저장된 트리 비트맵과 비교하여 베스트 매칭 룰을 찾아 패킷을 분류하는 패킷 분류 수단; 및 상기 패킷 분류 수단에 의해 찾아진 베스트 매칭 룰의 정보를 저장하는 넥스트 홉 정보 저장수단을 포함한다.

한편, 본 발명의 방법은, IP 헤더 분석/추출 수단과, 패킷 데이터 제어수단과, 패킷 저장수단과, 수신된 패킷을 분류하는데 필요한 비트맵 정보와 링크시켜놓은 다음 하위 노드의 포인터 정보를 저장하는 룰 저장수단과, 상기 룰 저장수단에 저장된 트리 비트맵과 비교하여 베스트 매칭 룰을 찾아 패킷을 분류하는 패킷 분류 수단, 및 상기 패킷 분류 수단에 의해 찾아진 베스트 매칭 룰의 정보를 저장하는 넥스트 홉 정보 저장수단을 포함하는 패킷 분류 장치에서, 상기 룰 저장수단에 저장되는 룰을 구축하기 위한 방법에 있어서, 임의 번째 목적지 주소와 발신지 주소에 해당하는 멀티비트 그룹의 추가되는 프리픽스가 모두 마스크 되어 있는지 확인하는 제1 단계; 상기 제1 단계에서 모두 마스크 되어 있지 않으면, 상기 임의 번째 목적지 주소 멀티비트 그룹을 페치하고, 프리픽스를 저장할 노드 포인터를 획득하는 제2 단계; 상기 임의 번째 목적지 주소 멀티비트 그룹의 프리픽스를 저장하는 노드에서 새로 추가되는 프리픽스 외에 기존에 이미 존재하는 프리픽스가 있는지 확인하여, 상기 추가되는 프리픽스의 위치를 확인하고, 상기 추가되는 임의 번째 발신지 주소 멀티비트 그룹 프리픽스를 추가 저장하는 제3 단계; 노드 위치를 분석하여 노드내에 추가되는 임의 번째 목적지 주소가 하위 프리픽스들을 포함하고 있으면, 임의 번째 발신지 주소 레벨의 기존 노드 중 해당 추가되는 임의 번째 목적지 주소 프리픽스와 관련된 임의 번째 발신지 주소 프리픽스에 해당하는 프리픽스를 추가하여 마크 프리픽스를 갱신하는 제4 단계; 노드 내에 상위 프리픽스가 존재하면, 추가되는 발신지 주소 프리픽스 노드내의 바로 상위 프리픽스의 임의 번째 발신지 주소 프리픽스를 갖는 노드들이 가지는 모든 정보를 추가하여 마크 프리픽스로 추가하는 제5 단계; 추가되는 룰의 임의 번째 발신지 주소 멀티비트 프리픽스를 페치하여 저장 노드 포인터를 획득하고, 소정번째 발신지 주소 멀티비트 그룹의 프리픽스를 저장하는 노드에서 새로 추가되는 프리픽스 외에 기존에 이미 존재하는 프리픽스가 있는지 확인하여, 추가되는 프리픽스의 위치를 확인하고, 추가되는 임의 번째 다음의 목적지 주소 멀티비트 그룹 프리픽스를 추가 저장하는 제6 단계; 추가되는 프리픽스의 노드 위치를 분석하여 노드내에 추가되는 임의 번째 발신지 주소가 하위 프리픽스들을 포함하고 있으면, 임의 번째의 다음번 목적지 주소 레벨의 기존 노드 중 추가되는 임의 번째 발신지 주소 프리픽스와 관련된 임의 번째 다음번 목적지 주소 프리픽스에 해당하는 프리픽스를 추가하여 마크 프리픽스를 갱신하는 제7 단계; 및 임의 번째 발신지 주소 프리픽스 노드내에 상위 프리픽스가 존재하면, 추가 발신지 주소 프리픽스의 바로 상위 프리픽스의 임의 번째 다음번 목적지 주소 프리픽스 노드가 가지는 모든 정보를 추가하여 마크 프리픽스로 추가하는 제8 단계를 포함한다.

상술한 목적, 특징들 및 장점은 첨부된 도면과 관련한 다음의 상세한 설명을 통하여 보다 분명해 질 것이다. 이하, 첨부된 도면을 참조하여 본 발명에 따른 바람직한 일실시예를 상세히 설명한다.

도 1 은 본 발명에 따른 라우팅 시스템에서 패킷 처리 장치를 나타낸 일실시예 구성도이다.

라우팅 시스템에서의 라인정합 장치의 패킷 분류 기능을 수행하기 위한 패킷 처리 모듈은 IP 헤더 분석/추출부(100), 패킷 데이터 제어부(103), 패킷 메모리(104), 패킷 분류엔진(105), 룰테이블(101), 넥스트 홉(Next Hop) 정보 메모리(102), 그리고 패킷 헤더 편집부(106)를 포함한다.

IP 헤더 분석/추출부(100)는 수신되는 IP 패킷(107)으로부터 패킷 분류 기능을 수행하도록 IP 헤더 영역만을 분리하여 패킷 분류 엔진(105)으로 전달하고 전체 IP 패킷은 패킷 메모리(104)에 저장하도록 패킷 데이터 제어부(103)로 전송하는 기능을 가진다.

패킷 데이터 제어부(103)는 IP 헤더 분석/추출부(100)로부터 전달되는 IP 패킷(107)에 대하여 패킷 메모리(104)에 저장하는 제어 기능을 수행하고, 패킷 분류 엔진(105)으로부터 패킷 분류 검색이 완료되었다는 신호를 전달받으면 저장된 IP 패킷을 패킷 메모리(104)로부터 읽어 패킷 헤더 편집부(106)로 전달하는 역할을 수행한다.

패킷 메모리(104)는 수신되는 패킷을 패킷 분류 검색 기능을 완료할 때까지 일시적으로 저장하는 역할을 한다.

패킷 분류 엔진(105)은 IP 헤더 분석/추출부(100)로부터 전달받은 목적지 주 소, 발신지 주소, 프로토콜, 포트번호 등 여러 필드의 값을 이용하여 가장 매치가 잘되는 룰을 찾아내는 기능을 수행한다.

패킷 분류 엔진(105)은 수신한 목적지 주소, 발신지 주소를 일정한 크기의 비교 단위(Stride)로 나누고 각 비교 단위 마다 목적지 주소와 발신지 주소의 상위비교 단위부터 계층적으로 서로 교차하면서 룰테이블(101)에 구축되어 있는 트리 비트맵과 비교 기능을 수행하여 베스트 매칭(Best Matching) 룰을 찾아낸다.

룰테이블(101)은 패킷 분류를 위한 비트맵 정보를 저장하는 메모리로서 비트맵 정보와 링크시켜놓은 다음 하위노드의 포인터 정보를 저장하고 있다.

넥스트 홉(Next Hop) 정보 메모리(102)는 베스트 매칭(Best Matching) 룰을 찾은 후에 해당 룰의 정보를 저장하는 테이블로서 패킷의 폐기 여부, 플로우 정보, 서비스품질(QoS) 정보 등을 저장한다.

도 2 는 본 발명에 따른 룰 구축에 적용되는 룰 검색을 위한 IP 주소의 구조를 나타낸 일실시예 설명도이다.

도면에서, "210"은 IP버전 4의 32비트로 구성된 목적지 주소를 나타내고, "220"은 32비트로 구성된 발신지 주소를 나타내고 있다.

각 주소는 일정한 비트 수의 멀티비트 단위로 나누어져 멀티비트 트리 비트맵 기반의 패킷 분류를 위한 한번의 검색 단위로 사용된다.

"211"~"213"은 목적지 주소의 분해되는 주소 구조를 나타내고, "221"~"223"은 발신지 주소의 분해되는 주소 구조를 나타내며, 검색에 사용되는 순서는 목적지 주소 최상위 멀티비트 그룹(211), 발신지 주소 최상위 멀티비트 그룹(221), 그리고 다음 하위 레벨의 목적지 주소의 멀티비트 그룹(212), 다음 하위의 발신지 주소의 멀티비트 그룹(222)과 같이 서로 교차적으로 상위 레벨에서부터 하위 레벨로 검색이 종료되거나 마지막 레벨(213, 223)까지 검색에 사용된다.

도 3 은 본 발명에 따른 룰 구축에 적용되는 룰 검색 구조를 나타낸 일실시예 설명도이다.

도면에서, "330"은 멀티비트 트리 기반 검색 구조를 나타내고 있으며, 룰 구성이 {목적지 주소/마스크, 발신지 주소/마스크}의 형태를 가질 때 테이블 구성을 나타내고 있다. "331"은 최상위 멀티비트 그룹, 즉 상기 도 2의 "211" 위치에 해당하는 프리픽스의 존재를 나타내며, "332"는 상기 도 2의 "211"의 각 프리픽스가 나타내는 포인터로부터 하나의 노드를 형성하여 해당하는 프리픽스의 존재를 나타내고 있다. "333"은 상기 "332"의 부모 노드로부터 부모 프리픽스로부터 지정된 위치에 차일드 노드를 형성하여 프리픽스를 나타내고 있다. 이와 같이 레벨 N까지 부모 노드 프리픽스로부터 링크된 차일드 노드 프리픽스를 표시하므로서, 룰테이블은 구축된다.

이와 같이 구성되는 룰테이블에서 룰 검색은 외부로부터 수신한 패킷의 IP 헤더를 추출하여 상기 도 2에 나타난 주소 구조에서 처럼 상위 멀티비트 그룹에서부터 하위 멀티비트 그룹으로 상호 목적지 주소, 발신지 주소의 멀티비트 그룹 단위로 비교 검색 기능을 수행한다.

도 4 는 상기 도 3의 룰 구성을 나타낸 일실시예 설명도이다.

도 4는 목적지 주소 8비트, 발신지 주소 8비트로 구성된 7 룰 셋을 나타내고 있으며 "*"는 비교시 돈 케어(don't care)로 비트 마스크된 상태를 나타낸다. 각각의 룰은 4비트 크기의 멀티비트 그룹으로 나누어져 있으며, 목적지 주소 영역은 "DA_S1", "DA_S2" 발신지 주소는 "SA_S1", "SA_S2"로 구성되어 있다.

도 5 는 상기 도 4의 룰에 대한 백트랙킹이 존재하는 멀티비트 트리 비트맵 테이블 구조를 나타낸 일실시예 설명도이다.

도면에서, "540"은 DA_S1에 대한 루트 노드로서의 프리픽스의 존재를 나타내고 있으며, 각 프리픽스 위치로부터 SA_S1의 하위 레벨에 위치하는 차일드 노드의 위치 정보를 각각 나타낸다. 이와 같이 SA_S1의 각 멀티비트 노드로부터는 DA_S2의 하위 레벨에 해당하는 멀티비트 노드가 포인터로서 링크되어 있다. 이와 같은 테이블 구조로부터 각 노드에서는 수신된 패킷 헤더내의 비트를 추출하여 루트 노드로부터 하위 노드로 가장 길게 매치(Longest Prefix Match)되는 프리픽스를 해당 노드에서 선택된 프리픽스로 결정하여 그 프리픽스가 가리키는 다음 하위 노드로 이동하여 하위 노드에서 또 다시 멀티비트의 가장 길게 매치되는 프리픽스를 찾아내는 과정을 상위로부터 하위로 이동하면서 계속한다.

DS_S1 레벨에서 "541"은 R5프리픽스, "542"는 R4 프리픽스, "543"은 R6, "544"는 R3, "545"는 R7, "546"은 R2, "547"은 R1의 프리픽스로부터 포인팅된 노드들을 나타내고 있다. 이와 동일한 방법으로 "548", "549", "550"까지의 노드는 DA_S2 레벨에서의 상위 노드로부터 포인팅되어 저장된 프리픽스를 나타내고 있으며 "151", "152"는 SA_S2 레벨에서의 상위 노드로부터 포인팅되어 저장된 프리픽스를 나타내고 있다.

이와 같은 구조에서 임의의 {DA, SA} 주소 영역이 P={1100 1001, 0110 1100}인 패킷이 수신된 경우 루트 노드 DA_S1에서는 "1100"으로 "553"과 같은 경로로 최장 프리픽스 경로가 선택되고, SA_S1에서는 "0110"에 대한 최장 프리픽스 검색을 수행한다. 이때 위의 예에서는 매치되는 프리픽스가 존재하지 않게 되어 DA_S1에서 최장 다음으로 덜 긴 프리픽스 위치로 올라가는 백트랙킹 현상이 발생하게 된다. R2 프리픽스 위치에서 SA_S1의 하위 노드를 가리키는 포인터에서 "0110"과 프리픽스 맵을 비교하여 가장 길게 매치되는 프리픽스의 다음 하위 포인터를 획득하여 SA_S2 레벨까지 검색을 계속하여 "551" 노드에서 최종 매치된 룰 R2를 찾게 된다.

이와 같은 구조의 테이블을 구축할 시 테이블 구축은 쉬우나 검색 성능에 관련된 검색 회수에 백트랙킹이 존재하게 되어 성능 저하의 요인이 된다.

도 6 은 상기 도 4의 룰에 대한 백트랙킹이 없는 멀티비트 트리 비트맵 테이블 구조를 나타낸 일실시예 설명도이다.

도면에서, "660"은 상기 도 5의 "540"과 같이 상기 도 4의 루트 노드를 나타내고 있으며, "661"~"666"은 SA_S1 레벨에서의 각 각의 노드 프리픽스 맵을 나타내고 있다. 이와 같은 구조의 경우 SA_S1레벨의 각 노드는 자기 자신의 프리픽스에 해당하는 검은 색의 SA_S1레벨의 다른 노드가 가지는 프리픽스를 포함하고 있으며, 이것은 회색으로 마크되어 있다. 이와 같은 회색 마크된 내부 노드는 동일한 레벨의 노드상에서의 검색을 수행할 시 백트랙킹이 발생하지 않도록 하기 위한 룰테이블 구축 방법이다.

"660"의 루트 노드에서 R5는 R4, R3, R2, R1의 프리픽스들과 R6, R7의 프리픽스들을 포함하고 있으며, R4는 R3, R2, R1의 프리픽스들을 포함하고 있다. 또한 R3는 R2, R1을 포함하며, R2는 R1 프리픽스를 하위에 두고 있다.

이와 같이 하나의 노드내에 네스팅(Nesting)된 프리픽스들이 존재할 경우 다음 하위 노드에서 백트랙킹되어 하위노드 검색을 수행하는 경우가 많이 발생한다.

본 발명에서는 백트랙킹을 제거하기 위하여 다음과 같은 룰 추가 방법을 고안하였다.

추가되는 룰에 대하여 멀티비트 크기로 루트 노드로부터 하위 노드로 룰이 구축될 때 상위 노드와 하위의 여러 노드간에 기존에 이미 존재하는 프리픽스와 추가되는 프리픽스의 포함 관계를 이용하여 룰을 설정한다. "672"~"683"까지는 백트랙킹 제거 개념이 도입된 마킹 노드를 나타내고 있다.

도 7 은 본 발명에 따른 룰 구축 방법에 대한 일실시예 흐름도이다.

도 7에 도시된 바와 같이, 본 발명에 따른 룰 구축 방법은, 먼저 상위 멀티비트 그룹부터 시작하여 마지막 하위 멀티비트 그룹까지의 검사 기능을 수행한다(701~702).

한편, I번째 DA, SA에 해당하는 멀티비트 그룹의 추가되는 프리픽스가 모두 마스크되어 있는지를 확인하고(703), I번째 DA, SA에 해당하는 멀티비트 그룹의 추가되는 프리픽스가 모두 마스크되어 있는 경우에는 룰 추가 과정을 종료하고, I번째 DA, SA의 해당 멀티비트 그룹이 둘다 마스크 되어 있지 않으면, I번째 DA 멀티비트 그룹을 페치하고(704), 프리픽스를 저장할 노드 포인터를 획득한다(705). 그리고 I번째 DA 멀티비트 그룹의 프리픽스를 저장하는 노드에서 새로 추가되는 프리픽스 외에 기존에 이미 존재하는 프리픽스가 있는지 확인하고, 추가되는 프리픽스의 위치를 확인하여, 추가되는 I번째 SA멀티비트 그룹 프리픽스를 추가 저장한다(706~707).

다음으로, 노드 위치를 분석하여 노드내에 추가되는 I번째 DA가 하위 프리픽스들을 포함하고 있는지를 확인하여(708), 노드내 하위 프리픽스가 포함되어 있는 경우에는 I번째 SA 레벨의 기존 노드 중 해당 추가되는 I번째 DA 프리픽스와 관련된 I번째 SA 프리픽스에 해당하는 프리픽스를 추가하여, 마크 프리픽스를 갱신한다(710). 그리고, 노드내에 상위 프리픽스가 존재하는 경우(711), 추가되는 SA 프리픽스 노드내의 바로 상위 프리픽스의 I번째 SA 프리픽스는 노드가 가지는 모든 정보를 모두 추가하여 마크 프리픽스로 추가한다(712).

다음으로, 추가되는 룰의 I번째 SA 멀티비트 프리픽스를 페치하여(713) 저장 노드 포인터를 획득하고(714), I번째 SA 멀티비트 그룹의 프리픽스를 저장하는 노드에서 새로 추가되는 프리픽스 외에 기존에 이미 존재하는 프리픽스가 있는지 확인하고 추가되는 프리픽스의 위치를 확인하고(715), 추가되는 (I+1)번째 DA멀티비트 그룹 프리픽스를 추가 저장한다(716).

추가되는 프리픽스의 노드 위치를 분석하여 노드내에 추가되는 I번째 SA가 하위 프리픽스들을 포함하고 있는 경우에는(717), (I+1)번째 DA 레벨의 기존 노드 중 추가되는 I번째 SA 프리픽스와 관련된 (I+1)번째 DA 프리픽스에 해당하는 프리픽스를 추가하여 마크 프리픽스를 갱신한다(718, 719).

또한, I번째 SA 프리픽스 노드내에 상위 프리픽스가 존재하는 경우(720) 추가 SA 프리픽스의 바로 상위 프리픽스의 (I+1)번째 DA 프리픽스 노드가 가지는 모든 정보를 모두 추가하여 마크 프리픽스로 추가한다(721).

이와 같이 I를 계속 증가시키면서 N보다 크면 반복되는 수행 과정을 종료하며, 만약 도중에 DA, SA 프리픽스가 모두 마스크 되는 경우에도 룰 추가 과정을 종료한다.

상술한 바와 같은 본 발명의 방법은 프로그램으로 구현되어 컴퓨터로 읽을 수 있는 형태로 기록매체(씨디롬, 램, 롬, 플로피 디스크, 하드 디스크, 광자기 디스크 등)에 저장될 수 있다.

이상에서 설명한 본 발명은 전술한 실시예 및 첨부된 도면에 의해 한정되는 것이 아니고, 본 발명의 기술적 사상을 벗어나지 않는 범위 내에서 여러 가지 치환, 변형 및 변경이 가능하다는 것이 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 있어 명백할 것이다.

상기한 바와 같은 본 발명은, 수기가급 인터넷 망에서 차별화된 서비스 및 QoS 보장을 위한 서비스를 수행하기 위해 목적지 IP 주소 뿐만아니라 발신지 주소에 대한 영역을 참조하여 고속의 룰 검색을 요구하고 있는 현 시점에, 룰 검색을 멀티비트 트리 비트맵을 이용하여 하드웨어적으로 수행하는 경우 룰 검색시 백트랙킹이 발생하지 않도록 룰 구축을 함으로써 룰 검색 성능을 향상시킬 수 있다.

또한, 본 발명은, 트리 비트맵 기반 멀티 필드에 대한 룰 검색시 효율적인 룰테이블을 구축함으로써, 룰 검색시 백트랙킹이 발생하지 않도록 하여 룰 미스매치가 발생하였을 경우 상위의 매치된 프리픽스 포인터로 되돌아가서 다시 검색을 계속해야 하는 필요가 없기 때문에 부가적인 룰 검색 시간이 필요없고, 백트래킹을 배제함으로써 성능을 향상시킬 수 있다.

Claims

삭제
삭제
라우팅 시스템에서의 패킷 분류 장치에 있어서,

수신되는 IP(Internet Protocol) 패킷의 헤더 영역만을 분리하여 패킷 분류 수단으로 전달하고 전체 IP 패킷은 패킷 저장수단에 저장하도록 패킷 데이터 제어수단으로 전달하는 IP 헤더 분석/추출 수단;

상기 IP 헤더 분석/추출 수단으로부터 전달되는 IP 패킷을 상기 패킷 저장수단에 저장하고, 상기 패킷 분류 수단으로부터 패킷 분류 검색이 완료되었다는 신호를 전달받으면 상기 저장된 IP 패킷을 패킷 헤더 편집수단으로 전달하는 상기 패킷 데이터 제어수단;

수신되는 패킷을 일시 저장하는 상기 패킷 저장수단;

상기 수신된 패킷을 분류하는데 필요한 비트맵 정보와 링크시켜놓은 다음 하위 노드의 포인터 정보를 저장하는 것으로, 발신지 주소 최상위 멀티비트 그룹의 각 노드가 자기 자신의 프리픽스 외에 다른 노드가 가지는 프리픽스를 포함하도록 트리 구조로 구성한 상기 비트맵 정보를 저장하는 룰 저장수단;

상기 IP 헤더 분석/추출 수단으로부터 전달된 IP 패킷 헤더의 목적지 주소, 발신지 주소를 일정한 크기의 비교 단위(Stride)로 나누고, 각 비교 단위마다 목적지 주소와 발신지 주소의 상위비교 단위부터 계층적으로 서로 교차하면서 상기 룰 저장수단에 저장된 트리 비트맵과 비교하여 베스트 매칭 룰을 찾아 패킷을 분류하는 패킷 분류 수단; 및

상기 패킷 분류 수단에 의해 찾아진 베스트 매칭 룰의 정보를 저장하는 넥스트 홉 정보 저장수단을 포함하는 것을 특징으로 하는 패킷 분류 장치.
삭제
제 3 항에 있어서,

상기 넥스트 홉(Next Hop) 정보 저장수단은,

테이블로서 패킷의 폐기 여부, 플로우 정보, 서비스품질(QoS) 정보를 저장하는 것을 특징으로 하는 패킷 분류 장치.
IP 헤더 분석/추출 수단과, 패킷 데이터 제어수단과, 패킷 저장수단과, 수신된 패킷을 분류하는데 필요한 비트맵 정보와 링크시켜놓은 다음 하위 노드의 포인터 정보를 저장하는 룰 저장수단과, 상기 룰 저장수단에 저장된 트리 비트맵과 비교하여 베스트 매칭 룰을 찾아 패킷을 분류하는 패킷 분류 수단, 및 상기 패킷 분류 수단에 의해 찾아진 베스트 매칭 룰의 정보를 저장하는 넥스트 홉 정보 저장수단을 포함하는 패킷 분류 장치에서, 상기 룰 저장수단에 저장되는 룰을 구축하기 위한 방법에 있어서,

임의 번째 목적지 주소와 발신지 주소에 해당하는 멀티비트 그룹의 추가되는 프리픽스가 모두 마스크 되어 있는지 확인하는 제1 단계;

상기 제1 단계에서 모두 마스크 되어 있지 않으면, 상기 임의 번째 목적지 주소 멀티비트 그룹을 페치하고, 프리픽스를 저장할 노드 포인터를 획득하는 제2 단계;

상기 임의 번째 목적지 주소 멀티비트 그룹의 프리픽스를 저장하는 노드에서 새로 추가되는 프리픽스 외에 기존에 이미 존재하는 프리픽스가 있는지 확인하여, 상기 추가되는 프리픽스의 위치를 확인하고, 상기 추가되는 임의 번째 발신지 주소 멀티비트 그룹 프리픽스를 추가 저장하는 제3 단계;

노드 위치를 분석하여 노드내에 추가되는 임의 번째 목적지 주소가 하위 프리픽스들을 포함하고 있으면, 임의 번째 발신지 주소 레벨의 기존 노드 중 해당 추가되는 임의 번째 목적지 주소 프리픽스와 관련된 임의 번째 발신지 주소 프리픽스에 해당하는 프리픽스를 추가하여 마크 프리픽스를 갱신하는 제4 단계;

노드 내에 상위 프리픽스가 존재하면, 추가되는 발신지 주소 프리픽스 노드내의 바로 상위 프리픽스의 임의 번째 발신지 주소 프리픽스를 갖는 노드들이 가지는 모든 정보를 추가하여 마크 프리픽스로 추가하는 제5 단계;

추가되는 룰의 임의 번째 발신지 주소 멀티비트 프리픽스를 페치하여 저장 노드 포인터를 획득하고, 소정번째 발신지 주소 멀티비트 그룹의 프리픽스를 저장하는 노드에서 새로 추가되는 프리픽스 외에 기존에 이미 존재하는 프리픽스가 있는지 확인하여, 추가되는 프리픽스의 위치를 확인하고, 추가되는 임의 번째 다음의 목적지 주소 멀티비트 그룹 프리픽스를 추가 저장하는 제6 단계;

추가되는 프리픽스의 노드 위치를 분석하여 노드내에 추가되는 임의 번째 발신지 주소가 하위 프리픽스들을 포함하고 있으면, 임의 번째의 다음번 목적지 주소 레벨의 기존 노드 중 추가되는 임의 번째 발신지 주소 프리픽스와 관련된 임의 번째 다음번 목적지 주소 프리픽스에 해당하는 프리픽스를 추가하여 마크 프리픽스를 갱신하는 제7 단계; 및

임의 번째 발신지 주소 프리픽스 노드내에 상위 프리픽스가 존재하면, 추가 발신지 주소 프리픽스의 바로 상위 프리픽스의 임의 번째 다음번 목적지 주소 프리픽스 노드가 가지는 모든 정보를 추가하여 마크 프리픽스로 추가하는 제8 단계를 포함하는 것을 특징으로 하는 룰 구축 방법.
삭제