uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
High-Performance Longest Prefix Matching supporting High-Speed Incremental Updates and Guaranteed Compression
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology. Datorteknik. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Communication Research)
2005 (English)In: Proceedings of IEEE Infocom 2005, 2005Conference paper (Refereed)
Abstract [en]

Longest prefix matching is frequently used for IP forwarding in the Internet. Data structures used must be not only efficient, but 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 is 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^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 ~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^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
Keyword [en]
Routing, Classification
Research subject
Computer Science with specialization in Computer Communication
URN: urn:nbn:se:uu:diva-70780OAI: oai:DiVA.org:uu-70780DiVA: diva2:98691
Available from: 2005-05-13 Created: 2005-05-13 Last updated: 2011-01-12

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Larzon, Lars-Åke
By organisation
Department of Information TechnologyComputer Systems

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

Total: 211 hits
ReferencesLink to record
Permanent link

Direct link