[go: up one dir, main page]

Rooney et al., 2004 - Google Patents

Associative ternary cache for IP routing

Rooney et al., 2004

View PDF
Document ID
7011296965676320506
Author
Rooney J
Delgado-Frias J
Summerville D
Publication year
Publication venue
IEE Proceedings-Computers and Digital Techniques

External Links

Snippet

A study of a prefix routing cache for Internet IP routing is presented. An output port assignment requires one cache memory access when the assignment is found in cache. The cache array is divided into sets that are of variable size; all entries within a set have the …
Continue reading at eecs.wsu.edu (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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/12—Replacement control
    • G06F12/121—Replacement control using replacement algorithms
    • 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
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • 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
    • 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
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/10—Address translation
    • 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/12—Shortest path evaluation
    • 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/38—Flow based routing

Similar Documents

Publication Publication Date Title
Dharmapurikar et al. Longest prefix matching using bloom filters
US7418505B2 (en) IP address lookup using either a hashing table or multiple hash functions
US6434144B1 (en) Multi-level table lookup
CN107528783B (en) IP route caching with two search phases for prefix length
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
US10515015B2 (en) Hash table-based mask length computation for longest prefix match caching
Zhao et al. Exploiting graphics processors for high-performance IP lookup in software routers
Luo et al. A hybrid hardware architecture for high-speed IP lookups and fast route updates
Yu et al. Forwarding engine for fast routing lookups and updates
Jiang et al. Parallel IP lookup using multiple SRAM-based pipelines
Yang et al. Clue: Achieving fast update over compressed table for parallel lookup with reduced dynamic redundancy
Rooney et al. Associative ternary cache for IP routing
Tzeng Routing table partitioning for speedy packet lookups in scalable routers
Baer et al. Memory hierarchy design for a multiprocessor look-up engine
Zec et al. Pushing the envelope: Beyond two billion IP routing lookups per second on commodity CPUs
Jiang et al. Sequence-preserving parallel IP lookup using multiple SRAM-based pipelines
Nie et al. IP address lookup using a dynamic hash function
Jiang et al. Multi-terabit IP lookup using parallel bidirectional pipelines
Hsiao et al. A high-throughput and high-capacity IPv6 routing lookup system
Huang et al. Fast routing table lookup based on deterministic multi-hashing
Rajan et al. A Heterogeneously Segmented Cache architecture for a packet forwarding engine
Fradj et al. Implementation of a cache-based IPv6 lookup system with hashing
Chang et al. Efficient IP routing table lookup scheme
Erdem et al. MIPS extension for a TCAM based parallel architecture for fast IP lookup
Rajan et al. Two-level mapping based cache index selection for packet forwarding engines