[go: up one dir, main page]

Buchsbaum et al., 2003 - Google Patents

Fast prefix matching of bounded strings

Buchsbaum et al., 2003

View PDF
Document ID
9864239418805783212
Author
Buchsbaum A
Fowler G
Kirishnamurthy B
Vo K
Wang J
Publication year
Publication venue
Journal of Experimental Algorithmics (JEA)

External Links

Snippet

Longest Prefix Matching (LPM) is the problem of finding which string from a given set is the longest prefix of another, given string. LPM is a core problem in many applications, including IP routing, network data clustering, and telephone network management. These applications …
Continue reading at www.researchgate.net (PDF) (other versions)

Classifications

    • 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/12047—Directories; name-to-address mapping
    • H04L29/12056—Directories; name-to-address mapping involving standard directories and standard directory access protocols
    • H04L29/12066—Directories; name-to-address mapping involving standard directories and standard directory access protocols using Domain Name System [DNS]
    • 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]
    • 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/30861—Retrieval from the Internet, e.g. browsers
    • 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/02—Communication control; Communication processing contains provisionally no documents
    • H04L29/06—Communication control; Communication processing contains provisionally no documents characterised by a protocol
    • 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
    • H04L63/14—Network architectures or network communication protocols for network security for detecting or protecting against malicious traffic
    • 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
    • H04L61/00—Network arrangements or network protocols for addressing or naming
    • 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
    • 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/99941—Database schema or data structure
    • Y10S707/99943—Generating database or data structure, e.g. via user interface
    • 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/99941—Database schema or data structure
    • Y10S707/99942—Manipulating data structure, e.g. compression, compaction, compilation

Similar Documents

Publication Publication Date Title
Lakshminarayanan et al. Algorithms for advanced packet classification with ternary CAMs
Tzeng et al. On fast address-lookup algorithms
Zane et al. CoolCAMs: Power-efficient TCAMs for forwarding engines
Singh et al. Packet classification using multidimensional cutting
Gupta Algorithms for routing lookups and packet classification
Ruiz-Sánchez et al. Survey and taxonomy of IP address lookup algorithms
Waldvogel et al. Scalable high speed IP routing lookups
Dharmapurikar et al. Longest prefix matching using bloom filters
Waldvogel et al. Scalable high-speed prefix matching
US6985483B2 (en) Methods and systems for fast packet forwarding
Cheung et al. Optimal routing table design for IP address lookups under memory constraints
Pao et al. Efficient hardware architecture for fast IP address lookup
Warkhede et al. Multiway range trees: scalable IP lookup with fast updates
Lim et al. Priority tries for IP address lookup
WO2004006061A2 (en) Dynamic ip router tables using highest-priority matching
Tzeng Longest prefix search using compressed trees
Buchsbaum et al. Fast prefix matching of bounded strings
Pao et al. Efficient packet classification using TCAMs
US7191168B1 (en) Fast prefix matching of bounded strings
Hsieh et al. A classified multisuffix trie for IP lookup and update
Lu et al. Enhanced interval trees for dynamic IP router-tables
Kőrösi et al. On the memory requirement of hop-by-hop routing: Tight bounds and optimal address spaces
Chang Efficient multidimensional packet classification with fast updates
Chang et al. Dynamic segment trees for ranges and prefixes
Lim et al. High-speed packet classification using binary search on length