A New Pipelined Binary Search Architecture for IP Address Lookup 


Vol. 29,  No. 1, pp. 18-28, Jan.  2004


PDF
  Abstract

Efficient hardware implementation of address lookup is one of the most important design issues of internet routers. Address lookup significantly impacts router performance since routers need to process tens-to-hundred millions of packets per second in real time. In this paper, we propose a practical IP address lookup structure based on the binary tree of prefixes of different lengths. The proposed structure produces multiple balanced trees, and hence it solves the issues due to the unbalanced binary prefix tree of the existing scheme. The proposed structure is implemented using pipelined binary search combined with a small size TCAM. Performance evaluation results show that the proposed architecture requires a 2000-entry TCAM and total 245 kbyte SRAMs 10 store about 30,000 prefix samples from MAE-WEST router, and an address lookup is achieved by a single memory access. The proposed scheme scales very well with both of large databases and longer addresses as in IPv6.

  Statistics
Cumulative Counts from November, 2022
Multiple requests among the same browser session are counted as one view. If you mouse over a chart, the values of data points will be shown.


  Cite this article

[IEEE Style]

H. Lim, B. Lee, Y. Jung, "A New Pipelined Binary Search Architecture for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 29, no. 1, pp. 18-28, 2004. DOI: .

[ACM Style]

Hye-Sook Lim, Bo-Mi Lee, and Yeo-Jin Jung. 2004. A New Pipelined Binary Search Architecture for IP Address Lookup. The Journal of Korean Institute of Communications and Information Sciences, 29, 1, (2004), 18-28. DOI: .

[KICS Style]

Hye-Sook Lim, Bo-Mi Lee, Yeo-Jin Jung, "A New Pipelined Binary Search Architecture for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 29, no. 1, pp. 18-28, 1. 2004.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880