|
Published Articles >> Table of Contents >> Abstract
32nd IEEE Conference on Local Computer Networks (LCN 2007)
pp. 55-62
Storage-Efficient Architecture for Routing Tables via Prefix Transformation
Fong Pong, Broadcom Corp., USA
Nian-Feng Tzeng, University of Louisana at Lafayette, USA
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LCN.2007.154
Send link to a friend
| Abstract |
|
This article deals with a novel architecture for IP
routing table construction, on the basis of a single set-associative
hash table to support fast longest prefix matching (LPM). The
proposed architecture uses two key techniques to lower table storage
required drastically: (1) storing transformed prefix representations
and (2) accommodating multiple prefixes per table entry via prefix
aggregation. Given a set of chosen prefix lengths (called "treads"), all
prefixes are rounded down to nearest treads before hashed to the
table using their transformed representations so that prefix
aggregation opportunities abound in hash entries. Significant table
storage reduction makes it possible to fit a large routing table in
on-chip SRAM, solving both the memory and bandwidthintensive
problems faced by IP routing. Simulation results on real
routing tables show that the proposed architecture saves at least
two folds of storage when compared with most known hash tablebased
design or trie-based design. In addition, our design enjoys
fast lookups and incremental updates, with the worst-case lookup
time upper-bounded theoretically by the number of treads \zeta) but
found experimentally to be 4 memory accesses when\zeta equals 8.
|
 Additional Information
|
Citation:
Fong Pong, Nian-Feng Tzeng,
"Storage-Efficient Architecture for Routing Tables via Prefix Transformation,"
lcn,
pp. 55-62,
32nd IEEE Conference on Local Computer Networks (LCN 2007),
2007
|
|
