Parallel IP Address Lookup using Hashing with Multiple SRAMs

여러 개의 SRAM과 해슁을 이용한 병렬 IP 어드레스 검색에 대한 연구

  • 서지현 (이화여자대학교 과학기술대학원 정보통신학과 설계자동화 및 집적회로연구실) ;
  • 임혜숙 (이화여자대학교 과학기술대학원 정보통신학과컴퓨터 네트워킹 하드웨어 연구실) ;
  • 정여진 (이화여자대학교 과학기술대학원 정보통신학과컴퓨터 네트워킹 하드웨어 연구실) ;
  • 이승준 (이화여자대학교 과학기술대학원 정보통신학과 설계자동화 및 집적회로연구실)
  • Published : 2003.02.01

Abstract

One of the important design issues for IP routers responsible for packet forwarding in computer networks is the route-lookup mechanism. For each incoming packet, IP routing requires that a router performs a longest-prefix-match address lookup in order to determine the next hop that the incoming packet should be forwarded to. In this paper, we present a new scheme which applies the hashing function for IP address lookup. In the proposed scheme, the forwarding table is composed of multiple SRAMs, and each SRAM represents an address lookup table in each prefix. Hashing function is applied in order to find out the matching entries from the address lookup tables in parallel, and the entry with the longest prefix match among them is selected. Simulation using the MAE-WEST router example shows that a large routing table with 37000 entries can be compacted to a forwarding table of 300 Kbytes in the proposed scheme. It is also shown that the proposed scheme achieves one route lookup every 1.93 memory accesses in average.

컴퓨터간의 빠른 데이터 전송을 위해서는 링크 속도와 더불어 라우터에서의 패킷 전달율(forwarding rate) 이 중요하며, 이 중 어드레스 검색(address lookup) 은 패킷 전달 과정 중에서 매우 중요한 부분으로, 주요 시간 지연을 발생시키는 요인이라 할 것이다. 본 논문에서는 고속 라우터에 적합한 효율적인 어드레스 검색 하드웨어 구조를 제안하고자 한다. 본 논문에서 제안된 구조는 인터넷 어드레스의 프리픽스 길이별로 각각 다른 SRAM을 사용하여 여러 개의 어드레스 검색 테이블을 만들고, 각 테이블에 해슁(hashing)을 적용하여 동시에 어드레스 검색을 수행한 후, 각 테이블에서 일치되어 나온 엔트리 중 가장 길게 프리픽스가 일치하는 엔트리를 고르는 방식이다. 제안된 방식의 성능을 평가하기 위하여 MAE-WEST 라우터 예로 시뮬레이션을 수행하였다. 37000여 개의 라우팅 엔트리를 갖는 테이블 저장을 위해 약 300Kbyte의 메모리를 사용하였을 때, 패킷 당 1.93번의 메모리 접근 횟수를 갖는다.

Keywords

References

  1. M.A. Ruiz-Sanchez, E.W. Biersack, W. Dabbous, 'Survey and Taxonomy of IP Address Lookup Algoiithms', IEEE Network, Vol. 15 No. 2, pp. 8-23, 2001 https://doi.org/10.1109/65.912716
  2. M. Degermark, A. Brodnik, S. Carlsson, S. Pink, 'Small Forwarding Tables for Fast Routing Lookups', Proc. ACM SIGCOMM, pp. 3-14. 1997
  3. P. Gupta, S. Lin, N. McKeown, 'Routing Lookups in Hardware at Memory Access Speeds', Proc. IEEE INFOCOM, pp. 1240-1247, 1998
  4. M. Waldvogel, G. Varghese, J. Turner, B. Plattner, "Scalable High Speed IP Routing Lookups", Proc. ACM SIGCOMM, pp. 25-36, 1997
  5. B. Lampson, V. Srinivasan, G. Varghese, 'IP Lookups Using Multiwa yand Multicolumn Search', IEEE/ACM Transactions on Networking, vol. 7 No.3, pp. 324-334, 1999 https://doi.org/10.1109/90.779199
  6. Meht Networks, Inc. http://www.merit.edu
  7. R. Jain, 'A Comparison of Hashing Schemes for Address Lookup in Computer Networks : Technical report', Digital Equipment Corporation, 1989
  8. N. Huang, S. Ming, 'A Noble IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Sw itching Routers', IEEE Journal on selected areas in communications, vol. 17, pp. 1093-1104, 1999 https://doi.org/10.1109/49.772440