[go: up one dir, main page]

Hsieh et al., 2011 - Google Patents

A classified multisuffix trie for IP lookup and update

Hsieh et al., 2011

View PDF
Document ID
6813067327520301619
Author
Hsieh S
Yang Y
Publication year
Publication venue
IEEE Transactions on Computers

External Links

Snippet

In this paper, a new data structure, called the classified multisuffix trie (CMST), is proposed for designing dynamic router-tables. CMST achieves a better performance than existing data structures because each node can store more than one prefix and the longest matching …
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]
    • 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
    • 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
    • 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/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30952—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures using directory or table look-up
    • 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
    • H04L61/00—Network arrangements or network protocols for addressing or naming
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/12—Arrangements for maintenance or administration or management of packet switching networks network topology discovery or management
    • 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
    • H04L49/00—Packet switching elements
    • 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
    • H04L63/00—Network architectures or network communication protocols for network security

Similar Documents

Publication Publication Date Title
US6985483B2 (en) Methods and systems for fast packet forwarding
JP4452183B2 (en) How to create a programmable state machine data structure to parse the input word chain, how to use the programmable state machine data structure to find the resulting value corresponding to the input word chain, deep wire speed A method for performing packet processing, a device for deep packet processing, a chip embedding device, and a computer program including programming code instructions (method and device for deep packet processing)
US8089961B2 (en) Low power ternary content-addressable memory (TCAMs) for very large forwarding tables
CN101345707B (en) A method and device for realizing IPv6 message classification
US20090046724A1 (en) Method for compressing route data in a router
CN101594319B (en) Entry lookup method and entry lookup device
Warkhede et al. Multiway range trees: scalable IP lookup with fast updates
CN101507191A (en) Recursively partioned static ip router tables
US20110113129A1 (en) Method, device, computer program product and system for representing a partition of n w-bit intervals associated to d-bit data in a data communications network
CN100496019C (en) A Method for Rapid Search and Update of IPv6 Routing Table
CN101572647A (en) Method and device for searching data
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
Chang Fast binary and multiway prefix searches for packet forwarding
Sahni et al. O (log n) dynamic packet routing
Hsieh et al. A classified multisuffix trie for IP lookup and update
Sun et al. An on-chip IP address lookup algorithm
Veeramani et al. Efficient IP lookup using hybrid trie-based partitioning of TCAM-based open flow switches
Vijay et al. Implementation of memory-efficient linear pipelined IPv6 lookup and its significance in smart cities
Chang Efficient multidimensional packet classification with fast updates
Zhong An IPv6 address lookup algorithm based on recursive balanced multi-way range trees with efficient search and update
Hsieh et al. Multiprefix trie: A new data structure for designing dynamic router-tables
Lin et al. A multi-index hybrid trie for lookup and updates
Chang et al. A fast and memory efficient dynamic IP lookup algorithm based on B-Tree
Pao et al. Enabling incremental updates to LC-trie for efficient management of IP forwarding tables
Hsieh et al. A novel dynamic router-tables design for IP lookup and update