[go: up one dir, main page]

Rojas-Cessa et al., 2007 - Google Patents

Implementation of a parallel-search trie-based scheme for fast IP lookup

Rojas-Cessa et al., 2007

View PDF
Document ID
9742255107046240604
Author
Rojas-Cessa R
Ramesh L
Dong Z
D’Alessandro B
Ansari N
Publication year
Publication venue
Proceedings of the IASTED International Conference Communication Systems, Networks, and Application, Beijing, China

External Links

Snippet

ABSTRACT The Internet Protocol (IP) address lookup is required to be resolved fast to keep up with data rate increases. To cope with the increasing number of entries, solutions for IP lookup based on random access memory (RAM), which store prefixes in a trie-based …
Continue reading at www.briandalessandro.com (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
    • 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/02—Topology update or discovery
    • 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
    • H04L29/12792—Details
    • H04L29/12811—Caching of addresses
    • 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
    • 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
    • H04L29/12047—Directories; name-to-address mapping
    • H04L29/12056—Directories; name-to-address mapping involving standard directories and standard directory access protocols
    • H04L29/12066—Directories; name-to-address mapping involving standard directories and standard directory access protocols using Domain Name System [DNS]
    • 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/12—Shortest path evaluation

Similar Documents

Publication Publication Date Title
Gupta et al. Routing lookups in hardware at memory access speeds
US7418505B2 (en) IP address lookup using either a hashing table or multiple hash functions
US7610271B2 (en) Method and apparatus for performing a binary search on an expanded tree
US6880064B1 (en) Method and apparatus for physical width expansion of a longest prefix match lookup table
US6985483B2 (en) Methods and systems for fast packet forwarding
US8385343B2 (en) Method and apparatus for searching IP address
US7443841B2 (en) Longest prefix matching (LPM) using a fixed comparison hash table
US7106732B2 (en) Default route coding
US7630367B2 (en) Approach for fast IP address lookups
US20040044868A1 (en) Method and apparatus for high-speed longest prefix match of keys in a memory
Rojas-Cessa et al. Parallel search trie-based scheme for fast IP lookup
Rojas-Cessa et al. Implementation of a parallel-search trie-based scheme for fast IP lookup
EP3269101B1 (en) Generating a hash table in accordance with a prefix length
EP3319279B1 (en) Ip routing lookup
Kobayashi et al. A processor based high-speed longest prefix match search engine
EP1158431A2 (en) Method and apparatus for performing a binary search on an expanded tree
CN107204926B (en) Rapid route searching method for preprocessing cache
Rojas-Cessa et al. Fast Table-Update Scheme and Implementation of a Trie-based Scheme for Fast IP Lookup
Mehrotra et al. Binary search schemes for fast IP lookups
KR20050043035A (en) Method and hardware architecture for searching ip address by using multiple hashing function
Deng et al. High Speed IP Routing Lookup Algorithm Based on RAM and TCAM
JP2020201656A (en) Search circuit
Al-Khaffaf et al. Efficient partition based IPv6 lookup algorithm for packet forwarding
Erdem et al. MIPS extension for a TCAM based parallel architecture for fast IP lookup
Reddy Fast updating algorithm for TCAMs using prefix distribution prediction