효율적인 IP 주소 검색을 위한 개선된 LC-trie = Improved LC-trie for Efficient IP Address Lookup

다국어 초록 (Multilingual Abstract)

IP address lookup is one of the most important and complex functions in the router. In this paper, we propose an improved technique of LC-trie to increase the performance of IP address lookup in the high performance router. We effectively apply the prefix pruning method, which is used for the compression of the forwarding table in TCAM((Ternary Content Addressable Memory), to the LC-trie. This technique can decrease the number of memory accesses and upgrade the lookup speed. Moreover, through the real forwarding table and the real traffic distribution, we evaluate the performance of our scheme in terms of the lookup time and the number of memory access, comparing with that of the previous LC-trie.

국문 초록 (Abstract)

IP 주소 검색은 라우터에서 가장 중요하고 복잡한 기능중 하나이다. 본 논문에서는 고성능 라우터에서 IP 주소 검색의 성능을 향상시키기 위해 LC-trie를 개선하는 기법을 제안한다. TCAM(Ternary Content Addressable Memory)에서 테이블 압축을 위해 이용한 프리픽스 pruning 방법을 LC-trie에 효과적으로 적용한다. 이러한 기법은 메모리 참조 횟수를 감소시키고 검색의 속도를 높일 수 있다. 또한, 실제 사용되는 포워딩 테이블과 트래픽 분포를 사용하여 검색 시간과 메모리 참조 횟수 등의 관점에서 개선된 기법의 성능을 기존의 LC-trie 기법과 비교 평가한다.

참고문헌 (Reference)

1 "http://bgp.potaroo.net/286/bgp-active.html"

2 V. C. Ravikumar, "TCAM architecture for IP lookup using prefix properties" 24 (24): 60-69, 2004

3 M. A. Ruiz-Sanchez, "Survey and Taxonomy of IP Address Lookup Algorithms" 2001

4 H. Liu, "Routing table compaction in Ternary CAM" 22 (22): 58-64, 2002

5 W. Doeringer, "Routing on Longest Matching Prefixes" 4 : 86-97, 1996

6 F. Jing, "Performance evaluation and cache behavior of LC-trie for IP-address lookup" 29-35, 2006

7 H. J. Chao, "Next Generation Routers" 90 (90): 1518-1558, 2002

8 G. Varghese, "Network Algorithmics" Morgan Kaufmann Pub. 2005

9 V. C. Ravikumar, "Modified LC-trie based efficient routing lookup" 177-182, 2002

10 S. Nilsson, "IP-Address Lookup using LC-Tries" 17 : 1083-1092, 1999

11 D. Shah, "Fast Updating Algorithm for TCAMs" 21 (21): 36-47, 2001

12 A. J. McAuley, "Fast Routing Table Lookup using CAMs" 1382-1391, 1993

13 D. Pao, "Enabling Incremental Updates to LC-Trie for Efficient Management of IP Forwarding Tables" 7 (7): 245-247, 2003

14 S. Sahni, "Efficient construction of mutibit tries for IP lookup" 11 (11): 650-662, 2003

15 V. Fuller, "Classless Inter-Domain Routing (CIDR): An Address Assignment and Aggregation Strategy"