[논문]벡터 블룸 필터를 사용한 IP 주소 검색 알고리즘

변하영; 임혜숙

doi:10.5370/kiee.2016.65.12.2061

벡터 블룸 필터를 사용한 IP 주소 검색 알고리즘
IP Address Lookup Algorithm Using a Vectored Bloom Filter 원문보기

전기학회논문지 = The Transactions of the Korean Institute of Electrical Engineers, v.65 no.12, 2016년, pp.2061 - 2068

변하영 (Dept. of Electronic and Electrical Engineering, Ewha Womans University) , 임혜숙 (Dept. of Electronic and Electrical Engineering, Ewha Womans University)

Abstract ▼ AI-Helper

A Bloom filter is a space-efficient data structure popularly applied in many network algorithms. This paper proposes a vectored Bloom filter to provide a high-speed Internet protocol (IP) address lookup. While each hash index for a Bloom filter indicates one bit, which is used to identify the membership of the input, each index of the proposed vectored Bloom filter indicates a vector which is used to represent the membership and the output port for the input. Hence the proposed Bloom filter can complete the IP address lookup without accessing an off-chip hash table for most cases. Simulation results show that with a reasonable sized Bloom filter that can be stored using an on-chip memory, an IP address lookup can be performed with less than 0.0003 off-chip accesses on average in our proposed architecture.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

가설 설정

In programming, every element in a set S = {x₁, x₂, …, x_n} is programmed to the Bloom filter using k independent hash functions, each of which is used to map an element to a random number with a range {1, …, m}. To insert an element, the k bits corresponding to the k hash indices are set to 1. For n given elements, the optimal number of hash functions is k = (m/n) ln2.

제안 방법

1 is that a vector becomes useless when being programmed with the conflict. The proposed algorithm is refined to utilize the information included in the conflict vectors. In the refined structure, one bit is allocated for each output port.
The vectored Bloom filter can answer membership queries with output ports. The proposed approach improves the address lookup performance by decreasing the number of off-chip memory accesses since the off-chip hash table is accessed only when port conflicts occur. The simulation result showed that the port conflict rate and the wrong port rate both converge to 0% as the size of the vectored Bloom filter increases.

이론/모형

In this paper, we propose a new Bloom filter-based IP address lookup algorithm using a vectored Bloom filter (VBF). The remainder of this paper is organized as follows.
In this paper, we proposed a new IP address lookup algorithm using a vectored Bloom filter. The vectored Bloom filter can answer membership queries with output ports.

성능/효과

The proposed approach improves the address lookup performance by decreasing the number of off-chip memory accesses since the off-chip hash table is accessed only when port conflicts occur. The simulation result showed that the port conflict rate and the wrong port rate both converge to 0% as the size of the vectored Bloom filter increases. Hence, the proposed algorithm can provide the IP address lookup without an offchip hash table access.

참고문헌 (15)

H. J. Chao, "Next Generation Routers," Proc. IEEE, Vol. 90, No. 9, pp. 1518-1588, Sep. 2002.

상세보기
S. Fuller, T. Li, J. Yu, and K. Varadhan, "Classless Inter-Domain Routing(CIDR): An Address Assignment and Aggregation Strategy," RFC 1519, Sep.1993.
M. A. Ruiz-Sanchez, E. M. Biersack and W. Dabbous, "Survey and Taxonomy of IP Lookup Algorithms", IEEE Networks, Vol. 15, No. 2, pp. 8-23, Mar./Apr. 2001.
H. Lim and N. Lee, "Survey and Proposal on Binary Search Algorithms for Longest Prefix Match," IEEE Communications Surverys and Tutorials, Vol. 14, No. 3, pp. 681-697, Third Quarters, 2012.
T. Yand, G. Xie, Y. Li, Q. Fu, A. Liu, Q. Li, and L. Mathy, "Guarantee IP Lookup Performance with FIB Explosion," ACM Sigcomm, pp. 39-50, 2014.
P. Gupta, S. Lin, and N. Mckeown, "Routing Lookups in Hardware at Memory Access Speed." IEEE INFOCOM, pp.1240-1247, 1998.
S. Dharmapurikar, P. Krishnamurthy, and D. Taylor, "Longest Prefix Matching Using Bloom Filters," IEEE/ACM Trans. Networking, Vol. 14, No. 2, pp. 397-409, Feb. 2006.

상세보기
Y. Wang, T. Pan, Z. Mi, H. Dai, X. Guo, T. Zhang, B. Liu, and Q. Dong, "NameFilter: Achieving Fast Name Lookup with Low Memory Cost via Applying Two-Stage Bloom Filters," in Proceedings of the IEEE INFOCOM'13, pp. 93-99, 2013.
H. Lim, K. Lim, N. Lee, and K. Park, "On Adding Bloom Filters to Longest Prefix Matching Algorithms," IEEE Trans. Computers, Vol. 63, No. 2, pp. 411-423, Feb. 2014.

상세보기
P. Panda, N. Dutt, and A. Nicolau, "On-Chip vs. Off-Chip Memory: The Data Partitioning Problem in Embedded Processor-Based Systems," ACM Transactions on Design Automation of Electronics Systems, Vol. 5, No. 3, pp. 682-704, July 2000.

상세보기
B. H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors," Communications of the ACM, Vol. 13, No. 7, pp. 422-426, 1970.

상세보기
S. Tarkoma, C. E. Rothenberg, and E. Lagerspetz, "Theory and Practice of Bloom Filters for Distributed Systems," IEEE Communications Surveys and Tutorials, Vol. 14, No. 1, pp. 131-155, First Quarter, 2012.

상세보기
M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, "Scalable High Speed IP Routing Lookups," Proc. ACM SIGCOMM, pp. 25-35, 1997.
J. Mun, H. Lim and C. Yim, "Binary Search on Prefix Lengths for IP Address Lookup," IEEE Communications Letters, Vol. 10, No. 6, pp. 492-494, June 2006.

상세보기
J. Mun, and H. Lim, "New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based Algorithms," IEEE Trans. on Computers, Vol. 65, No. 5, pp. 1558-1565, May 2016.

상세보기

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

벡터 블룸 필터를 사용한 IP 주소 검색 알고리즘
IP Address Lookup Algorithm Using a Vectored Bloom Filter 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

가설 설정

제안 방법

이론/모형

성능/효과

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

벡터 블룸 필터를 사용한 IP 주소 검색 알고리즘 IP Address Lookup Algorithm Using a Vectored Bloom Filter 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

가설 설정

제안 방법

이론/모형

성능/효과

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

변하영 (1) 임혜숙 (34)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

벡터 블룸 필터를 사용한 IP 주소 검색 알고리즘
IP Address Lookup Algorithm Using a Vectored Bloom Filter 원문보기

AI 본문요약
AI-Helper