IPv6 주소 검색을 위한 블룸 필터를 사용한 레벨에 따른 이진 검색 구조 (Binary Search on Levels Using Bloom Filter for IPv6 Address Lookup)

서지정보

· 발행기관 : 한국통신학회
· 수록지 정보 : 한국통신학회논문지B / 34권 / 4호 / 403 ~ 418페이지
· 저자명 : 박경혜, 임혜숙

초록

IPv6는 32 비트를 갖는 IPv4의 주소 공간 부족 문제를 해결하기 위하여 제안된 새로운 IP주소 체계로서 128비트를 갖는다. 그러므로 IPv6의 라우팅 테이블을 트라이 구조에 저장한다고 가정할 때, IPv4에 비해 매우 많은 레벨이 존재하게 된다. 따라서 IPv6 주소 검색을 위해서는 트라이 레벨에 따른 선형 검색보다 레벨에 따른 이진 검색 구조가 적합하며, 검색 성능이 더 우수하다는 장점이 있다. 본 논문에서는 IPv6를 위한 트라이 레벨에 따른 새로운 이진 검색 알고리즘을 제안한다. 본 논문에서 제안하는 구조는 레벨에 따른 이진 검색의 수행 시 통합 블룸 필터를 사용하여 노드가 존재하지 않는 레벨을 미리 걸러주는 방법을 통하여 외부 메모리 접근 횟수를 줄인다. 실제 라우터에서 사용하는 IPv6 라우팅 데이터를 사용하여 시뮬레이션을 수행하였으며, 1096개의 엔트리를 갖는 라우팅 테이블에 대하여 평균 1~3의 메모리 접근을 통하여 IPv6 주소 검색이 가능함을 보았다.

영어초록

IP version 6 (IPv6) is a new IP addressing scheme that has 128-bit address space. IPv6 is proposed to solve
the address space problem of IP version 4 (IPv4) which has 32-bit address space. For a given IPv6 routing set,
if a forwarding table is built using a trie structure, the trie has a lot more levels than that for IPv4. Hence, for
IPv6 address lookup, the binary search on trie levels would be more appropriate and give better search
performance than linear search on trie levels. This paper proposes a new IPv6 address lookup algorithm
performing binary search on trie levels. The proposed algorithm uses a Bloom filter in pre-filtering levels which
do not have matching nodes, and hence it reduces the number of off-chip memory accesses. Simulation has been
performed using actual IPv6 routing sets, and the result shows that an IPv6 address lookup can be performed
with 1-3 memory accesses in average for a routing data set with 1096 prefixes.

참고자료

· 없음