[go: up one dir, main page]

Pao et al., 2014 - Google Patents

IP address lookup using bit-shuffled trie

Pao et al., 2014

Document ID
5138414765338210648
Author
Pao D
Lu Z
Poon Y
Publication year
Publication venue
Computer Communications

External Links

Snippet

An algorithmic RAM-based IP address lookup method called bit-shuffled trie is presented. By rearranging the bits of the prefixes, memory efficient index tables can be constructed to support IP address lookup. The address lookup engine can be implemented using pipelined …
Continue reading at www.sciencedirect.com (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
    • 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/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • G06F17/30625—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/30964—Querying
    • G06F17/30979—Query processing
    • G06F17/30985—Query processing by using string matching techniques
    • 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
    • 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/50—Computer-aided design
    • G06F17/5045—Circuit design
    • 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]

Similar Documents

Publication Publication Date Title
US7356033B2 (en) Method and apparatus for performing network routing with use of power efficient TCAM-based forwarding engine architectures
Waldvogel et al. Scalable high-speed prefix matching
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
KR100586461B1 (en) Method, Hardware Architecture and Recording Medium for Searching IP Address by Using Pipeline Binary Tree
CN105141525B (en) IPv6 method for searching route and device
Pao et al. IP address lookup using bit-shuffled trie
Huang et al. TCAM-based IP address lookup using longest suffix split
CN108875064A (en) OpenFlow multidimensional data matched and searched method based on FPGA
CN103546378A (en) Multi-match 2-level hierarchical search method for ranges on basis of TCAM (ternary content addressable memory)
Mishra et al. PETCAM—A power efficient TCAM architecture for forwarding tables
CN106416152A (en) Lookup device, lookup configuration method and lookup method
JP5878639B2 (en) Embedded memory and dedicated processor structure in integrated circuits
Wang et al. Memory-based architecture for multicharacter Aho–Corasick string matching
Pao et al. A multi-pipeline architecture for high-speed packet classification
Xin et al. FPGA-based updatable packet classification using TSS-combined bit-selecting tree
Le et al. Scalable high throughput and power efficient ip-lookup on fpga
Veeramani et al. Efficient IP lookup using hybrid trie-based partitioning of TCAM-based open flow switches
Lee et al. Utilizing 2-D leaf-pushing for packet classification
Kekely et al. Packet classification with limited memory resources
Erdem et al. Hierarchical hybrid search structure for high performance packet classification
CN110995876B (en) Method and device for storing and searching IP
US11120874B2 (en) Electronic memory device and a method of manipulating the electronic memory device
Vijay et al. A memory-efficient adaptive optimal binary search tree architecture for IPV6 lookup address
Erdem et al. Multi-pipelined and memory-efficient packet classification engines on FPGAs
Pao et al. Bit-shuffled trie: IP lookup with multi-level index tables