Dharmapurikar et al., 2003 - Google Patents

Longest prefix matching using bloom filters

Dharmapurikar et al., 2003

View PDF
Document ID
15658468528119778339
Author
Dharmapurikar S
Krishnamurthy P
Taylor D
Publication year
Publication venue
Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications

External Links

Snippet

We introduce the first algorithm that we are aware of to employ Bloom filters for Longest Prefix Matching (LPM). The algorithm performs parallel queries on Bloom filters, an efficient data structure for membership queries, in order to determine address prefix membership in …
Continue reading at dl.acm.org (PDF) (other versions)

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup or address filtering
    • H04L45/7457—Address table lookup or address filtering using content-addressable memories [CAM]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L29/00—Arrangements, apparatus, circuits or systems, not covered by a single one of groups H04L1/00 - H04L27/00 contains provisionally no documents
    • H04L29/12—Arrangements, apparatus, circuits or systems, not covered by a single one of groups H04L1/00 - H04L27/00 contains provisionally no documents characterised by the data terminal contains provisionally no documents
    • H04L29/12009—Arrangements for addressing and naming in data networks
    • H04L29/12792—Details
    • H04L29/12811—Caching of addresses
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup or address filtering
    • H04L45/7453—Address table lookup or address filtering using hashing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/20—Support for services or operations
    • H04L49/201—Multicast or broadcast
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/40—Wormhole routing

Similar Documents

Publication Publication Date Title
Dharmapurikar et al. Longest prefix matching using bloom filters
Dharmapurikar et al. Longest prefix matching using bloom filters
US7602785B2 (en) Method and system for performing longest prefix matching for network address lookup using bloom filters
Song et al. Ipv6 lookups using distributed and load balanced bloom filters for 100gbps core router line cards
Eatherton et al. Tree bitmap: hardware/software IP lookups with incremental updates
Lakshminarayanan et al. Algorithms for advanced packet classification with ternary CAMs
US8625604B2 (en) Hash-based prefix-compressed trie for IP route lookup
Tzeng et al. On fast address-lookup algorithms
Jiang et al. Large-scale wire-speed packet classification on FPGAs
US7019674B2 (en) Content-based information retrieval architecture
Lim et al. On adding bloom filters to longest prefix matching algorithms
Pao et al. Efficient hardware architecture for fast IP address lookup
Warkhede et al. Multiway range trees: scalable IP lookup with fast updates
AU7463198A (en) Method and system for fast routing lookups
US7739445B1 (en) Circuit, apparatus, and method for extracting multiple matching entries from a content addressable memory (CAM) device
Saxena et al. Radient: Scalable, memory efficient name lookup algorithm for named data networking
Kaxiras et al. IPStash: a set-associative memory approach for efficient IP-lookup
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
CA2303118A1 (en) Method and system for fast routing lookups
Baer et al. Memory hierarchy design for a multiprocessor look-up engine
Krishnamurthy et al. Longest Prefix Matching using Bloom Filters
Taylor et al. On using content addressable memory for packet classification
Saxena et al. Scalable, high-speed on-chip-based NDN name forwarding using FPGA
Sahni et al. Dynamic tree bitmap for IP lookup and update
Hanna et al. Progressive hashing for packet processing using set associative memory