Journal of KIISE:Information Networking (한국정보과학회논문지:정보통신)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

The Bit-Map Trip Structure for Giga-Bit Forwarding Lookup in High-Speed Routers

고속 라우터의 기가비트 포워딩 검색을 위한 비트-맵 트라이 구조

  • 오승현 (동국대학교 컴퓨터공학과) ;
  • 안종석 (동국대학교 컴퓨터공학과)
  • Published : 2001.06.01
Download PDF
⟨ Previous Next ⟩

Abstract

Recently much research for developing forwarding table that support fast router without employing both special hardware and new protocols. This article introduces a new forwarding data structure based on the software to enable forwarding lookup to be penormed at giga-bit speed. The forwarding table is known as a bottleneck of the routers penormance due to its high complexity proportional to the forwarding table size. The recent research that based on the software uses a Patricia trie and its variants. and also uses a hash function with prefix length key and others. The proposed forwarding table structure construct a forwarding table by the bit stream array in which it constructs trie from routing table prefix entries and it represents each pointer pointing the child node and the associated forwarding table entry with one bit The trie structure and routing prefix pointer need a large memory when representing those by linked-list or array. but in the proposed data structure, the needed memory size is small enough since it represents information with one bit. Additionally, by use a lookup method that start searching at desired middle level we can shorten the search path. The introduced data structure. called bit-map trie shows that we can implement a fast forwarding engine on the conventional Pentium processor by reducing the backbone routing table fits into Level 2 cache of Pentium II processor and shortens the searching path. Our experiments to evaluate the performance of proposed method show that this bit-map trie accomplishes 5.7 million lookups per second.

최근들어 특별한 하드웨어나 새 프로토콜의 도움없이 고속 라우터의 포워딩 검색을 지원하는 포워딩 테이블에 대한 연구가 다양하게 진행되고 있다. 본 논문에서는 소프트웨어를 기반으로 일반적인 펜티엄 프로세서에서 기가비트급 포워딩 검색을 지원할 수 있는 새포워딩 테이블 자료구조를 제시한다. 포워딩 검색은 테이블의 크기에 비례해서 복잡도가 증가하는 라우터 성능의 병목지점으로 알려져 있다. 기존의 소프트웨어를 기반으로 하는 포워딩 검색 연구들은 포워딩 테이블 자료구조로 패트리샤 트라이와 그 변형을 이용하거나 프리픽스 길이를 키로 해서 함수를 구성하는 방법등을 사용하여 왔다. 본 논문에서 제안된 포워딩 테이블 자료구조는 라우팅 테이블의 프리픽스를 완전이진 트라이로 구성한후 트라이의 구조와 각 노드별로 링크 되어있는 라우팅 테이블 포인터 정보를 비트열로 표현하여 포워딩테이블을 구성한다. 트라이의 구조와 라우팅 프리픽스 포인터 정보는 배열이나 링크드-리스트로 표현하면 대량의 저장공간을 필요로하지만 제안된 자료구조에서는 각 정보가 하나의 비트로 표현되므로 작은 저장공간으로 충분하며 또한 트라이를 중간 레벨에서부터 검색할 수 있는 방법을 라우팅 테이블을 펜티엄 프로세서의 L2 캐쉬에 저장할 수 있는 작은 크기로 압축하고 검색경로를 단축함으로써 일반적인 펜티엄 프로세서를 이용하여 고속의 포워딩 엔진을 구현할 수 있음을 보여준다. 제안된 방법의 성능을 평가하기 위해서 실제 라우팅 테이블을 대상으로 실험한 결과 초당 5.7백만 번의 라우팅검색성능을 기록하였다.

Keywords

References

  1. Peter Newman, Greg Minshall. and Larry Huston, 'IP Switching and Gigabit Routers,' IEEE Communications Magazine, January 1997 https://doi.org/10.1109/35.568212
  2. Inernet2, http://www,internet2.edu
  3. www.intel.com/design/PentiumII/
  4. Tong -Bi Pei and Charles Zukowski, 'Putting Routing Tables in Sillicon,' IEEE network Magazine, January 1992 https://doi.org/10.1109/65.120723
  5. A.J. McAuley and P. Francis, 'Fast routing table lookup using CAMs,' In Proceedings cf IEEE Infocom'93, v3. 1382-1391, San Francisco. 1993 https://doi.org/10.1109/INFCOM.1993.253403
  6. David C. Feldmeier. 'Improving gateway performance with a routing-table cache,' In proceedings of IEEE Infocom'98, New Orleans. Louisiana, March 1998 https://doi.org/10.1109/INFCOM.1988.12930
  7. Anthony J, Bloomfeld NJ McAuley, Paul F. Lake Hopatcong NJ Tsuchiya, and Daniel V. Rockaway Township Morris Country NJ Wilson, 'Fast Multilevel hierarchial routing table using content-addressable memory,' U.S. Patent serial number 034444
  8. P. Gupta, et al., 'Routing Lookups in Hardware at Memory Speeds.' In Proceedings of IEEE Infocom'98, San Francisco, April 1998 https://doi.org/10.1109/INFCOM.1998.662938
  9. A. Moestedt. et al., 'IPAddress Lookup in Hardware for High-Speed Routing,' Hot Interconnects, August 1998
  10. A. Bremler-Barr, Y. Afek, and S. Har-Peled, 'Routing with Clue.' In Proceedings of ACM SIGCOMM 99, Cambridge, September 1999
  11. Donald R Morrison, 'PATRICIA Practical Algorithm to Retreive Information Coded In Alfanumeric,' journal of the ACM, 15(4):514-534, October 1968 https://doi.org/10.1145/321479.321481
  12. Mikael Degermark, Andrej Brodnik, Svante Carlsson, and Stephen pink, 'Small Forwarding Tables for Fast Routing Lookups.' In Proceedings of ACM SIGCOMM'97, October 1997 https://doi.org/10.1145/263105.263133
  13. B. Lampson, V. Srinivasan and G. Varghese, 'IP Lookups using Multiway and Multicolumn Search.' In Proceeding of INFOCOM'98, March 1998 https://doi.org/10.1109/INFCOM.1998.662939
  14. S. Venkatachary and G. Varghese, 'Faster IP Lookups using Controlled Prefix Expansion,' In Proceedings of ACM Sigmetrics'98, June 1998 https://doi.org/10.1145/277851.277863
  15. Marcel Waldvogel, George Varghese, Jon Turner, and Bernhard Plattner, 'Scalable High Speed IP Routing Lookups,' In Proceedings of ACM SIGCOMM'97, October 1997 https://doi.org/10.1145/263105.263136
  16. Keith Sklower, 'A Tree-Based Routing Table for Berkeley Unix,' Technical report, University of California, Berkeley
  17. S. Nilsson and G. karlsson, 'Fast Address Look-Up for Internet Routers,' In Proceedings of IEEE Broadband Communications'98, April 1998
  18. T. Kijkanjanarat and H.J.Chao, 'Fast IP Lookups using a Two-Trio Data Structure,' In Proceedings of Globecom'99, 1999 https://doi.org/10.1109/GLOCOM.1999.830044
  19. E. Rosen, et al., 'Multi protocol Label Switching Architecture,' ftp://ds.internic.net/internet-drafts/draft-ierf-mpls-arch-07.txt, July 2000
  20. Yakov Rekhter et al, 'Tag switching architecture overview,' ftp://ds.internic/net/internet-drafts/draft-rfcedinfo-rekhter-00.txt, 1996
  21. Peter Newman, Tom Lyon, and Greg Minshall, 'Flow labeled IF: a connectionless approach to ATM,' In Proceedings of IEEE Infocom'96, San Francisco, California, March 1996 https://doi.org/10.1109/INFCOM.1996.493071
  22. Pinar A. Yilmaz, Andrey Belenkiy, Necdet Uzun, and Nitin Gogate, A Trie-based Algorithm for IF Lookup Problem , In Proceedings of Globecom'00, 2000 https://doi.org/10.1109/GLOCOM.2000.892085
  23. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, 'Data Structure and Algorithms,' Addison- Wesley, 1983
  24. K. Mehlhorn, S. Naher, and H.Alt, 'A lower bound on the complexity of the union-split-find probelm,' SIAM Journal on Computing, December 1988 https://doi.org/10.1137/0217070
  25. Michigan University and merit Network, Internet Performance Management and Analysis (IPMA) project, http://nic.merit.edu/~ipma
  26. Stanford University Workshop on Fast Routing and Switching, December 1996, http://tinytera.stanford.edu/Workshop_Dec96/
  27. Y. Rekhter and T. Li. 'A Border Gateway Protocol 4 (BGP-4),' IETF RFC 1771, March 1995
  28. S. Deering, and R. Hinden, 'Internet Protocol, Version 6 (IPv6) Specification,' IETF RFC 2460, December 1998