[go: up one dir, main page]

Nikolenko et al., 2016 - Google Patents

How to represent IPv6 forwarding tables on IPv4 or MPLS dataplanes

Nikolenko et al., 2016

View PDF
Document ID
4144052036676023588
Author
Nikolenko S
Kogan K
Rétvári G
Bérczi-Kovács E
Shalimov A
Publication year
Publication venue
2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)

External Links

Snippet

The Internet routing ecosystem is facing substantial scalability challenges on the data plane. Various “clean slate” architectures for representing forwarding tables (FIBs), such as IPv6, introduce additional constraints on efficient implementations from both lookup time and …
Continue reading at dspace.networks.imdea.org (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/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/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/30964—Querying
    • G06F17/30979—Query processing
    • G06F17/30985—Query processing by using string matching techniques
    • 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/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30386—Retrieval requests
    • 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
    • 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
    • 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
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/02—Network architectures or network communication protocols for network security for separating internal from external traffic, e.g. firewalls
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme

Similar Documents

Publication Publication Date Title
US9269411B2 (en) Organizing data in a hybrid memory for search operations
US6775737B1 (en) Method and apparatus for allocating and using range identifiers as input values to content-addressable memories
US9627063B2 (en) Ternary content addressable memory utilizing common masks and hash lookups
US9569561B2 (en) Label masked addressable memory
US7668160B2 (en) Methods for performing packet classification
US8089961B2 (en) Low power ternary content-addressable memory (TCAMs) for very large forwarding tables
CN111937360B (en) Longest prefix matching
US20050010612A1 (en) Storing and searching a hierarchy of items of particular use with IP security policies and security associations
Li et al. HybridCuts: A scheme combining decomposition and cutting for packet classification
US8375165B2 (en) Bit weaving technique for compressing packet classifiers
Qu et al. Scalable many-field packet classification on multi-core processors
Meiners et al. Topological transformation approaches to TCAM-based packet classification
Li et al. TabTree: A TSS-assisted bit-selecting tree scheme for packet classification with balanced rule mapping
Nikolenko et al. How to represent IPv6 forwarding tables on IPv4 or MPLS dataplanes
Qu et al. A decomposition-based approach for scalable many-field packet classification on multi-core processors
US6970971B1 (en) Method and apparatus for mapping prefixes and values of a hierarchical space to other representations
Li et al. A power-saving pre-classifier for TCAM-based IP lookup
Meiners et al. Hardware based packet classification for high speed internet routers
Lim et al. A new hierarchical packet classification algorithm
Kogan et al. FIB efficiency in distributed platforms
Veeramani et al. Efficient IP lookup using hybrid trie-based partitioning of TCAM-based open flow switches
Lo et al. Flow entry conflict detection scheme for software-defined network
Chang Efficient multidimensional packet classification with fast updates
Shen et al. Optimizing multi-dimensional packet classification for multi-core systems
Zhang et al. Pextcuts: A high-performance packet classification algorithm with pext cpu instruction