[논문]IP 주소 검색을 위한 최적화된 영역분할 이진검색 구조

박경혜; 임혜숙

문제 정의

본 논문에서는 영역분할 이진 검색 알고리즘의 최적화를 위하여 영역분할 이진 검색 알고리즘의 최대 단점인 엔트리의 개수를 줄이고, 두 개의 선 계산 필드를 하나로 합쳐 메모리 요구량을 줄이는 방법에 대하여 연구하였다.
본 논문에서는 영역분할 이진 검색의 단점인 라우팅 테이블의 엔트리 수가 프리픽스 개수의 최대 2배가 될 수 있어 메모리 요구량(memory requirement)이 커지는 단점을 보완하기 위하여, 어떤 프리픽스의 끝점과 다른 프리픽스의 시작점이 연속되는 경우, 끝점을 제거하여 엔트리 개수를 줄이는 방법과, “엔트리와 같은 경우” 필드와 "엔트리보다 큰 경우” 필드를 하나로 합치는 방법을 통해 메모리 요구량을 줄이는 최적화 방법에 대하여 연구하였다. 이러한 최적화 구조는 [8]의 논문에서 기본 아이디어가 제안된 바 있으며, 본 논문에서는 구체적인 예시를 통하여, 최적화 구조의 원리를 설명하였으며, 기존의 영역분할 이진 검색 알고리즘과의 성능 비교뿐 아니라, 기존에 나와 있는 다양한 이진 검색 알고리즘과의 성능 비교를 통하여 최적화 구조의 장점을 보였다.
하지만 불필요한 엔트리가 라우팅 테이블에 존재하여 필요 이상의 메모리가 요구된다는 단점이 있다. 따라서 본 논문에서는 영역분할 이진 검색 (BSR) 알고리즘의 성능을 최적화하는 방안을 연구하였다. 엔트리 개수의 최적화를 위하여, 연속된 엔트리의 끝 점을 제거하는 방법으로 엔트리의 개수를 최대 34%까지 감소시킬 수 있음을 보였으며, 두 개의 선 계산 필드를 하나로 합치는 방법으로 요구하는 메모리의 양을 최대 45%까지 줄일 수 있음을 보였다.

제안 방법

이진 검색 트리两는 이진 트라이가 갖고 있는 단점인 빈 내부 노드를 없애며, 프리픽스 값에 대하여 이진 검색을 수행하]는 방식이다 이진 검색 트리 알고리즘은 다양한 길이를 갖는 프리픽스들의 크기 비교를 가능하게 하는 새로운 정의를 제안하여, 프리픽스들을 크기별로 정렬 한 후 이진 트리를 구성하였다.
이진 검색 트리는 먼저 디스조인트 프리픽스와인클로져 프리픽스만으로 이루어진 리스트를 정렬하여 중간에 위치한 프리픽스를 선택하여 이진 검색 트리의 노드로 결정하며, 인클로져 프리픽스가 선택이 된 경우, 해당 인클로즈드 프리픽스들이 리스트에 추가되는 방식을 재귀적으로 반복함에 의하여 이진 검색 트리를 구성하게 된다. 그림 2에 표 1의 프리픽스 셋에 대하여 구성된 이진 검색 트리를 보였다.
영역분할 이진 검색 알고리즘에서는 영역의 시작점과 끝점이 모두 라우팅 테이블의 엔트리가 되는데, 각 엔트리에는 해당 엔트리의 값과 일치하였을 때의 포워딩 정보와, 해당 엔트리의 값보다 큰 경우에 해당하는 포워딩 정보를 선계산(pre-computation) 하여 저장한다. 이러한 선계산을 갖는 엔트리로 이루어진 리스트를 크기별로 정렬 한 후, 이진 검색을 수행한다. 예를 들어, 표 1의 프리픽스에서, 가장 길이가 긴 프리픽스 길이인 6에 맞추어서 프리픽스 뒤에 0을 붙여 시작점(start point)을 만들고 1을 붙여 끝점(end point)을 만든다.
그러므로 “엔트리와 같은 경우” 필드에는 프리픽스 P4에 해당하는 포워딩 정보를, “엔트리보다 큰 경우” 필드에는 프리픽스 P5에 해당하는 포워딩 정보를 저장하게 된다. 본 논문에서는 설명의 편의를 위하여 포워딩 정보대신 프리픽스의 이름을 사용하여 선계산을 수행하였으며, 그 결과를 표 4에 보였다
최적화 방법에 대하여 연구하였다. 이러한 최적화 구조는 [8]의 논문에서 기본 아이디어가 제안된 바 있으며, 본 논문에서는 구체적인 예시를 통하여, 최적화 구조의 원리를 설명하였으며, 기존의 영역분할 이진 검색 알고리즘과의 성능 비교뿐 아니라, 기존에 나와 있는 다양한 이진 검색 알고리즘과의 성능 비교를 통하여 최적화 구조의 장점을 보였다.
Ⅳ.장의 성능 평가를 통하여 이를 확인하였다.
[8]의 경우, 끝점을 제거하고 두 개의 필드를 하나로 통합하는 실험을 하였으며 생성된 라우팅 테이블의 엔트리 수와 필드의 수를 기존의 영역분할. 이진 검색(BSR)과 비교하였다. 본 논문에서는 끝점을 제거하고 두 개의 필드를 통합한 라우팅 테이블에서 검색 속도와 메모리 요구량을 원래의 영역분할 이진 검색 알고리즘과 비교하였으며, 다양한 기존의 이진 검색 알고리즘들과 비교하였다.
이진 검색(BSR)과 비교하였다. 본 논문에서는 끝점을 제거하고 두 개의 필드를 통합한 라우팅 테이블에서 검색 속도와 메모리 요구량을 원래의 영역분할 이진 검색 알고리즘과 비교하였으며, 다양한 기존의 이진 검색 알고리즘들과 비교하였다. 룰의 개수를 N, 프리픽스의 최대 길이를 W라 하였을 때, 기존의 이진 검색 구조와 본 논문의 최적화 구조의 메모리접근 횟수를 나타내면 표 6과 같다.
영역분할 이진 검색 알고리즘과 최적화 구조의 경우 모두 0(N)의 메모리 요구량과 O(logN)의 메모리접근 횟수로 표현 할 수 있으나, 실제 성능은 점근적으로 표현되기 어려운 구조이므로 실제 라우터에서 사용하는 데이터를 사용하여 성능을 측정하였다’ 메모리 접근은 IP 주소 검색과정 중 시간을 가장 많이 소요하는 작업으로서, 메모리 접근 회수는 성능 비교의 척도로 사용되어 왔으므로” 본 논문에서도 각 알고리즘의 메모리 접근 회수를 사용하여 성능을 비교하였다. 라우팅 데이터를 사용하여 시뮬레이션을 한 결과 기존의 영역분할 이진 검색(BSR) 알고리즘과 최적화 구조(optimized binary-search-on-range, OBSR) 모두 바른 검색 결고}를 보임을 확인하였으며, 두 구조의 엔트리 수를 비교한 결과를 표 7에 보였다.

성능/효과

본 논문의 최적화 대상인 영역분할 이진 검색 알고리즴3에서는 모든 프리픽스는 크기가 [0, 23勺] 인직선상의 영역으로 표현될 수 있으며, 프리픽스의 길이가 길수로 작은 영역을, 짧을수록 큰 영역을 차지함을 이용한다. 먼저 프리픽스를 영역으로 표현하는데 있어, 다양한 길이의 프리픽스를 모두 최대 프리픽스 길이로 확장하되, 0으로 패딩한 값을 영역의 시작점(start point)으5, 1로 패딩한 값을 영역의 끝점(end point)으로 정한다.
표 4와 표 5를 비교하여 보면 엔트리의 개수는 11개에서 10개로 필드의 개수는 두 개에서 한 개로 줄어들었음을 볼 수 있으며, 프리픽스의 개수가 많아질수록 줄어드는 엔트리의 개수가 많아져 최적화 구조의 성능이 더 좋아질 것으로 생각된다. Ⅳ.
본 논문에서는 실제 백 본 라우터에서 사용된 다양한 크기의 라우팅 데이테이를 가지고 성능을 실험하였다 IPv4에서 사용하는 데이터의 경우 프리픽스의 최대 길이가 32비트 이며, CIDR(Classless Inter-Domain Routing) 주소 체계로 인해 프리픽스의 길이가 8에서 32비트의 다양한 분포를 보인다. [8]의 경우, 끝점을 제거하고 두 개의 필드를 하나로 통합하는 실험을 하였으며 생성된 라우팅 테이블의 엔트리 수와 필드의 수를 기존의 영역분할.
라우팅 데이터를 사용하여 시뮬레이션을 한 결과 기존의 영역분할 이진 검색(BSR) 알고리즘과 최적화 구조(optimized binary-search-on-range, OBSR) 모두 바른 검색 결고}를 보임을 확인하였으며, 두 구조의 엔트리 수를 비교한 결과를 표 7에 보였다.
표 7의 결과에서 볼 수 있듯이, 최적화 구조는 두 개의 필드를 하나로 합치는 과정에서, “엔트리와 같은 경우“에 저장된 값이 최대 길이의 프리픽스인 경우 새로운 엔트리가 생성됨에도 불구하고, 한 영역의 끝점과 다른 영역의 시작점이 연속된 경우 끝점(end point)을 제거함으로써, 엔트리 수에 있어 기존의 영역분할 이진 검색(BSR) 보다 최대 34% 감소한다는 것을 알 수 있으며, 라우팅 테이블의 크기가 클수록, 그 효과가 뛰어남을 알 수 있다. 특히 Grouptlcom의 경우, 원래 라우팅 테이블의 프리픽스의 개수보다도 적은 수의 엔트리를 갖는 라우팅 테이블의 구성이 가능함을 볼 수 있었으며, 이는 라우팅 테이블 자체가 불필요한 프리픽스를 많이 포함하고 있는 것으로 생각될 수 있다
이진 검색의 성능을 보-였다. 표 8에서 보여주는 바와 같이, 프리픽스의 개수가 220, 000이 넘는 라우팅 데이터에 대하여 최대 18번, 평균 17.4번의 메모리 접근으로 매우 빠른 1P주소 검색이 가능함을 알 수 있으며, 라우팅 데이터의 크기가 커져도 그 성능이 크게 나빠지지 않는 것을 볼 수 있다. 요구되는 메모리의 양에 있어서는 프리픽스당 5 byte 에서 9 byte의 적은 메모리를 요구하며' 특히 라우팅 데이터의 크기가 커질수록 프리픽스당 요구되는 메모리의 양이 적어져, 확장성이 매우 우수함을 볼 수 있다.
영역분할 이진 검색 알고리즘은 기존의 다른 이진 검색 알고리즘에 비하여 월등히 좋은 검색 성능을 보이며, 최적화된 구조는 영역분할 이진 검색 알고리즘의 평균 검색 성능을 조금 더 향상 시킨 것을 볼 수 있다. 특별히 영역분할 이진 검색 알고리즘 및 최적화 구조의 성능은 라우텅 테이블의 크기가 커져도 그 성능이 크게 나빠지지 않으므로 확장성이 매우 뛰어난 구조임을 알 수 있다.
수 있다. 특별히 영역분할 이진 검색 알고리즘 및 최적화 구조의 성능은 라우텅 테이블의 크기가 커져도 그 성능이 크게 나빠지지 않으므로 확장성이 매우 뛰어난 구조임을 알 수 있다. 최적화된 영역 분할 이진 검색 알고리즘과 원래의 영역분할 이진 검색E 알고리즘의 평균 검색 성능을 비교할 때, 라우팅 테이블의 크기가 작은 경우, 최적화 구 조의엔 트리 개수가 원래의 영역분할 이진 검색의 엔트리 개수보다 적음에도 불구하고, 초!적화 구조의 평균 검색 성능이 원래의 영역분할 이진 검색 알고리즘의 검색성능보다 조금 나쁜 것을 볼 수 있다.
특별히 영역분할 이진 검색 알고리즘 및 최적화 구조의 성능은 라우텅 테이블의 크기가 커져도 그 성능이 크게 나빠지지 않으므로 확장성이 매우 뛰어난 구조임을 알 수 있다. 최적화된 영역 분할 이진 검색 알고리즘과 원래의 영역분할 이진 검색E 알고리즘의 평균 검색 성능을 비교할 때, 라우팅 테이블의 크기가 작은 경우, 최적화 구 조의엔 트리 개수가 원래의 영역분할 이진 검색의 엔트리 개수보다 적음에도 불구하고, 초!적화 구조의 평균 검색 성능이 원래의 영역분할 이진 검색 알고리즘의 검색성능보다 조금 나쁜 것을 볼 수 있다. 이는 기존의 이진 검색 알고리즘에서 특정 엔트리와 정확하게 일치하여 검색을 즉시 종료시킬 수 있는 인풋들에 대하여 최적화 방법으로 엔트리 개수를 줄였을 때, 정확하게 일치하는 경우에 해당되지 못하고 검색을 끝까지 진행하여야 하는 경우가 발생하기 때문인 것으로 판단된다.
타 구조와 비교하여 보았다. 영역분할 이진 검색알고리즘의 최적화 구조는 라우텅 데이터의 크기가 커질수록 불필요한 엔트리를 삭제하고 “엔트리보다 큰 경우” 필드와 “엔트리와 같은 경우” 필드를 “엔트리보다 크거나 같은 경우” 필드로 합쳐 메모리 요구량을 감소시킴으로써, 타 구조와 비교하였을 때 메모리 요구량에서 매우 효율적인 구조라는 것을 알 수 있다. 또한 기존의 영역분할 이진검색 구조와 비슷한 메모리 요구량을 보이는 이진 검색 트리 구조 보다 최적화된 구조의 메모리 요구량이 현저히 적다.
영역분할 이진 검색알고리즘의 최적화 구조는 라우텅 데이터의 크기가 커질수록 불필요한 엔트리를 삭제하고 “엔트리보다 큰 경우” 필드와 “엔트리와 같은 경우” 필드를 “엔트리보다 크거나 같은 경우” 필드로 합쳐 메모리 요구량을 감소시킴으로써, 타 구조와 비교하였을 때 메모리 요구량에서 매우 효율적인 구조라는 것을 알 수 있다. 또한 기존의 영역분할 이진검색 구조와 비슷한 메모리 요구량을 보이는 이진 검색 트리 구조 보다 최적화된 구조의 메모리 요구량이 현저히 적다. 본 논문에서 연구한 최적화 구조는 영역 분할이진 검색의 메모리 요구량에 관한 성능을 최대 45%까지 향상시킨 것을 볼 수 있다.
또한 기존의 영역분할 이진검색 구조와 비슷한 메모리 요구량을 보이는 이진 검색 트리 구조 보다 최적화된 구조의 메모리 요구량이 현저히 적다. 본 논문에서 연구한 최적화 구조는 영역 분할이진 검색의 메모리 요구량에 관한 성능을 최대 45%까지 향상시킨 것을 볼 수 있다.
따라서 본 논문에서는 영역분할 이진 검색 (BSR) 알고리즘의 성능을 최적화하는 방안을 연구하였다. 엔트리 개수의 최적화를 위하여, 연속된 엔트리의 끝 점을 제거하는 방법으로 엔트리의 개수를 최대 34%까지 감소시킬 수 있음을 보였으며, 두 개의 선 계산 필드를 하나로 합치는 방법으로 요구하는 메모리의 양을 최대 45%까지 줄일 수 있음을 보였다. 또한 큰 프리픽스 셋으로 갈수록 패킷을 포워딩하는 속도가 상대적으로 좋아져 확장성이 우수한 구조임을 보았다.
엔트리 개수의 최적화를 위하여, 연속된 엔트리의 끝 점을 제거하는 방법으로 엔트리의 개수를 최대 34%까지 감소시킬 수 있음을 보였으며, 두 개의 선 계산 필드를 하나로 합치는 방법으로 요구하는 메모리의 양을 최대 45%까지 줄일 수 있음을 보였다. 또한 큰 프리픽스 셋으로 갈수록 패킷을 포워딩하는 속도가 상대적으로 좋아져 확장성이 우수한 구조임을 보았다. 기존에 연구되어온 다른 이진 검색 알고리즘과의 성능 비교를 통하여 영역 분할이진 검색 알고리즘의 최적화 구조가 검색 속도나 메모리 사용량에 있어 월등히 우수함을 보였다.
또한 큰 프리픽스 셋으로 갈수록 패킷을 포워딩하는 속도가 상대적으로 좋아져 확장성이 우수한 구조임을 보았다. 기존에 연구되어온 다른 이진 검색 알고리즘과의 성능 비교를 통하여 영역 분할이진 검색 알고리즘의 최적화 구조가 검색 속도나 메모리 사용량에 있어 월등히 우수함을 보였다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] IP 주소 검색을 위한 최적화된 영역분할 이진검색 구조
Optimized Binary-Search-on- Range Architecture for IP Address Lookup 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

Keyword

AI 본문요약
AI-Helper

문제 정의

제안 방법

성능/효과

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

활용도 분석정보

활용도 Top5 논문

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] IP 주소 검색을 위한 최적화된 영역분할 이진검색 구조 Optimized Binary-Search-on- Range Architecture for IP Address Lookup 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

Keyword

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

성능/효과

참고문헌 (11)

이 논문을 인용한 문헌

저자의 다른 논문 :

박경혜 (3) 임혜숙 (34)

활용도 분석정보

활용도 Top5 논문 더보기

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] IP 주소 검색을 위한 최적화된 영역분할 이진검색 구조
Optimized Binary-Search-on- Range Architecture for IP Address Lookup 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

활용도 Top5 논문