[go: up one dir, main page]

Lim et al., 2010 - Google Patents

Priority tries for IP address lookup

Lim et al., 2010

Document ID
1662890925432608856
Author
Lim H
Yim C
Swartzlander E
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. The longest prefix matching for IP address lookup is more complex than exact matching because it involves dual dimensions: length and value. This paper presents …
Continue reading at ieeexplore.ieee.org (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]
    • 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
    • G06F17/30961—Trees
    • 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
    • G06F17/30958—Graphs; Linked lists
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems
    • 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/48—Routing tree calculation
    • 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
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/02—Details
    • 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
    • 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
    • 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/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. local area networks [LAN], wide area networks [WAN]
    • 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
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements

Similar Documents

Publication Publication Date Title
Lim et al. Priority tries for IP address lookup
US7089240B2 (en) Longest prefix match lookup using hash function
US7509300B2 (en) Dynamic IP router tables using highest-priority matching
Baboescu et al. Scalable packet classification
US6985483B2 (en) Methods and systems for fast packet forwarding
US6594655B2 (en) Wildcards in radix- search tree structures
Lim et al. On adding bloom filters to longest prefix matching algorithms
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
Warkhede et al. Multiway range trees: scalable IP lookup with fast updates
Pao et al. Efficient hardware architecture for fast IP address lookup
CN107967219A (en) A kind of extensive character string high-speed searching method based on TCAM
US20050083937A1 (en) IP address lookup method using pipeline binary tree, hardware architecture, and recording medium
CN100385880C (en) Grouping classifiers and methods using field-level tries
Priya et al. Hierarchical packet classification using a Bloom filter and rule-priority tries
Lim et al. Reducing false positives of a Bloom filter using cross-checking Bloom filters
CN100496019C (en) A Method for Rapid Search and Update of IPv6 Routing Table
CN100413285C (en) Design and Implementation of High Speed Multidimensional Packet Classification Algorithm Based on Network Processor
Lim et al. A new hierarchical packet classification algorithm
Lim et al. Two-dimensional packet classification algorithm using a quad-tree
Pao et al. A multi-pipeline architecture for high-speed packet classification
Yim et al. Efficient binary search for IP address lookup
Sun et al. An on-chip IP address lookup algorithm
Chang Efficient multidimensional packet classification with fast updates
Lim et al. Binary searches on multiple small trees for IP address lookup
Lim et al. NXG06-1: An efficient IP address lookup algorithm using a priority trie