Weighted Binary Search Tree for NDN Lookup

Abstract

오늘날 사용되는 IP 기반의 호스트 중심 라우팅 방식은 대용량 콘텐츠 전송과 반복 요청 트래픽 처리에서 비효율을 초래하고 있다. 동일한 데이터가 여러 사용자에 의해 반복적으로 요청되더라도 매번 원 서버로부터 데이터를 다시 전송해야 하기 때문에 네트워크 지연과 혼잡이 증가하는 문제가 발생한다. 이러한 한계를 극복하기 위해 등장한 이름 기반 네트워킹(Named Data Networking, NDN)은 IP 주소가 아닌 데이터 이름 기반으로 패킷을 전달하고, 네트워크 내부 캐싱과 데이터 중심 보안 모델을 제공함으로써, 이동성이 크거나 연결이 불안정한 환경에서도 낮은 지연과 높은 안정성을 보장하는 차세대 네트워크 아키텍처이다. 그러나 NDN 라우터 내부에서 수행되는 핵심 연산인 최장길이 이름 프리픽스 매칭(Longest Name Prefix Matching, LNPM)을 기존의 이름 접두사 트라이(Name Prefix Trie, NPT)로 처리할 경우 트리 깊이가 이름 컴포넌트 수에 비례해 선형 증가하고, 다수의 빈 내부 노드 및 오프칩 메모리 접근이 누적되어 조회 시간이 크게 상승하는 문제가 존재한다. 이러한 탐색구조의 편향과 메모리 접근 비용을 줄이기 위해, 본 연구는 가중치 이진 트리인 Weighted Binary Search Tree(WBST)에 주목하였다. 본 연구는 프리픽스 목록을 특수 사전순으로 정렬하고, 전체 가중치 합의 절반 이상이 되는 최초 프리픽스를 피벗으로 선택하여 좌·우 서브트리의 가중치 균형을 재귀적으로 맞추는 가중치 절반 피봇 규칙(half-weight pivot rule) 기반 구조를 적용하였다. 이 구조는 편향된 이름 분포에서도 기대 탐색 깊이를 억제하고 평균 메모리 접근 횟수를 최소화하여 결과적으로 통신망의 성능과 직결되는 LNPM 기능이 선속도로 안정적으로 동작할 수 있도록 한다.