[go: up one dir, main page]

McLaughlin et al., 2007 - Google Patents

High-speed ip address lookups using hardware based tree structures

McLaughlin et al., 2007

Document ID
5488872825090979139
Author
McLaughlin K
Sezer S
Publication year
Publication venue
Second NASA/ESA Conference on Adaptive Hardware and Systems (AHS 2007)

External Links

Snippet

This paper examines the need for high speed IP address lookups and investigates a number of hardware architectures that are capable of delivering high-speed lookup performance. A survey is provided detailing architectures based on tree structures targeted for hardware …
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
    • 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
    • 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
    • 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/30587—Details of specialised database models
    • G06F17/30589—Hierarchical databases, e.g. IMS, LDAP data stores, Lotus Notes
    • 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
    • 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/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
    • 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
    • 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
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems
    • H04L12/56—Packet switching systems

Similar Documents

Publication Publication Date Title
Tzeng et al. On fast address-lookup algorithms
US6728732B1 (en) Data structure using a tree bitmap and method for rapid classification of data in a database
US7356033B2 (en) Method and apparatus for performing network routing with use of power efficient TCAM-based forwarding engine architectures
US7415463B2 (en) Programming tree data structures and handling collisions while performing lookup operations
US8780926B2 (en) Updating prefix-compressed tries for IP route lookup
US7418505B2 (en) IP address lookup using either a hashing table or multiple hash functions
US7433871B2 (en) Efficient ipv4/ipv6 best matching prefix method and apparatus
Basu et al. Fast incremental updates for pipelined forwarding engines
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
US6985483B2 (en) Methods and systems for fast packet forwarding
US7249149B1 (en) Tree bitmap data structures and their use in performing lookup operations
KR100586461B1 (en) Method, Hardware Architecture and Recording Medium for Searching IP Address by Using Pipeline Binary Tree
EP1551141A1 (en) Apparatus and method using hashing for efficiently implementing an IP lookup solution in hardware
Pao et al. Efficient hardware architecture for fast IP address lookup
US20090077076A1 (en) Database and database processing methods
Le et al. Memory-efficient and scalable virtual routers using FPGA
US7478109B1 (en) Identification of a longest matching prefix based on a search of intervals corresponding to the prefixes
CN100496019C (en) A Method for Rapid Search and Update of IPv6 Routing Table
Le et al. Scalable high throughput and power efficient ip-lookup on fpga
Lim et al. Binary searches on multiple small trees for IP address lookup
Chang et al. LayeredTrees: Most specific prefix-based pipelined design for on-chip IP address lookups
McLaughlin et al. High-speed ip address lookups using hardware based tree structures
Smiljanić et al. A comparative review of scalable lookup algorithms for IPv6
KR100364433B1 (en) IP address look-up method using a bit-vector table
Lim et al. A new pipelined binary search architecture for IP address lookup