[go: up one dir, main page]

Erdem et al., 2012 - Google Patents

Hierarchical hybrid search structure for high performance packet classification

Erdem et al., 2012

View PDF
Document ID
3361495688471092453
Author
Erdem O
Le H
Prasanna V
Publication year
Publication venue
2012 Proceedings IEEE INFOCOM

External Links

Snippet

Hierarchical search structures for packet classification offer good memory performance and support quick rule updates when implemented on multi-core network processors. However, pipelined hardware implementation of these algorithms has two disadvantages:(1) …
Continue reading at cial.csie.ncku.edu.tw (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
    • 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
    • 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/742—Route cache and its operation
    • 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/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/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
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/30—Peripheral units, e.g. input or output ports
    • H04L49/3009—Header conversion, routing tables or routing tags
    • 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
    • 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
    • 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/04—Interdomain routing, e.g. hierarchical routing
    • 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
    • H04L49/00—Packet switching elements
    • H04L49/20—Support for services or operations
    • H04L49/201—Multicast or broadcast
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/35—Application specific switches
    • H04L49/354—Support for virtual LAN, VLAN tagging or multiple registration, e.g. according to IEEE 802.1q
    • 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
    • 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

Similar Documents

Publication Publication Date Title
US8780926B2 (en) Updating prefix-compressed tries for IP route lookup
Jiang et al. Large-scale wire-speed packet classification on FPGAs
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
KR100512949B1 (en) Apparatus and method for packet classification using Field Level Trie
Le et al. Memory-efficient and scalable virtual routers using FPGA
Pao et al. A multi-pipeline architecture for high-speed packet classification
Li et al. TabTree: A TSS-assisted bit-selecting tree scheme for packet classification with balanced rule mapping
Chang et al. Range-enhanced packet classification design on FPGA
Erdem et al. Hierarchical hybrid search structure for high performance packet classification
Le et al. Scalable high throughput and power efficient ip-lookup on fpga
Jiang et al. A FPGA-based parallel architecture for scalable high-speed packet classification
Chang Fast binary and multiway prefix searches for packet forwarding
Meiners et al. Hardware based packet classification for high speed internet routers
Lim et al. Two-dimensional packet classification algorithm using a quad-tree
Veeramani et al. Efficient IP lookup using hybrid trie-based partitioning of TCAM-based open flow switches
Le et al. Memory-efficient ipv4/v6 lookup on fpgas using distance-bounded path compression
Waldvogel Multi-dimensional prefix matching using line search
Erdem et al. Multi-pipelined and memory-efficient packet classification engines on FPGAs
CN100426791C (en) Engine apparatus for route forwarding table address searching
Erdem et al. Clustered hierarchical search structure for large-scale packet classification on FPGA
Chang et al. LayeredTrees: Most specific prefix-based pipelined design for on-chip IP address lookups
Erdem Pipelined hierarchical architecture for high performance packet classification
Erdem et al. Value-coded trie structure for high-performance IPv6 lookup
Jiang et al. Scalable packet classification: Cutting or merging?
Huang et al. Memory-efficient IP lookup using trie merging for scalable virtual routers