@inproceedings{5f23a957cc2f450bb6c17731ebb1ed50,
title = "A new pipelined binary search architecture for IP address lookup",
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 of 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 250-kbyte SRAM to store about 30,000 prefix samples from MAE-WEST router, and an address lookup is achieved by one memory access. The proposed scheme scales very well with both of large databases and longer addresses as in IPv6.",
keywords = "Binary Prefix Tree, EnBiT, Longest Prefix Match, Pipelined Binary Search",
author = "Hyesook Lim and Bomi Lee",
year = "2004",
language = "English",
isbn = "0780383753",
series = "IEEE Workshop on High Performance Switching and Routing, HPSR",
pages = "86--90",
booktitle = "2004 Workshop on High Performance Switching and Routing, HPSR 2004",
note = "null ; Conference date: 19-04-2004 Through 20-04-2004",
}