IP 주소 검색을 위한 블룸 필터를 적용한 새로운 리프푸싱 트라이

이정원, 심채연, 박슬기 et al. · 대한전자공학회 학술대회 · 2015

This paper proposes a new IP address lookup algorithm which applies a Bloom filter for the prefix search in a leaf-pushing trie. The proposed approach is differentiated from a previous approach in the way of programming the Bloom filter. The proposed algorithm in this paper does not program every node in a trie but programs internal nodes with at least a prefix child. Hence the Bloom filter size is greatly reduced. In addition, the proposed algorithm starts the search process from the longest length, which is 32 bits in IPv4, in order to utilize the characteristic of the leaf-pushing trie. Simulations using actual routing tables show that the proposed approach achieves less than 1.25 number of hash table accesses in average to perform an IP address lookup.

Cited by 0 works.

Authors