Change search
ReferencesLink to record
Permanent link

Direct link
High-performance longest prefix matching supporting high-speed incremental updates and guaranteed compression
2005 (English)In: Proceedings - 4th Annual Joint Conference of the IEEE Computer and Communications Societies: INFOCOM 2005 / [ed] Kia Makki, IEEE Communications Society, 2005, Vol. 3, 1641-1652 p.Conference paper (Refereed)
Abstract [en]

Longest prefix matching is frequently used for IP forwarding in the Internet. Data structures used must be not only efficient, hut also robust against pathological entries caused by an adversary or misconfiguration. In this paper, we attack the longest prefix matching problem by presenting a new algorithm supporting high lookup performance, fast incremental updates and guaranteed compression ratio. High lookup performance is achieved by using only four memory accesses. Guaranteed compression ratio is achieved by combining direct indexing with an implicit tree structure and carefully choosing which construct to use when updating the forwarding table. Fast incremental updates are achieved by a new memory management technique featuring fast variable size allocation and deallocation while maintaining zero fragmentation. An IPv4 forwarding table data structure can be implemented in software or hardware within 2.7 Mb of memory to represent 2/sup 18/ routing entries. Incremental updates require only 752 memory accesses in worst case for the current guaranteed compression ratio. For a hardware implementation, we can use 300 MHz SRAM organized in four memory banks and four pipeline stages to achieve a guaranteed performance of 300 million lookups per second, corresponding to /spl sim/ 100 Gbit/s wire speed forwarding, and 400,000 incremental updates per second. In measurements performed on a 3.0 GHz Pentium 4 machine using a routing table with more than 2/sup 17/ entries, we can forward over 27 million IPv4 packets per second, which is equivalent to wire speeds exceeding 10 Gbit/s. On the same machine and with the same routing table, we can perform over 230,000 incremental updates/second.

Place, publisher, year, edition, pages
IEEE Communications Society, 2005. Vol. 3, 1641-1652 p.
, IEEE Infocom. Proceedings, ISSN 0743-166X
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-27068DOI: 10.1109/INFCOM.2005.1498446Local ID: 0605d9e0-95a9-11db-8975-000ea68e967bISBN: 0-7803-8968-9OAI: diva2:1000249
Annual Joint Conference of the IEEE Computer and Communications Societies : 13/03/2005 - 17/03/2005
Validerad; 2005; 20061227 (ysko)Available from: 2016-09-30 Created: 2016-09-30Bibliographically approved

Open Access in DiVA

fulltext(242 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 242 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Sundström, MikaelLarzon, Lars-Åke

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

ReferencesLink to record
Permanent link

Direct link