기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
패킷 분류를 위한 스마트 셋-프루닝 트라이
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 패킷 분류를 위한 스마트 셋-프루닝 트라이
저자명
민세원,이나라,임혜숙,Min. Seh-Won,Lee. Na-Ra,Lim. Hye-Sook
간행물명
한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스
권/호정보
2011년|36권 |pp.1285-1296 (12 pages)
발행정보
한국통신학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

패킷분류는 라우터의 가장 기본적이면서도 중요한 기능 중의 하나이며, 실시간 전송을 요구하는 새로운 인터넷 응용 프로그램의 등장과 더불어 그 중요성이 더욱 커지고 있다. 패킷분류는 입력 패킷에 대하여 선속도로 이루어져야 하며, 여러 헤더 필드에 대해 다차원 검색을 수행해야 하기 때문에 라우터 설계의 어려운 문제 중에 하나이다. 고속의 패킷분류를 제공하기 위한 다양한 패킷분류 알고리즘이 제안되어 왔으며, 그 중 계층적 접근 방식을 사용한 알고리즘은 하나의 필드에 대하여 검색이 수행될 때마다 많은 검색 영역이 제거되기 때문에 효율적이다. 그러나 계층적 구조는 역추적이라는 문제를 내재하고 있으며, 이를 해결하기 위해 사용되는 셋-프루닝 트라이나그리드-오브-트라이는 지나치게 많은 노드 복사를 야기하거나, 선-계산이라는 복잡한 과정을 요구한다. 본 논문에서는 셋-프루닝 하위 트라이의 간단한 합병을 통하여 복사되는 노드의 개수를 줄일 수 있는 스마트 셋-프루닝 구조를 제안한다. 시뮬레이션 결과 제안된 구조는 셋-프루닝 트라이와 비교하여 복사되는 노드 수 및 룰 수가 2-8% 줄어듦을 확인하였다.

기타언어초록

Packet classification is one of the basic and important functions of the Internet routers, and it became more important along with new emerging application programs requiring real-time transmission. Since packet classification should be accomplished in line-speed on each incoming input packet for multiple header fields, it becomes one of the challenges in designing Internet routers. Various packet classification algorithms have been proposed to provide the high-speed packet classification. Hierarchical approach achieves effective packet classification performance by significantly narrowing down the search space whenever a field lookup is completed. However, hierarchical approach involves back-tracking problem. In order to solve the problem, set-pruning trie and grid-of-trie algorithms are proposed. However, the algorithm either causes excessive node duplication or heavy pre-computation. In this paper, we propose a smart set-pruning trie which reduces the number of node duplication in the set-pruning trie by the simple merging of the lower-level tries. Simulation result shows that the proposed trie has the reduced number of copied nodes by 2-8% compared with the set-pruning trie.