[go: up one dir, main page]

Lim et al., 2012 - Google Patents

On adding bloom filters to longest prefix matching algorithms

Lim et al., 2012

View PDF
Document ID
16741781952759676076
Author
Lim H
Lim K
Lee N
Park K
Publication year
Publication venue
IEEE Transactions on Computers

External Links

Snippet

High-speed IP address lookup is essential to achieve wire-speed packet forwarding in Internet routers. Ternary content addressable memory (TCAM) technology has been adopted to solve the IP address lookup problem because of its ability to perform fast parallel …
Continue reading at cial.csie.ncku.edu.tw (PDF) (other versions)

Classifications

    • 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
    • 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
    • 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/30964—Querying
    • G06F17/30979—Query processing
    • 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/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • 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/54—Organization of routing tables
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication
    • H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3236—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using cryptographic hash functions
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security

Similar Documents

Publication Publication Date Title
Lim et al. On adding bloom filters to longest prefix matching algorithms
Mun et al. New approach for efficient ip address lookup using a bloom filter in trie-based algorithms
Dharmapurikar et al. Longest prefix matching using bloom filters
Quan et al. TB2F: Tree-bitmap and bloom-filter for a scalable and efficient name lookup in content-centric networking
Dharmapurikar et al. Longest prefix matching using bloom filters
Song et al. Ipv6 lookups using distributed and load balanced bloom filters for 100gbps core router line cards
US7715385B2 (en) Default route coding
US6985483B2 (en) Methods and systems for fast packet forwarding
US7868792B2 (en) Generating a boundary hash-based hierarchical data structure associated with a plurality of known arbitrary-length bit strings and using the generated hierarchical data structure for detecting whether an arbitrary-length bit string input matches one of a plurality of known arbitrary-length bit springs
Warkhede et al. Multiway range trees: scalable IP lookup with fast updates
Lim et al. Priority tries for IP address lookup
Pao et al. Efficient hardware architecture for fast IP address lookup
Lee et al. Name prefix matching using bloom filter pre-searching for content centric network
Pak et al. High performance and high scalable packet classification algorithm for network security systems
Lim et al. Reducing false positives of a Bloom filter using cross-checking Bloom filters
Priya et al. Hierarchical packet classification using a Bloom filter and rule-priority tries
Pao et al. A multi-pipeline architecture for high-speed packet classification
Sahni et al. O (log n) dynamic packet routing
Huang et al. Fast and deterministic hash table lookup using discriminative bloom filters
Lin et al. A multi-index hybrid trie for lookup and updates
Ahmadi et al. Modified collision packet classification using counting bloom filter in tuple space.
CN115714752A (en) Packet classification method and device, forwarding chip and electronic equipment
Li et al. An IPv6 routing lookup algorithm based on hash table and HOT
Dou et al. Order-hiding range query over encrypted data without search pattern leakage
Sourdis et al. Range tries for scalable address lookup