Weighted Binary Prefix Tree for IP Address Lookup 


Vol. 29,  No. 11, pp. 911-919, Nov.  2004


PDF
  Abstract

IP address lookup is one of the essential functions on internet routers, and it determines overall router performance. The most important evaluation factor for software-based IP address lookup is the number of the worst case memory accesses. Binary prefix tree (BPT) scheme gives small number of worst case memory accesses among previous software-based schemes. However the tree structure of BPT is normally unbalanced. In this paper, we propose weighted binary prefix tree (WBP) scheme which generates nearly balanced tree, through combining the concept of weight to the BPT generation process. The proposed WBPT gives very small number of worst case memory accesses compared to the previous software-based schemes. Moreover the WBPT requires comparably small size of memory which can be fit within L2 cache for about 30,000 prefixes, and it is rather simple for prefix addition and deletion. Hence the proposed WBPT can be used for software-based IP address lookup in practical routers.

  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]

C. Yim, H. Lim, B. Lee, "Weighted Binary Prefix Tree for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 29, no. 11, pp. 911-919, 2004. DOI: .

[ACM Style]

Changhoon Yim, Hyesook Lim, and Bomi Lee. 2004. Weighted Binary Prefix Tree for IP Address Lookup. The Journal of Korean Institute of Communications and Information Sciences, 29, 11, (2004), 911-919. DOI: .

[KICS Style]

Changhoon Yim, Hyesook Lim, Bomi Lee, "Weighted Binary Prefix Tree for IP Address Lookup," The Journal of Korean Institute of Communications and Information Sciences, vol. 29, no. 11, pp. 911-919, 11. 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