Abstract
Rapid growth of internet traffic requires more internet bandwidth and high-speed packet processing in internet routers. IP address lookup in routers is an essential operation that should be performed in real-time for routers where hundreds of million packets arrive per second. In this paper, we propose a new software-based architecture for efficient IP address lookup. In the proposed scheme, a large routing table is divided into multiple balanced trees, and sequential binary searches are performed on those trees, and hence the number of memory accesses depends on the number of routing entries not on the length of routing prefixes. Performance evaluation results show that the proposed architecture requires a single 301.7 KByte SRAM to store about 41000 routing entries, and an address lookup is achieved by 11 memory accesses in average.
| Original language | English |
|---|---|
| Pages (from-to) | 75-77 |
| Number of pages | 3 |
| Journal | IEEE Communications Letters |
| Volume | 9 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 2005 |
Bibliographical note
Funding Information:Manuscript received June 28, 2004. The associated editor coordinating the review of this letter and approving it for publication was Prof. Changcheng Huang. This research was supported by the Ministry of Information and Communication (MIC), Korea, under the Chung-Ang University Home Network Research Center (HNRC-ITRC) support program supervised by the Institute of Information Technology Assessment (IITA).
Keywords
- Binary search
- Disjoint prefix
- Enclosure prefix
- IP address lookup
- Multiple balanced trees