IP 주소 검색을 위한 가중 이진 프리픽스 트리 


29권  11호, pp. 911-919, 11월  2004


PDF Full-Text
  요약

IP 주소 검색은 인터넷 라우터의 필수적인 기능의 하나로서, 라우터 전체의 성능을 결정하는 중요한 요소이다. 소프트웨어에 기반한 IP 주소 검색 방식의 성능 평가 기준 중 가장 중요한 것은 라우터의 처리 속도를 보장해 주는 의미를 갖는 최대 메모리 접근 횟수이다. 이진 프리픽스 트리 방식(BPT)은 최대 메모리 접근 횟수에 있어서 기존의 다른 소프트왜어에 기반한 방식 중 우수한 방식이지만, 트리의 구조가 불균형적이 되는 단점이 있다. 본 논문에서는 기존의 BPT 방식의 트리 생성 과정에 가중치 개념을 추가하여, 완전 균형 트리에 매우 근접하는 트리를 생성하는 가중 이진 프리픽스 트리 (WBPT) 방식을 제안한다. 제안하는 WBPT 방식은 기존의 소프트웨어에 근거한 방식들에 비교하여 최대 메모리 접근 횟수에 있어서 가장 적은 성능을 보인다. 또한 3만 개 정도의 프리픽스에 대해서 L2 캐쉬에 저장이 가능한 정도의 작은 메모리 크기를 요구하고, 프리픽스의 추가, 삭제가 용이하므로 실제적인 라우터의 IP 검색을 위하여 사용될 수 있는 방식이다.

  통계
2022년 11월부터 누적 집계
동일한 세션일 때 여러 번 접속해도 한 번만 카운트됩니다. 그래프 위에 마우스를 올리면 자세한 수치를 확인하실 수 있습니다.
  관련 논문
  논문 참조

[IEEE Style]

C. Yim, H. Lim, B. Lee, "Weighted Binary Prefix Tree for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 29, no. 11, pp. 911-919, 2004. DOI: .

[ACM Style]

Changhoon Yim, Hyesook Lim, and Bomi Lee. 2004. Weighted Binary Prefix Tree for IP Address Lookup. The Journal of Korean Institute of Communications and Information Sciences, 29, 11, (2004), 911-919. DOI: .

[KICS Style]

Changhoon Yim, Hyesook Lim, Bomi Lee, "Weighted Binary Prefix Tree for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 29, no. 11, pp. 911-919, 11. 2004.

검색
(제목, 저자, 키워드)

세부 검색 ▼

관심이 많은 키워드
(상위 10개 키워드)

최근 출판 목록
(최근 3년)






pISSN : 1226 - 4717
eISSN : 2287 - 3880