KR20020081569A - Ternary CAM(Content Addressable Memory)을 이용하는네트웍 장치에서의 CAM내 동일한 엔트리 크기를 가지는다수의 테이블 관리 방법 - Google Patents

Abstract

패킷을 전달하는 프로토콜이 사용되는 네트워크 장치에서는 성능을 높이기 위해서, 하드웨어적으로 검색 기능을 보조해주는 Ternary CAM(Content Addressable Memory)을 이용하여 각종 테이블들을 관리하고 있다.

종래 기술에서 CAM 엔트리의 크기가 동일한 테이블들이 CAM에 있는 경우, 특정 엔트리를 검색하게 되면 복수의 테이블이 동시에 산출되기 때문에 그 결과 값이 어느 테이블에서 나오는지를 알 수가 없으며, 복수개의 검색 결과 값 중 우선순위가 가장 높은 하나의 검색 값만이 산출되는 문제로 인하여 동일 크기의 엔트리를 가지는 테이블이 하나 이상 있는 경우 지정된 하나의 테이블 내에서만 검색하는 것이 불가능하였다. 본 발명에서는 이러한 문제점을 해결하기 위한 방법으로 Ternary CAM의 특성을 응용하는 테이블 구분자 설정 방법을 사용하여 검색 시 원하는 결과를 얻을 수 있게 한다.

본 발명의 효과는 동일한 크기의 엔트리를 가지는 복수의 테이블을 가져도 단일 테이블 내에서 검색 결과 값을 산출하기 때문에 내용 검색 결과 값을 패킷을 전달하고자 하는 제어 값으로 사용할 수 있게 되었다.

Description

Ternary CAM(Content Addressable Memory)을 이용하는 네트웍 장치에서의 CAM내 동일한 엔트리 크기를 가지는 다수의 테이블 관리 방법 {The Management Method of tables that have entries of same size on CAM in Network device}

본 발명은 CAM(Content Addressable Memory)을 검색용 테이블로 사용하는 네트워크 장치와 관련된 것으로 특히 CAM내 관리하는 테이블들을 더욱 효율적으로 사용하기 위한 방법에 관한 것이다.

본 발명의 종래의 기술에는 CAM 방법과 Ternary CAM 방법이 있다.

CAM 방법은 CAM내에 있는 특정 엔트리를 하드웨어적으로 지정된 시간, 즉, 고정된 몇 clock cycle 내에 찾아주는 장점을 갖는다.

네트워크 환경과 네트워크 장치 내에서 관리되는 테이블 구조와 같이 MAC 주소(130), IP 주소(140), {송신 IP 주소, 송신 포트 번호, 수신 IP 주소, 수신 포트 번호}(160) 등, 테이블 내 데이터 필드들로 이루어진 튜플을 CAM에 저장한 후 CAM을 검색해서 찾고 그 결과를 적절하게 패킷 송수신에 이용하는 것이다.

Ternary CAM 방법은 기존의 binary CAM이 가지던 0과 1 값뿐만 아니라 "don't care" 값을 가지는 것을 가능하게 함으로써 비교할 필요가 없는 엔트리내 특정 필드를 don't care로 둘 수 있다. 이것은 CAM을 다양한 어플리케이션으로의 응용을 훨씬 용이하게 해준다. 그래서 CAM은 고속을 요구하는 차세대 네트워크 장치에 빠질 수 없는 보조 메모리로 등장하게 되었다.

본 발명과 관련된 종래의 특허에는 현재 출원 된 "다이나믹 콘텐츠 주소지정 가능 메모리(CAM) 셀(출원번호 10-2001-712599, 공개번호 특2002-0012168, 공개일자 2002년2월15일)" 이다. 이 특허는 CAM의 응용이라기보다는 CAM 자체 고유 기능에 관한 특허이다.

종래의 기술인 CAM이 가지는 단점은 CAM의 특징상 엔트리 크기가 36bit, 72bit, 144bit, 288bit 등과 같이 고정되어 있다는 것과, 같은 크기의 엔트리를 가지는 테이블들 간에는 구분하여 검색할 방법이 없다는 것이다. 테이블이란 것은 CAM 사용자 입장에서 논리적으로 나눈 것이지, 하드웨어적으로 나뉘어져 있는 것이아니기 때문에 CAM 자체는 검색 시 검색하고자 하는 테이블 만을 검색하는 것이 아니라 검색용 엔트리 크기에 맞춰서 CAM 내 동일한 크기를 가지는 모든 엔트리들을 테이블 종류에 상관없이 검색하므로 본 발명을 발생시킨 효과를 가져왔다.

CAM내에 들어가는 테이블들의 실시 예에서 보면 사용자가 CAM 메모리(210) 내에 A 테이블(211)에서만 검색을 하려고 검색 명령을 내리게 되면, CAM내에 동일한 엔트리 크기를 가지는 B 테이블(212)이 있으므로 A 와 B 테이블은 동시에 검색되고 두 테이블 내에서 최초로 검색되어 일치된 엔트리 값을 그 결과로 얻게 될 것이다. 그래서 A 테이블에서 일치가 최초로 발생하면 원하는 결과 값을 얻을 수 있으나, 만일 B 테이블(212)에서 최초로 일치가 발생한 경우에는 원하는 결과를 얻지 못하게 되는 상황이 발생하게 된다.

본 발명의 목적은 동일한 CAM 엔트리 크기를 가지는 다양한 테이블을 CAM내에 구성하는 네트워크 장치의 경우, 검색하지 못하는 단점을 갖는 종래의 기술을 극복할 수 있는 CAM 엔트리 추가 방법을 발명하였다. 본 발명으로 인하여 동일한 크기의 엔트리를 갖는 테이블의 경우 CAM 방식에서 검색하지 못한 단점을 극복하여 검색할 수 있게 되었다.

제 1 도 네트워크 환경과 네트워크 장치 내에서 관리되는 테이블 구조

제 2 도 CAM내에 들어가는 테이블들의 실시 예

제 3 도 네트워크 장치 내 패킷 전달 방법

제 4 도 CAM 테이블에 테이블 구분자 정보를 포함한 엔트리 추가 방법

제 5 도 테이블 구분자 값 설정 방법

제 6 도 CAM 테이블에 테이블 구분자 정보를 포함하여 추가한 엔트리 구조

제 7 도 테이블 구분자 값 설정 방법의 실시 예

제 8 도 CAM 테이블 내 엔트리 검색 방법

이하 첨부된 도면에 의해 본 발명의 구성을 설명하면 다음과 같다.

제 1 도 네트워크 환경과 네트워크 장치 내에서 관리되는 테이블 구조는 MAC 주소(130)와 IP 주소(140) 테이블을 갖는다. 이들 테이블은 스위치 라우터(120)내에 존재하며, 인터넷(110)을 통한 데이터 전송을 하거나, 스위치라우터(120)에 연결된 컴퓨터들(121,122, 123)과 데이터 전송을 한다. 발신지에서 착신지까지 데이터를 전송하기 위한 정보는 송신 IP 주소(150), 송신 포트 번호(160), 수신 IP 주소(170), 수신 포트 번호(180)등으로 구성한다. 이러한 정보를 갖는 테이블 내 데이터 필드들로 이루어진 튜플을 CAM에 저장한 후 CAM을 검색해서 찾고 그 결과를 적절하게 패킷 송수신에 이용하는 것이다.

제 2 도 CAM내에 들어가는 테이블들의 실시 예에서 보면 사용자가 CAM 메모리(210) 내에 36bit-size entry를 갖는 Table A(211)에서만 검색을 하려고 검색 명령을 내리게 되면, CAM내에 동일한 엔트리 크기를 가지는 Table A(211)와 Table B(212)가 있으므로 Table A(211)와 Table B(212)는 동시에 검색되고 두 테이블 내에서 최초로 검색되어 일치된 엔트리 값을 그 결과로 얻게 될 것이다. 그래서 원하는 엔트리가 A 테이블(211)에 있는 경우, Table A(211)에서 일치가 최초로 발생하면 원하는 결과 값을 얻을 수 있으나, 만일 Table B(212)에서 최초로 일치가 발생한 경우에는 원하는 결과를 얻지 못하게 되는 문제가 발생된다.

72bit-size entry를 갖는 Table C(213)인 경우에는 동일한 크기가 하나 밖에 없으므로 항상 하나만 선택되므로 문제가 발생하지 않는다.

144bit-size entry를 갖는 Table D(214), Table E(215), Table F(216)인 경우에는 동일한 크기의 테이블이 CAM내에 3개가 있으므로 Table D와 Table E, Table F는 동시에 검색되고 3개 테이블 내에서 최초로 검색되어 일치된 엔트리 값을 그 결과로 얻게 될 것이다. 그래서 원하는 엔트리가 F 테이블(216)에 있는 경우,Table F(216)에서 일치가 최초로 발생하면 원하는 결과 값을 얻을 수 있으나, 만일 Table D(214) 또는 Table E(215)에서 최초로 일치가 발생한 경우에는 원하는 결과를 얻지 못하게 되는 문제가 발생된다.

제 3 도 네트워크 장치 내 패킷 전달 방법은 테이블 초기화(310)에서 CAM 엔트리를 추가(311)하고, 데이터 패킷을 수신(320)하고, 테이블 검색 용 튜플을 작성(330)한 후에, 테이블을 검색(340), 테이블 검색 결과분석(350)을 한다. 테이블 검색 결과분석(350)에서는 CAM 엔트리 추가(351)를 하고 해당 포트로 패킷 송신 또는 폐기를 한다. 이와 같이 일련의 절차가 종료되면, 데이터 패킷 수신(320)으로 이동한다.

즉, 먼저 CAM에 들어갈 테이블을 위한 기본적인 초기화 루틴을 실시한다. 이 때 필요한 테이블을 미리 만들 수도 있다. 그런 뒤 데이터 패킷을 수신하게 되는데 수신된 패킷이 유효한지 여부와 어떤 포트로 전달할 것인지를 결정하게 되는데 이때 사용되는 것이 CAM에 있는 테이블이다. 테이블을 초기화할 때(310)와 테이블의 검색 결과를 분석할 때(350) 'CAM 엔트리 추가'(311, 351)라는 항목이 있는데, 엔트리 추가시 동일한 CAM 엔트리 크기를 가지는 복수의 테이블을 구분할 수 있는 테이블 구분자를 테이블 내 하나의 필드로 추가하는 것이 이 발명의 요지이다.

제 4 도 CAM 테이블에 테이블 구분자 정보를 포함한 엔트리 추가 방법은 제 3 도의 CAM 엔트리 추가(311, 351)하는 방법을 나타낸 것이다. 종래의 기술에서 갖고 있지 못한 CAM 엔트리 추가(311, 351)하는 방법을 제 4 도에서 설명한다. 첫째로 만들고자하는 테이블의 엔트리 크기 값을 정의한다(401). 그리고 테이블의 엔트리 크기 값보다 큰 CAM 엔트리 크기 값을 정한다(402). 동일한 크기의 CAM 엔트리를 가지는 다른 테이블들 중에서 가장 큰 데이터 튜플을 가지는 테이블의 데이터 튜플 크기 값과 CAM 엔트리 크기 값의 차이가 테이블 구분자의 크기(403)가 되고, 테이블 구분자 크기를 비교(404)하여 테이블 구분자 크기가 0보다 크면, 테이블 구분자 크기 내에서 실제 구분자 값을 설정(405)하고, 테이블 구분자 크기를 비교(404)하여 테이블 구분자 크기가 0보다 작으면, CAM 엔트리 크기 선택(402)를 다시 실행한다.

제 5 도 테이블 구분자 값 설정 방법은 테이블 구분자 값 설정 방법(405)을 구체적으로 설명하고 있다. 테이블 구분자 값의 범위는 0 ∼ (2^{테이블 구분자 크기}-1) 까지 가능한데(501), 이것은 동일한 크기의 엔트리를 가지는 가능한 테이블의 수를 의미하기도 한다. 테이블에 첫 번째 테이블 값을 세팅(502)한다. 첫 번째 테이블의 구분자 값을 0으로 초기화(503)한 후, 만일 구분자 값을 비교(504)하여 2^{(테이블 구분자 크기)}보다 작게 되면, 테이블에 동일크기의 엔트리를 가지는 다음 테이블을 세팅(505)하고 존재하는 테이블인가를 수행(506)하여, 아니면 종료(508)하고, 존재하는 테이블이면 해당 테이블의 구분자 값을 1씩 증가시켜서 구분자 값을 설정(507)한다. 만일 구분자 값을 비교(504)하여 2^{(테이블 구분자 크기)}보다 크거나 같게 되면, 제 4 도에서의 테이블 구분자 크기 구하는 방법을 다시 수행(401)하여 더 큰 크기의 구분자 값을 할당할 수 있도록 한다. 이렇게 설정된 테이블 구분자 값은 테이블 내 엔트리 작성 시 함께 작성되어 하나의 엔트리가 된다(406).

제 6 도 CAM 테이블에 테이블 구분자 정보를 포함하여 추가한 엔트리구조는 72 bit인 구조와 144 bit인 구조가 있다. 72bit 크기의 CAM 엔트리 내에 48bit의 검색 데이터 튜플을 가지는 경우 최대 24bit 크기의 테이블 구분자(601)가 있다. 그리고 검색하고자하는 데이터 튜플의 크기가 112bit이고 CAM이 지원 가능한 엔트리 크기가 144bit인 경우, 같은 크기의 144bit 엔트리를 가지는 또 다른 테이블의 테이블 구분자 값이 16bit 크기이면 다음과 같이 Reserved 필드(603)를 추가하여 테이블 구분자 값 크기를 16bit로 한다(602).

제 7도는 테이블 구분자 값 설정 방법의 실시 예이다. 테이블 A와 B는 36bit 크기의 CAM 엔트리를 가지는 테이블로서 각각 0 값(701)과 1 값(702)을 테이블 구분자 값으로 사용하고 있다. 테이블 구분자의 크기는 6bit 이다. 테이블 D와 E, F는 144bit 크기의 CAM 엔트리를 가지는 테이블로서 각각 0 값(704)과 1 값(705), 그리고 2 값(706)을 테이블 구분자값으로 사용하고 있다. 테이블 구분자의 크기는 8bit 이다.

이렇게 테이블 엔트리 내에 테이블 구분자를 두어 테이블을 생성함으로써 동일한 크기의 CAM 엔트리를 가지는 두 개 이상의 테이블이 CAM에 있더라도 검색 시 검색 결과를 목적 테이블에서만 얻을 수 있게 되었다.

검색방법은 제 8 도에 나온 것과 같이 먼저 테이블 구분자와 함께 테이블 검색용 튜플을 작성(801)한 후, 검색용 테이블 구분자를 추가(802)하고, CAM검색을 실시(803)한다. match된 엔트리의 유무를 판단(804)하고, 없으면 검색하고자 하는엔트리가 해당 테이블에 없음(806)을 지정하고, 있으면 테이블 구분자에서 해당 테이블에서 찾음(805)을 실행한다. 이렇게 얻어진 결과는 제 3 도의 마지막으로 패킷을 폐기할 것인지 해당 목적지로 송신할 것인지를 결정(360)하게 된다.

이상에서 설명한바와 같이 본 발명은 동일한 엔트리 크기를 가지는 테이블을 구분할 수 있는 테이블 구분자를 테이블 엔트리 내에 둠으로써 동일한 크기의 엔트리를 갖는 경우 CAM 방식에서 검색하지 못한 단점을 극복하여 검색할 수 있게 되었다.

종래의 기술인 CAM이 가지는 단점은 CAM의 특징상 엔트리 크기가 36bit, 72bit, 144bit, 288bit 등과 같이 고정되어 있다는 것과 같은 크기의 엔트리를 가지는 테이블들 간에는 구분하여 검색할 수 있는 방법이 없다는 것이다. 이러한 단점을 해결하기위해서 복수의 테이블 검색 시 검색하고자 하는 테이블 만을 검색할 수 있는 발명의 효과가 발생하였다.

Claims (3)

1. 네트워크 환경과 네트워크 장치 내에서 관리되는 MAC 주소(130)와 IP 주소(140) 등의 테이블 구조를 갖고, 이들 테이블은 스위치라우터(120)내에 존재하며, 인터넷(110)을 통한 데이터 전송을 하거나, 스위치라우터(120)에 연결된 컴퓨터들(121,122, 123)들과 데이터 전송하고, 발신지에서 착신지까지 데이터를 전송하기 위한 정보는 송신 IP 주소(150), 송신 포트 번호(160), 수신 IP 주소(170), 수신 포트 번호(180) 등으로 구성한 환경에서,

   Ternary CAM을 이용하는 네트워크 장치에서, 동일한 크기의 CAM 엔트리를 가지는 테이블들이 존재하는 경우, 테이블들을 구분할 수 있는 테이블 구분자를 테이블 내 하나의 필드로 추가하는 방법으로,

   네트워크 장치 내 패킷 전달 방법은 테이블 초기화(310)에서 CAM 엔트리를 추가(311)하고, 데이터 패킷을 수신(32)하고, 테이블 검색 용 튜플작성(330)한 후에, 테이블을 검색(340), 테이블 검색 결과분석(350)하여, 테이블 검색 결과분석(350)에서 CAM 엔트리 추가(351)를 하고, 해당 포트로 패킷 송신 또는 폐기를 하고, 이와 같이 일련의 절차가 종료되면, 데이터 패킷 수신(320)으로 이동함에 있어서,

   CAM에 있는 테이블을 초기화할 때(310)와 테이블의 검색 결과를 분석할 때(350) 'CAM 엔트리 추가'(311, 351)라는 항목이 있는데, 엔트리 추가 시 동일한 CAM 엔트리 크기를 가지는 테이블들을 구분할 수 있는 테이블 구분자를 테이블 내하나의 필드로 추가하는 방법
2. 제 1 항에 있어서,

   만들고자하는 테이블의 엔트리 크기 값을 정의(401)하고, 테이블의 엔트리 크기 값보다 큰 CAM 엔트리 크기 값을 정의(402)하며, 동일한 크기의 CAM 엔트리를 가지는 다른 테이블들 중에서 가장 큰 데이터 튜플을 가지는 테이블의 데이터 튜플 크기 값과 CAM 엔트리 크기 값의 차이 값이 테이블 구분자의 크기(403)가 되고, 테이블 구분자 크기를 비교(404)하여 테이블 구분자 크기가 0보다 크면, 테이블 구분자 크기 내에서 실제 구분자 값을 설정(405)하고, 테이블 구분자 크기를 비교(404)하여 테이블 구분자 크기가 0보다 작으면, CAM 엔트리 크기 선택(402)을 다시 실행하여 CAM 테이블에 테이블 구분자 정보를 포함한 엔트리 추가 방법
3. 제 2항에 있어서,

   테이블 구분자 값의 범위는 0 - (2^{테이블 구분자 크기}-1) 까지 가능한 구조에서,

   테이블에 첫 번째 테이블 값을 세팅(502)하고, 첫 번째 테이블의 구분자 값을 0으로 초기화(503)한 후, 만일 구분자 값을 비교(504)하여 2^{(테이블 구분자 크기)}보다 작게 되면, 테이블에 동일크기의 엔트리를 가지는 다음 테이블을 세팅(505)하고 존재하는 테이블인가를 수행(506)하여, 아니면 종료(508)하고, 존재하는 테이블이면 해당 테이블의 구분자 값을 1씩 증가시켜서 구분자 값을 설정(507)하고, 만일 구분자 값을 비교(504)하여 2^{(테이블 구분자 크기)}보다 크거나 같게 되면, 테이블 구분자 크기 구하는 방법을 다시 수행(401)하여 더 큰 크기의 구분자 값을 할당할 수 있도록 하여, 설정된 테이블 구분자 값은 테이블 내 엔트리 작성 시 함께 작성되어 하나의 엔트리(406)가 되도록 하는 테이블 구분자값 설정 방법